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.

两个主题： 我提出了两个非常独立的主题：分支计划较低 界限和机器学习。我有30年的经验，很棒 在我接受的第一个和过去六个月中，成功的交易 很少有课程阅读第二本书。在当今的就业市场中 学生倾向于吸引机器学习而不是逻辑（这样 作为下限）。 学习专业知识。除了AI中已经存在的专业知识 深度学习，约克U正在启动一个专门针对的新计划 机器学习以满足这种需求。我的计划是包括培训 将来的这一学科的学生。 分支程序的下限： 出于实际和理论原因，我们想知道 解决给定的最短时间（或空间）所需的时间（或空间） 在给定尺寸的输入上的计算问题。上限 提供了一种实现一定时间绑定的算法。下限 证明没有算法正确地解决问题的速度更快 多么聪明。证明一般计算模型的下限 （例如，在Java或Turing Machine中）是我们无法实现的。为了这 原因，研究人员经常在较弱的模式下证明 计算。测量的最强大的计算模型 算法使用的空间数量是分支程序。我们将 继续在基本研究的这一重要领域，以便 了解有关计算限制的更多信息。 机器学习： 现在，计算机可以驾驶汽车并在X射线检查中找到癌症。更好或更好 更糟糕的是，这将改变世界（以及就业市场）。奇怪的是 设计这些算法不是通过告诉计算机要做什么来完成的 通过了解计算机的作用或什至是通过做什么。计算机 从很多数据和大量试验中学习自己， 错误。这个学习过程与大脑如何发展更类似 超过数十亿年的学习。机器本身是神经 网络对两个大脑电路进行建模，非常适合 计算。与神经网络的唯一区别是他们 计算由这些权重的重量和小变化确定 为您提供计算结果的微小更改。过程 寻找这些权重的最佳设置类似于 找到山谷的底部。如果机器可以给出正确的 关于随机选择的培训数据的答案，而无需简单地记住， 然后，我们可以证明，如果高概率相同的机器将 同样可以很好地效果，从未见过。