Mathematical Sciences: Complexity Theoretic Applications of Functional Analysis

研究了解析复杂性理论及其在神经网络中的应用，并利用随机过程模拟神经网络组态空间上的半群。该项目专注于前馈神经网络学习的复杂性理论和学习算法的最优性。这种算法适合于复杂性理论分析，并将研究神经网络学习时间下界的存在性和特征。这将涉及到构建工作前馈学习网络的可行性问题。这些问题将主要从功能分析的方法来研究。研究者还将研究半群和统计力学方法来寻找神经网络中的全局能量最小值（有助于最小化学习算法中的误差）。这项工作的主要目的是开发更快速的半群模拟方法（与模拟退火过程相关），以优化神经网络中的权重。分析复杂性的工作将涉及研究算法的最坏情况性质与其平均情况特征之间的关系。它还将集中于随机化（例如，蒙特卡罗方法）在打破连续数学问题的难解性中的作用。复杂性理论的目标是分析和理解解决数学问题的难度（在时间和计算量方面）。某些看似简单的问题在受到攻击（比如在计算机上）时，会变得异常复杂。在复杂性理论中有一个棘手的概念，也就是说，一个问题是如此困难，以至于即使使用人们可以想象到的所有计算资源（现在存在或将来存在），这个问题仍然无法解决。研究者研究这些概念，特别是在神经网络的背景下。神经网络领域涉及对与大脑神经元非常相似的计算元素的研究，其最终目标是展示如何能够复制像大脑这样的自然智能系统的功能。近年来，这一领域已经得到了相当多的数学研究，而且复杂性理论在这一领域有一些真正的发展潜力。这是因为已经证明，原则上神经网络可以解决任何可以想象的问题，但这种解决方案需要多长时间（或需要多少神经元）的问题非常微妙和困难。特别重要的是，要知道在目前的神经网络范式中，哪些所谓的智能问题是可处理的。这里的数学问题可以很自然地提出，研究者将研究它们的意义和答案。他还将学习使用随机过程模拟等技术对神经网络建模的其他方法。此外，研究者还将研究与上述可追溯性问题相关的其他复杂性理论问题。

The investigator studies analytic complexity theory and its applications to neural networks, and the use of stochastic processes to simulate semigroups on neural network configuration spaces. The project focusses on the complexity theory of learning for feed-forward neural networks and on the optimality of learning algorithms. Such algorithms are amenable to complexity theoretic analyses, and existence and characteristics of lower bounds on learning times for neural networks will be studied. This will bear on questions regarding feasibility of constructing working feedforward learning networks. The problems will be studied largely from a functional analytic approach. The investigator will also study semigroup and statistical mechanics approaches to finding global energy minima in neural nets (useful in minimizing the error in learning algorithms). The main aim of this work is to develop more rapid semigroup simulation methods (related to the simulated annealing process) for optimizing weights in neural nets. Work in analytic complexity will involve investigation of relationships of worst-case properties of algorithms to their average case characteristics. It will also concentrate on the role of randomization (e.g., Monte Carlo methods) in breaking intractability of continuous mathematical problems. Complexity theory has as its goal the analysis and understanding of the difficulty (in terms of time and amount of computation) of solving mathematical problems. Certain simple-looking problems are surprisingly complex when they are attacked, say, on the computer. There is in complexity theory the notion of intractability, namely, the phenomenon in which a problem is so difficult that, even with all of the computing resources one can imagine (existing now or in the future), the problem is nevertheless unsolvable. The investigator studies these notions, especially in the context of neural networks. The area of neural networks involves the study of computing elements connected very much like neurons in the brain, and has the ultimate goal of showing how one might be able to duplicate the functions of naturally intelligent systems like the brain. This field has been approached quite mathematically in recent years, and is an area in which complexity theory has some real potential for inroads. This is because it has been shown that in principle neural networks can solve essentially any problem imaginable, but the question of how long such solutions will take (or how many neurons they will require) is very subtle and difficult. In particular, it is important to know which so-called intelligence problems are tractable in the present neural network paradigms. The mathematical questions here can be framed quite naturally, and the investigator will study their meaning and answers. He will also study other methods of modeling neural networks using techniques such as simulation via random processes. In addition, the investigator will study other complexity theoretic issues related to the above problems of tractability.