On the Errors that Learning Machines Will Make. Revision
DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Associated with each learning system there is a class of learnable behaviors. If the target behavior to be acquired is in the learnable class, it will be learned perfectly. If it is outside that class, the machine will only be able to acquire a behavior that approximates the target and it will always make errors. It is desirable for a learning machine to have a large learnable class to maximize the chances of acquiring the unknown behavior and to minimize the expected error when only an approximation is possible. However, it is also desirable to have a small learnable class so that learning can be achieved rapidly. Thus the design of learning machines involves selecting a position on the spectrum minimum error and slow learning time versus larger error and faster learning time. Machines that have fast learning times, relatively small learnable classes, and thus relatively large expected errors are called realization sparse in this paper. It is shown that many common learning systems are of this type including signature tables, linear system models, and conjunctive normal form expression based systems. These studies lead to the concept of an optimum machine which spreads its learnable behaviors across the behavior space in a manner to minimize the expected error. An approximation to such optimum machines is presented and its behavior is compared to the more traditional learning machines.