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.