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

SVM (Support Vector Machine)

개요

• 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_P(\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_D(\alpha )\\ & \\ & \\ \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{\mathbf{x}}_i^T{\mathbf{x}}_j\\ & \end{array}$$

• 듀얼 형태로 변환 과정을 통해 $\alpha$에 관한 식($L_D$)으로 간단해지고, $\alpha$의 최고차항의 계수가 음수이므로 최소값을 찾는 문제가 최대값을 찾는 문제로 바뀌었다. 즉, 풀고자하는 전체 라그랑주 식을 정리하면 아래와 같다.

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

• 위 문제를 풀어 $\alpha$를 구할 수 있고, $\alpha$를 식 (2)인 $\mathbf{w}=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i$ 에 대입하여 $\mathbf{w}$를 구할 수 있게 된다.
• $\mathbf{w}$를 알게되면 제약식 $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$ 을 이용해 $b$ 역시 구할 수 있게 된다.
• 따라서 support vector들로 이루어진 decision boundary가 가장 최적의 boundary라고 할 수 있다.

Soft Margin

• 모든 샘플들이 경계선 바깥쪽에 올바르게 분류되어 있다면 하드 마진이라고 하지만, 데이터가 선형적으로 구분되어 있어야 제대로 동작하고, 이상치(Outlier)에 민감하다.
• 데이터 포인트가 초평면을 잘못 분류하는 정도를 나타내는 허용 오차(Slack Variable) ${\xi }_i\ge 0$ 를 도입하여​ Margin을 가능한 최대로 유지하는 것을 Soft Margin이라함.
• 따라서, Soft Margin은 마진 오류를 최소화하기 위해 가능한 ${\xi }_i$를 작게 만드는 것과 마진의 역수 $\frac{1}{2}||\mathbf{w}|{|}^2$를 가능한 작게 만드는 것, 두 가지 목표를 가진다.
• 허용오차 ${\xi }_i$를 적용하고, 두 목표 사이의 trade-off 를 조절하는 하이퍼파라미터 $C$를 정의해 아래와 같이 제약과 함께 정의할 수 있다.

$$\underset{\mathbf{w},b,\xi }{\min }\frac{1}{2}||\mathbf{w}|{|}^2+C\sum _{i=1}^n{\xi }_i$$ $$\text{subject to }{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

• 하드 마진과 동일할게 KKT 조건을 만족하도록 라그랑주 승수법을 적용하면 아래와 같은 듀얼 문제의 최적화를 얻을 수 있다.

$$\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{\mathbf{x}}_i^T{\mathbf{x}}_j$$ $$\text{subject to }0\le {\alpha }_i\le C,\sum _{i=1}^n{\alpha }_i{y}_i=0\text{for}i=1,\cdots ,n$$

• 적절한 $C$ 를 적용하여 Soft Margin 최적화를 수행할 수 있다.
  • $C$ 값이 크면 오차에 대한 강한 패널티 → Hard Margin에 가까움, 오버피팅 가능성
  • $C$ 값이 작으면 오차를 어느 정도 허용 → 오버피팅 방지, 언더피팅 가능성

---

Kernel Trick (Non-Linear)

• 기본적으로 SVM은 선형 분류기이며, 선형적으로 구분 가능한 데이터를 다룬다. 하지만 현실에서는 비선형적으로 분포한 데이터가 많아 데이터를 단순한 직선또는 초평면으로 분류할 수 없다.
• 커널 트릭(Kernel Trick)은 비선형 데이터를 다루기 위해, 데이터를 더 높은 공간의 차원으로 변환하여 선형 분리가 가능해지도록 하는 효과를 이용함.

고차원으로의 매핑

• 예를 들어, 다음과 같은 1차워 데이터는 선형으로 분류하기가 힘들다.
• 기저함수(Basis function) $\Phi ,x\to \{x,x^2\}$ 를 이용하여 2차원 feature space로 1차원 데이터를 2차원으로 매핑(mapping)하면 다음과 같이 선형 분류 가능한 공간이 생성된다.

• 아래와 같이 2차원 데이터도 마찬가지로, 선형 분리가 어려운 데이터를 고차원으로 변환하여 선형 분리가 가능한 초평면을 찾을 수 있다.

• 이처럼, 적절히 좋은 mapping function을 찾는 것이 핵심.

---

참고

• 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)
• [머신러닝] Kernel/Kernel trick(커널, 커널트릭)