서포트 벡터 머신(Support Vector Machine; SVM)은 선형이나 비선형 분류, 회귀, 이상치 탐색 등 다양한 목적으로 활용 가능한 모형이다. 이 글에서는 분류 문제에 초점을 맞추고 서포트 벡터 머신의 작동 원리에 대해 설명한다.
서포트 벡터 머신은 '결정 경계(Decision Boundary)'라는 기준 선을 정의함으로써 클래스를 분류하는 이진 분류 모형이다. 이때 결정 경계에 위치한 샘플이 바로 '서포트 벡터(Support Vector)'이다.
예를 들어, 2차원 상에 데이터가 존재한다고 하자. 왼쪽 그래프를 보면 두 개의 클래스가 직선으로 잘 구분되고 있다. 다만 두 클래스를 구분하는 직선은 무수히 많다. 선형 서포트 벡터 머신은 '어떤 직선이 최적의 구분선일까'라는 질문에서 출발한다. 이제 임의의 직선 하나를 선택한다. 그리고 직선으로부터 가장 가까운 데이터 포인트를 찾아 그곳을 결정 경계(Decision Boundary)로 설정한다. 오른쪽 그래프에서 점선에 해당한다. 이때 처음 설정한 직선(실선)과 결정 경계(점선) 간의 차이를 마진(Margin)이라 하며, 마진을 최대로 하는 직선이 바로 최적의 구분선이 된다. 2차원 공간에서는 직선으로 표현되지만 (대부분의 경우에 해당하는) 3차원 이상의 공간에서 이 구분선은 초평면(Hyperplane)이 된다.
소프트 마진 분류(Soft Margin Classification)
모든 샘플이 마진 바깥쪽에 올바르게 분류된 경우를 하드 마진 분류(Hard Margin Classification)라고 한다. 오른쪽 이미지와 같이 데이터를 분류했다면 이는 하드 마진 분류에 해당한다. 그러나 실제 데이터에서 모든 데이터가 선형적으로 완전히 구분된다는 것은 다소 비현실적이다. 그리고 이러한 구분은 이상치에 특히 민감하다. 하드 마진의 문제를 해결하기 위해 등장한 것이 소프트 마진 분류(Soft Margin Classification)이다. 마진 내에 어느 정도의 오차를 허용하는 보다 유연한 모형이다. 간단히 하드 마진 분류에 완화 변수(Slack Variable)를 추가함으로써 기능한다.
수식으로 이해하기
두 개의 클래스가 각각 -1, 1이고 임의의 초평면이 $f(x)=\mathbf{w}^\top\mathbf{x}+b=0$ 라고 하자. 그러면 서포트 벡터 머신은 모든 관측치에 대해 아래 식을 만족하는 $\mathbf{w}$와 $b$를 구하는 문제가 된다.
$$\mathbf{w}^\top\mathbf{x}+b \geq 1 \quad\; ,\; y_{i}=1$$
$$\mathbf{w}^\top\mathbf{x}+b \leq -1 \quad ,\; y_{i}=-1$$
정리하면, 모든 데이터 포인트는 다음 식을 만족해야 한다.
$$y_{i}(\mathbf{w}^\top\mathbf{x}+b) \geq 1$$
한편, SVM의 핵심은 마진을 최대화하는 초평면을 찾는 것이다. 상위 경계의 피처 값을 $\mathbf{x}_{+},$ 하위 경계 피처 값을 $\mathbf{x}_{-}$로 표현하면 두 경계 사이 거리는 $\mathbf{w}^\top(\mathbf{x}_{+}-\mathbf{x}_{-})=2$다. 두 그룹을 완전하게 구분하는 모든 초평면은 이 식을 만족하기 때문에 표준화가 필요하다.
$$\text{Margin} = \frac{\mathbf{w}}{||\mathbf{w}||}(\mathbf{x}_{+}-\mathbf{x}_{-}) = \frac{2}{||\mathbf{w}||}$$
마진을 최대화하는 것이 SVM의 목적이므로, 결과적으로 이는 $||\mathbf{w}||$ 를 최소화하는 문제와 동일하다. 소프트 마진 분류에서는 완화변수(slack variable) $\zeta_{i}$ 를 도입해 더 작은 마진을 설정함으로써 조건을 완화한다. 일반화해 표현하면, SVM의 최적화 문제는 $y_{i}(\mathbf{w}^\top\mathbf{x}+b) \geq 1-\zeta_{i}$라는 조건 하에서 아래와 같이 정의된다.
$$\text{min}\frac{1}{2}||\mathbf{w}||^2 + c\sum_{i=1}^{n}\zeta_{i}$$
$||\mathbf{w}||$를 제곱하고 상수를 곱해 노름 계산을 단순화했다. c는 완화변수를 조정하는 초모수이며, 0일때 하드 마진 분류이다. 너무 크면 과대적합을 발생시킬 위험이 있다.
커널 트릭(Kernel Trick)
SVM은 기본적으로 두 클래스가 선형적으로 구분 가능할 때 효과적으로 작동한다. 앞서 설명한 예시에서 우리는 '직선'으로 클래스를 구분했다. 그러나 현실의 데이터는 선형적으로 완벽하게 구분되기 어렵다. 비선형 데이터를 다루는 한 가지 방법은 다항 변수를 추가하는 것이다. 과대적합인 경우 다항식의 차수를 줄이고, 과소적합인 경우 다항식의 차수를 늘린다. 간단하고 모든 알고리즘에서 잘 작동하지만, 높은 차수의 다항식은 굉장히 많은 피처 조합을 생성하므로 모형을 느리게 한다. 이러한 문제를 해결하기 위해 등장한 것이 커널 트릭(Kernel Trick)이다.
커널 트릭을 활용해 실제로는 피처를 추가하지 않으면서 피처를 많이 추가한 것 같은 결과를 얻을 수 있다. 고차원 변환을 암묵적으로 처리하여 계산 효율성을 높인다. 흔히 쓰이는 커널로 다항식 커널, 방사형 기본 함수(가우시안 커널), 시그모이드 함수 등이 있다. 커널 트릭에 대한 자세한 설명은 별도의 포스팅에서 다룰 것이다.
Reference
Aurélien Géron, Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow
박유성, 파이썬을 이용한 통계적 머신러닝