Article Preview
TopI. Introduction
The field of Artificial Neural Networks has been dramatically expanding over the past decades (Bishop, 1996; Haykin, 1999; Perlovsky, 2001). Neural networks have been established as powerful tools in the areas of pattern recognition, function approximation, and control, to name just a few. The latest expansion is mostly due to the advances in the development of efficient learning algorithms for feed-forward and recurrent architectures. Despite the successes, the neural networks, along with the other computing paradigms, run into serious limitations as the size of problems being tackled increases. Going beyond the neural networks paradigm, modeling complex systems with methods of artificial intelligence, pattern recognition, or modeling processes in the mind encountered computational complexity in many applications. The fundamental principles of artificial intelligence and learning were summarized in Perlovsky (2001), Cherkassky and Mulier (2007), and Mitchell (1997).
Consider a simple object perception that involves signals from sensory organs and internal mind’s representations (memories) of objects. During perception, the mind associates subsets of sensor signals corresponding to objects with representations of object. This produces object recognition; it activates brain signals leading to mental and behavioral responses, which constitutes understanding.
Mathematical modeling of the very first recognition step in this seemingly simple association-recognition-understanding process met a number of difficulties over decades. These difficulties were first identified in pattern recognition and classification research in the 1960s and were named “the curse of dimensionality” (Bellman, 1961). It seemed that learning algorithms and neural networks could learn solutions to any problem ‘on their own’, if provided with a sufficient number of training examples. The following thirty years of developing learning algorithms led to a conclusion that the required number of training examples often was combinatorially large. Self-learning pattern recognition and neural network approaches encountered combinatorial complexity (CC) of learning requirements. Various ways of overcoming CC in neural networks include techniques like pruning, regularization, weight sharing. For examples of such approaches see (LeCun et al., 1990; Ilin et al., 2008).
To overcome CC of learning, rule systems were proposed in the 1970’s (Minsky, 1975; Winston, 1984). A guiding idea was that rules would capture the required knowledge and eliminate a need for learning. However in the presence of variability, the number of rules grew, and rules became contingent on other rules causing combinations of rules to be considered. Thus rule systems encountered CC of rules.
Model systems were proposed in the 1980’s to combine the advantages of a priori knowledge and learning. Model systems used models depending on adaptive parameters. The knowledge was encapsulated in the models, whereas unknown aspects of particular situations were to be learned by fitting the model parameters. Fitting models to data required selecting data subsets corresponding to various models. The number of subsets, however, is combinatorially large. A general popular algorithm for fitting models to the data, multiple hypotheses testing (Singer et al., 1974) is known to face CC of computations. Thus, model-based approaches encountered computational CC (Perlovsky et al., 1998b).
Computational difficulties were summarized under the notion of CC in (Perlovsky, 1998a). In general, CC refers to multiple combinations of various elements in a complex system; for example, recognition of a scene often requires concurrent recognition of its multiple elements that could be encountered in various combinations. CC is prohibitive because the number of combinations is very large: for example, consider 100 elements (not too large a number); the total number of subsets of a set with 100 elements is 2100, exceeding the number of all elementary events in life of the Universe; no computer would ever be able to compute that many combinations.