레퍼런스
SVM 위키 : https://en.wikipedia.org/wiki/Support_vector_machine
KKT 위키 : https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
Quora KKT 질문 : https://www.quora.com/What-do-the-Karush%E2%80%93Kuhn%E2%80%93Tucker-conditions-mean
이기창님 블로그 : https://ratsgo.github.io/machine%20learning/2017/05/23/SVM/
개요
가장 유명한 머신러닝 알고리즘 중 하나인 SVM(Support Vector Machine; 서포트 벡터 머신)에 대해 알아보려고 한다.
상대적으로 작은 데이터셋에서 좋은 분류결과를 잘 냈기 때문에 딥러닝 이전에는 상당히 강력한 분류기였다. 하지만 아주 큰 데이터 셋에 대해서는 잘 작동하지 않아 딥러닝에 밀리게 된다. 그래도 아직까지는 널리 잘 쓰이고 있기 때문에 리뷰해보려고 한다.
가장 좋은 분류기
분류기라 하면 공간 상의 데이터 벡터들을 어떠한 기준을 두고 분류하는 것을 말할 것이다. 직선으로 분류하는 것이 가장 보편적이다.
초록색 별모양 데이터와 빨간색 동그라미 데이터를 직선으로 나눠보자. 노란색과 주황색 선 중에 어느 직선이 데이터들을 더 잘 분류했다고 할 수 있을까? 자연스럽게 주황색이라는 생각이 든다. 주황색 선은 노란색 선보다 데이터를 더 여유롭게 나누고 있기 때문일 것이다.
수학적으로 접근할 수 있도록 해보자. "여유롭게" 나눈다는 것은 경계선과 가장 가까운 데이터까지의 거리가 멀다는 얘기일 것이다. 거리가 멀수록 좋기 때문에 이를 분류기의 점수라 둘 수 있겠다.
이 때, 분류기에서 가장 가까운 점까지의 거리를 마진(margin), 그 점들을 서포트 벡터(Support Vector)라 하겠다. 그리고 마진은 $M$이라고 표시한다. 그러면 아래 그림과 같이 나타낼 수 있다. 서포트 벡터가 된 데이터들은 굵게 표시했다.
그럼 우리의 목표는 마진 $M$을 가장 크게 하는 직선을 찾는 것이라 할 수 있다. 학습이 끝나면 서포트 벡터를 제외한 점들은 다 버리고 서포트 벡터만을 분류에 사용해도 된다. 저장 공간 절약의 이점도 있다.
수치화
본격적으로 수치화해보자. 초록별 클래스 서포트 벡터를 $\mathbf{x}^+$, 빨간 동그라미 클래스 서포트 벡터를 $\mathbf{x}^-$로 놓을 수 있다. 그리고 두 클래스를 관통하는 주황색 직선을 $\mathbf{w}^T \mathbf{x} + b = 0$, 경계선을 $\mathbf{w}^T \mathbf{x} + b = \pm1$ 이라 하면 아래 그림과 같이 표현할 수 있다.
고등학교 때 배웠던 평면위의 점과 직선사이의 거리를 벡터로 생각해보면 $d = {|\mathbf{w}^T \mathbf{x}' + b| \over ||\mathbf{w}||}$가 되는데 이를 초평면 $\mathbf{w}^T \mathbf{x} + b = 0$ 에도 똑같이 적용할 수 있다. 그러면 마진 $M$을 $\mathbf{w}$를 이용해 표현할 수 있게 된다.
$$M = {|\mathbf{w}^T \mathbf{x}^\pm + b| \over ||\mathbf{w}||} = {|\pm1| \over ||\mathbf{w}||} = {1 \over ||\mathbf{w}||}$$
우리의 목표는 이 마진 $M = {1 \over ||\mathbf{w}||}$을 가장 크게 하는 $\mathbf{w}$를 찾는 것이다. 이는 $\mathbf{w}^T \mathbf{w} = ||\mathbf{w}||^2$를 최소화하는 것과 동치인데 후자를 사용하면 convex 문제가 되어 강력한 풀이법을 사용할 수 있으니 후자로 계산한다. 계산상의 편의를 위해 2로 나눠준다(안 나눠줘도 상관 없다!!!! 그냥 예쁘게 보이려고 나누는 것이다). 따라서 우리의 목표는 다음과 같다.
$$ \text{maximize } M \Leftrightarrow \text{minimize } ||\mathbf{w}||^2 \Leftrightarrow \text{minimize } {1 \over 2} \mathbf{w}^T \mathbf{w} $$
문제를 수학적으로 정의하는 데에 성공했다. 하지만 아직 서포트 벡터를 제외한 다른 점들을 고려하지 않았다. 다른 점들까지 고려하면 목표 식에 제약조건이 따라 붙게 된다.
초록 클래스의 데이터 점들은 $ \mathbf{w}^T \mathbf{x}_i + b \ge 1$, 빨간 클래스는 $ \mathbf{w}^T \mathbf{x}_i + b \le -1$를 만족하므로 식을 더 간단하게 하기 위해 목표값(클래스의 라벨) $t_i$를 $1$ 또는 $0$이 아닌 $+1$ 또는 $-1$을 갖게 해 $ t_i \cdot ( \mathbf{w}^T \mathbf{x}_i + b ) $ 를 항상 양수가 되도록 만든다. 그러면 제약조건을 수식 하나로 표현할 수 있다. (클래스의 라벨은 사실 우리가 정하기 나름이다. 복잡한 계산을 좋아한다면 초록색 별을 $+123$ 동그라미를 $-372$로 설정해도 된다.)
$$ t_i = \begin{cases} +1 & \text{(for green)} \\ -1 & \text{(for red)} \end{cases} \\ t_i ( \mathbf{w}^T \mathbf{x}_i + b ) \ge 1 $$
따라서 최종 목표를 다시 쓰면 다음과 같다.
$$ \begin{align*} \text{minimize}& \quad {1 \over 2} \mathbf{w}^T \mathbf{w} \\ \text{subject to}& \quad 1 - t_i ( \mathbf{w}^T \mathbf{x}_i + b ) \le 0 \\ \text{for all}& \quad i = 1, \dots, n \end{align*}$$
Method of Lagrangian Multiplier
만약 제약식이 모두 등호 조건이라면 학부 1학년 때 배운 라그랑주 승수법으로 문제를 풀 수 있다.
등호 조건이 하나인 문제
만약 제약이 한 개인 문제라면
제약 $g$의 plot에 $f$를 접하도록 만드는 것이 핵심이다. 어떤 함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}$를 제약 $g : \mathbb{R}^n \rightarrow \mathbb{R}$에 맞춰 최적화 시키면 최적해 $\mathbf{x}^*$에 대해 다음이 성립한다.
$$\nabla f(\mathbf{x}^*) = \lambda \nabla g(\mathbf{x}^*) \\ g(\mathbf{x}^*) = 0$$
($g(\mathbf{x}^*) =c$일 수도 있지만 어차피 넘기면 $=0$으로 만들 수 있으니 그러려니 하자.)
그러면 적당한 $\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x})$을 정의하여 문제를 식 하나로 정의할 수 있다.
$$\nabla_{\mathbf{x}, \lambda} \mathcal{L}(\mathbf{x}, \lambda) = 0 \Leftrightarrow \begin{cases} \nabla_{\mathbf{x}} f(\mathbf{x}) - \lambda \nabla_{\mathbf{x}} g(\mathbf{x}) = 0 \\ g(\mathbf{x}) = 0 \end{cases}$$
등호 조건이 여러 개인 문제
이 또한 Lagrangian으로 푸는 것이 가능하다. 제약이 $M$개 있다고 하면 승수를 $M$개 사용해 제약 $g_i$를 하나의 제약으로 표현하는 것이 가능하다.
$$g(\mathbf{x}) = [g_1(\mathbf{x}), \, \dots, g_M(\mathbf{x})]^T \\ \lambda = [ \lambda_1, \, \dots, \lambda_M]^T \\ \mathbf{\lambda}^T g(\mathbf{x}) = \sum_{k=1}^M \lambda_k g_k(\mathbf{x})$$
그럼 등호 조건이 한 개인 문제와 같아진다. 아 람다가 안 굵어진다...ㅠ 람다에 아래 첨자 안 붙어 있으면 벡터다.
$$\mathcal{L}(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) - \mathbf{\lambda}^T g(\mathbf{x}) \\ \nabla_{\mathbf{x}, \lambda} \mathcal{L}(\mathbf{x}, \lambda) = 0 \Leftrightarrow \begin{cases} \nabla_{\mathbf{x}} f(\mathbf{x}) - \mathbf{\lambda}^T \nabla_{\mathbf{x}} g(\mathbf{x}) = 0 \\ g(\mathbf{x}) = \mathbf{0} \end{cases}$$
등호 조건이 한 개인 문제에서 $\lambda$가 벡터로 바뀐 차이 밖에 없다. 미지수가 $\mathbf{x}$가 $n$개, $\mathbf{\lambda}$가 $M$개 합해서 $n + M$개에다가 방정식이 $n + M$개 있으므로 웬만하면 풀 수 있다.
여러 개의 등호 조건에 부등호 조건 여러 개가 섞인 문제
부등호 조건이 $m$개, 등호 조건이 $l$개인 최적화 문제를 식으로 표현하면 $f, g, h: \mathbb{R}^n \rightarrow \mathbb{R}$인 $f, g, h$에 대해
$$\begin{align*} \text{optimize}& \quad f(\mathbf{x}) \\ \text{subject to}& \quad g_i(\mathbf{x}) \le 0 \\ &\quad h_j(\mathbf{x}) = 0 \\ \text{for}& \quad i = 1, \dots, m, j = 1, \dots, l \end{align*}$$
이렇게 되겠다. 이 역시도 Lagrangian으로 풀이가 가능하지만 KKT(Karush-Kuhn-Tucker) 조건이라는 특별한 조건을 만족해야 한다.
Karush-Kuhn-Tucker Conditions
문제의 최적해 $\mathbf{x}^*$에 대해 다음 명제를 모두 만족시키는(KKT 조건을 성립시키는) $\lambda, \mu$가 존재한다.
KKT (Karush-Kuhn-Tucker) Conditions
$$ \begin{align*} \text{optimize}& \quad f(\mathbf{x}) \\ \text{subject to}& \quad g_i(\mathbf{x}) \le 0, \\ & \quad h_j(\mathbf{x}) = 0 \\ \text{for}& \quad i = 1, \dots, m, \,\, j = 1, \dots, l \end{align*}$$
Stationarity (문제의 최적해; 우리가 풀 방정식)
$$ \nabla f(\mathbf{x}^*) + \sum^m_{i=1} \mu_i \nabla g_i(\mathbf{x}^*) + \sum^l_{j=1} \lambda_j \nabla h_j(\mathbf{x}^*) = 0 $$
Primal feasibility (Primal 문제가 해를 가질 조건; 그냥 제약 조건 한 번 더 씀)
$$ g_i(\mathbf{x}^*) \le 0, \text{ for } i = 1, \dots , m \\ h_j(\mathbf{x}^*) = 0, \text{ for } j = 1, \dots , l $$
Dual feasibility (Dual 문제가 해를 가질 조건)
$$ \mu_i \ge 0, \text{ for } i = 1, \dots, m $$
Complementary slackness ($\mathcal{L}$을 깔끔하게 정의하려면 필요함)
$$ \mu_i g_i(\mathbf{x}^*)=0, \text{ for } i = 1, \dots, m $$
우리의 문제를 여기에 대입해보자. Notation도 살짝 변경해야 한다.
$$\mathbf{x} \leftarrow \mathbf{w}, \mathbf{\mu} \leftarrow \mathbf{\alpha}, m \leftarrow n, l = 0, \\ f(\mathbf{w}) = {1 \over 2} ||\mathbf{w}||^2, g_i(\mathbf{w}) = t_i(\mathbf{w}^T \mathbf{x} + b) - 1$$
를 넣어보자! 시력테스트... 참고로 SVM에서는 등호 조건이 없으므로 $l=0$이다.
$$ \begin{align*} \text{minimize}& \quad f(\mathbf{w}) = {1 \over 2} ||\mathbf{w}||^2 \\ \text{subject to}& \quad g_i(\mathbf{w}) = t_i(\mathbf{w}^T \mathbf{x}_i + b) -1 \,\,{\color{red} \ge}\,\, 0, \\ \text{for}& \quad i = 1, \dots, n \end{align*}$$
Stationarity
$$\nabla f(\mathbf{w}^*) \,\,{\color{red} -}\,\, \sum_{i=1}^m \alpha_i \nabla g_i(\mathbf{w}^*) = 0$$
Primal feasibility
$$g(\mathbf{w}^*) = t_i(\mathbf{w}^T \mathbf{x}^*_i + b) - 1 \,\,{\color{red} \ge}\,\, 0$$
Dual feasibility
$$\alpha_i \ge 0$$
Complementary slackness
$$\alpha_i g_i(\mathbf{w}^*) = \alpha_i(t_i(\mathbf{w}^{*T} \mathbf{x}_i + b) - 1)= 0$$
제약식의 부호가 바뀌어 Stationarity의 $g$의 부호가 바뀐 것을 확인해보자. (빨간색)
그리고 $g$와 $h$가 모두 아핀(선형변환 + 상수)이면 KKT 조건을 만족하여 후술할 strong duality를 보장한다. 그러니 자세한 건 무시하고 위의 식에 대입하여 풀면 되겠다.
Complementary Slackness를 확인해보자. $\alpha_i$ 또는 $g_i$가 둘 다 음이 아니므로 둘 중에 하나는 무조건 0이다. 만약 $g_i \neq 0$이면 ($\mathbf{x}_i$가 서포트 벡터가 아니면) $\alpha_i = 0$임을 알 수 있다. $\alpha_i = 0$이기 때문에 이 벡터들은 나중에 evaluation 시에 무시할 수 있다.
그럼 이제 KKT 조건을 이용해 안심하고 Lagrangian을 적용할 수 있다.
$$\mathcal{L}(\mathbf{w}, b, \alpha) = {1 \over 2} ||\mathbf{w}||^2 - \sum_{i=1}^n \alpha_i [ t_i (\mathbf{w}^T \mathbf{x}_i + b) -1 ]$$
를 정의하고 Stationarity를 이용하면 된다.
$$ \begin{align*} \left . {\partial \mathcal{L} \over \partial \mathbf{w}} \right | _{\mathbf{w}=\mathbf{w}^*} = 0 \quad&\Rightarrow\quad \mathbf{w}^* - \sum_{i=1}^n \alpha_i t_i \mathbf{x}_i = 0 \\ \left . {\partial \mathcal{L} \over \partial b} \right |_{\mathbf{w}=\mathbf{w}^*} = 0 \quad&\Rightarrow\quad \sum_{i=1}^n \alpha_i t_i = 0 \end{align*}$$
여기서
$$ \mathbf{w}^* = \sum^n_{i=1} \alpha_i t_i \mathbf{x}_i, \,\, \sum^n_{i=1} \alpha_i t_i = 0$$
를 얻었지만 아직 $\alpha$는 변수이다. $\alpha$를 얻기 위해 방금 얻은 식을 다시 $\mathcal{L}$에 대입해준다.
Duality
일단 첫 번째 항
$$ \begin{align*} {1 \over 2} ||\mathbf{w}^*||^2 &= {1 \over 2} \mathbf{w}^{*T} \mathbf{w}^* \\ &= {1 \over 2} \mathbf{w}^{*T} \sum_{j=1}^n \alpha_j t_j \mathbf{x}_j \\ &= {1 \over 2} \sum_{j=1}^n \alpha_j t_j(\mathbf{w}^{*T} \mathbf{x}_j) \\ &= {1 \over 2} \sum_{j=1}^n \alpha_j t_j \left [ \sum_{i=1}^n \alpha_i t_i \mathbf{x}^T_i \mathbf{x}_j \right ] \\ &= {1 \over 2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j t_i t_j \mathbf{x}^T_i \mathbf{x}_j \end{align*} $$
그리고 두 번째 항
$$ \begin{align*} \sum_{i=1}^n \alpha_i (t_i(\mathbf{w}^{*T} \mathbf{x}_i + b) - 1) &= \sum_{i=1}^n \alpha_i t_i (\mathbf{w}^{*T} \mathbf{x}_i + b) - \sum_{i=1}^n \alpha_i \\ &= \sum_{i=1}^n \alpha_i t_i \mathbf{w}^{*T} \mathbf{x}_i + b \underbrace{\sum_{i=1}^n \alpha_i t_i}_{=0} - \sum_{i=1}^n \alpha_i \\ &= \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j t_i t_j \mathbf{x}^T_i \mathbf{x}_j - \sum_{i=1}^n \alpha_i \end{align*} $$
둘이 계산하면
$$\mathcal{L} (\mathbf{w}^*, b^*, \alpha) = \sum_{i=1}^n \alpha_i - {1 \over 2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j t_i t_j \mathbf{x}^T_i \mathbf{x}_j $$
근데 우리가 만약 $\mathcal{L}_\text{dual} (\alpha) = \mathcal{L} (\mathbf{w}^*, b^*, \alpha)$라 놓는다면 원래의 최적화문제
$$\min_{\mathbf{w}, b, \alpha} \mathcal{L} (\mathbf{w}, b, \alpha)$$
는
$$\max_\alpha \mathcal{L} (\mathbf{w}^*, b^*, \alpha) = \mathcal{L}_\text{dual} (\alpha)$$
와 같아진다.
이렇게 convex 문제를 바꾼 문제를 Dual 문제라고 하는데 왜 $\min$이 $\max$로 바뀌었는지 원리를 간단하게 설명해보겠다.
$$\mathcal{L} (\mathbf{w}, b, \alpha) \ge \mathcal{L} (\mathbf{w}^*, b^*, \alpha)$$
인 것은 자명하고 $\mathcal{L} (\mathbf{w}, b, \alpha)$의 최솟값을 $\mathcal{L}_P$, $\mathcal{L} (\mathbf{w}^*, b^*, \alpha)$의 최댓값을 $\mathcal{L}_D$라 하면 Weak Duality에 의해
$$\mathcal{L} (\mathbf{w}, b, \alpha) \ge \mathcal{L}_P \ge \mathcal{L}_D \ge \mathcal{L} (\mathbf{w}^*, b^*, \alpha)$$
가 성립하는데 여기서 또 Strong duality에 의해 $\mathcal{L}_P = \mathcal{L}_D$가 성립한다. 따라서 우리는 한 쪽 문제만 골라서 풀면 되는 것이다. 그리고 지금은 Dual 문제가 더 쉬우니 Dual 문제를 풀도록 한다.
정리해서 써보면
$$\begin{align*} \text{maximize} \quad& \mathcal{L}_\text{dual} (\alpha) \\ &= \sum_{i=1}^n \alpha_i - {1 \over 2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j t_i t_j \mathbf{x}^T_i \mathbf{x}_j \\ \text{subject to} \quad& \sum_{i=1}^n \alpha_i t_i = 0 \\ \quad& \alpha_i \ge 0 \\ \text{for} \quad& i = 1, \dots, n \end{align*}$$
Stable Bias
$b^*$를 아직 안 정했다.
$$\left . {\partial \mathcal{L} \over \partial b} \right |_{\mathbf{w}=\mathbf{w}^*} = 0 \quad\Rightarrow\quad \sum_{i=1}^n \alpha_i t_i = 0$$
조건은 $b^*$에 독립적임을 볼 수 있으므로 $b^*$는
$$t_i ( \mathbf{w}^{*T} \mathbf{x}_i + b^* ) - 1 \ge 0$$
만 만족하면 된다.
아무 서포트 벡터나 하나 대입해서
$$t_i ( \mathbf{w}^{*T} \mathbf{x}_i + b^* ) - 1 = 0$$
를 이용해 쉽게 계산할 수 있지만 만약 대입한 서포트 벡터에 오류가 있을 경우 모델이 매우 불안정해진다. 그래서 모든 서포트 벡터를 평균 내서 계산하기로 한다.
$$b^* = {1 \over N_s} \sum_{\text{support vectors } j} \left ( t_j - \sum_{i=1}^n \alpha_i t_i \mathbf{x}_i^T \mathbf{x}_j \right ) \qquad \left ( \because \, \mathbf{w}^* = \sum_{i=1}^n \alpha_i t_i \mathbf{x}_i \right )$$
$\mathbf{w}^*$를 계산할 때 모든 벡터에 대해서 계산하는 것 같아 보이지만 서포트 벡터가 아니면 $\alpha_i = 0$이기 때문에 결국에는 서포트 벡터끼리 계산하나 마찬가지다.
Evaluation
이제 모델은 완성했고 새로운 벡터 $\mathbf{z}$에 대해 다음과 같이 계산해 evaluation할 수 있다.
$$\mathbf{w}^{*T} \mathbf{z} + b^* = \left ( \sum_{i=1}^n \alpha_i t_i \mathbf{x}_i \right )^T \mathbf{z} + b^*$$
의 부호를 따져서 클래스를 판단하면 되겠다.
Soft Margin
하지만 언제나 데이터들이 초평면 하나로 깔끔하게 나뉘지는 않을 것이다. 그래서 어느 정도 잘못 분류된 자료들을 허용하여 모델을 최적화 시키기로 한다. 슬랙(slack; 느슨한) 변수 $\xi_i \ge 0$를 사용해 오류를 얼마 정도 허용할지 결정한다.
$$ t_i (\mathbf{w}^T \mathbf{x} - b) \ge 1 - \mathbf{\xi}_i $$
그러면 최적화 문제는 목적함수도 작게 하는 와중에 잘못 분류되는 정도도 작게 해야 한다. 따라서 달라진 최적화 문제는 다음과 같다.
$$\begin{align*} \text{minimize}& \quad {1 \over 2} ||\mathbf{w}||^2 + C \sum_{i=1}^n \xi_i \\ \text{subject to}& \quad t_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1 - \xi_i, \\ &\quad \xi_i \ge 0 \\ \text{for}& \quad i = 1, \dots, n \end{align*}$$
그리고 KKT 조건을 잘 적용하면 다음의 Dual 문제를 얻을 수 있다고 한다. (사실 어떻게 적용했는지는 모르겠다.)
$$\begin{align*} \text{maximize} &\quad \mathcal{L}_\text{dual} (\alpha) = \sum_{i=1}^n \alpha_i - {1 \over 2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j t_i t_j \mathbf{x}^T_i \mathbf{x}_j \\ \text{subject to} &\quad 0 \le \alpha_i \le C \\ &\quad \sum_{i=1}^n \alpha_i t_i = 0 \\ \text{for} &\quad i = 1, \dots, n \end{align*}$$
$\xi_i$는 우리가 만질 필요가 없는 것을 확인했다. 우리는 적절한 $C$만 찾아주면 된다.
이로서 SVM으로 비선형 분류를 할 수 있게 되었지만 조심히 사용하지 않으면 목적함수가 non-convex해져 최적해를 찾을 수 없을 수 있다.(위키)