SVM

Support Vector Machine

Andrew ng lecture note 를 공부하며 정리한 자료입니다.

SVM을 이해하기 위해서는 Margin(마진)과 데이터를 분리해주는 경계선과 데이터 사이의 거리 Gap이 커야 한다는 것에 초점을 맞춰야 한다.

1. Margin

여기에서는 ‘confidence’라는 개념이 등장한다.

confidence는 예측이 얼마나 맞는지에 대한 확신을 나타낸다.

그림을 보면 경계선(Seperating hyperplane) 근처에 있으면 Confidence가 낮고 즉 예측의 정확도가 낮아지고, 경계선에서 멀어질수록 Confidence가 높아지며 예측의 정확도가 높아진다.

2. Notation

여기에서 $x$ feature와 $y$ label를 사용한다.

label $y$는 SVM에서 $y \in \{-1, 1\}$ 로 지정해 준다.

사용할 파라미터는 $w$, $b$로 표기할것이다.

classifier는 다음과 같다.

$$h_{w,b}(x)=g(w^Tx + b)$$

만약 $w^Tx + b \geq 0$ 이면 $g(w^Tx + b)=1$ 이 되고, $w^Tx + b \leq 0$ 이면 $g(w^Tx + b)=-1$ 이 된다.

3. Functional / geomeric margins

3.1 Functional margins

training dataset $(x^{(i)},y^{(i)})$ 가 주어지면 functional margin $\left(\widehat\gamma^{(i)} \right)$은 다음과 같다.

$$\widehat\gamma^{(i)}=y^{(i)} (w^Tx + b)$$

식에서 보면 functional margin이 커지기 위해서는 $y^{(i)}=1$ 이면 $w^Tx + b$ 가 양의 부호로 커져야 하고, $y^{(i)}=-1$ 이면 $w^Tx + b$ 가 음의 부호로 커져야 한다. 또한 $y^{(i)} (w^Tx + b) > 0$ 이면 예측이 맞았다는 뜻도 된다.

그러므로 functional margin은 confidence와 예측의 정확성을 나타낸다.

단 여기서 functional margin $\left(\widehat\gamma \right)$은 데이터 마다의 functional margins중에서 가장 작은 값이 functional margin이 된다.

$$\widehat\gamma=min_{i=1,\ldots,m} \widehat\gamma^{(i)}$$ 3.2 geomeric margins

여기에서 $w$는 경계선(seperating hyperplane)과 직교한다

A는 데이터중 하나인 $x^{(i)}$이고 라벨 $y=1$을 나타낸다

선 AB는 경계선과의 거리 $\gamma ^{(i)}$로 나타낸다

점 B는 다음과 같이 나타낼수 있다

$$x^{(i)}-\gamma^{(i)} \cdot \frac{w}{\lVert w \rVert}$$

$\frac{w}{\lVert w \rVert}$ 는 unit vector를 나타낸다.

경계선 $w^Tx + b=0$을 나타내므로, 경계선 위의 점 B를 이용하면 $w^T \left( x^{(i)}-\gamma^{(i)} \cdot \frac{w}{\lVert w \rVert}\right)+b=0$인 식을 유도할수 있다

$\gamma^{(i)}$에 대한 식으로 바꿔주면 다음과 같다

$$\gamma^{(i)}=\left(\frac{w}{\lVert w \rVert}\right)^T x^{(i)}+\frac{b}{\lVert w \rVert}$$

geometric margins$\left(\gamma^{(i)}\right)$는 다음과 같다

$$\gamma^{(i)}=y^{(i)}\left( \left(\frac{w}{\lVert w \rVert}\right)^T x^{(i)}+\frac{b}{\lVert w \rVert} \right)$$

만약 $\lVert w \rVert =1$ 이면 결국 functional margin과 같다진다는 것을 알수있다

geometric margin도 데이터 마다의 geometric margin중에서 가장 작은 값이 geometric margin이 된다.

$$\widehat\gamma=min_{i=1,\ldots,m} \widehat\gamma^{(i)}$$ 4. The optimal margin classifier

마진을 최대화 하는 경계선을 찾아내는 것이 최적화한다는 것이다.

$$\begin{matrix} max_{\gamma ,w,b} && \gamma \end{matrix}$$ $$\begin{matrix} s.t. && y^{(i)} (w^Tx + b) \geq \gamma , i=1,\ldots,m \\ && \lVert w \rVert=1 \end{matrix}$$

margin을 최대화 하는 최적화 문제이고, 모든 데이터 마다 최소한의 마진보다는 항상 크고, $\lVert w \rVert=1$은 결국 functional / geometric margin이 같다는 것을 나타낸다

위의 식은 풀기가 까다로운 식이므로 식을 다음과 같이 변형할수 있다

$$\begin{matrix} min_{w,b} && \frac{1}{2}\lVert w \rVert^2 \end{matrix}$$ $$\begin{matrix} s.t. && y^{(i)} (w^Tx + b) \geq 1 , i=1,\ldots,m \end{matrix}$$

위의 식을 직관적으로 이해해 보면, 예를 들어 만약 임의의 점을 $x$, 경계선 위의 점을 $x_p$ 라고 한다면 $x_p$에서 $w$방향으로 $\gamma$만큼 이동한것이 $x$이다.

$$x = x_p + r \frac{w}{\lVert w \rVert}$$ $$w \cdot x + b = w \left ( x_p + r \frac{w}{\lVert w \rVert} \right) + b = w \cdot x_p + b + r \frac{w \cdot w}{\lVert w \rVert}$$

• $w \cdot x_p + b = 0$ 이므로 ($x_p :$ 경계선 위의점)

$$w \cdot x + b = r \lVert w \rVert$$ $$r = \frac{w \cdot x + b}{\lVert w \rVert} = \frac{c}{\lVert w \rVert}$$

$c:$ constant

결국 $\gamma$를 최대화 한다는것은 $w$를 최소화 하는것과 같다

5. Lagrange duality

최적화 문제를 풀기 위해서는 Lagrange duality에 대해서 이해를 하고 있어야 한다. 강의 노트에서 나온 정도로만 간단히 정리해보겠다

$$\begin{matrix} min_w && f(w) \end{matrix}$$ $$\begin{matrix} s.t. && g_i(w) \leq 0 \\ && h_i(w)=0 \end{matrix}$$

부등식 제약조건이 있는 것은 Primal optimization 문제라고 부른다

일반화된 라그랑지안식(generalized Lagrangian)은 다음과 같다

$$L(w,\alpha , \beta)=f(w)+\sum_{i=1}^k\alpha_i g_i(w) + \sum_{i=1}^l\beta_i h_i(w)$$

여기에서 $\alpha ,\beta$는 Lagrange multipliers 이다

5.1 primal optimal problem $$\theta_P(w)=max_{\alpha ,\beta : \alpha >0} L(w,\alpha , \beta)$$ $$\theta_P(w)= \begin{cases} f(x) & \text{if }g_i(w) \leq 0 \text{, } h_i(w)=0 \\ \infty & \text{if } g_i(w) > 0 \text{ or }h_i(w)\neq0 \end{cases}$$

제약 조건을 모두 만족하면 $\theta_P(w)=f(x)$가 되고 제약 조건하나라도 만족을못하면 무한대로 발산한다

결국 위식에서 알수 있는 것은 제약식을 모두 만족 시키려면 $\theta_P(w)$를 가장 최소화 해야 된다는것을 알수 있다.

$$p^*=min_w \theta_P(w)=min_wmax_{\alpha ,\beta : \alpha >0} L(w,\alpha , \beta)$$ 5.2 dual optimal problem

dual problem은 primal problem과 반대로 $w$를 최소화하는 라그랑지안을 구하는 것이다

$$\theta_D(\alpha, \beta) =min_w L(w,\alpha , \beta)$$ $$d^{*}=max_{\alpha ,\beta : \alpha >0} \theta_D(\alpha , \beta)=max_{\alpha ,\beta : \alpha >0} min_w L(w,\alpha , \beta)$$ 5.3 primal / dual optimal problem

primal optimal 과 dual optimal 식은 min max를 자리바꾼것 말고는 다른게 없다. max min 함수가 min max보다 항상 작거나 같다. 하지만 특정한 조건하에서는 $d$ = $p$ 가 성립한다

$f$와 $g_i$가 convex, $h_i$가 affine하고 모든 $i$에 대해서 $g_i(w) < 0$ 라고 가정하면 $w, \alpha ,\beta$는 반드시 존재하게 된다. $w$는 Primal problem의 solution이 되고, $\alpha, \beta$는 Dual problem의 solution이 된다

5.4 KKT conditions $${\partial\over\partial w_i}L(w^*,\alpha^* , \beta^*)=0, \text{ } i=1,\ldots,n$$ $${\partial\over\partial \beta_i}L(w^*,\alpha^* , \beta^*)=0, \text{ } i=1,\ldots,l$$ $$\alpha_i^* g_i(w^*)=0, \text{ } i=1,\ldots,k$$ $$g_i(w^*)\leq 0, \text{ } i=1,\ldots,k$$ $$\alpha_i^* \geq0, \text{ } i=1,\ldots,k$$

$w,\alpha , \beta$가 KKT 조건을 만족한다면 dual problem과 primal Problem이 같아지므로 두개 모두의 해가 된다

5. Optimal margin classifiers

다시 Margin classifiers문제로 돌아와 보자

$$\begin{matrix} min_{w,b} && \frac{1}{2}\lVert w \rVert^2 \end{matrix}$$ $$\begin{matrix} s.t. && y^{(i)} (w^Tx^{(i)} + b) \geq 1 , i=1,\ldots,m \end{matrix}$$

제약식을 다음과 같이 고쳐 써줄수있다

$$g_i(w)=-y^{(i)} (w^Tx^{(i)} + b)+1 \leq 0$$

Functional margin은 1이되게 된다

다음 그림에서 margin이 가장 작은 점은 3개가 있다(두개의 negative 한개의 positive)

3개가 support vector가 된다. 또한 support vector에서는 $\alpha$값이 절대 0이 되지 않는다. 그렇다는것은 KKT조건에 의해 $g_i(w)$가 0이 되어야 한다는것이다

Lagranian 식은 다음과 같다.

$$L(w^*,\alpha^* , \beta^*)=\frac{1}{2}\lVert w \rVert^2-\sum_{i=1}^m \alpha_i \left[y^{(i)} (w^Tx^{(i)} + b)-1\right]$$

부등식 제약조건만 있으므로 $\alpha_i$만 존재한다

dual problem을 푸기 위해서 $minimize_{w,b}L(w,\alpha , \beta)$ $\alpha$는 고정한 상태에서 $w$, $b$에 대해서 미분을 해야한다

w에 대해 미분한다

$$\nabla_w L(w,\alpha , \beta)= w -\sum_{i=1}^m\alpha_i y^{(i)}x^{(i)}=0$$ $$w=\sum_{i=1}^m\alpha_i y^{(i)}x^{(i)}$$

b에 대해 미분한다

$${\partial\over\partial b}L(w,\alpha , \beta)=\sum_{i=1}^m\alpha_i y^{(i)}=0$$

미분해서 구한 w를 라그랑지안 식에 대입해주고 정리해주면 다음과 같은 식을 얻을수 있다

$$L(w,\alpha , \beta)=\sum_{i=1}^m\alpha_i - \frac{1}{2} \sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j \left(x^{(i)}\right)^T x^{(j)}-b\sum_{i=1}^m\alpha_i y^{(i)}$$

$\sum_{i=1}^m\alpha_i y^{(i)}=0$이므로 최종식은 다음과 같다

$$L(w,\alpha , \beta)=\sum_{i=1}^m\alpha_i - \frac{1}{2} \sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j \left(x^{(i)}\right)^T x^{(j)}$$

현재까지 w,b에 대해서 최소화 하는 문제를 풀었고 최종 dual problem을 풀기위해서는 제약식 $\alpha >0$ 을 포함한 $max_\alpha W(\alpha)$를 구해야 한다. dual problem 식은다음과 같다

$$max_{\alpha} W(\alpha)=\sum_{i=1}^m\alpha_i- \frac{1}{2} \sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j <x^{(i)}, x^{(j)}>$$

다음의 식을 최대화하는 $\alpha$를찾으면 $w=\sum_{i=1}^m\alpha_i y^{(i)}x^{(i)}$를 이용해 optimal $w$를 찾는다

$b$는 구해진 $w$를가지고 다음식에 대입하여 풀수 있다.

$$b^{*}=-\frac{max_{i:y^{(i)}=-1}w^{*T}x^{(i)}+min_{i:y^{(i)}=1}w^{*T}x^{(i)}}{2}$$

추가적으로 $w=\sum_{i=1}^m \alpha_i y^{(i)} x^{(i)}$를 이용하여 다음과 같은 식을 도출해낼수 있다. 이것은 나중에 kernel trick에서 사용하게 될것이다.

$$w^Tx +b =\left(\sum_{i=1}^m \alpha_i y^{(i)} x^{(i)}\right)x + b=\sum_{i=1}^m \alpha_i y^{(i)}<x^{(i)},x>+b$$

classification할때 예측하려는 input data ($x$)와 트레이닝 학습 데이터 ($x^{(i)}$)의 내적 합 으로 예측할수있다. 위 식은 kernel trick에서 사용된다.