SVM과 커널법

 

선형 분류기 (Linear Classifier)

개요

• 정의
  입력 벡터 ( x )를 선형 결정함수로 분류하는 모델.

f(x) = wᵀx + w₀

• 분류 기준
  • ( f(x) > 0 ) → 클래스 +1
  • ( f(x) < 0 ) → 클래스 -1
• 특징
  • 학습 시스템의 복잡도가 낮음
  • 과적합(Overfitting) 문제를 피하기 쉬움
  • 하지만 비선형 경계가 필요한 문제에서는 성능 한계 존재

---

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

개요

• SVM은 일반화 오차(Generalization Error) 를 최소화하기 위해
  마진(Margin) 을 최대화하는 방향으로 학습되는 선형 분류기이다.

---

주요 개념

1) 결정경계 (Decision Boundary)

• 분류를 위한 선형 함수의 형태:

wᵀx + w₀ = 0

---

2) 마진 (Margin)

• 결정경계에서 가장 가까운 데이터(서포트 벡터)까지의 거리.

Margin = 2 / ||w||

---

3) 서포트 벡터 (Support Vector)

• 결정경계에 가장 가까운 데이터 포인트들.
• 마진의 위치를 직접적으로 결정함.

---

4) 최적화 문제 (Optimization Problem)

SVM은 다음 목적함수를 최소화하는 문제로 정의된다.

minimize   (1/2) ||w||²
subject to  yᵢ (wᵀxᵢ + w₀) ≥ 1   for all i

• 목표: 두 클래스 간의 마진을 최대화
• 제약조건: 모든 샘플이 올바른 쪽으로 분류되도록 함

---

학습 과정

① 목적함수 Q(α) 정의

• 라그랑주 승수 ( α_i )를 도입하여 목적함수를 구성:

Q(α) = ∑ αᵢ - 1/2 ∑∑ αᵢ αⱼ yᵢ yⱼ (xᵢ ⋅ xⱼ)

---

② 이차계획법(Quadratic Programming) 으로 최적화

• 제약조건 ( ∑ αᵢ yᵢ = 0 ), ( αᵢ ≥ 0 ) 을 만족하며
  ( Q(α) )를 최대화하는 ( α_i )를 찾음.

---

③ 서포트 벡터 결정

• ( α_i > 0 ) 인 데이터만이 서포트 벡터가 됨.

---

④ 파라미터 계산

• 결정경계의 법선 벡터 ( w ) 계산:

w = ∑ αᵢ yᵢ xᵢ

• 절편 ( w₀ ) 계산:

w₀ = yₖ - wᵀxₖ    // 서포트 벡터 중 하나를 사용

---

⑤ 모델 저장

• 서포트 벡터 집합, ( α_i ), ( w₀ )를 저장하여 분류 단계에서 사용.

---

인식/분류 단계

새로운 데이터 ( x )가 주어졌을 때 판별함수를 계산한다.

f(x) = ∑ αᵢ yᵢ (xᵢ ⋅ x) + w₀

• ( f(x) > 0 ) → 클래스 +1
• ( f(x) < 0 ) → 클래스 -1

---

다중 클래스 분류

• SVM은 기본적으로 이진 분류기이므로,
  다중 클래스 문제는 다음 방식으로 확장한다.

1. One-vs-Rest (1대 나머지)
   • 각 클래스 vs 나머지 모든 클래스 학습
     → 총 ( K )개의 분류기 생성.
2. One-vs-One (1대1)
   • 클래스 쌍마다 분류기 생성
     → 총 ( K(K-1)/2 )개의 분류기 생성.

---

슬랙 변수 (Slack Variable)

• 선형 분리가 불가능한 데이터를 처리하기 위한 허용 변수.

yᵢ (wᵀxᵢ + w₀) ≥ 1 - ξᵢ

• ( ξ_i ): 데이터 ( x_i )의 오분류 정도(0 이상)
• 슬랙변수 ( ξ_i )가 클수록 더 큰 오분류 허용

최종 목적함수:

minimize   (1/2)||w||² + C ∑ ξᵢ

• ( C ): 오분류를 얼마나 허용할지 결정하는 규제 파라미터

---

커널법 (Kernel Method)

개요

• 비선형 문제를 해결하기 위해 입력 데이터를 고차원 특징 공간으로 매핑하고,
  그 공간에서 선형 분류를 수행.

---

고차원 매핑 개념

x ∈ ℝⁿ   →   Φ(x) ∈ ℝᵐ   (m >> n)

그러나 실제로 ( Φ(x) )를 명시적으로 계산하면 연산량 폭증.
→ 대신 커널 함수(Kernel Function) 를 사용해 내적을 직접 계산하지 않고 대체.

---

커널 함수 정의

k(x, y) = Φ(x) ⋅ Φ(y)

• 두 데이터의 고차원 내적을 직접 계산하지 않고
  커널 함수 ( k(x, y) )로 대체함.

---

대표 커널 함수

선형 커널 (Linear)	k(x, y) = x ⋅ y	기본 SVM과 동일
다항식 커널 (Polynomial)	k(x, y) = (x ⋅ y + c)ᵈ	다항 차수를 통한 비선형 경계
시그모이드 커널 (Sigmoid)	k(x, y) = tanh(κ (x ⋅ y) + c)	뉴럴넷 형태와 유사
가우시안 RBF 커널	```k(x, y) = exp(-

---

커널 SVM 판별식

f(x) = ∑ αᵢ yᵢ k(xᵢ, x) + w₀

• 입력 데이터를 고차원으로 매핑하지 않고도
  비선형 결정경계를 학습할 수 있음.