SVM (Support Vector Machine)

분류와 회귀 분석을 위한 대표적인 머신러닝 기법인 SVM에 대한 정리

SVM 개요

• SVM(Support Vector Machine)은 전통적인 이진 분류를 위한 기법 중 하나로, N 차원 공간을 N-1 차원으로 나눌 수 있는 초평면(hyper plane)을 찾는 분류 기법.
• 초평면은 어떤 N차원 공간에서 한 차원 낮은 N-1차원의 subspace을 의미하며 예를 들어, 2차원에서 데이터를 다룰 경우 2차원 데이터를 분류할 수 있는 1차원 선으로 초평면이 결정된다.
• 두 클래스(데이터) 사이에 존재하는 ‘여백(margin)을 최대화’ 하려는 목적으로 설계됨.
• 비선형 데이터의 경우 커널 트릭(Kernel Trick)을 활용하여 고차원 공간으로 변환하여 분류함.

---

SVM의 Decision Rule

결정 초평면(Decision Hyperplane)

• 법선 벡터와 임의의 실수를 이용하면 n차원 공간에서의 초평면(hyperplane)을 알아낼 수 있다.
• SVM의 결정 규칙(Decision Rule) 은 학습된 모델을 사용하여 새로운 데이터 포인트 $\mathbf{x}$가 어떤 클래스로 분류되는지를 결정하는 규칙.
• SVM의 목표는 데이터를 가장 잘 구분하는 결정 초평면(Decision Hyperplane) 을 찾는 것으로 2차원 데이터를 예로 들어, 직선의 방정식은 아래와 같다.

$$\begin{array}{rl}f(x)& ={\mathbf{w}}^T\mathbf{x}+b=0\\ & \\ & =\mathbf{w}\cdot \mathbf{x}+b=0\end{array}$$

• 이때, $\mathbf{w}$ 는 초평면의 법선 벡터(normal vector) 이고 $b$는 바이어스(bias)를 의미함.
• 따라서, 초평면 직선을 기준으로 법선 벡터 $\mathbf{w}$와 임의의 데이터 $\mathbf{x}$에 대해 $\mathbf{w}\cdot \mathbf{x}+b$ 의 값이 특정 상수보다 큰지 작은지를 확인하여 클래스를 분류할 수 있다.

Margin

• 최대화하려는 m argin을 정의하기 전에 먼저 임의로 2개의 평행한 직선을 정의해야 한다.

• 초평면에 가장 가까운 샘플(support vector)을 이용하여 초평면에 평행하고 임의의 $\delta$ 만큼 동일하게 떨어진 두 직선은 아래 조건을 만족해야 한다.
• ${\mathbf{x}}^{+}$ 는 임의의 + 클래스의 데이터, ${\mathbf{x}}^{-}$ 는 임의의 - 클래스의 데이터

$$\begin{array}{r}\mathbf{w}\cdot {\mathbf{x}}^{+}+b\ge +\delta \\ \mathbf{w}\cdot {\mathbf{x}}^{-}+b\le -\delta \end{array}$$

• 위 식을 정규화하여 단순하게 만들면 아래와 같다.

$$\begin{array}{r}\mathbf{w}\cdot {\mathbf{x}}^{+}+b\ge +1\\ \mathbf{w}\cdot {\mathbf{x}}^{-}+b\le -1\end{array}$$

• + 클래스를 +1로, -클래스를 -1로 두어 클래스를 나타내는 $y_i$ 를 표현하면 아래와 같다.

$$\begin{array}{rl}{y}_i& =\{\begin{array}{ll}+1& for+\\ -1& for-\end{array}\end{array}$$

• $y_i$ 를 이용해 두 평행한 직선 조건을 하나의 식으로 만들면 아래와 같다. 제약식이라 할 수 있다.

$$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1=$$ $$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1\ge 0$$

• 이때 두 평행한 직선(초평면) 위에 있는 모든 점들을 Support Vector라 한다.
• 마진은 +초평면과 -초평면 사이의 거리를 의미함. 위 그림에서 직선 $b_1$과 $b_2$사이의 거리를 의미하며 마진은 다음과 같이 유도할 수 있다.
• 서포트 벡터 ${\mathbf{x}}_{+}$ 와 ${\mathbf{x}}_{-}$는 각 평행초평면에 가장 가까운 데이터 포인트이며, 각각 다음을 만족한다.

$$\begin{array}{rl}\mathbf{w}\cdot {\mathbf{x}}_{+}+b& =+1\\ \mathbf{w}\cdot {\mathbf{x}}_{-}+b& =-1\end{array}$$

• 점과 평면 사이의 거리 공식을 이용하여 결정 초평면과 서포트 벡터 ${\mathbf{x}}_{+}$ 와 ${\mathbf{x}}_{-}$ 각각의 거리를 계산하면 아래와 같다.

$$\begin{array}{rl}(\text{점과 평면 사이의 거리})& =\frac{|\mathbf{w}\cdot \mathbf{x}+b|}{||\mathbf{w}|{|}_2}\\ & \\ (\text{결정 초평면과 }{\mathbf{x}}_{+}\text{ 사이의 거리)}& =\frac{|\mathbf{w}\cdot {\mathbf{x}}_{+}+b|}{||\mathbf{w}|{|}_2}=\frac{1}{||\mathbf{w}|{|}_2}\\ (\text{결정 초평면과 }{\mathbf{x}}_{-}\text{ 사이의 거리)}& =\frac{|\mathbf{w}\cdot {\mathbf{x}}_{-}+b|}{||\mathbf{w}|{|}_2}=\frac{1}{||\mathbf{w}|{|}_2}\end{array}$$

• 따라서, 마진(Margin)은 두 서포트 벡터 사이의 거리 이므로, 아래와 같다.

$$\text{Margin}=\frac{1}{||\mathbf{w}|{|}_2}+\frac{1}{||\mathbf{w}|{|}_2}=\frac{2}{||\mathbf{w}|{|}_2}$$

Optimization

Linear SVM 정의

• SVM의 목적은 마진을 최대화하는 경계면을 찾는 것.

$$\underset{\mathbf{w},b}{\max }\frac{2}{||\mathbf{w}|{|}_2}$$

• 수학적 계산의 용이함을 위해 마진의 절반을 제곱한 것에 역수를 취한 뒤 그 절반을 최소화하는 문제로 바꿀 수 있다.($||\mathbf{w}|{|}_2$이 제곱근을 포함하고 있기 때문에 풀기 어렵다)

$$\underset{\mathbf{w},b}{\max }\frac{2}{||\mathbf{w}|{|}_2}\to \underset{\mathbf{w},b}{\min }\frac{1}{2}||\mathbf{w}|{|}_2^2$$

• 위 식이 SVM 문제를 해결하기 위한 목적식(Objective) 이며, 만족해야하는 제약식(Constraint) 은 아래와 같다.

$$y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1$$

• 위에서 정의된 목적식과 제약식이 선형 분리를 위한 Hard Margin SVM 최적화 방법이며 모든 데이터 포인트가 결정 초평면으로부터 일정 거리 이상 떨어져 있어야 하므로, 완전히 선형 분리가 가능한 경우에 적용된다.
• Soft Margin SVM은 실제 데이터는 완벽하게 선형 분리가 되지 않는 경우가 많으므로, 허용 오차를 추가하여 최적의 초평면을 구하도록 설계되었다.(완벽한 선형 분리가 불가능할 때 오류를 허용하는 방법)

라그랑주 함수(Lagrangian) 정의

• 제약 조건을 포함한 최적화 문제를 풀기 위해 라그랑주 승수법(Lagrange Multipliers) 을 사용함.
• 제약 조건을 라그랑주 승수 ${\alpha }_i$ 를 사용하여 라그랑주 함수를 아래와 같이 구성할 수 있다.

$$\min L(\mathbf{w},b,{\alpha }_i)=\frac{1}{2}||\mathbf{w}|{|}_2^2-\sum _{i=1}^n{\alpha }_i(y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1)\text{\hspace{1em}(1)}$$

• 여기서, 위 식은 아래를 만족함.
  • 목적 함수에 제약 조건이 포함되었음
  • ${\alpha }_i$ 는 라그랑주 승수 (각 데이터 포인트에 대해 하나씩 존재)
  • ${\alpha }_i\ge 0$ (KTT* 조건에 의해)

KTT(Karush-Kuhn-Tucker) 조건은 제약이 있는 최적화 문제의 해가 되기 위한 필수 조건이며, 아래 조건을 포함 한다.

1. 모든 변수에 대한 미분값은 0이다.
2. 모든 라그랑주 승수값과 제약 조건 부등식의 곱은 0이다.
3. 라그랑주 승수값은 음수가 아니다.

• 목적함수 $L(\mathbf{w},b,\alpha )$를 $\mathbf{w}$와 $b$에 대해 편미분하여 0으로 설정하면 다음과 같다.(각 편미분 0이 되는 지점에서 최소값을 가지므로)

$$\begin{array}{rl}\frac{\partial L}{\partial \mathbf{w}}& =\mathbf{w}-\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i=0\\ & \mathbf{w}=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i\end{array}\text{\hspace{1em}(2)}$$ $$\begin{array}{rl}\frac{\partial L}{\partial b}& =-\sum _{i=1}^n{\alpha }_i{y}_i=0\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}\text{\hspace{1em}(3)}$$

• 즉, $\mathbf{w}$는 일부 데이터 샘플(서포트 벡터)들의 선형 합으로 나타 낼 수 있다.
• 서포트 벡터는 ${\alpha }_i>0$ 인 데이터 포인트가 된다. 경계선에 존재하는 샘플 ${\mathbf{x}}_i$​를 제외하고 모든 샘플에서의 ${\alpha }_i$ 값은 0이 된다.
• 따라서, $\alpha$ 값만 알게되면 $\mathbf{w}$를 구할 수 있다.

듀얼 문제(Dual Problem) 유도 및 해결

• 라그랑주 함수식(1)에 $\mathbf{w}$와 $b$의 편미분 식 (2), (3)을 대입하여 정리하면, 라그랑주 함수 식을 변형한 목적 함수의 dual problem(쌍대 형식)을 유도할 수 있다.
• 아래와 같이 $\alpha$에 대한 최적 문제로 정리된다.

$$\begin{array}{rl}\frac{1}{2}||\mathbf{w}|{|}^2-\sum _{i=1}^n{\alpha }_i(y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1)& =\sum _{i=1}^n{\alpha }_i+\frac{1}{2}||\mathbf{w}|{|}^2-\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{w}}^T{\mathbf{x}}_i\\ & =\sum _{i=1}^n{\alpha }_i+\frac{1}{2}{\mathbf{w}}^T\mathbf{w}-{\mathbf{w}}^T\mathbf{w}\\ & =\sum _{i=1}^n{\alpha }_i-\frac{1}{2}{\mathbf{w}}^T\mathbf{w}\\ & =\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{\mathbf{x}}_i^T{\mathbf{x}}_j\\ & \\ & =L(\alpha )\end{array}$$

• $L$ 을 최대화
• 위 문제를 풀어 $\alpha$를 구할 수 있고, $\alpha$를 식 (2)인 \mathbf w = \sum\limits_{i=1}^{n}\alpha_i y_i \mathbf x_i \tag{2} 에 대입하여 $\mathbf{w}$를 구할 수 있게 된다.
• $\mathbf{w}$를 알게되면 제약식 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$ 을 이용해 $b$ 역시 구할 수 있게 된다.

---

참고

• Support vector machine - Wikipedia
• 서포트 벡터 머신 - 위키백과, 우리 모두의 백과사전
• Jaejun Yoo’s Playground: 초짜 대학원생의 입장에서 이해하는 Support Vector Machine (1)
• 16. Learning: Support Vector Machines - YouTube
• [파이썬/머신러닝] SVM(Support Vector Machine) 분류 - 이론 : 네이버 블로그
• 서포트 벡터 머신 (Support Vector Machine) · ratsgo’s blog
• [데이터마이닝] Support Vector Machine (SVM)
• [ML] Support Vector Machine(SVM)