서포트 벡터 머신

1. 개요[편집]

서포트 벡터 머신 Support Vector Machine
약칭	SVM
계보	Vapnik & Chervonenkis (1963) → Boser·Guyon·Vapnik (1992, 커널) → Cortes & Vapnik (1995, 소프트 마진)
정체	볼록 이차계획 문제 하나
목적	두 클래스 사이 마진 최대화 = 힌지 손실 + L2 벌점 최소화
표준 솔버	SMO (Platt, 1998) · LIBSVM · LIBLINEAR
비용	커널 SVM 대략 O(n²)~O(n³) — 표본 수가 지배

딥러닝 이전, 이 바닥의 국룰은 “일단 RBF 커널 SVM부터 돌려 보고 그보다 나은지 확인해라”였다. 그리고 그 국룰은 표본이 적은 자리에서 아직 안 죽었다.

서포트 벡터 머신(support vector machine, SVM)은 두 클래스를 나누는 무수한 분리초평면 중 양쪽 클래스까지의 최소 거리(마진)를 최대화하는 하나를 고르고, 그 문제를 볼록 이차계획으로 정식화해 전역 최적해를 보장하는 분류기다. 여기에 두 가지 장치가 붙는다 — 겹치는 데이터를 허용하는 소프트 마진, 그리고 비선형 경계를 내적 교체만으로 얻는 커널.

SVM이 1990년대에 판을 뒤집은 이유는 정확도 자체가 아니라 정직함이었다. 당시 주류였던 다층 퍼셉트론은 초기값에 따라 다른 지역해로 수렴했고, 은닉층 개수는 사실상 점술이었다. SVM은 목적함수가 볼록이라 초기값과 무관하게 같은 답이 나오고, 모형 복잡도는 마진이라는 기하량 하나로 조절되며, 그 마진이 일반화 성능의 상계와 연결된다는 이론까지 딸려 왔다. “재현되는 답”이 얼마나 큰 미덕인지는 심층 학습의 시드 지옥을 겪어 본 사람이라면 안다.¹

2. 최대 마진이라는 아이디어[편집]

선형분리가 가능한 데이터 $\{(\mathbf x_i, y_i)\}_{i=1}^{n}$, $y_i \in \{-1,+1\}$ 를 나누는 초평면 $\mathbf w^{\mathsf T}\mathbf x + b = 0$ 은 무한히 많다. 로지스틱 회귀는 그중 가능도가 가장 큰 것을 고르고(분리 가능하면 사실 발산한다), 퍼셉트론은 그냥 먼저 찾은 것을 고른다. SVM의 선택 기준은 기하다 — 가장 가까운 점까지의 거리를 최대로.

점 $\mathbf x_i$ 에서 초평면까지의 거리는 $|\mathbf w^{\mathsf T}\mathbf x_i + b| / \lVert \mathbf w\rVert$ 다. 여기서 $(\mathbf w, b)$ 를 같은 상수로 곱해도 초평면은 그대로이므로, 이 잉여 자유도를 가장 가까운 점에서 $|\mathbf w^{\mathsf T}\mathbf x + b| = 1$ 이 되도록 못 박는다(정준 스케일링). 그러면 두 지지초평면 $\mathbf w^{\mathsf T}\mathbf x + b = \pm 1$ 사이 폭이 정확히 $2/\lVert\mathbf w\rVert$ 이고, 마진 최대화는

$$\min_{\mathbf w, b}\ \tfrac{1}{2}\lVert \mathbf w\rVert^2 \qquad \text{s.t.}\quad y_i(\mathbf w^{\mathsf T}\mathbf x_i + b) \ge 1,\quad i=1,\dots,n$$

가 된다. 목적함수가 양정치 이차형식이고 제약이 전부 아핀이므로 볼록 이차계획이다. 지역해가 곧 전역해이고, 슬레이터 조건이 자동으로 만족되어 쌍대성 갭이 0이다. 이 한 줄이 SVM이 가진 모든 이론적 안정감의 출처다.

3. 소프트 마진 — 겹치는 데이터를 위한 세금[편집]

현실 데이터는 겹친다. 위 제약을 그대로 두면 실행가능영역이 비어 문제가 아예 풀리지 않으므로, 여유변수 $\xi_i \ge 0$ 로 위반을 허용하고 위반량에 값을 매긴다(Cortes & Vapnik, 1995).

$$\min_{\mathbf w, b, \boldsymbol\xi}\ \tfrac{1}{2}\lVert \mathbf w\rVert^2 + C\sum_{i=1}^{n}\xi_i \qquad \text{s.t.}\quad y_i(\mathbf w^{\mathsf T}\mathbf x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0$$

$C$ 는 마진 폭과 위반 허용량 사이의 환율이다. $C\to\infty$ 면 하드 마진으로 돌아가고(분리 가능하다면), $C$ 가 작으면 몇 개쯤 틀려도 좋으니 마진을 넓게 가져간다. 실무에서 $C$ 와 커널 폭 $\gamma$ 두 개를 로그 격자로 훑는 것이 표준 절차이고, 교차검증 없이 기본값으로 돌린 SVM 결과는 대체로 믿을 게 못 된다.

여유변수에 붙는 벌점이 $\xi_i$ 의 1제곱이라는 점이 중요하다. $\xi_i^2$ 를 쓰면(L2-SVM) 미분가능해져 최적화는 편해지지만, 아래에서 볼 희소성이 사라진다. 왜 그런지는 쌍대문제를 봐야 보인다.

4. 쌍대문제와 KKT — 서포트 벡터는 왜 소수인가[편집]

라그랑주 승수법으로 제약을 목적함수에 흡수하고 $\mathbf w, b$ 로 미분해 0을 놓으면

$$\mathbf w = \sum_{i=1}^{n}\alpha_i y_i \mathbf x_i, \qquad \sum_{i=1}^{n}\alpha_i y_i = 0$$

이 나온다. 가중치 벡터가 데이터점들의 선형결합으로 강제된다는 첫 번째 식이 이 문서의 나머지 전부를 결정한다. 이걸 되돌려 넣으면 원시 변수가 전부 사라지고 승수만 남는다.

$$\max_{\boldsymbol\alpha}\ \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j\,\mathbf x_i^{\mathsf T}\mathbf x_j \qquad \text{s.t.}\quad \sum_i \alpha_i y_i = 0,\ \ 0 \le \alpha_i \le C$$

하드 마진과 다른 곳은 딱 하나, $\alpha_i \le C$ 라는 상자 제약뿐이다(여유변수의 승수 $\mu_i$ 가 $\alpha_i + \mu_i = C$ 를 강제한 결과다). 소프트 마진이 “복잡한 확장”이 아니라 “위쪽 뚜껑 하나”라는 사실은 몇 번을 봐도 산뜻하다.

희소성은 KKT 상보여유조건에서 나온다. 최적점에서

$$\alpha_i\big[y_i(\mathbf w^{\mathsf T}\mathbf x_i + b) - 1 + \xi_i\big] = 0, \qquad \mu_i\xi_i = (C-\alpha_i)\xi_i = 0$$

이 성립하므로, $\alpha_i$ 의 값에 따라 점이 세 종류로 정확히 갈린다.

$\alpha_i$	점의 위치	이름
$\alpha_i = 0$	마진 바깥, 여유 있게 정분류	비-서포트 벡터
$0 < \alpha_i < C$	마진 경계 위에 정확히 놓임	자유 서포트 벡터
$\alpha_i = C$	마진 안쪽 또는 오분류	속박 서포트 벡터

즉 여유 있게 맞힌 점은 승수가 정확히 0이 되어 해에 전혀 기여하지 않는다. 판정함수 $f(\mathbf x)=\sum_i \alpha_i y_i \mathbf x_i^{\mathsf T}\mathbf x + b$ 의 합에서 그 점들은 통째로 빠지고, 남는 것이 경계 근처의 소수 — 서포트 벡터다. 데이터의 90%를 지우고 다시 학습해도 서포트 벡터만 남아 있으면 같은 초평면이 나온다. 이것이 SVM이 “메모리 기반 방법인데 데이터를 다 안 들고 다니는” 이유이고, 힌지 손실이 정확히 0인 평평한 구간을 갖기 때문에 생긴다. $\xi_i^2$ 벌점을 쓰면 이 평평한 구간이 사라져 모든 점이 $\alpha_i > 0$ 을 받는다.

서포트 벡터의 개수에는 실용적인 의미도 붙는다. 바프닉이 보인 단일제거(leave-one-out) 오차의 상계

$$\mathbb{E}[\text{LOO 오차율}] \;\le\; \frac{\mathbb{E}[\#\text{SV}]}{n}$$

는 논증이 간단하다 — 서포트 벡터가 아닌 점을 빼도 해가 안 바뀌므로 그 점은 제거해도 여전히 맞힌다.² 따라서 오답 가능성이 있는 것은 서포트 벡터뿐이다. 서포트 벡터가 표본의 절반을 넘으면 그 모형은 이미 과적합을 의심할 이유가 있다는 현장 감각이 여기서 나온다. 쇤코프의 $\nu$-SVM 은 아예 이 비율을 $\nu$ 라는 하이퍼파라미터로 노출시켜, $\nu$ 가 마진 오차 비율의 상한이자 서포트 벡터 비율의 하한이 되도록 재정식화한다.

5. 커널 — 내적만 바꿔치기[편집]

쌍대문제를 다시 보면 데이터가 오직 $\mathbf x_i^{\mathsf T}\mathbf x_j$ 라는 내적으로만 등장한다. 판정함수도 마찬가지다. 그러면 이 내적을 다른 함수 $k(\mathbf x_i,\mathbf x_j)$ 로 갈아 끼워도 알고리즘 전체가 한 글자도 안 바뀌고 돌아간다. 이것이 커널 트릭이고, 보저·기용·바프닉이 1992년에 SVM에 이식하면서 이 방법을 20세기 말의 주역으로 만들었다.

무엇이 정당한 커널인가? 답은 양정치성이다. 대칭 함수 $k$ 가 임의의 유한 표본에 대해 그람 행렬 $K_{ij}=k(\mathbf x_i,\mathbf x_j)$ 를 항상 양반정치로 만들면, 그에 대응하는 특징사상 $\varphi$ 와 힐베르트 공간이 존재해 $k(\mathbf x,\mathbf y)=\langle\varphi(\mathbf x),\varphi(\mathbf y)\rangle$ 가 성립한다. 콤팩트 정의역 위 연속 커널에 대한 고전적 진술이 머서 정리(1909)이고, 유한 표본만으로 진술하는 현대적 판본이 무어-아론샤인 정리(재생 커널 힐베르트 공간의 존재)다. 실무적으로 중요한 것은 딱 하나 — $K$ 가 양반정치라야 쌍대 목적함수가 오목이 되어 볼록 QP가 유지된다. 이게 깨지면 SMO가 발산하거나 이상한 지역해에 눌러앉는다.

• 선형 $\mathbf x^{\mathsf T}\mathbf y$ — 텍스트처럼 차원이 이미 충분히 높은 데이터의 기본값.
• 다항식 $(\mathbf x^{\mathsf T}\mathbf y + c)^d$ — 특징공간 차원이 $\binom{p+d}{d}$ 로 폭발하지만 계산은 내적 한 번.
• RBF(가우시안) $\exp(-\gamma\lVert\mathbf x-\mathbf y\rVert^2)$ — 특징공간이 무한차원. 서로 다른 점들의 그람 행렬이 항상 full rank라 어떤 데이터든 훈련오차 0을 만들 수 있다. 그래서 $C$ 와 $\gamma$ 가 곧 모형 복잡도이고, 튜닝 없이 쓰면 반드시 과적합한다.
• 시그모이드 $\tanh(\kappa\,\mathbf x^{\mathsf T}\mathbf y + c)$ — 신경망과의 유비 때문에 유명하지만 일반적인 파라미터에서 양반정치가 아니다. “신경망과 동치”라는 마케팅이 만든 좀비 커널에 가깝다.

커널 SVM이 무한차원 공간에서 최적화를 하면서도 유한 계산으로 끝나는 근거는 재현자 정리(Kimeldorf & Wahba, 1971)다 — RKHS 노름으로 정규화된 경험위험 최소화의 해는 반드시 학습점들이 만드는 $\varphi(\mathbf x_i)$ 의 span 안에 있다. 앞의 $\mathbf w = \sum\alpha_i y_i\varphi(\mathbf x_i)$ 는 그 정리의 특수한 경우다. 같은 트릭을 회귀에 쓰면 가우시안 프로세스와 이웃이 되고, 주성분에 쓰면 커널 PCA, 이상 판정에 쓰면 이상치 탐지 문서의 원-클래스 SVM이다.

6. SMO — 왜 두 개씩 푸는가[편집]

쌍대문제는 변수가 $n$ 개인 QP이고, 그람 행렬만 $O(n^2)$ 메모리를 먹는다. $n=10^5$ 이면 배정밀도로 80 GB라 범용 QP 솔버로는 아예 시작이 안 된다. 그래서 표준 해법은 작업집합 분해다 — 승수 몇 개만 자유롭게 두고 나머지를 고정한 부분문제를 반복해 푸는 것.

플랫의 SMO(sequential minimal optimization, 1998)는 이 작업집합을 최소 크기인 2개로 잡는다. 하나가 아니라 둘인 이유는 등식 제약 때문이다.

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

승수 하나만 움직이면 이 합이 곧바로 깨진다. 등식 제약을 유지하면서 움직일 수 있는 최소 개수가 2이고, $\alpha_1 y_1 + \alpha_2 y_2$ 를 상수로 유지한 채 둘을 반대 방향으로 밀면 된다. 그리고 변수 두 개짜리 QP는 상자 제약과 직선 하나가 만드는 선분 위의 1차원 문제라 해석해가 존재한다 — 미제약 최적점

$$\alpha_2^{\text{new}} = \alpha_2 + \frac{y_2(E_1 - E_2)}{\eta}, \qquad \eta = k_{11} + k_{22} - 2k_{12}$$

을 계산해 구간 $[L, H]$ 로 클리핑하면 끝이다($E_i$ 는 현재 예측 오차). 내부 반복도, 수치 선형대수도, 행렬 저장도 없다. QP 솔버를 부르지 않고 QP를 푸는 이 구성이 SMO의 전부이고, 커널 SVM을 연구실 밖으로 내보낸 실질적 사건이었다.³

남는 것은 “어느 두 개를 고를 것인가”이고, 여기가 성능이 갈리는 자리다. KKT 조건을 가장 크게 위반하는 쌍을 고르는 최대위반쌍 규칙(Keerthi 외)이 기본이고, LIBSVM은 목적함수의 2차 정보까지 쓰는 선택 규칙을 쓴다. 커널값 재계산을 막는 LRU 캐시가 실제 실행시간의 절반을 좌우한다는 것도 구현 상식이다. 경험적 복잡도는 대략 $O(n^2)\!\sim\!O(n^3)$ 이라 표본 수십만이면 커널 SVM은 사실상 끝이고, 그때부터는 선형 SVM이나 무작위 푸리에 특징 같은 근사로 갈아탄다.

선형 SVM에는 더 좋은 길이 있다. 절편 $b$ 를 없애거나 특징 벡터에 상수항으로 흡수시키면 위 등식 제약이 사라지고, 그러면 승수 하나씩 갱신하는 좌표하강이 가능해진다. LIBLINEAR의 쌍대 좌표하강(Hsieh 외, 2008)이 이것이며 비용이 비영요소 수에 선형이다. “두 개씩 푸는 이유”가 절편 하나 때문이었다는 사실이 여기서 역으로 드러난다.

7. 힌지 손실 + L2 라는 재해석[편집]

소프트 마진 원문제에서 $\xi_i$ 를 소거해 보자. 제약 $\xi_i \ge 1 - y_i f(\mathbf x_i)$ 와 $\xi_i \ge 0$ 을 동시에 만족하는 최소값은 $\xi_i = \max(0,\,1-y_i f(\mathbf x_i))$ 이고, 최소화 문제이므로 최적점에서 등호가 성립한다. 대입해 $Cn$ 으로 나누면

$$\min_{\mathbf w,b}\ \frac{1}{n}\sum_{i=1}^{n}\max\big(0,\ 1 - y_i f(\mathbf x_i)\big) \;+\; \frac{\lambda}{2}\lVert\mathbf w\rVert^2, \qquad \lambda = \frac{1}{Cn}$$

제약이 하나도 없는 정규화 경험위험 최소화가 된다. 기하학적 이야기였던 마진 최대화가 사실은 힌지 손실 + L2 벌점이었다는 것이며, 이 관점이 SVM을 다른 모든 선형 모형과 같은 언어에 올려놓는다. 손실만 갈아 끼우면 로그 손실은 로지스틱 회귀, 제곱 손실은 능형회귀다. 벌점을 L1으로 바꾸면 라쏘 계열이 되고, 그러면 계수가 희소해지는 대신 앞서 본 서포트 벡터 희소성과는 성격이 완전히 다른 희소성을 얻는다.

힌지와 로그 손실의 차이는 한 지점에 응축된다. 힌지는 $y f \ge 1$ 에서 정확히 0이고, 로그 손실은 어디서도 0이 아니다. 그래서 로지스틱 회귀는 모든 표본이 조금씩 계수에 기여하고(희소성 없음), 대신 확률 $P(y\mid\mathbf x)$ 를 제대로 추정한다. SVM은 반대다 — 희소하지만 $f(\mathbf x)$ 는 확률이 아니다. 확률이 필요하면 플랫 스케일링으로 $f$ 에 로지스틱을 사후 적합해야 하고, 이건 원리에서 나온 것이 아니라 덧댄 것이라 보정이 잘 안 맞는 경우가 흔하다.

이 재해석의 실용적 결실이 Pegasos(Shalev-Shwartz 외, 2007) 같은 확률적 준경사법이다. 힌지 손실의 준경사를 미니배치로 계산해 확률적 경사하강법으로 내려가면, 반복 횟수가 $O(1/\lambda\epsilon)$ 으로 표본 수와 무관해진다. 쌍대·QP·SMO를 전부 우회하고 선형 SVM을 대규모로 푸는 오늘날의 표준 경로다.

8. 딥러닝 이후의 자리[편집]

2012년 이후 이미지·음성·자연어에서 SVM은 사실상 퇴장했다. 이유는 명확하다 — 그람 행렬이 $O(n^2)$ 이라 데이터가 커질수록 불리하고, 커널은 사람이 고르는 고정된 유사도라 표현을 학습하지 않는다. 원시 픽셀에 RBF 커널을 씌우는 것과 합성곱 신경망이 계층적 특징을 학습하는 것 사이의 격차는 튜닝으로 메울 수 있는 종류가 아니다.

그럼에도 SVM이 여전히 기본값인 자리가 있고, 공통점은 표본이 적고 차원이 높다는 것이다.

• 소표본·고차원. 유전자 발현(표본 수십, 변수 수만), 재료 실험, 임상 코호트처럼 $n \ll p$ 인 데이터에서 SVM은 여전히 강하다. 마진 기반 상계가 명시적 차원 의존성을 갖지 않고 $R^2/\gamma^2$ 같은 기하량으로 표현된다는 점이 이 체제와 궁합이 좋다. 데이터가 100개인데 파라미터 수백만 개짜리 망을 학습시키는 것보다, 볼록 QP 하나를 푸는 쪽이 재현성 면에서도 압도적이다.
• 구조화된 입력. 문자열 커널, 그래프 커널, 화학 구조 커널처럼 벡터화가 어려운 대상에 유사도 함수는 정의할 수 있는 경우. 커널 방법의 원래 강점이 그대로 남는다.
• 한 클래스만 있는 문제. 정상 데이터만으로 경계를 학습하는 원-클래스 SVM·SVDD는 이상치 탐지의 고전 도구로 아직 현역이다.
• 회귀 대리모형. $\epsilon$-불감 손실을 쓰는 서포트 벡터 회귀는 대리 모델 후보 중 하나로 남아 있다. 다만 이 자리에서는 불확실성까지 같이 주는 크리깅 쪽이 대체로 우세하다.
• 베이스라인. 새 방법이 SVM을 못 이기면 그 방법은 아직 준비가 안 된 것이다. 이 용도만으로도 SVM은 계속 설치된다.

이론 쪽에서는 오히려 재회가 있었다. 무한 폭 신경망의 학습 동역학이 신경 접선 커널(NTK)이라는 고정 커널을 가진 커널 회귀로 수렴한다는 결과 이후, “깊은 망이 왜 되는가”를 커널 언어로 번역하려는 시도가 이어지고 있다. 커널 방법이 딥러닝에 밀린 자리에서, 딥러닝을 설명하는 도구로 커널이 다시 불려 나온 셈이다.⁴

9. 실무에서 밟는 지뢰[편집]

• 스케일링은 선택이 아니다. RBF 커널의 $\lVert\mathbf x-\mathbf y\rVert$ 안에서 단위가 큰 변수가 거리를 독점한다. 표준화를 안 하고 성능이 안 나온다고 커널을 바꾸는 것이 가장 흔한 오진.
• $C$ 와 $\gamma$ 는 상호작용한다. 따로따로 최적화하면 안 되고 2차원 격자로 훑어야 한다. 로그 스케일 $C \in \{2^{-5},\dots,2^{15}\}$, $\gamma \in \{2^{-15},\dots,2^{3}\}$ 가 LIBSVM 실전 가이드의 오래된 권고다.
• 클래스 불균형. 소수 클래스가 1%면 전부 다수 클래스로 찍는 것이 힌지 손실 기준으로도 유리해진다. 클래스별로 $C$ 를 다르게 주는 것이 표준 처방.
• 다중분류는 원래 없다. SVM은 이진 분류기이고, 다중분류는 일대다·일대일·크래머-싱어 정식화로 덧붙인 것이다. LIBSVM 기본값인 일대일은 $\binom{K}{2}$ 개 모형을 학습하지만 각각이 작아서 실제로는 일대다보다 빠른 경우가 많다.
• 결과가 마음에 안 들면 커널부터 의심하지 마라. 대개는 스케일링, 그다음이 $C$, 그다음이 라벨 품질이다.

10. 관련 문서[편집]

• 로지스틱 회귀 · 결정 트리 · 랜덤 포레스트
• 커널 PCA · 가우시안 프로세스 · 무작위 푸리에 특징
• 이차계획법 · 볼록 최적화 · 쌍대성 · 라그랑주 승수법
• 능형회귀 · 라쏘 · 티호노프 정규화 · 과적합 · 교차검증
• 확률적 경사하강법 · 경사하강법
• 이상치 탐지 · 대리 모델 · 차원의 저주
• 설명 가능한 인공지능 · 심층 학습

11. Footnotes[편집]

1. 물론 SVM도 완전히 결정론적이지는 않다. SMO의 작업집합 선택 순서, 커널 캐시 크기, 부동소수점 합산 순서에 따라 마지막 자릿수는 흔들린다. 다만 “다른 시드로 돌렸더니 정확도가 4%포인트 달라졌다” 같은 일은 벌어지지 않는다는 뜻이다. ↩

2. 이 상계는 꽤 헐겁다. 서포트 벡터가 30%면 “LOO 오차가 30% 이하”라고만 말해 주는데, 실제 오차는 보통 훨씬 작다. 그럼에도 계산이 공짜(학습이 끝나면 이미 알고 있는 수)라서 모형 선택의 1차 필터로는 여전히 쓸모가 있다. ↩

3. SMO 논문이 나온 곳이 학술지가 아니라 마이크로소프트 리서치 테크니컬 리포트였고, 정식 수록은 이듬해 논문집 Advances in Kernel Methods였다. 인용 수 만 단위인 알고리즘의 출처가 사내 리포트인 사례로 종종 언급된다. ↩

4. 이 재회를 두고 “커널이 이겼다”고 읽으면 곤란하다. NTK 체제는 폭이 무한대이고 가중치가 초기값에서 거의 안 움직이는 극한이라, 실제로 특징을 학습해서 이기는 유한 폭 신경망과는 다른 대상이다. 오히려 “NTK로 설명되는 부분은 딥러닝의 강점이 아니다”라는 쪽이 요즘의 해석이다. ↩