Branching Program Lower Bounds

分支程序下界

• 批准号: RGPIN-2019-06288
• 负责人: Edmonds, Jeffrey
• 金额: $ 1.68万
• 依托单位: York University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=752422
• 关键词: 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年的经验，并且在第二次学习了几门课程，并在第二本书中读了几本书。在当今的就业市场中，学生倾向于被机器学习而不是逻辑吸引（例如下限）。在机器学习专业知识的HQP中，HQP也是一个大型的就业市场。除了已经在AI和深度学习中现有的专业知识外，约克U还启动了一个新的计划，致力于机器学习以满足这一需求。我的计划是将来包括在这个学科中培训学生。分支程序中的下限：出于实际和理论原因，我们想知道在给定大小的输入中解决给定的计算问题所需的最短时间（或空间）。上限提供了一种实现一定时间绑定的算法。下边界证明，无论多么聪明，没有算法都能正确解决问题。在一般的计算模型（例如，在Java或Turing Machine中）证明了较低的界限是我们无法实现的。因此，研究人员经常证明计算模式的下限。测量算法使用的空间量的最强大的计算模型是分支程序。我们将继续研究基础研究的这一重要领域，以了解有关计算限制的更多信息。机器学习：计算机现在可以驾驶汽车并在X射线检查中找到癌症。无论好坏，这都会改变世界（以及就业市场）。奇怪的是，设计这些算法不是通过告诉计算机该怎么做甚至通过了解计算机的作用来完成的。计算机从大量数据以及许多反复试验中学习。这个学习过程更类似于大脑在数十亿年的学习中如何发展。该机器本身是一个神经网络，对两个大脑电路都建模，非常适合计算。与神经网络的唯一区别在于，它们计算的内容取决于权重，而这些权重的小变化为您的计算结果提供了很小的变化。找到这些权重的最佳设置的过程类似于找到山谷的底部。如果机器可以在不简单记忆的情况下可以在随机选择的训练数据上给出正确的答案，那么我们可以证明，如果较高的概率，同一机器也可以很好地奏效，那么在实例前从未见过。