Branching Program Lower Bounds

分支程序下界

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