Margin, Support Vector

Support Vector Machine: Basic

SVM 핵심

DT는 overfitting(regularization이 없는 경우)이 심하고 일반화가 어렵다.

$\blacksquare$: Support vector, $|\larr\rarr|$: Margin

• Optimal Hyperplane: 서로 다른 두 class의 vectors(samples) 사이에 maximal margin이 있는 linear decision function
  • 그러기 위해서 필요한 것은 이러한 margin을 결정하는 support vectors
  • optimal hyperplane은 dataset보다 한 차원 낮음
• Margin을 이용한 일반화 능력 향상 기법
  • ANN(Artificial Neural Network)에서는 2와 3사이의 $\bullet$을 $\circ$로 인식
  • SVM은 그에 비해, 최대한 안전하고 일반화가 가능하도록 3까지 진행

Linear SVM

Example: 선형분리가 가능한 iris dataset

• 왼쪽의 경우, bad example로, 새로운 data에 대해 매우 sensitive하기에 Decision boundary가 바뀔 수 있다.
• 오른쪽의 경우, SVM으로, Decision boundary가 크게 변하지 않는다.

SVM classifier: class간 가능한 가장 넓은 거리를 적합하도록 하고 이를 large margin (maximum-margin) classification라고 한다.

• 거리 바깥에 더 많은 training instances를 추가하게 되면,
  Linear SVM의 경우 decision boundary에 영향이 거의 없다.

Assumption

• binary linear classifier, d(x)는 다음과 같은 linear equation으로 표현할 수 있다.
  • $d(x)=w_1x_1+w_2x_2+\cdots+w_dx_d+b=w^Tx+b=0$
  • $d(x)$는 0보다 큰 경우와, 0보다 작은 경우로 특징 공간이 나뉠 수 있다.
  • $w$: hyperplane에 직교하는 normal vector, $b$: y절편
• Linear separable 가능한 경우
  • 결정 직선이 두 부류를 완벽히 분류하면서 분할 띠의 중앙에 위치하도록 정함
  • 직선의 방향 $w$를 정하면 bias $b$는 자동으로 정해짐
    • 여기서 너비 "2s"를 여백(margin)이라 부름
    • 분할 띠 경계(곧, 점선 위)에 걸쳐있는 sample이 support vector

SVM의 목표

• Margin이 가장 큰 hyperplane의 방향 $w$를 찾는 것
  $h=\frac{|d(x)|}{||w||_2} (h=s)$
• hard margin classification: 직선을 그었을 때 깔끔하게 두 group으로 분류되는 경우

linearly separable이 불가능한 경우?

• 직선을 아무리 그어도 두 그룹으로 분류되지 않는 경우 즉 hard margin classfication으로 해결되지 않는 경우
• Problem of hard margin classification
  • data 자체가 linearly separable한 경우에만 사용가능하다.
  • outliers에 민감
    • 오른쪽의 경우 분류는 가능하지만, margin을 최대화하기가 어려움 $\rarr$ 일반화가 어려움

위의 이슈 해결을 위해 좀 더 유연한 model을 사용
Soft margin classification

• 거리는 최대한으로 크게 하면서, margin에 대한 위반은 어느 정도 풀어주는 good balance를 찾는 것

Soft margin classification

• Scikit-Learn으로 hyperparameters를 명시함으로써 구현가능
  • 왼쪽의 경우, Large Margin을 가지고, Violation이 많아 정확도가 낮다. (soft)
  • 오른쪽의 경우, Fewer Margin을 가지고, Violation이 적어 정확도가 높다. (hard)

Nonlinear SVM Classification

Not linearly separable

• feature가 $x_1$ 1개
  • linear로는 분류 불가능
• feature가 $x_1$ 1개 $\rarr$ feature $x_2=(x_1)^2$ 추가
  • linearly separable
  • 특징을 추가함으로써 선형 분리가 가능해짐

Code

• polynomial feature을 가진 SVM을 사용하여 $make\_moon$ 예측
  • degree=3 로, 차수를 지정
  • Linear로 해결 불가일 경우, polynomial feature(차원 변환) 사용

---

SVM with kernel

SVM regression, Kernel method, Kernelized SVM

SVM Regression

SVM classification

: 두 classes간 가능한 가장 큰 거리를 적합하는 것 (optimal hyperplane 사용/hard, soft)

SVM regression

: 두 classes간 거리 안에 가능한 많은 instances를 적합하는 것 (classification과 반대)

• Example of SVM regression
  • $\epsilon-intensive$ : decision 자체는 $\epsilon$ 과 상관 없음

    

    • 왼쪽의 경우, violation은 적고, margin은 크고, accuracy가 작다. ($\epsilon$ = 1.5)
    • 오른쪽의 경우, violation은 크고, margin은 작고, accuracy가 크다. ($\epsilon$ = 0.5)

SVM Regression: Code

SVM Regression: for nonlinear data

• kernelized SVM을 사용하는 nonlinear regression의 예시
  • polynomial kernel
    • $C$ 가 작아지면서 violation은 증가하였고, 이는 곧 일반화 측면에서는 Good
• code
  • Not 'LinearSVR' class
  • 하지만 kernel trick을 지원하는 'SVR' class 사용
    • kernel에 주어지는 값에 따라 decision boundary가 다르게 그려진다.

Kernel Trick

공간변환은 ML의 핵심 연산

공간변환의 이유: 원래 특징 공간을 목적 달성에 더 유리한 새로운 공간으로 변환하는 작업 (예시)

공간변환을 위한 커널 기법$^{kernel \,method}$

커널기법이 필요한 이유

• 예: 원래 특징 공간 $L$을 새로운 특징 공간 $H$로 변환하여 선형에 가까운 데이터 분포를 만듦
• $H$는 매우 높은 차원이라 실제 변환은 불가능 $\rarr$ 커널 트릭을 사용하여 실제 변환하지 않고도 마치 변환을 하고 계산한 듯한 변환 효과를 가져옴 (실제로 변환하는 것 X)
  • 공간 변환을 통해 선형 분리 확보
  • 결과적으로는 선형 분리를 위해서 공간 변환을 사용

공간변환 추가설명

공간 변환 과정

• 원래 특징 벡터x($d$차원), 변환 후 벡터의 차원은 $q$(커널 기법에서는 보통 $q>>d$)
  $\Phi(x) = \Phi((x_1,x_2,\cdots,x_d)^T)=\big(\phi_1(x),\phi_2(x),\cdots,\phi_q(x)\big)^T$
• $\Phi(x)$: 변환함수(Transformation or 'mapping function')
• 공간변환 예시(2차원 $\rarr$ 2차원)
  • 본래 선형분리 불가능한 2차원
  • $\rarr$ 분리가능한 2차 공간으로 변환
    • (a): $\Phi$가 퍼셉트론
    • (b): $\Phi$가 RBF(Radial Basis Function)
• 공간변환 예시(2차원 $\rarr$ 3차원)
  • 변환함수 $\Phi$는 아래 식이라고 가정할 경우,
    $\Phi(x) = (\phi_1(x),\phi_2(x),\phi_3(x))^T = ({x_1}^2, {x_2}^2, \sqrt{2}x_1x_2)^T$
    ($\sqrt{2}x_1x_2$는 새 차원에 대한 연산)

Kernel Trick의 필요성

원 특징공간이 매우 고차원인 경우

• 예시
  • MNIST(손글씨): 28*28=784차원
  • ILSVRC: 224*224=50176차원
  • 커널 트릭을 이용해 연산을 좀 더 쉽게 수행

커널함수 K(x,z)** 정의

원래 특징 공간 $L$에 정의된 두 특징 벡터 $x$와 $z$에 대해 $K(x,z)=\Phi(x)\cdot\Phi(z)$ 인 변환함수 $\Phi$가 존재하면 $K(x,z)$를 커널함수라고 한다.

커널 트릭(커널 대치)

• $\Phi(x)$로 변환한 $H$ 공간에서 내적 연산을 원래 특징 공간 $L$에서 커널함수 계산으로 대치
  • 고차원에서 계산할 필요가 없음 (즉, 계산은 원래 특징 공간 차원에서 할 수 있음)
  • 동시에, '선형 분리 가능'이라는 고차원 공간의 좋은 특성을 이용 가능
• 제약 사항: $H$ 공간에서의 연산이 내적(dot product)으로 표현할 수 있어야 함

Example

• Second-degree polynomial transformation to 2D set
  변환 함수는 이와 같고, 변환 함수를 이용하면,
  $\phi(x)=\phi \begin{pmatrix}\begin{pmatrix} x_1\\ x_2 \end{pmatrix}\end{pmatrix} = \begin{pmatrix} {x_1}^2 \\ \sqrt{2}x_1x_2 \\ {x_2}^2 \end{pmatrix}$
  이를 통해, 2D가 아닌 3D로 변환된 vector를 얻을 수 있다.
• Second-degree polynomial mapping을 위한 kernel trick(변환하지 않아도 내적으로 표현되므로 계산 가능)
  • $\phi(a)^T\phi(b) = (a^Tb)^2=K(a,b)$
    : 현 차원에서도 커널함수를 안다면 차원 변환 필요없이도 연산이 가능
    이 때, $(a^Tb)^2=K(a,b)$를 second-degree polynomial kernel이라 한다.

Common kernels