서포트 벡터 머신(Linear & Hard Margin SVM)
07 Mar 2021 | Machine-Learning
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Linear & Hard Margin SVM
이번 게시물부터 이후 몇 개의 게시물에 걸쳐 커널 기반의 학습 방법의 대표격인 서포트 벡터 머신(Support Vector Machine, SVM)에 대해서 알아보겠습니다. 서포트 벡터 머신은 기본적으로 이진 분류(Binary classification)을 위한 알고리즘입니다.
머신러닝에서 사용되는 분류기는 결정 경계를 만들어 나가는 로직을 알고리즘마다 가지고 있습니다. 아래 이미지는 각 분류기의 결정 경계 예시를 나타내고 있습니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
가장 왼쪽에 있는 kNN(k-Nearest Neighbor)은 가장 가까이에 있는 k개의 인스턴스 중 어떤 클래스에 속한 인스턴스가 더 많은 지에 따라서 결정 경계를 형성합니다. 다음에 있는 의사 결정 나무(Decision Tree)는 가장 높은 설명력을 확보하는 수직인 결정 경계를 반복해서 생성합니다. 세 번째에 있는 선형 분류기는 선형의 결정 경계를 형성하며 로지스틱 회귀, 선형 판별 분석(Linear Discriminant Analysis) 등이 이런 분류에 속합니다. 맨 오른쪽에 있는 비선형 분류기에는 뉴럴넷과 같은 것들이 속하게 됩니다. 서포트 벡터 머신은 기본적으로 선형(Linear) 모형에 해당하는 알고리즘입니다.
Support Vector Machine
서포트 벡터 머신에서 사용되는 가정과 표기법에 대해서 알아보도록 하겠습니다. 가장 먼저, 모든 인스턴스가 독립이며 동일한 분포(independent identically distributed, i.i.d.)로 샘플링 되었다고 가정합니다.
서포트 벡터 머신은 인스턴스 레이블을 표기하는 데에 있어서 일반적인 이진 분류기와 다른 점이 있습니다. 대부분의 이진 분류기는 ${1, 0}$, 즉 Positive 클래스를 $1$로, Negative 클래스를 $0$으로 표기하는데요. 서포트 벡터 머신에서는 Negative 클래스를 $-1$로 표기합니다. ${1, -1}$로 나누게 되는 것이지요. 이렇게 표기하는 이유는 서포트 벡터 머신의 알고리즘과도 관련이 있는데 이에 대해서는 아래에서 더 자세히 알아보도록 하겠습니다.
Better Classifier?
사실 많은 경우에 선형 분류기의 결정 경계가 하나로만 나오지는 않습니다. 아래 그림을 보겠습니다. (아래 분류기에서는 검은색과 흰색 클래스로 분류하였습니다.)
이미지 출처 : ko.wikipedia.org
위 그림에는 3개의 분류기의 결정 경계 $H_1,H_2,H_3$ 가 나타나 있습니다. 세 분류기의 성능을 비교해보자면 일단 $H_3$ 는 한 눈에 보아도 성능이 좋지 못한 분류기임을 알 수 있습니다. 인스턴스를 제대로 분류하고 있지 못함을 알 수 있지요. 그렇다면 $H_1,H_2$ 의 성능 비교는 어떻게 할 수 있을까요? 일단 두 분류기 모두 주어진 학습 데이터를 잘 구분하여 경험적 위험(Empirical risk)은 모두 $0$입니다 .
Margin
결론부터 이야기하자면 $H_2$ 가 $H_1$ 보다 더 좋은 분류기이며, 서포트 벡터 머신은 알아서 이러한 분류 경계를 찾아갑니다. 어떤 분류기가 더 좋은 지를 알 수 있는 척도를 마진(Margin) 이라고 합니다. 마진이란 ‘결정 경계로부터 등간격으로 확장시켰을 때 가장 가까이 만나는 (양쪽 클래스의) 객체와의 거리’입니다. 위 그림에서 $H_1, H_2$ 와 각각 가장 가까운 양 범주의 인스턴스를 잇는 얇은 선의 길이가 바로 마진이지요.
그렇다면 어떻게 마진이 이런 기준이 될 수 있을까요? 이를 알기 위해서는 지난 게시물에서 언급했던 VC dimension이라는, 모델의 복잡도와 관련있는 개념을 다시 가져와야 합니다. VC dimension $h$ 은 다음과 같은 식을 사용하여 구할 수 있습니다.
\[h \leq \min(\bigg[\frac{R^2}{\Delta^2}\bigg], D) + 1\]
이미지 출처 : www.researchgate.net
위 식에서 $R$ 은 공간 상에서 모든 데이터를 포함하는 구의 반지름이며, $\Delta$ 는 마진입니다. 그리고 $D$ 는 데이터의 차원입니다. $R, D$ 는 주어진 데이터로부터 결정됩니다. 결정 경계를 어떻게 정하더라도 달라지지 않는 상수이지요. 결정 경계를 어떻게 하느냐에 따라 달라지는 것은 마진 $\Delta$ 뿐입니다.
위 식에 따르면 $\Delta$가 작아서 $\frac{R^2}{\Delta^2}$ 가 $D$ 보다 클 때에는 분류기의 VC dimension이 $D+1$ 이 됩니다. $\Delta$가 커서 $\frac{R^2}{\Delta^2}$ 이 $D$ 보다 작아지게 되면 분류기의 VC dimension은 $\big[\frac{R^2}{\Delta^2}\big]+1$ 입니다. 마진이 클수록 VC dimension이 작아지는 것이지요. VC dimension $h$ 가 작아지면 아래 식에서 파란색에 해당하는 Capacity term이 작아지고 기대 위험(Expected risk) $R[f]$ 역시 작아지게 됩니다.
\[R[f] \leq R_\text{emp}[f] + \color{blue}{\sqrt{\frac{h(\ln\frac{2n}{h}+1) - \ln(\frac{\delta}{4})}{n}}}\]
다시 말해서 마진이 클수록 VC dimension이 작아집니다. VC dimension이 작아지면 Capacity term이 작아지면서 일반화에서 발생하는 오류가 작아지게 됩니다.
Kernel Machine vs Neural Net
“Margin이 클수록 더 좋은 분류기가 된다”와 “서포트 벡터 머신은 항상 마진이 최대가 되도록 한다”는 것만 기억한 채 잠깐 샛길로 빠져보겠습니다. 커널 머신이 잘 나가던 시절에 신경망, 즉 딥러닝이 공격받았던 지점이 이 부분입니다. 서포트 벡터 머신은 항상 마진을 최대로 하는 점, 즉 전역 최적점(Global optimum)을 찾습니다. 하지만 신경망은 경험적 위험만을 최적점을 찾아가는 척도로 하기 때문에 지역 최적점(Local optimum)에 빠져버리기 쉽다는 것이지요.
하지만 2014년에 발표된 논문에 의하면 ‘실험적으로 지역 최적점에 갇혀 빠져나가지 못하는 경우가 많지 않음’을 알아냈습니다. 저차원 공간에서는 지역 최적점에 빠졌을 때 경사 하강법 알고리즘으로 빠져 나오기가 어렵습니다. 하지만 실제 데이터는 수 십, 수 백 차원으로 구성되어있습니다. 이런 고차원 공간 상에서는 모든 방향으로 기울기가 0인 점이 거의 없습니다. 그렇기 때문에 학습을 충분히 한다면 경사 하강법으로도 전역 최적점을 찾아갈 수 있게 되지요. 이 논문으로 인해 딥러닝은 오해(?)를 풀고 연구에 박차를 가하게 되었으며 컴퓨터 비전이나 자연어처리 분야에서 각광받을 수 있었습니다.
Quantization
다시 본론으로 돌아와서 서포트 벡터 머신을 더 자세히 알아보도록 하겠습니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
마진을 수식으로 나타내면 다음과 같습니다. 먼저 결정 경계면 위의 점 $x_0$ 에서 법선 벡터 $w$ 를 정의하고, 법선 벡터가 $+$ 마진 평면과 만나는 점을 $x_1$ 이라고 하면 $x_1 = x_0 + pw$ 로 나타낼 수 있습니다. 여기서 $p$ 는 우리가 구하고자 하는 마진의 크기(너비)입니다. 이 값을 $x_1$ 에 대입해주면 $p$ 를 구할 수 있습니다.
\[\begin{aligned}
w^Tx_1 + b &= 1 \\
w^T(x_0+pw) + b &= 1 \\
w^Tx_0 + pw^Tw + b &= 1 \\
pw^Tw &= 1 \\
(\because w^Tx_0 + b &= 0)\\
\therefore p = \frac{1}{w^Tw} &= \frac{1}{\Vert w\Vert^2}
\end{aligned}\]
마진을 $\frac{2}{\Vert w\Vert^2}$ 로 나타내는 책도 있습니다. 마진을 결정 경계와 서포트 벡터 사이의 거리로 볼 지, 아니면 그 2배로 볼 지에 따라 달라집니다. 수치는 다르지만 어느 것을 사용하더라도 최소화하는 방법은 동일하니 일단은 전자 $\frac{1}{\Vert w\Vert^2}$ 로 보도록 하겠습니다.
Hard Margin SVM
서포트 벡터 머신은 결정 경계면이 선형(Linear)인지 아닌지, 예외를 허용하는 지에 따라서 아래와 같이 4가지로 구분할 수 있습니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
가장 먼저 결정 경계면이 선형이며 예외를 허용하지 않는 하드 마진(Hard margin) 서포트 벡터 머신에 대해서 알아보겠습니다. 아래는 인스턴스와 결정 경계면, 마진 평면을 나타낸 이미지입니다. 아래 식에서 $x_i$ 는 각 인스턴스를 나타내며 $y_i$ 는 인스턴스의 클래스를 나타냅니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
위 이미지에서 파란색으로 표현된 인스턴스의 클래스 $y_i = 1$ 이고 모든 인스턴스는 $\mathbf{w}^T\mathbf{x}+b \geq 1$ 을 만족합니다. 빨간색으로 표현된 인스턴스의 클래스 $y_i = -1$ 이고, 인스턴스의 $\mathbf{w}^T\mathbf{x}+b \leq -1$ 을 만족하지요. 그렇기 때문에 모든 인스턴스가 $y_i(\mathbf{w}^T\mathbf{x} + b) \geq 1$ 라는 식을 만족합니다.
목표는 서포트 벡터 사이의 거리 $\frac{2}{\Vert \mathbf{w}^2 \Vert}$ 의 최대화입니다. 목적 함수를 역수인 $\frac{1}{2}\Vert \mathbf{w}\Vert^2$ 로 설정하고 이를 최소화 $\mathbf{w}$ 를 찾는 문제로 변경하겠습니다. 위에서 구한 제약 조건을 반영한 라그랑주 승수법을 사용하여 나타내면 다음은 같습니다.
\[\min L_p(\mathbf{w},b,\alpha_i) = \frac{1}{2}\Vert \mathbf{w}\Vert^2 - \sum^N_{i=1}\alpha_i(y_i(\mathbf{w}^T\mathbf{x}_i + b) -1) \\
s.t. \quad \alpha_i \geq 0\]
$L_p$ 는 원초(Primal) 문제이며 여기서 구해진 조건을 사용하여 쌍대(Dual)문제로1 바꿀 수 있습니다. 말로는 어려우니 아래 예시를 살펴보도록 하겠습니다.
Primal-Dual
$f(x) = 0.5x^2-2x +3$ 이고 $x \geq 2$ 라는 제약조건이 있을 때 다음과 같은 원초 문제를 만들 수 있습니다.
\[0.5x^2 - 2x + 3 \qquad x \geq 2 \\
L_P : 0.5x^2 - 2x + 3 -\lambda(x-2)\]
원초 문제로 주어진 함수를 최소화 하는 조건이 미분했을 때 0이되는 점이므로 이로부터 $x$ 에 관한 식을 만들 수 있습니다.
\[\frac{\partial L_p}{\partial x} = x - 2 - \lambda \\
\frac{\partial L_p}{\partial x} = 0 \rightarrow x = 2+\lambda\]
그리고 이렇게 구한 조건을 다시 원초 문제에 대입하면 Wolfe’s 쌍대 문제 $L_D$ 로 변형할 수 있습니다. 대신 원초 문제가 최댓값 찾기라면 쌍대 문제는 최솟값 찾기가 되고, 원초 문제가 최솟값 찾기라면 쌍대 문제는 최댓값 찾기가 됩니다. 아무튼 위 원초 문제를 변환한 쌍대 문제는 다음과 같습니다.
\[\begin{aligned}
L_D &= 0.5(2+\lambda)^2 - 2(2+\lambda) + 3 - \lambda(\lambda+2-2) \\
&=-0.5 \lambda^2 +1 \qquad (s.t. \quad \lambda \geq 0)
\end{aligned}\]
위 쌍대 문제를 최대화하는 $\lambda = 0$ 이므로 $x = 2$ 가 됩니다. 이는 원초 문제를 최소로 하는 $x$ 값과 동일합니다. 이렇게 식을 변형해서 쓰는 이유는 원초 문제보다 쌍대 문제가 쉬울 때가 있기 때문인데요. 다시 원래 서포트 벡터 머신으로 돌아가서 원초 문제를 바꿔보도록 하겠습니다.
KKT Condition
서포트 벡터 머신의 원초 문제는 다음과 같았습니다.
\[\min L_p(\mathbf{w},b,\alpha_i) = \frac{1}{2}\Vert \mathbf{w}\Vert^2 - \sum^N_{i=1}\alpha_i(y_i(\mathbf{w}^T\mathbf{x}_i + b) -1) \\
s.t. \quad \alpha_i \geq 0\]
KKT 조건2을 사용하여 해당 식이 최저일 때의 조건을 구해보겠습니다. 원초 문제를 각 변수인 $\mathbf{w}, b$ 로 편미분한 값이 0일 때의 조건을 구합니다.
\[\frac{\partial L_p}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum^N_{i=1} \alpha_iy_i\mathbf{x}_i \qquad \frac{\partial L_p}{\partial b} = 0 \Rightarrow \sum^N_{i=1} \alpha_iy_i = 0\]
$\mathbf{w} = \sum^N_{i=1} \alpha_iy_i\mathbf{x}_i$ 를 다시 대입하여 쌍대 문제로 만들어주면 다음과 같은 $L_D$ 식을 얻을 수 있습니다.
\[L_D = \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1} \alpha_i\alpha_jy_iy_j\mathbf{x}_i\mathbf{x}_j - \sum^N_{i=1}\sum^N_{j=1} \alpha_i\alpha_jy_iy_j\mathbf{x}_i\mathbf{x}_j - b\sum^N_{i=1}\alpha_iy_i+\sum^N_{i=1}\alpha_i \\\]
$\sum^N_{i=1} \alpha_iy_i = 0$ 조건을 사용하여 식을 정리하면 다음과 같이 간단하게 식을 변형할 수 있습니다.
\[L_D = \sum^N_{i=1}\alpha_i - \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1} \alpha_i\alpha_jy_iy_j\mathbf{x}_i\mathbf{x}_j \\
s.t. \quad \sum^N_{i=1}\alpha_iy_i =0, \quad \alpha_i \geq0\]
이렇게 구해진 쌍대문제 $L_D$ 는 $\alpha$ 에 대한 컨벡스 함수(Convex function)이기 때문에 항상 최적해를 찾을 수 있게 됩니다. 항상 최적해를 찾을 수 있기 때문에 일반화로부터 발생하는 오류를 최소화할 수 있지요.
Conclusion
이번 게시물에서는 서포트 벡터 머신의 가장 기본적인 형태인 하드 마진 선형 분류기에 대해 알아보았습니다. 마진이 최대화 되는 과정에서 복잡한 수식이 등장했지만 포인트는 마진을 최대화 하는 결정 경계가 항상 하나로 나온다는 것이지요. 하지만 하드 마진 선형 분류기로 모든 데이터를 분류할 수 있는 것은 아닙니다. 다음 게시물에서는 소프트 마진 선형 분류기나 커널 트릭을 사용한 비선형 분류기에 대해서 알아보도록 하겠습니다.
-
쌍대성에 관한 설명은 ratsgo님의 블로그나 모두를 위한 컨벡스 최적화를 참조하시면 좋습니다. ↩
-
KKT 조건에 대한 설명 역시 ratsgo님의 블로그나 모두를 위한 컨벡스 최적화를 참조하시면 좋습니다. ↩
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Linear & Hard Margin SVM
이번 게시물부터 이후 몇 개의 게시물에 걸쳐 커널 기반의 학습 방법의 대표격인 서포트 벡터 머신(Support Vector Machine, SVM)에 대해서 알아보겠습니다. 서포트 벡터 머신은 기본적으로 이진 분류(Binary classification)을 위한 알고리즘입니다.
머신러닝에서 사용되는 분류기는 결정 경계를 만들어 나가는 로직을 알고리즘마다 가지고 있습니다. 아래 이미지는 각 분류기의 결정 경계 예시를 나타내고 있습니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
가장 왼쪽에 있는 kNN(k-Nearest Neighbor)은 가장 가까이에 있는 k개의 인스턴스 중 어떤 클래스에 속한 인스턴스가 더 많은 지에 따라서 결정 경계를 형성합니다. 다음에 있는 의사 결정 나무(Decision Tree)는 가장 높은 설명력을 확보하는 수직인 결정 경계를 반복해서 생성합니다. 세 번째에 있는 선형 분류기는 선형의 결정 경계를 형성하며 로지스틱 회귀, 선형 판별 분석(Linear Discriminant Analysis) 등이 이런 분류에 속합니다. 맨 오른쪽에 있는 비선형 분류기에는 뉴럴넷과 같은 것들이 속하게 됩니다. 서포트 벡터 머신은 기본적으로 선형(Linear) 모형에 해당하는 알고리즘입니다.
Support Vector Machine
서포트 벡터 머신에서 사용되는 가정과 표기법에 대해서 알아보도록 하겠습니다. 가장 먼저, 모든 인스턴스가 독립이며 동일한 분포(independent identically distributed, i.i.d.)로 샘플링 되었다고 가정합니다.
서포트 벡터 머신은 인스턴스 레이블을 표기하는 데에 있어서 일반적인 이진 분류기와 다른 점이 있습니다. 대부분의 이진 분류기는 ${1, 0}$, 즉 Positive 클래스를 $1$로, Negative 클래스를 $0$으로 표기하는데요. 서포트 벡터 머신에서는 Negative 클래스를 $-1$로 표기합니다. ${1, -1}$로 나누게 되는 것이지요. 이렇게 표기하는 이유는 서포트 벡터 머신의 알고리즘과도 관련이 있는데 이에 대해서는 아래에서 더 자세히 알아보도록 하겠습니다.
Better Classifier?
사실 많은 경우에 선형 분류기의 결정 경계가 하나로만 나오지는 않습니다. 아래 그림을 보겠습니다. (아래 분류기에서는 검은색과 흰색 클래스로 분류하였습니다.)
이미지 출처 : ko.wikipedia.org
위 그림에는 3개의 분류기의 결정 경계 $H_1,H_2,H_3$ 가 나타나 있습니다. 세 분류기의 성능을 비교해보자면 일단 $H_3$ 는 한 눈에 보아도 성능이 좋지 못한 분류기임을 알 수 있습니다. 인스턴스를 제대로 분류하고 있지 못함을 알 수 있지요. 그렇다면 $H_1,H_2$ 의 성능 비교는 어떻게 할 수 있을까요? 일단 두 분류기 모두 주어진 학습 데이터를 잘 구분하여 경험적 위험(Empirical risk)은 모두 $0$입니다 .
Margin
결론부터 이야기하자면 $H_2$ 가 $H_1$ 보다 더 좋은 분류기이며, 서포트 벡터 머신은 알아서 이러한 분류 경계를 찾아갑니다. 어떤 분류기가 더 좋은 지를 알 수 있는 척도를 마진(Margin) 이라고 합니다. 마진이란 ‘결정 경계로부터 등간격으로 확장시켰을 때 가장 가까이 만나는 (양쪽 클래스의) 객체와의 거리’입니다. 위 그림에서 $H_1, H_2$ 와 각각 가장 가까운 양 범주의 인스턴스를 잇는 얇은 선의 길이가 바로 마진이지요.
그렇다면 어떻게 마진이 이런 기준이 될 수 있을까요? 이를 알기 위해서는 지난 게시물에서 언급했던 VC dimension이라는, 모델의 복잡도와 관련있는 개념을 다시 가져와야 합니다. VC dimension $h$ 은 다음과 같은 식을 사용하여 구할 수 있습니다.
\[h \leq \min(\bigg[\frac{R^2}{\Delta^2}\bigg], D) + 1\]
이미지 출처 : www.researchgate.net
위 식에서 $R$ 은 공간 상에서 모든 데이터를 포함하는 구의 반지름이며, $\Delta$ 는 마진입니다. 그리고 $D$ 는 데이터의 차원입니다. $R, D$ 는 주어진 데이터로부터 결정됩니다. 결정 경계를 어떻게 정하더라도 달라지지 않는 상수이지요. 결정 경계를 어떻게 하느냐에 따라 달라지는 것은 마진 $\Delta$ 뿐입니다.
위 식에 따르면 $\Delta$가 작아서 $\frac{R^2}{\Delta^2}$ 가 $D$ 보다 클 때에는 분류기의 VC dimension이 $D+1$ 이 됩니다. $\Delta$가 커서 $\frac{R^2}{\Delta^2}$ 이 $D$ 보다 작아지게 되면 분류기의 VC dimension은 $\big[\frac{R^2}{\Delta^2}\big]+1$ 입니다. 마진이 클수록 VC dimension이 작아지는 것이지요. VC dimension $h$ 가 작아지면 아래 식에서 파란색에 해당하는 Capacity term이 작아지고 기대 위험(Expected risk) $R[f]$ 역시 작아지게 됩니다.
\[R[f] \leq R_\text{emp}[f] + \color{blue}{\sqrt{\frac{h(\ln\frac{2n}{h}+1) - \ln(\frac{\delta}{4})}{n}}}\]다시 말해서 마진이 클수록 VC dimension이 작아집니다. VC dimension이 작아지면 Capacity term이 작아지면서 일반화에서 발생하는 오류가 작아지게 됩니다.
Kernel Machine vs Neural Net
“Margin이 클수록 더 좋은 분류기가 된다”와 “서포트 벡터 머신은 항상 마진이 최대가 되도록 한다”는 것만 기억한 채 잠깐 샛길로 빠져보겠습니다. 커널 머신이 잘 나가던 시절에 신경망, 즉 딥러닝이 공격받았던 지점이 이 부분입니다. 서포트 벡터 머신은 항상 마진을 최대로 하는 점, 즉 전역 최적점(Global optimum)을 찾습니다. 하지만 신경망은 경험적 위험만을 최적점을 찾아가는 척도로 하기 때문에 지역 최적점(Local optimum)에 빠져버리기 쉽다는 것이지요.
하지만 2014년에 발표된 논문에 의하면 ‘실험적으로 지역 최적점에 갇혀 빠져나가지 못하는 경우가 많지 않음’을 알아냈습니다. 저차원 공간에서는 지역 최적점에 빠졌을 때 경사 하강법 알고리즘으로 빠져 나오기가 어렵습니다. 하지만 실제 데이터는 수 십, 수 백 차원으로 구성되어있습니다. 이런 고차원 공간 상에서는 모든 방향으로 기울기가 0인 점이 거의 없습니다. 그렇기 때문에 학습을 충분히 한다면 경사 하강법으로도 전역 최적점을 찾아갈 수 있게 되지요. 이 논문으로 인해 딥러닝은 오해(?)를 풀고 연구에 박차를 가하게 되었으며 컴퓨터 비전이나 자연어처리 분야에서 각광받을 수 있었습니다.
Quantization
다시 본론으로 돌아와서 서포트 벡터 머신을 더 자세히 알아보도록 하겠습니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
마진을 수식으로 나타내면 다음과 같습니다. 먼저 결정 경계면 위의 점 $x_0$ 에서 법선 벡터 $w$ 를 정의하고, 법선 벡터가 $+$ 마진 평면과 만나는 점을 $x_1$ 이라고 하면 $x_1 = x_0 + pw$ 로 나타낼 수 있습니다. 여기서 $p$ 는 우리가 구하고자 하는 마진의 크기(너비)입니다. 이 값을 $x_1$ 에 대입해주면 $p$ 를 구할 수 있습니다.
\[\begin{aligned} w^Tx_1 + b &= 1 \\ w^T(x_0+pw) + b &= 1 \\ w^Tx_0 + pw^Tw + b &= 1 \\ pw^Tw &= 1 \\ (\because w^Tx_0 + b &= 0)\\ \therefore p = \frac{1}{w^Tw} &= \frac{1}{\Vert w\Vert^2} \end{aligned}\]마진을 $\frac{2}{\Vert w\Vert^2}$ 로 나타내는 책도 있습니다. 마진을 결정 경계와 서포트 벡터 사이의 거리로 볼 지, 아니면 그 2배로 볼 지에 따라 달라집니다. 수치는 다르지만 어느 것을 사용하더라도 최소화하는 방법은 동일하니 일단은 전자 $\frac{1}{\Vert w\Vert^2}$ 로 보도록 하겠습니다.
Hard Margin SVM
서포트 벡터 머신은 결정 경계면이 선형(Linear)인지 아닌지, 예외를 허용하는 지에 따라서 아래와 같이 4가지로 구분할 수 있습니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
가장 먼저 결정 경계면이 선형이며 예외를 허용하지 않는 하드 마진(Hard margin) 서포트 벡터 머신에 대해서 알아보겠습니다. 아래는 인스턴스와 결정 경계면, 마진 평면을 나타낸 이미지입니다. 아래 식에서 $x_i$ 는 각 인스턴스를 나타내며 $y_i$ 는 인스턴스의 클래스를 나타냅니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
위 이미지에서 파란색으로 표현된 인스턴스의 클래스 $y_i = 1$ 이고 모든 인스턴스는 $\mathbf{w}^T\mathbf{x}+b \geq 1$ 을 만족합니다. 빨간색으로 표현된 인스턴스의 클래스 $y_i = -1$ 이고, 인스턴스의 $\mathbf{w}^T\mathbf{x}+b \leq -1$ 을 만족하지요. 그렇기 때문에 모든 인스턴스가 $y_i(\mathbf{w}^T\mathbf{x} + b) \geq 1$ 라는 식을 만족합니다.
목표는 서포트 벡터 사이의 거리 $\frac{2}{\Vert \mathbf{w}^2 \Vert}$ 의 최대화입니다. 목적 함수를 역수인 $\frac{1}{2}\Vert \mathbf{w}\Vert^2$ 로 설정하고 이를 최소화 $\mathbf{w}$ 를 찾는 문제로 변경하겠습니다. 위에서 구한 제약 조건을 반영한 라그랑주 승수법을 사용하여 나타내면 다음은 같습니다.
\[\min L_p(\mathbf{w},b,\alpha_i) = \frac{1}{2}\Vert \mathbf{w}\Vert^2 - \sum^N_{i=1}\alpha_i(y_i(\mathbf{w}^T\mathbf{x}_i + b) -1) \\ s.t. \quad \alpha_i \geq 0\]$L_p$ 는 원초(Primal) 문제이며 여기서 구해진 조건을 사용하여 쌍대(Dual)문제로1 바꿀 수 있습니다. 말로는 어려우니 아래 예시를 살펴보도록 하겠습니다.
Primal-Dual
$f(x) = 0.5x^2-2x +3$ 이고 $x \geq 2$ 라는 제약조건이 있을 때 다음과 같은 원초 문제를 만들 수 있습니다.
\[0.5x^2 - 2x + 3 \qquad x \geq 2 \\ L_P : 0.5x^2 - 2x + 3 -\lambda(x-2)\]원초 문제로 주어진 함수를 최소화 하는 조건이 미분했을 때 0이되는 점이므로 이로부터 $x$ 에 관한 식을 만들 수 있습니다.
\[\frac{\partial L_p}{\partial x} = x - 2 - \lambda \\ \frac{\partial L_p}{\partial x} = 0 \rightarrow x = 2+\lambda\]그리고 이렇게 구한 조건을 다시 원초 문제에 대입하면 Wolfe’s 쌍대 문제 $L_D$ 로 변형할 수 있습니다. 대신 원초 문제가 최댓값 찾기라면 쌍대 문제는 최솟값 찾기가 되고, 원초 문제가 최솟값 찾기라면 쌍대 문제는 최댓값 찾기가 됩니다. 아무튼 위 원초 문제를 변환한 쌍대 문제는 다음과 같습니다.
\[\begin{aligned} L_D &= 0.5(2+\lambda)^2 - 2(2+\lambda) + 3 - \lambda(\lambda+2-2) \\ &=-0.5 \lambda^2 +1 \qquad (s.t. \quad \lambda \geq 0) \end{aligned}\]위 쌍대 문제를 최대화하는 $\lambda = 0$ 이므로 $x = 2$ 가 됩니다. 이는 원초 문제를 최소로 하는 $x$ 값과 동일합니다. 이렇게 식을 변형해서 쓰는 이유는 원초 문제보다 쌍대 문제가 쉬울 때가 있기 때문인데요. 다시 원래 서포트 벡터 머신으로 돌아가서 원초 문제를 바꿔보도록 하겠습니다.
KKT Condition
서포트 벡터 머신의 원초 문제는 다음과 같았습니다.
\[\min L_p(\mathbf{w},b,\alpha_i) = \frac{1}{2}\Vert \mathbf{w}\Vert^2 - \sum^N_{i=1}\alpha_i(y_i(\mathbf{w}^T\mathbf{x}_i + b) -1) \\ s.t. \quad \alpha_i \geq 0\]KKT 조건2을 사용하여 해당 식이 최저일 때의 조건을 구해보겠습니다. 원초 문제를 각 변수인 $\mathbf{w}, b$ 로 편미분한 값이 0일 때의 조건을 구합니다.
\[\frac{\partial L_p}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum^N_{i=1} \alpha_iy_i\mathbf{x}_i \qquad \frac{\partial L_p}{\partial b} = 0 \Rightarrow \sum^N_{i=1} \alpha_iy_i = 0\]$\mathbf{w} = \sum^N_{i=1} \alpha_iy_i\mathbf{x}_i$ 를 다시 대입하여 쌍대 문제로 만들어주면 다음과 같은 $L_D$ 식을 얻을 수 있습니다.
\[L_D = \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1} \alpha_i\alpha_jy_iy_j\mathbf{x}_i\mathbf{x}_j - \sum^N_{i=1}\sum^N_{j=1} \alpha_i\alpha_jy_iy_j\mathbf{x}_i\mathbf{x}_j - b\sum^N_{i=1}\alpha_iy_i+\sum^N_{i=1}\alpha_i \\\]$\sum^N_{i=1} \alpha_iy_i = 0$ 조건을 사용하여 식을 정리하면 다음과 같이 간단하게 식을 변형할 수 있습니다.
\[L_D = \sum^N_{i=1}\alpha_i - \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1} \alpha_i\alpha_jy_iy_j\mathbf{x}_i\mathbf{x}_j \\ s.t. \quad \sum^N_{i=1}\alpha_iy_i =0, \quad \alpha_i \geq0\]이렇게 구해진 쌍대문제 $L_D$ 는 $\alpha$ 에 대한 컨벡스 함수(Convex function)이기 때문에 항상 최적해를 찾을 수 있게 됩니다. 항상 최적해를 찾을 수 있기 때문에 일반화로부터 발생하는 오류를 최소화할 수 있지요.
Conclusion
이번 게시물에서는 서포트 벡터 머신의 가장 기본적인 형태인 하드 마진 선형 분류기에 대해 알아보았습니다. 마진이 최대화 되는 과정에서 복잡한 수식이 등장했지만 포인트는 마진을 최대화 하는 결정 경계가 항상 하나로 나온다는 것이지요. 하지만 하드 마진 선형 분류기로 모든 데이터를 분류할 수 있는 것은 아닙니다. 다음 게시물에서는 소프트 마진 선형 분류기나 커널 트릭을 사용한 비선형 분류기에 대해서 알아보도록 하겠습니다.
-
쌍대성에 관한 설명은 ratsgo님의 블로그나 모두를 위한 컨벡스 최적화를 참조하시면 좋습니다. ↩
-
KKT 조건에 대한 설명 역시 ratsgo님의 블로그나 모두를 위한 컨벡스 최적화를 참조하시면 좋습니다. ↩
Comments