Soft Margin SVM, Nonlinear SVM, Kernel

# 개요

SVM의 기본 개념은 이전에 정리했었다. 

https://push-and-sleep.tistory.com/81

SVM (Support Vector Machine)

 

이전에 정리한 내용은 선형으로 분리가 되는 것이었는데 Hard Margin SVM이라 부른다. 

 

기본적인 Soft Margin의 컨셉은 어느정도 에러를 허용하자는 것이다. 

 

# Soft Margin SVM

아래 그림과 같이 오차를 허용하는데 이 오차와 마진의 거리를 ξ(크사이)로 표현한다. 

이를 이용하여 수식으로 나타내면 아래와 같다. 

w, b와 더불어 ξ까지 결정해줘야 한다. (decision variable)

ξ는 slack variable이라고 하는데 training error를 허용하겠다는 의미이다. 

 

C는 margin과 training error에 대한 trade-off를 결정하는 파라미터로, tuniing parameter라고 부른다. 

• C가 크면, training error를 많이 허용하지 않으므로 overfit 될 수 있다. (왼쪽 그림)
• C가 작으면, training error를 많이 허용하므로 underfit 될 수 있다. (오른쪽 그림)

## 최적해 찾기

풀이 방식은 Hard Margin SVM과 같다. 

 

Lagrangian multiplier를 이용하여 Lagrangian primal 문제로 변환해서 푼다. 

primal 문제에서는 w, b, ξ를 결정해야 한다. 

 

앞에서 했던 방식으로 각각에 대해 미분해서 풀면 된다. 

이를 이용해서 식을 전개하는 과정은 생략. 

 

결과적으로 Lagrangian dual을 살펴보면 Hard Margin SVM과 같다. 

 

다만 α의 범위가 생겼다는 것만 다르다. 

 

Soft Margin도 역시 KKT condition을 만족해야 하고 그 중 Complementary slackness가 중요하다. 

α값에 따라 케이스별로 살펴보면

 

① α=0이면, 위의 C=γ가 되고 (위 미분의 3번) ξ=0이 된다. (위의 두 번째 식)

그리고 α와 ξ를 식에 대입하면 (y(wx + b) -1)≠0이 된다.  

여기에 해당하는 x는 그림처럼 plus-plane, minus-plane 위에 있지 않다. 

 

② 0<α<C 이라면, γ>0이 되고 (위 미분의 3번) ξ=0이 된다. (위의 두 번째 식)

그리고 α와 ξ를 식에 대입하면 (y(wx + b) -1)=0이 되어야 한다.  

여기에 해당하는 x는 plus-plane, minus-plane 위에 있다. (support vector)

 

③ α=C 라면, γ=0이 되고 ξ>0이 된다. 

 α와 ξ 모두 소거되지 않으므로 식은 그대로인데 아래와 같이 적을 수 있다. (전개해서 넘김)

ξ는 에러를 허용하겠다는 뜻이고 그림을 보면 plus-plane과 minus-plane 사이에 있다. 

이 또한 support vector라고 부른다. 

 

# Nonlinear SVM

위의 Soft Margin SVM은 선형으로 표현하기 어려운 점들을 위한 것이었다. 

하지만 이것도 선형 SVM에 해당한다. 

 

이번에는 비선형으로 접근하는 방식을 살펴보려고 한다. 

그 중 하나의 방법이 아래 그림처럼 고차원으로 보내서 분류하는 것이다. 

기호를 몇 가지 살펴봐야 하는데 Φ는 phi라 읽으며 x들의 함수를 뜻한다. (pi는 원주율로 발음 주의)

여기서는 Φ로 x를 변환하니 5개의 변수로 늘어났으며 이 고차원 공간을 Feature Space라고 부른다. 

그럼 어떻게 고차원으로 보내야 하는가?

이를 위한 효율적인 방법이 있다. 

 

# Kernel Function

고차원으로 보내서 계산하는 것을 수식으로 표현하면 아래와 같다. 

 

기존의 SVM 식에서 x끼리 내적하는 부분이 있는데 Φ를 통해 고차원으로 변형한 것으로 내적한다. 

그런데 아래와 같이 Φ로 직접 데이터를 변환할 필요 없이 한번에 내적의 효과를 내는 함수를 사용할 수 있다. 

예시로 아래와 같이 x, y값이 주어졌다고 가정하자. 

그리고 아래와 같은 Φ로 변환해서 내적을 할 수 있다. 

그런데 아래 예시를 보면 Φ를 몰라도 내적과 같은 결과가 나오게 하는 함수를 찾을 수 있다. 

이 함수를 kernel function이라 부르며 Φ를 찾지 않고 해결하는 방법이라서 Kernel Trick이라고도 한다. 

 

Kernel Function으로는 아래와 같은 것들이 있다. 

위의 예시는 polynomial이다. 

 

- Polynomial Kernel

- Sigmoid Kernel (Hyperbolic tangent kernel)

- Gaussian Kernel (Radial basis function (RBF) kernel)

Kernel 사용 시 참고할 사항을 살펴보면

• kernel을 정하는 기준은 딱히 없으므로 다 해보고 성능이 잘 나오는 것을 쓴다. 
• kernel에 따라 feature space의 특징이 달라지므로 데이터 특성에 맞는 kernel을 쓴다. 
• 일반적으로는 RBF, sigmoid, 4차 미만의 polynomial이 많이 쓰인다. 

 

참고 : 김성범 교수님 유튜브