n 차원 공간을 가를 수 있는 해당 공간의 차원보다 하나 낮은 수학적 관계라고 풀어서 쓸 수 있다.
즉, x1이나 x2 중 하나만 주어지면 나머지 위치가 주어진다.
쉽게 y=x+1의 직선을 생각하면 된다. 2차원 평면에서 x의 값이 주어지면 y값이 정해진다. 이 직선은 2차원 평면에 위치하지만 사실상 1차원의 속성을 지니게 된다.
x=(x1,x2)의 벡터가 있다고 할 때, 하이퍼플레인은 벡터 w와 b에 의해 정의된다. 즉,
w⋅x+b=0
Classifier
하이퍼플레인을 기준으로 클래시파이어를 다음과 같이 정의한다. 특정한 관찰 벡터 x가 있다고 하자. 이때 분류 h의 정의는 아래와 같다.
h(x)=⎩⎪⎪⎨⎪⎪⎧+1−1ifw⋅x+b≥0ifw⋅x+b<0
Explained Visually
그림으로 보다 직관적으로 이해해보자.
어떤 원점을 기준으로 training example까지의 벡터를 xi라고 하자. 이때 둘을 가르는 하이퍼플레인이 있을 때 이와 직교하는 벡터 (orthogonal vector) w를 생각해보자. 왜 orthogonal해야 하는가? 잠시 후 그 이유를 알 수 있다. 하이퍼플레인은 기본적으로는 두 벡터 사이의 닷 프로덕트다1. 닷 프로덕트를 그림으로 나타낼 수 있는 방법은 이를 projection으로 생각해보는 것이다.
즉, xi를 w로 프로젝션을 한다면(projection of xi on w), 이는
Projwxi=∥w∥w⋅xi
닷 프로덕트의 부분이 시각적으로는 projection 결과 곱하기 ∥w∥로 나타난다. 즉, xi에서 w를 향해 내린 선분이 프로젝션이고 이를 ∥w∥로 스케일링 한 w 위에서의 길이가 닷 프로덕트를 시각적으로 나타낸 것이다. 이 프로젝션의 길이에 따라서 해당 트레이닝 샘플이 어떤 것으로 분류될지에 관해서 파악할 수 있다. ∥w∥가 고정되어 있다고 하면, 프로젝션의 크기가 일정 숫자보다 크면 분류의 오른쪽에 작으면 분류의 왼쪽에 위치하는 것이다. 이를 아래와 같이 표시해보자.
w⋅xr+b≥1
w⋅xl+b≤1
프로젝션의 길이가 일정한 기준보다 길면 오른쪽에 짧으면 왼쪽에 위치한 것으로 분류할 수 있다. 이 조건을 yi와 함께 나타내보자. 즉,
yi(w⋅xi+b)−1≥0
앞서 분류기에서 해당 값이 0보다 크면 yi(w⋅xi+b)−1≥0가 성립한다. 반면, 해당 값이 0보다 작으면 음수를 곱하는 것이 되어 부등호가 바뀌게 되고, 이 경우 역시 위의 식이 성립한다.
이제 cosθ를 벡터 xsvr−xsvl와 w가 이루는 각이라고 생각하자. 이때 w는 하이퍼플레인과 orthogonal하며 적절한 training sample 즉, 적절한 하나의 서포트 벡터를 지난다. 이때 cosθ는 다음과 같이 쉽게 정의된다.2
cosθ=∥xsvr−xsvl∥∥w∥(xsvr−xsvl)⋅w
한편, 하이퍼플레인과 평행하면서 서포트 벡터를 지나가는 하이퍼플레인의 거리 Δx는 다음과 같다.
이 녀석들을 다시 라그랑주 방정식에 대입하면, α로만 된 일종의 maximal function 혹은 라그랑주 방정식의 하한(infimum)을 만들 수 있다. Wolfe duality에 따르면, 최소화 최대화를 한 번에 푸는 것과 한 가지 문제를 먼저 푼 후 해당 결과를 목적 함수에 넣고 두 번째 문제를 순차적으로 푸는 것이 동일하다. 따라서 위의 일계 조건을 목적 함수에 넣은 목적함수는 구해보자.
W(α)=i=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxi⋅yj
이제 문제는 α에 관해서 극대화 문제를 푸는 것으로 바뀐다. 즉,
αmaxW(α)s.t.αi≥0,i=1∑mαi(yi(w⋅x∗+b)−1)=0
제약 부분이 부등식이므로 KT(Kuhn-Tucker) 조건에 따라서 풀면 된다.
αi[yi(w⋅x∗+b)−1]=0
KT 조건이란 부등식 제약을 푸는 테크닉이다. 즉, αi>0의 제약이 유효하다면 제약을 만족시키기 위해서는 yi(w⋅x∗+b)−1=0이 만족해야 한다. 이렇게 제약이 걸리는 경우에 위치한 x∗가 바로 ‘서포트 벡터’다. 반면, αi=0는 제약이 등호로 걸릴 필요가 없는 트레이닝 셋의 관찰들이다. 이들은 분류 하이퍼플레인까지의 길이가 서포트 벡터의 길이보다 크다.
Compute w and b
w 의 경우 1계 조건에서 쉽게 얻을 수 있다.
w−i=1∑mαiyixi=0
한편, b의 경우 서포트 벡터의 경우 위에서 본 것 같이 제약 식의 등호가 성립한다. 즉, 서포트 벡터를 x∗라고 할 때,
yi(w⋅x∗+b)−1=0
양변에 yi를 곱하면, yi2=1이므로,
b=yi−w⋅x∗
서포트 벡터가 S개 존재할 경우라면,
b=S1i=1∑S(yi−w⋅xi∗)
Limitation
앞서 본 것을 이른바 hard margin SVM이다. 즉, 서포트 벡터 사이의 마진을 획일적으로 적용하는 분류 알고리듬이다. 하드 마진 SVM은 다음의 두가지 경우에 취약하다.
데이터에 노이즈가 있을 경우
하드 마진의 큰 문제는 아웃라이어에 취약할 수 밖에 없다는 것이다. 풀어서 말하면 제약이 선형이고 그 제약이 강력하다는 데 있다. 트레이닝 데이터에 이런 저런 노이즈가 있을 경우 하드 마진은 아예 계산이 불가능할 수 있다. 이때 사용하는 기법이 soft margin SVM이다.
데이터 자체가 선형으로 분리되지 않을 경우
애초부터 데이터 자체가 선형을 통한 분류를 허용하지 않을 경우에는 비선형 분류를 사용할 수 있다. 이때 동원하는 테크닉이 커널 트릭 (kernel trick)이다.
정규화 파라미터인 C를 어떻게 이해할까? 식 그대로 보면, ζ를 얼마나 중요하게 최적화 문제에 반영할 것인지가 중요하다. 다시 말하면 이는 에러를 어떻게 볼 것인가와 연결되어 있다. 만일 C가 양의 무한대 값이라면 이는 하드 마진과 동일하다. 만일 C=0 이라면 αi=0가 된다. 이는 사실상 선형 제약이 사라지게 되는 결과가 된다. 따라서 하이퍼플레인이 어떤 것도 분류하기 못하게 될 것이다. 즉, C는 하드 마진과 소프트 마진 사이를 적절하게 조절하는 역할을 수행한다.
Kernel Trick
마지막에 얻은 극대화 문제를 살펴보면, training set이 관련된 부분이 딱 하나 밖에 없다. xi⋅xj 뿐이다. 따라서 이 부분을 유연하게 조정해줌으로써 비선형적 형태의 분류를 만들 수 있는 것이다. 앞서 봤던 하드 마진 SVM은 선형 커널을 사용한다. 즉,
K(xi,xj)=xi⋅xj
이런 커널만 있을 형태는 없다. 여러가지 함수를 커널로 취할 수 있을 것이다. 가장 많이 사용되는 커널은 RBF(Radial Basis Function) 혹은 가우시안이라고 한다.
벡터의 방향에 대해서 약간 갸우뚱하는 분들이 있을지 모르겠다. cosθ를 제대로 정의하기 위해서는 $-({\bf x}{\rm svr} - {\bf x}{\rm svl}),- \mathbf{w}$라고 쓰는 것이 맞을 것이다. 하지만, 둘의 닷 프로덕트를 구하면 서로 상쇄되어 아래 적은 것과 동일하다. ↩