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

두 클래스 사이에서 가장 넓은 길을 찾습니다. 이게 전체 아이디어입니다.

유형: Build 언어: Python 선수 지식: Phase 1 (08 최적화, 14 노름과 거리(Norms and Distances), 18 볼록 최적화(Convex Optimization)) 예상 시간: 약 90분

학습 목표

• 힌지 손실(Hinge loss)과 원문제(Primal formulation)의 경사하강법(Gradient descent)을 사용해 선형 SVM(Linear SVM)을 처음부터 구현합니다.
• 최대 마진 원리(Maximum margin principle)를 설명하고, 학습된 모델에서 서포트 벡터(Support vector)를 식별합니다.
• 선형(Linear), 다항식(Polynomial), RBF 커널(RBF kernel)을 비교하고, 커널 트릭(Kernel trick)이 명시적인 고차원 매핑 없이 어떻게 동작하는지 설명합니다.
• C 파라미터(C parameter)가 마진 너비와 분류 오류 사이의 절충을 어떻게 제어하는지 평가합니다.

문제

두 클래스의 데이터 포인트가 있고, 이를 나누는 선 또는 초평면(Hyperplane)을 그려야 합니다. 가능한 선은 무한히 많습니다. 그중 무엇을 골라야 할까요?

가장 큰 마진(Margin)을 갖는 선을 골라야 합니다. 마진은 결정 경계(Decision boundary)와 양쪽 클래스에서 가장 가까운 데이터 포인트 사이의 거리입니다. 마진이 넓을수록 분류기는 더 확신 있게 판단하고, 보지 못한 데이터에도 더 잘 일반화됩니다.

이 직관은 머신러닝에서 가장 수학적으로 우아한 알고리즘 중 하나인 서포트 벡터 머신(Support Vector Machine, SVM)으로 이어집니다. SVM은 딥러닝 이전에 지배적인 분류 방법이었고, 지금도 작은 데이터셋, 고차원 데이터, 이론적 보장이 있는 잘 이해된 모델이 필요한 문제에서 좋은 선택지입니다.

SVM은 Phase 1과 직접 연결됩니다. 최적화는 볼록 최적화(Convex optimization)이고, 마진은 노름(Norm)으로 측정하며, 커널 트릭은 점곱(Dot product)을 이용해 고차원 공간을 직접 계산하지 않고도 비선형 경계를 다룹니다.

개념

최대 마진 분류기

라벨 y_i가 {-1, +1}이고 특성 벡터가 x_i인 선형 분리 가능 데이터가 있다고 해봅니다. 목표는 두 클래스를 나누는 초평면 w^T x + b = 0을 찾는 것입니다.

점 x_i에서 초평면까지의 거리는 다음과 같습니다.

distance = |w^T x_i + b| / ||w||

올바르게 분류된 점은 y_i * (w^T x_i + b) > 0을 만족합니다. 마진은 초평면에서 양쪽의 가장 가까운 점까지 거리의 두 배입니다.

graph LR
    subgraph Margin
        direction TB
        A["w^T x + b = +1"] ~~~ B["w^T x + b = 0"] ~~~ C["w^T x + b = -1"]
    end
    D["+ 클래스 점"] --> A
    E["- 클래스 점"] --> C
    B --- F["결정 경계"]

최적화 문제는 다음과 같습니다.

maximize    2 / ||w||     (마진 너비)
subject to  y_i * (w^T x_i + b) >= 1  for all i

동일하게, ||w||^2를 최소화하는 형태가 더 다루기 쉽습니다.

minimize    (1/2) ||w||^2
subject to  y_i * (w^T x_i + b) >= 1  for all i

이는 볼록 이차 계획(Convex quadratic program)입니다. 전역 최적해가 유일하게 존재합니다. 마진 경계 위에 정확히 놓인 데이터 포인트, 즉 y_i * (w^T x_i + b) = 1인 점이 서포트 벡터입니다. 이 점들만 결정 경계를 정합니다. 서포트 벡터가 아닌 점을 움직이거나 제거해도 경계는 바뀌지 않습니다.

서포트 벡터: 중요한 소수

graph TD
    subgraph Classification
        SV1["서포트 벡터(+ 클래스)<br>y(w'x+b) = 1"] --- DB["결정 경계<br>w'x+b = 0"]
        DB --- SV2["서포트 벡터(- 클래스)<br>y(w'x+b) = 1"]
    end
    O1["다른 + 점<br>(경계에 영향 없음)"] -.-> SV1
    O2["다른 - 점<br>(경계에 영향 없음)"] -.-> SV2

대부분의 학습 포인트는 경계 결정에 직접 필요하지 않습니다. 서포트 벡터만 중요합니다. 그래서 SVM은 예측 시점에 전체 학습 세트가 아니라 서포트 벡터만 저장하면 되므로 메모리 효율적입니다.

서포트 벡터의 개수는 일반화 오류의 경계도 제공합니다. 데이터셋 크기에 비해 서포트 벡터가 적을수록 일반화가 더 좋다는 신호입니다.

소프트 마진: C 파라미터로 노이즈 다루기

실제 데이터는 완벽히 분리되지 않는 경우가 많습니다. 어떤 점은 경계의 잘못된 쪽에 있거나, 마진 안쪽에 있을 수 있습니다. 소프트 마진(Soft margin)은 슬랙 변수(Slack variable)를 도입해 이런 위반을 허용합니다.

minimize    (1/2) ||w||^2 + C * sum(xi_i)
subject to  y_i * (w^T x_i + b) >= 1 - xi_i
            xi_i >= 0  for all i

슬랙 변수 xi_i는 점 i가 마진을 얼마나 위반했는지 측정합니다. C는 절충을 제어합니다.

C는 정규화 강도(Regularization strength)의 역수입니다. 큰 C는 정규화가 약하고, 작은 C는 정규화가 강합니다.

힌지 손실: SVM의 손실 함수

소프트 마진 SVM은 제약 없는 최적화 문제로 다시 쓸 수 있습니다.

minimize    (1/2) ||w||^2 + C * sum(max(0, 1 - y_i * (w^T x_i + b)))

max(0, 1 - y_i * f(x_i)) 항이 힌지 손실입니다. 점이 올바르게 분류되고 마진 바깥에 있으면 손실은 0입니다. 점이 마진 안쪽에 있거나 잘못 분류되면 선형으로 벌점을 줍니다.

단일 점의 힌지 손실:

loss
  |
  | \
  |  \
  |   \
  |    \
  |     \_______________
  |
  +-----|-----|-------->  y * f(x)
       0     1

y*f(x) >= 1이면 손실은 0입니다. 올바르게 분류되고 마진 바깥에 있다는 뜻입니다.
y*f(x) < 1이면 선형 벌점이 적용됩니다.

로지스틱 회귀(Logistic regression)의 로지스틱 손실(Logistic loss)과 비교해봅니다.

Hinge:     max(0, 1 - y*f(x))          마진에서 단단히 끊김
Logistic:  log(1 + exp(-y*f(x)))        매끄럽고, 정확히 0이 되지 않음

힌지 손실은 희소한 해(Sparse solution)를 만듭니다. 서포트 벡터만 0이 아닌 기여를 합니다. 로지스틱 손실은 모든 데이터 포인트를 사용합니다. 그래서 SVM은 예측 시점에 더 메모리 효율적일 수 있습니다.

경사하강법으로 선형 SVM 학습하기

제약 이차 계획법(Quadratic Programming; QP) 솔버를 풀지 않고도, 힌지 손실과 L2 정규화에 대해 경사하강법을 적용해 선형 SVM을 학습할 수 있습니다.

L(w, b) = (lambda/2) * ||w||^2 + (1/n) * sum(max(0, 1 - y_i * (w^T x_i + b)))

w에 대한 기울기(gradient):
  If y_i * (w^T x_i + b) >= 1:  dL/dw = lambda * w
  If y_i * (w^T x_i + b) < 1:   dL/dw = lambda * w - y_i * x_i

b에 대한 기울기(gradient):
  If y_i * (w^T x_i + b) >= 1:  dL/db = 0
  If y_i * (w^T x_i + b) < 1:   dL/db = -y_i

이를 원문제(Primal formulation)라고 합니다. 한 에포크(epoch)당 시간 복잡도는 O(n * d)입니다. 여기서 n은 샘플 수, d는 특성 수입니다. 텍스트 분류처럼 크고 희소하며 고차원인 데이터에서는 이 방식이 빠릅니다.

쌍대 문제와 커널 트릭

SVM 문제의 라그랑주 쌍대(Lagrangian dual)는 Phase 1 Lesson 18의 KKT 조건과 연결됩니다.

maximize    sum(alpha_i) - (1/2) * sum_ij(alpha_i * alpha_j * y_i * y_j * (x_i . x_j))
subject to  0 <= alpha_i <= C
            sum(alpha_i * y_i) = 0

쌍대 문제에는 데이터 포인트 사이의 점곱 x_i . x_j만 등장합니다. 이것이 핵심입니다. 모든 점곱을 커널 함수 K(x_i, x_j)로 바꾸면, SVM은 변환을 명시적으로 계산하지 않고도 비선형 경계를 학습할 수 있습니다.

Linear kernel:      K(x, z) = x . z
Polynomial kernel:  K(x, z) = (x . z + c)^d
RBF (Gaussian):     K(x, z) = exp(-gamma * ||x - z||^2)

RBF 커널은 데이터를 무한 차원 공간으로 매핑하는 것처럼 동작합니다. 입력 공간에서 가까운 점은 커널 값이 1에 가깝고, 멀리 있는 점은 0에 가깝습니다. 부드러운 결정 경계를 학습할 수 있습니다.

graph LR
    subgraph "입력 공간(분리 불가)"
        A["2D 데이터 포인트<br>원형 경계"]
    end
    subgraph "특성 공간(분리 가능)"
        B["고차원 데이터 포인트<br>선형 경계"]
    end
    A -->|"커널 트릭<br>K(x,z) = phi(x).phi(z)"| B

커널 트릭은 실제로 그 공간에 가지 않고도 고차원 공간의 점곱을 계산합니다. D차원에서 d차 다항식 커널을 명시적으로 펼치면 특성 공간은 O(D^d) 차원이 됩니다. 하지만 K(x, z)는 O(D) 시간에 계산됩니다.

회귀용 SVM: SVR

서포트 벡터 회귀(Support Vector Regression; SVR)는 데이터 주변에 너비 엡실론(epsilon)의 튜브를 맞춥니다. 튜브 안의 점은 손실이 0입니다. 튜브 밖의 점은 선형으로 벌점을 받습니다.

minimize    (1/2) ||w||^2 + C * sum(xi_i + xi_i*)
subject to  y_i - (w^T x_i + b) <= epsilon + xi_i
            (w^T x_i + b) - y_i <= epsilon + xi_i*
            xi_i, xi_i* >= 0

엡실론(epsilon) 파라미터는 튜브 너비를 제어합니다. 튜브가 넓으면 서포트 벡터가 적고 더 부드러운 적합이 됩니다. 튜브가 좁으면 서포트 벡터가 많고 더 촘촘한 적합이 됩니다.

SVM이 딥러닝에 밀린 이유와 아직 강한 경우

SVM은 1990년대 후반부터 2010년대 초반까지 머신러닝을 지배했습니다. 딥러닝이 이를 넘어선 이유는 다음과 같습니다.

그래도 SVM은 다음 상황에서 여전히 강합니다.

• 작은 데이터셋(수백에서 수천 샘플)
• 고차원 희소 데이터(TF-IDF 특성을 사용하는 텍스트 등)
• 수학적 보장, 예를 들어 마진 경계가 필요한 경우
• 학습 시간이 매우 짧아야 하는 경우, 특히 선형 SVM
• 명확한 마진 구조가 있는 이진 분류
• 이상 탐지(One-class SVM)

만들어 보기

Step 1: 힌지 손실과 기울기(gradient)

기반부터 만듭니다. 배치에 대한 힌지 손실과 기울기(gradient)를 계산합니다.

def hinge_loss(X, y, w, b):
    n = len(X)
    total_loss = 0.0
    for i in range(n):
        margin = y[i] * (dot(w, X[i]) + b)
        total_loss += max(0.0, 1.0 - margin)
    return total_loss / n

Step 2: 경사하강법으로 선형 SVM 학습하기

정규화된 힌지 손실을 최소화하며 학습합니다. 이차 계획법(QP) 솔버는 필요하지 않습니다.

class LinearSVM:
    def __init__(self, lr=0.001, lambda_param=0.01, n_epochs=1000):
        self.lr = lr
        self.lambda_param = lambda_param
        self.n_epochs = n_epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_features = len(X[0])
        self.w = [0.0] * n_features
        self.b = 0.0

        for epoch in range(self.n_epochs):
            for i in range(len(X)):
                margin = y[i] * (dot(self.w, X[i]) + self.b)
                if margin >= 1:
                    self.w = [wj - self.lr * self.lambda_param * wj
                              for wj in self.w]
                else:
                    self.w = [wj - self.lr * (self.lambda_param * wj - y[i] * X[i][j])
                              for j, wj in enumerate(self.w)]
                    self.b -= self.lr * (-y[i])

    def predict(self, X):
        return [1 if dot(self.w, x) + self.b >= 0 else -1 for x in X]

Step 3: 커널 함수

선형, 다항식, RBF 커널을 구현합니다.

def linear_kernel(x, z):
    return dot(x, z)

def polynomial_kernel(x, z, degree=3, c=1.0):
    return (dot(x, z) + c) ** degree

def rbf_kernel(x, z, gamma=0.5):
    diff = [xi - zi for xi, zi in zip(x, z)]
    return math.exp(-gamma * dot(diff, diff))

Step 4: 마진과 서포트 벡터 식별

학습이 끝난 뒤 어떤 점이 서포트 벡터인지 찾고 마진 너비를 계산합니다.

def find_support_vectors(X, y, w, b, tol=1e-3):
    support_vectors = []
    for i in range(len(X)):
        margin = y[i] * (dot(w, X[i]) + b)
        if abs(margin - 1.0) < tol:
            support_vectors.append(i)
    return support_vectors

모든 데모(demo)를 포함한 전체 구현은 code/svm.py에서 확인합니다.

사용하기

scikit-learn을 사용할 때는 다음과 같이 구성합니다.

from sklearn.svm import SVC, LinearSVC, SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", C=1.0, gamma="scale")),
])
clf.fit(X_train, y_train)
print(f"정확도: {clf.score(X_test, y_test):.4f}")
print(f"서포트 벡터 수: {clf['svm'].n_support_}")

중요합니다. SVM을 학습하기 전에는 항상 특성을 스케일링해야 합니다. SVM은 특성 크기에 민감합니다. 마진이 ||w||에 의존하기 때문에, 스케일되지 않은 특성은 기하 구조를 왜곡합니다.

큰 데이터셋에서는 SVC 대신 LinearSVC를 사용합니다. LinearSVC는 원문제 방식으로 에포크(epoch)당 O(n)에 가깝게 동작하지만, SVC의 커널 쌍대 방식은 O(n^2)에서 O(n^3)까지 커질 수 있습니다.

from sklearn.svm import LinearSVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", LinearSVC(C=1.0, max_iter=10000)),
])

연습문제

1. 2D 선형 분리 가능 데이터셋을 만듭니다. LinearSVM을 학습하고 서포트 벡터를 식별합니다. 서포트 벡터가 결정 경계에 가장 가까운 점인지 확인합니다.

2. 노이즈가 있는 데이터셋에서 C를 0.001부터 1000까지 바꿔봅니다. 각 C 값에 대한 결정 경계를 그립니다. 넓은 마진의 과소적합에서 좁은 마진의 과적합으로 이동하는 과정을 관찰합니다.

3. 클래스 경계가 원형인, 즉 선형이 아닌 데이터셋을 만듭니다. 선형 SVM이 실패한다는 것을 보입니다. RBF 커널 행렬을 계산하고, 커널이 유도한 특성 공간에서는 클래스가 분리될 수 있음을 보입니다.

4. 같은 데이터셋에서 힌지 손실과 로지스틱 손실을 비교합니다. 선형 SVM과 로지스틱 회귀를 학습합니다. 각 모델의 결정 경계에 기여하는 학습 포인트가 몇 개인지 셉니다. SVM은 서포트 벡터, 로지스틱 회귀는 모든 포인트가 관여합니다.

5. SVR의 엡실론 비민감 손실(epsilon-insensitive loss)을 구현합니다. y = sin(x) + noise에 맞추고, 예측 주변의 엡실론 튜브를 그린 뒤 튜브 밖의 서포트 벡터를 강조합니다.

핵심 용어

더 읽을거리

• Vapnik: The Nature of Statistical Learning Theory (1995) — SVM과 통계적 학습 이론의 기반이 되는 책입니다.
• Cortes & Vapnik: Support-vector networks (1995) — SVM의 원 논문입니다.
• Platt: Sequential Minimal Optimization (1998) — SVM 학습을 실용적으로 만든 SMO 알고리즘 설명입니다.
• scikit-learn SVM documentation — scikit-learn SVM 구현과 사용상의 주의점을 확인할 수 있습니다.
• LIBSVM: A Library for Support Vector Machines — 많은 SVM 구현의 기반이 되는 C++ 라이브러리입니다.