Mathematical Sciences: Complexity Theoretic Applications of Functional Analysis

数学科学：泛函分析的复杂性理论应用

• 批准号: 9109042
• 负责人: Mark Kon
• 金额: $ 1.5万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1995-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9109042&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Complexity; Theoretic; Applications

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.

研究者研究分析复杂性理论及其 神经网络的应用，以及随机 在神经网络结构上模拟半群的过程 空间. 该项目侧重于复杂性理论， 前馈神经网络的学习及其最优性 学习算法。 这种算法适用于 复杂性理论分析，复杂性的存在与特征 神经网络学习时间的下限将是 研究了 这将影响到关于是否可行的问题， 构建工作前馈学习网络。 的问题 将主要从功能分析方法进行研究。 的 研究者还将学习半群和统计力学 在神经网络中找到全局能量最小值的方法（有用 最小化学习算法中的误差）。 的主要目的 本文的工作是发展更快速的半群模拟方法 （与模拟退火过程相关）用于优化 神经网络中的权重 分析复杂性的工作将涉及 最坏情况下性能的关系的研究 算法的平均情况下的特点。 它还将 专注于随机化的作用（例如，蒙特卡罗 方法）在突破连续数学难题中的应用 问题 复杂性理论的目标是分析和 理解困难（在时间和数量方面） 计算）解决数学问题。 某些 看起来简单的问题，当它们 比如说在电脑上被攻击 在复杂性理论中 棘手的概念，即，一个现象， 问题是如此困难，即使所有的计算 我们可以想象的资源（现在或将来）， 问题仍然是无法解决的。 研究者研究 这些概念，特别是在神经网络的背景下。 的 神经网络领域涉及计算元素的研究 连接非常像大脑中的神经元，并且具有 最终目标是展示如何能够复制 大脑等自然智能系统的功能。 这 近年来，人们已经用数学的方法来研究这个领域， 这是复杂性理论具有真实的潜力的领域 来入侵 这是因为已经表明，原则上 神经网络基本上可以解决任何可以想象到的问题， 这些解决方案需要多长时间（或多少）的问题， 它们将需要的神经元）是非常微妙和困难的。 在 特别是，重要的是要知道哪些所谓的智能 问题在当前的神经网络范例中是易处理的。 这里的数学问题可以很自然地构建， 调查员会研究他们的意思和答案。 他 我还将研究其他的神经网络建模方法， 例如通过随机过程进行模拟的技术。 此外，本发明还提供了一种方法， 研究者将研究其他复杂性理论问题 与上述易处理性问题有关。