for textmining

서포트 벡터 머신 (Support Vector Machine)

|

이번 글에서는 딥러닝 이전 뛰어난 성능으로 많은 주목을 받았던 서포트 벡터 머신(Support Vector Machine)에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님과 같은 대학의 김성범 교수님 강의, 그리고 이곳을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

margin

두 범주를 나누는 분류 문제를 푼다고 가정해 보겠습니다. 아래 그림에서 직선 $B_1$과 $B_2$ 모두 두 클래스를 무난하게 분류하고 있음을 확인할 수 있습니다.

좀 더 나은 분류경계면을 꼽으라면 $B_1$일 겁니다. 두 범주를 여유있게 가르고 있거든요. 위 그림에서 $b_{12}$을 minus-plane, $b_{11}$을 plus-plane, 이 둘 사이의 거리를 마진(margin)이라고 합니다. SVM은 이 마진을 최대화하는 분류 경계면을 찾는 기법입니다. 이를 도식적으로 나타내면 아래와 같습니다.

그럼 마진의 길이가 얼마인지 유도해보겠습니다. 우선 우리가 찾아야 하는 분류경계면을 $w^Tx+b$라고 둡시다. 그러면 벡터 $w$는 이 경계면과 수직인 법선벡터가 됩니다.

이해하기 쉽도록 $w$를 2차원 벡터 $(w_1,w_2)^T$라고 두겠습니다. $w$에 대해 원점과의 거리가 $b$인 직선의 방정식은 $w^Tx+b=w_1x_1+w_2x_2+b=0$이 됩니다. 이 직선의 기울기는 $-w_1/w_2$이고, 법선벡터 $w$의 기울기는 $w_2/w_1$이므로 두 직선은 수직입니다. 이를 차원을 확장하여 생각해도 마찬가지입니다.

어쨌든 이 사실을 바탕으로 plus-plane 위에 있는 벡터 $x^+$와 $x^-$ 사이의 관계를 다음과 같이 정의할 수 있습니다. $x^-$를 $w$ 방향으로 평행이동시키되 이동 폭은 $λ$로 스케일한다는 취지입니다.

그럼 $λ$은 어떤 값을 지닐까요? $x^+$는 plus-plane, $x^-$는 minus-plane 위에 있다는 사실과 $x^+$와 $x^-$ 사이의 관계식을 활용하면 다음과 같이 유도해낼 수 있습니다.

마진은 plus-plane과 minus-plane 사이의 거리를 의미합니다. 이는 $x^+$와 $x^-$ 사이의 거리와 같습니다. 둘 사이의 관계식과 $λ$값을 알고 있으므로 식을 정리하면 마진을 다음과 같이 유도할 수 있습니다.

목적식과 제약식 정의

SVM의 목적은 마진을 최대화하는 경계면을 찾는 것입니다. 계산상 편의를 위해 마진 절반을 제곱한 것에 역수를 취한 뒤 그 절반을 최소화하는 문제로 바꾸겠습니다. 이렇게 해도 문제의 본질은 바뀌지 않습니다.

여기엔 다음과 같은 제약조건이 관측치 개수만큼 붙습니다. 식의 의미는 이렇습니다. plus-plane보다 위에 있는 관측치들은 $y=1$이고 $w^Tx+b$가 1보다 큽니다. 반대로 minus-plane보다 아래에 있는 점들은 $y=-1$이고 $w^Tx+b$가 -1보다 작습니다. 이 두 조건을 한꺼번에 묶으면 아래와 같은 제약식이 됩니다.

라그랑지안 문제로 변환

라그랑지안 승수법(Lagrange multiplier method)은 제약식에 형식적인 라그랑지안 승수를 곱한 항을 최적화하려는 목적식에 더하여, 제약된 문제를 제약이 없는 문제로 바꾸는 기법입니다. 이에 대해 추가적인 내용은 이곳을 참고하면 좋을 것 같습니다.

우리가 이미 정의한 목적식과 제약식을 라그랑지안 문제로 식을 다시 쓰면 다음과 같습니다.

원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.

Dual 문제로 변환

KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 최소값을 갖습니다. 다음과 같습니다.

위 식을 $L$에 넣어 정리해 보겠습니다. 우선 첫번째 항부터 보겠습니다.

이번엔 두번째 항입니다.

지금까지 도출한 결과를 토대로 $L_p$를 정리하면 다음과 같습니다. 식을 변형하는 과정에서 $α$에 관한 식으로 간단해졌습니다. $α$의 최고차항의 계수가 음수이므로 최소값을 찾는 문제가 최대값을 찾는 문제로 바뀌었습니다. 이로써 Dual 문제로 변환된 것입니다.

KKT 조건에 의해 $L_D$의 제약식은 다음과 같습니다.

SVM의 해

우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.

$x_i$와 $y_i$는 우리가 가지고 있는 학습데이터이므로 라그랑지안 승수인 $α$값들만 알면 $w$를 찾을 수 있습니다. 그런데 여기에서 $α_i$가 0인 관측치들은 분류경계면 형성에 아무런 영향을 끼치지 못합니다. 바꿔 말해 $i$번째 관측치에 대응하는 라그랑지안 승수 $α_i$가 0보다 커야 마진 결정에 유의미하다는 이야기입니다.

아울러 KKT 조건에 의해 해당 함수가 최적값을 갖는다면 아래 두 개 가운데 하나는 반드시 0입니다.

(1) $α_i$

(2) $y_i(w^Tx_i+b-1)$

$α_i$가 0이 아니라면 $y_i(w^Tx_i+b-1)$가 반드시 0입니다. 따라서 $x_i$는 plus-plane 또는 minus-plane 위에 있는 벡터가 됩니다. 이렇게 마진 결정에 영향을 끼치는 관측치들을 서포트 벡터(support vectors)라고 합니다. 아래 그림(출처)과 같습니다.

한편 $b$는 이미 구한 $w$와 학습데이터, $y_i(w^Tx_i+b-1)=0$ 식을 활용해 바로 구할 수 있게 됩니다. 새로운 데이터가 들어왔을 때는 해당 관측치를 $y_i(w^Tx_i+b-1)$에 넣어서 0보다 크면 1, 0보다 작으면 -1 범주로 예측하면 됩니다.

Comments