[단단한 머신러닝] Ch 6 - 서포트 벡터 머신

훈련 세트의 샘플들을 분리할 때 분할 초평면이 쓰인다. 가장 잘 분리된 분할 초평면이란 이분법적 분리 클래스에서 샘플이 분류 경계에서 어느 정도 거리기 있어 오류가 없는 초평면 상태이다. 샘플 공간에서 분할 초평면은 다음 선형 방정식을 통해 묘사된다.
\( w^{T}x + b = 0\) 
\(w\) 는 법선 벡터이고, 초평면의 방향을 결정한다. \(b\)는 변위항으로 초평면과 원점 간의 거리를 결정한다. 샘플 공간에서의 임의점 x에서 초평면 (\(w, b)\)까지의 거리는 
\[ r = \frac{\left| w^{T}x + b \right|}{\left\| w \right\| }\]
양성 클래스 +1 이면, \( w^{T}x + b > 0\). 음성 클래스 -1이면, \( w^{T}x + b < 0\) 
여기서, 초평면에 가장 가까운 몇 개의 훈련 샘플 포인트는 다음 조건을 만족해야 하며, 이들을 서포트 벡터라고 한다. 두 개의 서로 다른 클래스의 서포트 벡터에서 초평면에 달하는 거리의 합은 그 다음에 나오는 식에 해당하며, 이를 마진이라 부른다.
\[\left\{
\begin{array}{ll}
w^{T}x_i + b \geq +1, & y_i=+1 \\
w^{T}x_i + b \leq -1, & y_i=-1
\end{array}
\right.\]
\[ \iota = \frac{2}{\left\| w \right\|} \]

최대 거리, 즉 분할 초평면이 잘 분리된 상태를 가지고 싶다면,
\[ \underset {w, b}{max} \frac{2}{\left\| w \right\|} \]
\[ s.t. y_i(w^{T}x_i + b) \geq 1, i=1,2...m\]
위의 조건들에서 \(\left\| w \right\|^{-1}\) 최대화해야하고, 이는 \(\left\| w \right\|^{2}\) 최소화와 같은 맥락이다.
\[ \underset {w, b}{min} \frac{\left\| w \right\|^{2}}{2} \]
\[ s.t.  y_i(w^{T}x_i + b) \geq 1, i=1,2...m\]
컨벡스 이차 프로그래밍 문제이며 최적화 방법을 통해 서포트 벡터들을 구할 수 있으며,
이것이 서포트 벡터 머신의 기본 모델이다.

---

쌍대문제에 다뤄볼 것이다.
위의 서포트 벡터 기본 모델에 라그랑주 승수법을 사용하면, 쌍대문제를 얻는다. 이는 서포트 벡터들을 구하기 위한 최적화 방법이며, 기본 모델 식에 라그랑주 승수를 추가해 다음과 라그랑주 함수 식을 도출할 수 있다.
\[ L(w, b, \alpha) =  \frac{\left\| w \right\|^{2}}{2} + \sum_{i=1}^{m} \alpha_i (1- y_i(w^{T} x_i + b))\]

위 식을 정리하면,
\[f(x) = w^{T}x + b \\= \sum_{i=1}^{m} \alpha_i y_i x_i^{T}x +b \]
위의 모델이 도출되며, 서포트 벡터 기본 모델의 s.t 뒤의 제약 조건에서 알 수 있듯이 다음 KKT( Karush-kuhn-Tucker) 조건들을 만족해야 한다.
\[\left\{
\begin{array}{ll}
\alpha_i \geq 0 \\
y_i f(x_i) - 1 \geq 0 \\
\alpha_i(y_i f(x_i) - 1) = 0 \\
\end{array}
\right.\]
모든 훈련 샘플은 첫 번째의 라그랑주 상수가 0 이거나, 두 번째 식이 0이다. 라그랑주 상수가 0이라는 의미는 서포트 벡터 모델에 영향을 주지 않는 샘플이라는 의미이고, 후자는 최대 마진 경계상에 위치한다는 의미이다. 즉, 서포트 벡터라는 의미이다.
여기까지 훈련 샘플이 서포트 벡터 머신인지 아닌지를 쌍대 문제와 연관시켜서 풀어보았다. 이제 x, 해를 구해야한다.

가장 유명한 SMO(Sequential Minimal Optimization) 방법을 이용해서 풀어보도록 하겠다.
조건은 라그랑주 상수 외에 모든 변수는 고정이며 라그랑주 상수에서의 극한값을 구한다. 제약 조건( s.t )에 의해 라그랑주 상수는 매번 두 개의 변수를 선택해서 그 둘을 제외한 나머지들을 고정한 후 극한값을 구한다. 두 라그랑주 상수 중 하나라도 KKT 조건을 만족하지 못하면, 해를 구하고자 하는 함수는 커지며 해를 도출하기가 힘들어진다. 둘 중 어떤 라그랑주 상수가 이 함수를 증가시키는지, 즉 KKT 조건 위배 정도가 가장 큰 변수를 선택한다. 이후 SMO 알고리즘으로 라그랑주 상수 및 b (편항항)을 구한다. SMO 알고리즘에 관한 설명은 다음 블로그에서 참고하도록 하자.

---

앞선 문제들은 선형 분리가 가능하다는 전제로 했었다. 만약 선형 분리가 되지 않아 이차함수, 더 다양한 함수와 같이 클래스가 구분된다면 x를 \(\phi(x)\)로 공간을 확장한다. 결론적인 식만 얘기하지면
\[f(x) = w^{T}\phi(x) + b \\= \sum_{i=1}^{m} \alpha_i y_i \phi(x_i)^{T}\phi(x) +b \\ = \sum_{i=1}^{m} \alpha_i y_i \kappa(x, x_i) +b \]
여기서 \(\kappa\)는 커널 함수이며, 위의 식을 전개해서 모델의 최적해를 얻을 수 있다. 이를 서포트 벡터 전개라고 부른다.

우라는 샘플이 특정 공간 내에서 선형 분리되기를 바라며, 이 커널 함수를 통해 최적화 및 해를 구하는 데에 도움이 된다. 적절한 커널 함수를 고름으로써 일종의 초평면의 분류 성능이 좋은지, 나쁜지 결정된다. 종류는 선형 커널, 다항식 커널, 가우스 커널, 라플라스 커널, 시그모이드 커널이 대표적이다.

위에서 말했듯이 선형 분리가 된다고 가정했는데 실제로는 선형 분리가 가능한 적절한 커널 함수를 얻기 힘들다. 구현했더라도 과적합의 가능성이 있기에 커널 함수에 약간의 오류를 허용해주면 해결이 가능하다. 이를 소프트 마진(soft margin)이리고 한다. 여태까지 선형 분리가 된다고 가정한 것은 하드 마진(hard margin) 이라고 한다.

위의 기본 모델에서 라그랑주 상수 대신 0/1 손실함수를 쓰며, 이는 다음과 같다.