Branching Program Lower Bounds

分支程序下界

• 批准号: RGPIN-2019-06288
• 负责人: Edmonds, Jeffrey
• 金额: $ 1.68万
• 依托单位: York University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715985
• 关键词: Branching; Program; Lower; Bounds

Two Topics: I am proposing two quite independent topics: Branching program lower bounds and machine learning. I have 30 years of experience and a great deal of success in the first and the last six months I have taken a few courses and read a few books in the second. In today's job market, students tend to be drawn to Machine Learning rather than Logic (such as Lower Bounds).There is also a large job market for HQP with Machine Learning expertise. In addition to already existing expertise in AI and Deep Learning, York U is starting a new program dedicated to Machine Learning to address this need. My plan is to include training students in this discipline in the future. Lower Bounds in Branching Programs: For both practical and theoretical reasons, we would like to know the minimum amount of time (or space) needed to solve a given computational problem on an input of a given size. An upper bound provides an algorithm that achieves some time bound. A lower bound proves that no algorithm correctly solves the problem faster no matter how clever. Proving lower bounds on general models of computation (eg. in JAVA or a Turing Machine) is beyond our reach. For this reason, researchers often prove lower bounds on weaker modes of computation. The most powerful model of computation measuring the amount of space used by an algorithm is branching programs. We will continue in this important area of fundamental research in order to understand more about the limits of computation. Machine Learning: Computers can now drive cars and find cancer in x-rays. For better or worse, this will change the world (and the job market). Strangely, designing these algorithms is not done by telling the computer what to do or even by understanding what the computer does. The computers learn themselves from lots and lots of data and lots of trial and error. This learning process is more analogous to how brains evolved over billions of years of learning. The machine itself is a neural network which models both the brain circuits, which are great for computing. The only difference with neural networks is that what they compute is determined by weights and small changes in these weights give you small changes in the result of the computation. The process for finding an optimal setting of these weights is analogous to finding the bottom of a valley. If a machine can give the correct answers on randomly chosen training data without simply memorizing, then we can prove that with high probability the same machine will also work well on never seen before instances.

两个主题： 我提出两个相当独立的主题：分支程序较低 bounds边界and machine机learning学习.我有30年的经验， 在第一个和最后六个月的成功交易，我已经采取了 在第二节课上读几门课和几本书。在今天的就业市场上， 学生倾向于被机器学习而不是逻辑（如 作为下限）。HQP也有很大的就业市场， 学习专业知识。除了现有的AI专业知识外， 和深度学习，约克U正在启动一个新的计划，致力于 机器学习可以满足这一需求。我的计划是包括训练 学生在未来的学科。 分支程序中的下限： 出于实际和理论原因，我们希望了解 解决给定问题所需的最少时间（或空间） 在给定大小的输入上的计算问题。一个上界 提供了一个算法，实现了一定的时间限制。一个下界 证明了没有任何算法能更快地正确解决问题， 真聪明。一般计算模型的下界证明 （例如：在Java或图灵机中）是我们无法达到的。为此 因此，研究人员经常证明较弱模式的下限， 计算最强大的计算模型， 一个算法使用的空间量是分支程序。我们将 继续在这一重要的基础研究领域， 更多地了解计算的极限。 机器学习： 计算机现在可以驾驶汽车，并通过x光发现癌症。不管是好是 更糟糕的是，这将改变世界（和就业市场）。奇怪的是， 设计这些算法并不是通过告诉计算机 做什么，甚至理解计算机做什么。计算机 从大量的数据和试验中学习， 错误.这种学习过程更类似于大脑的进化过程 在数十亿年的学习中。机器本身是一个神经 这两种大脑回路的模型网络， 计算的与神经网络的唯一区别是， 计算由权重和这些权重的微小变化决定 给你计算结果的微小变化。过程 找到这些权重的最佳设置类似于 寻找谷底如果一台机器能给出正确的 答案是随机选择的训练数据，而不是简单的记忆， 那么我们可以证明，同一台机器很有可能 在以前从未见过的情况下也能很好地工作。