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.