본문 바로가기

머신러닝/분석 base

SVM (Support Vector Machine)

SVM이란

  • supervised learning algorithm
  • classification / regression 모두 가능하고 classification에 높은 성능을 보인다.
  • 탄탄한 수학적 이론으로 딥러닝 이전에 인기가 많았음
  • hyperplane(초평면)을 이용하여 카테고리를 나눈다.

 

SVM 모델

margin을 최대로 하는 분류 경계면을 찾는 문제와 같다.

 

 

 

SVC 수식

x(i)의 i번째 example의 방향 벡터를 u 벡터, decision boundary와 수직인 벡터를 v 벡터라고 했을 때, w˙v의 내적 길이에 따라 x가 x-인지 x+인지가 결정될 수 있다. 그 경계에 있는 실수를 b라고 했을 때 w˙u+b>=0이면 x는 x+, <0이면 x는 x-에 속한다고 할 수 있다. 

이번엔 decision boundary가 기점이 아닌 support vector의 경계에 대해 확실한 x+와 x-를 나눈다고 하면, w˙u+b>=1이면 x+, <=-1이면 x-이라고 할 수 있다. 즉, minus plane에 걸쳐진 x는 w˙u+b=-1을만족하고 plus plane에 걸쳐진 x는 w˙u+b=1을 만족하고, decision boundary에 걸쳐진 x는 w˙u+b=0을 만족한다고 할 수 있다.

여하튼 위와 같은 데이터에 대해 수학적 편리함을 위해 yi 변수를 추가한다.

i에 상관 없이 아래와 같은 식이 만족한다.

즉, i에 관게 없이 아래와 같은 식이 성립한다.

 

margin의 폭을 최대로 만들기

x+,x-를 각각 plus plane과 minus plane에 맞닿은 support vector라고 해보자. margin의 폭은 아래와 같이 나타낼 수 있다.

 

x+와 x-는 support vector이기 때문에 아래 식을 만족한다. 

i에 +와 -를 넣어서 식을 정리하면 width는 다음과 같이 정리된다.

 

우리는 width를 최대로 만들기 위해 다음과 같이 적을 수 있다. 

min (1/2)*||w||^2에 대한 제약 조건이 있는데, 제약조건을 고려하지 않고 최소화 하기 위해 라그랑즈 승수법을 이용한다.

L을 w,b에 대해 미분하여 0이 되는 w,b를 찾아야 하고 다음과 같은 식을 얻을 수 있다.

이 식을 L에 넣어보자.

결과적으로 다음과 같은 L을 maximize 해야 한다.

- L은 xi*xj에 의해서만 결정된다.

결론

1. α를 구하면 w 벡터를 구할 수 있다. 

2. α 값이 0이 아니라는 것은 해당 x 벡터가 경계선을 정하는 sample, 즉 support vector라는 뜻이다.

3. L(α) 식의 성질에 의해 SVM으로 구한 해는 항상 현재 SVM으로 구할 수 있는 최적의 해라는 것을 이론적으로 보장한다. => local minimum에 빠지지 않는다. 

=> support vector들로 정해진 decision boundary가 가장 최적의 boundary이며 새로운 샘플이 들어왔을 때 일반화를 가장 잘 할 수 있는 decision rule을 찾을 수 있는 것이다.

 

SVM의 종류

hard margin SVM

- 오분류를 허용하지 않는 SVM

- overfitting으로 인해 최적의 결정 경계를 구하지 못 할수도 있음

 

 

 

 

 

 

 

soft margin SVM

- 오분류를 허용하는 svm

- 대부분 어느 정도의 오분류를 인정하는 soft margin svm을 사용

 

 

 

 

 

 

 

margin과 오분류는 trade-off 관계임

margin이 높을수록 overfitting의 가능성이 적다.

 

 

 

 

C-SVM

슬랙 변수: 데이터의 완벽한 분리가 불가능 할 때, 선형적 분류를 위해 허용된 오차를 위한 변수

- 입실론(ε): 선형적 분류를 할 수 없을 때 분류를 위해 오차를 허용해야 함. 이 때 constraints를 완화하여 오차를 허용할 때 발생하는 변수

- overfitting을 피하기 위함

  • ε=0 : 정상적으로 분류됨
  • 0<ε<=1 : margin violation (margin 안에 들어온 경우)
  • ε>1 : 분류가 잘못된 경우 

C-SVM

- soft margin SVM

- overfitting을 막기 위해 ε만큼 panalty를 부과

- C는 regularization parameter로, C의 크기로 마진의 폭을 조절

  • C가 크면 ||w||가 극도로 작아야 하므로 train set에서 cost function이 0이 되어야 하므로 margin이 작아지고 overfitting의 위험성이 있다.
  • C가 작으면 ||w||가 커져도 되므로 margin이 커진다.

- 목적식이 아래와 같이 변한다.

 

 

데이터 분류가 비선형일 경우 kernel trick

data들이 선형적으로 분류되지 않을 땐 저차원공간에서 고차원공간으로의 mapping을 통해 선형적으로 분류할 수 있다.

즉, 선형적으로 분리가 가능한 (linear separable) 특징들에 대해 hyper-plane을 구하여 분류할 수 있는 것이다.

이렇게 저차원 공간에서는 선형적으로 분리가 불가능하지만 mapping을 통해 고차원 공간으로 보내서 SVM을 사용하여 선형적으로 분리하도록 하는 모델을 kernel trick이라고 하고 이 때 사용하는 함수를 kernel function이라고 한다. 

무한 차원을 가지는 공간으로 데이터를 보낼 수도 있는데, 매우 큰 차원이 가지는 표현력을 이용하면서 실제 decision boundary에 영향을 주는 support vector들은 적을 것이기 때문에 일반화를 잘 하는 모델을 세울 수 있다.

 ϕ로 x와 y벡터를 다른 차원으로 보내준다면 kernel 함수 K로 x와 y 벡터의 새로운 차원/공간에서의 내적값을 알 수 있다.

kernel function은 위처럼 여러가지가 가능하고 gaussian kernel이 가장 대표적이다. 

gaussian kernelRBF(Radial Basis Function)이라고도 한다. 

 

Gaussian kernel

Andrew Ng 교수님의 machine learning 강의에서 kernel function과 gaussian kernel에 대해 들은 수업 내용이다. 

gaussian kerne (rbf kernel)에서 σ(gamma)라는 hyper parameter가 등장한다.

gamma는 rbf kernel에서 하나의 데이터가 샘플이 영향력을 행사하는 거리를 나타낸다.

  • gamma가 크면 데이터가 행사하는 영향력의 거리가 짧아진다.
  • gamma가 작으면 데이터가 행사하는 영향력의 길이가 길어지고 overfitting의 위험성이 커진다.

- C가 커질수록, 혹은 gamma가 작아질수록 overfitting의 위험성이 커진다.

=> grid search로 가장 좋은 성능을 내는 매개변수의 조합을 찾을 수 있다. 

'머신러닝 > 분석 base' 카테고리의 다른 글

Resnet  (0) 2021.02.23
Boosting & Adaboost  (0) 2021.02.09
Bagging & Random Forest : Programming  (0) 2021.02.09
Bagging & Random Forest  (0) 2021.02.09
SVM: programming  (0) 2021.02.08