ISL 9. Support Vector Machines

서포트 벡터 머신(support vector machines; SVM)은 1990년대 컴퓨터 과학계에서 개발되어 지금까지 널리 사용되는 분류 기법 중 하나이다. 이번 챕터에서는 먼저 초평면 분리를 이용하는 최대 마진 분류기(maximal margin classifier)와, 소프트 마진(soft margin)을 이용해 최대 마진 분류기보다 모델의 분산을 낮출 수 있는 서포트 벡터 분류기(support vecotr classifier)에 대해 알아본다. SVM은 선형 결정 경계를 가지는 서포트 벡터 분류기를 비선형 경계로 확장한다. 직접 피처의 개수를 늘리지 않고 커널(kernel)을 이용하는 방식으로 피처 공간을 확장하여 비선형 결정 경계를 가지면서도 계산이 빠르다. 두 개 이상의 클래스가 존재할 때 SVM을 활용하는 방식을 살펴보고, 보다 전통적인 통계적 학습법인 로지스틱 회귀와 SVM을 비교해보며 이번 챕터를 마친다.

9.1 최대 마진 분류기

9.1.1 초평면이란 무엇인가?

\(p\)차원의 공간에서 초평면(hyperplane)은 \(p-1\) 차원의 평평한(flat) 아핀 부분공간(affine subspace)이다. 예를 들어, 2차원에서의 초평면은 평평한 1차원 부분공간, 즉 선이며, 3차원에서의 초평면은 평평한 2차원 부분공간, 즉 면이다. 수학적으로 정의해보면, \(p\)차원에서 초평면은 아래와 같이 정의된다.

위 식을 만족하는 모든 \(X =(X_1,X_2, . . . , X_p)^T\) (길이가 \(p\)인 벡터)는 해당 초평면 위에 존재한다.

만일, \(X\)가 \(β_0 + β_1X_1 + β_2X_2 + ... + β_pX_p > 0\)을 만족한다면, \(X\)는 초평면의 한쪽에 위치한다고 할 수 있을 것이다. 반대로, \(X\)가 \(β_0 + β_1X_1 + β_2X_2 + ... + β_pX_p < 0\)을 만족한다면, \(X\)는 초평면의 다른 쪽에 위치한다고 할 수 있다. 따라서 초평면이 \(p\)차원의 공간을 둘로 나눈다고 생각해볼 수 있다.

9.1.2 초평면 분리를 통한 분류

이제 \(p\)차원 공간에서 \(n\)개의 훈련 관측치로 구성된 \(n×p\) 데이터 행렬 \(X\)가 있다고 가정해보자.

그리고 이러한 관측치들은 두 클래스 중 하나에 속한다. 즉, \(y_1, . . . , y_n ∈ \left\{−1, 1\right\}\)이다. \(-1\)과 \(1\)은 각각 다른 클래스를 의미한다. 테스트 관측치는 \(p\)차원의 벡터 \(x^∗ = (x^∗_1\ . . .\ x^∗_p)^T\)이다. 우리의 목표는 훈련 데이터로부터 분류기를 만들어 테스트 관측치를 올바르게 분류하는 것이다. 지금까지 많은 분류 방법들을 배웠지만 이번에는 초평면 분리에 기반한 새로운 방법을 알아보자.

훈련 관측치를 각각이 속한 클래스에 따라 완벽하게 분리하는 초평면을 찾았다고 가정해보자. 그렇다면 초평면은 아래의 특성을 가질 것이다.

같은 말로, 분리하는 초평면은 모든 \(i = 1, . . . , n\)에 대하여 아래와 같은 특성을 가진다.

이렇듯 분리하는 초평면이 존재한다면 테스트 관측치가 초평면의 어떤 쪽에 위치하는지에 따라 클래스를 할당하는 아주 자연스러운 분류기를 만들 수 있을 것이다. 즉, 테스트 관측치 \(x^∗\)를 \(f(x^∗) = β_0+β_1x^∗_1+β_2x^∗_2+. . .+β_px^∗_p\)의 부호에 따라 분류하는 것이다. \(f(x^∗)\)가 양수라면 테스트 관측치를 클래스 1에, 음수라면 -1에 할당한다. \(f(x^∗)\)의 절댓값의 크기도 해석할 수 있다. \(f(x^∗)\)가 0으로부터 멀다는 것은 \(x^∗\)가 초평면으로부터 멀리 떨어져 있음을 의미하기 때문에 \(x^∗\)의 클래스 할당에 대하여 확신할 수 있다. 반대로 \(f(x^∗)\)가 0에 가깝다면 \(x^∗\)가 초평면 가까이에 위치한다는 것이기 때문에 \(x^∗\)의 클래스 할당에 대한 확신도 낮아진다. 분리하는 초평면에 기반하는 분류기는 선형 결정 경계(linear decision boundary)를 가진다.

9.1.3 최대 마진 분류기

분리하는 초평면은 사실상 무한개로 존재한다. 이중 최대 마진 초평면(maximal margin hyperplane) 또는 최적 분리 초평면(optimal seperating hyperplane)은 훈련 관측치들로부터 가장 먼 것이다. 이때, 마진(margin)이란 관측치들로부터 초평면까지의 최소 거리를 의미한다. 최대 마진 분류기는 테스트 관측치가 최대 마진 초평면의 어떤 쪽에 위치하는지에 따라 해당 관측치를 분류한다. 즉, \(β_0, β_1, . . . , β_p\)가 최대 마진 초평면의 계수라면 최대 마진 분류기는 테스트 관측치 \(x^∗\)를 \(f(x^∗) = β_0+β_1x^∗_1+β_2x^∗_2+. . .+β_px^∗_p\)의 부호에 따라 분류한다. 이때, 최대 마진 초평면으로부터 가장 가까운 훈련 관측치들을 서포트 벡터(support vectors)라고 한다. 서포트 벡터는 \(p\)차원 공간의 벡터이며, 조금만 움직여도 최대 마진 초평면 역시 이동한다는 점에서 최대 마진 초평면을 “서포트”한다. 최대 마진 초평면은 다른 관측치에는 영향을 받지 않으며 서포트 벡터에 직접적으로 좌우된다.

9.1.4 최대 마진 분류기 만들기

\(n\)개의 훈련 관측치 세트 \(x_1, . . . , x_n ∈ \mathbb{R}^p\)와 관련된 클래스 라벨 \(y_1, . . . , y_n ∈ \left\{−1, 1\right\}\)을 가지고 최대 마진 분류기를 만들어보자. 간단히 말해, 최대 마진 초평면은 아래 최적화 문제의 해이다.

수식의 세 번째 줄은 \(M\)이 양수라는 전제 하에 각 관측치가 초평면의 올바른 쪽에 놓이도록 한다. 이전 절에서 살펴본 바와 같이 \(y_i(β_0 + β_1x_{i1} + β_2x_{i2} + . . . + β_px_{ip}) > 0\)만으로 각 관측치를 올바른 쪽에 놓을 수 있지만, 양수 \(M\)이 일종의 쿠션 역할을 하는 것이다. 한편, 수식의 두 번째 줄에 의해 \(i\)번째 관측치로부터 초평면까지의 수직 거리(perpendicular distance)는 \(y_i(β_0 + β_1x_{i1} + β_2x_{i2} + . . . + β_px_{ip})\)가 된다. 정리하자면 수식의 두세 번째 줄은 각 관측치가 초평면의 올바른 쪽에 놓이며, 초평면으로부터 적어도 \(M\)의 거리를 두도록 한다. 따라서 \(M\)은 초평면의 마진을 나타내고, 최적화 문제는 \(M\)을 최대화하는 \(β_0, β_1, . . . , β_p\)를 선택하는 것이다.

9.2 서포트 벡터 분류기

9.2.1 서포트 벡터 분류기의 개관

불행히도 많은 경우 관측치들을 완벽하게 분리하는 초평면은 존재하지 않는다. 따라서 최대 마진 분류기도 존재하지 않고, 이전 절에서 살펴본 최적화 문제도 \(M >0\)일 때 해가 없다. 설사 관측치들이 완벽히 분리된다고 하더라도 초평면 분리를 통한 분류기는 개별 관측치들에 매우 민감하다. 관측치 하나가 추가됨으로써 최대 마진 초평면에 극적인 변화가 발생하여 마진이 좁아지고 훈련 데이터에 과적합이 발생할 수 있다. 이런 경우 클래스를 완벽히 분리하지는 못하더라도 개별 관측치에 더 강인(robust)하고 대부분의 훈련 관측치들을 더 잘 분류하는 모델이 훨씬 나을 것이다.

서포트 벡터 분류기(support vector classifier) 혹은 소프트 마진 분류기(soft margin classifier)는 이렇듯 몇 개의 훈련 관측치들을 잘못 분류하더라도 전반적인 관측치들을 더 잘 분류하고자 한다. 이때 마진이 몇몇 훈련 관측치들에 의해 위반될 수 있기 때문에 소프트 마진이라고 한다.

9.2.2 서포트 벡터 분류기의 세부 내용

서포트 벡터 분류기는 아래 최적화 문제를 풀어 초평면을 찾는다.

\(M\)은 마진의 너비로, 최대화하고자 하는 값이다. \(C\)는 음수가 아닌 튜닝 파라미터로, \(\epsilon_i\)의 합산 값을 제한하여 마진을 위반하는 개수와 정도를 조정한다. \(C = 0\)이면 마진에 대한 위반을 조금도 받아들이지 않으며, \(\epsilon_1 = . . . = \epsilon_n = 0\)이다. \(C > 0\)이면 초평면의 잘못된 쪽에 놓이는 관측치의 개수는 \(C\)를 초과하지 못한다. \(C\)가 증가할수록 마진 위반에 대한 허용(tolerance) 정도가 커지고 마진이 넓어진다. \(C\)는 교차검정을 통해 선택되는 튜닝 파라미터이며 편향-분산 트레이드오프를 조정한다. 값이 작아지면 편향이 낮지만 분산이 크고, 값이 커지면 편향이 높지만 분산이 작다. \(\epsilon_i,...,\epsilon_n\)은 개별 관측치들이 마진 혹은 초평면의 잘못된 쪽에 놓일 수 있게 하는 여유 변수(slack variables)이다. 여유 변수 \(\epsilon_i\)는 초평면 및 마진의 측면에서 \(i\)번째 관측치가 어디에 위치하고 있는지 말해준다. \(\epsilon_i = 0\)이면 \(i\)번째 관측치는 마진의 올바른 쪽에 위치한다. \(\epsilon_i > 0\)이면 \(i\)번째 관측치는 마진의 잘못된 쪽에 위치한다. \(\epsilon_i > 1\)이면 \(i\)번째 관측치는 초평면의 잘못된 쪽에 위치한다.

위 최적화 문제를 풀면 테스트 관측치 \(x^∗\)가 초평면의 어느 쪽에 놓이는지에 따라 분류할 수 있다. 즉, \(f(x^∗) = β_0 + β_1x^∗_1 + . . . + β_px^∗_p\)의 부호에 따라 테스트 관측치를 분류한다. 마진 위에 놓이거나 마진을 위반하여 초평면에 영향을 미치는 관측치들을 서포트 벡터라 한다. \(C\)가 크면 서포트 벡터의 수도 많아지고, 작으면 서포트 벡터의 수도 적어진다.

9.3 서포트 벡터 머신

9.3.1 비선형 결정 경계의 분류

이전 절에서 살펴본 서포트 벡터 분류기는 선형 결정 경계를 가지기 때문에 비선형 경계를 가지는 관측치들을 분류하게 되면 성능이 나빠질 것이다. 한 가지 해결책은 예측변인에 대하여 고차항을 가지는 다항함수를 사용하는 것이다. 예를 들어, \(p\)개의 피처 \(X_1,X_2, . . . , X_p\)를 사용하는 대신, \(2p\)개의 피처 \(X_1,X^2_1,X_2,X^2_2, . . . , X_p,X^2_p\)를 사용하는 식이다. 이밖에도 다양한 방식으로 피처 공간(feature space)을 넓힐 수 있겠지만 피처의 개수가 늘어날수록 계산은 어려워진다. 이와 달리, 다음 절부터 살펴볼 서포트 벡터 머신은 피처의 개수를 늘릴 필요 없이 계산을 효율화하는 방면으로 서포트 벡터 분류기에 쓰이는 피처 공간을 넓혀줄 수 있다.

9.3.2 서포트 벡터 머신

서포트 벡터 머신(support vector machine; SVM)은 커널(kernel)을 이용하는 특정 방식으로 피처 공간을 넓히는 서포트 벡터 분류기의 확장이다. 서포트 벡터 분류기 문제의 해는 관측치들의 내적(inner products)만을 포함한다. 두 \(r\)차원 벡터 \(a\)와 \(b\)의 내적은 \(\left\langle a, b \right\rangle =\sum^r_{i=1} a_ib_i\)로 표현한다. 따라서 두 관측치 \(x_i\), \(x_{i'}\)의 내적은 \(\left\langle x_{i}, x_{i'} \right\rangle =\sum^p_{j=1} x_{ij}x_{i'j}\)이다. 선형 서포트 벡터 분류기는 아래와 같이 표현할 수 있다. \(f(x) = β_0 + \sum^n_{i=1}α_i \left\langle x, x_i \right\rangle\)

이때, 관측치당 \(n\)개의 파라미터 \(α_i\), \(i = 1, . . . , n\)가 존재한다. 파라미터 \(α_1, . . . , α_n\)과 \(β_0\)를 추정하기 위해서는 훈련 관측치 모든 쌍 간의 \(n \choose 2\)개의 내적 \(\left\langle x_{i}, x_{i'} \right\rangle\)가 필요하다. 위 식에 따르면, 함수 \(f(x)\)를 계산하기 위해서는 새로운 포인트 \(x\)와 각 훈련 포인트 \(x_i\) 간의 내적을 계산해야 한다. \(α_i\)는 서포트 벡터에 대해서만 0이 아니다. 즉, 어떤 훈련 관측치가 서포트 벡터가 아니면 \(α_i\)는 0이 된다. 따라서 서포트 포인트의 인덱스 목록을 \(\mathcal{S}\)라 할 때, 위 식을 아래와 같이 쓸 수 있다.

\(f(x) = β_0 + \sum_{i∈\mathcal{S}}α_i \left\langle x, x_i \right\rangle\) 이제 위와 같은 식에서 내적 \(\left\langle x_{i}, x_{i'} \right\rangle\)가 등장하거나 서포트 벡터 분류기의 해를 계산할 때 \(K(x_i,x_{i'})\)와 같은 형태로 내적을 일반화한다. \(K\)는 커널이라 불리며, 두 관측치 간의 유사성을 정량화하는 함수이다. 예를 들어 아래와 같은 커널을 취하면 서포트 벡터 분류기를 얻을 수 있다.

서포트 벡터 분류기가 피처에 대하여 선형이기 때문에 이것을 선형 커널(linear kernel)이라 한다. 선형 커널은 본질적으로 피어슨 상관(Pearson correlation)을 이용해 관측치 한 쌍의 유사성을 정량화한다. 한편, 아래와 같이 다른 형태의 커널을 사용할 수도 있다.

위는 \(d\)가 양수인 \(d\)차의 다항 커널이며, 유연한 경계를 갖는다. 이와 같은 비선형 커널과 결합한 서포트 벡터 분류기를 서포트 벡터 머신이라고 한다. 이러한 비선형 함수는 아래와 같은 형태로 표현된다.

방사 커널(radial kernel) 역시 자주 사용되는 비선형 커널이며, 아래와 같은 형태를 취한다.

이때, \(γ\)는 양의 상수이다. 유클리드 거리(Euclidean distance) 면에서 어떤 테스트 관측치 \(x^∗ = (x^∗_1 . . .x^∗_p)^T\)가 훈련 관측치 \(x_i\)로부터 멀다면, \(\sum^p_{j=1}(x^∗_j−x_{ij})^2\)도 커지고, \(K(x^∗, x_i) = \exp(−γ\sum^p_{j=1}(x^∗_j− x_{ij} )^2)\)은 매우 작아질 것이다. 즉, SVM의 함수에서 \(x_i\)가 \(f(x^∗)\)에 사실상 아무런 영향도 미치지 않게 된다. \(x^∗\)로부터 먼 훈련 관측치들은 \(x^∗\)의 클래스 라벨을 예측하는 데 영향을 미치지 않는 것이다. 따라서 방사 커널은 테스트 관측치의 클래스 라벨에 근접한 훈련 관측치들만 영향을 미치는 국지적(local)인 성질을 띤다.

그렇다면 단순히 원래의 피처들의 함수를 사용해 피처 공간을 넓히는 것에 비해 커널을 사용하는 것의 이점은 무엇일까? 한 가지는 계산상의 이점이다. 커널을 사용하면 넓어진 피처 공간을 직접 다루지 않고도 모든 \(n \choose 2\)개의 쌍 \(i\), \(i'\)에 대한 \(K(x_i, x'_i)\)만 계산하면 되기 때문이다. 많은 SVM의 활용에서는 피처 공간이 너무 넓기 때문에 이는 매우 큰 장점이다. 특히, 방사 커널과 같은 몇몇 커널에서는 피처 공간이 아예 암묵적(implicit)이고 무한 차원이기 때문에 이를 직접 다루는 것 자체가 불가능하다.

9.4 두 개 이상의 클래스에서의 SVM

9.4.1 One-Versus-One 분류

SVM을 이용해 \(K > 2\)개의 클래스에 대한 분류를 수행한다고 해보자. One-versus-one 혹은 all-pairs 접근에서는 우선 클래스들의 모든 쌍에 대한 \(K \choose 2\)개의 SVM 모델을 만든다. 이러한 \(K \choose 2\)개의 분류기를 사용해 테스트 관측치를 분류하고, 해당 관측치가 각 \(K\)개의 클래스에 할당된 횟수를 센다. 최종적으로 이러한 \(K \choose 2\)개의 쌍별 분류에서 가장 빈번하게 할당된 클래스에 테스트 관측치를 할당한다.

9.4.2 One-Versus-All 분류

One-Versus-All 접근에서는 \(K\)개의 클래스 중 하나와 남은 \(K - 1\)개의 클래스를 비교하여 \(K\)개의 SVM을 적합시킨다. \(β_{0k}, β_{1k}, . . . , β_{pk}\)를 \(k\)번째 클래스와 그 외 클래스를 비교하여 적합시킨 SVM의 파라미터라고 한다면, 테스트 관측치 \(x^*\)는 \(β_{0k}+β_{1k}x^∗_1+β_{2k}x^∗_2+. . .+β_{pk}x^∗_p\)가 가장 커지는 클래스에 할당된다. 이 값이 크다는 것은 다른 클래스에 비해 \(k\)번째 클래스에 테스트 관측치가 속할 신뢰도(confidence)가 높다는 것을 의미하기 때문이다.

9.5 로지스틱 회귀와의 관계

데이터를 잘 분리하는 초평면을 찾는다는 개념, 커널을 통해 피처 공간을 넓힌다는 개념은 SVM이 발표된 당시 굉장히 새롭게 느껴졌다고 한다. 그러나 SVM 역시 다른 전통적인 통계적 방법들과 관련이 있다. 서포트 벡터 분류기 \(f(X) = β_0 + β_1X_1 + . . . + β_pX_p\)를 적합시킨다고 할 때 9.2.2절에서 살펴본 최적화 문제는 아래와 같이 다시 쓸 수 있다.

이때, \(λ\)는 음이 아닌 튜닝 파라미터이며, 9.2.2절의 식에서 \(C\)에 대응한다. 위 식의 \(λ \sum^p_{j=1} β^2_j\) 항은 릿지 페널티 항이며, 비슷하게 서포트 벡터 분류기의 편향-분산 트레이드오프를 조정하는 역할을 한다. 위 식은 \(\underset{β_0,β_1,...,β_p}{\mathrm{minimize}} \left\{ L(\mathbf{X},\mathbf{y},β) + λ P(β) \right\}\)와 같은 “손실(Loss) + 페널티(penalty)”의 형태로 이루어져 있다. 여기에서 \(L(\mathbf{X},\mathbf{y},β)\)는 \(β\)의 파라미터를 가지는 모델이 데이터 \((\mathbf{X},\mathbf{y})\)에 적합하는 정도를 수량화하는 어떤 손실 함수이다. \(P(β)\)는 파라미터 벡터 \(β\)의 효과가 음이 아닌 튜닝 파라미터 \(λ\)에 의해 조정되는 페널티 함수이다. 위 식의 손실 함수는 아래와 같은 형태이다.

이것은 힌지 로스(hinge loss)로 알려져 있으며, 로지스틱 회귀에 쓰이는 손실 함수와 관련이 있다. 앞서 서포트 벡터 분류기에서는 서포트 벡터만이 영향력을 발휘한다는 점을 배웠다. 이는 \(y_i(β_0 + β_1x_{i1} +. . .+ β_px_{ip}) ≥ 1\)인 관측치에 대하여 손실 함수가 완전히 0이 되기 때문이다. 이 관측치들은 마진의 올바른 쪽에 놓인 것이다. 한편, 로지스틱 회귀의 손실 함수는 완전히 0이 되지는 않지만 결정 경계로부터 먼 관측치들에 대해서는 매우 작아진다. 이렇듯 손실 함수에서의 유사성으로 인해 로지스틱 회귀와 서포트 벡터 분류기는 자주 비슷한 결과를 낸다. 클래스가 잘 분리되어 있을 때는 로지스틱 회귀에 비해 SVM의 성능이 우수하고, 클래스가 중첩되는 경우에는 로지스틱 회귀의 성능이 낫다.

이번 장에서 다루지 않았지만 SVM을 회귀로 확장한 것을 서포트 벡터 회귀(support vector regression)라고 한다. 챕터 3에서 살펴본 최소 자승 회귀가 잔차 제곱합을 최소로 하는 계수 \(β_0, β_1, . . . , β_p\)를 찾는 한편, 서포트 벡터 회귀에서는 최소화하고자 하는 손실의 종류가 다르다.어떤 양의(positive) 상수보다 절댓값이 큰 잔차들만 손실 함수에 영향을 미친다. 서포트 벡터 분류기에서 사용되는 마진이 회귀로 확장된 개념이라고 이해할 수 있다.