서포트 벡터 머신 (Support Vector Machine)
23 May 2017 | 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 }^{ + }={ x }^{ - }+\lambda w\]
그럼 $λ$은 어떤 값을 지닐까요? $x^+$는 plus-plane, $x^-$는 minus-plane 위에 있다는 사실과 $x^+$와 $x^-$ 사이의 관계식을 활용하면 다음과 같이 유도해낼 수 있습니다.
\[\begin{align*}
{ w }^{ T }{ x }^{ + }+b&=1\\ { w }^{ T }({ x }^{ - }+\lambda w)+b&=1\\ { w }^{ T }{ x }^{ - }+b+\lambda { w }^{ T }w&=1\\ -1+\lambda { w }^{ T }w&=1\\\\ \lambda =\frac { 2 }{ { w }^{ T }w }
\end{align*}\]
마진은 plus-plane과 minus-plane 사이의 거리를 의미합니다. 이는 $x^+$와 $x^-$ 사이의 거리와 같습니다. 둘 사이의 관계식과 $λ$값을 알고 있으므로 식을 정리하면 마진을 다음과 같이 유도할 수 있습니다.
\[\begin{align*}
Margin&=distance({ x }^{ + },{ x }^{ - })\\ &={ \left\| { x }^{ + }-{ x }^{ - } \right\| }_{ 2 }\\ &={ \left\| { x }^{ - }+\lambda w-{ x }^{ - } \right\| }_{ 2 }\\ &={ \left\| \lambda w \right\| }_{ 2 }\\ &=\lambda \sqrt { { w }^{ T }w } \\ &=\frac { 2 }{ { w }^{ T }w } \sqrt { { w }^{ T }w } \\ &=\frac { 2 }{ \sqrt { { w }^{ T }w } } \\ &=\frac { 2 }{ { \left\| w \right\| }_{ 2 } }
\end{align*}\]
목적식과 제약식 정의
SVM의 목적은 마진을 최대화하는 경계면을 찾는 것입니다. 계산상 편의를 위해 마진 절반을 제곱한 것에 역수를 취한 뒤 그 절반을 최소화하는 문제로 바꾸겠습니다. 이렇게 해도 문제의 본질은 바뀌지 않습니다.
\[max\frac { 2 }{ { \left\| w \right\| }_{ 2 } } \rightarrow \min { \frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 } }\]
여기엔 다음과 같은 제약조건이 관측치 개수만큼 붙습니다. 식의 의미는 이렇습니다. plus-plane보다 위에 있는 관측치들은 $y=1$이고 $w^Tx+b$가 1보다 큽니다. 반대로 minus-plane보다 아래에 있는 점들은 $y=-1$이고 $w^Tx+b$가 -1보다 작습니다. 이 두 조건을 한꺼번에 묶으면 아래와 같은 제약식이 됩니다.
\[{ y }_{ i }({ w }^{ T }{ x }_{ i }+b)\ge 1\]
라그랑지안 문제로 변환
라그랑지안 승수법(Lagrange multiplier method)은 제약식에 형식적인 라그랑지안 승수를 곱한 항을 최적화하려는 목적식에 더하여, 제약된 문제를 제약이 없는 문제로 바꾸는 기법입니다. 이에 대해 추가적인 내용은 이곳을 참고하면 좋을 것 같습니다.
우리가 이미 정의한 목적식과 제약식을 라그랑지안 문제로 식을 다시 쓰면 다음과 같습니다.
\[{\min{ L_{p}(w,b,{ \alpha }_{ i }) } } =\frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 }-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1) }\]
원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.
\[{ \alpha }_{ i }\ge 0,\quad i=1,...,n\]
Dual 문제로 변환
KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 최소값을 갖습니다. 다음과 같습니다.
\[\begin{align*}
\frac { \partial L(w,b,{ \alpha }_{ i }) }{ \partial w } =0\quad &\rightarrow \quad w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } } \\ \frac { \partial L(w,b,{ \alpha }_{ i }) }{ \partial b } =0\quad &\rightarrow \quad \sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0
\end{align*}\]
위 식을 $L$에 넣어 정리해 보겠습니다. 우선 첫번째 항부터 보겠습니다.
\[\begin{align*}
\frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 }&=\frac { 1 }{ 2 } { w }^{ T }w\\ &=\frac { 1 }{ 2 } { w }^{ T }\sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ x }_{ j } } \\ &=\frac { 1 }{ 2 } \sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ ({ w }^{ T }x }_{ j }) } \\ &=\frac { 1 }{ 2 } \sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ (\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i }^{ T }{ x }_{ j } } }) } \\ &=\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } }
\end{align*}\]
이번엔 두번째 항입니다.
\[\begin{align*}
-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1) } &=-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }({ w }^{ T }{ x }_{ i }+b) } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \\ &=-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ w }^{ T }{ x }_{ i } } -b\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \\ &=-\sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } }
\end{align*}\]
지금까지 도출한 결과를 토대로 $L_p$를 정리하면 다음과 같습니다. 식을 변형하는 과정에서 $α$에 관한 식으로 간단해졌습니다. $α$의 최고차항의 계수가 음수이므로 최소값을 찾는 문제가 최대값을 찾는 문제로 바뀌었습니다. 이로써 Dual 문제로 변환된 것입니다.
\[\max { { L }_{ D }({ \alpha }_{ i }) } =\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } -\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } }\]
KKT 조건에 의해 $L_D$의 제약식은 다음과 같습니다.
\[\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0
\\{ \alpha }_{ i }\ge 0,\quad i=1,...,n\]
SVM의 해
우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.
\[w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } }\]
$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 범주로 예측하면 됩니다.
이번 글에서는 딥러닝 이전 뛰어난 성능으로 많은 주목을 받았던 서포트 벡터 머신(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 }^{ + }={ x }^{ - }+\lambda w\]그럼 $λ$은 어떤 값을 지닐까요? $x^+$는 plus-plane, $x^-$는 minus-plane 위에 있다는 사실과 $x^+$와 $x^-$ 사이의 관계식을 활용하면 다음과 같이 유도해낼 수 있습니다.
\[\begin{align*} { w }^{ T }{ x }^{ + }+b&=1\\ { w }^{ T }({ x }^{ - }+\lambda w)+b&=1\\ { w }^{ T }{ x }^{ - }+b+\lambda { w }^{ T }w&=1\\ -1+\lambda { w }^{ T }w&=1\\\\ \lambda =\frac { 2 }{ { w }^{ T }w } \end{align*}\]마진은 plus-plane과 minus-plane 사이의 거리를 의미합니다. 이는 $x^+$와 $x^-$ 사이의 거리와 같습니다. 둘 사이의 관계식과 $λ$값을 알고 있으므로 식을 정리하면 마진을 다음과 같이 유도할 수 있습니다.
\[\begin{align*} Margin&=distance({ x }^{ + },{ x }^{ - })\\ &={ \left\| { x }^{ + }-{ x }^{ - } \right\| }_{ 2 }\\ &={ \left\| { x }^{ - }+\lambda w-{ x }^{ - } \right\| }_{ 2 }\\ &={ \left\| \lambda w \right\| }_{ 2 }\\ &=\lambda \sqrt { { w }^{ T }w } \\ &=\frac { 2 }{ { w }^{ T }w } \sqrt { { w }^{ T }w } \\ &=\frac { 2 }{ \sqrt { { w }^{ T }w } } \\ &=\frac { 2 }{ { \left\| w \right\| }_{ 2 } } \end{align*}\]목적식과 제약식 정의
SVM의 목적은 마진을 최대화하는 경계면을 찾는 것입니다. 계산상 편의를 위해 마진 절반을 제곱한 것에 역수를 취한 뒤 그 절반을 최소화하는 문제로 바꾸겠습니다. 이렇게 해도 문제의 본질은 바뀌지 않습니다.
\[max\frac { 2 }{ { \left\| w \right\| }_{ 2 } } \rightarrow \min { \frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 } }\]여기엔 다음과 같은 제약조건이 관측치 개수만큼 붙습니다. 식의 의미는 이렇습니다. plus-plane보다 위에 있는 관측치들은 $y=1$이고 $w^Tx+b$가 1보다 큽니다. 반대로 minus-plane보다 아래에 있는 점들은 $y=-1$이고 $w^Tx+b$가 -1보다 작습니다. 이 두 조건을 한꺼번에 묶으면 아래와 같은 제약식이 됩니다.
\[{ y }_{ i }({ w }^{ T }{ x }_{ i }+b)\ge 1\]라그랑지안 문제로 변환
라그랑지안 승수법(Lagrange multiplier method)은 제약식에 형식적인 라그랑지안 승수를 곱한 항을 최적화하려는 목적식에 더하여, 제약된 문제를 제약이 없는 문제로 바꾸는 기법입니다. 이에 대해 추가적인 내용은 이곳을 참고하면 좋을 것 같습니다.
우리가 이미 정의한 목적식과 제약식을 라그랑지안 문제로 식을 다시 쓰면 다음과 같습니다.
\[{\min{ L_{p}(w,b,{ \alpha }_{ i }) } } =\frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 }-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1) }\]원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.
\[{ \alpha }_{ i }\ge 0,\quad i=1,...,n\]Dual 문제로 변환
KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 최소값을 갖습니다. 다음과 같습니다.
\[\begin{align*} \frac { \partial L(w,b,{ \alpha }_{ i }) }{ \partial w } =0\quad &\rightarrow \quad w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } } \\ \frac { \partial L(w,b,{ \alpha }_{ i }) }{ \partial b } =0\quad &\rightarrow \quad \sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0 \end{align*}\]위 식을 $L$에 넣어 정리해 보겠습니다. 우선 첫번째 항부터 보겠습니다.
\[\begin{align*} \frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 }&=\frac { 1 }{ 2 } { w }^{ T }w\\ &=\frac { 1 }{ 2 } { w }^{ T }\sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ x }_{ j } } \\ &=\frac { 1 }{ 2 } \sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ ({ w }^{ T }x }_{ j }) } \\ &=\frac { 1 }{ 2 } \sum _{ j=1 }^{ n }{ { \alpha }_{ j }{ y }_{ j }{ (\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i }^{ T }{ x }_{ j } } }) } \\ &=\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } } \end{align*}\]이번엔 두번째 항입니다.
\[\begin{align*} -\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1) } &=-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }({ w }^{ T }{ x }_{ i }+b) } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \\ &=-\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ w }^{ T }{ x }_{ i } } -b\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \\ &=-\sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } } +\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } \end{align*}\]지금까지 도출한 결과를 토대로 $L_p$를 정리하면 다음과 같습니다. 식을 변형하는 과정에서 $α$에 관한 식으로 간단해졌습니다. $α$의 최고차항의 계수가 음수이므로 최소값을 찾는 문제가 최대값을 찾는 문제로 바뀌었습니다. 이로써 Dual 문제로 변환된 것입니다.
\[\max { { L }_{ D }({ \alpha }_{ i }) } =\sum _{ i=1 }^{ n }{ { \alpha }_{ i } } -\frac { 1 }{ 2 } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }_{ i }{ { \alpha }_{ j }y }_{ i }{ y }_{ j }{ x }_{ i }^{ T }{ x }_{ j } } }\]KKT 조건에 의해 $L_D$의 제약식은 다음과 같습니다.
\[\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0 \\{ \alpha }_{ i }\ge 0,\quad i=1,...,n\]SVM의 해
우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.
\[w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } }\]$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