Pattern Recognition System Using Support Vectors

This invention relates to learning machines.

The main objective of a learning machine is to learn to recognize as well as possible an unknown pattern, given a set of training examples. Of particular importance in the learning process for a learning machine is the method of deriving a decision function based on the training examples, in order to distinguish representatives of one class from representatives of another class. The derived decision function can be used to recognize unknown patterns.

The ability of a decision system to perform well a particular task depends on several factors such as, the number of examples in the training set, the number of errors in the training set and the complexity of the classifier. Prior art decision systems are predicated on two major approaches, each one with particular limitations and drawbacks.

In an approach called the optimal margin approach, a learning machine determines a decision function which is a weighted sum of the components of the input patterns or a weighted sum of arbitrary predefined functions of the input patterns (e.g. Perceptrons and polynomial classifiers). The weights are determined such that a) the number of training patterns that are misclassified by an optimal margin decision system is minimized, and b) the margin between the correctly classified training patterns and the decision boundary is maximized. The margin is defined as the distance of the closest training patterns to the decision boundary. The weights that optimize the margin are a function of only a subset of all training patterns, called the "supporting patterns". The latter are patterns that are closest to the decision boundary.

The capacity of a decision system using the optimal margin approach or, more specifically, the ability of such a system to solve complex problems is restricted by the number of predefined functions. Accordingly, the number of predefined functions had to be limited for computational reasons, hence, limiting the range of applications of decision systems using the optimal margin approach.

In another approach called "memory-based decision approach" prior art decision systems were designed to allow decision functions (e.g. Radial Basis functions, Potential functions) to be represented by a weighted sum of kernel functions, each kernel function being itself a function of two patterns, namely, an input pattern and a memorized pattern (also called "memory" or "prototype"). In this approach, however, prototype patterns and weights are determined in a suboptimal way, thereby limiting the ability of the decision system to perform complex tasks.

The present invention is directed to a method which a) takes advantage of the dual representation mathematical principle which permits some decision functions that are weighted sums of arbitrary predefined functions to be represented as memory-based decision function and vice versa, and b) allows design of memory-based decision systems with optimum margin in which weights and prototypes of training patterns of a memory-based decision function are determined such that the corresponding dual decision function satisfies the criterion of margin optimality.

In an embodiment of the principles of the invention, input data that may be represented, for example, by a set of vectors in n-dimensional space, are classified with decision rules that may be graphically represented by non-linear decision surfaces. In accordance with the invention, the classification is facilitated by transforming the input patterns to a new space using, for example, convolution of dot products, for linear separation by at least one optimal hyperplane represented by a decision function in the transformed space. According to one aspect of the invention, during the training process, training patterns or dot-product-transformed training patterns that are unused to determine the decision function, are identified and removed to allow the training process to be restarted with the remaining training patterns.

In a specific example implementing the principles of the invention, a processor, such as a UNIX workstation includes a memory which stores training patterns data which may be for example, bit-mapped pixel images data, and a classification program which is designed to associate input data (received by the workstation) with a specific class. This association is achieved by automatically attributing to the same class all the patterns that are on the same side of the optimal hyperplane (or hyperplanes) in the transformed space.

According to one of the aspects of the invention optimal decision hyperplane(s) is identified by simultaneously a) identifying support vectors from the training patterns data, and b) assigning weights to the support vectors through the mapping of the training patterns data into high dimension feature space. The steps described in a) and b) are performed jointly by a computer program in a manner that achieves correct classification of the training patterns while leaving the largest possible margin between the training patterns and the decision hyperplane in the feature space. Thus, input data received by the workstation from a source are classified in that workstation to allow the resulting classified data to be delivered to an output device. As a result, training patterns are assigned to the correct side of the decision hyperplane and as far as possible from the decision hyperplane in the feature space. It is mathematically provable that an automatic classification system built according to that principle has high probability to perform better than other systems on any particular classification task (such as speech or handwriting recognition).

Advantageously, our invention permits to build rapidly such an automatic classification system on a computer, given training patterns and regardless of the high dimension of selected feature space.

Advantageously, decision systems that are equivalent to linear classifiers in large multidimensional space, (10.sup.12, 10.sup.16 dimensions), can be derived using a small amount of supporting patterns. Thus, decision systems of arbitrary capacity with both good speed and classification accuracy can be obtained. For example, polynomial decision functions of any order can be optimally selected. Furthermore, the number of computations required to classify patterns is only proportional to the number of supporting patterns and the number of inputs to the system when the kernel functions are properly selected.

FIG. 1 illustrates a prior art decision system in which two classes in a training set are linearly separated by a decision boundary;

FIGS. 2 and 3 show examples of non-linear decision boundaries obtained by using the maximum margin memory-based method;

FIG. 4 shows some hardware components that may be used to implement the classification system of the invention; and

FIG. 5 is a flow diagram of programmed instructions executed by the processor of FIG. 4 to implement the principles of the invention.

FIG. 1 shows a decision system in which two classes in a training set are linearly separated by a decision boundary. FIG. 1 graphically illustrates a training set and a linear decision boundary which yields the best generalization performance. FIG. 1 is presented in this example to facilitate a better understanding of the optimal margin technique that is used in the decision system of the invention. Shown in FIG. 1 is a training set extracted from two classes A and B. The training examples from class A are illustrated in small rectangular blocks while the training examples from class B are represented by small circles. The area 103 that is delimited by KLMNOP represents the largest possible margin between the decision boundary QR and the training patterns on either side. That margin provides the best generalization performance for a classifier trained with the training set of FIG. 1, as proved mathematically in further detail below. Graphically, this statement appears intuitively justifiable since a new example from class A is likely to fall within or near the convex envelope 101 of the examples of class A (and similarly for class B). By providing the largest possible "safety" margin, the chances are minimized that examples from class A and B cross the border to the wrong side.

An important property of the maximum margin solution is that it is only dependent upon a restricted number of training examples, called supporting patterns (or informative patterns). In FIG. 1, the supporting patterns as represented by those examples that lie on the margin and, therefore, are closest to the decision boundary. The number m of linearly independent supporting patterns satisfies the inequality: m.ltoreq.min(N+1,p). In this equation, (N+1) is the number of adjustable parameters and equals the well-known Vapnik-Chervonenkis dimension (VC-dimension), and p is the number of training examples. The generalization error is bounded by m/p and, therefore, m is a measure of the complexity of the learning problem. Because m is bounded by p and is generally a lot smaller than p, the maximum margin solution obtains good generalization even when the problem is grossly underdetermined, i.e. the number of training patterns p is much smaller than the number of adjustable parameters, N+1. As described in further detail below, the existence of supporting patterns is advantageous for computational reasons as well.

FIGS. 2 and 3 show examples of decision boundaries obtained by using the memory-based maximum margin technique. The decision boundaries shown in FIGS. 2 and 3 are derived (as explained in further detail below) by mapping the examples in set A and B to another space. FIG. 2 is an illustration of a second order polynomial decision boundary while FIG. 3 is an illustration of a Radial Basis Function decision boundary. The rainbow-shaped area 201 shown in FIG. 2 and the criss-crossed area of FIG. 3 represent the margin area 301 projected into the input space. The method of deriving the decision functions that yield the optimal margins in FIGS. 1, 2, and 3 are explained immediately below.

An optimal margin decision system designed in accordance with the invention, finds a decision function for pattern vectors x of dimension n belonging to either of two classes A and B. The input to the decision system is a set of p examples x.sub.i with labels y.sub.i

where

From these training examples the decision system finds the parameters of the decision function D (x) during a learning phase. After training, the classification of unknown patterns is predicted according to the following rule:

The equation D(x)=0 determines the decision boundary. The decision functions must be linear in their parameters but are not restricted to linear dependencies of x. These functions can be expressed either in direct, or in dual space. The direct space notation is identical to the Perceptron decision function: ##EQU1## In this equation the .phi..sub.i are predefined functions of x, and the w.sub.i and b are the adjustable parameters of the decision function. Polynomial classifiers are a special case of Perceptrons for which .phi..sub.i (x) are products of components of x. In the dual space, the decision functions are of the form ##EQU2## The coefficients .alpha..sub.k are the parameters to be adjusted and the x.sub.k are the training patterns. The function K is a predefined kernel which can be, for example, a potential function or any Radial Basis Function Under certain conditions, symmetric kernels possess finite or infinite series expansions of the form ##EQU3## In particular, the kernel K(x, x')=(x.multidot.x'+1).sup.q corresponds to a polynomial expansion .phi.b(x) of order q. Other examples of kernel functions include

Of particular importance in these examples is the fact that those kernel functions can be evaluated with a number of computations proportional to the number n of inputs that is the dimension of vector x.

Provided that the expansion stated in Equation (5) exists, Equations (3) and (4) are dual representations of the same decision function and ##EQU4##

The parameters w.sub.i are called direct parameters, and the .alpha..sub.k are referred to as dual parameters.

In this embodiment, this decision system is extended to train classifiers linear in their parameters. First, the margin between the class boundary and the training patterns is formulated in the direct space. This problem description is then transformed into the dual space by means of the Lagrangian. The resulting problem is that of maximizing a quadratic form with constraints and is amenable to efficient numeric optimization decision system.

In order to maximize the margin in the direct space, the decision function is expressed as:

where w and .phi.(x) are N dimensional vectors and b is a bias. That decision function defines a separating hyperplane in .phi.-space. The distance between this hyperplane and pattern x is D(x)/.vertline..vertline.w.vertline..vertline.. Assuming that a separation of the training set with margin M between the class boundary and the training patterns exists, all training patterns fulfill the following inequality: ##EQU5## The objective of the decision system is to find the parameter vector w that maximizes M: ##EQU6## subject to: y.sub.k D(x.sub.k).gtoreq.M, k=1,2, . . . , p.

The bound M* is attained for those patterns satisfying ##EQU7## These patterns are called the supporting patterns of the decision boundary.

The problem of finding a hyperplane in .phi.-space with maximum margin is therefore a minimax problem of the form: ##EQU8## The norm of the parameter vector in equations 9 and 11 is fixed to pick one of an infinite number of solutions that differ only in scaling. Instead of fixing the norm of w to take care of the scaling problem, the product of the margin M and the norm of a weight vector w can be fixed.

Thus, maximizing the margin M is equivalent to minimizing the norm .vertline..vertline.w.vertline..vertline.. If the training data are not linearly separable, the maximum margin may be negative. In this case, M.vertline..vertline.w.vertline..vertline.=-1 is imposed. Maximizing the margin is then equivalent to maximizing .vertline..vertline.w.vertline..vertline.. If the training data are linearly separable, the problem of finding a maximum margin separating hyperplane w* stated in Equation (9) reduces to solving the following quadratic problem: ##EQU9## under conditions y.sub.k D(x.sub.k).gtoreq.1, k=1,2, . . . , p.

The maximum margin is M*=1/.vertline..vertline.w*.vertline..vertline..

In principle the problem stated in Equation 13 can be solved directly with numerical techniques. However, this approach is impractical when the dimensionality of the .phi.-space is large or infinite. Moreover, no information is gained about the supporting patterns.

The problem of Equation (13) can be transformed into the dual space by means of the Lagrangian ##EQU10## subject to .alpha..sub.k .gtoreq.0, k=1, 2, . . ., p. The factors .alpha..sub.k are called Lagrange multipliers or Kuhn-Tucker coefficients and satisfy the conditions

.alpha..sub.k (y.sub.k D(x.sub.k)-1)=0, k=1,2, . . . , p. (15)

The factor one half has been included for cosmetic reasons; it does not change the solution.

The optimization problem of Equation 13 is equivalent to searching a saddle point of the function L (w, b, .alpha.). This saddle point is the minimum of L (w, b, .alpha.) with respect to w, and a maximum with respect to .alpha.(.alpha..sub.k .gtoreq.0). At the solution, the following necessary condition is met: ##EQU11## The patterns which satisfy y.sub.k D(x.sub.k)=1 are the supporting patterns. According to equation 16 the vector w* that specifies the hyperplane with maximum margin is a linear combination of only the supporting patterns, which are those patterns for which .alpha..sub.k *.apprxeq.0. Usually the number of supporting patterns is much smaller than the number p of patterns in the training set.

The dependence of the Lagrangian L(w, b, .alpha.) on the weight vector w is removed by substituting the expansion of w* given by Equation 16 for w. Further transformations result in a Lagrangian which is a function of the parameters .alpha. and the bias b only: ##EQU12##

subject to .alpha..sub.k .gtoreq.0, k=1, 2 . . ., p.

Here H is a square matrix of size p.times.p with elements H.sub.ki y.sub.k y.sub.i K(x.sub.k x.sub.i)

In order for a unique solution to exist, H must be positive definite. For fixed bias b, the solution .alpha.* is obtained by maximizing J(.alpha., b) under the conditions .alpha..sub.k .gtoreq.0. Based on equations 7 and 16, the resulting decision function is of the form ##EQU13## where only the supporting patterns appear in the sum with nonzero weight.

The choice of the bias b gives rise to several variants of the decision system. Two variants are considered in this embodiment. In the first variant, the bias can be fixed a priori and not subjected to training. In the second variant, the function represented by Equation 17 can be optimized with respect to w and b. This approach gives the largest possible margin M*.

In both cases the solution is found with standard nonlinear optimization decision system for quadratic forms with linear constraints. The second approach gives the largest possible margin. There is no guarantee, however, that the second solution exhibits also the best generalization performance.

One possible strategy to optimize the margin with respect to both w and b allows Equation 17 to be solved for differences of pattern vectors to obtain .alpha.* independent of the bias, which is computed subsequently. The margin in .phi.-space is maximized when the decision boundary is halfway between the two classes. Hence the bias b* is obtained by applying Equation 18 to two arbitrary supporting patterns x.sub.A .epsilon. class A and x.sub.B .epsilon. class B and taking into account that D(x.sub.A)=1 and D(x.sub.B)=-1. ##EQU14##

The dimension of problem 17 equals the size of the training set, p. To avoid the need to solve a dual problem of exceedingly large dimensionality, the training data is divided into chunks that are processed iteratively. The maximum margin hypersurface is constructed for the first chunk and a new training set is formed consisting of the supporting patterns from the solution and those patterns x.sub.k in the second chunk of the training set for which y.sub.k D(x.sub.k)<1-.epsilon.. A new classifier is trained and used to construct a training set consisting of supporting patterns and examples from the first three chunks which satisfy y.sub.k D(x.sub.k)<1-.epsilon.. This process is repeated until the entire training set is separated. In an actual implementation of the principles of the invention, training data are received in the optimal margin classification via input device 401 of FIG. 4 which forwards the training data to processor 402. Input device 401 may be for example, a data reading device, such as a magnetic disk arranged to transfer training data stored therein to processor 402. The latter includes a memory 403 that stores the programmed instructions for the classification system that are illustratively shown in Appendices 1 and 2. Processor 402 may be implemented using, for example a workstation which runs under the UNIX.RTM. operating system to execute the programmed instructions in memory 403, using the processing power of Central Processing Unit (CPU) 404 in order to define decision rules for the classification of input data. Upon assigning input data to a particular class, processor 402 forwards the classified data to output device 405 which may be, for example, a display monitor or a processor capable of executing instructions of specialized graphics software to represent a multidimensional hyperplane.

FIG. 5 shows a flow diagram of instructions executed by processor 402 to classify input data. Upon command from a user via input device 401, processor 402, initiates the process contemplated by the invention by selecting a type of learning machine for the classification system, as indicated in step 501. The type of learning machine selected depends on the kernel function picked (high order polynomial or radial basis function, to name a few), and may be, for example, a neural network. Thus, when processor 402 receives in step 502, a set of input patterns from input device 401, processor 402 in step 503, retrieves a set of training patterns contained in memory 403. Thereafter, processor 402 in step 504, derives a weighted sum of one or more selected associations between the input patterns and the training patterns. This association may take the form of the kernel functions described above. In step 505, processor 402 determines the decision function for the classification task by identifying weighting parameters for the weighted sum. These weighting parameters permit processor 402 to identify supporting patterns that are used in the determination of the decision surface. Armed with the identified supporting patterns and the associated wighting parameters, processor 402 then, in step 506, uses the decision function to classify input data received from input device 401.

FIG. 5 shows a flow diagram of instructions executed by processor 402 to classify input data. Upon command from a user via input device 401, processor 402, initiates the process contemplated by the invention by selecting a type of learning machine for the classification system, as indicated in step 501. The type of learning machine selected depends on the kernel function picked (high order polynomial or radial basis function, to name a few), and may be, for example, a neural network. Thus, when processor 402 receives in step 502, a set of input patterns from input device 401, processor 402 in step 503, retrieves a set of training patterns contained in memory 403. Thereafter, processor 402 in step 504, derives a weighted sum of one or more selected associations between the input patterns and the training patterns. This association may take the form of the kernel functions described above. In step 505, processor 402 determines the decision function for the classification task by identifying weighting parameters for the weighted sum. These weighting parameters permit processor 402 to identify supporting patterns that are used in the determination of the decision surface. Armed with the identified supporting patterns and the associated wighting parameters, processor 402 then, in step 506, uses the decision function to classify input data received from input device 401.

A decision system designed according to the principles of the invention exhibit some interesting properties. Some of these properties are described below.

Since maximizing the margin between the decision boundary and the training patterns is equivalent to maximizing a quadratic form in the positive quadrant, there are no local minima and the solution is always unique if H has full rank. At the optimum ##EQU15## The uniqueness of the solution is a consequence of the maximum margin cost function and represents an important advantage over other decision systems for which the solution depends on the initial conditions or other parameters that are difficult to control.

Another benefit of the maximum margin objective is its insensitivity to small changes of the parameters w or .alpha.. Since the decision function D(x) is a linear function of w in the direct space, and of .alpha. in the dual space, the probability of misclassifications due to parameter variations of the components of these vectors is minimized for maximum margin. The robustness of the solution--and potentially its generalization performance--can be increased further by omitting some supporting patterns from the solution. Preferably, a selected subset of supporting patterns can be removed from the training set and the solution recomputed with this newly redefined training set. Equation 20 indicates that the largest increase in the maximum margin M* occurs when the supporting patterns with largest .alpha..sub.k * are eliminated. The elimination can be performed automatically or with assistance from a supervisor. To facilitate the elimination procedure, patterns can be ranked according to the value of the coefficient .alpha..sub.k *. This feature gives rise to other important uses of the optimum margin decision system in database cleaning applications.

Another property of the decision system of the invention is that the optimum margin decision system performs automatic capacity tuning of the decision function to achieve good generalization. An estimate for an upper bound of the generalization error is obtained with the "leave-one-out" method: A pattern x.sub.k is removed from the training set. A classifier is then trained on the remaining patterns and tested on x.sub.k. This process is repeated for all p training patterns. The generalization error is estimated by the ratio of misclassified patterns over p. For a maximum margin classifier, two cases arise. In the first case if x.sub.k is not a supporting pattern, the decision boundary is unchanged and x.sub.k will be classified correctly. In the second case, if x.sub.k is a supporting pattern, two possibilities exist. In the first possibility, the pattern x.sub.k is linearly dependent on the other supporting patterns. In this case it will be classified correctly. In the second possibility, x.sub.k is linearly independent from the other supporting patterns. In this case the outcome is uncertain. In the worst case m' linearly independent supporting patterns are misclassified when they are omitted from the training data.

Hence the frequency of errors obtained by this method is at most m'/p, and has no direct relationship with the number of adjustable parameters. The number of linearly independent supporting patterns m' itself is bounded by min(N,p). This suggests that the number of supporting patterns is related to an effective capacity of the classifier that is usually much smaller than the VC-dimension, N+1.

In polynomial classifiers, for example, N.apprxeq.n.sup.q, where n is the dimension of x-space and q is the order of the polynomial. In practice, m.ltoreq.p<<N, i.e. the number of supporting patterns is much smaller than the dimension of the .phi.-space. The capacity tuning realized by the maximum margin decision system is essential to get generalization with high-order polynomial classifiers. In addition, further capacity tuning can be achieved by adjusting certain parameters of the kernel functions. For example, the order q in the polynomial classifier or the parameter .gamma. in the Radial Basis Function can be tuned in order to achieve better classification performance.

Appendices 1 and 2 are computer program listings representing an illustrative implementation of a decision system designed in accordance with the invention. The program in Appendix 1 is written in the generally known C computer language and is used to derive an optimal margin decision function. The program in Appendix 2 is written in LISP and is the user interface for input and output operations. The program in Appendix 1 can be compiled and executed on Sun Microsystems workstations running the well-known UNIX operating system. The LISP program in Appendix 2 requires a learning machine LISP interpreter to be executed. These computer programs are copyrighted programs owned by the American Telephone and Telegraph Co. (Copyright 1993 American Telephone and Telegraph Co.) and are not to be copied except in connection with making paper copies of this patent. ##SPC1##