Method and apparatus for efficient training of support vector machines
View Patent ↗The present invention provides a system and method for building fast and efficient support vector classifiers for large data classification problems which is useful for classifying pages from the World Wide Web and other problems with sparse matrices and large numbers of documents. The method takes advantage of the least squares nature of such problems, employs exact line search in its iterative process and makes use of a conjugate gradient method appropriate to the problem. In one embodiment a support vector classifier useful for classifying a plurality of documents, including textual documents, is built by selecting a plurality of training documents, each training document having suitable numeric attributes which are associated with a training document vector, then initializing a classifier weight vector and a classifier intercept for a classifier boundary, the classifier boundary separating at least two document classes, then determining which training document vectors are suitable support vectors, and then re-computing the classifier weight vector and the classifier intercept for the classifier boundary using the suitable support vectors together with an iteratively reindexed least squares method and a conjugate gradient method with a stopping criterion.
1. A computer-readable storage medium storing a set of instructions for building a support vector classifier useful for classifying a plurality of documents, including textual documents, the set of instructions being executed by a processor, the set of instructions performing the steps of:
selecting a plurality of training documents, each training document having suitable numeric attributes which are associated with a training document vector;
initializing a classifier weight (w) and a classifier intercept (b) for a classifier boundary, the classifier boundary separating at least two document classes;
determining which training document vectors arc suitable support vectors;
re-computing the classifier weight vector and the classifier intercept for the classifier boundary using the suitable support vectors together with an iteratively reindexed least squares method and a conjugate gradient method with a stopping criterion; and
storing the recomputed classifier weight vector and the classifier intercept for the classifier boundary at a data store in communication with the processor.
2. The computer-readable storage medium of claim 1 wherein the textual documents include sparse data matrices.
3. The computer-readable storage medium of claim 2 wherein the textual documents are from the World Wide Web.
4. The computer-readable storage medium of claim 1 wherein β is assigned an initial value of 0, β= (w,b), and wherein β is used to build the support vector classifier.
5. The computer-readable storage medium of claim 1 wherein a first known value for β associated with a first regularization value is used to calculate a second value of β for a second regularization value.
6. The computer-readable storage medium of claim 1 wherein the iteratively re-indexed least squares method includes an exact line search.
7. The computer-readable storage medium of claim 1 , wherein the conjugate gradient method includes:
setting β 0 =β k ;
computing z 0 =ƒ−Aβ 0 , r 0 =A T z 0 −λβ 0 , p 0 =r 0 ; and
for j=0, 1 . . . computing:
q j =Ap j
γ j =∥r j ∥ 2 /(∥ q j ∥2 +λ∥p j ∥ 2 )
β j+1 =βj+γ j p j
z j+1 =z j +γ j p j
r j+1 =A T z j+1 −λβ j+1 ; and
if r j+1 ≈0
stop the conjugate gradient method, else computing:
ω j =∥r j+1 ∥ 2 /∥r j ∥ 2 ; and
p j+1 =r j+1 +ω j p j .
8. The computer-readable storage medium of claim 1 wherein the stopping criterion for the conjugate gradient method is r j+1 ≈0.
9. The computer-readable storage medium of claim 7 wherein r j+1 ≈0 is implemented using the condition ∥r j+1 ∥≦ε∥∥z j+1 ∥ for ε=10 −3 .
10. The computer-readable storage medium of claim 1 wherein for a first value of β, iterations of the conjugate gradient method are substantially reduced, wherein the iteratively reindexed least squares method and the conjugate gradient method are completed using ε=10 −3 to obtain a second value of β, and wherein the iteratively reindexed least squares method and the conjugate gradient method are repeated using ε=10 −6 .
11. The computer-readable storage medium of claim 1 wherein β 0 =(γ{acute over (ω)}, b 0 ), wherein γ=(p 22 q 1 −p 12 q 2 )/d, and b 0 =(p 11 q 2 −p 12 q 1 )/d, and wherein
p
11
=
λ
ω
~
2
+
∑
i
∈
I
ρ
i
;
p
12
=
∑
i
∈
I
ρ
i
(
ω
·
x
i
)
;
q
1
=
∑
i
∈
I
ρ
i
t
i
(
ω
~
·
x
i
)
;
q
2
=
∑
i
∈
I
ρ
i
t
i
;
and
d
=
p
11
p
22
-
(
p
12
)
2
.