서포트 벡터 머신

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
선형 SVM이 두 자료(흰색 원, 검은색 원)을 직선으로 분리하고 있다.

서포트 벡터 머신(support vector machine, SVM)은 지도 학습에서 사용되는 방법으로, 주어진 자료에 대해서 그 자료들을 분리하는 초평면 중에서, 자료들과 가장 거리가 먼 초평면을 찾는 방법이다.

이 기법은 비선형 분류에서도 커널 트릭을 사용하여 적용할 수 있다.

SVM의 개념적 특징[편집]

다음과 같은 데이터집합 D가 주어졌다고 생각해보자.

\mathcal{D} = \{ (\mathbf{x}_i, c_i)|\mathbf{x}_i \in \mathbb{R}^p, c_i \in \{-1,1\}\}_{i=1}^n

ci 는 1이나 -1의 값을 갖는 변수로 \mathbf{x}_i 가 속한 클래스를 의미하며, \mathbf{x}_i p차원 실수벡터이다.

H3은 두 클래스의 점들을 제대로 분류하고 있지 않다. H1과 H2는 두 클래스의 점들을 분류하는데, H2가 H1보다 더 큰 마진을 갖고 분류하는 것을 확인할 수 있다.

신경망을 포함하여 많은 학습 알고리즘들은, 이러한 학습데이터가 주어졌을때 c_i=1인 점들과 c_i=-1인 점들을 분리하는 hyperplane을 찾아내는 것이 공통의 목표인데, SVM이 다른 알고리즘과 차별화되는 특징은 단지 점들을 분리하는 hyperplane을 찾는 것으로 끝나는 것이 아니라, 점들을 분리할 수 있는 수많은 후보평면들 가운데 마진이 최대가 되는(maximum-margin) hyperplane을 찾는다는 것이다. 여기서 margin이란 hyperplane으로부터 각 점들에 이르는 거리의 최솟값을 말하는데, 이 margin을 최대로 하면서 점들을 두 클래스로 분류하려면, 결국 클래스1에 속하는 점들과의 거리 중 최솟값과 클래스 -1에 속하는 점들과의 거리 중 최솟값이 같도록 hyperplane이 위치해야 하며, 이러한 hyperplane을 maximum-margin hyperplane이라고 한다. 결론적으로 SVM은 두 클래스에 속해있는 점들을 분류하는 수많은 hyperplane들 중, 최대한 두 클래스의 점들과 거리를 유지하는 것을 찾아내는 형락 알고리즘이라 할 수 있다.


선형 SVM[편집]

주어진 학습용 데이터 집합 D(N 개의 점으로 이루어진 집합)를 다음과 같이 정의해보자.

\mathcal{D} = \{ (\mathbf{x}_i, y_i)|\mathbf{x}_i \in \mathbb{R}^p, y_i \in \{-1,1\}\}_{i=1}^n

\mathbf{x}_i 는 p차원의 실수 벡터이고 , y_i\mathbf{x}_i 가 어떤 클래스에 속해있는지를 나타내는 값으로 1 혹은 -1의 값을 가진다.

위의 학습용 데이터 집합이 y_i값에 따라 선형적으로 분리될 수 있을 때, 데이터 집합을 분리하는 것을 초평면(hyperplane)이라 하며 다음의 조건을 만족하는 점 X의 집합으로 나타낼 수 있다.

\mathbf{w}\cdot\mathbf{x} - b=0.\,

\cdot 은 내적 연산자이고, {\mathbf{w}}은 초평면의 법선 벡터이다.

주어진 초평면의 support vector({\mathbf{X}}+, {\mathbf{X}}-)는 다음과 같이 정의된다.

{\mathbf{X}}+ : y_i=+1의 데이터중에서 초평면과 가장 가까운 데이터
{\mathbf{X}}- : y_i=-1의 데이터중에서 초평면과 가장 가까운 데이터

주어진 초평면과 같은 법선벡터를 가지면서 {\mathbf{X}}+ 를 지나는 초평면은

\mathbf{w}\cdot\mathbf{x} - b=+1\,

으로 나타낼 수 있고 비슷한 방식으로 {\mathbf{X}}- 를 지나는 초평면은

\mathbf{w}\cdot\mathbf{x} - b=-1\,

이와 같이 나타낸다.

초평면의 마진(margin)은 각 support vector를 지나는 초평면 사이의 거리를 의미한다.
기하학적으로 두 초평면 사이의 거리 즉, 마진을 구하면 \tfrac{b}{\|\mathbf{w}\|}라는 것을 알 수 있으며 서포트벡터머신은 마진을 최대로 만드는 알고리즘이다.

서포트벡터를 지나는 초평면 사이엔 데이터 포인트가 존재하지 않아야 하므로 다음과 같은 식이 성립한다.

y_i=+1\mathbf{x}_i 에 대해서 \mathbf{w}\cdot\mathbf{x}_i - b \ge+1\,
y_i=-1\mathbf{x}_i 에 대해서 \mathbf{w}\cdot\mathbf{x}_i - b \le-1\,

위 두 식은 아래와 같은 식으로 나타낼 수 있다.

y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,\text{ for all } 1 \le i \le n.

초평면의 조건을 따르며 마진의 최댓값을 구하고자 하는 서포트 벡터 머신 문제는 다음과 같은 최적화 문제로 표현할 수 있다.

y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,\text{ for all } 1 \le i \le n. 의 조건을 만족하는 (\mathbf{w}, b)에 대해서 \operatorname*{arg\,min}_w{\|\mathbf{w}\|}를 구하라

소프트 마진[편집]

1995년에 Corinna Cortes와 Vladimir N. Vapnik은 잘못 분류된 자료들을 허용하는 변형된 최대 마진 아이디어를 제안했다. 만약 “네” 또는 “아니오”라는 결과를 내야하는 자료들을 분할하는 초평면이 존재하지 않는다고 하자. 그러면 소프트 마진 방법은 여전히 가장 가까이 위치해 있는 깨끗하게 분리되는 자료들의 거리를 최대화하면서, 주어진 자료들을 가능한 한 깨끗하게 분리하는 초평면을 찾을 것이다. 이 방법은 음수가 아닌 느슨한 변수(slack variables) \xi_i를 이용하는데, 이 변수는 자료 x_i가 잘못 분류된 정도를 측정한다.

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i \quad 1 \le i \le n. \quad\quad(2)

그러면 목적함수는 0이 아닌 \xi_i에 대해 페널티를 부과하는 함수에 의해서 증가된다. 그에 따른 최적화는 마진을 크게 하는 것과 에러에 대한 페널티를 작게 하는 것의 균형을 맞추는 것이 된다. 만약 페널티를 부과하는 함수가 선형이라면, 최적화 문제는 다음과 같이 된다.

\arg\min_{\mathbf{w},\mathbf{\xi}, b } \left\{\frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \right\}

아래의 조건 하에서 (어떠한  i=1,\dots n에 대해서)

 y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i, ~~~~\xi_i \ge 0

다변수 적응 회귀 스플라인(Multivariate Adaptive Regression Splines, MARS)에서와 같이 경첩 함수(hinge function) 표기법을 이용하면, 이 최적화 문제는 다음과 같이 쓰일 수 있다.

[1-y_i(w \cdot x_i + b)]_+ = [\xi_i]_+ = \xi_i, \quad \lambda = 1/2C 일 때,
 \sum_i [1-y_i(w \cdot x_i + b)]_+ + \lambda \|w\|^2

(2)에서의 제약조건은 목적함수에서 \|\mathbf{w}\|를 최소화하는 것과 함께 라그랑주 승수법을 이용하여 위에서와 마찬가지로 해결될 수 있다. 그러면 다음의 문제를 해결해야 한다.

 \alpha_i, \beta_i \ge 0일 때,
\arg\min_{\mathbf{w},\mathbf{\xi}, b } \max_{\boldsymbol{\alpha},\boldsymbol{\beta} }
\left \{ \frac{1}{2}\|\mathbf{w}\|^2
+C \sum_{i=1}^n \xi_i
- \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b) -1 + \xi_i]}
- \sum_{i=1}^{n} \beta_i \xi_i \right \}
소프트 마진 서포트 벡터 머신의 결과에 대한 예시

듀얼 형식[편집]

다음의 두 조건 (어떠한 i = 1, \dots, n에 대해서)

0 \leq \alpha_i \leq C,\,

 \sum_{i=1}^n \alpha_i y_i = 0.

하에, 다음의 식을 최대화한다 (\alpha_i에 대해서)

\tilde{L}(\mathbf{\alpha})=\sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j k(\mathbf{x}_i,\mathbf{x}_j)

선형 페널티 함수의 핵심 장점은 상수 C가 오직 라그랑주 승수법의 추가적인 제약조건에 등장함으로써, 듀얼 문제에서는 느슨한 변수가 사라진다는 점이다. 위의 공식화와 이것의 실제상황에서 미치는 큰 영향에 대해서 Cortes와 Vapnik은 2008년에 ACM Paris Kanellakis Award를 수상하였다. 비선형 페널티 함수들도 특히 분류기에서 이상치의 효과를 줄이는데 사용되고 있다. 그러나 이를 사용하는데 주의를 기울이지 않는다면 문제는 볼록하지 않게 되고, 그러면 이는 전역해를 찾는데 상당히 어려운 문제가 된다.