SVM(Support Vector Machine)

SVM(Support Vector Machine)에 대해 알아보자.

이전에는 신경망을 통해 2차원 데이터 셋을 분류해본 적이 있다. (신경망 참조)

[그림 1]을 보면 신경망 모델의 한계를 볼수 있다. 1번을 초기로 설정한뒤 점차 오류를 줄여가는 과정에서

2번에 도달하였을 경우 신경망은 오류함수가 0을 가지게 되므로 종료한다. 하지만 3번의 경우가 2번의 경우보다

더 데이터를 더 잘 분류한 경우가 될 것이다.

   [그림 1] 신경망 모델의 한계

학습의 입장에서 보면 2번과 3번 모두 데이터를 잘 분류한 결과가 되지만, 만약에 데이터가 새로 들어올 가능성을

고려한다면 2번의 경우 오류가 생길수 있는 확률이 3번의 경우보다 높다. 분류기 성능으로 본다면 3번의 경우가

좀더 잘 분류된 경우가 될 것이다.

이처럼 SVM은 오류를 최소화 하여 분류하는 것으로 부터 한발짝 더 나아가 분류된 데이터 셋을 고려해

여백(margin)을 최대화 하여 일반화 능력을 극대화 시키는 것을 말한다. 즉, SVM은 최대 여백을 구한다.

첫번째 선형적으로 데이터를 분류할 경우를 고려해 선형 SVM에 대해 정리한다.

1. 선형 SVM

[그림 1]과 같이 이진 분류를 결정하는 초평면 식은 다음과 같이 표현할 수 있다.

[그림 2]를 보면 w가 고정되있을때, b의 값에 따라 직선의 위치가 변화하는것을 관찰할 수 있다.

  [그림 2] w와 b에 따른 분류기의 위치 변화

속이 찬 샘플들(직선에 가까운 것들)은 서포트 벡터(support vector)라고 부른다. 이 벡터들은 직선의 위치에 

직접적인 영향을 끼친다. 결정 직선에서 서포트 벡터 x까지 거리가 1(즉, |d(x)|=1)이 되도록 적당히 크기 조절을

하면 여백을 다음과 같이 쓸 수 있다.

모든 샘플들의 집합을 올바르게 분류한다는 가정 하에 최대 여백을 갖는 초평면(Hyperplane)을 찾으면 된다.

[식2]를 만족하며 [식3]을 최소화 하는 w를 찾으면 된다. 다르게 보면 조건부 최적화 문제이다.

보통 조건부 최적화 문제는 라그랑주 승수(Lagrange multiplier)를 도입하여 해결한다.

(조건부 최적화 : 조건이 정해진 상태에서 최대, 최소를 구하는 문제)

라그랑주 승수법이 잘 정리된 곳을 있어 소개한다. [http://kipid.tistory.com/50#secId1-1]

[식 3]을 라그랑주 함수 L(..)로 표현하면 [식 4]와 같다. 이때 조건식 마다 라그랑주 승수 αi를 부여하였다.

함수 L을 매개변수 w와 b로 미분한 후 그것을 0으로 놓고 KKT(Karush-kuhn-Tucker)조건식을 유도한뒤

그 결과를 Wolfe 듀얼 문제로 변형하면 [식 5]를 얻는다.

즉, [식 5]를 최대화 하는 문제로 바뀐다. [식 5]를 보면 w와 b가 사라졌음을 볼 수 있다.

따라서 w와 b를 구하는 문제가 아니라 라그랑주 승수 α를 구하는 문제가 되었다. 라그랑주 승수를 구하면

그것으로 w와 b를 구하면 된다. 또한 특징 벡터 xi가 혼자 나타나지 않고 두 개의 특징 벡터의 내적인

xi·xj로 나타난다. 

참조 : 컴퓨터비전(오일석)