Pattern Classifiers and Trainable Machines

Just as the successful invention of the airplane stimulated the study of aerodynamics, the modern digital computer has stimulated the study of intelligence and learning.

Much of the analysis of trainable classifiers is simplified if it is known that every pair of class regions encountered by the classifier can be separated by a linear hypersurface. In augmented feature space such a surface is determined by an equation of the form

Gradient descent as a technique for finding the minimum of a loss function J(v) was introduced in Section 2.10. Recall that the technique consists of finding the gradient ∇ J(v) and then adjusting the parameter vector v so that the change in v is in the direction of the negative of the gradient.

In this chapter we describe several training procedures based on the gradient and stochastic approximation techniques of the preceding chapter. Although our discussion in this chapter is restricted to two-class cases, the techniques may be extended to multiple-class cases by using the concepts of Section 2.6. The training procedures of this chapter apply to pairs of classes that are linearly nonseparable, i.e., that are not linearly separable, as well as those that are linearly separable. Linearly nonseparable classes include pairs of classes that are separable but not by a hyperplane, as well as pairs of classes that overlap.

In Chapter 2, we derived the convergence under separability property of the proportional increment training procedure. As interesting as this property is, convergence is usually of less practical importance than a good estimate of the performance of the classifier as a function of training length. Indeed, it is sometimes possible to obtain a noncovergent training procedure that performs better over a finite training period than a convergent training procedure on the same input data. This situation has motivated much of the research on the learning dynamics of trainable classifiers.

In Chapter 6 we showed how the transient and steady-state behavior of single-feature training procedures can be analyzed by Markov chains. However in most training procedures the state space is multidimensional and the density of states is indefinitely large, thereby making finite Markov chain models inappropriate. Consider, for example, the proportional increment training procedure described by Equations (2.13) and (2.14) in Chapter 2. (In this chapter, we replace r(n) by the random variable R (n).) The augmented weight vector V(n) takes the role of a state, in the sense that the future statistical behavior of V(n + M), m ≥ 0, is completely determined from a knowledge of the present weight vector (i.e., V(n)), the constituent densities, and the training procedure. The motion of V(n) is similar to Brownian motion, as illustrated in Figure 7.1, so that the set of possible values of V(n) is infinitely dense. Thus V(n) cannot be a Markov chain in this case. Yet V(n) is a Markov process, i.e., since (a) the proportional increment training procedure generates V(n + 1) from ω(n), R(n), and V(n), (b) the statistics of R(n) depend on V(n) and ω(n), and (c) the random variables {ω(n)} are statistically independent.