ON THE ERRORS THAT LEARNING MACHINES WILL MAKE

Associated with each learning system there is a class of learnable beh aviors. If the target behavior to be acquired is in the learnable clas s, it will be learned perfectly. If it is outside that class, the mach ine will only be able to acquire a behavior that approximates the targ et and it will always make errors. It is desirable for a learning mach ine to have a large learnable class to maximize the chances of acquiri ng the unknown behavior and to minimize the expected error when only a n approximation is possible. However, it is also desirable to have a s mall learnable class so that learning can be achieved rapidly. Thus th e design of learning machines involves selecting a position on the spe ctrum: minimum error and slow learning time versus larger error and fa ster learning time. A computational method is given for finding where a given learning machine is on this spectrum. Machines that have fast learning times, relatively small learnable classes, and thus relativel y large expected errors are called realization sparse in this article. These machines do little better than a random coin flipping algorithm in many situations. It is shown that many common learning systems are of this type including signature tables, linear system models, and co njunctive normal form expression based systems. These studies lead to the concept of an ''optimum'' machine which spreads its learnable beha viors across the behavior space in a manner to minimize the expected e rror. An approximation to such optimum machines is presented and its b ehavior is compared to the more traditional learning machines. (C) 199 4 John Wiley & Sons, Inc.