SVM

1. Support Vector Machines(SVM)

- 두 클래스 사이의 마진을 최대화하면서 동시에 support vectors만을 이용해 결정 경계를 정의

- a를 보면 여러 개의 hyperplane 후보가 있음

- b에서 가운데 굵은 선이 실제로 선택된 최적의 마진 경계. 

- b에서 원으로 크게 표시된 점들은 서포트 벡터. 마진에 가장 가까운 데이터 포인트들

 

 

- 따라서 max margin = min w^Tw

 

 

- VC 차원 : 분류기가 몇 개의 점을 어떤 라벨링으로든 분리할 수 있는지를 나타냄

- 예를들어 아래와 같은 경우 마지막 경우는 모든 라벨링을 분리할 수 없으므로 VC는 3

- VC 차원이 클수록 테스트 에러가 커질 수 있음

- 마진 γ가 클수록, 즉 분류 경계로부터 데이터가 멀리 떨어져 있을수록 모델의 복잡도(VCD)가 낮아짐

→ 마진을 키우면 일반화 성능이 좋아짐

 

- 마진이 최소 1이 되도록 하는 제약식

tn은 1또는 -1

 

 

2. SVM의 Primal Problem

- 마진을 최대화하는 것은 곧 ||w||를 최소화하는 것

- decision boundary는 wTx+b=0이므로 최적화 변수는 w, b

- 즉 Primal 문제는 w,b에 대해 최소화하는 문제야.

- Primal Problem을 직접 풀기 어렵기 때문에, 이를 해결하기 위해 라그랑지안 함수를 도입

Lagrangian Function

- w,b를 최소화하려면 w와 b에 대해 미분하여 0으로 만들기

 

 

 

3. SVM의 Dual Problem

- Dual function은 Lagrangian에서 w, b에 대해 최소화한 후, 그 값을 a 에 대해 최대화하는 문제

- 위에서 미분하여 유도한 식을 라그랑지안 함수에 대입하면 아래와같이 나옴

 

- 이제 a에 대해 최대화하기

- 최대화한 a를 구한 후 결정 함수 y(x)에 대입

 

 

4. 절편 b 구하기

- 조건 tn​y(xn​) = 1

- 양 변에 tn을 곱함(tn^2 = 1)

- support vector의 평균을 사용해야 하므로 |S|로 나눠줌

- 위의 과정을 정리하면 아래와 같은 b가 나옴

 

 

 

5. Support Vectors 정리

- KKT 조건:

  1) Lagrange multiplier 조건 : an >= 0

  2) Original constraint 조건 : tn​y(xn​) −1 ≥ 0

  3) Complementary slackness : αn​(tn​y(xn​) − 1) = 0

- 우리가 원하는 건 tn​y(xn​) − 1 = 1이라 결국 an > 0

- Support Vectors:  an > 0 인 데이터 포인트들

- 결정 경계에 직접 영향을 주는 점들

- SVM의 최종 예측 함수는 다음과 같음

- Decision Rule : if y(xtest) > 0 ⇒ Class 1 else ⇒ Class 0

 

 

 

6. Kernel Trick

- 커널 트릭은 데이터를 고차원으로 올리지 않고도 고차원 공간에서 계산한 것과 동일한 결과를 얻는 테크닉

- x^Ty 같은 내적을 계산하는 대신 k(x, y)로 대체하는 게 커널 트릭

- ϕ: input space → feature space 로 매핑하는 함수

- 기존 SVM dual form의 xnTxm 자리에 커널 k(xn, xm)을 넣으면 고차원 특징 공간에서 분류 가능