Large scale semi-supervised linear support vector machines

US 20070239642A1
Filed: 03/31/2006
Published: 10/11/2007
Est. Priority Date: 03/31/2006
Status: Active Grant

First Claim

Patent Images

1. A computerized method for semi-supervised learning, comprising:

receiving a set of training elements;

labeling elements of the set of training elements that are determined to fall within a classification group, the set of training elements thereby having labeled elements and unlabeled elements;

using selected labeled elements and unlabeled elements as examples in a semi-supervised support vector machine to select a linear classifier;

receiving unclassified data elements; and

using the selected linear classifier for classifying the received unclassified data elements.

View all claims

9 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A computerized system and method for large scale semi-supervised learning is provided. The training set comprises a mix of labeled and unlabeled examples. Linear classifiers based on support vector machine principles are built using these examples. One embodiment uses a fast design of a linear transductive support vector machine using multiple switching. In another embodiment, mean field annealing is used to form a very effective semi-supervised support vector machine. For both these embodiments, the finite Newton method is used as the base method for achieving fast training

92 Citations

View as Search Results

21 Claims

1. A computerized method for semi-supervised learning, comprising:
- receiving a set of training elements;
  
  labeling elements of the set of training elements that are determined to fall within a classification group, the set of training elements thereby having labeled elements and unlabeled elements;
  
  using selected labeled elements and unlabeled elements as examples in a semi-supervised support vector machine to select a linear classifier;
  
  receiving unclassified data elements; and
  
  using the selected linear classifier for classifying the received unclassified data elements.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
- - 2. The method of claim 1, wherein the number of unlabeled elements in the set of training elements that fall within the classification group is specified as an estimate.
  - 3. The method of claim 1, wherein the semi-supervised support vector machine uses a finite Newton method for fast training.
  - 4. The method of claim 3, wherein a step w^(k)=w^(k)+n^(k)in the finite Newton method for determining a weight vector w in a k-th iteration, with n being a Newton step, is given by solving the following linear system associated with a weighted linear regularized least squares problem over a data subset defined by a set of active indices j(w^(k)):
    - [λ
      
      I+X_j(w_(k)₎^TC_j(w_(k)₎X_j(w_(k)₎] w^(k)=X_j(w_(k)₎^TC_j(w_(k)₎Y_j(w_(k)₎where I is the identity matrix, and wherein once w^(k)is obtained, w^(k+1)is obtained from w^(k+1)=w^(k)+δ
      
      ^(k)n^(k)by setting w^(k+1)=w^(k)+δ
      
      ^k( w^(k)−
      
      w^(k)) after performing an exact line search for δ
      
      ^k, which is by exactly solving a one-dimensional minimization problem;
      
      $δ^{(k)} = \underset{δ \geq 0}{\arg \min} f (w^{(k)} + δ ({\overline{w}}^{(k)} - w^{(k)}))$
  - 5. The method of claim 4, wherein the modified Newton method uses a conjugate gradient for least squares method to solve large, sparse, weighted regularized least squares problem.
  - 6. The method of claim 1, wherein the semi-supervised support vector machine is implemented using a modified finite Newton method with one or multiple switching of labels of unlabeled example elements from the training set.
  - 7. The method of claim 6, wherein the objective function is as follows. $w^{*} = \arg$
    - ⁢
      
      min w ∈
      
      ⁢
      
      ℝ
      
      d , { y i ∈
      
      { - 1 , + 1 } } j = 1 u ⁢
      
      λ
      
      2 ⁢
      
      
      
      w 
      
      2 + 1 2 ⁢
      
      l ⁢
      
      ∑
      
      i = 1 l ⁢
      
      max ⁡
      
      [ 0 , 1 - y i ⁡
      
      ( w T ⁢
      
      x i ) ] 2 + λ
      
      ′
      
      2 ⁢
      
      u ⁢
      
      ∑
      
      j = 1 u ⁢
      
      max ⁡
      
      [ 0 , 1 - y j ′
      
      ⁡
      
      ( w T ⁢
      
      x j ′
      
      ) ] 2 $subject to; \frac{1}{u} \sum_{j = 1}^{u} \max [0, sign (w^{T} x_{j}^{'})] = r$
  - 8. The method of claim 7, comprising of optimizing w for fixed y′
    - _jusing the finite Newton method.
  - 9. The method of claim 8, wherein a step w^(k)=w^(k)+n^(k)in the finite Newton method for determining a weight vector w in a k-th iteration, with n being a Newton step, is given by solving the following linear system associated with a weighted linear regularized least squares problem over a data subset defined by a set of active indices j(w^(k)):
    - [λ
      
      I+X_j(w_(k)₎^TC_j(w_(k)₎X_j(w_(k)₎] w^(k)=X_j(w_(k)₎^TC_j(w_(k)₎Y_j(w_(k)₎where I is the identity matrix, and wherein once w^(k)is obtained, w^(k+1)is obtained from w^(k+1)=w^(k)+δ
      
      ^(k)n^(k)by setting w^(k+1)=w^(k)+δ
      
      ^k( w^(k)−
      
      w^(k)) after performing an exact line search for δ
      
      ^k, which is by exactly solving a one-dimensional minimization problem;
      
      $δ^{(k)} = \underset{δ \geq 0}{\arg \min} f (w^{(k)} + δ ({\overline{w}}^{(k)} - w^{(k)}))$
  - 10. The method of claim 9, wherein the modified Newton method uses a conjugate gradient for least squares method to solve large, sparse, weighted regularized least squares problem.
  - 11. The method of claim 7, comprising of optimizing y′
    - _jfor a fixed w by switching one or more pairs of labels.
  - 12. The method of claim 1, wherein the semi-supervised support vector machine is implemented using a mean field annealing method.
  - 13. The method of claim 12, wherein a step w^(k)=w^(k)+n^(k)in the finite Newton method for determining a weight vector w in a k-th iteration, with n being a Newton step, is given by solving the following linear system associated with a weighted linear regularized least squares problem over a data subset defined by a set of active indices j(w^(k)):
    - [λ
      
      I+X_j(w_(k)₎^TC_j(w_(k)₎X_j(w_(k)₎] w^(k)=X_j(w_(k)₎^TC_j(w_(k)₎Y_j(w_(k)₎where I is the identity matrix, and wherein once w^(k)is obtained, w^(k+1)is obtained from w^(k+1)=w^(k)+δ
      
      ^(k)n^(k)by setting w^(k+1)=w^(k)+δ
      
      ^k( w^(k)−
      
      w^(k)) after performing an exact line search for δ
      
      ^k, which is by exactly solving a one-dimensional minimization problem;
      
      $δ^{(k)} = \underset{δ \geq 0}{\arg \min} f (w^{(k)} + δ ({\overline{w}}^{(k)} - w^{(k)}))$
  - 14. The method of claim 13, wherein the modified Newton method uses a conjugate gradient for least squares method to solve large, sparse, weighted regularized least squares problem.
  - 15. The method of claim 12, comprising relaxing discrete variables to continuous probability variables in mean field annealing method, wherein a non-negative temperature parameter T is used to track a global optimum.
  - 16. The method of claim 15, comprising writing a semi-supervised support vector objective as follows:
    - $w^{*} = \underset{w \in ℝ^{d}, {μ_{j} \in {0, 1}}_{j = 1}^{u}}{\arg \min} \frac{λ}{2} { w }^{2} + \frac{1}{2 l} \sum_{i = 1}^{l} {\max [0, 1 - y_{i} (w^{T} x_{i})]}^{2} + \frac{λ^{'}}{2 u} \sum_{j = 1}^{u} (μ_{j} {\max [0, 1 - (w^{T} x_{j}^{'})]}^{2} + (1 - μ_{j}) {\max [0, 1 + (w^{T} x_{j}^{'})]}^{2})$ wherein binary valued variables μ
      
      _j=(1+y_j)/2 are introduced, p_jε
      
      [0,1] denote the belief probability that the unlabeled example belongs to the positive class, l is the number of labeled example elements, u is the number of unlabeled example elements, wherein λ and
      
      λ
      
      ′
      
      are regularization parameters, and the Ising model of mean field annealing motivates the following objective function, where the binary variables μ
      
      _jare relaxed to probability variables p_j, and include entropy terms for the distributions defined by p_j;
      
      $\begin{matrix} w_{T}^{*} = \underset{w \in ℝ^{d}, {p_{j} \in [0 1]}_{j = 1}^{u}}{\arg \min} \frac{λ}{2} { w }^{2} + \frac{1}{2 l} \sum_{i = 1}^{l} {\max [0, 1 - y_{i} (w^{T}, x_{i})]}^{2} + \frac{λ^{'}}{2 u} \sum_{j = 1}^{u} (p_{j} {\max [0, 1 - (w^{T} x_{j}^{'})]}^{2} + (1 - p_{j}) {\max [0, 1 + (w^{T} x_{j}^{'})]}^{2}) + \frac{T}{2 u} \sum_{j = 1}^{u} (p_{j} \log p_{j} + (1 - p_{j}) \log (1 - p_{j})) & (8) \end{matrix}$ wherein the temperature T parameterizes a family of objective functions, wherein the objective function for a fixed T is minimized under the following class balancing constraints;
      
      $\frac{1}{u} \sum_{j = 1}^{u} p_{j} = r$ where r, the fraction of the number of unlabeled examples belonging to the positive class.
  - 17. The method of claim 16, wherein the solution to the optimization problem is tracked as the temperature parameter T is lowered to 0, wherein the final solution is given as:
    - $w^{*} = \lim_{T \to 0} w_{T}^{*}$
  - 18. The method of claim 17, comprising optimizing w keeping p fixed, wherein the call to finite Newton method is made on data {circumflex over (X)}=[X^TX^′
    - TX^′
      
      T]^Twhose first l rows are formed by labeled examples, and the next 2u rows are formed by unlabeled examples appearing as two repeated blocks, wherein the associated label vector and cost matrix are given by;
      
      $C = diag \overset{\hat{Y} = [y_{1}, y_{2} \dots y_{l}, \overset{\overset{u}{︷}}{1, 1, \dots 1,} \overset{\overset{u}{︷}}{- 1, - 1 \dots - 1}]}{[\overset{\overset{l}{︷}}{\frac{1}{l} \dots \frac{1}{l}}, \overset{\overset{u}{︷}}{\frac{λ^{'} p_{1}}{u} \dots \frac{λ^{'} p_{u}}{u}} \overset{\overset{u}{︷}}{\frac{λ^{'} (1 - p_{1})}{u} \dots \frac{λ^{'} (1 - p_{u})}{u}}]}$ where y₁,y₂. . . y_lare labels of the labeled example elements.
  - 19. The method of claim 16, comprising optimizing p for a fixed w, a Lagrangian is constructed using Lagrangian multiplier v as follows:
    - $ℒ = \frac{λ^{'}}{2 u} \sum_{j = 1}^{u} (p_{j} {\max [0, 1 - (w^{T} x_{j}^{'})]}^{2} + (1 - p_{j}) {\max [0, 1 + (w^{T} x_{j}^{'})]}^{2}) + \frac{T}{2 u} \sum_{j = 1}^{u} (p_{j} \log p_{j} + (1 - p_{j}) \log (1 - p_{j})) - υ [\frac{1}{u} \sum_{j = 1}^{u} p_{j} - r]$ wherein, differentiating the Lagrangian with respect to p_j, produces;
      
      $\frac{\partial ℒ}{\partial p_{j}} = \frac{λ^{'}}{2 u} ({\max [0, 1 - (w^{T} x_{j}^{'})]}^{2} - {\max [0, 1 + (w^{T} x_{j}^{'})]}^{2}) + \frac{T}{2 u} \log \frac{p_{j}}{1 - p_{j}} - \frac{v}{u} = 0$ defining
      g_j=λ
      
      ′
      
      (max[0,1−
      
      (w^Tx′
      
      _j)]²−
      
      max[0,1+(w^Tx′
      
      _j)]²), wherein the expression for p_jis given by;
      
      $p_{j} = \frac{1}{1 + ⅇ^{\frac{g_{j} - 2 v}{T}}}$ wherein, substituting the expression for p_jin the balance constraint, a one-dimensional non-linear equation in v is as follows;
      
      $\frac{1}{u} \sum_{j = 1}^{u} \frac{1}{1 + ⅇ^{\frac{g_{i} - 2 v}{T}}} = r$ wherein the value of v is computed exactly by using a hybrid combination of Newton-Raphson iterations and the bisection method to find the root of the function $B (v) = \frac{1}{u} \sum_{i = l + 1}^{l + u} \frac{1}{1 + ⅇ^{\frac{g_{i} - v}{T}}} - r .$

20. A system for semi-supervised learning, comprising:
- an input device for receiving a set of training elements;
  
  a processor for labeling elements of the set of training elements that are determined to fall within a classification group, the set of training elements thereby having labeled elements and unlabeled elements;
  
  the processor further for using selected labeled elements and unlabeled elements as examples in a semi-supervised support vector machine to select a linear classifier;
  
  the input device further for receiving unclassified data elements; and
  
  the processor further for using the selected linear classifier for classifying the received unclassified data elements.

21. A computer program product stored on a computer-readable medium having instructions for performing a semi-supervised learning method, the method comprising:
- receiving a set of training elements;
  
  labeling elements of the set of training elements that are determined to fall within a classification group, the set of training elements thereby having labeled elements and unlabeled elements;
  
  using selected labeled elements and unlabeled elements as examples in a semi-supervised support vector machine to select a linear classifier;
  
  receiving unclassified data elements; and
  
  using the selected linear classifier for classifying the received unclassified data elements.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
R2 Solutions LLC (Acacia Research Corporation)
Original Assignee
Yahoo! Inc. (Apollo Global Management, Inc.)
Inventors
Sindhwani, Vikas, Selvaraj, Sathiya

Granted Patent

US 7,562,060 B2
Time in Patent Office

Days
Field of Search
US Class Current

706/25
CPC Class Codes

G06F 18/2411 based on the proximity to a...

G06N 3/08 Learning methods

Large scale semi-supervised linear support vector machines

First Claim

9 Assignments

0 Petitions

Accused Products

Abstract

92 Citations

21 Claims

Specification

Solutions

Use Cases

Quick Links

Large scale semi-supervised linear support vector machines

First Claim

9 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

92 Citations

21 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links