Improved sparse least-squares support vector machines

  • 格式:pdf
  • 大小:93.69 KB
  • 文档页数:7
i; j ∈S i=1 j ∈S
Setting the partial derivatives with respect to ÿ and b to zero, and dividing through by 2 =‘, yields
‘ ‘
ÿi
i∈S j =1
kij + ‘b =
j =1
yj
and
ÿi
School of Information Systems, University of East Anglia, Norwich NR4 7TJ, UK Received 4 September 2001; received in revised form 4 March 2002; accepted 10 March 2002
2 ‘
+

(yi − w · (xi ) − b)2 ;
(3)
i=1
The optimal expansion can be found by solving the system of linear equations (2) substituting = (K + ‘ −1 I ).
G.C. Cawley, N.L.C. Talbot / Neurocomputing 48 (2002) 1025 – 1031

This work was supported by Royal Society Research Grant RSRG-22270. Corresponding author. E-mail address: gcc@ (G.C. Cawley).
0925-2312/02/$ - see front matter c 2002 Elsevier Science B.V. All rights reserved. PII: S 0 9 2 5 - 2 3 1 2 ( 0 2 ) 0 0 6 0 6 - 9
Keywords: Support vector machines; Sparse approximation; Kernel ridge regression
1. Least-squares support vector machines The least-squares support vector machine (LS-SVM), given training data, D = d {xi ; yi }‘ i=1 ; x ∈ X ⊂ R ; yi ∈ Y ⊂ R, constructs a linear regression model, f (x) = w · (x) + b, in a high-dimensional feature space, F( : X → F), induced by a kernel function deÿning the inner product K(x; x ) = (x) · (x ). A commonly used kernel is the Gaussian radial basis function, K(x; x ) = exp{− −2 x − x 2 }. The optimal values for the weight vector, w, and bias, b, are given by the minimum of an
1027
The generalisation performance of sparse approximations of least-squares support vector machines can be further improved by including the residuals of patterns not used in the kernel expansion within the objective function. The weight vector, w, is then represented as a weighted sum of selected training patterns, w = i∈S ÿi (xi ), where S ⊂ {1; 2; : : : ; ‘} is the set of indices of training patterns used to form the kernel expansion. The objective function (3) can then be written as 2 ‘ 1 yi − W (ÿ; b) = ÿi ÿj kij + ÿj kij − b : 2 ‘
Neurocomputing 48 (2002) 1025 – 1031
/locate/neucom
Letters
Improved sparse least-squares support vector machines
Gavin C. Cawley ∗ , Nicola L.C. Talbot
1026
G.C. Cawley, N.L.C. Talbot / Neurocomputing 48 (2002) 1025 – 1031
objective function W (w; b) = 1 w 2
2 ‘
+
i=1
(yi − w · (xi ) − b)2 ;
(1)
implementing a quadratic regularisation of a sum-of-squares empirical risk. The representer theorem [3] states that the solution of this problem can be written as an expansion in terms of training patterns,
Abstract Suykens et al. (Neurocomputing (2002), in press) describe a weighted least-squares formulation of the support vector machine for regression problems and present a simple algorithm for sparse approximation of the typically fully dense kernel expansions obtained using this method. In this paper, we present an improved method for achieving sparsity in least-squares support vector machines, which takes into account the residuals for all training patterns, rather than only those incorporated in the sparse kernel expansion. The superiority of this algorithm is demonstrated on the motorcycle and Boston housing data sets. c 2002 Elsevier Science B.V. All rights reserved.
k =1
where
= {!ij }i; j∈S , !ij = (‘= 2 )kij +
i∈S
‘ kir + 2
‘ j =1
kjr kji + b


kir =
i=1 i=1
Hale Waihona Puke yi kir ;∀r ∈ S:
These equations can be expressed as a system of |S| + 1 linear equations in |S| + 1 unknowns, c ÿ ; = ‘ T b ‘ yk
2. Improved sparsiÿcation In this section, we present two modiÿcations to the least-squares support vector machine. The ÿrst modiÿcation is based on the observation that changing the number of training patterns alters the balance between the sum-of-square empirical risk and the quadratic regulariser in the objective function (1). This implies that model selection based on cross-validation schemes will generally lead to under-regularised models. This can easily be remedied by quadratic regularisation of a mean-squared-error empirical risk, W (w; b) = 1 w 2
T
0
b
=
y 0
;
(2)
T T where = (K + −1 I ), K = {kij = K(xi ; xj )}‘ i; j =1 , 1 = (1; 1; : : : ; 1) , y = (yi ; y2 ; : : : ; y‘ ) and = ( i ; 2 ; : : : ; ‘ )T . The kernel expansions describing least-squares support vector machines are typically fully dense, i.e. i = 0; ∀i ∈ {1; 2; : : : ; ‘}. Suykens et al. [6,7] advocate the use of the following algorithm to obtain a sparse approximation: A LS-SVM is trained on the entire data set, yielding a vector of coe cients, . A small fraction of the data (say 5%), associated with coe cients having the smallest magnitudes, are discarded and the LS-SVM retrained on the remaining data. This process is repeated until a su ciently small kernel expansion is obtained. It is observed in [7] that model selection should be performed at each iteration to ÿnd new values for the regularisation parameter, and any kernel parameters, such that optimal generalisation is achieved.