[Machine Learning] Support Vector Machine (4), Soft margin SVM

이전 포스팅까지는 Hard margin SVM에 대해 설명하였다.

[Machine Learning] Support Vector Machine (SVM) (3)

 

이번 포스트에서는 Soft margin SVM에 대해 설명하겠다.

---

 

이전 포스트에서까지 언급했듯, Hard margin SVM은 linearly separable한 데이터에 대해서만 사용할 수 있다.

그럼 linearly separable하지 않은 데이터에는 어떻게 SVM을 적용할 수 있을까?

그 방법은 크게 두 가지가 있다.

 

1. linearly separable하지 않아 발생하는 잘못된 분류, 즉 에러를 허용하되 그 에러에 대한 패널티를 준다.

2. non linear한 decision boundary를 사용한다.

 

이번 포스트에서는 에러를 허용하되 그 에러에 대한 패널티를 주는 SVM, Soft margin SVM에 대해 설명하겠다.

 

---

Soft margin SVM이란?

Error case를 허용하는 SVM이다.

hyperplane을 결정하는 데에 에러 케이스의 데이터도 이용되므로, support vector의 종류가 더 늘어난다.

 

1. On margin SV

decision boundary로부터 가장 가까운 데이터들의 집합, 즉 Hard marign SVM에서 support vector로 이용되었던 데이터들이다.

 

2. Inside margin SV

margin 내부에 있는 잘못 분류된 데이터들이다.

 

3. Outside margin SV

margin 외부에 있는 잘못 분류된 데이터들이다.

 

Soft margin SVM은 에러를 허용한다. 따라서 2, 3번 support vector들은 잘못 분류되어 에러임에도 support vector로 사용된다.

에러를 허용하기만 해서는 좋은 decision boundary를 찾을 수 없으므로, 에러에 대한 패널티를 준다. 패널티를 얼마나 줄지 어떻게 결정하는가?

 

에러가 클수록 큰 패널티를 줘야하므로, 에러가 얼마나 발생했는지를 저장하는 slack variable들을 도입한다.

 

Slack Variable

모든 데이터에게 각각 slack variable을 부여하여 에러가 얼마나 발생했는지를 측정한다.

$\xi$ = {$\xi_1$, . . . , $\xi_N$ }  ($\xi$는 크사이라고 읽는다.)

$\xi_i$는 $X_i$가 hyperplane을 기준으로 얼마나 에러를 발생시켰는지를 나타낸다.

 

Support vector가 아닌 데이터들은 hyperplane으로부터 멀리 떨어져서 잘 분류되고 있으므로 $\xi_i$ = 0이다.

On margin SV들은 경계면에 존재하므로 에러를 발생시키지 않아 $\xi_i$ = 0이다.

Non margin SV(inside, outside margin SV)들은 잘못 분류되어 에러를 발생시키고 있으므로 $\xi_i$ > 0이다.

 

기존 Hard margin SVM의 objective function은 다음과 같았다.

$y_i$(𝐰T$x_i$+𝑏) ≥ 1

이는 데이터들이 모두 에러 없이 분류되어야 한다는 것이므로, 매우 빡빡한 제약조건이다.

 

Soft margin SVM에서는 에러를 허용하기 위해 $\xi$를 이용해 제약조건을 완화시킨다.

Soft margin SVM의 제약조건은 다음과 같다.

 

$y_i$(𝐰T$x_i$+𝑏) ≥ 1−$\xi_i$, $\xi_i$ ≥ 0

 

에러에 대해 패널티를 주어야 하므로 objective function에 $\xi$를 반영한다.

Soft margin SVM의 objective function은 다음과 같다.

 

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

 

C는 hyper parameter로, 학습을 통해 얻는 것이 아니라 사람이 모델에 적절한 값을 주어야 한다.

C값이 커질수록 에러에 대한 패널티가 크므로, 모델은 에러를 최대한 허용하지 않는 쪽으로 학습되어 Hard margin SVM과 같은 decision boundary를 얻게 된다.

C값을 작게 줄수로고 에러에 대한 패널티가 작으므로, 잘못 분류되는 에러 데이터들이 생긴다. 그러나 에러 데이터가 생기는 hyperplane을 허용함으로서 margin이 커지므로, 미래에 데이터가 들어오면 그 데이터에 대한 generalized performance 성능이 더 좋을 수 있다.

각각 장단점이 있으므로, 적절한 값을 주어야 한다.

 

---

 

Hard margin SVM에서 했던 것과 같은 방법으로 objective function을 minimize하는 parameter를 찾는다.

제약조건이 있는 최소값을 찾는 문제는 뭐다?

바로 Lagrange multiplier를 이용하는 것이다.

 

Lagrange multiplier를 이용하기 위해 Lagrange primal function을 정의한다.

이 식은 convex하므로 analytic한 방법으로 최적의 해를 구할 수 있다.

( 함수가 convex한지 판단하는 방법은 이전 포스트에 작성 해놓았다. )

 

각 parameter로 편미분해서 나온 식이 0이 되게 하는 parameter가 최적의 해이다.

최적의 해를 구했으니 이제 lagrange dual form으로 바꾸어줄 것이다.

 

Hard margin SVM의 dual function과 식이 같지만, 제약조건이 다르다.

 

Soft margin SVM의 Langrange dual form의 제약조건은 다음과 같다.

$\alpha_i$ ≥ 0, $\gamma_i$ ≥ 0이고 $C$ - $\alpha_i$ - $\gamma_i$ = 0이므로 0 ≤ $\alpha_i$ ≤ $\gamma_i$ 이다.

따라서 제약조건을 다음과 같이 고쳐 쓸 수 있다.

 

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

 

 

Soft margin SVM의 Lagrange dual function의 objective function은 다음과 같다.

Hard margin SVM과 같이, 이 식을 Quadratic Programming Solver에 집어넣어서 최적의 $\alpha$를 찾을 수 있다.

 

---

Analysis

 

Non-SV의 경우,

제대로 분류되며 hyperplane의 결정에 영향을 미치지 않으므로 $\xi_i$와 $\alpha_i$ 모두 0이다.

 

Margin SV의 경우,

에러를 발생시키지 않으므로 $\xi_i$ = 0이고, $\gamma_i$ > 0이다.

또한 margin 위에 있는 support vector이므로 $\alpha_i$ > 0이다.

$C - \alpha_i - \gamma_i$ = 0이고 $alpha_i$ > 0, $gamma_i$ > 0 이므로 $alpha_i$는 0보다 크고 $C$보다 작다.

 

Non-Margin SV의 경우,

에러를 발생시키므로 $\xi_i$  > 0이고, $\gamma_i$ = 0이다.

따라서 $\alpha_i$ = $C$이다.

 

 

 

에러를 발생시키고 있는 Non margin SV의 경우 $\alpha$ 값이 $C$임을 알 수 있다.