SVM (Support Vector Machine)

1. What is the SVM ?

- BEST 한 Supervised learning 으로 알려짐

*Supervised learning 이란 training set들이 주어졌을 때, 각각의 데이터가 어떤 분류 항 목인지(negative or positive) 정보가 주어져있음. 반면에 unsupervised learning은 주어진 데이터가 어떤 분류의 항목인지 정보가 없음(ex. SOM)

- Optimal margin classifier

: Lagrange duality를 이용해 SVM은 가장 최적의 margin을 가지는 classifier를 생성 최적의 margin을 생성하기 위해서는 hyperplane과 가장 가까운 training data의 거리가 최대가 되도록 hyperplane을 위치시킨다.

O : positive training examples

X : negtive training examples

The red line : hyperplane

- Kernel

: High dimension의 Vector를 효과적으로 SVM에 적용 할 수 있다.

 Kernel trick을 이용해서 연산량을 줄일수 있고, 여러가지 Mapping 모델을 적용 할 수 있다.

2. Margin

2.1 notation

Hyperplane은 다음과 같이 수식적으로 표현 될 수 있다.

 ........................(1)

X가 x,y 축을 가지는 2차원이라고 할 때 (여기서 x = x1 , y = x2 라고 쓰자)

 라고 쓸 수 있으며 X 벡터는 additional한 1을 가진다. 두 식을 전개 해보면 그 이유를 알 수 있다. 다음을 보자

 되고 이식을 정리 하면

 이 된다.

이는 기울기가    이고 y 절편이    인 직선이다. 이는 차원이 n차원으로 늘어나도 똑같이 적용 된다. 

그러므로    가 된다.

Hyperplane은 다음과 같이 좀 더 알아보기 쉽게 일반화 시킬 수 있다.

 ........................(2)

식(1)의 X와 theta가 다음과 같다면 

식(2)의 X와 W는 다음과 같다 

(*식(1)의 theta와 식(2)의 w는 같다.)

이렇게 정의된 hyperplane은 test data(=unseen data)를 다음과 같이 분류 할 수 있다.

 ................... (3)

다시 위의 그래프를 보며 생각해보면,    이라는 test data가 들어왔을 때, 식(3)에 vector X를 넣었을 때, hyperplane보다 위쪽 영역에 위치하면   이므로 , h(x)는 1이 되고 아래쪽 영역에 위치하면   이므로 h(x)는 -1이 된다.

 일 경우에는 confident 하게 test data를 구분 할 수 있다.

* 추가 개념 1. Hyperplane과 벡터 W는 항상 서로 orthogonal 하다. 2차원의 Hyperline으로 이를 보이자면,  일 때 Hyperline(2차원이므로 line이라고 일컫겠다) 는 기울기벡터    을 가지고 있다.  이다. 서로의 내적값이 0 이므로 두 벡터의 사이각은 90도가 됨을 알 수 있다. 차원이 증가해도 이러한 성질은 동일하므로, N차원의 hyperplane과 n차원의 벡 터 W는 항상 직교함을 알 수 있다.

2.2 Functional margin

functional margin은 다음과 같이 정의 된다. (이하 F-Margin)

 ...................... (4)

F-Margin은 hyperplane 으로부터 예측한 값 y (+1 , -1)와 hyperplane 에 해당 vector를 넣은 값의 곱이다.

전자와 후자가 엄밀히 말해 같은 값이지만 이 두 값을 곱함으로써 다음과 같이 생각 할 수 있다.

F-Margin 의 값이 만약에 0보다 크다면, (i)번째에 해당하는 test data에 대한 prediction을 올바르게 했다는 것을 알 수 있다.

또한 F-Margin의 값이 크면 클수록, 더 confident 하고 reliable한 prediction이라고 할 수 있다.

2.3 Geometric margin

2.2에서 functional 하게 margin을 정의 해보았다. 이번에는 Geometric Margin을 생각해보자. (이하 G-Margin)

위의 그래프를 살펴보자. 어떤 data(index = i)는    좌표에 위치 하고 있다. (    : position of data) 그 데이터와 hyperplane    과의 euclidean distance가  라고 하자.

추가개념 1에서 설명했듯이 W는 Hyperplane의 법선벡터이다. 그러므로 유닛 법선 벡터는

 이 된다. 그림 참고

우리는 거리와 법선벡터를 이용해 Hyperplane 위에 있는 점    (    ) 을 다음과 같이 알 수 있다.

이는 Hyperlane 위에 있는 점이므로 다음을 만족 한다.

 이 식을 정리 하면    값은 다음과 같다.

 이 식의 결과는 positive training example 에만 적용이 된다. negative의 경우 값이 음수가 되기 때문에 이를 막기 위해 다음과 같이 정의 한다.

 .................. (5)

이 결과를 F-Margin에서 구한 결과와 비교해보자. 식 (4)와 식 (5)를 비교해보면

 .................. (4)

 ................... (5)

 일 경우 식 (4)와 (5)가 같은 식이 됨을 알 수 있다.

즉 Geometric 하게 구한 Margin과 Functional 하게 구한 Margin이 서로 비슷한 경향을 보임을 알 수 있다.

3 The optimal margin classifier

사실 SVM에서 고려해야하는 Margin은 F-Margin 이든 G-Margin이든 가장 작은 값이다. 그 이유는 간단하다. 가장 작은 Margin만 고려해서 hyperplane을 생성하면 다른 training example들 간의 Margin은 고려할 필요가 없기 때문이다. 다시 말해 가장 가까운 training example을 정확하게 분류 할 수 있는 hyperplane은 나머지 example 또한 자명하게 분류 할 수 있다.

그렇다면 최적의 Margin을 가지는 hyperplane(classifier)은 어떻게 생성 할 수 있을까.

 이라는 constraint는 모든 상황에서 항상 유효하지 않다 (non-convex) 그러므로 optimal margin classifier를 구하기 위해서는 F-Margin 대신에 G-Margin을 이용한다.

 ............ (6)

*    은    로부터 만든 constraint 이다.

여기서 또 한가지의 constraint를 걸어 줄 수 있다.

hyperplane의 성분 W,b를    과 같이 일정한 배수배로 조정을 해도 hyperplane의 성질이 변하지가 않는다. 그 이유는 식(3)에서 정의한    의 값은 sign값에 의해 결정되지 magnitude에 의해서 결정되는 것이 아니기 때문이다.

그렇기 때문에 우리는    를 적절히 조절해서    = 1 로 설정 할 수 있다는 이야기다.

위 그림을 참고하면,    = 1 로 설정해도 오른쪽처럼 전체적인 변동은 있지만 hyperplane은 동일한 역할을 수행한다.

그렇다면 식 (6)의 optimization 문제는 다음과 같이 간단화 될 수 있다.

optimization할 term을    으로 정의 하는 것은, 뒤에 나올 primal optimization problem 과 연관이 있는 듯하다 (아마 문제를 정의하기 유리한 form이기 때문일 것이다.) <- 이부분은 뒷부분이 공부된뒤 다시 기입

최종적으로 우리는 다음의 간단화 된 optimization 문제를 풀면 된다.

4 Lagrange duality
............. 이 부분은 optimization을 공부 하고...

naive하게 적어보자면
Lagrange duality를 이용해, vector를 support vector들과의 inner product로 표현 가능하게 변환 시킬수 있다.

이렇게 변환 하게 되면, kernel을 적용 하기에 유리한 모양이 되므로
kernel trick을 이용할 수 있게 되고, 보다 다양한 mapping function을 적용 할 수 있게 된다.