JP2017126158A - Binary classification learning device, binary classification device, method, and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To learn a score function capable of accurately performing binary classification even in the case where difference between a positive example number and a negative example number is large.SOLUTION: A score calculation section 32 uses an evaluation value model, a generation probability model of positive example data and a generation probability model of negative example data to calculate a score which indicates whether or not a sample without label is the positive example data, for each sample without label. An evaluation value model calculation section 34 and a generation probability model calculation section 36 calculate an evaluation value model on the basis of a score for each sample without label, a sample with label and the sample without label, and calculate a generation probability model of positive example data and a generation probability model of negative example data. Until it converges, the score calculation section 32, evaluation value model calculation section 34 and generation probability model calculation section 36 repeat processing.SELECTED DRAWING: Figure 2

Description

  The present invention relates to a binary classification learning device, a binary classification device, a method, and a program for binary classification.

  In binary content classification technology based on statistical methods, a score function representing the strength of dependency between content and category is given as a function of model parameters and feature vectors. Binary classification of content is performed by estimating the above. The value of the model parameter is generally obtained using content (hereinafter referred to as a labeled sample) that is known whether or not it is related to the type. In the method based on this framework, the accuracy of binary classification of new content can be improved by increasing the amount of labeled samples used for calculation of model parameter values. However, in order to obtain a labeled sample, it is necessary to classify the contents manually, so it is not easy to prepare a large number of labeled samples. Therefore, a large amount of content (hereinafter referred to as unlabeled samples) for which it is not known whether or not it is related to the relevant category is collected, and these unlabeled samples are used for calculation of model parameters. There is a semi-supervised learning technique that compensates for insufficient learning of feature quantities that are not obtained and improves the accuracy of binary classification as compared to using only labeled samples.

  The technique of Non-Patent Document 1 is characterized in that the parameter value of the score function is calculated based on margin maximization learning so that the AUC value that is generally used to express the accuracy of binary classification is maximized. AUC (Area Under the Curve) is an evaluation index based on the receiver operating characteristic (Receiver Operating Characteristic) curve.The larger the AUC value, the more correctly the content is ranked in the score from positive to negative examples. Show. In this technology, the difference between the score value of content related to the type (hereinafter referred to as positive example) and the score value of content not related to the type (hereinafter referred to as negative example) is equal to or greater than a certain margin value. The parameter value of the score function is learned. This parameter learning takes into account the differences for all positive and negative example combinations. Also, predict whether the unlabeled sample is positive or negative, and if the prediction result is negative, the difference between the score value of each labeled sample in the positive example minus the score value of the unlabeled sample If the prediction result is positive, the difference between the score value of the unlabeled sample minus the score value of the negative labeled sample is learned to be greater than a certain margin. To do.

  In the technologies of Non-Patent Document 2 and Patent Document 1, with respect to the problem of classifying each content into any one of a plurality of categories such as sports, music, science, economy, etc., the identification function used for classification is a labeled sample. Learning from unlabeled samples, the discriminant function is given by weighted integration of a content generation probability model in each category and a category conditional probability model (discriminative probability model) for the content. As described in Non-Patent Document 3, in general, the generation probability model is an effective model for learning the distribution of unlabeled samples, whereas the discriminative probability model correctly classifies labeled samples. It is known to be effective. In the techniques of Non-Patent Document 2 and Patent Document 1, by appropriately combining both models, statistical information of labeled and unlabeled samples is effectively used for learning of the discrimination function, and the classification accuracy of new samples is improved. Let

Japanese Patent No. 5308360

Shijun Wang, Diana Li, Nicholas Petrick, Berkman Sahiner, Marius George Linguraru, and Ronald M. Summers: Optimizing area under the ROC curve using semi-supervised learning.Pattern Recognition, Elsevier 48 276−287 (2015). A. Fujino, N. Ueda, and M. Nagata: Adaptive semi-supervised learning on labeled and unlabeled data with different distributions.Knowledge and Information Systems (KAIS), Springer, 37 (1), 129-154 (2013). M. Seeger: Learning with labeled and unlabeled data.Technical report, University of Edinburgh (2001).

  In the technique of Non-Patent Document 1, margin maximization learning, which is often used in supervised learning using labeled samples, is expanded and unlabeled samples are also used for learning of the score function. However, as described in Non-Patent Document 3, it is generally known that the generation probability model is effective for learning the distribution of unlabeled samples, and by using the generation probability model for learning, There is a possibility of obtaining a score function that gives high classification accuracy. The technologies of Non-Patent Document 2 and Patent Document 1 are technologies aimed at accurately predicting an appropriate category from among a plurality of category candidates for each content, and increasing the accuracy rate of category prediction. To learn the parameters of the discriminant function. However, in the binary classification problem targeted by the present invention, the number of contents (positive examples) related to a specific type is often very small compared to the number of unrelated contents (negative examples). In such a case, learning a discriminant function that determines all negative examples can obtain a correct rate of category prediction close to 100%, but it is not always possible to correctly extract positive examples. Therefore, even if the techniques of Non-Patent Document 2 and Patent Document 1 are applied as they are to the problem of binary classification with a large difference between the number of positive examples and negative examples, there is no guarantee that positive examples and negative examples can be classified with high accuracy. . The problem is to obtain a score function that gives high classification accuracy by effectively using unlabeled samples for learning for the problem of binary classification where the difference between the number of positive examples and negative examples is large.

  In the present invention, it was made in view of the above circumstances, and it is possible to learn a score function that can accurately perform binary classification even when the difference between the numbers of positive examples and negative examples is large. An object of the present invention is to provide a binary classification learning device, method, and program.

  Another object of the present invention is to provide a binary classification apparatus, method, and program capable of performing binary classification with high accuracy.

  In order to achieve the above object, the binary classification learning device according to the present invention is given whether it is positive example data related to a specific type or negative example data not related to the specific type Binary classification learning for learning a score function for binary classification based on training data consisting of a labeled sample and an unlabeled sample whose positive or negative data is unknown. An evaluation value model represented using a function that outputs a value indicating whether or not the data is positive data for each of the unlabeled samples, and a generation probability model of positive data, A score calculation unit that calculates a score indicating whether the unlabeled sample is the positive example data using a negative example data generation probability model, and the label calculated by the score calculation unit An evaluation value model calculation unit that calculates the evaluation value model based on the score for each of the samples, the labeled sample, and the unlabeled sample; and the unlabeled sample calculated by the score calculation unit A generation probability model calculation unit that calculates the generation probability model of the positive example data and the generation probability model of the negative example data based on the score, the labeled sample, and the unlabeled sample And repeating the calculation by the score calculation unit, the calculation by the evaluation value model calculation unit, and the calculation by the generation probability model calculation unit until a predetermined convergence determination condition is satisfied, and the evaluation value model and the generation probability And a convergence determination unit that outputs the score function using a model.

  Whether the binary classification learning method according to the present invention includes a score calculation unit, an evaluation value model calculation unit, a generation probability model calculation unit, and a convergence determination unit, and is positive data related to a specific type? Training data consisting of a labeled sample given whether it is negative example data not related to the specific type, and an unlabeled sample whose positive example data or negative example data is unknown A binary classification learning method in a binary classification learning device that learns a score function for binary classification based on whether the score calculation unit is positive data for each of the unlabeled samples The unlabeled sample is converted into the positive value using the evaluation value model expressed using a function that outputs a value indicating whether or not, a positive example data generation probability model, and a negative example data generation probability model. Example de The evaluation value model calculation unit calculates the score for each of the unlabeled samples calculated by the score calculation unit, the labeled sample, and the unlabeled The evaluation value model is calculated based on the sample, and the generation probability model calculation unit calculates the score for each of the unlabeled samples calculated by the score calculation unit, the labeled sample, and the label Based on the no sample, the generation probability model of the positive example data and the generation probability model of the negative example data are calculated, and the score calculation is performed until the convergence determination unit satisfies a predetermined convergence determination condition. Repeat the calculation by the calculation part, the calculation by the evaluation value model calculation part, and the calculation by the generation probability model calculation part. And outputs the score function using the evaluation value model and said generation probability model.

  The binary classification device according to the present invention calculates a score value indicating that the test data is a positive example based on the input test data and the score function learned by the binary classification learning device. It is comprised including the score calculation part to do.

  A binary classification method according to the present invention is a binary classification method in a binary classification device including a score calculation unit, wherein the score calculation unit learns by input test data and the binary classification learning method described above. A score value indicating that the test data is a positive example is calculated based on the score function thus obtained.

  Moreover, the program of this invention is a program for functioning a computer as each part which comprises said binary classification learning apparatus or a binary classification apparatus.

  As described above, according to the binary classification learning device, method, and program of the present invention, for each of the unlabeled samples, the evaluation value model, the positive data generation probability model, and the negative data A score indicating whether the unlabeled sample is the positive example data, the score for each of the unlabeled samples, the labeled sample, By calculating the evaluation value model based on the unlabeled sample and calculating the generation probability model of the positive example data and the generation probability model of the negative example data, the positive example and the negative example are repeated. Even when the difference in number is large, it is possible to learn a score function that can accurately perform binary classification.

  Moreover, according to the binary classification apparatus, method, and program of the present invention, binary classification can be performed with high accuracy.

It is a block diagram which shows the functional structure of the binary classification device which concerns on this embodiment. It is a block diagram which shows the functional structure of the score function production | generation part of the binary classification device which concerns on this embodiment. It is a flowchart figure of the binary classification learning process routine in the binary classification device concerning this embodiment. It is a flowchart figure of the binary classification processing routine in the binary classification device concerning this embodiment.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Outline of Embodiment of the Present Invention>
First, an outline of the present embodiment will be described.

  In the binary classification apparatus according to the present embodiment, content consisting of text information such as papers, patents, online news data, e-mails, etc. included in the database, text information such as Web data, blog data, and link information When extracting content related to a specific type, such as sports, music, science, economics, etc., from a set of content that can be expressed by feature vectors such as content consisting of image data or content such as image data The feature vector of the content is used as an input using the statistical information of the content that is known to be related to the specific type and the content that is unknown whether it is related, and represents the degree of the specific type Learning a binary classifier that outputs score values, and binary content using the binary classifier Classify.

  Further, in the binary classification device according to the present embodiment, a score function is given by weighted integration of an evaluation value model that learns parameters so as to maximize the AUC value and a generation probability model, and the parameters of both models are It is obtained by calculating using statistical information of both labeled and unlabeled samples simultaneously. The score function and parameter values are the logarithmic expected value of the evaluation value model, the expected log likelihood of the generation probability model, the entropy regularization term of the probability value given by the score function, and the evaluation value model and the generation probability model It is given based on the regularization term of the parameter and a weighted maximization of it.

<Configuration of Binary Classification Device According to First Embodiment of the Present Invention>
Next, the configuration of the binary classification device according to the first embodiment of the present invention will be described. As shown in FIG. 1, a binary classification device 100 according to the present embodiment includes a CPU, a RAM, a program for executing a binary classification learning processing routine and a binary classification processing routine described later, and various data. It can be composed of a computer including a stored ROM. Functionally, the binary classification device 100 includes an input unit 10, a calculation unit 20, and an output unit 90 as shown in FIG.

  The input unit 10 receives a training data set generated by collecting examples of content having the same format as the content to be subjected to binary classification.

  For example, when performing binary classification of Web articles, use training data that records examples of Web articles and classes that indicate whether the examples are related to a specific type (music, sports, business, etc.) . There are two types of classes: a positive example (+) indicating that it is related to the specific type, and a negative example (-) indicating that it is not related to the specific type. Either a positive example or a negative example is given as a class for each example of content.

  The training data set includes a content body, a labeled sample composed of a pair of classes given as described above, and an unlabeled sample composed of a content body whose class is unknown.

  Further, the input unit 10 receives a test data set that is a content to be subjected to binary classification.

  The calculation unit 20 includes a training data database 22, a score function generation unit 24, a test data database 26, and a ranking unit 28. The score function generation unit 24 is an example of a binary classification learning device.

  The training data database 22 stores a training data set received by the input unit 10.

  The score function generation unit 24 generates a score function for binary classification based on the training data set stored in the training data database 22.

  As shown in FIG. 2, the score function generation unit 24 includes an initialization unit 30, a score calculation unit 32, an evaluation value model calculation unit 34, a generation probability model calculation unit 36, a convergence determination unit 38, and a score function storage unit 40. Contains.

  Hereinafter, the principle of generating the score function will be described.

First, x represents a feature vector of content. ω∈ {+, −} represents a class whose value is either positive example (+) or negative example (−). Also, the evaluation value model is represented as F (x; W), the generation probability model is represented as p (x; θ _ω ), and the parameters of the score function are

It expresses. In addition, a positive example set of labeled samples stored in the training data database 22

And a negative example set of labeled samples

And the unlabeled sample set

It expresses.

  In this embodiment, a case where a linear function is used as an evaluation value model and a Naive Bayes model (hereinafter referred to as NB model) is used as a generation probability model will be described as an example.

  A feature space composed of words, pixels, links, or combinations included in content

When a feature vector x of the content, based on the frequency x _v of t _v in the content

It is expressed by V represents the number of types of features that may be included in the content. For example, when the content is text data, V represents the total number of vocabularies that can appear in the content. A ^T represents the transpose of the matrix (vector) A.

  In the evaluation value model, a function f (x; W) that outputs a large scalar value when the content feature vector is a positive example is designed. Positive set of labeled samples

And negative example set

When the evaluation value model is applied to the AUC value, the AUC value representing the accuracy of the binary classification can be calculated by the following equation.

  However,

Is

Is a step function that outputs 1 in the case of 0 and 0 in other cases. When the evaluation value model is learned only from the labeled data sets D ⁺ and D ^{−, it is} only necessary to solve an optimization problem for obtaining W that maximizes the AUC. But the step function

Is a non-differentiable function and it is not easy to solve the above optimization problem. Therefore, the above optimization problem is converted into a step function.

The sigmoid function

The evaluation value model can be easily learned by replacing it with the problem of obtaining W that maximizes the following objective function approximated using.

  R (W) in equation (3) is a regularization term relating to the parameter W of the evaluation value model, and C is a hyperparameter that gives the weight of the regularization term. Regularization terms are often used to suppress over-learning, which reduces prediction accuracy for new samples due to excessive model adaptation to labeled sample sets.

  In this embodiment, an unlabeled sample set

Is used with a labeled sample to learn the parameters of the score function. Probability P unlabeled sample x _m is a positive example | a (+ x _m), the probability P unlabeled sample x _m is negative example - | if (x _m) is given, for example, the following objective function W to be maximized can be calculated as a parameter estimation value of the evaluation value model.

  In formula (4)

Is unlabeled sample x _m is negative examples set D Label Yes Sample ^- For _j, ^- all samples x contained in

The maximum value is 1 in the case of

In this case, the minimum value is 0. To the objective function

Is introduced if the unlabeled sample x _m is expected to be a positive example,

This is because the parameter W is learned so that Similarly,

Is introduced for a positive example set D ⁺ of labeled samples when the unlabeled sample x _m is predicted to be a negative example.

This is because the parameter W is learned so that

R (P _m ) in equation (4) is an entropy regularization term for P (+ | x _m ) and P (− | x _m ), for example,

Can be used. γ is a hyperparameter that gives the weight of the regularization term R (P _m ). Constraints

By using the Lagrange undetermined multiplier method, W and P (ω | x _m ), ω∈ {+, −}, ∀m that maximize J (W, P) can be obtained.

However, in the learning based on J (W, P) in Expression (4), the parameter value is learned by predicting the class of the unlabeled sample based only on the positive and negative information of the labeled sample. Therefore, the effect of using unlabeled samples for learning is small. In the present embodiment, the effect of using the unlabeled sample for learning is enhanced by using, as prior knowledge, the distribution characteristic of the content assumed in the generation probability model according to the type of content such as a document or an image. Introducing a positive content generation probability model p (x; θ ₊ ) and a negative content generation probability model p (x; θ ₋ ), an evaluation value model parameter W, and a generation probability model parameter and, unlabeled sample class probability _{P - Θ = [θ + θ} ] (ω | x m), ω ∈ {+, -}, and ∀M, a is learned so as to maximize an objective function below.

  P (Θ) in Equation (6) represents a prior probability distribution of the parameter Θ of the generation probability model, and is a regularization term for suppressing overlearning of Θ. β is a hyperparameter that gives the degree of contribution of the generation probability model to learning.

  Constraints

Using Lagrange's undetermined multiplier method under, the solution of P (ω | x _m ), ω ∈ {+, −}, ∀m that maximizes J (W, Θ, P) in equation (6) ^ P Solution of (ω | x _m ; W, Θ)

Is obtained. However,

It is. In the present embodiment, the function ^ P (+ | x; W, Θ) for x given by equation (7) is used as a score function for determining whether or not the content is a positive example.

  Substituting Equation (7) into Equation (6), the objective function for W and Θ

Is obtained.

  W and Θ that maximize the objective function ^ J (W, Θ) given by equation (10) are, for example,

By repeatedly calculating W and Θ that maximize the following Q1 (W, Θ, W ^(t) , Θ ^(t) ) that satisfies the following, ^ J (W, Θ) around the initial values of W and Θ A local optimal solution to be maximized can be obtained.

However,

It is. (t + 1) step estimate

By calculating as follows, it is possible to obtain the estimated values of W and Θ that monotonically increase ^ J (W, Θ). The solution of equation (14) can be obtained by independently calculating W ^{(t + 1)} and Θ ^{(t + 1)} as follows.

  A function f (x, W) used in the evaluation value model is obtained by using a parameter vector w having the same dimension as that of the content feature vector x.

As a regular function R (W) of W

Is used, the solution W ^{(t + 1)} = w ^{(t + 1)} of equation (15)

The w that maximizes J ^(t) _s (w) around the initial value w ^(t) is obtained by repeatedly calculating w that maximizes the following Q ₂ (x, x ^(u) ) satisfying May be.

  (u + 1) step estimate

By calculating as follows, an estimated value of w that monotonically increases J ^(t) _s (w) can be obtained. The estimated value ^ w obtained by parameter estimation according to equation (20) is

Therefore, the value of Q 1 (W, Θ, W ^(t) , Θ ^(t) ) shown in the equation (11) is larger in the case of W than in the case where W is w ^(t) . Therefore, by obtaining the estimated value of w by the iterative calculation according to equation (20) at the (t + 1) step of equation (14), ^ J (W, Θ) is monotonically increased W ^{(t + 1)} = w ^{(t + 1)} is obtained.

Since Q ₂ (w, w ^(u) ) is a concave function related to w, a global optimum solution of w ^{(u + 1)} satisfying Expression (20) can be obtained. The solution w ^{(u + 1)} of Equation (20) can be calculated using, for example, a BFGS algorithm (see Non-Patent Document 4) which is a kind of quasi-Newton method.

Non-Patent Document 4: D. C. Liu and J. Nocedal: On the limited memory BFGS method for large scale optimization, Math. Programming, Ser. B, Vol. 45, No. 3, pp. 503-528 (1989).

When designing the generation probability model using the NB model, the generation probability model p (x; θ ₊ ) of the positive example content and the generation probability model p (x; θ ₋ ) of the negative example content are:

Defined by here,

And

It is. Also, using the Dirichlet distribution, the prior probability distribution of Θ

Design like this. ξ (> 0) is a hyper parameter. Thus, when designing a generation probability model using the NB model, the solution satisfying equation (16) is

It can be calculated with

(t + 1) After calculating the parameter estimate values W ^{(t + 1)} and Θ ^{(t + 1)} of the score function in the learning step, for example, it is confirmed whether or not the convergence condition given by the following equation is satisfied.

|| W ^(t) || and || Θ ^(t) || in Equation (25) represent the Frobenius norm of the matrices W ^(t) and Θ ^(t) . ε is a minute value given by the designer. When the convergence condition is satisfied, W ^{(t + 1)} and Θ ^{(t + 1)} are stored in the score function storage unit 40 as the parameter values ^ W and ^ Θ of the score function. If the convergence condition is not satisfied, t ← t + 1 and repeat the above process.

  In accordance with the principle described above, the initialization unit 30 of the score function generation unit 24 sets initial values for the parameter W of the evaluation value model and the parameter Θ of the generation probability model.

The score calculation unit 32 sets an initial value for each of the unlabeled samples x _{m by} the initialization unit 30 or the parameter W of the evaluation value model previously calculated by the evaluation value model calculation unit 34, and the initialization unit 30. In the above equation (7), in which the initial value is set at or the parameter Θ of the generation probability model previously calculated by the generation probability model calculation unit 36 is used and the entropy regularization term R (P _m ) of the probability value is considered. accordingly the probability value unlabeled sample x _m is the data of the positive sample _{^ P (+ | x m;} W, Θ), and a negative sample in which the probability value _{^ P (- | x m;} W, Θ) calculated To do.

The evaluation value model calculation unit 34 calculates the probability values ^ P (+ | x _m ; W, Θ) and ^ P (− | x _m ; W, for each of the unlabeled samples x _m calculated by the score calculation unit 32. Θ), the above-mentioned formulas (19) and (14) taking into account the regularization term R (W) of the model parameter of the evaluation value model based on the labeled samples x ⁺ _i , x ^- _j and the unlabeled sample x _m According to (20), the parameter W of the evaluation value model is calculated so as to maximize the AUC (Area Under the Curve) value approximated by using the sigmoid function with respect to the evaluation value model F (x; W). .

The generation probability model calculation unit 36 calculates the probability values ^ P (+ | x _m ; W, Θ) and ^ P (− | x _m ; W, for each of the unlabeled samples x _m calculated by the score calculation unit 32. (23), which takes into account the regularization term p (Θ) of the model parameter of the generation probability model based on Θ), labeled samples x ⁺ _i , x ^- _j and unlabeled samples x _m According to (24), the log likelihood of the labeled sample obtained using the positive data generation probability model p (x; θ ₊ ) and the negative data generation probability model p (x; θ ₋ ) and The parameter θ _{+, v} of the positive example data generation probability model and the parameter θ _{−, v} of the negative example data generation probability model are calculated so as to maximize the sum of the expected log likelihoods of the unlabeled samples.

  The convergence determination unit 38 repeats the calculation by the score calculation unit 32, the calculation by the evaluation value model calculation unit 34, and the calculation by the generation probability model calculation unit 36 until the convergence determination condition represented by the above formula (25) is satisfied. The estimated value ^ W of the evaluation value model used in the function and the estimated value ^ Θ of the parameter of the generation probability model are stored in the score function storage unit 40.

  In the test data database 26, a set of test data received by the input unit 10

Is remembered.

The ranking unit 28 uses, for each of the test data _xz included in the test data set Dp stored in the test data database 26, the parameter W of the evaluation value model used in the score function stored in the score function storage unit 40. Then, based on the parameter Θ of the generation probability model, a probability value ^ P (+ | x _z ; W, Θ) is calculated as a score value indicating that the test data x _z is a positive example according to the above equation (7). Then, the test data _xz is rearranged in descending order of the score values, and the obtained score values and the order of the test data are output by the output unit 90 as binary classification results. Note that a threshold value may be provided for the score value, and only test data for which a score value equal to or greater than the threshold value is obtained may be output as a positive example.

<Operation of Binary Classification Device According to First Embodiment of the Present Invention>
Next, the operation of the binary classification device 100 according to the first embodiment of the present invention will be described. The binary classification device 100 accepts the training data set by the input unit 10 and stores it in the training data database 22, and receives the test data set and stores it in the test data database 26. A value classification learning process routine is executed.

First, in step S101, included in the training data set stored in the training data database 22, a label Yes Yes positive sample set D ⁺ and label samples negative examples set D of sample ^- and the unlabeled sample set D _u Is read. Here, i represents the ID number of the labeled sample included in the positive example set, j represents the ID number of the labeled sample included in the negative example set, and m represents the unlabeled sample included in the unlabeled sample set. Represents an ID number.

In the next step S102, the initialization unit 30 sets a hyperparameter value used for calculation of the parameter value. Specifically, the values of hyper parameters C, ξ, γ, β are set. In addition, a convergence condition parameter ε and a value of the maximum number of iterations t _max are set.

In step S103, the initialization unit 30 sets the initial value t = 0 of the learning step t and the initial value Θ ⁽⁰⁾ of the parameter of the generation probability model that constitutes the score function. For example, 1 / V is substituted for each element θ ⁽⁰⁾ _{ω, v} (ω ∈ {+, −}) of Θ ⁽⁰⁾ .

Further, in step S104, the initialization unit 30 calculates the parameter value of the evaluation value model using the positive example set D ⁺ of the labeled sample and the negative example set D ⁻ of the labeled sample, and obtains the obtained value as The initial value W ⁽⁰⁾ of the parameter of the evaluation value model constituting the score function is used.

  Step S104 includes, for example, the following 1. ~ 4. To achieve.

1. The convergence condition parameter ε ′ and the maximum number of iterations u _max are set.

2. 0 is assigned to u, and 0 is assigned to each element of w ^(u) . ^ P (ω | x _m ; w ⁽⁰⁾ , Θ ⁽⁰⁾ ), 0 is substituted into ω ∈ {+, −}.

3. Using the BFGS algorithm, a solution of w ^{(u + 1)} that satisfies the above equation (20) is calculated.

4). The following learning end determinations (a) and (b) are executed.

(A) Convergence conditions

When u <u _{max is} not satisfied i. Substitute u + 1 for u.
ii. 3. above. Return to.

(B) In other ^cases , w ^{(u + 1)} is substituted for w ^(t) .

In step S105, the score calculation unit 32 calculates the parameter W ^(t) obtained in step S104 or step S106 described later and the parameter Θ ^(t) obtained in step S104 or step S107 described later. used as the parameter values for each of the unlabeled sample x _m, in accordance with the above equation (7), the probability value without the label sample x _m is a positive example _{^ P (+ | x m;} W (t), Θ ( ^t) ) and a negative example probability value ^ P (− | x _m ; W ^(t) , Θ ^(t) ) are calculated.

In step S106, the evaluation value model calculation unit 34, a probability value for each of the calculated unlabeled samples x _m in step _{S105 ^ P (+ | x m} ; W, Θ), ^ P (- | x m ; W, Θ), labeled samples x ⁺ _i , x ⁻ _j and unlabeled samples x _m are used to calculate the estimated value W ^{(t + 1)} of the parameters of the evaluation value model.

  Step S106 is realized by the following (a) to (d), for example.

(A) The value of the convergence condition parameter ε ′ and the maximum number of iterations u _max are set.

(B) 0 is substituted for ^u, and w ^(t) is substituted for w ^(u) .

(C) A solution of w ^{(u + 1)} satisfying the above equation (20) is calculated using the BFGS algorithm.

(D) i. To ii. Execute learning end judgment

i. Convergence condition

When u <u _{max is} not satisfied A. Substitute u + 1 for u.
B. Return to (c) above.

ii. Otherwise, substitute w ^{(u + 1)} for W ^{(t + 1)} .

In step S107, the generation probability model calculation unit 36, a probability value for each of the calculated unlabeled samples x _m in step _{S105 ^ P (+ | x m} ; W, Θ), ^ P (- | x m ; W, Θ), labeled samples x ⁺ _i , x ⁻ _j and unlabeled samples x _m are used to calculate the estimated value Θ ^{(t + 1)} of the generation probability model. Specifically, using the above formula (23) and formula (24),

Calculate

In step S108, the convergence determination unit 38 calculates the change amount d (t + 1, t) of the estimated value of the parameter W, and the convergence determination condition d (t + 1, t) <ε in the above equation (25). It is determined whether or not the above is satisfied. When the convergence determination condition is satisfied, in step S110, ^ W ← W ^{(t + 1)} and ^ Θ ← Θ ^{(t + 1)} are set, and the estimated values ^ W and ^ Θ of the score function are used as the score function. It stores in the memory | storage part 40, and complete | finishes a binary classification learning process routine. On the other hand, if the convergence determination condition is not satisfied, the parameter learning step is updated as t ← t + 1 in step S109, the process returns to step S105, and the processes from step S105 to step S108 are performed again. This process is repeated until the convergence determination condition is satisfied or the learning step t 1 reaches the maximum value t _max given in advance by the designer.

  Further, the binary classification processing routine shown in FIG.

First, in step S201, the test data set D _p stored in the test data database 26 is read.

  In the next step S202, a score function is acquired from the score function generator 24. In step S203, the score function parameter values ^ W and ^ Θ are read from the score function storage unit 40.

In step S204, the test data set D _p read in step S201, the score function of the loaded parameters computed in step S202 and step S203 ^ P (+ | w; ^ W, ^ Θ) of The score value ^ P (+ | _wz ; ^ W, ^ Θ) is calculated for each test data _xz , and the test data is rearranged in descending order of the score values. Then, the order of the obtained score values and test data is output as a binary classification result by the output unit 90, presented to the user, and the result of rearranging the test data set in the order of higher score as necessary is displayed. Save to an appropriate location and end the binary classification routine.

  As described above, according to the binary classification device according to the first embodiment, for each of the unlabeled samples, the evaluation value model, the positive example data generation probability model, and the negative example data generation Using the probability model, calculate the probability that the unlabeled sample is positive data, the probability that it is negative data, and calculate the probability for each unlabeled sample, labeled sample, and unlabeled sample On the basis of this, the evaluation value model is calculated, and the generation probability model of the positive example data and the generation probability model of the negative example data are repeated, so that the difference between the numbers of the positive example and the negative example is large. However, it is possible to learn a score function that can perform binary classification with high accuracy. Moreover, it is possible to classify the test data with high accuracy using the score function learned in this way.

  In the binary classification problem for determining whether or not the content represented by the feature vector is related to a specific type, the evaluation value model parameter that is a parameter of the score function, and the generation probability model parameter are Learns a score function that gives a larger score for positive samples than for negative samples by calculating simultaneously using statistical information for both labeled and unlabeled samples, and statistics for unlabeled samples Incorporates information effectively to compensate for the lack of learning of the score function for features that are not included in labeled samples. With the above technology, to realize a classification device that extracts content related to a specific type from a new content set with high accuracy even in a binary classification problem in which there is a large difference between the number of positive examples and negative examples. Can do.

<Second Embodiment>
Next, a binary classification apparatus according to the second embodiment will be described. Note that the configuration of the binary classification device according to the second embodiment is the same as that of the first embodiment, and therefore, the same reference numerals are given and description thereof is omitted.

  In the second embodiment, the objective function for calculating the evaluation value model is different from that in the first embodiment.

  In the first embodiment, since the unlabeled sample is used for learning of the evaluation value model, the objective function of the above equation (4) is defined. In the second embodiment, the following objective function is used. To learn the evaluation value model.

  In the first embodiment, the objective function for performing the comparison of the function value of the unlabeled sample and the positive labeled sample and the comparison of the function value of the unlabeled sample and the negative labeled sample in parallel is provided. In contrast, in the second embodiment, when one unlabeled sample is added, the AUC is calculated from the function value of the unlabeled sample and each function value of the labeled sample set. Design an objective function to find the parameter value that maximizes the value.

In the same manner as in the first embodiment, a positive content generation probability model p (x; θ ₊ ) and a negative content generation probability model p (x; θ ₋ ) are introduced and evaluated. and parameters W value model, the parameters of the generation probability model theta = _- a, unlabeled sample class probability _{P [θ + θ] (ω} | x m), ω ∈ {+, -}, and ∀M, less To learn to maximize the objective function of.

Constraints

Using Lagrange's undetermined multiplier method under, the solution of P (ω | x _m ), ω ∈ {+, −}, ∀m that maximizes J (W, Θ, P) in Eq. (27)

Is obtained. However,

It is. In this embodiment, the function ^ P (+ | x; W, Θ) for x given by Expression (28) is used as a score function for determining whether or not the content is a positive example.

  Substituting equation (28) into equation (27), the objective function for W and Θ

Is obtained.

  As a calculation method of W and Θ that maximizes the objective function ^ J (W, Θ) given by the above equation (31), for example,

^ J (W, Θ) around the initial values of W and Θ by repeatedly calculating W and Θ that maximize the following Q ₁ (W, Θ, W ^(t) , Θ ^(t) ) that satisfies It is possible to obtain a local optimal solution that maximizes.

However,

J ^(t) _g (Θ) satisfies the above equation (13). However, unlike the case of the first embodiment, ^ P (ω | x _m ; W ^(t) , Θ ^(t) ) included in the equation (13) is calculated by the equation (28). Is an estimate of the probability of being done. (t + 1) step estimate

By calculating as follows, it is possible to obtain the estimated values of W and Θ that monotonically increase ^ J (W, Θ). The solution of the above equation (20) can be obtained by independently calculating W ^{(t + 1)} and Θ ^{(t + 1)} as follows.

When the function f (x, W) used in the evaluation value model is designed as a linear function as shown in equation (17) and equation (18) is used as the regularization term R (W) of W, the solution of equation (35) W ^{(t + 1)} = w ^{(t + 1)}

The w that maximizes J ^(t) _a (w) is obtained around the initial value w ^(t) by repeatedly calculating w that maximizes the following Q ₂ (w, w ^(u) ) that satisfies May be.

However,

It is. Since Q ₂ (w, w ^(u) ) is a concave function related to w, the global optimal solution w ^{(u + 1) for} w that maximizes Q ₂ (w, w ^(u) ) using the BFGS algorithm or the like. Can be requested.

  In accordance with the principle described above, the initialization unit 30 of the score function generation unit 24 sets initial values for the parameter W of the evaluation value model and the parameter Θ of the generation probability model, as in the first embodiment.

The score calculation unit 32 sets an initial value for each of the unlabeled samples x _{m by} the initialization unit 30 or the parameter W of the evaluation value model previously calculated by the evaluation value model calculation unit 34, and the initialization unit 30. The probability that the unlabeled sample x _m is positive data according to the above equation (7) using the parameter Θ of the generation probability model previously set by or the generation probability model calculation unit 36 previously calculated The value {circumflex over (P)} (+ | x _m ; W, Θ) and the negative probability value {circumflex over (P)} (− | x _m ; W, Θ) are calculated.

The evaluation value model calculation unit 34 calculates the probability values ^ P (+ | x _m ; W, Θ) and ^ P (− | x _m ; W, for each of the unlabeled samples x _m calculated by the score calculation unit 32. Θ), labeled samples x ⁺ _i , x ⁻ _j and unlabeled samples x _m , using the sigmoid function for the evaluation value model according to the above equations (27) and (28) The parameter W of the evaluation value model is calculated so as to maximize the approximate AUC (Area Under the Curve) value.

The generation probability model calculation unit 36 calculates the probability values ^ P (+ | x _m ; W, Θ) and ^ P (− | x _m ; W, for each of the unlabeled samples x _m calculated by the score calculation unit 32. and theta), the label has a sample x ⁺ _i, x ^- and _j, based on the unlabeled sample x _m, as in the first embodiment, the equation (23), according to equation (24), positive The generation probability model θ _{+, v} of the example data and the generation probability model θ _{−, v} of the negative example data are calculated.

  Similar to the first embodiment, the convergence determination unit 38 performs the calculation by the score calculation unit 32, the calculation by the evaluation value model calculation unit 34, and the generation probability until the convergence determination condition represented by the above equation (25) is satisfied. The calculation by the model calculation unit 36 is repeated, and the evaluation value model parameter W and the generation probability model parameter Θ used in the score function are stored in the score function storage unit 40.

  In addition, since it is the same as that of 1st Embodiment about the other structure and effect | action of the binary classification device based on 2nd Embodiment, description is abbreviate | omitted.

<Experimental example>
Next, experimental results when the binary classification device 100 according to the first embodiment is applied to a database 20 newsgroups (20News, see Non-Patent Document 2) often used for performance evaluation of an automatic text classification device. Tables 1 and 2 show. Table 1 shows the experimental results when the number of labeled samples is 100, and Table 2 shows the experimental results when the number of labeled samples is 200.

  This database is provided with category information to which the content main body and the content belong, and the total number of categories is 20. In performance evaluation, we created an evaluation data set that was classified into one target category (TC) and another 19 categories. Twenty categories included in the database were used as target categories (TC), and 20 evaluation data sets were created.

  In the experimental evaluation using each evaluation data set, a labeled sample and 5000 unlabeled samples used for calculation of the parameter values of the binary classification apparatus 100 were randomly extracted from the evaluation data set. Here, the labeled sample is a sample that uses both the content body and class information (positive and negative examples) as training data, and the unlabeled sample is a sample that uses only the content body information as training data. . That is, for the content extracted as an unlabeled sample, the score function parameters are calculated without using the class information recorded in the database. Also, from the remaining contents that were not extracted as labeled samples and unlabeled samples, 2000 documents were randomly extracted as contents that the user wanted to classify (hereinafter referred to as test samples) to evaluate the performance of binary classification. Using. The AUC value often used for the evaluation of binary classification was used as a scale for performance evaluation.

  Tables 1 and 2 show the results when the parameter values of the discrimination function of the binary classification device 100 are calculated using 100 and 200 labeled samples, respectively. Random sample extraction and experimental evaluation were repeated 10 times under the respective conditions for the number of labeled data and the target class, and the average AUC value was calculated. The column of “Method 1” in the table is the average AUC value obtained using the first embodiment, and “Method 2” is the average obtained by applying the technique of Non-Patent Document 2 to the binary classification. The AUC value, “method 3” is a function of the evaluation value model described in the first embodiment.

Is the standard deviation of the AUC values obtained in 10 experimental evaluations, indicating the average AUC value obtained by learning only with the labeled sample by maximizing the objective function of equation (10).

  From Tables 1 and 2, Method 1 obtained higher classification accuracy than Methods 2 and 3 in both cases where the number of labeled samples was 100 and 200. From comparison between Method 1 and Method 3, it was confirmed that the classification accuracy is improved by using the unlabeled sample for learning of the score function in the binary classification apparatus according to the present invention. Further, by comparing Method 1 and Method 2, the binary classification device according to the first embodiment of the present invention has an advantage in classification performance compared with the classification device according to the prior art of Non-Patent Document 2. You can see that

  Note that the present invention is not limited to the above-described embodiment, and various modifications and applications are possible without departing from the gist of the present invention.

  For example, in the above embodiment, the case where the binary classification learning device and the binary classification device are realized by one binary classification device has been described as an example. However, the present invention is not limited to this. A classification learning device and a binary classification device may be provided separately. In this case, the binary classification learning device may include the input unit 10, the training data database 22, the score function generation unit 24, and the output unit 90. Further, the binary classification device may include the input unit 10, the test data database 26, the score function storage unit 40, the ranking unit 28, and the output unit 90.

  In the present specification, the program has been described as an embodiment in which the program is installed in advance. However, the program can be provided by being stored in a computer-readable recording medium or provided via a network. Is also possible.

DESCRIPTION OF SYMBOLS 10 Input part 20 Operation part 22 Training data database 24 Score function generation part 26 Test data database 28 Ranking part 30 Initialization part 32 Score calculation part 34 Evaluation value model calculation part 36 Generation probability model calculation part 38 Convergence determination part 40 Score function Storage unit 90 Output unit 100 Binary classification device

Claims (8)

A labeled sample given whether it is positive example data related to a specific type or negative example data not related to the specific type, and the positive example data or the negative example data A binary classification learning device for learning a score function for binary classification based on training data consisting of an unlabeled sample that is unknown.
For each of the unlabeled samples, an evaluation value model expressed using a function that outputs a value indicating whether or not the data is positive data, a generation probability model of positive data, and negative data A score calculation unit that calculates a score indicating whether the unlabeled sample is the positive example data using a generation probability model;
An evaluation value model calculation unit that calculates the evaluation value model based on the score for each of the unlabeled samples calculated by the score calculation unit, the labeled sample, and the unlabeled sample;
Based on the score for each of the unlabeled samples calculated by the score calculation unit, the labeled sample, and the unlabeled sample, the generation probability model of the positive example data and the negative example data A generation probability model calculation unit for calculating a generation probability model of
Until the predetermined convergence determination condition is satisfied, the calculation by the score calculation unit, the calculation by the evaluation value model calculation unit, and the calculation by the generation probability model calculation unit are repeated, and the evaluation value model and the generation probability model A convergence determination unit that outputs the score function using
A binary classification learning device. The function of the evaluation value model is a linear function related to a feature vector extracted from the data,
2. The evaluation value model calculation unit calculates the evaluation value model so as to maximize an AUC (Area Under the Curve) value approximated by using a sigmoid function to the evaluation value model. Binary classification learning device. The generation probability model of the positive example data is obtained by modeling the probability distribution of the positive example data using a naive bayes model,
The generation probability model of the negative example data is obtained by modeling the probability distribution of the negative example data using a naive Bayes model,
The generation probability model calculation unit obtains the log likelihood of the labeled sample and the expected log likelihood of the unlabeled sample, which are obtained using the generation probability model of the positive example data and the generation probability model of the negative example data. The binary classification learning device according to claim 1, wherein the generation probability model of the positive example data and the generation probability model of the negative example data are calculated so as to maximize the sum of degrees. The score calculation unit calculates the score for each of the unlabeled samples in consideration of an entropy regularization term of a probability value given by the score,
The evaluation value model calculation unit calculates the evaluation value model in consideration of the regularization term of the model parameter of the evaluation value model,
The generation probability model calculation unit calculates a generation probability model of the positive example data and a generation probability model of the negative example data in consideration of a regularization term of model parameters of the generation probability model. The binary classification learning device according to claim 3. A score value indicating that the test data is a positive example based on the input test data and the score function learned by the binary classification learning device according to any one of claims 1 to 4. The binary classification device containing the score calculation part which calculates | requires. Negative example data that includes a score calculation unit, an evaluation value model calculation unit, a generation probability model calculation unit, and a convergence determination unit and is positive example data related to a specific type or not related to the specific type A score for binary classification based on training data consisting of a labeled sample given whether or not and whether the positive or negative data is unknown. A binary classification learning method in a binary classification learning device for learning a function,
The score calculation unit, for each of the unlabeled samples, an evaluation value model represented using a function that outputs a value indicating whether or not the data is a positive example, and a generation probability model of positive data And using a negative example data generation probability model to calculate a score indicating whether the unlabeled sample is the positive example data,
The evaluation value model calculation unit calculates the evaluation value model based on the score for each of the unlabeled samples calculated by the score calculation unit, the labeled sample, and the unlabeled sample. ,
The generation probability model calculation unit generates the positive example data based on the score, the labeled sample, and the unlabeled sample for each of the unlabeled samples calculated by the score calculation unit. Calculating a probability model and a generation probability model of the negative example data;
Until the convergence determination unit satisfies a predetermined convergence determination condition, the calculation by the score calculation unit, the calculation by the evaluation value model calculation unit, and the calculation by the generation probability model calculation unit are repeated, and the evaluation value model And a binary classification learning method for outputting the score function using the generation probability model. A binary classification method in a binary classification device including a score calculation unit,
The score calculation unit calculates a score value indicating that the test data is a positive example based on the input test data and the score function learned by the binary classification learning method according to claim 6. Binary classification method.   The program for functioning a computer as each part of the binary classification learning apparatus of any one of Claims 1-4, or the binary classification apparatus of Claim 5.