Lecture 4: Generalization Error of SVM

Lecture 04 Generalization error of SVM. 18.465 Assume we have samples z1 = (x1 , y1 ), . . . , zn = (xn , yn ) as well as a new sample zn+1 . The classifier trained on the data z1 , . . . , zn is fz1 ,...,zn . The error of this classifier is Error(z1 , . . . , zn ) = Ezn+1 I(fz1 ,...,zn (xn+1 ) �= yn+1 ) = Pzn+1 (fz1 ,...,zn (xn+1 ) �= yn+1 ) and the Average Generalization Error A.G.E. = E Error(z1 , . . . , zn ) = EEzn+1 I(fz1 ,...,zn (xn+1 ) �= yn+1 ). Since z1 , . . . , zn , zn+1 are i.i.d., in expectation training on z1 , . . . , zi , . . . , zn and evaluating on zn+1 is the same as training on z1 , . . . , zn+1 , . . . , zn and evaluating on zi . Hence, for any i, A.G.E. = EEzi I(fz1 ,...,zn+1 ,...,zn (xi ) �= yi ) and ⎤ ⎡ ⎥ ⎢ � ⎥ ⎢ 1 n+1 ⎥ I(f (x ) � = y ) A.G.E. = E ⎢ z1 ,...,zn+1 ,...,zn i i ⎥. ⎢n + 1 ⎦ ⎣ i=1 � �� � leave-one-out error Therefore, to obtain a bound on the generalization ability of an algorithm, it’s enough to obtain a bound on its leave-one-out error. We now prove such a bound for SVMs. Recall that the solution of SVM is �n+1 ϕ = i=1 αi0 yi xi . Theorem 4.1. min(# support vect., D2 /m2 ) n+1 where D is the diameter of a ball containing all xi , i ≤ n + 1 and m is the margin of an optimal hyperplane. L.O.O.E. ≤ + + + + + + + - Remarks: • dependence on sample size is • dependence on margin is m 1 n 1 m2 • number of support vectors (sparse solution) - - - - Lecture 04 Generalization error of SVM. 18.465 Lemma 4.1. If xi is a support vector and it is misclassified by leaving it out, then αi0 ≥ 1 D2 . Given Lemma 4.1, we prove Theorem 4.1 as follows. Proof. Clearly, L.O.O.E. ≤ # support vect. . n+1 Indeed, if xi is not a support vector, then removing it does not affect the solution. Using Lemma 4.1 above, � I(xi is misclassified) ≤ i∈supp.vect � αi0 D2 = D2 � αi0 = i∈supp.vect In the last step we use the fact that � αi0 = 1 m2 . Indeed, since |ϕ| = D2 . m2 1 m, � 1 2 = |ϕ| = ϕ · ϕ = ϕ · αi0 yi xi m2 � = αi0 (yi ϕ · xi ) � � � = αi0 (yi (ϕ · xi + b) − 1) + αi0 − b αi0 yi � �� � � �� � 0 = � 0 αi0 � We now prove Lemma 4.1. Let u ∗ v = K(u, v) be the dot product of u and v, and �u� = (K(u, u)) 1/2 be the corresponding L2 norm. Given x1 , · · · , xn+1 ∈ Rd and y1 , · · · , yn+1 ∈ {−1, +1}, recall that the primal problem of training a support vector classifier is argminψ 12 �ψ�2 subject to yi (ψ ∗ xi + b) ≥ 1. Its dual � � � � 2 problem is argmaxα αi − 12 � αi yi xi � subject to αi ≥ 0 and αi yi = 0, and ψ = αi yi xi . Since the � � 2 1 1 1 Kuhn-Tucker condition can be satisfied, minψ 2 ψ ∗ ψ = maxα αi − 2 � αi yi xi � = 2m2 , where m is the margin of an optimal hyperplane. � 2 αi yi xi � . Let α0 = argmaxα w(α) subject to αi ≥ 0 and αi yi = 0. Let � α� = argmaxα w(α) subject to αp = 0, αi ≥ 0 for i �= p and αi yi = 0. In other words, α0 corresponds to Proof. Define w(α) = � i αi − 12 � � the support vector classifier trained from {(xi , yi ) : i = 1, · · · , n+1} and α� corresponds to the support vector ⎛1 ⎞ p−1 p p+1 n+1 ↓ ↓ ↓ ↓ ↓ classifier trained from {(xi , yi ) : i = 1, · · · , p − 1, p + 1, · · · , n + 1}. Let γ = ⎝0, · · · , 0 , 1, 0 , · · · , 0 ⎠. It follows that w(α0 − αp0 · γ) ≤ w(α� ) ≤ w(α0 ). (For the dual problem, α� maximizes w(α) with a constraint that αp = 0, thus w(α� ) is no less than w(α0 − αp0 · γ), which is a special case that satisfies the constraints, including αp = 0. α0 maxmizes w(α) with a constraint αp ≥ 0, which raises the constraint αp = 0, thus w(α� ) ≤ w(α0 ). For the primal problem, the training problem corresponding to α� has less samples (xi , yi ), where i �= p, to separate with maximum margin, thus its margin m(α� ) is no less than the margin m(α0 ), Lecture 04 Generalization error of SVM. 18.465 and w(α� ) ≤ w(α0 ). On the other hand, the hyperplane determined by α0 − αp0 · γ might not separate (xi , yi ) for i = � p and corresponds to a equivalent or larger “margin” 1/�ψ(α0 − αp0 · γ)� than m(α� )). Let us consider the inequality max w(α� + t · γ) − w(α� ) ≤ w(α0 ) − w(α� ) ≤ w(α0 ) − w(α0 − αp0 · γ). t For the left hand side, we have �2 � 1� �� � � w(α� + tγ) = αi� + t − � αi yi xi + t · yp xp � 2 �� � �� � � 1� t2 �2 2 αi� yi xi � − t αi� yi xi ∗ (yp xp ) − �yp xp � = αi� + t − � 2 2 � t2 2 = w(α� ) + t · (1 − yp · ( αi� yi xi ) ∗xp ) − �xp � 2 �� � � ψ� and w(α� + tγ) − w(α� ) = t · (1 − yp · ψ � ∗ xp ) − t2 2 2 �xp � . Maximizing the expression over t, we find t = (1 − yp · ψ � ∗ xp )/�xp �2 , and 2 max w(α� + tγ) − w(α� ) = t 1 (1 − yp · ψ � ∗ xp ) . 2 �xp �2 For the right hand side, w(α0 − αp0 · γ) = � 1 � 0 αi0 − αp0 − � α yi xi −αp0 yp xp �2 2 � ��i � ψ0 1 1 � 0 �2 αi0 − αp0 − �ψ0 �2 + αp0 yp ψ0 ∗ xp − α �xp �2 2 2 p 1 � 0 �2 = w(α0 ) − αp0 (1 − yp · ψ0 ∗ xp ) − α �xp �2 2 p 1 � 0 �2 = w(α0 ) − α �xp �2 . 2 p = � The last step above is due to the fact that (xp , yp ) is a support vector, and yp · ψ0 ∗ xp = 1. Thus w(α0 ) − 2 � �2 � �2 (1−yp ·ψ� ∗xp ) w(α0 − αp0 · γ) = 12 αp0 �xp �2 and 12 ≤ 12 αp0 �xp �2 . Thus 2 �xp � αp0 ≥ ≥ |1 − yp · ψ � ∗ xp | �xp �2 1 . D2 The last step above is due to the fact that the support vector classifier associated with ψ � misclassifies (xp , yp ) according to assumption, and yp · ψ � ∗ xp ≤ 0, and the fact that �xp � ≤ D. �