[6기 강남 김현호] 온라인 문자인식 with SVM #4

#3까지의 포스팅에선 선형으로 분리 가능한 상황에서의 SVM을 구하였습니다.

그렇다면 다음과 같은 선형으로 분리가 불가능한 상황에서는 어떻게 해야 할까요?

(5) 슬랙 변수(Slack Variable)

데이터들을 보시면 3가지 경우로 나눌 수 있습니다.

1. 분류기에 의해 제대로 분리 되어 있다.

2. 제대로 분류되어 있지만 Support Vector의 경계 안에 있다.  (네모네모)

3. 분류기를 넘어가 잘 못 분류되어 있다.  (동글동글)

위를 식으로 표현하면 다음과 같이 표현할 수 있습니다.

1.  >= 1

2. 0 <=  < 1

3.  < 0

여기에 슬랙 변수(Slack Variable)이라고 불리는 변수를 도입하여 위 세가지 경우를 하나의 식으로 표현 할 수 있습니다.

 = 0 일때 1번의 경우  >= 1가 되고

0<  <=1 일때 2번의 경우 0 <=  < 1 가 되고

 > 1 일때 3번의 경우  < 0 가 됩니다.

이제 우리는 슬랙변수 를 줘서 원래의 SVM(여백을 최대 한 크게 하고, 동시에 최대한 1번의 경우가 될 수 있는) 을 결정하는 초평면을 찾는 문제가 됩니다.

이를 조건부 최적화 문제로 바꾸면 아래의 조건하에

를 최소화 하는 문제가 됩니다.

라그랑제 승수와, KKT 조건, Wolfe Dual을 거치면 최종적으로 아래의 조건 하에

아래의 식을 최대화 하는 문제로 바뀝니다.

이를 보면 #3에서 보았던 선형 분류기와 다른점이 크게 없다는 것을 보실 수 있습니다.

다만 0 <= a 였던 라그랑제 승수의 범위가 0 <= a <= C (slack variable) 로 바뀌었습니다.

자 이제 3개의 데이터를 가지고 예제 문제를 풀어보도록 하겠습니다.

데이터는 다음과 같습니다.

x1 = (2, 3)     t1 = 1

x2 = (4, 1)     t2 = -1

x3 = (5, 1)     t3 = 1

그럼 이제 조건부 최적화 문제로 적용시키면 아래의 조건하에

아래의 식을 최적화 하는 a = (a1, a2, a3)를 찾아야 합니다.

위는 4가지 경우로 나누어서 풀어볼 수 있겟습니다

1. a1 = 0    a2 != 0    a3 != 0

2. a1 != 0    a2 = 0    a3 != 0

3. a1 != 0    a2 != 0    a3 = 0

4. a1 != 0    a2 != 0    a3 != 0

1번의 경우

a2 = a3가 되므로

a1 = 0,     a2 = 2,     a3 = 2

w와 b, 그리고 결정 직선을 구하면

w = (2, 0),    b = -9

d(x) = 2x1 - 9 = 0 이 됩니다.

2번의 경우

a1 = 0, a3 = 0이면

x1과 x3가 서로 다른 부류의 서포트 벡터가 되는데 x1과 x3는 같은 분류이므로 모순이 발생하게 됩니다.

3번의 경우

a1 = a2이므로

a1 = 1/4,    a2 = 1/4,    a3 = 0

w = (-1/2, 1/2), b = 1/2

d(x) = -1/2*x1 + 1/2*x2 + 1/2 이 됩니다.

마지막으로 4번의 경우

a1 = a2 - a3를 대입한 후 미분을 통해 풀면

a1 = 3/2,    a2 = 13/2,    a3 = 5

w = (2, 3)

b = -12

d(x) = 2x1 + 3x2 - 12 가 됩니다.

이를 그래프로 표현하면 아래와 같습니다.

1번의 경우 x1이 오분류

3번은 x3가 오분류

4번은 데이터 모두가 서포트 벡터인것을 보실 수 있습니다.

여기에 a의 범위를 슬랙 변수 C를 통해 나누어 보면

C < 2 일때 ①과 ④는 a가 C의 범위에 들어가지 못하므로 오직 ③만 유효하게 됩니다.

2 <= C < 6.5 이면 ①과 ③ 만이 유효하게 되고

C <= 6.5 일때 비로소 ①, ③, ④ 모두를 커버 할 수 있습니다.

이렇게 슬랙 변수를 조정하므로서 어느정도의 trade off를 통해 SVM의 데이터 분류에 대한 강약을 조절 할 수 있습니다.

(6) 비선형 SVM

지금까지는 선형 SVM에 대해 알아보았습니다. 하지만 현실에서 선형으로 분류가 가능한 데이터는 그리 많지 않습니다. 그렇기 때문에 SVM을 비선형으로 확장 시켜야 합니다. 비선형으로 확장시키는 과정은 매우 어려울듯 보이나 Kernel Trick 이라는 아주 기가막힌 방법으로 쉽게 바꿀 수 있습니다.

우선 1963년 선형 분류기가 만들어진 후, 1992년 커널트릭을 통해 비선형 분류기를 만드는 방법을 제시 하였습니다. 

커널트릭을 간단하게 설명드리면 더 높은 차원 벡터로 표현하는 사상함수를 이용해 분류하는 방법입니다.

위처럼 빨간색과 파란색을 선형으로 구분 할 수 없을때 3차원으로 사상시켜 선형으로 구분 할 수 있게 합니다.

동영상 링크 따로 첨부해 드리니 직접 보시면 이해가 훨씬 더 쉬우실껍니다.

http://www.youtube.com/watch?v=3liCbRZPrZA

커널트릭 기법은 앞서 포스팅 #3에서 라그랑제 승수법을 통해 식을 변환 시켯을때 아래처럼 특징 벡터 x가 내적 형태로 나타나는 것을 이용합니다.

http://crsouza.blogspot.kr/2010/03/kernel-functions-for-machine-learning.html

위의 사이트에 의하면 대치할 수 있는 커널의 종류는 상당히 많지만 대표적으로 3가지의 커널을 사용합니다.

1. 다항식(Polynomial) 커널 

2. RBF(Radial Basis Function) / Gaussian 커널

3. Hyperbolic Tangent (Sigmoid) 커널

엄천 단순한 이러한 커널 대치를 통해 선형으로 분류 할 수 없던 작업을 비선형으로 가능하게 만들었습니다.

(7) Open Source SVM

이렇게 선형 / 비선형 SVM의 동작 원리를 살펴 보았습니다. 

하지만 SVM을 직접 구현하는 것은 매우 복잡하므로 현재 오픈소스로 구현된 SVM을 소개해 드리도록 하겠습니다.

1. http://svmlight.joachims.org/  

svm light는 C언어로 프로그래밍 된 open source SVM으로서 사용법과 논문등을 보실 수 있습니다.

2. http://www.csie.ntu.edu.tw/~cjlin/libsvm/

LIBSVM은 Java, C++ Python등 다양한 언어로 포팅된 open source SVM입니다.

두 사이트 모두 간단한 사용 설명법이 나와 있으므로 어렵지 않게 테스트 하실 수 있습니다.

머신러닝을 다뤄보면서 프로그래밍 보단 오히려 수학쪽을 더 많이 다루는 편이라 이해가 매우 힘드겠지만 이 분야에 대해 관심을 가지고 공부하는 여러분 모두 화이팅 입니다.

이상으로 길고 길었던 SVM에 대한 소개를 마치도록 하겠습니다. 감사합니다.