SVM (Support Vector Machine) 1탄

 

 

Introduction

• SVM은 분류 알고리즘으로, binary classification을 합니다.

• 위 그림은 SVM에서 사용되는 함수들입니다.
• original SVM은 기본적으로 선형모형입니다. 그래서 3번째 식에 속합니다.

선형 분류기의 목적

• SVM은 binary classification이기 때문에 label, 즉 y에 해당하는 값을 (-1,1)로 지정해줍니다. (이유는 뒤에서 설명하겠습니다.)

Problem: find hypothesis $h: X \rightarrow\left\{-1,+1 \right\}$ in $H$ (classifier) with small generalization error $R_D(h)$

 

• 저희의 목적은 $X$  라는 입력 공간 상에서, 각자 학습 데이터의 실제 정답에 해당하는 label(+1과 -1)을 잘 분류하는 classifier $H$  를 찾는 것입니다.
• 정리하면, small generalization error인 $R_D(h)$를 가장 작게 할 수 있는 분류기를 찾는 것입니다.

• SVM은 linear classifier이기 때문에 high-dimensional에서도 linear seperation을 진행합니다.
• 위 그림과 같이, 2차원은 선으로 3차원은 면으로 구분합니다.
• 만약 차원이 3차원보다 높다면(이떄 차원을 d 차원이라고 하겠습니다.), d 차원에서 두 범주를 잘 구분하는 (d-1) 차원의 hyperplane을 찾는 것입니다.

• 다시 말하면, 위 그림에서 검정색 선과 같은 선형 분류기를 찾는 것입니다.
• 왼쪽 그림에서 $\mathbf{w}\cdot\mathbf{x}+b=0$  이 식보다 더 큰 범주에 속하면 +1을, 아니면 -1을 부여합니다.

$H=\left\{\mathbf{x}\rightarrow sign(\mathbf{w}\cdot\mathbf{x}+b:\ \mathbf{w}\in R^d,\ b\in R) \right\}$

• 정리하면, 모델 H는 $\mathbf{w}\cdot \mathbf{x} +b$ 에 input인 $\mathbf{x}$을 넣어 label을 부여합니다.
• 이때 음수가 나오면 -1로, 양수가 나오면 +1로 보는게 선형 분류기입니다.
• 위 식에서 w, b는 hyperparameter입니다.

Local Opimum? Global Optimum!

• 위 그림에는 label을 정확하게 분류하는 다양한 분류기들이 있고, 분류 경계면이 칠해져 있습니다.
• 이때 최적의 분류기는 경계면의 margin이 제일 넓은 2번 분류기입니다.

• 이제 margin의 넓이를 구해보겠습니다.
• 위의 그림에서 청록색을 분류 경계면이라고 하겠습니다.
  plus-plane과 청록색-plane 사이의 gap을 margin이라고 하겠습니다.
• 청록색에 $x_0$가 있다고 하면, $w^Tx_0+b=0$이 성립합니다.
• 위 그림에서 $\mathbf{w}$ 는 법선 벡터 입니다.
  plus plane에 $x_1$ 이 있다고 하면, $x_1=x_0+pw$ 와 같이 표현할 수 있습니다.
• 또한 $x_1$이 $w^Tx+b=1$에 있는 값이기 때문에 아래와 같이 전개할 수 있습니다.
  $w^Tx_1+b=1\rightarrow w^Tx_0+p\cdot w^Tw+b=1$
  이때, $w^Tx_0$와 $b$는 $w^Tx_b=1$에 있는 점이기 때문에 0이 됩니다.
• 그러면 남는 것은,
  $p\cdot w^Tw=1$ 이 되고, $p=-\frac{1}{w^Tw}=-\frac{1}{||w||^2}\rightarrow |p|=\frac{1}{||w||^2}$ 이 됩니다.
  즉, $|p|=\frac{1}{||w||^2}$ 이게 margin이 됩니다.

Margin and VC Dimension

• margin과 VC dimension 간의 관계를 생각해 보겠습니다.

The VC dimension of a separating hyperplane with a margin $\Delta$ is bounded as follows
$h\leq min( \left [ \frac{R^2}{\Delta^2} \right ],D)+1$
where D is the dimensionality of the input space, and R is the radius of the smallest sphere containing all the input vectors

• 위 식에서 D는 차원 수이고, R은 전체 Data를 입력공간에서 감싸는 초구의 반지름입니다.
  $\Delta$ 는 margin을 뜻합니다.
  차원 수는 데이터가 주어지는 순간 고정됩니다.
  초구도 단 한 개만 만들어지므로, 고정됩니다.
• 가변적인 것은 margin 뿐입니다.
  $\Delta$ 가 커지면 $\left [ \frac{R^2}{\Delta^2} \right ]$는 작아질 것입니다.
  margin을 매우 키우면 dimension보다 $\left [ \frac{R^2}{\Delta^2} \right ]$이 더 작아지는 상황이 발생할 수 있습니다.
• margin이 충분히 커서 dimension보다 $\left [ \frac{R^2}{\Delta^2} \right ]$이 더 작아지면, VC dimension은 $\left [ \frac{R^2}{\Delta^2} \right ] +1$이 됩니다.
• 반대로 margin이 작으면 VC dimension이 D+1 이 됩니다.

 

• 만약 margin을 충분히 키우는 선형모형이 된다면, VC dimension 자체가 D+1 보다 작아질 수 있습니다.

$R[f]\leq R_{emp}[f]+\sqrt{\frac{h(ln\frac{2n}{n}+1)+ln\frac{\delta}{4}}{n}}$

• margin을 최대화 한다는 것은 -> VC dimension을 줄어들게 하고 -> VC dimension이 줄어드는 것은 -> h를 줄이는 것입니다.
• h를 줄이면, $h(ln\frac{2n}{n}+1)$가 작아지고 -> capacity term이 작아지고 -> ... -> generalization risk가 작아진다.
• 정리하면, margin이 최대화되는 점을 찾으면 -> VC dimension이 작아지고 -> capacity term도 작아지고 -> 따라서 기대할 수 있는 risk가 줄어듭니다.

앞선 설명을 이해하기 쉬운 예시로 나타낸 슬라이드입니다.

 

Support Vector Machine: Cases

• hard margin은 예외를 벗어나는 것을 허용하지 않습니다. 반면 soft margin은 예외를 허용합니다.
• input space에서 선형 분리가 불가능한 상황에서는, kernel trick을 이용합니다.
• SVM은 상황에 따라 여러 case가 있습니다. 하나씩 살펴보겠습니다.

SVM Case I: Linear Case & Hard Margin

• 선형으로 입력 공간에서 분리가 가능하면서, hard margin의 case입니다.

- Objective function
min $\frac{1}{2}||\mathbf{w}^2||$

- Constraints

$s.t.\ y_i(\mathbf{w}^T\mathbf{x}_i+b)\geq 1\ \ \forall i$

• margin이 $\frac{2}{||w||^2}$ 라고 하겠습니다. 이를 최대화하기 위해 역수를 취하면,
  $\frac{1}{2}||\mathbf{w}^2||$가 되고, 이 식을 최소화하는 문제로 바뀌게 됩니다.
• 저희가 구하고자 하는 것은 (X, y)가 주어졌을 때, parameter "w, b"입니다.

• 그림으로 설명하면, 파란색 동그라미는 +1 평면보다 위쪽에 위치해야 합니다.
  반면에, 빨간색 동그라미는 -1 평면보다 아래쪽에 위치해야 합니다.
  이를 식으로 표현하면 다음과 같습니다.
  $y_i=+1\\ w^Tx_i+b\geq 1$
  $y_i=-1\\ w^Tx_i+b\leq -1$
  
  이는 $y_i(w^Tx_i+b)\geq 1$로 한번에 나타낼 수 있습니다.

• SVM에서 수학적 원리를 알기 위해 필요한 수식 전개입니다.
  Lagrangian multiplier를 이용하며, $L_P$ 문제를 $L_D$ 문제로 바꿔서 쉽게 풀어내는 원리입니다.
  자세한 수식에 대한 설명은 [출처]에 있는 동영상 강의를 봐주시기 바랍니다.

• 위 식에서 $\frac{1}{2}||\mathbf{w}^2||$가 원래 minimize 해야 하는 목적 함수이고,
  $(y_i(\mathbf{w^T\mathbf{x}_i}+b)-1)$ 는 제약식입니다.
  $\alpha_i$는 lagrangian 승수이고, 모든 제약식에 대해 전부 만족해야 하므로, ​식은
  $\sum_{i=1}^{N}\alpha_i(y_i(\mathbf{w^T\mathbf{x}_i}+b)-1)$로 표현할 수 있습니다.
• Primal 문제의 최적해는 KKT condition에 의해서 찾을 수 있습니다.
  w & b가 미지수이기 때문에, 이를 편미분하면 $w-\sum_{i=1}^{N}\alpha_iy_ix_i=0$이 나옵니다.
  그래서 최적해 식이 $w=\sum_{i=1}^{N}\alpha_iy_ix_i$와 같이 나온 것입니다.
  
  b에 대해서 편미분하면 ​$-\sum_{i=1}^{N}\alpha_iy_i=0 \rightarrow \sum_{i=1}^{N}\alpha_iy_i=0 \rightarrow \sum_{i=1}^{N}\alpha_iy_i=0$와 같이 식이 전개 됩니다.
• 이제 앞선 Primal 문제를 Dual 문제로 치환한 후 $\alpha$에 대한 식으로 바꿔보겠습니다.

 

• $L_P$ 문제는 앞서 찾은 KKT condition에 의한 $\mathbf{w}$의 최적해, b의 최적해를 이용해서 $L_D$ 문제로 변환할 수 있습니다. (자세한 건 동영상 강의 참조)
• 수식 전개를 거친 후 이를 $\alpha$에 대한 식으로 매우 단순화 시키면, $-\frac{1}{2}\lambda\alpha^2+\alpha$와 같이 $\alpha$에 대한 최대값을 찾는 문제가 됩니다.즉 $L_D$는 $\alpha$에 대한 convex function 입니다.

​

• 정리하면, primal 문제가 dual 문제로 바뀌면서 $\alpha$에 대한 문제가 되는 것입니다.
• 이에 따라 최적해는 다음과 같이 구할 수 있습니다.
  $x_{new}$ 라는 새로운 값이 들어오면​, $f(x_{new})=sign(\sum_{i=1}^{N}\alpha_i y_ix_i^T x_{new}+b)$와 같이 구할 수 있습니다.

• 추가적으로 알아야 할 사항은, 분류경계면에서 왼쪽 경계와 오른쪽 경계에 위치한 값들만이 w를 결정하는데 영향을 미칩니다.
  이들을 support vectors라고 합니다.

 

 

[출처] : https://www.youtube.com/watch?v=eZtrD6pYaaE&list=PLetSlH8YjIfWMdw9AuLR5ybkVvGcoG2EW&index=9