[ML개론] (13) dual problem of SVM

SVM은 inequality constraint인 (wx+b)y>=1 아래 w*w를 최소화하는 convex problem과 마찬가지다. 

이는 이전글(https://alba-tross.tistory.com/95)에서 살펴볼 수 있듯이 primal fn을 Lagrangian dual fn으로 변형함으로서 더욱 쉽게 해결할 수 있다. 따라서 SVM의 primal fn을 duality를 이용하여 dual problem으로 해결하고자 한다. 

 

풀이방법은 다음과 같다.

첫째, optimal solution w,b를 구하기 위해 Lagrangian fn인 L(w,b,λ)를 w,b로 편미분한다. 그 결과는 위의 식과 같다.

둘쨰, 구한 w*, b* 값을 Lagrangian dual fn인 q(λ)에 대입한다. 그리고나서 q(λ)를 최대화해주는 λ를 찾아 다시 w*에 대입해주면 optimal w*값을 구할 수 있다. 

 

이 문제의 경우 제약함수가 affine funtion이기 때문에 regularity condition인 LCQ를 만족한다. 또한 KKT의 5가지 조건이 모두 충족된다. 따라서 q(λ)가 최대화되는 λ* 지점을 찾아 이를 다시 w*=w(λ)에 대입하면 SVM의 최적의 두 인자 w, b를 찾을 수 있다.