선형 SVM까지 끝장보기

이전 시간에 훈련샘플의 개수만큼 제약조건 식이 세워지는 대참사가 일어났다.

 

$$\textrm{minimize  } J(w) = \frac{1}{2}||w||_2^2$$
$$\textrm{subject to     } y_i(w^Tx_i + b)-1\geq 0, i=1,2, ... , n$$

 

 

여기서 라그랑즈를 사용한다!

우리는 KKT Condition에서

$$\textrm{minimize } f(x) \textrm{      subject to } g(x)\leq 0$$

 

라그랑즈로 우리는 다음처럼 표현했다.

$$L(x, \lambda) = f(x) + \lambda g(x)$$

 

 

제약조건마다 $\lambda$ 대신 $\alpha_i$를 붙여서 표현하면 다음처럼 된다.

$$L(w, b, \alpha) = \frac{||w||^2}{2}- \sum_\limits{i=1}^n \alpha_i(y_i(w^Tx_i + b)-1) $$

 

equality, inequality 공통적으로 $\bigtriangledown_x L(x, \lambda) = 0$로 풀어내었다.

 

그러므로 우리가 구하고자 하는 파라미터는 w와 b이니 이에 대해 편미분하여 0이 되는 지점을 찾는다.

 

1) w로 편미분하기

일련의 과정을 거쳐 ① - ② = 0을 정리해서 써보면

$$w = \sum_\limits{i=1}^n\alpha_iy_ix_i$$

$\alpha_i$를 알면 w를 구할 수 있고 w는 support vector의 선형 결합임을 알 수 있다.

 

 

2) b로 편미분하기

$$\sum_\limits{i=1}^n\alpha_iy_i=0$$

 

그러므로 Linear SVM 문제에 대해서는 최종적으로는 다음을 통해 풀면 된다.

식을 살펴보면 L을 최대화 시키는 데에는 오직 $x$끼리의 내적만이 영향을 끼친다.

$$\textrm{maximize  } L(\alpha) = \sum_i\alpha_i - \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_j y_i y_j\vec{x}_i\cdot\vec{x}_j$$
$$\textrm{subject to     }\sum_\limits{i=1}^n\alpha_iy_i=0$$
$$\alpha_i\geq 0, i= 1, 2, 3, ... n$$

 

그러나 linear에 대해서만 가능하니 비선형은 커버할 수 없다는 점, $O(n^2)$로 여전히 복잡도가 크다는 점이 남아있다.