개요
Perceptron에서 Mediocore문제를 해결하기 위하여 마진이라는 개념을 이용하여 두 집단을 분류하는 방법론을 말한다.
선형 SVM
주어진 학습용 데이터 집합 D(N 개의 점으로 이루어진 집합)를 다음과 같이 정의해보자.
- [math]\mathcal{D} = \{ (\mathbf{x}_i, y_i)|\mathbf{x}_i \in \mathbb{R}^p, y_i \in \{-1,1\}\}_{i=1}^n[/math]
각 [math]\mathbf{x}_i[/math] 는 p차원의 실수 벡터이고 , [math]y_i[/math] 는 [math]\mathbf{x}_i[/math] 가 어떤 클래스에 속해있는지를 나타내는 값으로 1 혹은 -1의 값을 가진다.
위의 학습용 데이터 집합이 [math]y_i[/math]값에 따라 선형적으로 분리될 수 있을 때, 데이터 집합을 분리하는 것을 초평면이라 하며 다음의 조건을 만족하는 점 X의 집합으로 나타낼 수 있다.
- [math]\mathbf{w}\cdot\mathbf{x} - b=0.\,[/math]
[math]\cdot[/math] 은 내적 연산자이고, [math]{\mathbf{w}}[/math]은 초평면의 법선 벡터(normal vector)이다.
주어진 초평면의 서포트 벡터([math]{\mathbf{X}}[/math]+, [math]{\mathbf{X}}[/math]-)는 다음과 같이 정의된다.
- [math]{\mathbf{X}}[/math]+ : [math]y_i=+1[/math]의 데이터중에서 초평면과 가장 가까운 데이터
- [math]{\mathbf{X}}[/math]- : [math]y_i=-1[/math]의 데이터중에서 초평면과 가장 가까운 데이터
주어진 초평면과 같은 법선벡터를 가지면서 [math]{\mathbf{X}}[/math]+ 를 지나는 초평면은
- [math]\mathbf{w}\cdot\mathbf{x} - b=+1\,[/math]
으로 나타낼 수 있고 비슷한 방식으로 [math]{\mathbf{X}}[/math]- 를 지나는 초평면은
- [math]\mathbf{w}\cdot\mathbf{x} - b=-1\,[/math]
이와 같이 나타낸다.
초평면의 마진은 각 서포트 벡터를 지나는 초평면 사이의 거리를 의미한다. 기하학적으로 두 초평면 사이의 거리 즉, 마진을 구하면 [math]\tfrac{2}{\|\mathbf{w}\|}[/math]라는 것을 알 수 있으며 서포트벡터머신은 마진을 최대로 만드는 알고리즘이다.
서포트벡터를 지나는 초평면 사이엔 데이터 포인트가 존재하지 않아야 하므로 다음과 같은 식이 성립한다.
- [math]y_i=+1[/math]인 [math]\mathbf{x}_i[/math] 에 대해서 [math]\mathbf{w}\cdot\mathbf{x}_i - b \ge+1\,[/math]
- [math]y_i=-1[/math]인 [math]\mathbf{x}_i[/math] 에 대해서 [math]\mathbf{w}\cdot\mathbf{x}_i - b \le-1\,[/math]
위 두 식은 아래와 같은 식으로 나타낼 수 있다.
- [math]y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,\text{ for all } 1 \le i \le n.[/math]
초평면의 조건을 따르며 마진의 최댓값을 구하고자 하는 서포트 벡터 머신 문제는 다음과 같은 최적화 문제로 표현할 수 있다.
- [math]\arg\min_{(\mathbf{w},b)}\|\mathbf{w}\|[/math]
- 단, [math]y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,\text{ for all } 1 \le i \le n.[/math]
원 형식
위에서 설명한 최적화 문제는 [math]\mathbf{w}[/math]의 노름인 [math]\|\mathbf{w}\|[/math]이 제곱근을 포함하고 있기 때문에 풀기 어렵다. 위의 최적화 문제에서 [math]\|\mathbf{w}\|[/math]를 [math]\tfrac{1}{2}\|\mathbf{w}\|^2[/math]로 치환하여도 최적화 문제를 만족시키는 해 [math]\mathbf{w}[/math], [math]b[/math]는 변하지 않는다. 또한 [math]\tfrac{1}{2}\|\mathbf{w}\|^2[/math]로 치환을 하게 되면 위의 문제는 2차 계획법(틀:Llang) 최적화 문제가 된다. 치환된 최적화 문제는 아래와 같이 나타낼 수 있다.
- [math]\arg\min_{(\mathbf{w},b)}\frac{1}{2}\|\mathbf{w}\|^2[/math]
- 단, [math]y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1,\text{ for all } 1 \le i \le n.[/math]
라그랑주 승수법을 이용하면 위의 문제를 다음과 같은 안장점(틀:Llang)을 찾는 문제로 나타낼 수 있다.
- [math]\arg\min_{\mathbf{w},b } \max_{\boldsymbol{\alpha}\geq 0 } \left\{ \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b)-1]} \right\}[/math]
안장점을 찾는 과정에서 [math]y_i(\mathbf{w}\cdot\mathbf{x_i} - b) - 1 \gt 0 [/math]으로 분류될 수 있는 모든 점들은 그에 대응하는 [math]\alpha_i[/math]가 0으로 지정되기 때문에 영향을 미치지 않는다. 이제 이 문제는 정규 2차 계획법 기법으로 해결할 수 있다. 정적 Karush-Kuhn-Tucker 조건에 따르면, 문제의 해는 훈련 벡터(틀:Llang)의 선형 조합으로 표현될 수 있다.
- [math]\mathbf{w} = \sum_{i=1}^n{\alpha_i y_i\mathbf{x_i}}[/math]
적은 수의 [math]\alpha_i[/math]만이 0보다 큰 값을 가지고, 그에 대응하는 [math]\mathbf{x_i}[/math]들은 [math]y_i(\mathbf{w}\cdot\mathbf{x_i} - b) = 1[/math]를 만족하는 정확한 서포트 벡터이다. 이 식을 통해 다음과 같이 오프셋 (컴퓨터 과학) [math]b[/math]에 대한 정의를 유도할 수 있다.
- [math]\mathbf{w}\cdot\mathbf{x_i} - b = \frac{1}{y_i} = y_i \iff b = \mathbf{w}\cdot\mathbf{x_i} - y_i[/math]
[math]b[/math]는 [math]y_i[/math]와 [math]x_i[/math]에 의존하므로 각각의 데이터 포인트마다 값이 다르다. 표본 분포의 평균은 모평균(population mean)에 대해 불편 추정량(틀:Llang)이므로 다음과 같이 모든 서포트 벡터 [math]N_{SV}[/math]에 대해서 평균을 취하는 것이 좋다.
- [math]b = \frac{1}{N_{SV}} \sum_{i=1}^{N_{SV}}{(\mathbf{w}\cdot\mathbf{x_i} - y_i)}[/math]
분류 가능하지 않으면
- 실수를 허용한다. 그러나 최대한 이러한 실수를 줄이기 위해서 노력한다.
- 더 많은 feature를 더한다. 그러나 이러면 curse of dimensionality에 걸려 overfitting이 일어나게 된다.
실수를 허용하면
todo!()