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

 

서포트 벡터 머신(이하 SVM)은 최대 마진 분류기(Maximal margin classifier)를 일반화한 모델입니다.
최대 마진 분류기는 매우 단순하면서도 강력하지만, 대부분의 데이터셋이 선형 결정 경계(Decision boundary)로 구별되기 어렵기 때문에 이를 더 확장한 모델들을 만들어냈습니다.
이번 글에서는 이들이 어떻게 다르고, 또 구체적으로 어떻게 동작하는지 정리해보았습니다.

 

 

최대 마진 분류기

---

앞서 언급한 모든 분류기가 하는 일은 바로 최적의 분리 초평면(Hyperplane)을 찾는 것입니다.
여기서 초평면이란 p차원의 공간에서 p-1차원인 평평한 아핀(affine) 부분 공간을 말합니다.
예를 들어 3차원 공간에서 평평한 2차원의 초평면을 수식으로 나타내면 다음과 같습니다. (이때 `X_1`, `X_2`는 초평면 상의 점)

$$f(X) = \beta_0 + \beta_1 X_1 + \beta_2 X_2 = 0$$

더 직관적인 이해를 위해 위 식에 임의의 값을 넣어 그래프를 그려보았습니다.

책 『가볍게 시작하는 통계학습: R로 실습하는』

위와 같이 파란색과 보라색 점들이 있을 때, 가운데 진한 검은 선이 바로 초평면을 나타냅니다.
즉 `f(X) = 0`이 되는 이 직선을 경계로, 그 값이 0보다 크거나 작을 경우 각각 파란색과 보라색 영역으로 분리할 수 있습니다.

 

그런데 이러한 초평면은 몇 개나 그릴 수 있을까요?
주어진 점들을 가르는 선의 개수는 계수들의 값을 조금씩만 바꿔 무한히 만들어낼 수 있습니다.
따라서 이들 중 가장 합리적인 초평면을 결정하는 방법이 필요하겠죠.
그것이 바로 최대 마진 초평면(또는 최적 분리 초평면)입니다.

마진(Margin)이란 각각의 훈련 관측치에서 주어진 초평면까지의 수직 거리 중 가장 짧은 거리를 말합니다.
훈련 데이터에 대해 큰 마진을 가질수록 검정 데이터에 대해서도 큰 마진을 가질 것이므로, 검정 관측치들을 올바르게 분류할 것이라고 기대할 수 있습니다.
따라서 마진이 가장 큰 초평면이 가장 최적의 분리 초평면이 됩니다.

https://www.analyticsvidhya.com/blog/2021/04/insight-into-svm-support-vector-machine-along-with-code/

여기까지 내용을 `n`개의 훈련 관측치들 `x_1, ..., x_n \in \; \mathbb{R}^p`을 클래스 라벨 `y_1, ..., y_n \in \;(-1, 1)`을 기반으로 하는 최대 마진 초평면 문제로 나타내면 다음과 같습니다.

$$\underset{\beta_0, \beta_1, ..., \beta_p}{maximize}\; M$$

$$subject \; to \sum_{j=1}^{p} \beta_j^2 = 1,$$

$$y_i(\beta_0 + \beta_1x_{i1} + \cdots + \beta_px_{ip}) \geq M \;  \forall \; i = 1, ..., n$$

즉 이는 `M`(Margin)을 최대로 하는 `\beta`(계수 또는 가중치)들을 선택하는 최적화 문제입니다.

 

 

서포트 벡터 분류기(Support Vector Classifier)

---

앞서 살펴본 최대 마진 분류기는 분리 초평면이 존재할 경우 효과적인 해결 방법이 될 수 있습니다.
그러나 많은 경우에 분리 초평면이 존재하지 않고, 이처럼 `M > 0`인 경우에는 그 해가 없습니다.
즉 클래스를 정확하게 분류해낼 수 없는 것이죠.

또는 분리 초평면이 존재한다고 해도 이에 따른 분류가 바람직하지 않을 수도 있습니다.
오히려 데이터에 과적합되어 개별 관측치에 대해 더 강건(robust)하지 못할 가능성이 큽니다.

따라서 차라리 몇몇 관측치를 잘못 분류하더라도 나머지를 더 잘 분류할 수 있도록, 분리 초평면 개념을 확장한 소프트 마진(Soft Margin)을 이용하는 것이 일반적입니다.
이를 서포트 벡터 분류기(이하 SVC) 또는 소프트 마진 분류기(Soft Margin Classifier)라고 합니다.
즉 모든 관측치의 클래스를 올바르게 분류하는 가장 큰 마진을 찾는 대신, 일부 관측치가 마진을 위반해도 허용하는 것입니다.

 

이를 수식으로 나타내면 다음과 같습니다.

$$\underset{\beta_0, \beta_1, ..., \beta_p, \epsilon_1, ..., \epsilon_n}{maximize}\; M$$

$$subject \; to \sum_{j=1}^{p} \beta_j^2 = 1,$$

$$y_i(\beta_0 + \beta_1x_{i1} + \cdots + \beta_px_{ip}) \geq M(1 - \epsilon_i) \;  \forall i = 1, ..., n,$$

$$\epsilon_i \geq 0, \sum_{i=1}^{n} \epsilon_i \leq C$$

그런데 여기서 결정 함수의 기울기는 사실 계수(가중치) 벡터의 노름(norm) `\left\| \mathbf{\beta} \right\|` 과도 같습니다.
다음 그래프에서는 계수 `\beta`를 보다 친숙한 `w`를 이용해 나타내고 있습니다.
두 그래프를 비교하면 가중치 벡터 `\mathbf{w}`에 따라 결정 함수의 기울기가 결정되고, 기울기가 작을수록 마진이 커짐을 확인할 수 있습니다.

책 『핸즈온 머신러닝』

앞서 마진을 최대화하는 것이 목표라고 했으므로, 기울기인 `\left\| \mathbf{\beta} \right\|`는 최소화해야 합니다.
따라서 소프트 마진 SVM 분류기의 목적 함수를 수식으로 정리하면 다음과 같습니다.

$$\underset{\beta_0, \beta_1, ..., \epsilon}{minimize}\; \frac{1}{2}\beta_j^2 + C \sum_{j=1}^{p} \epsilon_i$$

여기서 `\epsilon`은 0보다 크거나 같은 슬랙 변수(Slack variable)로 `i`번째 샘플이 얼마나 마진을 위반할지를 정합니다.
`\beta` 앞에 `\frac{1}{2}`이 붙은 것은 추후 목적 함수의 미분이 쉽도록 한 것입니다. (목적 함수의 최적화를 위해 미분 값을 사용)

이 목적 함수는 두 개의 상충되는 목표를 가지고 있습니다.
하나는 마진 오류를 최소화하기 위해 가능한 한 슬랙 변수 `\epsilon_i`의 값을 작게 만드는 것이고,
다른 하나는 마진을 크게 하기 위해 `\beta_j^2`을 가능한 한 작게 만드는 것입니다.

이때 슬랙 변수 앞에 곱해진 C는 0보다 크거나 같은 하이퍼파라미터로, `\epsilon_i`의 합을 한정하여 마진에 대한 허용 위반의 수와 그 정도를 결정하고, 두 목표 사이 트레이드오프(trade-off)를 정의합니다.
즉 C가 증가함에 따라 마진 위반에 대한 허용 정도가 크고, 마진의 폭이 넓어집니다. 이는 편향이 더 높고 분산은 낮은 분류기를 만들어 데이터에 덜 적합(fit)되도록 합니다.

책 『가볍게 시작하는 통계학습: R로 실습하는』

위 그래프는 C에 따른 마진과 결정 경계(Decision boundary)의 차이를 보여줍니다.
왼쪽 위부터 가장 큰 C 값이 적용되어 오른쪽 아래로 올수록 점점 작은 값이 적용되었습니다.
이처럼 C가 감소함에 따라 관측치가 잘못 분류될 수 있는 허용 수준이 줄어들어 마진이 줄어드는 것을 볼 수 있습니다.

하드 & 소프트 마진 문제는 모두 선형적 제약 조건이 있는 볼록 함수의 이차 최적화 문제라고 할 수 있습니다.
이를 QP(Quadratic Programming) 문제라고 하는데, 이에 대해 정확히 이해하려면 컨벡스 최적화(Convex Optimization) 이론에 대한 이해가 먼저 필요합니다. 궁금한 분은 여기에 내용이 잘 정리되어 있으니, 참고하시면 됩니다.

 

 

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

---

지금까지는 모두 결정 경계가 선형인 경우만 살펴보았습니다. 그러나 현실에서는 클래스 경계가 비선형인 상황도 존재합니다.
이처럼 비선형 결정 경계를 만들기 위해서는 더 높은 차수의 다항식 함수들을 사용해 변수 공간을 확장할 수 있습니다.
그러나 어떤 특성을 추가해야 할지 알 수 없고, 특성을 많이 추가할수록 특성들의 모든 조합을 계산하게 되므로 연산 비용이 매우 커집니다.
이러한 문제를 해결하기 위해 SVM은 SVC에서 확장해 커널 트릭(Kernel trick) 또는 커널 기법을 활용합니다.
트릭이라고 말하는 이유는 실제로는 특성을 추가하지 않으면서, 다만 확장된 특성에 대한 데이터 포인트들의 거리(정확히 말해 내적 inner/dot product)를 계산해 다항식 특성을 많이 추가한 것과 같은 결과를 얻을 수 있기 때문입니다.

이처럼 SVM에서 데이터를 고차원 공간에 매핑하기 위해 많이 사용하는 방법은 두 가지입니다.
원래 특성의 가능한 조합을 지정된 차수까지 모두 계산하는 다항식 커널과,
가우시안(Gaussian) 커널로도 불리우는 RBF(Radial Basis Function) 커널이 그것입니다.
이중 가우시안 커널은 차원이 무한한 특성 공간에 매핑하는 것으로, 모든 차수의 모든 다항식을 고려합니다.

아래 그림 중 왼쪽은 3차 다항식 커널을 가진 SVM, 오른쪽은 RBF 커널을 가진 SVM이 적용된 경우 각 결정 경계를 나타냅니다.

책 『가볍게 시작하는 통계학습: R로 실습하는』

커널 기법 자체가 어렵게 느껴지지만, 단순히 설명하면 그저 효율적인 하나의 계산 기법이라고 할 수 있습니다.
즉 앞서 설명한 것처럼 관측치 자체가 아닌 관측치들의 거리(내적)를 통해 분류기 문제의 해를 찾는 방법인 셈입니다.

예를 들어 관측치 쌍들 `x_i, x_{i'}` 사이 내적은 `\left< x_i, x_{i'} \right> = \sum_{j=1}^{p} x_{ij}x_{i'j}` 입니다.
이를 두 관측치들의 유사성을 수량화하는 함수, 즉 커널 함수 `K`로 표현할 수 있습니다.
차수가 `d`인 다항식 커널로 표현하면 다음과 같습니다.

$$K(x_i, x_{i'}) = (1 + \sum_{j=1}^{p} x_{ij}x_{i'j} )^d$$

SVC가 이와 같은 비선형 커널과 결합될 때 비로소 SVM이라고 할 수 있으며, 그 함수는 다음과 같습니다.

$$f(x) = \beta_0 + \sum_{i \in S} \alpha_i K(x, x_i)$$

즉 `d=1`일 때에는 곧 SVC가 됩니다.

 

널리 사용되는 또 다른 비선형 커널은 RBF 커널이며, 다음과 같은 형태를 가집니다.

$$K(x_i, x_{i'}) = exp \left( -\gamma \sum_{j=1}^{p} (x_{ij} - x_{i'j})^2 \right)$$

 

 

아래 자료를 참고했습니다.

• 책 『가볍게 시작하는 통계학습: R로 실습하는』
• 책 『핸즈온 머신러닝』
• 커널 서포트 벡터 머신