Branching Program Lower Bounds

分支程序下界

• 批准号: RGPIN-2019-06288
• 负责人: Edmonds, Jeffrey
• 金额: $ 1.68万
• 依托单位: York University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=738818
• 关键词: 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也有很大的就业市场。除了现有的人工智能和深度学习专业知识外，约克U正在启动一个专门用于机器学习的新项目，以满足这一需求。我的计划是在将来培养这门学科的学生。分支程序中的下界：出于实践和理论的原因，我们想知道在给定大小的输入上解决给定计算问题所需的最小时间（或空间）。上界提供了一种实现某个时间界限的算法。下限证明，没有任何算法能更快地正确解决问题，无论它有多聪明。证明一般计算模型的下界（例如，在Java或图灵机中）是我们无法达到的。出于这个原因，研究人员经常在较弱的计算模式上证明下界。衡量一个算法所使用的空间量的最强大的计算模型是分支程序。我们将继续在这个重要的基础研究领域，以了解更多关于计算的限制。机器学习：计算机现在可以驾驶汽车，并在X射线中发现癌症。不管是好是坏，这将改变世界（和就业市场）。奇怪的是，设计这些算法并不是通过告诉计算机做什么，甚至不是通过理解计算机做什么来完成的。计算机从大量的数据和大量的试验和错误中学习自己。这种学习过程更类似于大脑在数十亿年的学习中进化的过程。机器本身是一个神经网络，它模拟了大脑回路，这对计算很有帮助。与神经网络的唯一区别是，它们的计算是由权重决定的，这些权重的微小变化会给计算结果带来微小的变化。寻找这些权重的最佳设置的过程类似于寻找谷底。如果一台机器可以在随机选择的训练数据上给出正确的答案，而不需要简单的记忆，那么我们可以证明，同一台机器很有可能在以前从未见过的情况下也能很好地工作。