C-SVM
29 May 2017 | Support Vector Machine
이번 글에서는 서포트 벡터 머신(SVM)의 변형인 C-SVM에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. SVM의 일반적인 내용에 대해서는 이곳을 참고하시기 바랍니다. 그럼 시작하겠습니다.
C-SVM의 목적의식
SVM은 두 범주를 잘 분류하면서 마진(margin)이 최대화된 초평면(hyperplane)을 찾는 기법입니다. 기본적으로 선형분류를 한다는 것이죠. 하지만 아래 그림처럼 어떤 직선을 그어도 두 범주를 완벽하게 분류하기 어려운 경우도 많습니다.
이 경우에는 두 가지 해결 방법이 있습니다. minus-plane과 plus-plane 사이(즉 마진) 안에 관측치가 존재할 수 있도록 제약을 완화하는 방안이 첫번째입니다. 두번째로는 분류 경계면을 아예 구불구불한 비선형 모양으로 만드는 겁니다. 전자가 C-SVM, 후자가 Kernel-SVM 기법의 핵심 아이디어입니다. Kernel-SVM 기법에 대해서는 이곳을 참고하시면 좋을 것 같습니다.
C-SVM 개요
기존 SVM은 마진 안에 관측치가 들어올 수 없습니다(hard-margin). 마진 폭이 줄어드는 걸 감수하고서라도 그런 관측치가 없도록 마진을 설정하기 때문이죠. 그런데 C-SVM은 마진 안에 관측치의 존재를 허용합니다. 이를 Soft-margin이라고 합니다. 아래 그림을 보겠습니다.
위 그림에서 minus-plane을 벗어난 빨간점과 plus-plane을 벗어난 파란점이 눈에 띕니다. 마진을 최대화하되 이런 관측치들을 허용하는 게 바로 C-SVM입니다. 다만 plus/minus-plane을 벗어난 $ξ$ 만큼 panelty를 부과합니다. 우리가 찾아야할 C-SVM의 초평면을 $w^Tx+b$라고 할 때 C-SVM의 목적식은 다음과 같습니다. ($n$=관측치 개수)
\[\min { \frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 } } +C\sum _{ i=1 }^{ n }{ { \xi }_{ i } }\]
위 목적식에서 $C$는 사용자가 설정하는 하이퍼파라메터(hyperparameter)입니다. $C$가 커질수록 마진 폭이 줄어듭니다. 이 기법이 C-SVM으로 불리는 이유입니다. $C$의 크기에 따른 효과는 이후 자세히 살펴보겠습니다.
C-SVM의 제약식은 다음과 같습니다. ($i=1,2,…,n$)
\[{ y }_{ i }({ w }^{ T }{ x }_{ i }+b)\ge 1-{ \xi }_{ i },\quad { \xi }_{ i }\ge 0\]
제약식의 의미는 이렇습니다. 원 SVM의 제약식은 $y_i(w^Tx_i+b)≥1$이었습니다. 마진 폭이 $ξ_i$만큼 줄어들 수 있기 때문에 이를 반영한 것입니다. $ξ_i$가 음수라면 plus/minus-plane을 벗어나지 않은 경우이므로 고려할 필요가 없습니다.
해 구하기
제약식에 라그랑지안 승수를 곱해 목적식에 합쳐 라그랑지안 Primal 문제로 바꾸면 다음과 같습니다.
\[{ \min { L_{ p }(w,b,{ { \xi }_{ i },\alpha }_{ i },{ \mu }_{ i }) } }=\frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 }+C\sum _{ i=1 }^{ n }{ { \xi }_{ i } } -\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1 + {\xi}_{ i }) } -\sum _{ i=1 }^{ n }{ { { \mu }_{ i }\xi }_{ i } }\]
원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.
\[{ \alpha }_{ i }\ge 0,\quad{ \mu }_{ i }\ge 0,\quad i=1,...,n\]
KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 $L_p$가 최소값을 갖습니다. 다음과 같습니다.
\[\begin{align*}
\frac { \partial L_{p} }{ \partial w } =0\quad &\rightarrow \quad w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } } \\ \frac { \partial L_{p} }{ \partial b } =0\quad &\rightarrow \quad \sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0\\\frac { \partial L_{ p } }{ \partial { \xi }_{ i } } =0\quad &\rightarrow \quad C-{ \alpha }_{ i }-{ \mu }_{ i }=0
\end{align*}\]
위 식을 $L$에 넣어 정리하면 라그랑지안 Primal 문제가 Dual 문제로 바뀝니다. $a_i$에 관한 문제로 단순해졌고, 미지수 최고차항 계수가 음수여서 최대화 문제로 바뀌었습니다. 이는 기존 SVM의 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
\\0\le { \alpha }_{ i }\le C,\quad i=1,...,n\]
위 제약식에서 $0≤α_i≤C$가 도출된 배경은 이렇습니다. $L_p$ 제약에 의해 $α_i$, $μ_i$는 모두 0 이상의 값을 가져야 합니다. 여기에서 KKT 조건에 의해 $L_p$를 $ξ_i$로 미분한 식을 0으로 두고 풀어서 나온 $C-α_i-μ_i=0$을 생각해 봅시다. 그렇다면 $α_i$는 아무리 커도 $C$ 이상의 값을 가질 수 없습니다.
C-SVM의 서포트 벡터
우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.
\[w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } }\]
$x_i$와 $y_i$는 우리가 가지고 있는 학습데이터이므로 라그랑지안 승수인 $α_i$값들만 알면 $w$를 찾을 수 있습니다. 그런데 여기에서 $α_i$가 0인 관측치들은 분류경계면 형성에 아무런 영향을 끼치지 못하는 non-support vector들입니다.
KKT 조건에 의해 $L_D$가 최대값을 갖는다면 아래 두 개 가운데 하나는 반드시 0입니다.
(1) $α_i$
(2) $y_i(w^Tx_i+b)-1+{\xi}_{i}$
아울러 아래 두 개 가운데 하나도 반드시 0입니다.
(1) $μ_i$
(2) $ξ_i$
$α_i$는 다음의 범위를 갖습니다.
\[0\le { \alpha }_{ i }\le C\]
$α_i$가 0보다 크고 $C$ 이하라면 $y_i(w^Tx_i+b)-1+ξ_{i}$는 0입니다. $ξ_{i}$는 0이 될 수 있습니다(${\mu}_{i}$가 0보다 큰 값인 경우). 따라서 이 조건을 만족하는 관측치들은 마진 위에 있는 support vector들이 됩니다.
$α_i$가 $C$라면 $μ_i$는 0입니다. $C-α_i-μ_i=0$가 성립해야 하기 때문입니다. 그러면 $ξ_i$는 0보다 큰 값을 갖습니다. 따라서 이 조건을 만족하는 관측치들은 plus-plane과 minus-plane 사이에 있는, 즉 마진 안에 있는 support vector들이 됩니다.
C의 효과
하이퍼파라메터 $C$는 마진 폭을 줄이거나 넓히는 역할을 합니다. $C$가 크면 라그랑지안 문제에서 $ξ_i$의 역할이 커지고, 그만큼 마진 폭이 줄어듭니다. 그 효과를 나타낸 그림은 아래와 같습니다.
이번 글에서는 서포트 벡터 머신(SVM)의 변형인 C-SVM에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. SVM의 일반적인 내용에 대해서는 이곳을 참고하시기 바랍니다. 그럼 시작하겠습니다.
C-SVM의 목적의식
SVM은 두 범주를 잘 분류하면서 마진(margin)이 최대화된 초평면(hyperplane)을 찾는 기법입니다. 기본적으로 선형분류를 한다는 것이죠. 하지만 아래 그림처럼 어떤 직선을 그어도 두 범주를 완벽하게 분류하기 어려운 경우도 많습니다.
이 경우에는 두 가지 해결 방법이 있습니다. minus-plane과 plus-plane 사이(즉 마진) 안에 관측치가 존재할 수 있도록 제약을 완화하는 방안이 첫번째입니다. 두번째로는 분류 경계면을 아예 구불구불한 비선형 모양으로 만드는 겁니다. 전자가 C-SVM, 후자가 Kernel-SVM 기법의 핵심 아이디어입니다. Kernel-SVM 기법에 대해서는 이곳을 참고하시면 좋을 것 같습니다.
C-SVM 개요
기존 SVM은 마진 안에 관측치가 들어올 수 없습니다(hard-margin). 마진 폭이 줄어드는 걸 감수하고서라도 그런 관측치가 없도록 마진을 설정하기 때문이죠. 그런데 C-SVM은 마진 안에 관측치의 존재를 허용합니다. 이를 Soft-margin이라고 합니다. 아래 그림을 보겠습니다.
위 그림에서 minus-plane을 벗어난 빨간점과 plus-plane을 벗어난 파란점이 눈에 띕니다. 마진을 최대화하되 이런 관측치들을 허용하는 게 바로 C-SVM입니다. 다만 plus/minus-plane을 벗어난 $ξ$ 만큼 panelty를 부과합니다. 우리가 찾아야할 C-SVM의 초평면을 $w^Tx+b$라고 할 때 C-SVM의 목적식은 다음과 같습니다. ($n$=관측치 개수)
\[\min { \frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 } } +C\sum _{ i=1 }^{ n }{ { \xi }_{ i } }\]위 목적식에서 $C$는 사용자가 설정하는 하이퍼파라메터(hyperparameter)입니다. $C$가 커질수록 마진 폭이 줄어듭니다. 이 기법이 C-SVM으로 불리는 이유입니다. $C$의 크기에 따른 효과는 이후 자세히 살펴보겠습니다.
C-SVM의 제약식은 다음과 같습니다. ($i=1,2,…,n$)
\[{ y }_{ i }({ w }^{ T }{ x }_{ i }+b)\ge 1-{ \xi }_{ i },\quad { \xi }_{ i }\ge 0\]제약식의 의미는 이렇습니다. 원 SVM의 제약식은 $y_i(w^Tx_i+b)≥1$이었습니다. 마진 폭이 $ξ_i$만큼 줄어들 수 있기 때문에 이를 반영한 것입니다. $ξ_i$가 음수라면 plus/minus-plane을 벗어나지 않은 경우이므로 고려할 필요가 없습니다.
해 구하기
제약식에 라그랑지안 승수를 곱해 목적식에 합쳐 라그랑지안 Primal 문제로 바꾸면 다음과 같습니다.
\[{ \min { L_{ p }(w,b,{ { \xi }_{ i },\alpha }_{ i },{ \mu }_{ i }) } }=\frac { 1 }{ 2 } { \left\| w \right\| }_{ 2 }^{ 2 }+C\sum _{ i=1 }^{ n }{ { \xi }_{ i } } -\sum _{ i=1 }^{ n }{ { \alpha }_{ i }({ y }_{ i }({ w }^{ T }{ x }_{ i }+b)-1 + {\xi}_{ i }) } -\sum _{ i=1 }^{ n }{ { { \mu }_{ i }\xi }_{ i } }\]원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.
\[{ \alpha }_{ i }\ge 0,\quad{ \mu }_{ i }\ge 0,\quad i=1,...,n\]KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 $L_p$가 최소값을 갖습니다. 다음과 같습니다.
\[\begin{align*} \frac { \partial L_{p} }{ \partial w } =0\quad &\rightarrow \quad w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } } \\ \frac { \partial L_{p} }{ \partial b } =0\quad &\rightarrow \quad \sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0\\\frac { \partial L_{ p } }{ \partial { \xi }_{ i } } =0\quad &\rightarrow \quad C-{ \alpha }_{ i }-{ \mu }_{ i }=0 \end{align*}\]위 식을 $L$에 넣어 정리하면 라그랑지안 Primal 문제가 Dual 문제로 바뀝니다. $a_i$에 관한 문제로 단순해졌고, 미지수 최고차항 계수가 음수여서 최대화 문제로 바뀌었습니다. 이는 기존 SVM의 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 \\0\le { \alpha }_{ i }\le C,\quad i=1,...,n\]위 제약식에서 $0≤α_i≤C$가 도출된 배경은 이렇습니다. $L_p$ 제약에 의해 $α_i$, $μ_i$는 모두 0 이상의 값을 가져야 합니다. 여기에서 KKT 조건에 의해 $L_p$를 $ξ_i$로 미분한 식을 0으로 두고 풀어서 나온 $C-α_i-μ_i=0$을 생각해 봅시다. 그렇다면 $α_i$는 아무리 커도 $C$ 이상의 값을 가질 수 없습니다.
C-SVM의 서포트 벡터
우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.
\[w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } }\]$x_i$와 $y_i$는 우리가 가지고 있는 학습데이터이므로 라그랑지안 승수인 $α_i$값들만 알면 $w$를 찾을 수 있습니다. 그런데 여기에서 $α_i$가 0인 관측치들은 분류경계면 형성에 아무런 영향을 끼치지 못하는 non-support vector들입니다.
KKT 조건에 의해 $L_D$가 최대값을 갖는다면 아래 두 개 가운데 하나는 반드시 0입니다.
(1) $α_i$
(2) $y_i(w^Tx_i+b)-1+{\xi}_{i}$
아울러 아래 두 개 가운데 하나도 반드시 0입니다.
(1) $μ_i$
(2) $ξ_i$
$α_i$는 다음의 범위를 갖습니다.
\[0\le { \alpha }_{ i }\le C\]$α_i$가 0보다 크고 $C$ 이하라면 $y_i(w^Tx_i+b)-1+ξ_{i}$는 0입니다. $ξ_{i}$는 0이 될 수 있습니다(${\mu}_{i}$가 0보다 큰 값인 경우). 따라서 이 조건을 만족하는 관측치들은 마진 위에 있는 support vector들이 됩니다.
$α_i$가 $C$라면 $μ_i$는 0입니다. $C-α_i-μ_i=0$가 성립해야 하기 때문입니다. 그러면 $ξ_i$는 0보다 큰 값을 갖습니다. 따라서 이 조건을 만족하는 관측치들은 plus-plane과 minus-plane 사이에 있는, 즉 마진 안에 있는 support vector들이 됩니다.
C의 효과
하이퍼파라메터 $C$는 마진 폭을 줄이거나 넓히는 역할을 합니다. $C$가 크면 라그랑지안 문제에서 $ξ_i$의 역할이 커지고, 그만큼 마진 폭이 줄어듭니다. 그 효과를 나타낸 그림은 아래와 같습니다.
Comments