[ISLR] 서포트 벡터 머신(SVM, Support Vector Machine)

서포트 벡터 머신(Support Vector Machine)

 서포트 벡터 머신(SVM, support vector machine)은 서포트 벡터 분류기(support vector classifier)의 확장으로, 커널(kernel)을 사용하여 변수 공간을 확장한 결과입니다. 변수와 출력값 사이의 비선형 관계를 설명하기 위하여 변수 공간을 확장해야 하는데, SVM은 커널을 사용하여 효율적인 연산량으로 변수 공간을 확장한 방법입니다.

 

 서포트 벡터 분류기 문제에 대한 해는 관측값들의 내적만이 관련이 있습니다. 두 관측치 사이의 내적은 다음과 같이 주어집니다.

 

 

 선형 서포트 벡터 분류기(Linear support vector classifier)는 다음과 같이 나타낼 수 있습니다.

 

 

 여기서 n개의 파라미터 $\alpha _i, i = 1, ... , n$이 존재하며 훈련 관측치 하나에 한개씩 입니다.

 

 이 파라미터 $\alpha _1, ..., \alpha _n$와 $\beta _0$을 추정하기 위하여 훈련 관측치들의 모든 쌍 사이의 ${n \choose 2}$개의 내적 $\left\langle x, x_i \right\rangle$ 이 필요합니다.

 

 이 말은 함수 f(x)를 추정하기 위하여 새로운 포인트 x와 훈련 포인트 $x_i$ 사이의 내적을 계산해야 합니다. 하지만 $\alpha _i$는 서포트 벡터에 대해서만 nonzero 입니다. 만약 훈련 관측치가 서포트 벡터가 아니라면 $\alpha _i$는 0입니다. 따라서 서포트 벡터에 대한 인덱스 모임을 S로 표현하면 다음과 같이 식을 작성할 수 있습니다.

 

 

 이렇게 표현함으로써 항이 훨씬 더 줄었습니다.

 

 이 선형 분류기 f(x)를 나타내고 계수를 계산하는데에 필요한 모든 것은 내적입니다.

 

 내적을 다음과 같은 일반화 형태로 나타낼 수 있습니다. 

 

 

 여기서 K는 kernel이라고 언급될 어떤 함수입니다. 커널은 두 관측치의 유사도를 수량화하는 함수입니다. 예를 들어 커널은 서포트 벡터 분류기를 나타내는 다음과 같은 형태를 취할 수 있습니다.

 

 

 위 식은 선형 커널로 알려져 있으며 서포트 벡터 분류기는 변수들에 선형이기 때문입니다. 선형 커널은 피어슨 상관(Pearson correlation)을 사용하여 관측치 쌍의 유사도를 수량화 합니다. 다른 형태의 커널도 존재합니다.

 

 

 이 커널은 차수가 d인 다항식 커널입니다. 선형 커널 대신에 다항식 커널을 사용하여 서포트 벡터 분류기는 더 유연한 결정 경계를 생성할 수 있습니다. 이는 원래의 변수 공간이 아니라 차수 d인 다항식들이 관련되어 있는 고차원 공간에서 서포트 벡터 분류기를 적합합니다.

 

 이와 같이 비선형 커널과 결합된 서포트 벡터 분류기를 서포트 벡터 머신이라고 합니다. 이 비선형 함수는 다음과 같은 형태를 갖습니다.

 

 

 

 위 그림에서 왼쪽 그림은 차수 3을 지닌 다항식 커널을 지닌 SVM이 비선형 데이터에 적용된 결과입니다.

 

 또 다른 비선형 커널로는 방사 커널(radial kernel)이 있습니다.

 

 

 위 그림에서 오른쪽 그림은 방사 커널을 지닌 SVM을 비선형 데이터에 적용한 예 입니다. 두 클래스를 잘 분류하고 있습니다.

 

 방사형 터널은 얼마나 잘 작동할까요? 만약 test observation이 training observation과 멀리 떨어져 있다면 Euclidean distance는 매우 커지게 되고 방사 커널값은 매우 작아질 것입니다. 이는 $x_i$가 f($x^*$)에 사실상 아무 역할도 하지 않을 것입니다. 이는 test observation에 가까이 존재하는 train observation만이 test의 class 할당에 영향을 주므로 방사 커널이 매우 국소적인 방식으로 작동한다는 것을 의미합니다.

 

 원래 변수 공간을 단순히 확장하는 것보다 kernel을 사용하는 것의 이점은 무엇일 까요? 한 가지 장점은 연산량입니다. 커널을 사용하면 n(n-1)/2 개의 서로 다른 모든 쌍에 대해 단지 커널만 계산하면 됩니다.

 

---

참고자료 및 그림 출처

Gareth James의 An Introduction to Statistical Learning