7-2 Kernels

SVM을 Complex nonlinear classifier로 사용하기 위한 Kernel에 대해 알아본다.

다음과 같은 data를 잘 분류하는 Non-linear decision boundary가 있을 때, 이와 같은 boundary는 오른쪽과 같은 굉장히 복잡한 다항식을 사용한 모델일 것이며 이때 가설 h(x) 값이 0 이상이면 1, 그렇지 않으면 0으로 예측할 것이다. 그리고 x1, x2, x1*x2의 feature를 f1, f2, f3와 같이 다른 표기법으로 나타내어 h(x)를 표현할 수 있다. 컴퓨터 비전 문제를 풀 때 굉장히 복잡한 고차 다항식 모델을 사용하게 될 것이고 이러한 모델은 계산량이 매우 expensive하다는 단점이 있다.

그럼 f1, f2, f3와 같은 새로운 feature를 잘 정의할 수 있는 방법은 무엇일까?

x1, x2가 있을 때(x0는 무시함), 매뉴얼하게 선택한 3개의 지점을 l(1), l(2), l(3)라고 하면 feature f1, f2, f3는 train data x에 대해서 l(1), l(2), l(3)와의 similarity로 정의할 수 있다. 여기서 Similarity를 kernel 이라고 부르며 구체적으로 exp(…)으로 정의한 커널을 Gaussian kernel이라고 부른다. smiliarity(x, l(i)) 대신 간단하게  k(x, l(i))로 나타낼 수 있다.

앞서 정의한 것처럼 f1이 다음과 같을 때 sample x가 l(1)과 매우 가깝다면 f1 값은 1에 가까워질 것이다. 이와 반대로 x가 l(1)과 멀리 떨어져 있다면 f1 값은 0이 될 것이다. (1이면 유사도가 높은 것, 0이면 유사도가 낮은 것으로 간주할 수 있음)

이와 같은 방식으로 l(2), l(3)에 따라 f2, f3,를 정의할 수 있다.

2개의 feature x1, x2가 있고 l(1)과 𝝈^2=1 다음과 같다고 해보자

그럼 f1에 대한 그림은 다음과 같이 그려질 것이다. x1, x2 = 3, 5일 때 f1 값은 1이 될 것이고 해당 지점에서 멀어지면 f1 값은 0에 가까워질 것이다.

앞선 그림에서 𝝈 값을 1로 두었지만 𝝈 역시 가우시안 커널의 파라미터이기 때문에 𝝈 값에 따라 결과가 조금 달라질 수 있다. 만약 𝝈^2=0.5라면 중간 그림과 같은 결과를 얻을 수 있다. 𝝈^2 = 1일 때와 비슷하지만 width가 조금 narrow해졌다. 따라서 𝝈 값이 작아지면 landmark에서 조금만 벗어나도 f1 값이 급격하게 0에 가까워진다. 반면 𝝈 값이 커지면 이러한 변화가 둔해지는 효과가 있다.

주어진 feature와 landmark에 따라 h(x)를 정의하고 해당 파라미터 𝜽값이 다음과 같을 때, training example이 분홍색 지점의 위치에 있다면 어떻게 될까? 주어진 sample x는 l(1)과 매우 가깝기 때문에 f1 값은 1에 가까울 것이고 l(2), l(3)와의 거리는 멀기 때문에 f2, f3는 0에 가까운 값이 될 것이다. 따라서 가설 h(x) 값은 0.5가 되어 0이상이기 때문에 y=1로 predict할 것이다. 이번에는 하늘색 지점의 training sample이 있을 때, 해당 sample은 l(1), l(2), l(3)와 모두 멀기 때문에 f1, f2, f3 값은 모두 0에 가까울 것이다. 따라서 가설 h(x) 값은 -0.5가 되어 y=0으로 predict할 것이다.

 

이와 같은 방식으로 주어지는 training sample에 대해 f1, f2, f3 값을 구할 수 있고 해당 가설 h(x) 값에 따라 y=0 or y=1로 예측할 수 있다. 결과적으론 대략 빨간색과 같은 decision boundary가 그려지게 된다. l(1) 혹은 l(2) 둘 중에 하나와 가까우면 y=1, l(1), l(2) 두개의 landmark 지점으로부터 멀리 떨어져 있으면 y=0이 된다.

커널 및 SVM에 적용하기 위한 new feature(landmark)를 정의하는 방법과 bais, variance trade-off에 대해 알아본다.

Feature x1, x2에 대해 landmark가 다음과 같을 때 커널 f = similarity( x, l(i) )의 값을 다음과 같이 정의하였고 이와 같은 커널을 가우시안 커널이라고 하였다. 이를 이용하여 새롭게 정의된 가설 h(x)가 다음과 같을 때 h(x) 값이 0이상이면 y=1, 0미만이면 y=0으로 predict하였다.

 

그러면 landmark 값은 어떻게 정의해야 하는가?

가장 간단한 방법은 training data가 위치한 지점을 landmark로 사용하는 것이다. 따라서 m개의 sample이 있으면 m개의 landmark를 구할 수 있다.

총 m개의 sample이 있을 때 m개의 landmark를 구할 수 있었다. 이를 사용하여 validation data 혹은 test data에 대한 f1, f2, f3 … 값을 구할 수 있으며 f0=1로 설정하면 m+1차원의 벡터 f를 정의할 수 있다. 나아가 벡터 f를 사용하여 training data x를 정의할 수 있다. 하나의 training sample에 대하여 m개의 커널(f 값)을 구할 수 있으므로 f0를 1로 설정하면 x(i)를 m+1차원의 벡터 f(i)로 정의할 수 있다.

이제 예측해야 하는 주어진 어떤 cross validation data 혹은 test data가 있을 때, 이를 가설 h(x) 값 𝜽'와 m+1차원의 벡터 f의 곱으로 정의할 수 있다. 그 결과값에 따라 y=1 or y=0으로 예측하게 된다.

 

따라서 SVM에서 우리가 학습을 통해 최적화해나가는 파라미터 𝜽 값에 대한 학습 알고리즘은 다음과 같이 정의된다. 

원래 𝜽'x(i)였던 것을 위에서 x(i)를 벡터 f(i)로 정의한 것을 사용하여 𝜽'f(i)로 바꾼 것이다.

다음으로 SVM을 사용할 때 파라미터에 따른 Bias, Variance effect는 다음과 같다.

C는 1/람다 이므로 C가 매우 큰 값이라면 로지스틱 회귀에서의 람다 값이 매우 작은 값이라고 생각하면 된다. 따라서 C가 매우 큰 값이라면 Lower bias, High variance(over fitting)가 된다.

반대로 C가 매우 작은 값이라면 로지스틱 회귀에서의 람다 값이 매우 큰 값이므로 High bias, Low variance(under fitting)가 된다.

 

또 하나의 파라미터인 𝝈에 따라 Bias, Variance effect가 달라질 수 있다.

𝝈값이 매우 크다면 앞에서 봤던 것처럼 feature 값에 따라 커널(f 값) 값이 변화하는 정도가 둔할 것이다. 따라서 이 경우 High bias, Low variance가 된다.

반대로  𝝈값이 매우 작은 값이라면 feature 값에 따라 커널 값이 변화하는 정도가 급격하게 변하게 되므로 이 경우 Low bias, High variance가 된다.