서포트 벡터 머신(SVM)의 최적화
본 포스팅은 고려대학교 강필성 교수님의 강의를 참고하여, SVM의 최적화 방법을 다룬 포스팅입니다. SVM의 기본 정의만 궁굼하신 분은 제 이전 포스팅을 참고해주세요!
서포트 벡터 머신은 두 데이터 집합을 나누는 결정 경계의 마진(margin)이 최대화 되는 결정 경계 $wx+b=0$를 탐색하는 모델이다. 마진이란 결정 경계와 가장 가까운 샘플인 서포트 벡터와 결정 경계의 거리를 의미한다.
위 그림에서, 파란색 샘플들의 클래스가 $y_i=1$이고 빨간색 샘플들의 클래스가 $y_i=-1$이라고 하면, 모든 샘플이 $y_i(wx+b) \geq 1$을 만족한다.
자료에 따라 결정 경계와 서포트 벡터의 거리 $\frac{1}{||w||^2}$를 마진으로 보기도 하고 서포트 벡터와 서포트 벡터의 거리 (즉, 앞선 마진의 두배) $\frac{2}{||w||^2}$를 마진으로 보기도 하는데, 결국 최적화 대상은 동일하다.
SVM 목적 함수
마진의 최대화를 수식으로 나타내면 다음과 같다.
$$ \max\frac{2}{||w||^2}$$
최적화 문제 풀이의 편의를 위해, 목적 함수에 역수를 취하여 최소화 문제로 바꿔줄 수 있다.
$$ \min\frac{1}{2}||w||^2$$
라그랑주 승수법을 통한 원초 문제 정의
라그랑주 승수법은 제약이 있는 문제의 제약식에 라그랑주 승수($\alpha$)를 곱하여 제약이 없는 문제로 변형하는 것이다.
이때, 올바른 분류를 위해 앞서 언급한 $y_i(wx+b) \geq 1$의 제약 조건을 추가하여 라그랑주 승수법 형태로 목적함수를 변환하면 다음과 같다.
$$ \min L_p(w, b, \alpha_i) = \frac{1}{2}||w||^2 - \sum^N_{i=1} \alpha_i \psi_i \\
\psi_i = (y_i(wx_i + b)-1) \\
s.t. \alpha_i \geq 0$$
라그랑주 승수법을 모르면 약간 헷갈릴 수 있는데, 위 식에서 $\psi$는 SVM의 제약식을 나타낸다. 만약 샘플 $x_i$가 서포트 벡터보다 결정경계에서 멀리 떨어져 있다면 $\psi_i$는 0 이상의 값을 가지게 되고, 그렇지 않다면 0 미만의 값을 가진다. (즉, 분류가 잘 되었으면 0 이상, 그렇지 않으면 0 미만)
$L_p$를 최소화하기 위해서는 $\psi_i$ 항이 최대화되어야 하기 때문에, 결국 모델이 최적화되는 과정에서 제약 조건이 적용되게 된다. 다만, 라그랑주 승수법을 통해 제약 조건이 조건 형태가 아닌 $\alpha$에 의한 규제 항 형식으로 변환된 것이다.
이렇게 정의된 $L_p$가 SVM의 원초 문제(Primal Problem)가 된다.
쌍대 문제로 전환
쌍대 문제란 특정 조건을 만족할 때, 원초 문제와 동일한 해를 갖는 문제를 의미한다. 원초 문제가 컨벡스하지 않아 해를 구하기 어려울 때, 같은 해를 갖는 컨벡스한 쌍대 문제를 통해 해를 구하는 우회적인 방법을 사용한다.
앞서 $L_p$ 식이 최저일 때, 즉 변수 $w, b$에 대한 편미분이 0일 때 다음과 같은 조건이 성립한다.
$$ \frac{\partial L_p}{\partial w} = 0 \rightarrow w=\sum^N_{i=1}\alpha_iy_ix_i$$
$$\frac{\partial L_p}{\partial b} = 0 \rightarrow \sum^N_{i=1}\alpha_iy_i=0$$
$L_p$에 $w=\sum^N_{i=1}\alpha_iy_ix_i$를 대입하여 아래와 같은 쌍대 문제 $L_D$를 얻는다.
$$L_D = \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_jx_ix_j - \sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_jx_ix_j - b\sum^N_{i=1}\alpha_iy_i + \sum^N_{i=1}\alpha_i$$
위 식에 $\sum^N_{i=1}\alpha_iy_i=0$를 대입해 정리하면 아래와 같다.
$$L_D = \sum^N_{i=1}\alpha_i - \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_jx_ix_j $$
이렇게 구해진 $L_D$가 $\alpha$에 대한 컨벡스 함수이기 때문에, $L_D$가 최대화되는 $\alpha$의 최적해를 찾을 수 있다.
변환된 SVM 예측
이제 최적의 $\alpha$ 값을 알게 되었으니, $w=\sum^N_{i=1}\alpha_iy_ix_i$를 이용해 새로운 데이터 $x_{new}$가 입력되었을 때 다음과 같이 예측을 수행할 수 있다.
$$ f(x_{new}) = \text{sign}(\sum^N_{i=1}\alpha_iy_ix_i^Tx_{new} + b)$$
$x_i$와 $y_i$는 학습 데이터로 고정된 값이고, $b$는 $y_i(wx_i+b-1)=0$의 식을 통해 구할 수 있기 때문에 결국 쌍대 문제에서 $\alpha$의 해만 구하면 SVM을 최적화할 수 있게되는 것이다.
서포트 벡터
앞서 $ w=\sum^N_{i=1}\alpha_iy_ix_i$를 통해 예측을 수행했는데, 이때 $\alpha_i=0$일 경우 해당 샘플 $x_i$는 $w$의 결정에 아무런 영향을 주지 않는 것을 알 수 있다. 즉, 라그랑지안 승수 $\alpha_i>0$인 샘플들만 결정 경계를 만드는데 영향을 주는 것인데 이 샘플들이 바로 서포트 벡터이다.
KKT 조건에 의해 $\alpha_i \neq 0$이라면 제약식 $y_i(wx_i+b)-1$이 반드시 0이어야 $\alpha$의 최적해가 존재할 수 있게 된다. 따라서, 서포트 벡터 $x_i$는 반드시 $wx_i+b=1 \text{or} wx_i+b=-1$에 위에 존재하게 된다.
커널 트릭
선형 모델인 SVM을 이용해 비선형 문제를 풀기 위해, 변수 $x$에 커널함수 $\phi$를 씌워 사용하기도 한다. 이때, $\phi(x)$를 새로운 입력 변수로 활용할 것 없이 쌍대 문제의 $x$에 바로 적용하는 형태로 계산을 효율적으로 수행할 수 있다.
예를 들어, 앞서 쌍대 문제를 최소화 문제로 바꾼 아래 식을 보자.
$$\min_\alpha \frac{1}{2}\sum^N_{i=1} \sum^N_{j=1}\alpha_i\alpha_jy_iy_jx_ix_j - \sum^N_{i=1}\alpha_i$$
위 식에서 $x_ix_j$를 $(x_ix_j)^2$으로 바꿔주면 $\phi(x) = x^2$의 커널이 적용된다.
커널 트릭을 적용한 SVM의 파라미터를 계산할 때 $\alpha=0$이라면 커널이 적용되지 않은 $x_{new}$나 커널이 적용된 $\phi(x_{new})$나 같은 결과가 나오기 때문에, $\alpha \neq 0$인 서포트 벡터에 대해서만 $\phi(x_{new})$의 점곱을 새롭게 수행해주면 된다.