A theory of adaptive systems

This paper presents a survey of some recent results in the theory of adaptive decision making systems. When the statistics describing a given observation are completely known a decision rule merely provides a fixed mapping from the observation space to the space of possible actions. When the statistics are unknown, however, it is possible to employ a sequence of observations in order to improve the average performance of the system on each observation. Such a system may be said to "learn" the statistical description of the observations it is taking. The learning observations may be presented to the system either with or without information concerning the specific situation which gave rise to the observations. For example in character recognition the observations are usually presented to the system together with information specifying each learning observation as a sample of some specific character; in random channel applications on the other hand the more common situation is one in which the receiver obtains observations of previous transmissions through the channel but the receiver does not know which transmitter signal gave rise to each observation. The first situation is known as learning with a teacher while the second is known as learning without a teacher. Iterative solutions suitable for machine implementation will be presented for both of these problems. The question of the size of the system or the amount of the computation necessary to implement these adaptive systems will be emphasized. For any given amount of data to be processed (i.e., for any given dimension of the observation) there exist computational techniques for simplifying the calculations to be performed. The use of sufficient statistics can greatly reduce the amount of storage necessary for the system. In addition it is sometimes possible to evaluate the effect of taking varying amounts of data (i.e., of varying the dimemsion at the observation). For example, one surprising result is that inc- easing the dimension of the observation (i.e., taking additional measurements) may result in a degredation of the average performance of the adaptive system.