[머신러닝] SVM (Support Vector Machine)
Support Vector Machine
결정 경계 (Decision Boundary)와 가장 가까운 데이터 샘플을 Support Vector라고 부르고, 각 클래스의 Support Vector 사이의 거리를 마진 (margin)이라고 한다.
SVM은 이 마진을 최대화할 수 있는 결정 경계를 찾는 방법이다.
이전 포스터에서 설명했듯이, 결정 경계는 아래와 같이 표현할 수 있다.
\[\mathbf{w}^\top\mathbf{x}+b=0\]예를 들어, 위의 그림에서 파란색 데이터들의 라벨을 $y=+1$, 빨간색 데이터들의 라벨을 $y=-1$로 두면, 결정 경계로부터의 위치 관계는 아래와 같이 표현된다. 계산의 편의성을 위해, 영역의 범위를 $\geq1$과 $\leq-1$로 설정하였다.
\[\begin{cases} \mathbf{w}^\top\mathbf{x}+b\geq1&\text{if}~~ y=+1\\ \mathbf{w}^\top\mathbf{x}+b\leq-1&\text{if}~~ y=-1 \end{cases}\]위의 조건식은 아래와 같이 하나의 식으로 정리될 수 있다.
\[y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\ge1\]이때 마진은 아래와 같이 정의된다.
\[\text{Margin}=\frac{2}{\lVert\mathbf{w}\rVert}\]공식 유도
두 직선 $w_2x_2+w_1x_1+b-1=0$과 $w_2x_2+w_1x_1+b+1=0$ 사이의 거리 $d$는 아래와 같이 정의된다.
\[d=\frac{\lvert(b-1)-(b+1)\rvert}{\sqrt{w_2^2+w_1^2}}=\frac{2}{\lVert\mathbf{w}\rVert_2}\]SVM의 목표는 마진을 최대화하는 것이므로, 아래와 같이 표현할 수 있다.
\[\max_{\mathbf{w},b}{\frac{2}{\lVert\mathbf{w}\rVert}}\]하지만 분모에 $\lVert\mathbf{w}\rVert$이 존재하면 미분이 복잡해지므로, 계산의 편의성을 위해 동등한 최소화 문제로 변형한다. 또한 미분의 편의성을 위해 $\lVert\mathbf{w}\rVert$에 제곱을 취한 형태로 변형한다.
\[\min_{\mathbf{w},b}{\frac{\vphantom{\Big(}\lVert\mathbf{w}\rVert^2}{2}}\]이때, 제약 조건은 각 데이터 샘플이 올바르게 분리되도록 $y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\ge1$을 만족해야 한다.
SVM은 이러한 제약 조건을 엄격하게 적용하느냐, 혹은 일부 위반을 허용하느냐에 따라 Hard Margin SVM과 Soft Margin SVM으로 구분된다.
Hard Margin SVM
Hard Margin SVM은 단 하나의 오분류도 허용하지 않는 방식으로, 데이터가 선형적으로 완벽하게 분리될 수 있을 때만 사용한다.
Primal Problem
Hard Margin SVM의 목적 함수는 아래와 같이 표현된다.
\[\begin{aligned} \min_{\mathbf{w},b}{\frac{\vphantom{\Big(}\lVert\mathbf{w}\rVert^2}{2}}~~~~~~~~~~~~~~~~~\\ \text{subject to}~~y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\ge1 \end{aligned}\]Dual Problem
Hard Margin SVM 최적화 문제의 Dual Problem은 아래와 같이 정의된다.
\[\begin{aligned} \max_{\mu}{\left(\sum_{i=1}^N\mu^{(i)}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\mu^{(i)}\mu^{(j)}y^{(i)}y^{(j)}\mathbf{x}^{(i)}\mathbf{x}^{(j)}\right)}\\ \text{subject to}~~\sum_{i=1}^N\mu^{(i)}y^{(i)}\mathbf{x}^{(i)}=0~~~~~~~~~~~~~~\\ \mu_i\geq0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}\]라그랑주 승수법이랑 쌍대 문제 (Dual Problem)에 대한 내용은 아래 포스터를 참고해주세요.
공식 유도
1. 라그랑주 함수 정의
\[\mathcal{L}(\mathbf{w},b,\mu)=\frac{\lVert\mathbf{w}\rVert^2}{2}+\sum_{i=1}^N\mu^{(i)}\left[1-y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\right] ~~,~~\mu^{(i)}\geq0\]2. Dual 함수 정의
\[\mathcal{D}(\mu)=\inf_{\mathbf{w},b}~\mathcal{L}(\mathbf{w},b,\mu)\]3. Dual 함수 계산
\[\nabla_\mathbf{w}\mathcal{L}=\mathbf{w}-\sum_{i=1}^N\mu^{(i)}y^{(i)}\mathbf{x}^{(i)}=0~~\to~~\mathbf{w}=\sum_{i=1}^N\mu^{(i)}y^{(i)}\mathbf{x}^{(i)}\] \[\nabla_b\mathcal{L}=-\sum_{i=1}^N\mu_iy_i=0~~\to~~\sum_{i=1}^N\mu_iy_i=0\]이를 $\mathcal{L}$에 대입하면, 아래와 같은 식을 얻을 수 있다.
\[\mathcal{D}(\mu)=\sum_{i=1}^N\mu^{(i)}-\frac{\lVert\mathbf{w}\rVert^2}{2}= \sum_{i=1}^N\mu^{(i)}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\mu^{(i)}\mu^{(j)}y^{(i)}y^{(j)}{\mathbf{x}^{(i)}}^\top\mathbf{x}^{(j)}\]4. Dual Problem 정의
\[\begin{aligned} \max_{\mu}{\left(\sum_{i=1}^N\mu^{(i)}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\mu^{(i)}\mu^{(j)}y^{(i)}y^{(j)}{\mathbf{x}^{(i)}}^\top\mathbf{x}^{(j)}\right)}\\ \text{subject to}~~\sum_{i=1}^N\mu^{(i)}y^{(i)}\mathbf{x}^{(i)}=0~~~~~~~~~~~~~~\\ \mu_i\geq0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}\]Soft Margin SVM
하지만 현실의 데이터에는 이상치 (outlier)가 존재하기 때문에 완벽하게 선형으로 분리하기 어렵다.
따라서 이를 위해 어느 정도의 오분류나 마진 경계를 침범하는 것을 허용하는 Soft Margin SVM을 사용한다.
Primal Problem
Soft Margin SVM의 목적 함수는 아래와 같이 표현된다.
\[\begin{aligned} \min_{\mathbf{w},b,\xi}{\frac{\lVert\mathbf{w}\rVert^2}{2}}+C\sum_{i=1}^N\xi^{(i)} ~~~~~~~~~~~\\ \text{subject to}~~y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\geq1-\xi^{(i)}\\ \xi^{(i)}\geq0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}\]여기서 $\xi$는 슬랙 변수 (Slack Variable)이고, $C$는 슬랙 패널티의 크기를 조절하는 하이퍼파라미터이다.
즉, $\xi$를 통해 일부 데이터가 마진을 침범하거나 오분류되는 것을 허용하고, $C$를 통해 그러한 허용 정도를 조절한다.
슬랙 변수 (Slack Variable)
슬랙 변수 $\xi^{(i)}$는 각 데이터 샘플의 마진 위반 정도를 나타낸다.
\[y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)}+b)\geq1-\xi^{(i)}\]- $\xi^{(i)}=0$ : 해당 샘플이 마진을 침범하지 않은 상태
- $0<\xi^{(i)}<1$ : 해당 샘플이 마진을 침범한 상태이지만 여전히 올바르게 분류되고 있는 상태
- $\xi^{(i)}\geq1$ : 해당 샘플이 결정 경계 반대편으로 넘어간 상태 (오분류)
이때 최적화 식에서 $C$는 마진을 침범한 샘플에게 얼마나 큰 패널티를 가할지를 결정한다.
오분류를 최소화하기 위해서는 $C$값을 키워, 위반한 샘플에게 큰 패널티를 부여하면 된다.
반대로 마진을 더 넓히기 위해서는 $C$값을 줄여, 위반한 샘플에게 작은 패널티를 부여하면 된다.
Dual Problem
Soft Margin SVM 최적화 문제의 Dual Problem은 아래와 같이 정의된다.
\[\begin{aligned} \max_{\mu}{\left(\sum_{i=1}^N\mu^{(i)}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\mu^{(i)}\mu^{(j)}y^{(i)}y^{(j)}{\mathbf{x}^{(i)}}^\top\mathbf{x}^{(j)}\right)}\\ \text{subject to}~~\sum_{i=1}^N\mu^{(i)}y^{(i)}\mathbf{x}^{(i)}=0~~~~~~~~~~~~~~\\ 0\leq\mu_i\leq C~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}\]Hard margin과 형태가 동일하며, 라그랑주 승수에 대한 제약 조건만 $0\leq\mu_i\leq C$으로 바뀐다.