[Machine Learning] Support Vector Machine (SVM) (3)

이전 글까지는 Hard margin SVM의 optimization problem의 primal form을 유도하였다.

이번 글에서는 Hard margin SVM의 최종 problem인 dual problem 및 최적화 과정까지 유도해보도록 하겠다.

[Machine Learning] Support Vector Machine (SVM) (2)

 

Lagrange Multipler를 이용하여 Hard SVM을 푸는 과정

1. primal form minimization problem 풀기

 

Hard margin SVM의 primal form minimization problem은 다음과 같이 정의된다.

 

이 form은 $w, b$ 측면에서 convex하고 continuous하므로 미분 = 0이 되게 하는 parameter로 optimal한 parameter를 찾을 수 있다.

$w$로 primal form loss를 편미분해서 0이 되는 지점을 통해 $w^*$를 구하였다.

그런데 $b$로 편미분 했을 때는 어떠한 식이 얻어졌다. 이 식을 추후에 이용하니 잘 기억해두도록 하자.

 

SVM primal form loss function이 convex 함을 증명

다변수 함수에서는 함수의 Hessian Matrix가 Positive Semi-Definite (PSD) 하다면 convex하다.

 

Hessian Matrix는 다음과 같이 정의된다.

$X$: n x 1 열벡터

$f: R^n -> R$ 함수

왼쪽은 정의이고, 오른쪽은 풀어서 설명한 것이다.

 

Matrix H의 Positive Semi-Definite는 다음과 같이 정의된다.

임의의 $X$에 대해 $X^THX ≥ 0$이면 $H$는 PSD하다.

 

따라서 primal form은 convex하다.

 

2. Lagrange Dual Function 정의

지금까지 우리는 Lagrange Primal Function $L_P$를 가지고 최적의 파라미터 $w^*$, $b^*$를 구했다.

아직 $\alpha$는 미지수이므로 $\alpha$를 구해야 한다.

따라서 Lagrange Dual Function $L_D$를 정의한다.

 

$L_D$를 정의하기 위해 위에서 구한 $w^*$, $b^*$를 $L_P$에 대입한다.

 

3. Lagrange Dual function을 maximize하는 $\alpha$를 찾는다.

primal form을 풀어서 모델의 optimal한 parameter $w^*, b^*$는 구해놓았다.

optimal solution을 적용해서 dual function을 얻어냈으므로 dual form이 최소가 되게 하는 $\alpha$를 구하는게 목적이 아니라, dual form이 원래 풀려던 primal form과 최대한 비슷해지는게 목적이다. 따라서 duality gap을 최소화 하는 $\alpha$, 즉 dual form을 maximize하는 $\alpha$를 찾는다.

 

Lagrange Dual form problem은 다음과 같이 정의된다.

 

첫 번째 제약조건: $L_D(\alpha)$를 유도할 때 $\sum_{i=1}^n$ $\alpha_i$$y_i$를 이용했고, 제약조건 안에 $\alpha$가 존재하므로 그냥 optimal한 $\alpha$가 아닌 조건을 만족하는 $\alpha$를 구해야 한다.

두 번째 제약조건: 처음에 lagrange multiplier를 적용할 때 정의한 제약 조건이다. active한 constraint라면 $\alpha$가 양수이고, inactive한 constraint라면 $\alpha$가 0이다.

 

그렇다면 이 문제는 어떻게 풀 것인가?

바로 Quadratic Programming (QP) Solver를 이용해 푼다.

 

원래 QP 형태는 다음과 같다.

$\underset{X}{minimize}$ $\frac{1}{2}X^TQX + c^TX$

subject to $AX$ ≤ $b$

$EX$ = $d$

 

이 original form의 $A, b, C, d, E, Q$에 각각 다음을 대입한다.

그러면 SVM lagrange dual problem을 다음과 같이 정의할 수 있다.

그러면 QP Solver가 dual problem을 해결해 준다.

그 결과로 optimal한 $\alpha^*$ = <$\alpha_1$, $\alpha_2$, ... , $\alpha_n$> 을 얻었다.

 

4. Final Step

${w^*}^TX_+ + b$ = 1 & ${w^*}^TX_- + b$ = -1

두 식을 연립해서 $b$를 구할 수 있다.

$b^*$ = − $\frac{1}{2}$($w^TX_+ + w^TX_-$)

 

따라서 우리는 최적의 $w, b, \alpha$를 구했다.

 

5. Optimization

margin은 support vector들에 의해서만 정의된다. 따라서 margin을 결정하는 데 관여하지 않는 vector(data)들은 KKT condition의 complementary slackness condition에 의해 hyperplane을 찾는 과정에서 제외된다.

 

KKT condition의 complementary slackness condition에 따르면 다음 식이 성립한다.

 

Non-support vector: $\alpha_i$ = 0

Support vector: $\alpha_i$ > 0

 

결국 support vector가 아닌 데이터를 $y_i(w^Tx + b) - 1$에 대입하면 inactive하게 되어 무시해도 되는 constraint가 되고, 따라서 hyperplane을 찾을 때 고려하지 않아도 된다.

 

그러면 우리의 최종 솔루션은 다음과 같아진다.

SV는 Support Vector의 축약형이다.

 

6. Classification

새로운 data ($X_new, y_new$)에 대해 우리의 모델은 다음과 같이 예측한다.

 

 

---

 

이로 Hard Margin SVM에 대한 설명이 끝났다.

다음에는 Non-linearly separable한 데이터를 분류하기 위한 SVM들에 대한 내용으로 돌아오겠다.

시험 끝나구..