Method for ensemble predictive modeling by multiplicative adjustment of class probability: APM (adjusted probability model)

• US 7,020,593 B2
• Filed: 12/04/2002
• Issued: 03/28/2006
• Est. Priority Date: 12/04/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Natarajan, Ramesh, Hosking, Jonathan R., Hong, Se June
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US10/309,191
• Publication Number:
  US 20040111169A1
• Time in Patent Office: 1,210 Days
• Field of Search: 703/2, 703/6, 703/22, 706/20, 706/12, 706/14, 702/19, 341/107
• US Class Current: 703/2
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation

Abstract

A new method is used to model the class probability from data that is based on a novel multiplicative adjustment of the class probability by a plurality of items of evidence induced from training data. The optimal adjustment factors from each item of evidence can be determined by several techniques, a preferred embodiment thereof being the method of maximum likelihood. The evidence induced from the data can be any function of the feature variables, the simplest of which are the individual feature variables themselves. The adjustment factor of an item of evidence E_j is given by the ratio of the conditional probability P(C|E_j) of the class C given E_j to the prior class probability P(C), exponentiated by a parameter a_j. The method provides a new and useful way to aggregate probabilistic evidence so that the final model output exhibits a low error rate for classification, and also gives a superior lift curve when distinguishing between any one class and the remaining classes. A good prediction for the class response probability has many uses in data mining applications, such as using the probability to compute expected values of any function associated with the response, and in many marketing applications where lift curves are generated for selected prioritized target customers.

Claims

1. A computer implemented method for aggregating items of evidence from multiple probability predictive models providing improved class probability estimation by multiplicative adjustment of class probability comprising the steps of:

a) combining items of probabilistic evidence given by prior probability of a class with successive multiplicative adjustments to obtain an adjusted probability model for a class of interest; and

b) optimizing the adjusted probability model by optimizing a loss function, which measures the fitness of the predictions, to obtain optimal values of adjustment parameters for the adjusted probability model; and

c) providing the APM in a computer usable form to one or more processors to allow class probability estimation to introduced input.

2. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 1, wherein the step of optimizing parameters of the adjusted probability model is performed subject to regularization constraints and subject to the use of a cross-validation procedure to determine an optimal value of the constraints.

3. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 1, further comprising the step of using the adjusted probability model for producing a lift curve.

4. A computer implemented method for aggregating items of evidence from multiple probability predictive models, comprising the steps of:

a) specifying a probability model for aggregating multiple evidences as defined by $P(C<br><br><br><br>X)\propto <br><br>P<br><br>\left(C\right)\times <br><br>\underset{j=1}{\overset{m^{\mathrm{\prime <br><br>}}}{\prod <br><br>}}<br><br><br><br>{\left[\frac{P(C<br><br><br><br>E_j)}{P<br><br>\left(C\right)}\right]}^{a_j},$

where P(C) is prior probability of a class C, P(C|E_j) is probability of the class C given evidence E_j(X), with P(C|E_j) being directly estimated from examples in training data (X,y), and a_j are adjustment parameters having a role of controlling influence of the ratio P(C|E_j)/P(C);

b) transforming training data to obtain a Q matrix, where an entry q_ij of the Q matrix is computed by $q_{\mathrm{ij}}={\lg }_2<br><br>\left(\frac{\left(1-P<br><br>\left(C\right)\right)<br><br>P(C<br><br><br><br>X_{\mathrm{ij}})}{P<br><br>\left(C\right)<br><br>(1-P<br><br>\left(C<br><br><br><br>X_{\mathrm{ij}})\right)}\right),$

where P(C) is a prior probability based on various evidences applied to each training example;

c) optimizing a loss function given by $\mathrm{Loss}=-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\left[y_i<br><br>{\lg }_2<br><br>P(C<br><br><br><br>X_i\right)+\left(1-y_i\right)<br><br>{\lg }_2\left(1-P<br><br>\left(C<br><br><br><br>X_i)\right)\right]$

to obtain optimal values of adjustment parameters a_j, denoted a_u, where subscript u stands for unconstrained; and

d) providing the probability model derived with consideration of the adjustment parameters to one or more computer processors to allow class probability estimation to introduced input.

5. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 4, wherein the step of optimizing comprises the steps of:

a) initializing adjustment a parameters to zero for j=1 through m′

;

b) computing an n-vector P whose ith element is P_i=P(C|X_i) and forming a diagonal matrix D whose ith diagonal element is P_i(1−

P_i);

c) computing an update Δ

a=(Q^TDQ)<sup>−

1</sup>Q^T(y−

P);

d) updating a←

a+Δ

a; and

e) stopping if maximum absolute value of Δ

a_j'"'"'s is less than a predetermined threshold;

f) otherwise, returning to step (b) and continue iteration.

6. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 4, further comprising the step of optimizing a loss function to obtain optimal values of the adjustment parameters a_j subject to a regularization constraint Σ

a_i²={circumflex over (M)}, where a suitable optimal value for {circumflex over (M)}^ is determined using a cross-validation procedure to obtain an adjusted probability model-regularized (APMR).

7. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 6, wherein the cross-validation procedure comprises the steps of:

a) randomly permuting an order of the examples in X and partitioning the training set in to v subsets W₁, W₂, . . . , W_v;

b) finding a_(u) on training data X;

c) trying APMR on a fixed number of M values between 0.1 and ∥

a_(u)∥

² and finding a value M′

that leads to the minimum value for CL(M), where total cross-validation estimate for the loss for a given value M is then denoted by CL(M)=Σ

_uLoss(W_u), and considering an interval of the adjacent values M₋

and M₊ bracketing M′

;

d) repeating APMR for a fixed number of M values in (M₋

, M₊); and

e) using a best value {circumflex over (M)}^ with a minimum cross-validation loss CL({circumflex over (M)}) and obtain an APMR solution using this value with an entire training set X.

8. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 7, wherein the step of finding a_(u) on training data X comprises the steps of:

a) initializing adjustment a_j parameters to zero for j=1 through m′

;

b) computing an n-vector P whose ith element is P_i=P(C|X_i)and forming a diagonal matrix D whose ith diagonal element is P_i(1−

P_i);

c) computing an update Δ

a=(Q^TDQ)<sup>−

1</sup>Q^T(y−

P);

d) updating a←

a+Δ

a; and

e) stopping if maximum absolute value of Δ

a_j'"'"'s is less than a predetermined threshold;

f) otherwise, returning to step (b) and continue iteration.

9. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 7, wherein the step of trying APMR includes the steps of:

a) Initializing $a={a_{\left(u\right)}<br><br>\left(\frac{M}{{<br><br>a_{\left(u\right)}<br><br>}^2}\right)}^{\frac{1}{2}}$

and λ

=0;

b) Computing P;

P_i=P(C|X_i), i=1, . . . , n;

c) Forming a diagonal matrix D whose ith diagonal element is P_i(1−

P_i), i=1, . . . , n;

d) Computing vector v=Q^T(P−

y)−

2λ

a and vector s=∥

a∥

²−

M;

e) Computing Δ

λ

=[4a(Q^TDQ+2λ

)<sup>−

1</sup>a^T}<sup>−

1</sup>[s−

2a(Q^TDQ+2λ

)<sup>−

1</sup>r and Δ

a=(Q^TDQ+2λ

)<sup>−

1</sup>[2a Δ

λ

+r];

f) Determining if maximum absolute value of Δ

a_j'"'"'s is less than some small threshold, say 10<sup>−

10</sup>;

If not, updating a←

a+Δ

a and λ

←

λ

+Δ

λ

;

Otherwise, stopping and outputting final model.

10. The computer implemented method for aggregating items of evidence from multiple probability predictive models recited in claim 4, further comprising the step of using the adjusted probability model for producing a lift curve.