Branching Program Lower Bounds

两个主题：我提出了两个相当独立的主题：分支程序下限和机器学习。我有30年的经验，在前六个月和后六个月都取得了很大的成功，第二个月我上了几门课，读了几本书。在当今的就业市场，学生更倾向于机器学习，而不是逻辑(如下限)。拥有机器学习专业知识的HQP也有很大的就业市场。除了已有的人工智能和深度学习方面的专业知识外，约克大学正在启动一个致力于机器学习的新项目，以满足这一需求。我的计划是在未来对学生进行这一学科的培训。分支程序的下限：出于实际和理论上的原因，我们想知道在给定大小的输入上解决给定计算问题所需的最小时间(或空间)。上限提供了一种实现一定时间界限的算法。一个下限证明，无论算法多么聪明，都不会正确地更快地解决问题。证明一般计算模型的下界(例如，Java或图灵机)超出了我们的能力范围。出于这个原因，研究人员经常证明较弱计算模式的下界。衡量算法所用空间量的最强大的计算模型是分支程序。我们将继续这一重要的基础研究领域，以便更多地了解计算的极限。机器学习：计算机现在可以驾驶汽车并通过X光发现癌症。无论是好是坏，这将改变世界(以及就业市场)。奇怪的是，设计这些算法并不是通过告诉计算机做什么，甚至不是通过理解计算机做什么来完成的。计算机从大量的数据和大量的试验和错误中学习自己。这种学习过程更类似于大脑在数十亿年的学习过程中是如何进化的。这台机器本身是一个神经网络，它对大脑的两个电路都进行建模，这对计算非常有用。与神经网络的唯一区别是，它们计算的内容是由权重决定的，这些权重的微小变化会给计算结果带来微小的变化。寻找这些权重的最佳设置的过程类似于寻找谷底。如果一台机器可以在不需要简单记忆的情况下，对随机选择的训练数据给出正确的答案，那么我们可以证明，同样的机器也很有可能在以前从未见过的例子上工作得很好。

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.