Support Vector Machine

Support Vector Machine

Classification technique 의 한 종류이다.

statistical learning theory에 근간을 두고 있다.

해당 알고리즘은 많은 실제 응용프로그램에서 높은 성능을 나타내게 된다.

handwritten digit recognition to text categorization 등에 사용된다.

curse of dimensionality에 강건한 모습을 가진다.

이것의 unique한 ascpect는

traning data의 subset만을 가지고 decision boundary를 결정 한다는 점이다.

이러한 training data의 subset을 support vector라고 한다.

일단은 linearly separable data를 가지고 linear SVM을 트레이닝 하는 방법을 배운다.

Linear SVM: Separable Case

---

그다음 non-linearly separable data에 대해서 SVM을 이끌어내는 방법을 배운다.

아래와 같이 2개의 영역으로 Classification 하는 문제에서

Hyper-plane은 무수히 많이 나올 수 있다.

이중 최적의 Hyper-plane은 무엇 일까?

그것은 아래와 같이 최대의 margin을 가지는 hyper plane일 것이다.

이렇게 최대 마진을 가지는 B1은 B2보다 노이즈에 강건하기 때문에 좋은 성능을 가지게 된다.

즉, generalization error가 적어지는 효과가 있다.

이러한 최대 margin을 가지는 hyperplane을 찾는 방법은 아래와 같다.

Wiki 피디아

Linear Decision Boundary

각각의 Example의 Tuple (xi,yi) 이다. i는 1,2,...N 이다.

그리고 전통적으로 y는 2개의 class 문제로써

이럴때 Decision Boundary는 아래와 같이 정의 된다.

여기서 w와 b는 모델의 파라메터가 값이 된다.

b는 bias로 threshold 값이 된다.

결정을 할때 특정 임계값을 줘서 그 강도를 조절 할 수 있다. 

위 그림은 이차원 training set 데이터를 나타낸다. 각각의 training data들은 사각형과 원형을 가지고 있다.

만약 2개의 점이 decision boundary 안에 위치 한다면, 아래의 식을 만족 한다.

여기서 x_b - x_a는 

Decision boundary와 병렬인 어떠한 벡터가 된다. 그리고 이것은 x_a에서 x_b로 직접적으로 가게 된다.

w와의 dot product는 0이기 때문에 벡터 w의 방향은 decision boundary와 반드시 직교하게 된다. 이것의 그림은 위와 같다.

이제 x_s는 decision boundary의 위에 위치 한다고 하고 우리는 이것을 아래와 같이 기술 할 수 있다.

Margin of a Linear Classifier 

decision boundary와 가장 가까운 square와 circle을 우리는 고려 해 볼 수 있다.

사각형은 decision boundary 위에 위치하기 떄문에, 그것은 반드시 

을 만족 한다. 즉, k는 어떠한 positive 값이 된다.

반면에 circle은 반드시 

을 만족 한다. 즉 k'은 어떠한 negative 값이 된다.

2개의 parallel hyperplanes 

를 설명하기 위해서 

decision boundary의 두개의 파라메터 w와 b를 다시 설정 한다.

decision boundary의 margin이란 결국 주어진 2개의 hyper-plane들 사이의 거리를 의미 한다.

이 margin을 계산 하기 위해서,

우선 은 b_i1 위에 있는 데이터 포인트 이다. 그리고 x_2는 bi2위에 있는 데이터 포인트 이다. 

이러한 모습은 위 그림과 같다.

2개의 점에서의 차이는 첫번째 equation에서 second equation을 빼는 것이다.

이것을 유도하면 아래와 같다.

핵심은 x1-x2가 다른 선이라도 smallest distance from each class 이기 때문에

가장 단거리 d를 의미하고

그것과 법선 벡터 w와는 cos 0로 값은 1이다.

따라서 위와 같이 간소화 될 수 있다.

Learning a Linear SVM Model 

Training 단계에서의 SVM은 

파라메터 decision boundary의 파라메터 w와 b를 트레이닝 하게 된다. 트레이닝 데이터로 부터

파라메터들은 반드시 다음과 같은 2개의 조건을 만족 하게 된다.

먼역 y=1이라면 모든 트레이닝 데이터들은 반드시 hyper plane 위에 위치 해야한다.

이와 반대로, y = -1이라면 그것은 반드시 hyperplane 아래에 위치하게 된다.

이러한 두개의 inequality는 다음과 같이 좀더 compat 한 수식으로 요약된다.

SVM의 decision boundary가 반드시 maximal 이어야 한다는 조건은 다음의 수식이 minimizing 되어야 한다는 의미와 같다.

Definition 5.1 (Linear SVM: Separable Case). The learning task in SVM can be formalized as the following constrained optimization problem: 

Dual Problem

---

기존의 문제가 Lagrange multipliers를 이용해서 Dual problem으로 변경 되어 질 수 있다.

Linear SVM: Non-separable Case

---

이전에 정의한 decision boundary는 mistake-free 한것들만 정의 했었다.

하지만, 소수의 데이터가 대부분의 데이터 보다 너무 멀리 떨어져있고, 이것이 Noise일 가능성이 있다면,

어느정도 이러한 noise들을 무시하는 tolerable to small training error를 가지는 SVM을 설계할 수있다. 이것을 soft margin이라고 한다.

더욱이 not linearly separable 하다면 이러한 soft margin은 더더욱 필요하게 된다.

Nonlinear Support Vector Machine

---

이제는 아에 not linearly separable data들에 대해서 다루도록 하겠다.

이때는 original coordinate space x를 아에 새로운 space로 transform 하게 된다.

아래의 기존 2차원 space를 transform 하게 되면,

더 높은 dimensional space로 변경하게 되면 아래와 같이 된다.

이것은 linearly separable data의 분포로 변경이 되어진다.

Kernel Method

---

하지만 위와 같은 transform 되는 higher dimensional space의 존재 여부를 알아내는 것이 매우 어려운 문제가 된다.

이것을 해결하기 위해서 Kernel Method를 사용하게 된다.

이것을 통해 의 존재를 알 수 있다.

 

Characteristics of SVM

---

Try to find the global minimum of the objective function

 - ANN tends to find locally optimum solutions

SVM is an algorithm for binary class problem

How to apply for multi-class problems

- one-against rest approach

- one-against-one approach

- Error-correcting output coding (ECOC)