SVM (Support Vector Machine)
- class 별 데이터를 가장 잘 구분하는 최적의 하이퍼플레인(Hyperplane)을 찾는 알고리즘
- 하이퍼플레인 (Hyperplane)
- 데이터가 분포되어 있는 n차원 피처 공간을 두 공간으로 나누는 n-1차원의 평면.
- ex
- 2차원 피처 공간에서 하이퍼플레인은 '선' (line)
- 3차원 피처 공간에서 하이퍼플레인은 '형면' (surface)
- 하이퍼플레인에 의해 양분된 두 공간 내에 있는 가장 가까운 데이터 포인트(벡터) 간의 거리(Margin)가 최대인 상태
- 가장 가까운 데이터 포인터 : 서포트 벡터(Support Vector)
o와 x를 나누는 hyperplane을 찾는 과정.
작동 알고리즘
- 단계 1 : 하이퍼플레인 표현하기
- 하이퍼플레인도 부분공간으로 생각하면 된다. (벡터들의 집합)
- 2차원 공간의 하이퍼플레인을 생각했을 때, 하이퍼플레인(line)이 포함하는 벡터(데이터 포인트)들은 다음과 같은 식으로 정의될 수 있다.
- w*x + b = 0
- 흔히 선을 표현할 때 사용하는 일차식 ax + by + c = 0을 벡터로 표현했다고 생각하면 된다.
- 최적의 하이퍼플레인 조건1
- 두 클래스의 데이터들을 양분하기 위해서 하이퍼플레인은 아래의 조건을 만족해야 한다.
- 2개의 클래스 중 한 쪽에 속한 모든 데이터 x에 대해 wx + b > 0
- 2개의 클래스 중 다른 쪽에 속한 모든 데이터 x에 대해 wx + b < 0
- 하지만, 이 조건을 만족하는 하이퍼플레인은 무수히 많을 수 있다 => 조건이 더 필요함!
A도, B도, C도 모두 양분은 함..
- 단계 2 : 서포트 벡터 표현하기
- 두 공간 내 가장 가까운 벡터들 사이의 거리가 멀면 멀수록 두 공간을 잘 가르는 하이퍼플레인일 것
- 즉, Margin이 크면 클수록 좋은 하이퍼플레인
- 이를 수학적으로 표현해보면?
Margin을 크게 하자!!
- Decision Hyperplane
- 두 공간을 양분하는 하이퍼플레인
w*x + b = 0
- Positive Hyperplane
- decision hyperplane보다 큰 곳에서 평행하는 하이퍼플레인
- 위치한 공간에서 decision hyperplane과 가장 가까운 데이터를 포함.
w*x_(p) + b = 1
- Negative Hyperplane
- decision hyperplane보다 작은 곳에서 평행하는 하이퍼플레인
- 위치한 공간에서 decision hyperplane과 가장 가까운 데이터를 포함.
w*x_(n) + b = -1
- 이 때, 1과 -1이라는 숫자는 계산 편의상 합이 0이 되게 하기 위해 사용하는 숫자로, b로 조정 가능하기 때문에 사실 어떤 수여도 상관없다.
- positive/negative hyperplane 내의 데이터가 서포트 벡터가 된다!
- 단계 3 : Margin 표현하기
- positive hyperplane의 점 x_p에서 직선 wx + b = 0 사이의 거리 d_p
- negative hyperplane의 점 x_n에서 직선 wx+b = 0 사이의 거리 d_n
- 결과적으로 margin은 아래와 같이 표현 가능하다.
- 최적의 하이퍼플레인 조건2
- 서포트 벡터 사이의 거리가 최대가 되도록 하는 ||w||가 최소인 하이퍼플레인
- 단계 4 : 최적의 하이퍼플레인 찾기
- 조건1 : 데이터 양분
- 2개의 클래스 중 한 쪽에 속한 모든 데이터 x에 대해 wx + b > 0
- 2개의 클래스 중 다른 쪽에 속한 모든 데이터 x에 대해 wx + b < 0
- 조건 1을 positive/negative hyperplane 표현으로 다시 바꿔보면
- wx_i + b >= 1 (if y_i = 1)
- wx_i + b <= -1 (if y_i = -1)
- x_i와 y_i는 i번째 데이터의 피처와 클래스 레이블을 표현.
- 2개의 식을 하나로 정리하면
- 즉, 조건 1은 모든 학습 데이터 (x_i, y_i)에 대하여 y_i * (wx_i + b) >= 1을 만족.
- 조건2 : 최대 Margin
- 이 조건들을 만족하는 하이퍼플레인을 찾는 것이 SVM의 학습 과정.
- 하지만! 현실적으로 조건1에 대해서 모든 학습 데이터를 모두 양분하는 선형 식을 찾기는 어렵다. 완화된 조건으로 수정이 필요.
- 완화된 조건
- 학습 단계에서 현재 선형식으로 학습 데이터를 분류해봤을 때, 올바르게 분류(양분)되지 못한 경우를 다음과 같이 수치화한다.
- 이를 Error라 하기도 하고, 힌지 손실 (Hinge Loss)라고 하기도 한다.
- Error가 0이라면 이상적이겠지만, 실질적으로 존재할 수 있기 때문에 학습 과정에서 Error가 최소가 되게 하는 조건을 추가하면 좋다.
분류가 안되면 그만큼의 차이를 계산.
- 최종 조건 (완화된 데이터 양분 + 최대 Margin)
- 파라미터 C
- Margin과 Error 중 어떤 것을 더 중요하게 볼 것인지 결정하는 하이퍼 파라미터
- C가 크면 Error 값을 더 고려, 학습 데이터에 오버피팅 이슈가 있을수도 있음
- C가 작으면 Error 값을 거의 고려 안함, 학습 데이터에 대한 정확도가 떨어질 수 있음.
- C로 모델의 바이어스와 분산 사이 밸런스를 결정한다고 볼 수 있다.
- 이러한 하이퍼 파라미터를 찾는 과정을 '모델 튜닝'이라고 하며 다른 파라미터 상황에서 모델의 성능으로 최적의 파라미터를 결정.
- 단계 5 : 학습 후 예측
- 학습을 통해 최적의 w와 b를 찾아 wx+b 식을 완성했다면
- 새로운 x'가 주어졌을 때 x'의 레이블 y'는 다음과 같이 결정.
SVM : 다중 클래스
- 앞서 봤던 SVM 모델은 데이터를 "양분"하는 하이퍼플레인을 찾기 때문에 이진 분류에 대한 모델이다.
- 만약 클래스가 3개 이상인 다중 클래스 분류 문제에 대해서는 SVM을 사용할 수 없을까?
- 사용할 수 있다! 각 클래스 별로 "해당 클래스"와 "그 외 다른 클래스들"을 가르는 하이퍼플레인을 찾는다고 생각하면 된다.
- 일대다 방법
- K-클래스 문제에 대해 K개의 (서로 다른) 이진 SVM 분류기를 만들어낸다.
- K번째 분류기의 경우 K번째 클래스를 양성 케이스로 처리하고 나머지 K-1개의 클래스는 음성 케이스로 처리한다.
- 이를 학습하여 하이퍼플레인 W_k * x + b_k = 0을 찾는다.
- 학습 후 x'의 클래스 y'는 이진 분류기의 W_k * x + b_k의 값이 가장 큰 값을 가지는 클래스 K를 x'의 클래스로 결정한다.
- y' = argmax_(k=1, ..., K) ( W_k * x + b_k )
일대다 방법의 과정.
- 일대일 방법
- 클래스의 각 쌍을 구분하는 이진 SVM 분류기를 생성
- 쌍 비교 방법 (Pairwise comparison)
- K개의 클래스가 있으면 K(K-1)/2개 분류기 생성
- 학습 후, 새로운 데이터 x'를 분류할 때는 모든 이진 분류기에 데이터를 넣고 결과를 뽑아보고 가장 많이 예측된 클래스를 x'의 최종 예측 클래스 y'로 결정한다.
일대일 방법의 과정.
- 일대다 vs. 일대일
- 일대일 방법은 일대다 방법보다 분류기가 훨씬 더 많이 만들어진다.
- 일대다 방법은 한 분류기를 학습시킬 때 학습데이터로 전체 데이터를 사용하지만, 일대일 방법은 대상이 되는 두 클래스에 속하는 데이터만 사용한다.
- 한 분류기를 학습하는 상황에서는 일대일이 메모리 활용, 컴퓨팅 계산 효율이 더 좋다.
Kernel
- default : linear
- 비선형 문제 (Non-Linear Problem)
- 아래와 같이 어떤 데이터들은 선형 식으로 완벼하게 잘 분류할 수 없다.
- 선형으로 모델링할 수 없는 문제를 비선형 문제라고 한다.
선형으로 해결할 수 없다.
- SVM과 비선형 문제
- 기본적으로 SVM은 선형식으로 표현되는 하이퍼플레인에 기반하고 있어 비선형 문제에 적합하지 않다.
- 그러나, 선형으로 양분할 수 있도록 피처 공간을 변환(Transform)한 뒤에 SVM을 적용하는 것이 가능하다.
- 고차원 피처 공간으로 변환한다?
- 원의 모양을 linear하게 변환할 수 있다.
피처 공간 transform
| |
커널 함수 |
| 다항식 커널 |
|
| RBF 커널 |
|
| 하이퍼볼릭 탄젠트 커널 |
|
- RBF Kernel (Radial Basis Function)
- 대표적인 SVM 커널이며, 가우시안 커널이라고도 불린다.
- RBF Kernel은 파라미터 감마를 가지는데, 이 값에 따라서 변환 결과를 조절할 수 있다.
- 감마 값이 크면 학습 데이터를 정확히 맞추는 변환 함수가 만들어져서 오버피팅 위험이 높아진다.
- 감마 값이 작으면 학습 데이터를 덜 정확히 맞추도록 변환 함수가 만들어져서 학습 데이터를 잘 대변하지 못할 수도 있다.
- Gamma for RBF Kernel
- gamma 값에 따라 어떤 변화가 있을까?
- gamma가 클수록 decision graph가 작아지고 세밀해진다.
- Linear Kernel과 RBF Kernel
- 기본적으로는 RBF Kernel의 사용을 추천하나, 아래와 같은 가이드라인을 참고할 수 있다.
