Large scale semi-supervised linear support vector machines

US 7,562,060 B2
Filed: 03/31/2006
Issued: 07/14/2009
Est. Priority Date: 03/31/2006
Status: Expired due to Fees

First Claim

Patent Images

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

receiving a set of web pages as training elements;

labeling some of the 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 implemented using a mean field annealing method, constructing a continuous loss function from a non-continuous loss function, train a linear classifier;

receiving unclassified web pages; and

classifying the unclassified web pages using the trained linear classifier.

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.

62 Citations

View as Search Results

20 Claims

1. A computerized method for semi-supervised learning for web page classification, comprising:
- receiving a set of web pages as training elements;
  
  labeling some of the 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 implemented using a mean field annealing method, constructing a continuous loss function from a non-continuous loss function, train a linear classifier;
  
  receiving unclassified web pages; and
  
  classifying the unclassified web pages using the trained linear classifier.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
- - 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 j ′
      
      ∈
      
      { - 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 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)})) .$
  - 13. The method of claim 12, wherein the modified Newton method uses a conjugate gradient for least squares method to solve large, sparse, weighted regularized least squares problem.
  - 14. The method of claim 1, 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.
  - 15. The method of claim 14, 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.
  - 16. The method of claim 15, 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}^{*} .$
  - 17. The method of claim 16, 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.
  - 18. The method of claim 15, 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 .$

19. A system for semi-supervised learning for web page classification, comprising:
- an input device operative to receive a set of web pages as training elements;
  
  a processor operative to label some of the 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 operative to use selected labeled elements and unlabeled elements as examples in a semi-supervised support vector machine implemented using a mean field annealing method, constructing a continuous loss function from a non-continuous loss function, to train a linear classifier;
  
  the input device further operative to receive unclassified web pages; and
  
  the processor further for operative to classify the received unclassified web pages using the trained linear classifier.

20. A computer program product stored on a computer-readable medium having instructions for performing a semi-supervised learning method for web page classification, the method comprising:
- receiving a set of web pages as training elements;
  
  labeling some of the 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 implemented using a mean field annealing method, constructing a continuous loss function from a non-continuous loss function, to train a linear classifier;
  
  receiving unclassified web pages; and
  
  classifying the unclassified web pages using the trained linear classifier.

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 Keerthi
Primary Examiner(s)
Vincent; David R
Assistant Examiner(s)
Kennedy; Adrian L

Application Number

US11/394,744
Publication Number

US 20070239642A1
Time in Patent Office

1,201 Days
Field of Search

706/25, 706/17, 706/20, 708/441, 708/440
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

62 Citations

20 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

62 Citations

20 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links