Choosing the working set in SVM

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

SVM and SMO

Instructor: Prof. Ganesh Ramakrishnan

November 2, 2015 1 / 28

Joachims’ SVM ^light

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Choosing the working set in SVM

Let

f(α) = 1

2α^⊤Qα−e^⊤α SVM^light chooses working setB by solving for:

∆α=min

d ∇^⊤f(α^k)d

whered is the descent direction and∆α=α^k+1−α^k s.t.

▶ |{d_i:d_i̸= 0}| ≤q

Intuitively, ifqnon-zerodi’s are possible, theywillbe picked up since such a set will reduce the objective further as compared to a smaller set

▶ y^⊤d= 0

(α^k)^⊤y= 0, and(α^k+1)^⊤y= 0 =⇒ (α^k+d)^⊤y= 0 Thus,y^⊤d= 0

▶ d_i ∈[−1,1]

▶ d_i ≥0, for (α^k)i= 0

▶ d_i ≤0, for (α^k)_i=C

November 2, 2015 3 / 28

Solving for d in SVM

The intuition is that:

The descent directionsd_i’s for the most violating (α^k)_i’s correspond to the(∇f(α^k))_i’s that are farthest from 0, taking care that we also wanty^⊤d= 0, ie. ∑

y_id_i = 0, for all i’s chosen as per above

(s.t. |{di :di̸= 0}| ≤q)

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Solving for d in SVM

1 Sorty_i(∇f(α^k))i in decreasing order

2 Symmetrically do:

From the top, sequentially setd_i =−y_i From the bottom, sequentially setd_i=y_i

▶ Until either

⋆ q

2 ‘d_i=−y_i’s have been selected from the top, and ^q₂

‘d_i=y_i’s have been selected from the bottom

⋆ we cannot findd_i=−y_i from the top andd_i=y_i from the bottom at the same time

▶ At any point,

if(αk)i = 0 andd_i =−1, set d_i= 0 and bypass it, and if(αk)i =C andd_i= 1, set d_i= 0 and bypass it

▶ The goal is to achieve a balancing between the two signs from the opposite ends, ie. ∑

y_id_i= 0

3 d_i’s not yet considered are assigned0

November 2, 2015 5 / 28

If ^q₂ ‘di =−yi’s from the top and ^q₂ ‘di =yi’s from the bottom could not be selected (or ifq is large enough), the algorithm will stop ati_t from the top and i_b from the bottom

One of the following will happen:

it is just before ib

There is one positioni between i_t and i_b with 0<(α^k)_i <C

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

When the algorithm stops, d is an optimal solution for

∆α=min

d ∇^⊤f(α^k)d s.t.

|{d_i:d_i̸= 0}| ≤q y^⊤d= 0

di∈[−1,1]

d_i≥0, for(α^k)i= 0 di≤0, for(α^k)i=C

When the algorithm stops at i_t, if the next index in the sorted list of yi(∇f(α^k))i is ¯it, there are three possible situations:

(α^k)¯it ∈(0,C)

(α^k)¯it = 0 and y¯it =−1 (α^k)¯it =C and y¯it = 1

If the last two do not hold, we can move down further by assigningd¯it = 0

November 2, 2015 7 / 28

Decomposition in Joachims’

SVM ^light

(continued)

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Choice of the working set size q

In the decomposition algorithm, a working set sizeq≤l must be chosen

There is a tradeoff between qand the number of iterations needed for the algorithm to converge

▶ The higher the working set sizeq, the lower will be the number of iterations needed

▶ However, with a largerq, individual iterations become extremely expensive

November 2, 2015 9 / 28

Correctness of the algorithm

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Verify that the algorithm actually minimizes the objective¹ When an iteration of the algorithm stops, d is an optimal solution for

∆α=min

d ∇^⊤f(α^k)d s.t.

▶ |{d_i:d_i̸= 0}| ≤q

▶ y^⊤d= 0

▶ d_i ∈[−1,1]

▶ d_i ≥0, for (α^k)i= 0

▶ d_i ≤0, for (α^k)i=C

1Full proof athttp://www.csie.ntu.edu.tw/~cjlin/papers/conv.pdf

Chih-Jen Lin.On the Convergence of the Decomposition Method for Support Vector Machines

November 2, 2015 11 / 28

When an iteration of the algorithm stops, the following KKT conditions are satisfied, showing that dis an optimal solution:

∇f(α^k) =−by+λ_i−ξ_i y^⊤d= 0

λ_i(d_i+ 1) = 0, if 0< α^k_i ≤C λ_id_i= 0, α^k_i = 0

ξi(1−di) = 0, if 0≤α^k_i <C ξidi = 0, if α^k_i =C

λi ≥0, ξi ≥0, ∀i= 1, . . . ,l

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Assume thatB is the working set at the kth iteration, and N= 1, . . . ,l\B

If we define s=α^k+1−α^k, thensN = 0 and

▶ f(α^k+1)−f(α^k)

= ¹₂s^⊤Qs+s^⊤Qα^k−e^⊤s

= ¹₂s^⊤_BQ_BBs_B+s^⊤_B(Qα^k)B−e^⊤_Bs_B

November 2, 2015 13 / 28

Thus, in thekth iteration, we solve the following problem with the variable s_B:

minsB

1

2s^⊤_BQ_BBs_B +s^⊤_B(Qα^k)_B −e^⊤_Bs_B s.t.

0≤(α_k+s)_i≤C, i∈B y^⊤_Bs_B = 0

This is written purely in terms of the basisB components, ignoring the function of s_N in the objective which does not depend on s_B

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Using the KKT conditions that the optimal solution s_B must satisfy, we show a sufficient decrease of f(α) over the iterations:

f(αk+1)≤f(α^k)− ^σ₂α^k+1−α^k2

▶ where, σ=min_I(min(eig(Q_II)))

At every step, the function decreases by an amount that does not become insignificant

November 2, 2015 15 / 28

Convergence of SMO

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

SVM Dual objective:

minα

1

2α^⊤Qα−e^⊤α s.t.

▶ 0≤αi ≤C,∀i

▶ y^⊤α= 0 where:

▶ Qis positive-semidefinite, and Q_ij =y_iy_jϕ^⊤(x_i)ϕ(x_j)

▶ e=





 1... 1





∈Rⁿ

November 2, 2015 17 / 28

We split the constraint 0≤α_i≤C,∀i into:

▶ −αi≤0, with the Lagrange multiplierθi

▶ αi ≤C, with the Lagrange multiplier Γi

and, consider y^⊤α= 0, with the Lagrange multiplier β Thus, we can write the Lagrangian as:

L(α, θ,Γ, β) = ¹₂α^⊤Qα−e^⊤α−θ^⊤α+ Γ^⊤(α−C) +βy^⊤α s.t. ∀i,

▶ θi ≥0

▶ Γi≥0

▶ θ_iα_i= 0

▶ Γi(αi−C) = 0 Taking ∇ L= 0, we get:

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

If α_i = 0, α_i−C̸= 0 and thus Γ_i = 0

▶ (Qα)_i−1−θi+βy_i= 0

=⇒ θi = (Qα)_i−1 +βy_i

▶ Asθi≥0,

(Qα)_i−1 +βy_i≥0 If α_i =C, θ_i = 0

▶ (Qα)_i−1 + Γ_i+βy_i= 0

=⇒ −Γi= (Qα)_i−1 +βy_i

▶ AsΓi≥0,

(Qα)_i−1 +βy_i≤0 If αi ∈(0,C), θi = 0 and Γi = 0

▶ Thus,

(Qα)_i−1 +βy_i= 0

November 2, 2015 19 / 28

Let us define the following sets of indices i I₀(α) ={i: 0< α_i<C}

I₁(α) ={i:y_i= +1, αi= 0} I₂(α) ={i:y_i=−1, αi=C} I₃(α) ={i:y_i= +1, αi=C} I₄(α) ={i:y_i=−1, αi= 0}

Let us now consider

1 I₀(α)∪I₁(α)∪I₂(α)

={i:y_i = +1, α_i <C} ∪ {i:y_i=−1, α_i >0}

▶ (

(Qα)_i−1)

y_i ≥ −β

2 I0(α)∪I3(α)∪I4(α)

={i₍:yi = +1, α₎ i >0} ∪ {i:yi =−1, αi <C}

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Thus, we have:

i∈Imin0∪I1∪I2

((Qα)−1)

yi ≥ max

i∈I0∪I3∪I4

((Qα)−1) yi

We get:

min (

y_i=+1,αmini>0−(

∇f(α))

i, min

yi=−1,αi<C

(∇f(α))

i

)

≥ max

(

yi=+1,αmaxi<C−(

∇f(α))

i, max

yi=−1,αi>0

(∇f(α))

i

)

Let the min be attained at index l, and max be attained at index j.

If for (l,j), the inequality is violated, the KKT conditions are violated.

November 2, 2015 21 / 28

We need to prove that for all such choices of l and jacross iterations,

∀k,

f(α^k+1)≤f(α^k)−σ 2

α^k+1−α^k2 s.t. σ >0, and α^k+1 ̸=α^k

Once we findl and j, we will find closed form solutions for α^k+1_l =g(α_l^k, α^k_j, α^k_N)

α^k+1_j = ¯g(α_l^k, α^k_j, α^k_N)

(which have been discussed before)

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Whatever be the values ofα^k+1_l and α^k+1_j , we will have:

▶ y_lα^k+1_l +y_jα^k+1_j =−y^⊤_Nα^k_N (constant)

Thus, we can say that ifα_l changes linearly, then α_j also changes linearly

▶ We can replace α^k+1_l andα_j^k+1 as:

αl(t)←α^k+1_l αj(t)←α^k+1_j

αl and αj vary linearly with t

▶ αl(t)≡α^k_l +ty=α^k_l + _y^t

l

▶ αj(t)≡α^k_j +ty=α^k_j +_y^t_j

November 2, 2015 23 / 28

Letf(α) =ψ(t)

▶ ψis a function of α_N,α_l(t), andα_j(t)

We need to analyze w.r.t. ¯t that minimizes ψ(t) subject to constraints

▶ ∑

αiy_i= 0

▶ αi ∈[0,C]

That would give

▶ α^k =



 α_N^k α^k_j α^k_l



, andα^k+1 =



 α^k_N α^k_j +_y^¯t

j

α^k_l +_y^¯t

l





▶ α^k+1−α^k =



 0

¯t yj

¯t yl





. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

Now, ψ(t) is a quadratic function on t Thus,ψ(t) = ψ(0) +ψ^′(0) +ψ^′′(0)^t₂² ψ^′(t) = ∑_m

i=1

(∇f(

α(t)))

i dαi(t)

dt

=yl

(∇f(

α(t)))

l−yj

(∇f(

α(t)))

j

=yl

(∑_m

i=1Qliαi(t)−1)

−yj

(∑_m

i=1Qjiαi(t)−1)

▶ ψ^′(0) =y_l(

∇f(α^k) )

l−y_j(

∇f(α^k) )

j

ψ^′′(t) =Q_ll+Q_jj−2y_ly_jQ_lj

=ϕ^⊤(xl)ϕ(xl) +ϕ^⊤(xj)ϕ(xj)−2ϕ^⊤(xl)ϕ(xj)

▶ ψ^′′(0) =ϕ(x_l)−ϕ(x_j)²

November 2, 2015 25 / 28

¯t minimizes ψ(t) s.t. ∑

α_iy_i = 0 and α_i ∈[0,C], ∀i

▶ |¯t|= √¹ 2

α^k+1−α^k

Supposet^∗ minimizes ψ(t)without constraints

▶ Solving forψ^′(t^∗) = 0, we get: t^∗ =−_ψ^ψ′′^′(0)(0)

ψ(¯t)≥ψ(t^∗)

We can say that¯t=γt^∗, where γ ∈[0,1]

(you could have gone tillt^∗ but had to halt at¯t due to constraints)

. . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . .

. .

. . . . .

ψ(¯t) =ψ(γt^∗) =ψ(−γ_ψ^ψ_′′^′(0)₍₀₎)

=ψ(0) +ψ^′(0)

(−γ_ψ^ψ_′′^′(0)₍₀₎ )

+ ^ψ′′₂⁽⁰⁾

(−γ_ψ^ψ_′′^′(0)₍₀₎ )2

=ψ(0)−γ(^ψ′(0))²

ψ^′′(0) + ^γ₂²(^ψ′(0))²

ψ^′′(0)

Since γ ∈[0,1], γ² ≤γ, and

γ²

2 −γ ≤ −^γ₂²

Thus,ψ(¯t)≤ψ(0)−^γ₂²(^ψ′(0))²

ψ^′′(0)

=⇒ ψ(¯t)−ψ(0) ≤ −^γ₂²(^ψ′(0))²

ψ^′′(0)

=⇒ ψ(¯t)−ψ(0) ≤ −^ψ′′₄⁽⁰⁾α^k+1−α^k2 This becomes:

f(α^k+1)−f(α^k)≤ −^σ₂α^k+1−α^k2

▶ where, σ= ^ψ′′₂⁽⁰⁾ = ¹₂ϕ(x_l)−ϕ(x_j)²

▶ σ >0except when feature vector ϕ(x_l) is the same asϕ(x_j)

November 2, 2015 27 / 28

We assume Qto be positive-semidefinite so that ψ^′′(0)≥0 But in the analysis of general decomposition, we assumed QII to be positive-semidefinite for any submatrix of Q, which is a stronger assumption