JPH10320370A - Pattern recognition method by integrating multiple discriminant functions - Google Patents

Abstract

(57) [Summary] (With correction) [Problem] To perform pattern recognition by integrating a plurality of identification functions. SOLUTION: M kinds of discriminant functions prepared in advance are individually classified into N kinds of discriminant functions using N sets of training data composed of pairs of feature vectors and classes to which the feature vectors belong. To learn, M kinds of level 0
A discriminant function is constructed, and one set of training data is sequentially extracted from the N sets of training data.
−1 sets of training data are used to newly learn M kinds of discriminant functions, M kinds of level 1 discriminant functions are constructed for each class, and then M kinds of level 1 discriminants for one set of extracted data A total N consisting of a pair of a KM-dimensional vector composed of the output values of the function and a class label of the extracted data
A set of level 1 data is formed, and a new discriminant function is formed as a linear sum of the outputs of the learned discriminant functions.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a pattern recognition method by integrating a plurality of discriminant functions, which can realize nonparametric pattern recognition without assuming a probability distribution of data.

[0002]

2. Description of the Related Art First, consider the problem of classifying a feature vector x into one of K classes. At this time, a function f ^(k) (x), k = 1,...
^(k) A method of determining the class having the maximum value of (x) as the class of the feature vector x is called an identification function method, and the function used at this time is called an identification function.

That is, the class determination by the discriminant function is

(Equation 1) I can write Here, C (x) represents the class of the feature vector x. Thus, one classifier is composed of K discriminant functions.

In the discriminant function method, first, a discriminant function is determined parametrically, and then parameters of the discriminant function are determined using training data consisting of a feature vector and its class label so that the training data is recognized as correctly as possible. Is estimated. This parameter estimation process is called a learning process of the discriminant function.

[0005] As the simplest identification function, there is a linear discriminant function parameter is represented by linear ^{f (k) (x) =} Θ T x ... (1) with respect to the feature vector x. Here, Θ represents an unknown parameter vector, and T represents transposition of the vector.

In pattern recognition using a discriminant function, the recognition performance depends on the model of the discriminant function to be used, that is, what kind of function is used as the discriminant function.

For example, a linear discriminant function that generates a linear boundary is appropriate for a classification problem including class boundaries that can be linearly separated. In the case of a complex class boundary, a discriminant function having a higher degree of freedom according to the degree of complexity is appropriate. Is desired.

[0008]

However, conventionally,
Although we tried to determine the optimal model of the discriminant function based on some criteria, the single model obtained in this way would not be a good one for a classification problem consisting of class boundaries of similar complexity. Is selected, but in the case of a classification problem in which a simple class boundary and a complex class boundary are mixed, a problem arises in that an identification function having an intermediate complexity between the two must be selected. For example, in an application having a large number of classes such as character recognition, such a situation can easily occur.

SUMMARY OF THE INVENTION The present invention has been made in view of the above problems, and is based on the integration of a plurality of discriminant functions which can solve the problem of model selection of discriminant functions in pattern recognition using a discriminant function generated by the selection of a single model. It is an object to provide a pattern recognition method.

[0010]

In order to achieve the above object, according to the present invention, a feature vector obtained as an observation result of a certain pattern is classified into one of K classes. For the pattern recognition problem, K discriminating functions are prepared, and in a pattern recognition method using a discriminating function in which a class having the maximum value of the discriminant function is a class to which the data belongs, M kinds of prepared in advance are used. The discrimination functions are individually trained using the M sets of discrimination functions using N sets of training data composed of a pair of a feature vector and a class to which the feature vector belongs. The level 0 learning process to be constituted, and one set of training data is sequentially extracted from the N sets of training data, and each time one set is extracted, the M is set using the remaining N-1 sets of training data. After configuring the level 1 discriminant function M types for each class by each newly learned identification function classes,
M types of level 1 for the extracted set of data
A level 1 data generating step of forming a total of N sets of level 1 data consisting of a pair of a KM dimensional vector including an output value of the identification function and a class label of the extracted data;
A discriminant function integrating step of forming a new discriminant function as a linear sum of outputs of the discriminant functions learned in the level 0 learning step using the level 1 data. The gist is that pattern recognition is performed by the discrimination function.

According to a second aspect of the present invention, in the configuration of the first aspect of the invention, in the discriminant function integrating step, the average value over the level 1 data of the loss function defined as a function of the degree of the classification error is provided. The point is to obtain the linear weight so as to minimize.

[0012]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, a pattern recognition method according to the present invention by integrating a plurality of identification functions will be described.

In order to achieve the above object, in the present invention, an integrated discriminant function expressed as a linear combination of M kinds of discriminant functions is considered. That is, f
_{Assuming that ens} ^(k) (x) represents the output of the k-th class identification function after integration for a certain feature vector x, the integrated identification function of each class according to the present invention is given in advance as shown below. and M types of the same training discriminant function data _{D = {(x i, C} (x i)); i = 1, ..., N} is called with each individually learned discriminant function (level 0 discriminant function using ) Is defined as a linear combination of the MK outputs for x.

[0014]

(Equation 2) Is an MK dimensional vector consisting of the outputs of the MK level 0 discriminant functions for x. The identification rules by the ensemble classifier are given below.

[0015]

(Equation 3) When the equation (2) is expressed as a matrix, y (x) = W ^T f ＾ (x; D) (4)

(Equation 4) I can write

Next, the means for determining the linear weight W according to claim 2 will be described. First, linear mapping of the linear weighting W in Equation (3) from the identification function space (f ^ space) into K-dimensional: W: has a R ^KM → R ^K. Here, if we look carefully at equation (4), f
_ens ^(k) can be regarded as a linear discriminant function having α ^(k) as a parameter in the discriminant function space f ＾. That is, the linear weight W in the equation (4) is calculated at N points f ＾ (x ₁ ),.
＾ (x _N ) is replaced by its respective class label C (x ₁ ),
.., C (x _N ), which correspond to the parameters of a linear discriminant function for classifying as faithfully as possible. That is, the problem of determining the optimal connection weight is reduced to a design problem of the optimal linear discriminant function in the discriminant function space.

Now, given a certain linear weight W, the loss caused by misclassification of the sample x of the k-th class by the equations (2) and (3) is represented by g _k (f ＾ (x); W). Where F is a random variable that follows the distribution p (f ＾), the expected value of the loss is

(Equation 5) I can write Here, P _k is the k-th class prior probability (priority
). Therefore, the optimal linear weight W from the viewpoint of minimizing expected loss can be obtained by solving the L minimization problem. However, since the distribution of the random variable F is actually unknown, the above-described expected value calculation is performed using the empirical distribution based on the learning data:

(Equation 6) Is approximated by Here, 1 (u) is a function that returns “1” when u is true, and returns “0” otherwise.

However, in equation (5), since D is used for both the estimation of f と and the estimation of the linear weight W, the obtained ensemble classifier performs over-learning on the specific training data D. overfit). Therefore, a known means, “StackedGeneralization” (Wolpert
DH, “Stacked generalization,” Neural Network
s, vol.5, no.2, pp.241-259, 1992), this problem is addressed using "level 1 data".

That is, the level 1 data is obtained by subtracting the original learning data from the “leave-one-out cross validity check method”.
on) ”. Specifically, D to disconnect the i th sample point x _i from the original data _(-i) ≡D - learn _{{(x i, C (x} i))} with f _m ^(k), it is unplugged F _m for data x _i
^{Assuming that} the output of ^(k ) is represented by f _m ^(k) (x _i ; D _(-i) ), the level 1 data is

D ′ = {(f ＾ _i , C (f ＾ _i )); i = 1,..., N}. here,

(Equation 8) Also, _{obviously, C (f ^ i) ≡C} (x i). After all, the estimated value of the linear weight W is obtained by solving the following minimization problem from D ′.

[0020]

(Equation 9) Obviously, replacing f ＾ _i with x _i in equation (6) is a design problem for a normal discriminant function in the feature vector space. Therefore, as the loss function, for example, a smoothed 0-1 loss function (Juang B.
H. and KatagiriS., “Discriminantlearning for minimu
m error classification, ”IEEE Trans.Signal Proc.,
vol.40, no.12,1992):

(Equation 10) Can be applied. Where ξ is a positive constant that controls the slope of the sigmoid function. D _k is a scale indicating the degree of misclassification when a class k sample is misclassified, and is defined by the following equation.

[0021]

[Equation 11] The detailed description of equation (8) is described in the above-mentioned known paper “Discriminantlear
ning for minimum errorclassification, ”

Conversely, in the case of this problem, d
_k (x) to d _k (f ＾, w) and f ^(k) (x) to α ^{(k) T}
misclassification measure for f ＾ such that C (f ＾) = k by substituting f ＾

(Equation 12) Get. η is a positive constant.

When f ＾ is correctly classified, d
_k (f ＾; W) <0, and d if misclassified
_k (f ＾; W)> 0. Also, when f ＾ is correctly classified, the value of the loss function gradually approaches 0 as the value of | d _k (f 関 数; W) | increases, while d _k (f The value of the loss function asymptotically approaches 1 as the value of 漸; W) increases. That is, the value of the loss function is
It depends not only on the correct or incorrect answer of the classification, but also on the degree.

In addition, it is apparent that around d _k = 0, the same degree of loss is provided regardless of whether the classification result is correct or incorrect. This suppresses over-learning, and has the effect of increasing the robustness to unknown data, as well as regularization.

If the loss function is obtained explicitly from equations (8) and (9), the objective function (empirical loss function) J of equation (6) is obtained as a function of the linear weight W. In this case, since the empirical loss function J is nonlinear with respect to the linear weight W, a closed-form solution cannot be obtained, and the linear weight W is estimated by an iterative method.
For example, a stochastic descent method (Amari S., “A
theory of adaptive pattrn classifiers, ”IEEE Tran
s.Elec.Comput., vol. 16, pp. 299-307, 1967) can be used to sequentially estimate the linear weight W.

[0026]

(Equation 13) U is a K-th positive definite matrix (actually, a unit matrix may be used)
It is. Further, ε (t) is a learning rate, and when the following condition is satisfied, the convergence of the algorithm to the local optimal solution is theoretically guaranteed.

[0027]

[Equation 14] As described above, the present invention uses an identification function obtained by linearly combining a plurality of models instead of an identification function of a single model, so that the present invention can be applied to a classification problem in which class boundaries having different complexity are mixed. A class boundary of appropriate complexity is automatically generated, and a good class boundary is obtained.

[0028]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a block diagram showing a functional configuration of an apparatus for implementing a pattern recognition method by integrating a plurality of identification functions according to an embodiment of the present invention.

In the level 0 learning step, unknown parameters of M kinds of identification functions given in advance are estimated using the training data given from outside, and the level 0 identification function is constructed. For the configuration of the level 0 identification function, a known method according to the identification function to be used can be used. For example,
An example in which a three-layer neural network known as a nonlinear discriminant function is adopted as a discriminant function (in this case, the number of input units is the number of dimensions of the feature vector and the number of output units is the number of classes K) will be described below.

As a method of selecting a neural network model,
Known methods using regularization parameters can be used. The regularization parameter is a real value, and the larger the value is, the more the degree of freedom of the neural network is reduced. Therefore, for the training data, M
The neural network is learned by setting the types of the regularization parameters, and M types of discriminant functions are configured. A known back error propagation method can be used for learning the neural network.

In the level 1 data generation step, i = 1,
Steps 1 and 2 are performed for each of 2, 2,..., N.

[0032] The (Step 1) the i-th pair from the training data D D removal of the _{(x i, C (x i} )) (-i) = D- (x i, C (x i)) using Thus, the M types of neural nets are newly learned.

(Procedure 2) The learned M obtained in the procedure 1
X extracted in step 1 for each type of neural network
Enter _i . Output of the m-th neural network (K
The dimensional _{vector) f ^ i = (f m} (1); expressed by _{(x i D (-i))} , (f ^ i, C (f ^ i)) the level 1 data i-th pair And

According to the above procedure, level 1 data D ′ = {(f ＾ _i , C (f ＾ _i )); i = 1,...

In the discriminant function integrating step, first, the linear weights are obtained by the following procedures 1 and 2 using the level 1 data.

(Procedure 1) An initial value of linear weight W (0) = (α ⁽¹⁾ ,..., Α ^(K) ) is appropriately set. Let t ← 0.

(Procedure 2) Until an appropriate convergence condition is satisfied,

(Equation 15) Is performed, and the converged value of W is set as the value of the linear weight.

Next, the linear weight obtained above and the level 0
Using the M types of learned neural nets obtained in the learning step, an integrated discriminant function is obtained by the linear combination shown in equation (4).

FIGS. 2 to 7 show experimentally the effectiveness of the present invention. In the experiment, two-dimensional, four-class Gaussian distribution

(Equation 16) , Artificially generated learning data: 50 / class and test data: 300 / class. The true classification boundary (Bayes boundary) calculated from the distribution is superimposed on FIG.

The regularization parameter value is λ = 5.0,
Intermediate unit H changed to 1.0, 0.2, 0.04
= 20, and an integrated discriminant function was constructed by the above procedure based on the level 1 data obtained by learning each of the neural networks of = 20.
3 when the regularization parameter value λ = 5.0, FIG. 4 when λ = 1.0, FIG. 5 when λ = 0.2, and FIG. 6 when λ = 0.04. Each class boundary obtained from a single neural network is shown. FIG. 7 shows class boundaries obtained from the integrated neural network.

As described above, from FIGS. 2 to 6, if the value of the regularization parameter is too large (λ = 5), the class boundary is too simple to perform flexible recognition, and conversely, too small (λ = 0.04), which results in a class boundary specialized for learning data due to a complicated class boundary.

In practice, λ = 5.0, 1.0, 0.2, 0.
The classification error rate (%) for the training data of each neural network for No. 04 is 58.0, 28.5, 2
At 2.0 and 19.5, that for the test data was 59.7, 28.3, 23.3 and 23.6, respectively. In preliminary experiments with a single neural network, λ = 0.2
At the time, the generalization error (test error) was the minimum.

On the other hand, when integrated, the classification error rates for the learning data and the test data are 20.0, 22.
It was 4. A better result (22.4%) than the best (corresponding to λ = 0.2) 23.3% of a single neural network with H = 20 was obtained, and the desired classifier could be constructed. ing. 7, the obtained classification boundary is similar to that of λ = 1.0 between class 1 and class 3, and λ = 0 between class 2 and class 3. .2, and between Class 2 and Class 4, it is similar to that of λ = 0.04.
This result indicates that the integrated discriminant function does not constitute the average discriminator of each discriminator, but can construct the best integrated discriminator taking advantage of each discriminator.

[0044]

As described above, according to the present invention, an identification function obtained by linearly combining a plurality of models is used instead of an identification function of a single model, so that class boundaries having different complexity are mixed. Also for a classification problem, a class boundary having appropriate complexity is automatically generated adaptively, and a good class boundary is obtained.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a functional configuration of an apparatus for implementing a pattern recognition method by integrating a plurality of identification functions according to an embodiment of the present invention.

FIG. 2 is a diagram for showing the effectiveness of the present invention from an experiment, and showing a true class boundary.

FIG. 3 is a diagram for showing the effectiveness of the present invention from an experiment, showing class boundaries obtained from a single neural network when the regularization parameter value λ = 5.0.

FIG. 4 is a diagram for showing the effectiveness of the present invention experimentally and showing class boundaries obtained from a single neural network when the regularization parameter value λ = 1.0.

FIG. 5 is a diagram for showing the effectiveness of the present invention through experiments, and showing class boundaries obtained from a single neural network when the regularization parameter value λ = 0.2.

FIG. 6 is a diagram for showing the effectiveness of the present invention from an experiment, and is a diagram showing class boundaries obtained from a single neural network when the regularization parameter value λ = 0.04.

FIG. 7 is a diagram for showing the effectiveness of the present invention through experiments, and showing class boundaries obtained from an integrated neural network.

[Explanation of symbols]

 1 Level 0 learning process 3 Level 1 learning process 5 Integration process 7 Training data 9 Level 1 data

Claims (2)

[Claims] For a pattern recognition problem in which a feature vector obtained as an observation result of a certain pattern is classified into one of K classes, K identification functions are prepared, and a class having the maximum value of the identification function is determined. In the pattern recognition method using a discriminant function as a class to which the data belongs, M kinds of discriminant functions prepared in advance are used to convert N sets of training data comprising a pair of a feature vector and a class to which the feature vector belongs. A level 0 learning step of individually learning each of the M types of discriminant functions to form M types of level 0 discriminant functions, and sequentially extracting one set of training data from the N sets of training data and one set Each time sampling was performed, the M types of discriminant functions were newly learned using the remaining N-1 sets of training data, and M types of level 1 discriminant functions were constructed for each class. , A total of N consisting of pairs of class labels of the data drawn the the KM-dimensional vector consisting of the output value of the level 1 discriminant function M type for a set of data drawn the
A level 1 data generating step of forming a set of level 1 data; and a discriminant function integration of forming a new discriminant function as a linear sum of outputs of the discriminant functions learned in the level 0 learning step using the level 1 data. And performing pattern recognition using the identification function configured in the identification function integration step. 2. A level 1 of a loss function defined as a function of a degree of a classification error in the discriminant function integrating step.
2. The pattern recognition method according to claim 1, wherein the linear weight is determined so as to minimize an average value over data.