Support Vector Machine(SVM)

decision boundary로부터 가장 가까이 있는 점의 거리(margin)이 최소가 되도록 하여 hyperplane을 만드는 기법.

모든 점에 대하여 비교하는 것이 아니라, decision boundary에 가까운 일부분만 사용하므로 기존의 방식에 비하여 간단하다.

Motivation: Vapnik's principle,

복잡한 문제보다는, 간단한 문제에서부터 시작해 풀자는 것.
decision boundary를 결정할 때 기존의 방식으로는, $P (c_{i} ∣ x) = P (c_{j} ∣ x)$ 인 posterior를 예측하기 위해 $ar g max_{k} P (c_{k} ∣ x)$ : Bayesian Decision방식을 사용했다. 하지만 이는 직접 decision boundary를 찾자는 바로 어려운 문제를 푸는 것과 같다.
이보다는, 쉽고 간단한 linear한 decision bounary를 이용해 문제를 해결하자는 것이 아이디어이다.

Support Vector로부터 가장 가까이 있는 점의 margin이 최소가 되는 그러한 decision boundary가 optimal hyperplane이라고 본다.

Advancement

반드시 Linear decision boundary만을 이용하는 것이 아니라, 고차원으로 mapping 시켜주는 함수를 이용해 고차원 상에서는 linear하지만, 저차원 상에서는 nonlinear한 함수를 만들 수 있도록 한다.

이를 kernel trick이라 하며, 고차원으로 만들어주는 함수는 basis function이라 한다.

데이터의 Attribute를 조합하여서, 새로운 Attribute를 만들어 새로운 축을 만들어준다면(차원 향상), 새로운 양상이 나타나기도 한다.

이렇게 새로운 양상을 이용해 저차원에서는 해결 불가능한 nonlinear 문제를, 고차원에서의 linear문제로 바꾸어 해결하는 일종의 trick이다.

기존의 feature1에 대하여, 새로운 특성 feature3를 만들어 새롭게 차원을 증강시킨다. 이 때, 이 Boundary를 결정지을 수 있는 Hyperplane이 보이기도 한다.

$z = [z_{1}, z_{2}, \dots, z_{k}]^{⊤} = ϕ (x)$ 이 때, 기존의 $x$ 의 차원보다 커지게 되며, 위의 xor문제에서는 2차원에서 3차원으로 변한다.
$ϕ (x) = [x_{1}, x_{2}, (x_{1} - x_{2})^{2}]^{⊤}$ : 파란 점이 새로운 차원 상에서 위에 있게 되며, linear한 decision boundary를 그을 수 있다. $x$ 대신 $ϕ$ 를 넣어 계산한다.

하지만, 실제로 고차원 상에서의 basis function의 계산은 오래 걸리므로 저차원에서 이와 동일한 결과를 가져올 수 있는 Kernel 함수를 이용한다.

정확히는, 이를 kernel trick이라 한다. 이를 위하여, Support Vector를 계산할 때 Dual Problem으로 바꾸어 계산한다.

L_{d} \equiv= - \frac{1}{2} t \sum s \sum α^{t} α^{s} r^{t} r^{s} ϕ^{⊤} (x^{t}) ϕ (x^{s}) + t \sum α^{t}

K (x^{t}, x^{s}) = ϕ^{⊤} (x^{t}) ϕ (x^{s})

과 같은 kernel function $K$ 를 찾아 내적을 통한 빠른 계산을 할 수 있다.

gram matrix: 빠른 계산을 위하여, Kernel 함수의 경우에 대해 미리 계산하여 놓고 사용하기 도 한다.

Margin에서, 그 Margin 경계에 다른 Dataset이 들어오도록 예외를 허용하여 여유로운 마진을 가지도록 한다.

이는 곧 Generalization으로 이어져, Overfitting이 발생하지 않도록 한다.