Classification with SVM

MATHEMATICS FOR MACHINE LEARNING (Deisenroth, M. P., Faisal, A. A., & Ong, C. S. (2020)) 을 바탕으로 작성되었습니다.

$f : \mathbb{R}^D \rightarrow {\{+1,-1\}}$

이진 분류 문제의 경우 차원 D를 갖는 feature vector들을 두개의 숫자(e.g., +1, -1) 로 mapping하는 적절한 함수 $f$를 찾는 문제라고 할 수 있다.

적절하다는 것은 각 $\vec{x}_n$에 해당하는 정답 $\vec{y}_n \in \{+1,-1\}$ 이 있을 때, 다음과 같이 pair들로 구성된 set$\{(\vec{x}_1,y_1),\cdots\,(\vec{x}_N,y_N)\}$에 대해서 높은 정답률을 갖는다는 것이다.

그리고 이러한 task에 대해서 적절한 $f$를 찾는 방법론 중 하나가
Support Vector Machine 이다.

Separating Hyperplanes

많은 classification algorithm의 아이디어는 $\mathbb{R}^D$ 공간을 적절하게 나눠서 같은 partition의 data들에게 같은 label을 할당하는 것 이다.

D = 2일때의 예시는 다음 그림과 같다.

위 그림과 같은 경우, 직선 하나로 나뉘는 partition을 통해 두 class를 잘 분류할 수 있음이 명확하다.

마찬가지의 binary classification 문제에 대해 linearly splitting하는 경우, $D = 3$ 인 공간에서는 두개의 partition을 만드는 평면을 생각할 수 있고

일반적으로 $D \geq 4$인 경우는 적절한 hyperplane을 고려할 수 있다.

feature vector $\vec{x}$들이 Projection 되었을 때 같은 class끼리 잘 나뉘는 방향벡터 $\vec{w}$ 가 있다면, 해당 $\vec{w}$를 normal vector로 갖고 b만큼 $\vec{w}$방향으로 translation한 hyperplane $f(\vec{x})$=0을 생각할 수 있다.

$f : \mathbb{R}^D \rightarrow \mathbb{R}$
$\vec{x} \mapsto f(\vec{x}) := \lang \vec{w}, \vec{x}\rang + b$

그리고 당연하게도 hyperplane위의 임의의 벡터는 $\vec{w}$와 orthogonal하다.
pf.
$f(\vec{x}_a) - f(\vec{x}_b) = \lang \vec{w}, \vec{x}_a\rang + b - ( \lang \vec{w}, \vec{x}_b\rang + b) = \lang \vec{w} ,\vec{x}_a-\vec{x}_b \rang$
$f(\vec{x}_a) = 0, f(\vec{x}_b)= 0$ 이므로
$\lang \vec{w} ,\vec{x}_a-\vec{x}_b \rang = 0$

hyperplane의 기하학적인 의미를 생각해보면 ,
$y_n = +1$ 일 때, $\lang \vec{w}, \vec{x}_n\rang + b \geq 0$
$y_n = -1$ 일 때, $\lang \vec{w}, \vec{x}_n\rang + b < 0$
가 되도록 학습 시키는 것이 목적이다.

위 두 식은 하나의 식 $y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq 0$ 로 나타낼 수 있다.

상술한 관점에서 두 class를 구분짓는 가능한 hyperplane은 위 그림처럼 무수히 많을 수 있다.

무수히 많은 hyperplane 중에서 우리가 원하는 좋은 hyperplane이란 margin을 최대화시키는 hyperplane이다.

margine이란 hyperplane과 가장 가까운 feature vector $\vec{x}_{a}$ 사이의 거리이다.

Concept of the Margin

$\mathbf{x}^{'}_{a} = \mathbf{x}_{a} + r \frac{\mathbf{w}}{\mathbf{||w||}}$ 이고 $||\mathbf{w}|| = 1$ 이라면 ,

$\mathbf{x}^{'}_{a} = \mathbf{x}_{a} + r{\mathbf{w}}$ 이므로
hyperplane이 적어도 r만큼의 margin을 갖는 상황으로 해석해서

$y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq r$ 로 적을 수 있다.

즉, $||\mathbf{w}|| = 1$ 이라면, 다음과 같은 제약조건을 만족시키는

$y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq r , r>0$

$r$의 최대값을 찾는 문제가 된다.

Hard Magin SVM

$||\mathbf{w}|| = 1$ 라는 normalization 가정을 주지 않았을 경우 margin maximazation problem이 어떻게 되는지 살펴보자.

normalization 가정 대신에, cloest data의 거리가 $\lang \mathbf{w},\mathbf{x}_a\rang +b = 1$이 되도록 data의 scale을 변화시키는 가정을 주자.

$\lang \mathbf{w},\mathbf{x}^{'}_a\rang +b = 0$

$\Rightarrow \lang \mathbf{w},\mathbf{x}_a - r \frac{\mathbf{w}}{\mathbf{||w||}}\rang +b =0$

$\Rightarrow \lang \mathbf{w},\mathbf{x}_a\rang +b -r \frac{\lang\mathbf{w},\mathbf{w}\rang}{\mathbf{||w||}}=0$

$\Rightarrow 1 -r ||\mathbf{w}||=0$

$\Rightarrow r = \frac{1}{||\mathbf{w}||}$

즉, 다음과 같이 묘사할 수 있다.

유사하게, hyperplane이 적어도 1만큼의 margin을 갖는 상황으로 해석해서

$y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq 1$ 로 적을 수 있다.

즉, 다음과 같은 제약조건을 만족시키는

$y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq 1$

$1\over||\mathbf{w}||$의 최대값을 찾는 문제가 된다.

일반적으로 다음과 같이 동등한 문제로 바꾼다.

1/2 constant 는 gradient 계산의 편의를 위한 것이다.

식 (12.18)을 hard margin SVM이라고 하고 "hard"의 의미는 1보다 같거나 크다는 condition을 침범할 수 없기 때문이다.

만약 data의 분포가 linearly separable 하지 않다면 , hard condition을 완화시켜서 soft condition을 갖는 문제로 바꾼다.

Soft Margin SVM : Geometric View

soft condition으로 완화된 SVM을 soft margin SVM 이라고 한다.

기하학적인 관점에서 먼저 살펴보자.

각각의 $(\mathbf{x}_n,y_n)$ 에 대응되는 $\xi_n$을 hard margin SVM condition
$y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq 1$ 에서 빼주면 각각의 feature vector는 1 보다 $\xi_n$ 만큼 작은 거리만큼 hyperplane으로 부터 떨어져도 되게 된다.

$y_n(\lang \vec{w}, \vec{x}_n\rang + b) \geq 1 - \xi_n$

양수인 $\xi_n$이 1 보다 클 수 있으므로 다음 그림과 같이 잘못된 partition에 속한 feature vector인 경우도 허용할 수 있게 된다.

$\xi_n$들도 최소화되어야 좋은 최적화이므로 Objective function은 다음과 같다.
$\because C > 0$

linearly separable 한 상황이라면, $\xi_n$ = 0 인 경우가 이상적으로 optimize된 상황일 테니 해당 경우는 hard margin SVM의 경우와 같아진다.

이 경우 해당 objective function의 $||\mathbf{w}||^2$는 L2 regularization으로 볼 수 있다.
다만 b의 경우는 regularized 되지 않았기 때문에 이경우 theoretical analysis는 복잡하다.

Soft Margin SVM : Loss Function View

위에서 언급한대로 $||\mathbf{w}||^2$를 regularzation으로 본다면, 대응 되는 Loss function은 무엇일까?

binary classification문제에서 Loss function은 label과 prediction이 틀린 수와 관련되어 있어야 할 것이다.

따라서 prediction에 해당하는 $f(\mathbf{x}_n)$과 label에 해당하는 $y_n$이 일치하면 0, 다르면 1을 출력하는 zero-one loss function을 생각할 수있다.
$\Sigma_i\delta(f(\mathbf{x}_i) \neq y_i)$

하지만 zero-one loss function을 optimize하는 문제는 이산공간에서 최적의 해를 찾는 (e.g., Traveling Salesman Problem (TSP)) Combinatorial optimization problem 이기 때문에 일반적으로 continuous optimization problem에 비해 어렵다. (많은 Combinatorial Optimization Problem이 NP-hard problem 이다.)

따라서 hinge loss를 사용한다.

hinge loss는 다음과 같다.
$\ell(t) = max (\{0, 1-t\})$ where $t = yf(\mathbf{x}) = y(\lang \mathbf{w}, \mathbf{x} \rang +b)$

만약 prediction과 y가 일치하고, 기하학적으로 hyperplane으로 부터 거리가 1 이상 떨어져 있다면, $y(\lang \mathbf{w}, \mathbf{x} \rang +b) \geq 1$ 이므로 t=0 이고 $\ell = 0$ 이다.

prediction과 y가 일치하지만, 기하학적으로 떨어진 거리가 1 미만이라면 0 < t < 1 이고 작은 값 $\ell > 0$ 을 갖는다.

반면에 prediction과 y가 다르면 t < 0 이고 큰 값 $\ell > 0$을 갖는다.

이상적으로 , hinge loss = 0 이 되도록 optimize한다는 것은 margin 내의 어떠한 feature vector도 위치시키지 않겠다는 것이므로
이전에 언급한

hard margin SVM 문제를 푸는 것과 동등하다.

하지만 다음과 같이 제약조건이 없는 optimization problem이 된다.

그리고 이것은 Geometric View에서 논의했던 $\xi$를 도입한 optimization problem을 상기해봤을 때 단순히 수식적으로

error term를 optimize하는 것에 해당하는 $\min\limits_{t}\max\{0, 1-t\}$ 푼다는 것이
$\min\limits_{\xi , t}\xi$ subject to $\xi \geq 0, \xi \geq 1 - t$ 를 푸는 것과 동등하다는 것을 알 수 있다.

Dual Support Vector Machine

위에서 살펴 본 SVM 들은 모두 primal SVM에 속한다. 이제는 동등하지만 dual view로 바라본 optimization problem에 대해 이야기 해보자.

간단히 말해서, optimization theory에서 최소값을 찾는 primal problem과 동등한 dual problem이란 최대값을 찾는 문제이다.
라그랑주 승수법을 통해 dual problem으로 변환된다.
https://en.wikipedia.org/wiki/Duality_(optimization).

0이 아닌 $\alpha_n$과 대응되는 $x_n$는 hyperplane을 만드는데 도움을 주기 때문에 "support vector"라고 한다.

$0\leq \alpha_i \leq C$ 같은 부등식 형태의 제약조건은 SVM에서 "box constraint" 라고 한다. 해당 조건은 KKT condition을 통해 유도될 수도 있다.

Optimal $\vec{\alpha} = [\alpha_1, \cdots, \alpha_N]\in \mathbb{R}^N$의 값은 Numerical Solvers로 푸는 것이 효율적이다.
Numerical Solver에 대해서는 다음 책의 Chap 5. Bound constrainted minimization를 참고할 것.
Dostal, Zden ´ ˘ek. 2009. Optimal Quadratic Programming Algorithms: With Applications to Variational Inequalities.

Dual SVM: Convex Hull View

convex hull 이란 아래 그림과 같이 partition의 점들을 포함하는 최소 크기 둘레의 다각형이다. 폐곡선 고무줄을 줄이는 것을 통해 만들어짐을 쉽게 상상할 수 있다.

convex set 이란 같은 label의 모든 feature vector들을 포함하는 smallest possible set이다.

라그랑주 승수법말고 Dual SVM를 유도하는 다른 접근법에 대해서 이야기해보자.

Convex Hull View에 대한 참고자료.
Reduced Convex Hulls에 대한 참고자료.

Dual SVM with kernels

위에서 살펴본 $\min\limits_{\alpha} \frac{1}{2} \Sigma \Sigma y_i y_j \alpha_i \alpha_j \lang \vec{x}_i, \vec{x}_j \rang$ subject to $\Sigma y_i \alpha_i = 0$ 문제는 $\alpha$에 대한 optimization이므로 내적 $\lang \vec{x}_i, \vec{x}_j \rang$을 다르게 바라보자.

일반적으로, $\lang \vec{x}_i, \vec{x}_j \rang = \vec{x}_i^\mathsf{T} \cdot \vec{x}_j = \vec{x}_i^\mathsf{T} \mathbf{I} \vec{x}_j$ 이다.

하지만 두 $\vec{x}$ 사이의 identity matrix $\mathbf{I}$ 대신 "positive-definite"한 matrix가 들어가더라도 내적의 정의를 만족하므로 이때의 임의의 positive-definite matrix를 kernel matrix $\mathbf{K}$ 라고 하고 $\lang \vec{x}_i, \vec{x}_j \rang = \vec{x}_i^\mathsf{T} \mathbf{K} \vec{x}_j$ 로 내적을 정의하자는 것이 kernel의 아이디어 이다.

다만 SVM에서 kernel 방법을 묘사할 때, 일반적인 표현은 $\mathbf{I}$를 $\mathbf{K}$로 바꾸지않고 $\vec{x}$의 표현을 바꿔서 $k(\vec{x}_i,\vec{x}_j)=\vec{x}_i^\mathsf{T} \mathbf{K} \vec{x}_j = \lang\phi(\vec{x}_i),\phi( \vec{x}_j)\rang_\mathcal{H}$ 라고 적고 이때의 $\phi(\cdot)$를 non-linear feature map , $k(\cdot,\cdot)$ 를 kernel 이라고 한다. $\mathcal{H}$는 hilbert space를 의미한다.

feature map $\phi : \mathbb{R}^D \rightarrow \mathcal{H}$ 는 입력에 해당하는 feature vector를 더 높은 차원으로 mapping 할 수 있는데 이는 일반적으로 hilbert space로 mapping 한다고 할 수 있다. hilbert space에서 알 수 있듯이 이론적으로 infinite dimension으로의 mapping을 함의한다.

내적의 정의.
연산 $\lang \cdot , \cdot \rang$ 이 다음 세 성질을 만족하면 내적이라 한다.
1. symmetry : $\lang \vec{u} , \vec{v} \rang = \lang \vec{v} , \vec{u} \rang$
2. Liniearity (in the first argument) :
2-1 : $\lang \alpha\vec{u} , \vec{v} \rang$ = $\alpha \lang \vec{u} , \vec{v} \rang$
2-2 : $\lang \vec{u} + \vec{v} , \vec{}w\rang$ = $\lang \vec{u} , \vec{w} \rang$ + $\lang \vec{v} , \vec{w} \rang$
3. Positive - Definiteness : $\lang \vec{u} , \vec{u} \rang \geq 0$ , $\lang \vec{u} , \vec{u} \rang = 0 \Leftrightarrow \vec{u} = 0$

참고로 Hermitian matrix & positive eigenvalue $\Leftrightarrow$ Positive-definite matrix
https://en.wikipedia.org/wiki/Definite_matrix

Polynomial kernel

예를 들어, feature vector들의 차원이 2인 경우의 polynomial kernel과 그것에 대응되는 feature map은 다음과 같다.

Gaussian kernel

Radial Basis Fuction (RBF) kernel 이라고도 부른다.

gaussian kernel의 경우는 feature map이 feature vector를 infinite dimension으로 mapping한다는 사실을 확인할 수 있다.

infinite dimension을 갖는 feature map을 계산하는 것은 불가능하지만 단순한 gaussian kernel $K_G(\vec{x},\vec{y}) = exp[-\gamma || \vec{x}-\vec{y}||^2]$ 를 계산함으로써 infinite dimension을 고려할 수 있기 때문에 kernel의 강력함을 느낄 수 있다.

Gaussian kernel map의 증명과정 참고자료.
The intuition behind kernel methods
위 과정과 상이한 부분이 있어서 주의바람.

효율적인 kernel의 parameter와 kernel의 선택에는 nested cross-validation을 통해 이루어진다.

feature map $\phi$를 통해서 feature vector $\vec{x}$를 hyperplane으로 linearly separable한 높은 차원으로 mapping 한다고 생각 할 수도 있고 반대로 아래 그림과 같이 $\vec{x}$는 동일한 공간에 위치하고있고 hyperplane을 non-linear하게 변환한다고 여길 수 도 있다.