Kernel Support Vector Machines

Kernel Support Vector Machines 커널 서포트 벡터머신

SVM은 입력 데이터(Input)에서 단순한 초평면(Hyperplane)으로 정의되지 않는 더 복잡한 모델을 만들 수 있도록 확장한 것으로 쉽게 말해 일반적인 특성들은 선형적으로 분류가 되지 않는 경우가 많다. 이에 따라, 곡선과 같은 결정경계 모델이 필요해 탄생한 것.

Regression과 Classification 모두 가능하지만 분류(SVC)만 다룰예정. (SVR에서도 같은 개념을 사용함.)

*초평면이란 어떤 R^n공간에서 이 공간의 한점을 통과하는 해집합이다. 해집합이 R^n공간 안에서 n-1차원을 형성한다.

초평면 자체는 R^n의 subspace를 보장하진 않는다. 

a1x1 + a2x2 +...+ anxn +b = 0 임의의 a에 대해 x는 R^n공간에서 모든 초평면들이 형성하는 해집합을 의미함.(n-1차원)

쉽게 생각하면, 3차원에서 초평면이 2차원 면, 2차원에선 1차원 점으로, 하나의 초평면은 해당 공간을 두 영역으로 분리해준다. 

---

Linear Model과 unlinear feature들

앞서 봤던 그림으로, 직선과 hyperplane은 유연성이 떨어져, Low Dimension의 data set에는 Linear Model이 매우 제한적

이에 따라, linear model을 유연하게 하기위해 feature간의 곱이나 feature들의 거듭제곱하는 식의 새로운 특성(unlinear)을 도입

앞절에서 트리로 구분했던 위의 데이터셋은 선형모델로 구분하기엔 무리가 따른다. 분류를 위한 선형모델은 직선으로만 데이터 포인트를 구분 나누기 때문이다.

이 때문에, 특성1^2의 새로운 특성을 추가해 보겠다.

이는 3차원 공간의 평면을 통해 두클래스로 구분이 된다. 다시 원래 차원의 데이터로 투영하게 되면 (위에서 쳐다본 상황)

선형 SVM모델이 선형이 아닌것으로 나타나게 된다.

---

Kernel Method

앞서 본 방식은 unlinear feature(특성1^2)를 도입하여 linear model을 강화했다.

하지만, 많은 feature를 기준없이 추가하면 연산 비용이 커진다. kernel method는 수학적 개념을 이용해 새로운 feature를 만들지 않고, 고차원 분류기를 학습시킨다.

실제 데이터를 확장하지 않고 확장된 특성에 대한 데이터 포인트들의 거리(스칼라곱)을 계산한다.

SVM에서 데이터를 고차원 공간에 매핑하는 방법은 크게 2가지이다.

1. 원래 특성의 가능한 조합을 지정된 차수까지 모두 계산( ex) 특성1^2*특성2^5)하는 다항식 커널
2. 가우시안 커널로도 불리는 RBF(radical basis function)커널
• 차원이 무한한 feature space에 매핑하는 것으로, 모든 차수의 모든 다항식을 고려한다고 생각하면 편하다. (1번의 다항식 커널의 경우 일부 지정된 차수 까지만 계산하고 RBF는 이를 무한하게 확장)

*커널의 자세한 설명 참고

http://blog.daum.net/tlos6733/136

---

SVM의 이해

학습이 진행되는 동안 SVM은 각 훈련 데이터 포인트가 두 클래스 사이의 결정 경계를 구분하는 데 얼마나 중요한지를 학습한다.

일반적으로 일부의 훈련 데이터가 결정 경계를 만드는 데 도움을 준다.

->두 클래스 사이의 경계에 위치한 데이터 포인트들

->이를 Support Vector 서포트 벡터라고 한다.

방식

h(x)

새로운 데이터 포인트 예측을 위해 각 SV와의 거리를 측정

분류 결정은 SV까지의 거리에 기반하며 SV의 중요도는 훈련 과정에서 학습

데이터 포인트 사이의 거리 산정

가우시안 커널 (RBF)를 사용한다. 

거리를 의미하는 ||x1-x2||^2는 유클리디안 거리 (L2 distance basis와 상관없는 절대적인 거리) 

γ(감마)는 가우시안 커널의 폭을 제어하는 매개변수이다.

결정경계가 비선형 이며, 굵은 점들이 SV이다.

---

Hyper-parameter 튜닝

γ

γ는 가우시안 커널 폭의 역수에 해당한다. 즉, 하나의 training sample이 미치는 영향의 범위를 결정한다.

γ가 작으면 넓은 영역을 의미하고, 크면 영향을 미치는 범위가 제한적이다.

커널의 반경이 클수록 traing sample의 영향 범위가 커진다.

*γ가 0보다 커야하므로 가우시안 커널 함수값은 e^0 ~ e^-∞이므로, 1~0사이의 범위 값이다. γ가 작을수록 1에 가까ㅏ워져 데이터 포인트의 영향범위가 커진다.

C

linear model과 유사한 Regulation term이다. 각 포인트의 중요도를 제한(overfit 방지)한다.

γ가 커질 수록( 왼쪽에서 오른쪽 방향 ) 각 데이터 포인트의 영향 범위가 줄어든다(가우시안 커널의 반경이 줄어듬).

결국엔 많은 포인트들이 큰 영향을 미쳐, 결정 경계를 하나의 데이터에도 민감하게 고려하여 생성한다.

이는 모델의 복잡도가 올라가 부드러운 경계에서 복잡한 경계로 바뀌게 된다.

C가 작은 값 ( 위의 행 그림 3개 )일때 각 데이터 포인트의 제약이 큰 모델을 만들고 각 데이터 포인트는 작은 영향력을 갖는다.

C가 커질 수록 각 포인트가 모델의 영향력을 크게 주어 결정 경계를 휘어서 정확하게 분류한다.

C와 γ 모두 커질수록 복잡한 모델을 만든다.

따라서, C와 γ를 함께 조정해야 한다.

RBF커널에서 default로 설정되는 hyper-parameter는 C=1, γ = 1/n_features.

---

SVM을 필요한 데이터 pre-processing

유방암 데이터셋의 특성을 검사해보면,

특성들의 크기 단위가 천차 만별이다 특히나 4번 feature의 비해 5번 feature는 거의 없는 것이나 다름없다. 이로인해 도출된 가설함수에 대한 training-set 정확도는 1.00이고, test-set 정확도는 약 0.63이 나왔다.

직관적으로 보면, 4번 feature같은 상대적으로 전체적인 크기가 큰 특성들이 예측에 큰 영향을 미치는 것이다. 하지만, 특성 전체적인 크기가 중요도와 비례하는 것은 아니다. 만약 단위를 바꾼다고하면, 결과는 다시 바뀌므로 이는 절대적인 예측이 될 수 없다.

따라서, 특성값의 범위가 비슷해지도록 조정하는 것이 해결책 중 하나가 될 수 있다.

그중에서도, 모든 feature를 0~1로 만드는 것이 가장 많이 사용되는 방식이다. ( (X-min(X))/(max(X)-min(X)) ) mean normalization

---

장단점과 Parameter

장점

• 강력한 모델로 다양한 데이터셋에서 잘 작동
• 특성이 몇 개 안되더라도 복잡한 결정 경계를 만들 수 있다.
• 저차원과 고차원의 데이터(특성의 적고 많음)에 상관없이 잘 작동

단점

• 샘플이 많을 때 잘 맞지 않음
• 특히나, 10,000개 정도의 샘플은 괜찮지만 100,000개 이상의 데이터는 속도와 메모리상 어려움이 있다.
• 데이터 전처리와 hyper-parameter에 신경을 많이 써야 한다.
• 분석이 어렵다.

장점보다 단점이 명확하여 RF나 GB같은 (전처리가 거의 또는 전혀 필요없는)트리 기반 모델을 앱에서 많이 사용한다.

하지만, 모든 특성이 비슷한 단위이고(예를 들면 모든 값이 픽셀의 컬러 강도) 스케일이 비슷하면 SVM을 시도할만 하다.

Hyper-parameter

• regulation term의 C
• 어떤 커널을 사용할지와 각 커널에 따른 매개변수
• RBF 커널은 가우시안 커널 폭의 역수인 γ매개변수도 갖는다.

γ와 C 모두 모델의 복잡도를 조정하며 둘 다 큰 값이 더 복잡한 모델 사용.

따라서, 연관성이 많은 C와 γ는 함께 조정하는 것이 바람직하다.