SVM

SVM

• 서포트 벡터 머신 (large margin classifier)
• 마진을 최대로 하는 결정 경계로 분류

마진

• 마진이 클수록 일반화 성능이 좋음
• 경계에 가까울 수록 분류기는 적은 확신의 결론을 내림

서포트 벡터

• 정의: 결정 경계에 가장 가까이 있는 데이터 포인트
• 목표: 서포트 벡터와 결정 경계 사이의 거리를 최대화함으로써, 일반화 성능을 향상시키기
• 양의 초평면 또는 음의 초평면 위에 위치
• 결정 경계의 위치와 방향을 정의
• 결정 경계를 계산하는데 사용, 메모리와 계산 측면에서 효율적

양의 초평면과 음의 초평면

• 양의 초평면과 음의 초평면이 마진을 정의함.
• 양의 초평면: $w^{T}x+b=1$
• 음의 초평면: $w^{T}x+b=-1$

종류

• 선형 SVM
• 비선형 SVM
• 하드 마진 SVM: 이상치 불허
• 소프트 마진 SVM: 이상치 허용

풀이법

• 라그랑주 승수
• KKT 컨디션

이차 계획법과 라그랑주 승수

이차 계획법

• 목적함수는 2차이고 제약조건은 1차 함수인 최적화 문제
• 계산이 효율적임
• 문제가 convex 하여 전역 최솟값이 존재함

라그랑주 해법

• 이차 계획법 문제를 라그랑주 승수로 쉽게 풀 수 있음
• 원본 함수의 최소값 문제를 듀얼의 최댓값 문제로 품

SVM 의 마진 계산하기

• margin 계산
  • $margin = distance(x^+, x^-) = (x^+ - x^-) = ||x^+ - x^-||_2$
  • $x^{+}$와 $x^{-}$의 관계를 이용합니다. (즉, $x^{+} = x^{-} + \lambda w$)
  • 계산
    • $\text{margin}$
    • $= ||x^- + \lambda w - x^-||_2$
    • $= ||\lambda w||_2 = \lambda ||w||_2$
    • $=\lambda \sqrt{w^t w}$

• $\lambda$ 계산하기

  • $w^T x^+ + b = 1$ 에 $x^{+} = x^{-} + \lambda w$ 대입
  • $\rightarrow w^T(x^- + \lambda w) + b = 1$
  • $\rightarrow (w^T x^- + b) + \lambda w^T w = 1$
  • $\rightarrow \lambda ||w||^2 = 2 \Rightarrow \lambda = \frac{2}{||w||^2} \Rightarrow \lambda = \frac{2}{w^t w}$ (여기서 $w^T x^- + b = -1$ 이므로)

• 위의 두 식을 합치면

  1. $\text{margin}=\lambda \sqrt{w^t w}$
  2. $\lambda = \frac{2}{w^t w}$

• $\text{Margin} = \frac{2}{||w||^2} \times ||w|| = \frac{2}{||w||}$

SVM 목적 함수 정의

• 우리는 $\frac{2}{||w||}$ 를 최대화 해야합니다.

• 이는 $\frac{1}{2}||w||^2_2$ 를 최소화 하는 것과 같습니다.

• 왜 $||w||$ 대신 $||w||_{2}^{2}$를 사용하는가?

  • 도함수 계산을 간단하게 함
  • convex 한 2차 함수로 만들어 글로벌 미니멈을 갖도록 함

• 왜 $||w||$ 대신 $\frac{1}{2}$ 을 곱해서 사용하는가?

  • 미분시 깔끔해지려고 (결과 (최적의 w)에는 영향을 미치지 않음)

• 목적 함수: 마진 최대화 하기
  • $obj.function=\min \frac{1}{2}||w||^2_2$
• 제약 조건: 데이터가 올바르게 분류 되도록 보장
  • $w^t x + b \ge \pm 1$
  • $y_i(w^T x_i + b) \ge 1$

KKT 조건

1. 정지조건 (Stationarity):

• $w = \sum_{i}\alpha_i y_i x_i$
• $\sum_{i}\alpha_i y_i = 0$

2. 원문제 제약조건 (Primal feasibility):

• $y_i(w\cdot x_i + b) \ge 1$

3. 쌍대 문제 제약조건 (Dual feasibility):

• $\alpha_i \ge 0$

4. 상보적 여유성 (Complementary slackness):

• $\alpha_i(y_i(w\cdot x_i + b) - 1) = 0$

HARD SVM

선형 분리 가능한 데이터만 취급

목표

• 마진을 최대화 하는 결정 경계 찾기: $max \frac{2}{||w||}$
• 결정 경계: $wx +b$
• 마진 경계: $wx + b + 1,wx + b - 1$

원문제

• $min \frac{1}{2}||w||^2$
• s.t. $y_i(w\cdot x_i + b) \ge 1, \forall x_i$

라그랑주 해법

• $max_{\alpha} min_{w,b} L(w, b, \alpha) = \frac{1}{2}||w||^2 - \sum_{i}\alpha_i(y_i(w\cdot x_i + b) - 1)$
• s.t. $\alpha_i \ge 0, \forall x_i$

풀이
1. 원 문제 정의

• $min \frac{1}{2}||w||^2$
• $s.t. y_i(w\cdot x_i + b) \ge 1, \forall x_i$

2. 라그랑주 해법으로 변환

• 오리지널 함수의 최소값 문제를 듀얼의 최댓값 문제로 바꾸어 쉽게 해결
• $max_{\alpha} min_{w,b} L(w, b, \alpha) = \frac{1}{2}||w||^2 - \sum_{i}\alpha_i(y_i(w\cdot x_i + b) - 1)$
• s.t. $\alpha_i \ge 0, \forall x_i$

3. KKT 정지 조건으로 w, b 변수 제거

• $\frac{\partial L}{\partial w} = 0 \Rightarrow w = \sum_{i}\alpha_i y_i x_i$
• $\frac{\partial L}{\partial b} = 0 \Rightarrow \sum_{i}\alpha_i y_i = 0$

4. 듀얼 문제 풀기
5. 정지 조건으로 w 구하기, 상보 여유성으로 b 구하기
6. 최적성 검토

SOFT SVM

여유 변수

• 여유 변수 (Slack Variables) 를 추가하여 품
• $\xi_i$ (Xi): 데이터가 마진 경계를 넘어가는 것을 허용하되, 그에 대한 페널티를 부여함.
  • $0 < \xi_i < 1$: 데이터 $i$가 올바른 쪽에 있지만 마진 영역 안에 있음.
  • $1 < \xi_i$: 데이터 $i$가 초평면의 잘못된 쪽에 있음 (오분류).

원문제

• 목적 함수는 오분류된 인스턴스와 마진 내에 있는 인스턴스에 페널티를 부여함:

  • $min \frac{1}{2}||w||^2 + C\sum_{i}\xi_i$

• 제약 조건이 다음과 같이 변경됨:

  • $y_i(w\cdot x_i + b) \ge 1 - \xi_i, \forall x_i$
  • $\xi_i \ge 0$

특징

• $C$: 마진 너비와 오분류 사이의 트레이드오프(trade-off)를 조절함.
• 알고리즘은 마진을 최대화하면서 $\xi_i$를 0으로 유지하려고 노력함.
• 오분류의 수를 최소화하는 것이 아님. 마진 경계와 오분류 데이터 거리의 합을 최소화.
• $C \to \infty$ 일 때 하드 마진 솔루션에 가까워짐.

듀얼 문제 (Dual Problem)

• Maximize: (목적 함수 $\tilde{L}(\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 x_i^T x_j$
• s.t.
  • $0 \le \alpha_i \le C, \forall i$ (상한선 C가 생김, C에 따라 선택)
  • $\sum_{i=1}^{n}\alpha_i y_i = 0$

• 제약 조건을 만족하는 케이스가 여러개 인경우
  • 크사이 값과(문제 제약 조건을 이용) 마진을 계산 후
  • 목적함수가 최소가 되는 결정 경계를 선택한다.

SOFT SVM 의 목적 함수와 크로스엔트로피

• $\text{min } C\frac{1}{2}\sum \theta_j^2 + \sum_{i} [y^{(i)}cost_1(\theta^T x^{(i)}) + (1-y^{(i)})cost_0(\theta^T x^{(i)})]$

• 로지스틱 회귀의 크로스엔트로피 비용함수와 비슷하게 생김

• cost 함수는 힌지 모양

비선형 SVM

• 비선형 데이터는 선형 모델로 분리 불가
• 입력 공간의 데이터를 고차원 특징 공간으로 매핑하여 선형 분리
• 고차원 특징 공간의 해를 입력 공간으로 가져오면 비선형 경계가 됨

커널 트릭

• 커널 트릭을 사용해 입력 공간의 데이터를 명시적으로 고차원 공간의 데이터로 매핑하지 않고도 고차원 공간에서의 내적을 계산할 수 있다.
• SVM 최적화 함수 내부에 데이터에 내적이 있음. 모든 내적을 커널 함수로 바꿔서 명시적 고차원 매핑 과정 없이 비선형 SVM 을 학습

가우시안 커널

가우시안 커널

• $K(x_1, x_2) = \exp(-\frac{||x_1 - x_2||^2}{2\sigma^2}), \sigma \ne 0$

• 데이터 포인트들을 종모양으로 들어올리는 효과.

• 특정 높이에서 자르면 비선형 경계가 생김

• 대부분의 복잡한 데이터의 분포를 잘 잡아냄.

• 보통 모든 데이터를 랜드마크로 사용함

SVM 파라미터

• C (오분류 페널티)

  • 클수록: 오분류 적음, 과적합 위험, 낮은 편향, 높은 분산
  • 작을수록: 오분류 허용, 과소적합 위험, 높은 편향, 낮은 분산

• $\sigma^2$ (가우시안 커널의 파라미터)

  • 클수록: 특징이 부드럽게 변함, 과소적합 위험, 높은 편향, 낮은 분산
  • 작을수록: 특징이 급격하게 변함, 과적합 위험, 낮은 편향, 높은 분산

• 감마 ($\sigma$)

  • 클수록: 과적합 위험, 결정 경계가 복잡해짐
  • 작을수록: 과소적합 위험, 결정 경계가 단순해짐