Support Vector Machine (SVM)

참고자료
1. 김성범 교수님 강의
2. 위키백과
3.

서포트 벡터 머신은 이진 분류를 위한 분류 모델이다.

SVM

SVM은 이진 분류를 수행하기 위해 두 클래스의 경계면을 찾는다.

만약 데이터가 단순히 2차원 상에 존재한다면 경계면은 직선, 3차원이라면 평면이 될 것이다. 즉, n차원의 데이터일 경우 n-1차원의 도형을 찾는 것이다. 이러한 n-1차원의 도형을 hyperplane(초평면)이라고 부른다.

두 클래스를 분류하는 hyperplane은 무수히 많이 존재하게 된다.

그렇다면 SVM은 어떤 hyperplane을 찾으려 할까?

SVM이 찾고자 하는 hyperplane은 margin을 최대화 하는 hyperplane이다.

hyperplane의 표현

우선 hyperplane은 다음과 같이 표현한다.

위와 같은 식은 도형의 방정식이 된다.

위 식을 풀어서 공간 상에 x가 위치할 수 있는 곳을 빨간색으로 나타내보면 다음과 같다.

즉, $\bold w^T \bold x = b$ 는 법선벡터를 w로 하는 평면의 방정식이 된다.

Margin

Margin이란 Support Vector를 지나는 hyperplane 사이의 거리이다.

Support Vector란 아래 그림에서 점선에 위치한 데이터들의 embedding을 의미한다.

각각의 클래스의 경계가 되는, 즉, support vector를 지나는 hyperplane들은 $\bold w^T \bold x - b=1$, $\bold w^T \bold x - b= -1$ 로 표현한다.

위 그림에서 margin은 $\frac{2}{||\bold w||}$가 된다.

방향벡터가 w인 직선의 방정식과 해당 직선과 평면의 교점 x1, x2를 이용하면 구할 수 있다.

SVM의 목적

다시 SVM의 목적으로 돌아와서 SVM은 margin($\frac{2}{||\bold w||}$)을 최대화하는 hyperplane($\bold w^T \bold x = b$) 을 찾는 것이다.

즉, SVM이 찾고자 하는 것은 hyperplane의 파라미터 $\bold w$와 $b$인 것이다.

다만 기본적으로 SVM이 기존 데이터에 대한 분류를 수행할 수 있어야 하므로 다음 식을 만족해야 한다.

SVM은 지도학습이므로 데이터들은 모두 클래스(1, -1)를 가진다.

각각의 데이터들 x가 클래스 y를 가진다.

이에 따라 SVM이 만족해야 하는 식은 다음과 같이 표현할 수 있다.

정리하면 SVM을 다음 문제를 푸는 것이다.

데이터 개수 n에 대해,

이 문제를 풀기 위해서는 KKL에 대한 이해가 필요하다.
추후에 보충할 예정이다.