[Machine Learning] SVM : Kernel

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

이번 시간에는 non-linear classifier에서 SVM을 적용하는 방법에 대해서 알아보자.

 

- Kernel

[Non-linear Decision Boundary]

위와 같은 data에서는 non-linear decision boundary가 필요하고, 우리는 다음과 같이 예측할 수 있을 것이다.

\[\begin{align*}\text{Predict } y = 1 \text{ if } \\ &\theta_0 + \theta_1x_1 + \theta_2x_2 + \theta_3x_1x_2 \\ &+ \theta_4x_1^2 + \theta_5x_2^2 + \cdots \leq 0 \end{align*}\]

 

즉, 우리는 아래와 같은 Hypothesis Function을 가지고 예측할 수 있다.

\[h_\theta(x) = \left\{\begin{matrix} 1 & \text{if } \theta_0 + \theta_1x_1 + \cdots \leq 0 \\ 0 & \text{otherwise} \end{matrix}\right.\]

 

여기서 우리는 다른 x로 표현되는 feature 대신, \(f_1, f_2, f_3, \cdots\)과 같은 다른 feature를 사용해서 decision boundary를 계산하는데 사용할 것이다. 새롭게 나타내면 다음과 같다.

\(\rightarrow \theta_0 + \theta_1f_1 + \theta_2f_2 + \theta_3f_3 + \cdots\)

이렇게 사용한 \(f\)들은 기존의 feature(\(x_1, x_2, ...\))를 어떠한 과정을 통해서 변환한 새로운 feature이다. 이제 우리는 새로운 feature들을 어떻게 구하고, 이것으로 non-linear decision boundary를 어떻게 나타내는지 알아보자.

 

 

실제로는 많은 feature들이 있겠지만, 우리는 우선 \(f_1, f_2, f_3\)라는 feature만 정의한다고 생각해보자. 그리고 사용하는 기존 feature가 \(x_1, x_2\)가 있다고 가정하자(\(x_0\)은 제외).

 

우리는 그래프에 임의의 Landmark \(l^{(1)}, l^{(2)}, l^{(3)}\)를 수동으로 선택한다. 그리고, 새로운 feature \(f\)들은 각 landmark에서 얼마나 가까운지를 나타내는 값으로 정의한다. 

feature \(f\)는 다음과 같이 정의된다.

\[\begin{matrix} f_1 = similarity(x, l^{(1)}) & = exp(-\frac{\left\| x - l^{(1)} \right\|^2}{2\sigma^2}) \\ f_2 = similarity(x, l^{(2)}) & = exp(-\frac{\left\| x - l^{(2)} \right\|^2}{2\sigma^2}) \\ f_3 = similarity(x, l^{(3)}) & = exp(-\frac{\left\| x - l^{(3)} \right\|^2}{2\sigma^2}) \end{matrix}\]

 

여기서 similarity 함수를 Kernel이라고 하며, 여기서 사용된 Kernel은 가우시안 커널(Gaussian Kernel)이다.

이 함수에서는 정규분포 함수와 같은 형태로 나타나며, landmark에 가까울수록 1에 가깝고, 멀수록 작은 값을 나타낸다.

조금 더 자세히 살펴보자.

 

만약 \(x\)가 Landmark \(l^{(1)}\)에 매우 근접하다면, \(f_1\)을 계산하게 되면 1에 가까운 값을 가지게 될 것이다. 반면에 \(x\)가 \(l^{(1)}\)에서 아주 멀어지게 된다면, \(f_1\)은 0에 가까운 값을 가지게 될 것이다.

 

여기서 \(\sigma^2\)은 가우시안 커널의 parameter인데, 이 값에 따라서 어떻게 변화하는지 살펴보자.

\(l^{(1)} = \begin{bmatrix} 3 \\ 5 \end{bmatrix}\) 일 때, 가우시안 커널에 의해서 \(f_1\)의 값은 아래와 같은 그래프로 나타나게 된다.

\(\sigma^2\)이 작을수록 더 좁은 등고선(contour)을 갖게되고, \(x\)가 \(l^{(1)}\)에서 멀어질수록 \(f_1\)의 값은 더 빠르게 0이 될 것이다. 반면에 \(\sigma^2\)이 크다면 넓은 등고선을 갖게 된다.(정규분포에서 분산에 해당)

 

 

위 그림으로 다시 한 번 살펴보자. 여기서 \(\theta_0 = -0.5, \theta_1 = 1, \theta_2 = 1, \theta_3 = 0\)으로 가정한다.

우리가 만약 \(l^{(1)}\)에 가까운 보라색 \(x\)를 선택했으면, \(f_1 \approx 1, f_2 \approx 0, f_3 \approx 0\)으로 feature의 값을 얻을 수 있다. 그리고, Decision Boundary에 대입하면 0보다 큰 0.5의 값을 얻을 수 있기 때문에 \(x\)의 예측값 \(y\)를 1로 예측할 수 있다. 

반면에 \(l^{(1)}, l^{(2)}, l^{(3)}\)에서 멀리있는 하늘색 \(x\)를 선택한다면, \(y = 0\)으로 예측할 수 있을 것이다.

 

여기서 \(\theta_3\)은 0이기 때문에, 우리는 Decision Boundary를 위와 같은 빨간색 선으로 설정할 수 있고, \(l^{(1)}, l^{(2)}\)에 가까울 때 \(y = 1\)로 예측 가능하다.

 

 

그렇다면 우리는 어떻게 landmark를 설정할 수 있는지와 가우시안 커널이 아닌 다른 종류의 커널을 사용할 수 있는지에 대해서 알아보자.

 

 

[Choosing the landmarks]

우리가 사용할 수 있는 방법 중 한 가지는 landmark를 우리의 training example들과 동일하게 두는 것이다. 즉, training example들을 landmark로 선택하는 것이다. m개의 example \(x\)가 있었다면, 우리는 이 example과 동일하게 \(l^{(1)}, l^{(2)}, ..., l^{(m)}\)으로 선택하는 것이다.

그리고 이렇게 선택한 landmark \(l\)을 사용해서 모든 similarity \(f\)를 구한다. 그렇게 구한 \(f\) vector를 x 대신 사용할 새로운 feature로 사용한다. 이때, 원한다면 \(f_0\)를 bias unit으로 1로 두고 추가해서 사용할 수 있다.

 

\[x^{(i)} \rightarrow \begin{matrix} f_1^{(i)} = similarity(x^{(i)}, l^{(1)}) \\ f_2^{(i)} = similarity(x^{(i)}, l^{(2)}) \\ \vdots \\ f_m^{(i)} = similarity(x^{(i)}, l^{(m)}) \end{matrix}\]

위와 같이 \(x^{(i)}\)로 새로운 feature \(f^{(i)}\)를 구한다.

 

정리하자면,

\(x^{(i)} \in \mathbb{R}^{(n)}\)(or \(\mathbb{R}^{(n+1)}\))인 feature \(x\)에서 m개의 training example을 landmark로 두고 새로운 feature \(f^{(i)}\)( \(\in \mathbb{R}^{(m)}\) or \(\mathbb{R}^{(m + 1)}\)) vector를 구하는 것이다. \(f_0^{(i)}\)를 추가하면 m+1차원이고, 추가하지 않으면 m 차원이다. \(f\)(m+1 차원)는 다음과 같다.

\[\begin{align*} f^{(i)} = \begin{bmatrix} f_0^{(i)} \\ f_1^{(i)} \\ \vdots \\ f_m^{(i)} \end{bmatrix} & ,f_0^{(i)} = 1 \end{align*}\]

 

우리는 주어진 x에 대해서 새로운 feature \(f\)를 구했고, \(\theta^Tf \leq 0\)일 때 \(y = 1\)로 예측할 수 있다.

이제 우리는 새로운 feature로 Cost Function을 정의해서 parameter \(\theta\)를 구해야한다. feature의 개수가 m+1개로 변경되었기 때문에, \(\theta \in \mathbb{R}^{m + 1}\) 이다. 사용되는 Cost Function은 다음과 같다.

\(\theta^Tx^{(i)}\)에서 \(\theta^Tf^{(i)}\)로 변경되었고, regularized(정규화)항의 summation에서도 n까지가 아닌 m까지로 변경된다. \(\theta_0\)은 bias unit이므로 정규화항에 포함되지 않는다.

정리하면 다음과 같다.

\[\underset{\theta}{min}C\sum_{i = 1}^{m}y^{(i)}cost_1(\theta^Tf^{(i)}) + (1 - y^{(i)})cost_0(\theta^Tf^{(i)}) + \frac{1}{2}\sum_{j = 1}^{m}\theta_j^2\]

 

정규화항의 \(\sum\theta_j^2\)은 반복적으로 계산하기에는 시간이 오래걸리기 때문에 우리는 vector로 만들어서 \(\theta^T\theta\)를 구하면 더욱 빠르게 계산할 수 있다. \(\theta^T\theta\)는 \(\left\| \theta \right\| ^2\)과 같다. 그리고 이것은 \(\theta^TM\theta\)로 계산될 수 있는데, 이때 M은 kernel에 따라 결정(사용)되는 Matrix이다. Parameter에 따라서 rescale되었다고 할 수 있다.

\(\theta\)는 \(\theta = \begin{bmatrix} \theta_1 \\ \theta_2 \\ \vdots \\ \theta_m \end{bmatrix}\)이다.

 

다음으로는 SVM Parameter \(C\)와 \(\sigma^2\)에 대해서 살펴보자.

이전에 SVM을 설명하면서 보았겠지만, \(C\)는 \(\frac{1}{\lambda}\)와 유사하다. 그래서 \(C\)가 크다면 \(\lambda\)가 작은 것과 동일하고, bias를 감소시키고, 높은 variance를 가지게 한다. 반면에 \(C\)가 작다면 \(\lambda\)가 큰 것과 동일하고, bias를 증가시키고, 낮은 variance를 갖게 한다.

 

\(\sigma^2\)은 정규분포 그래프에서 그래프의 분산과 동일하다.

\(\sigma^2\)이 크다면 feature \(f^{(i)}\)의 그래프는 smooth하게 분포되어 있는 모양이 될 것이다. 즉, 높은 bias를 가지고 낮은 variance를 갖게 된다.

반면에 \(\sigma^2\)가 작다면 feature \(f^{(i)}\)의 그래프는 narrow하게 분포되어 있는 모양이 될 것이다. 즉, 낮은 bias를 가지고 높은 variance를 갖게 된다.

 

 

우리는 커널을 SVM이 아니더라도 Logistic Regression 등 다른 학습 알고리즘에도 적용할 수 있다. 하지만 SVM에 적용되는 커널(Computational Tricks)는 Logistic Regression과 같은 다른 알고리즘에 잘 일반화되지 않고, 속도 측면에서 매우 느리다. 또한, SVM과 커널을 사용하면서 발견된 고급 최적화 기술들을 사용할 수 없다. 

물론, Logistic Regression과 커널을 함께 사용할 수는 있지만, 정말 매우 느리다. 

 

중요한 것은 결국 Cost Function을 최소화하는 Parameter를 찾는 것이지만, 직접 이것을 구현하는 것은 권장하지 않는다. 이미 잘 구현된 Software가 있기 때문에 우리는 이것을 사용하면 된다.

 

 

- SVMs in Practice

SVM 알고리즘은 특정한 최적화 문제를 제기한다. 계속 말해왔듯이 parameter \(\theta\)를 구하는데 직접 SW를 구현하는 것은 권장하지 않는다. SVM 최적화 문제를 해결하는 SW는 매우 복잡하고, 연구자들이 수년동안 수학적인 최적화 연구를 진행해왔다. 따라서, SVM 최적화 문제를 해결하기 위한 좋은 SW 라이브러리와 패키지가 있기 때문에 직접 구현하지 말고 최적화된 SW 라이브러리 중 하나를 사용하는 것을 추천한다.(e.g. liblinear, libsvm, ...)

이 라이브러리를 사용하기 위해서 우리는 해야할 일이 두 가지 있다.

첫 번째는 parameter \(C\)를 선택하는 것이고,

두 번째는 어떤 Kernel 또는 similarity function을 사용할 지 선택하는 것이다. 커널을 선택할 때, 커널을 사용하지 않을 수 있다(No kernel). No kernel은 linear kernel을 의미한다. 

 

linear kernel을 선택하면 SVM은 기본 linear classifier로 동작한다. 즉, \(\theta^Tx \leq 0\)일 때, \(y = 1\)로 예측할 수 있다.

그렇다면 어떤 경우에 linear kernel을 선택하느냐 ?

만약 많은 feature(n is large)가 있고, training example의 수가 적을 때(m is small) linear kernel을 사용하는 것이 낫다. 이미 적은 수의 example에서 많은 수의 feature를 가지고 있기 때문에 우리는 linear decision boundary를 원할 것이다. 그리고 충분한 data가 없기 때문에 복잡한 non-linear 함수에 맞추려고 시도할 필요가 없다. 만약 높은 차원의 feature를 가지고 복잡한 함수로 decision boundary를 맞추려고 한다면, training example의 수가 적기 때문에 overfitting(과적합)의 위험이 발생할 수 있다.

 

두 번째로는 가우시간 커널(Gaussian Kernel)을 선택할 수 있다. 가우시안 커널을 선택한다면, 우리는 bias와 variance의 trade-off 관계를 고려해서 \(\sigma^2\)를 선택해야한다. \(\sigma^2\)가 크다면 높은 bias를 가지고 낮은 variance를 가지는 classifier의 경향을 가지게 되고, \(\sigma^2\)가 작다면 높은 variance를 가지고 낮은 bias를 가진 classifier의 경향을 가지게 될 것이다.

그래서 우리는 언제 가우시안 커널을 선택해야 될까?

feature n이 작고, training example m이 많아서 좀 더 복잡한 non-linear decision boundary가 필요할 때 가우시안 커널을 사용하는 것은 좋은 선택이 될 수 있다. 강의 마지막에 어떻게 커널을 선택할 수 있는가에 대해서 조금 더 설명하겠다.

 

[Kernel(similarity functions]

만약 가우시안 커널을 선택했다면, 우리는 octave나 matlab에서 다음과 같은 라이브러리 함수를 사용하면 된다.

\(f^{(i)}\)를 구하는 데 파라미터 x1에 \(x^{(i)}\)를 인자로 전달하고, x2에 landmark \(l^{(i)}\)를 인자로 전달하면 된다. 이 함수 내부 연산을 통해서 feature \(f\)가 결과로 반환된다.

중요한 것은 카우시안 커널을 사용하기 전에 feature의 scaling을 수행해주어야 한다. 만약 집값 예측 예제에서 feature \(x_1\)은 집의 크기를 의미해서 천 단위의 범위를 갖고 있고, feature \(x_2\)는 방의 갯수로 일 단위의 범위를 갖고 있다고 가정해보자. 그렇다면 \(x_1 - l_1\)의 값은 매우 클 것이고, \(x_2 - l_2\)의 값은 작기 때문에 방의 갯수는 거의 무시될 것이다. 그래서 학습 알고리즘이 제대로 동작하기 위해서 feature scaling을 먼저 해주어야 한다.

 

[Other choices of kernel]

우리가 SVM 알고리즘을 사용할 때, 가우시안 커널이나 linear 커널(no kernel)이 아닌 다른 커널을 사용할 수 있다. 다만, 커널들을 사용해서 SVM Package의 최적화가 적절하게 동작하고 발산하지 않기 위해서는 사용하는 커널이 Mercer's Theorem를 만족해야 한다(parameter \(\theta\)를 효율적으로 구하기 위해서 이 조건을 만족하는 커널만 사용되도록 결정됨). 그래서 Mercer's Theorem을 만족하는 모든 SVM SW패키지는 많은 최적화 클래스를 사용하고 parameter \(\theta\)를 빠르게 구할 수 있다.

 

대부분은 결국 Linear 또는 가우시안 커널을 사용하지만, 여기에 Mercer's Theorem을 만족하는 다른 커널들이 있고, 다른 사람들이 사용하는 커널들을 사용할 수도 있다. 우연히 마주칠 수 있는 다른 커널들을 언급해보겠다.

 

그 중의 하나는 polynomial kernel이다. polynomial kernel의 similarity function은 다음과 같다.

\[k(x, l) = (X^Tl)^2\]

잘 사용되지는 않지만, 다른 사람들이 이것을 사용하는 것을 볼 수도 있다. 위의 similarity function은 polynomail kernel의 한 예시이며, 다른 similarity function을 사용하는 것도 있다.(e.g. \((X^Tl)^3, (X^Tl + 1)^3, (X^Tl + S)^4 \rightarrow (X^Tl + constant)^{degree}\)(general form))

Polynomial Kernel은 거의 좀 더 안 좋은 성능을 가진다. 

 

그리고, 가우시안 커널도 그렇게 많이 사용되지는 않는다. 보통 가우시안 커널은 \(x\)와 \(l\)이 엄격히 non-negative한 data에만 사용되고, \(x\)와 \(l\)의 내적이 절대 negative(음수)가 되지 않도록 보장한다. 이것은 \(x\)와 \(l\)이 서로 비슷하다는 것을 포착한 것이고, 이 두 벡터의 내적은 클 것이다. -> 또 다른 특성들도 있지만, 결론은 잘 사용하지 않는다고 한다.

 

또한, 우리가 무엇을 하느냐에 따라서 좀 더 난해한 커널들이 존재한다. string kernel(입력 data가 문자열인 경우), chi-square kernel, histogram intersection kernel 등이 있다. 하지만, Andrew Ng 교수님은 이러한 커널을 우연히 한 번정도 사용할까 말까하고, string kernel의 경우에는 사용해본 적이 없다고 한다.

 

[Multi-class classification]

강의에서 알려줄 두 가지 세부사항이 있는데, 하나는 Multi-class classification이다.

Multi-class classification에서 우리는 일반적으로 K개의 class간의 적절한 decision boundary를 얻을 수 있을 것이다. 대부분 SVM 패키지에서 이미 내장된 multi-class classification 기능을 가지고 있다. 따라서, SVM 라이브러리를 사용하면 적절하게 동작하게 될 것이다. 만약 그렇지 않다면, Logistic Regression에서 배웠던 one-vs-all 방법을 사용해서 1부터 K번째 class까지 SVM을 반복해서(kSVM) 데이터를 예측할 수 있다(\((\theta^{(i)})^Tx\)가 가장 큰 class 선택).

 

[Logistic Regression vs. SVMs]

마지막은 언제 우리가 두 알고리즘 중에 하나를 선택해야하는지에 대해서 이야기해볼 것이다.

- feature n이 m에 비해서 크다면, 예를 들어서 n이 10,000이고 m이 10 ~ 1000이라면 

  -> Logistic Regression이나 Kernel이 없는(linear kernel) SVM을 사용하는 것이 좋다.

- feature n이 작고, training example m이 중간 정도라면, 예를 들어서 n = 1 ~ 1000, m = 10 ~ 10000이라면

   -> 가우시안 커널을 사용하는 SVM이 좋다.

- feature n이 작고, training example m이 크다면, 예를 들어 n = 1 ~ 1000, m = 50,000 이상 이라면

   -> feature을 더 추가하고, Logistic Regression이나 Kernel이 없는 SVM을 사용하는 것이 좋다.

- Neural Network에서는 모든 경우에서 잘 동작하지만, 학습 속도는 느릴 수 있다.

 

 

보여주지는 않았지만, SVM optimization problem은 convex optimization problem(볼록 최적화 문제)이며, 좋은 SVM 최적화 패키지는 항상 Global Optima(전역 최소값) 또는 그에 가까운 값을 찾는다. 따라서, Local Optima(지역 최소값)에 대해서 걱정할 필요는 없다. 

실제로 Local Optima는 NN에서 큰 문제가 되지는 않지만, SVM을 사용하는 경우에는 걱정할 필요가 없다. 다만, 문제에 따라서 NN은 위 가이드라인대로 알고리즘을 선택했지만 SVM보다 더 느릴 수 있다. 가이드라인이 조금 모호하긴 하지만, 실제로 이것을 따르는 것은 괜찮다. 

 

머신러닝 문제에 직면했을 때, 사용하려는 알고리즘이 좋은지 확실하지 않을 수 있지만 중요한 것은 data의 양과 우리가 얼마나 오류를 분석하고 디버깅하는 것에 능숙한가와 새로운 feature를 디자인하고 학습 알고리즘에서 제공하는 feature들을 파악하는데 얼마나 능숙하느냐에 달려있다.