SVM(Support Vector Machine)

SVM (Support Vector Machine)은 지도 학습 알고리즘 중 하나로, 분류 및 회귀 문제를 해결하는 데 사용됩니다. 특히, 선형 분리가 가능한 데이터셋에서 가장 널리 사용되며, 커널 트릭을 사용하여 선형적으로 분리되지 않는 데이터도 처리할 수 있습니다.

기본 개념

SVM은 두 클래스를 분리하는 최적의 초평면(optimal hyperplane)을 찾는 알고리즘입니다. 이 초평면은 클래스 간의 마진(margin)을 최대화하는 방향으로 설정됩니다.

• 마진: 초평면과 가장 가까운 데이터 포인트(서포트 벡터) 사이의 거리.
• 서포트 벡터: 마진 경계에 위치한 데이터 포인트들.

---

수식

주어진 데이터셋 $(\mathbf{x}_i, y_i)$, $i = 1, \dots, N$에서:

• $\mathbf{x}_i \in \mathbb{R}^d$ : $i$-번째 샘플의 특징 벡터
• $y_i \in \{-1, +1\}$ : $i$-번째 샘플의 클래스 레이블

초평면은 다음과 같은 식으로 표현됩니다:

$\mathbf{w} \cdot \mathbf{x} + b = 0$

여기서:

• $\mathbf{w}$: 초평면의 법선 벡터 (normal vector)
• $b$: 초평면의 절편

초평면으로부터 데이터 포인트까지의 거리 :

$\text{distance} = \frac{|\mathbf{w} \cdot \mathbf{x} + b|}{\|\mathbf{w}\|}$

마진의 크기 :

$\text{margin} = \frac{2}{\|\mathbf{w}\|}$

두 서포트 벡터들 사이의 전체 마진은 $\frac{2}{\|\mathbf{w}\|}$가 됩니다.

마진을 최대화하기 위해, 다음 최적화 문제를 풉니다 :

$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$

제약 조건:

$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad \forall i$

이 조건은 데이터 포인트가 초평면의 올바른 한쪽에 위치하도록 보장합니다.

---

예제

마진을 최대화 하기 위한 최적화 문제

두 개의 클래스가 주어지고, 각 클래스에 대해 데이터 포인트가 다음과 같이 분포한다고 가정합니다:

• 클래스 $+1$의 데이터 포인트: $(1, 2)$, $(2, 3)$
• 클래스 $-1$의 데이터 포인트: $(4, 6)$, $(5, 7)$

이 데이터를 분리하는 초평면을 찾는 것이 목표입니다.

1. 최적화 문제 설정

먼저, 초평면을 정의합니다:

$\mathbf{w} \cdot \mathbf{x} + b = 0$

여기서:

• $\mathbf{w}$는 초평면의 법선 벡터.
• $b$는 절편입니다.

각 데이터 포인트 $\mathbf{x}_i$에 대해, 마진은 다음과 같이 정의됩니다:

$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 \quad \forall i$

2. 기호

1. $\forall$

• 의미: "모든" 또는 "임의의"를 뜻합니다. 수학적 정의에서 이 기호는 주어진 조건이 모든 $i$에 대해 성립함을 나타낼 때 사용됩니다.

• 예시:

  $\forall x \in \mathbb{R}, \, x^2 \geq 0$

  위 수식은 "모든 실수 $x$에 대해 $x^2$는 0보다 크거나 같다"는 의미입니다.

2. $\|\mathbf{w}\|$

• 의미: 벡터 $\mathbf{w}$의 유클리드 노름 (Euclidean norm) 또는 길이를 나타냅니다. 벡터 $\mathbf{w} = (w_1, w_2, \dots, w_n)$에 대해 노름은 다음과 같이 계산됩니다:

  $\|\mathbf{w}\| = \sqrt{w_1^2 + w_2^2 + \dots + w_n^2}$

• 예시:

  • $\mathbf{w} = (3, 4)$일 때, $\|\mathbf{w}\| = \sqrt{3^2 + 4^2} = 5$

3. 데이터 포인트

데이터 포인트가 다음과 같다고 가정합시다:

• 클래스 $+1$의 데이터 포인트 $(1, 2)$와 $(2, 3)$
• 클래스 $-1$의 데이터 포인트 $(4, 6)$와 $(5, 7)$

따라서, 데이터셋은 다음과 같습니다:

• $\mathbf{x}_1 = (1, 2), y_1 = +1$

• $\mathbf{x}_2 = (2, 3), y_2 = +1$

• $\mathbf{x}_3 = (4, 6), y_3 = -1$

• $\mathbf{x}_4 = (5, 7), y_4 = -1$

이때, 최적화 문제는 다음과 같이 설정됩니다:

$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$

제약 조건:

• $+1 \cdot (\mathbf{w} \cdot (1, 2) + b) \geq 1$

• $+1 \cdot (\mathbf{w} \cdot (2, 3) + b) \geq 1$

• $-1 \cdot (\mathbf{w} \cdot (4, 6) + b) \geq 1$

• $-1 \cdot (\mathbf{w} \cdot (5, 7) + b) \geq 1$

데이터 포인트 $\mathbf{x}_i$와 클래스 $y_i$를 곱하는 이유는 양성 및 음성 클래스 모두에 대해 단일한 제약 조건을 적용하기 위함입니다.

이 문제를 풀면 최적의 $\mathbf{w}$와 $b$를 얻을 수 있습니다.

4. 라그랑주 승수법

라그랑주

위에서 만든 최적화 문제 풀기

각 제약 조건에 대해 라그랑주 승수 $\alpha_i$를 도입합니다.

라그랑주 함수는 다음과 같이 정의됩니다:

$L(\mathbf{w}, b, \alpha_1, \alpha_2, \alpha_3, \alpha_4) = \frac{1}{2} \|\mathbf{w}\|^2 - \alpha_1 (y_1 (\mathbf{w} \cdot \mathbf{x}_1 + b) - 1) - \alpha_2 (y_2 (\mathbf{w} \cdot \mathbf{x}_2 + b) - 1) - \alpha_3 (y_3 (\mathbf{w} \cdot \mathbf{x}_3 + b) - 1) - \alpha_4 (y_4 (\mathbf{w} \cdot \mathbf{x}_4 + b) - 1)$

여기서:

• $\alpha_i$ 는 제약 조건입니다.
• $\alpha_i \geq 0$입니다.

---

4-1. 라그랑주 함수의 일반적인 형태: 제약 조건을 "만족하도록"

제약 조건 $g_i(\mathbf{w}, b) \leq 0$가 있을 때, 이를 라그랑주 승수로 목적 함수와 연결하면 다음과 같이 표현됩니다:

$L(\mathbf{w}, b, \boldsymbol{\alpha}) = f(\mathbf{w}, b) + \sum_{i} \alpha_i g_i(\mathbf{w}, b)$

이 형태에서는 제약 조건이 $g_i(\mathbf{w}, b) \leq 0$일 때 $\alpha_i g_i$가 양수가 되면서 적절히 페널티를 가합니다.

• KKT 조건 중 Dual feasibility에 따라 $\alpha \geq 0$ 입니다.

---

4-2. 문제에 주어진 형태: 제약 조건을 "만족시키지 않을 때 벌점"

지금 주어진 식에서는 제약 조건이 다음과 같은 형태로 표현됩니다:

$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1 \geq 0$

이때, 제약 조건이 위반되었을 때 벌점을 주기 위해 $-\alpha_i$가 사용됩니다. 따라서 라그랑주 함수는 다음과 같이 구성됩니다:

$L(\mathbf{w}, b, \boldsymbol{\alpha}) = f(\mathbf{w}, b) - \sum_{i} \alpha_i (y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1)$

• KKT 조건 중 Dual feasibility에 따라 $\alpha \geq 0$ 입니다.

• $y_i \in \{-1, +1\}$ : 클래스

---

5.라그랑주 함수의 편미분

라그랑주 함수에 대해 $\mathbf{w}$, $b$, $\alpha_1$, $\alpha_2$, $\alpha_3$, $\alpha_4$에 대해 편미분하여 최적화 문제를 풉니다.

$\mathbf{w}$에 대한 편미분:

$\frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^{4} \alpha_i y_i \mathbf{x}_i = 0$

$b$에 대한 편미분:

$\frac{\partial L}{\partial b} = - \sum_{i=1}^{4} \alpha_i y_i = 0$

$\alpha_i$에 대한 편미분:

각 $\alpha_i$에 대해 다음 조건을 만족해야 합니다:

$\alpha_i \geq 0, \quad \alpha_i (y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1) = 0$

이 조건은 KKT 조건을 만족하는 것으로, 각 $\alpha_i$는 대응하는 제약 조건이 활성화된 경우에만 0이 아니게 됩니다.

6. 쌍대 문제로 변환

최적화 문제를 쌍대 문제로 변환하기 위해, $\mathbf{w}$와 $b$를 라그랑주 함수에서 제거하고 $\alpha_i$만을 포함하는 식을 얻습니다.

$\mathbf{w}, b$에 대한 편미분 결과

• $\mathbf{w} = \sum_{i=1}^{4} \alpha_i y_i \mathbf{x}_i$

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

$\mathbf{w} = \sum_{i=1}^{4} \alpha_i y_i \mathbf{x}_i$를 대입하면, 쌍대 문제는 다음과 같습니다:

$q(\alpha) = \max_{\alpha} \left( \sum_{i=1}^{4} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{4} \alpha_i \alpha_j y_i y_j \mathbf{x}_i \cdot \mathbf{x}_j \right)$

제약 조건:

$\alpha_i \geq 0, \quad \sum_{i=1}^{4} \alpha_i y_i = 0$

쌍대 문제를 풀면 최적의 $\alpha_i$ 값을 찾을 수 있고, 이를 통해 최적의 $\mathbf{w}$와 $b$를 계산할 수 있습니다.

7. SMO 알고리즘

이어서

SMO (Sequential Minimal Optimization) 알고리즘은 서포트 벡터 머신(SVM)의 최적화 문제를 해결하는데 사용됩니다. SVM에서의 최적화 문제는 일반적으로 쌍대 문제를 풀어야 하며, SMO는 이를 해결하기 위해 두 개의 변수 $\alpha_i$와 $\alpha_j$를 순차적으로 최적화합니다. 각 $\alpha_i$는 라그랑주 승수이고, SMO는 이를 최소화하는 방법으로 최적의 $\mathbf{w}$와 $b$를 찾습니다.

---

소프트 마진 SVM

실제 데이터에서는 선형적으로 완벽하게 구분되지 않는 경우가 많습니다.
이를 해결하기 위해 소프트 마진이 도입됩니다.

$\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i$

제약 조건:

$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad \forall i$

여기서:

• $\xi_i$: 슬랙 변수(slack variable), 허용 오차를 나타냄.
• $C$: 마진과 분류 오차 간의 트레이드오프를 조정하는 하이퍼파라미터.

---

커널 SVM

선형 분리가 불가능한 데이터를 처리하기 위해 커널 트릭을 사용하여, 입력 데이터를 고차원 공간으로 매핑합니다:

$\phi: \mathbf{x} \to \phi(\mathbf{x})$

초평면은 새로운 특징 공간에서 찾습니다:

$\mathbf{w} \cdot \phi(\mathbf{x}) + b = 0$

커널 함수 $K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)$를 사용하여, 고차원 매핑을 명시적으로 계산하지 않아도 됩니다.

일반적인 커널 함수는 다음과 같습니다:

• Linear kernel: $K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i \cdot \mathbf{x}_j$

• Polynomial kernel: $K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j + c)^d$

• RBF kernel: $K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$
  (Radial Basis Function, Gaussian)

• Sigmoid kernel : $K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\alpha \mathbf{x}_i \cdot \mathbf{x}_j + c)$

---

라그랑주 듀얼 형식과 커널

SVM의 최적화 문제는 라그랑주 듀얼 형식으로 변환되어 해결되며, 결정 함수는 다음과 같습니다:

$f(\mathbf{x}) = \text{sgn}\left(\sum_{i=1}^N \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b\right)$

여기서:

• $\alpha_i$: 라그랑주 승수.
• $K(\mathbf{x}_i, \mathbf{x})$: 커널 함수.
• $\text{sgn}$은 부호 함수 (sign function)를 나타냅니다.
  이 함수는 입력값이 양수인지 음수인지를 판별하고, 그에 따라 1 또는 -1을 반환하는 함수입니다.
  $\text{sgn}(z) = \begin{cases} 1 & \text{if } z > 0 \\ 0 & \text{if } z = 0 \\ -1 & \text{if } z < 0 \end{cases}$

---