지도 학습(6+) : 서포트 벡터 머신 심화

 

이 포스팅에서는 Support Vector Machine에서 쓰이는 수학 개념 위주로 다룬다. 서포트 머신 벡터에 대한 기본 개념은 다음 포스팅을 참고하기 바람.

https://one-plus-one-is-two.tistory.com/17

지도 학습(6) : 서포트 벡터 머신

 

이번 포스팅은 다음 교재의 내용을 참고하여 작성하였다.

https://see.stanford.edu/materials/aimlcs229/cs229-notes3.pdf

 

포스팅 내용이 상당히 어려우므로 svm의 수학적 원리까지 안 궁금한 사람은 뒤로가기를 눌러도 된다. (사실 나도 완벽히 이해하진 못했다.)

 

① Lagrange Duality

라그랑주 함수(Lagragian)

다음과 같은 최적화 문제가 있다고 하자.

$h_i(w)=0$ ($i=1,\cdots,l$)이라는 제약 조건이 있을 때 $f(w)$의 최솟값을 구하라는 문제다.  s.t.는 subject to의 약어로, '~의 조건 하에'라는 뜻으로 이해하면 될 것 같다.

위 제약 조건이 있는 최적화 문제를 다음과 같이 하나의 라그랑주 함수(Lagrangian)로 바꿔쓸 수 있다.

이때, 제약조건 $h_i(w)$에 곱해진 $\beta_i$를 라그랑주 승수(Lagrange Multiplier)라고 한다. 이 라그랑주 함수 $\mathcal L$에 대해 다음 두 방정식을 연립해서 푼다.

$\frac{\partial \mathcal L}{\partial \beta_i} = 0$이 되어야 하는 이유는 제약 조건 $h_i(w)=0$을 만족시키기 위해서이다. $\mathcal L$을 $\beta_i$에 대해 편미분하면 $h_i(w)$가 됨을 주목하자.

이렇게 제약조건을 만족시킨 상태에서 $w$에 의한 $\mathcal L$의 최솟값을 찾아야 한다. 고등학교에서 미분가능한 함수 $f(x)$가 $x=\alpha$에서 극소 또는 극대, 즉  $f'(\alpha)=0$이면 $f(\alpha)$는 최솟값 또는 최댓값의 후보가 된다는 사실을 알고 있을 것이다. 여기서도 같은 논리로 $\frac{\partial \mathcal L}{\partial w} = 0$이 되도록 하는 $w$와 $\beta$에 대해 $\mathcal L(w, \beta)$가 $\mathcal L$의 최솟값 후보가 된다.

 

일반화된 라그랑주 함수(Generalized Lagrangian)

다음과 같은 최적화 문제를 보자.

이번에는 부등식 제약 조건이 포함돼 있다. 부등식 제약 조건이 포함돼 있어도 다음과 같이 하나의 Lagrangian으로 쓸 수 있다.

단, KKT 조건에 의해 $\alpha_i ≥ 0$이어야 한다. KKT 조건에 대해서는 나중에 알아보기로 하자.

라그랑주 승수 $\alpha$, $\beta$와 라그랑주 함수 $\mathcal L(w, \alpha, \beta)$에 대해 $\theta_{\mathcal P}$를 다음과 같이 정의하자(이때, $\mathcal P$는 Primal(원래의, 원시의)의 P이다).

이 primal은 $g_i(w)$와 $h_i(w)$가 제약 조건을 잘 지키면 $f(w)$가 되지만, 제약 조건을 위반하면 무한대로 발산해버린다.

만약에 $g_i(w)$가 $g_i(w)≤0$이라는 제약 조건을 무시하고 양수가 된다면, $\alpha_i$를 매우 크게 조정함으로써 Lagrangian $\mathcal L$을 한없이 크게 만들어버릴 수 있다. $h_i(w)$도 마찬가지로 $h_i(w)=0$라는 제약 조건을 무시하고 0이 아닌 값을 가지면 $\mathcal L$을 무한대로 발산시킬 수 있는 $\beta_i$의 값이 얼마든지 존재한다. 하지만 $g_i(w)$와 $h_i(w)$가 제약 조건을 잘 지킨다면 $\alpha_i g_i(w)$의 최댓값은 모두 0이고 $\beta_i h_i(w)$의 최댓값도 모두 0이므로 $\mathcal L$의 최댓값은 $f(w)$가 된다. 따라서 $\theta_{\mathcal P}$를 case에 따라 분류하면 다음과 같다. 

따라서 주어진 최적화 문제는 이 $\theta_{\mathcal P}$를 $w$에 대해 최소화시키는 문제와 같다.

$$p^*=\min_{w} \theta_{\mathcal P}(w) = \min_{w} \max_{\alpha, \beta : \alpha_i ≥ 0} \mathcal L (w, \alpha, \beta)$$

위 수식의 $p^*$이 원시 문제(Primal Problem)의 해가 된다.

 

이번엔 이 문제를 다른 관점에서 보자. 위 수식에서 min과 max의 순서를 바꿀 것이다. 먼저 $\theta_{\mathcal D}$를 다음과 같이 정의하자(이때, $\mathcal D$는 Dual(쌍대의)의 D이다.)

그런 다음 라그랑주 승수들에 대해 $\theta_\mathcal D$를 최대화 시킨다.

$$d^*=\max_{ \alpha, \beta : \alpha_i ≥ 0 } \theta_{\mathcal P}(w) = \max_{\alpha, \beta : \alpha_i ≥ 0}  \min_{w} \mathcal L (w, \alpha, \beta)$$

위 수식의 $d^*$이 쌍대 문제(Dual Problem)의 해이다.

 

지금까지 $p^*$와 $d^*$를 정의했는데, 일반적으로 이 둘 사이에는 다음과 같은 등식이 성립한다고 한다.

$$d^* ≤ p^*$$

하지만 어떤 조건이 성립한다면 둘의 값이 반드시 같아진다.

$$d^* = p^*$$

 

그 '어떤 조건'을 KKT(Karush-Kuhn-Tucker) 조건이라고 한다. KKT 조건의 내용은 다음과 같다.

 

② SVM에서의 Lagrange Duality 활용

하드 마진 방식의 SVM에서 풀어야 하는 최적화 문제는 다음과 같다.

여기서 부등호 제약 조건은 $g(x)≤0$ 꼴이 되어야 하므로 제약 조건을 다음과 같이 변형한다.

이때, $y^{(i)}$와 $b$는 스칼라이고 $w$와 $x^{(i)}$는 벡터이다. 이를 기반으로 Lagrangian을 작성하면 다음과 같다.

물론 이 문제의 해는 다음과 같이 정의되는 $p^*$이다.

$$p^* = \min_{w,b} \max_{\alpha : \alpha_i ≥ 0} \mathcal L(w, b, \alpha)$$

하지만 우리는 $p^*$ 대신 쌍대 문제의 해 $d^*$를 구할 것이다.

$$d^* = \max_{\alpha : \alpha_i ≥ 0} \min_{w,b}  \mathcal L(w, b, \alpha)$$

그런데 앞서 $d^* = p^*$를 만족시키려면 KKT 조건을 만족시켜야 한다고 했다.

 

우선 KKT 조건 중 $\nabla_w \mathcal L(w, b, \alpha)=0$ 조건을 만족시키도록 하는 $w$를 구해보자. $ \nabla_w \mathcal L(w, b, \alpha)$는 $\mathcal L$의 $w$에 대한 편도함수를 의미한다. 여기서는 $w$가 벡터이므로 표현을 바꿨다.

$$\mathcal L(w, b, \alpha) = \frac{1}{2} \| w \|^{2} - \sum_{i=1}^{m} \alpha_i \left[y^{(i)}(w^{\it T}x^{(i)}+b)-1 \right]$$

을 전개하면

$$\mathcal L(w, b, \alpha) = \frac{1}{2} \| w \|^{2} - \sum_{i=1}^{m} (\alpha_i y^{(i)}w^{\it T}x^{(i)}+ \alpha_i y^{(i)} b- \alpha_i )$$

인데, 이를 $w$에 대해 편미분하면 $\nabla_w \ \ \frac{1}{2}\| w \|^{2} = \nabla_w \frac{w^{\it T}w}{2}  = w$이고, 시그마 식에서 $\nabla_w \ \ \alpha_i y^{(i)}w^{\it T}x^{(i)}  = \alpha_i y^{(i)}x^{(i)} $이다. 나머지 항은 $w$가 없기 때문에 $w$에 대해 편미분하면 모두 0이 된다. 따라서 최종 편미분 결과는 다음과 같다.

따라서 $$w=\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}$$를 얻는다. 

 

다음으로 KKT 조건 중 $\frac{\partial \mathcal L}{\partial b} =0$을 만족시키도록 만들어보자.

$$\frac{\partial \mathcal L}{\partial b} = -\sum_{i=1}^{m} \alpha_i y^{(i)} = 0$$

따라서 다음을 얻는다.

$$\sum_{i=1}^{m} \alpha_i y^{(i)} = 0$$

 

그래서 구한 것들을 다음과 같이 $\mathcal L$에 대입해준다.

이를 위와 같이 대입해준다. 근데 대입해주는 것 마저도 쉽지가 않다... (하여튼 인생에 쉬운게 없어) 그래도 하나하나 해보자. 먼저 $\frac{1}{2} \| w \|^{2}$을 정리하는 과정부터 보이겠다.

\begin{aligned}
\frac{1}{2}\|w\|^{2} 
&= \frac{1}{2}w^{\it T}w \\[8pt]
&= \frac{1}{2}\left[\sum_{i=1}^{m}\alpha_i y^{(i)}x^{(i)}\right]^{\it T}  \left[\sum_{j=1}^{m}\alpha_j y^{(j)}x^{(j)}\right] \\[8pt]
&= \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_j y^{(i)}y^{(j)} \{x^{(i)}\}^{\it T} x^{(j)} \\[8pt]
&= \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_j y^{(i)}y^{(j)}\langle x^{(i)}, x^{(j)}\rangle
\end{aligned}

이때, $ \langle x^{(i)}, x^{(j)}\rangle $은 $x^{(i)}$와 $x^{(j)}$의 내적을 의미한다. 이는 $x^{(i)} \cdot x^{(j)}$ 또는 $\{x^{(i)}\}^{\it T} x^{(j)}$와 같은 의미이다.

 

그 다음으로 $\alpha_i y^{(i)} w^{\it T} x^{(i)}$를 정리해보자.

\begin{aligned}
\alpha_i y^{(i)} w^{\it T} x^{(i)}
&= \alpha_i y^{(i)} \left[ \sum_{j=1}^{m} \alpha_j y^{(j)} \{x^{(j)}\}^{\it T} \right] x^{(i)} \\[8pt]
&= \alpha_i y^{(i)} \sum_{j=1}^{m} \alpha_j y^{(j)} \{x^{(j)}\}^{\it T} x^{(i)} \\[8pt]
&= \sum_{j=1}^{m} \alpha_i \alpha_j y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle
\end{aligned}

 

따라서

\begin{aligned}
\mathcal L(w, b, \alpha) 
&=  \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_j y^{(i)}y^{(j)}\langle x^{(i)}, x^{(j)}\rangle -  \sum_{i=1}^{m} \left( \sum_{j=1}^{m}\alpha_i \alpha_j y^{(i)}y^{(j)}\langle x^{(i)}, x^{(j)}\rangle - \alpha_i \right) \\[8pt]
&= \sum_{i=1}^{m} \alpha_i -\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_j y^{(i)}y^{(j)}\langle x^{(i)}, x^{(j)}\rangle 
\end{aligned}

 

따라서 다음과 같은 Dual Problem을 얻을 수 있다.

즉, 원래 세 가지 파라미터 $w$, $b$, $\alpha$가 존재했던 목적 함수 $\mathcal L(w, b, \alpha)$는 파라미터가 하나인 $W(\alpha)$로 변환됐다. 그리고 이 목적 함수를 $\alpha$로 최대화시키는 것으로 문제가 바뀌었다. 이 문제 같은 경우에는 사람이 직접 풀기 어려우므로 컴퓨터를 이용하면 빠르게 계산할 수 있다. CVX, Quadprog, LIBSVM과 같은 최적화 소프트웨어를 사용하거나 Sequential Minimal Optimization(SMO) 알고리즘을 이용하여 계산할 수 있다고 한다.

 

주어진 최적화 문제의 해가 $w=w^{*}$, $b=b^{*}$, $\alpha = \alpha^{*}$라고 하자. $w^{*}$는 앞에서 $ w^{*}=\sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}$라고 언급한 바 있고, $\alpha^{*}$는 사람이 손으로 구하기엔 너무 복잡하므로 소프트웨어를 이용한다고 했다. 그런데 $b^{*}$를 아직 구하지 않았다. 이제 슬슬 내용 쓰기가 너무 귀찮아져서 그냥 ChatGPT에게 받은 답변만 그대로 캡쳐해왔다.

잘 알아들으셨기를 바람 솔직히 내가 직접 쓴 것도 이해하는 사람 거의 없을 듯 한데

 

③ Kernel SVM

이미지 출처 : https://varshasaini.in/questions/what-is-kernel-trick-and-how-it-is-useful/

 

내가 지난 포스팅에서 '커널 svm은 비선형으로 분포된 데이터에 대해 차원을 늘려서 분리하는 방식이고~ 이러이러한 커널들이 있고~ 이 커널은 이런 특징이 있고 이런 장단점이 있고...' 같이 뭉뚱그려서 얘기했었다. 사실 윗 내용을 모르면 kernel svm도 수식을 이용해서 설명할 수 없다. 근데 이제 내용을 다 알려줬으니(이해한 사람이 거의 없을듯 해도) kernel svm을 수식으로 이해해보도록 하자.

 

svm의 초평면은 다음과 같다.

$$f(x)=wx+b$$

그런데 최적화 되었을 때 $w= \sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}$가 된다고 세 번째 말하는 것 같고, $b$는 최적화 결과를 ChatGPT 캡쳐본으로 가져왔지만 저거 쓰기 굉장히 귀찮으니 그냥 $b$라고 쓰자. 따라서 최적화된 파라미터를 사용한 초평면은 다음과 같다.

\begin{aligned}
f(x)
&= \sum_{i=1}^m \alpha_i y^{(i)}x^{(i)} \cdot x+b \\[8pt]
&= \sum_{i=1}^m \alpha_i y^{(i)} \langle x^{(i)}, x \rangle + b
\end{aligned}

커널이 적용된 부분은 두 벡터가 내적 연산되는 부분 $  \langle x^{(i)}, x \rangle $이다. 여기서는 선형 커널(linear kernel)이 적용된 것이다. 선형 커널을 수식으로 쓰면 다음과 같다.

$$k(x^{(i)},\ x)= \langle x^{(i)}, \ x \rangle$$

 

Kernel SVM의 일반화

커널 $k(x^{(i)}, \ x)$가 적용된 결정함수 $f(x)$는 다음과 같이 나타낼 수 있다.

$$f(x) = \sum_{i=1}^m \alpha_i y^{(i)} k(x^{(i)},\ x)+b $$

커널이 선형 커널이면 $k(x^{(i)},\ x)= \langle x^{(i)}, \ x \rangle$임도 앞에서 언급했었다.

 

그러면 이제 다항 커널, RBF 커널, 시그모이드 커널은 어떤 수식을 취하는지 간단히 언급하고 마치려고 한다.

• 다항 커널(Polynomial Kernel) : $ k(x^{(i)},\ x) = (\gamma \langle x^{(i)}, \ x \rangle + c)^{d} $
• 가우시안 RBF 커널(Gaussian Radial Basis Function Kernel) :  $ k(x^{(i)},\ x) = \exp ( - \gamma \| (x^{(i)}, x)\|^{2}) $
• 시그모이드 커널(Sigmoid Kernel) : $ k(x^{(i)},\ x) = \tanh (  \gamma  \langle x^{(i)}, \ x \rangle  +c) $

그 외 다른 커널들이 있을 수 있지만 대표적으로 많이 쓰이는 커널은 이 네 가지이고, 이들 중에서도 가장 많이 쓰이는 커널이 가우시안 RBF 커널인 것 같다. 사이킷런의 SVC(분류), SVR(회귀) 클래스에서도 kernel 파라미터의 디폴트값은 'rbf'이다.

 

텍스트로만 보면 와닿지 않을 수 있으니, 가우시안 RBF 커널과 시그모이드 커널이 적용된 그림을 제시하고 포스팅을 마치겠다.

 

<가우시안 RBF 커널>

 

<시그모이드 커널>

 

커널이 적용되면서 2차원 평면이 3차원 공간으로 확장되었으니, 데이터를 분리할 때는 2차원 초평면을 이용하여 분리하면 된다.

 

다음 포스팅은 더 쉬운 내용으로 찾아오는걸로... (수식이 너무 많아서 나도 힘듦)