SVM (Support Vector Machine)

# 개요

고차원 데이터의 분류에 좋은 성능을 보이는 알고리즘이다. 

 

SVM의 궁극적인 목적은 아래와 같이 두 클래스를 잘 나누는 hyperplane을 찾는 것이다. 

 

즉 w와 b를 찾으면 된다. 

문제는 좋은 hyperplane의 기준이 무엇인가를 고민해봐야 한다. 

 

# Margin

각 클래스에서 가장 가까운 관측치 사이의 거리를 Margin이라고 한다. 

 

Margin을 최대화 하는 plane은 기울기 w로 표현이 가능하다. 

 

각 +1, -1에 해당하는 plane 또한 이 plane의 평행 이동으로 표현 가능하다. 

위의 경우는 각 클래스를 1, -1로 가정한 경우이다. 

 

마진만큼의 거리에 있는 plane위의 점들을 support vector라고 부른다. 

아마 여기 안으로는 못들어오는 지지선의 개념이라서 그런 것 같다. 

 

마진보다 멀리 있는 점들은 부등호로 표현할 수 있다. 

 

# 수식

+1에 해당하는 plane은 -1에 해당하는 plane의 평행 이동으로 표현할 수 있다. 

 

이를 이용해서 아래와 같이 식을 전개하면 λ를 w에 대한 식으로 나타낼 수 있다. 

이를 이용해서 Margin을 계산하면 아래와 같다. 

 

맨 아래에 절댓값 비슷하게 생긴건 norm을 뜻하는데 2가 붙어있으니 L2 norm이다. 

우리의 목적은 margin을 최대화하는 w를 찾는 것이고 아래와 같이 표현된다. 

L2 norm은 제곱근이 있으니 계산의 편의를 위해 제곱을 해준 형태를 목적함수로 쓴다. 

 

결과적으로 다시 정리해보면 아래와 같다. 

 

# Quadratic Programming

참고로 목적식이 이런 이차식으로 된 형태를 quadratic programming (QP)라고 부른다. 

 

이는 convex optimization에 해당하는데 최솟값이나 최댓값이 하나만 존재함을 뜻한다. 

 

QP는 이미 푸는 방법이 있으므로 풀이가 어렵지 않다. 

 

일단 Lagrangian multiplier를 이용하여 목적식과 제약식을 하나의 Lagrangian primal 형태로 변환할 수 있다. 

 

 

우리는 primal 형태를 minimize 시키고나서 dual form을 maximize 할 것이다. 

(솔직히 무슨말인지 모르겠다)

 

어쨌던 우리는 max는 무시하고 min부분만 구할 것이다. 

 

Convex, continuous이기 때문에 미분=0에서 최솟값을 가지니 아래와 같이 푼다. 

x, y는 데이터에서 주어진다. 

 

①, ②에서 구한 것을 min 부분에 대입해서 정리하면 아래와 같은 형태가 된다. 

(전개는 생략)

이제 원래의 식에서 w, b는 사라졌고 아래와 같이 max부분에 α만 남은 dual 형태로 바뀌었다. 

위의 형태로 정리되면 이제 풀기 쉬워졌다. 

 

# KKT (Karush-Kuhn-Tucker) conditions

(w, b, α)가 최적해가 되려면 KKT (Karush-Kuhn-Tucker) conditions를 만족해야 된다. 

 

4가지 조건 중 네 번째인 Complementary slackness를 살펴볼 필요가 있다. 

 

이 조건은 아래를 만족해야 한다. 

위의 식을 살펴보면 두 가지 경우가 있을 수 있다. 

 

먼저 α가 보다 크면 뒷 부분은 0이 되어야 한다.

이는 x값들이 마진 위에 있다는 것을 뜻하고 이런 값들을 support vector라고 부른다. 

 

두 번째 경우에 해당하는 x는 마진 위에 있지 않다. 

중요한건 이런 점들은 Hyperplane을 구축하는데 영향을 미치지 않는다는 것이다. 

그래서 SVM이 outlier에 robust하다. (강건하다)

 

즉 hyperplane을 구할 때는 support vector만 사용할 것이고 식으로 표현하면 아래와 같다. 

 

# 모델링

α는 dual form에서 구했고 w는 primal form에서 나온 위의 식으로 구할 수 있다. 

 

그럼 이제 b를 구해야 한다. 

 

이미 우리가 support vector 값을 알고 있고 α도 알고 있으므로 아래 식에 대입하면 구할 수 있다. 

이렇게 하면 α, w, b가 모두 구해졌고 모델링은 끝났다. 

 

예측을 해야 한다. 

 

새로운 데이터가 들어왔을 때 아래 값을 구한다. 

값이 0보다 작으면 -1인 클래스로 예측하고 0보다 크면 1인 클래스로 예측할 수 있다. 

 

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

(sign은 부호함수라는 것으로 특정 값에 대한 부호를 출력하는 함수이다.)

 

 

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