[Remark] Support Vector Machine 이해하기

 

[Remark] Support Vector Machine  이해하기

Support Vector Machine (SVM)은 Machine Learning의 분류기 중에 한 종류이다. Margine을 최대화하는 방향으로 학습한다는 말을 자주 사용하는데, 이번 포스팅에서는 Margine을 최대화하는 것의 의미를 짚어보고자 한다. 해당 글은 ratsgo blog 와 wikipedia를 참고하여 작성하였습니다.

 

1. 문제를 풀기 전, 주어진 상황

• $(x_1, y_1), \cdots, (x_n, y_n) $ 점들이 있다.
• $y\in \{ -1, 1 \}$ 레이블이다.   

* 여기서, -1, +1 으로 레이블을 고정하는 것은 나중에 최적화 문제를 푸는데 도움을 주기 때문입니다. 

2. SVM의 목표

• $w * x -b $ 값을 이용해서, y를 구분하는 classifier를 만드는 것

3. Remark

• 데이터셋에 대해서, $w * x-b>0$ 이면, $\hat y=1$ 로 예측하고, $w * x-b<0$ 이면, $hat y = -1$로 레이블을 예측한다.
• w 값을 적절하게 조절하면, 두 개의 레이블을 구분하는 평면을 찾을 수 있다. (혹은 최대로 구분되는)
• b 값을 적절하게 조절하면, $y=1$ 에 해당하는 점들과, $y=-1$ 에 해당하는 점들을 그림과 같이 동일한 거리로 나눌 수 있다. ($wx-b=0$이 두 선의 중앙선이 된다. )

 

이미지 출처 : Wikipedia, Support Vector Machine

---

4. Calculate the Margine 

그림과 같은 상황이라면, 노란색 영역을 최대화하는 것이 두 개의 데이터집합을 가장 잘 구분하는 선이 된다. 따라서 중앙선 ($w * x -b = 0$)으로부터 거리를 최대화하는 것이 목표이다. 여기서 $w$는 초평면 $w*x - b = 0$에 대해서 수직인 normal vector이다.

 

$w * x -b =-1$에 있는 점을 $x^+$, $w * x-b = -1$에 있는 점을 $x^-$ 라고 하면,

적절한 $\lambda$ 값에 대해서 다음이 성립한다.

$$x^+ - x^- = \lambda w   ~~~~ (1)$$

$$(w * x^+ - b) - (w * x^- -b) = 2 ~~~~  (2)$$

$\{w * x - b | x \in \mathcal{X}\}$ 는 초평면에 대한 집합이다. 여기서 $w$ 는 초평면에 대한 normal vector로, 평면에 수직이다. 따라서 $x^+, x^-$ 을 지나는 벡터는 $w$에 평행하며, 적당한 $\lambda$에 대해서 $x^+ - x^- = \lambda w$가 성립한다. 

 

주어진 식을 이용하여, 다음과 같이 Margine을  구할 수 있다.

$$w * (x^+ - x^-) = 2 ~~~~ (3)$$

$$w * \lambda w = 2 ~~~~ (4)$$

$$\lambda = \frac{2}{w^T w} ~~~~ (5)$$

따라서 거리(margine) 를 최대화하는 것은 $\frac{2}{||w||^2}$ 을 최대화 하는 것과 같은 문제이다. 이는 역수를 최소화하는 문제와 동일하므로 결국 다음 최대화 문제를 풀면, Margine을 최대화하는 것이다. 

$$maximize~ \frac{1}{2} ||w||^2 ~~~~(6) $$

하지만, 모든 $w$에 대해서 가능한 것은 아니고, 제약 사항을 만족하는 $w$만을 택해야 한다. 여기서 제약사항은 그림에서 나타낸 두 개의 추가적인 선에 대한 것으로, 다음과 같다. 

$$ w* x_i - b = 1 , ~~  \text{for}~ x_i, \text{s.t.}~ y_i = 1 $$

$$ w* x_i - b = -1 , ~~  \text{for}~ x_i, \text{s.t.}~ y_i = -1 $$ 이러한 제약사항이 추가된 최적화 문제는 constraint optimization으로, 다음에 기회가 되면 다루겠습니다. 해를 구하는 정확한 방법은 기존 원문을 참조해주세요.

 

5. 왜 이름이 Support Vector Machine인가?

SVM 을 공부하면서 가장 의문이 드는 점은 Support Vector라는 이름 그 자체입니다. 여기서 말하는 Support Vector는 $(x_i, y_i)$에서 특별한 $x_i$들을 지칭합니다. 초평면을 구하면서 마진을 최대화 할 때, $w* x_i - b = 1 , w* x_i - b = -1 $에 해당하는 $x_i$들이 있었습니다. 사실 마진을 최대화하는 초평면은 해당 평면들 위해 있는 $x_i$들에 의해서 완벽하게 결정됩니다. 이렇게 max-margine hyperplane을 결정하는데 도움을 주는 $w* x_i - b = 1 , w* x_i - b = -1 $의 벡터 $x_i$ 들을 support vector라고 하고, 애들로부터 max-margine hyperplane을 만들어서 분류하기 때문에, Support Vector Machine 이라는 이름이 붙었습니다. 

 

영어 원문: An important consequence of this geometric description is that the max-margin hyperplane is completely determined by those  $x_i$ that lie nearest to it. These  $x_i$ are called support vectors.

 

---

References

https://ratsgo.github.io/machine learning/2017/05/23/SVM/

https://en.wikipedia.org/wiki/Support-vector_machine