Kernel SVM

커널 서포트 벡터 머신

XOR

XOR(exclusive OR) 문제는 이진수에서의 or 연산이라고 생각하면 된다. 다음과 같이 하나만 1일 때 1이 되고, 나머지 경우는 0이 된다.

	x2=0	x2=1
X1=0	0	1
x1=1	1	0

이러한 경우 다음 그림처럼 클래스가 구분되는데, 퍼셉트론이나 SVM과 같은 선형판별함수 분류모형으로는 이 문제를 풀 수 없다.

이 문제를 SVM으로 풀게되면 아래처럼 선형 경계선이 그어져, 성능이 50정도밖에 나오지 않는다. 따라서 곡선을 사용해 경계를 판별해야 한다.

이러한 경우 사용할 수 있는 방법은 𝐷 차원 독립 변수 벡터 𝑥 대신 기저함수(basis function)으로 변환한 𝑀 차원 벡터 𝜙(𝑥)를 독립 변수 벡터로 사용하는 방법이다.

기저함수를 사용한 비선형 판별 모형

$$\phi (\cdot) : R^D \to R^M$$ $$x = (x_1,x_2,\cdots , x_D) \,\,\,\,\,\to\,\,\,\,\,\phi(x) = (\phi_1(x),\phi_2(x),\cdots , \phi_M(x))$$

기저함수 $\phi $ 는 D차원 벡터인 독립변수를 입력받아 함수식에 따라 계산하여 M개의 스칼라를 출력해 M차원 벡터를 만든다.

앞의 XOR 문제를 풀기 위해 다음과 같이 상호곱(cross-multiplication) 항을 추가한 기저함수를 사용해보자.

$$(x_1, x_2) \,\,\,\,\,\to \,\,\,\,\,\phi(x) = (x_1^2, \sqrt2 x_1x_2,x_2^2)$$

FunctionTransformer 전처리 클래스를 이용하면 기저함수를 이용한 변환을 할 수 있다.

위 기저함수로 변환한 데이터는 다음과 같은 분포를 갖게 되고, $\phi _2$ 가 0보다 큰지 작은지를 기준으로 클래스를 분류할 수 있게 된다.

X_xor2 = FunctionTransformer(basis).fit_transform(X_xor)
plt.scatter(X_xor2[y_xor == 1, 0], X_xor2[y_xor == 1, 1], c="b", marker='o', s=50)
plt.scatter(X_xor2[y_xor == 0, 0], X_xor2[y_xor == 0, 1], c="r", marker='s', s=50)
plt.ylim(-6, 6)
plt.title("변환 공간에서의 데이터 분포")
plt.xlabel(r"$\phi_1$")
plt.ylabel(r"$\phi_2$")
plt.show()

FunctionTransformer 와 SVC 클래스를 합쳐 $\phi$와 $x$ 사이의 비선형관계를 원래의 독립변수공간으로 다시 돌려놓으면 아래와 같이 휘어진 곡선으로 클래스가 분리된다.

from sklearn.pipeline import Pipeline

basismodel = Pipeline([("basis", FunctionTransformer(basis)), 
                       ("svc", SVC(kernel="linear"))]).fit(X_xor, y_xor)
plot_xor(X_xor, y_xor, basismodel, "기저함수 SVC 모형을 사용한 XOR 분류 결과")
plt.show()

결국 이러한 문제에서는 적절한 기저함수 $\phi$ 를 찾아내는 것이 관건이다. 위처럼 제곱, 루트, 곱하기 등 다양한 연산을 해보다 보면 어떻게든 찾을 수 있다. 그런데 이 때는 아래와 같은 문제들이 발생한다.

1. 기저함수를 너무 많이 만들어봐야 해서 계산이 많아진다.

2. 그 중 단 한 개도 제대로 된 기저함수가 안 나올 수도 있다.

그래서 나온 것이 커널이라는 개념이다.

커널 트릭

SVM모델의 목적함수와 예측모형은 다음과 같은 dual form으로 표현할 수 있었다.

$$L = \sum^N_{m=1}a_n-\frac{1}{2}\sum^N_{n=1}\sum^N_{m=1}a_na_my_ny_mx_n^Tx_m$$ $$y = w^Tx - w_0 = \sum^N_{n-1}a_ny_nx_n^Tx-w_0$$

여기서 기저함수를 사용하면 svm 모형을 푸는 것은 아래 수식을 푸는 문제가 된다.

$$L = \sum^N_{m=1}a_n-\frac{1}{2}\sum^N_{n=1}\sum^N_{m=1}a_na_my_ny_m\phi(x_n)^T\phi(x_m)$$ $$y = w^Tx - w_0 = \sum^N_{n-1}a_ny_n\phi(x_n)^T\phi(x)-w_0$$

즉 모든 기저함수는 두 개의 변환된 독립변수벡터를 내적한 $\phi(x_i)^T \phi(x_j)$의 형태로만 사용되며 독립적으로 사용되지 않는다.

따라서 이 값을 하나의 스칼라 함수로 나타낼 수 있다.(입력변수는 벡터)

$$k(x_i,x_j) = \phi(x_i)^T\phi(x_j)$$

이 함수를 커널(kernel)함수라고 한다.

대응하는 기저함수가 존재할 수만 있다면 기저함수를 먼저 정의하고 커널을 정의하는 것이 아니라 커널을 먼저 정의해도 상관 없다.

커널의 의미

위 수식을 커널함수로 바꿔 표현하면 다음과 같다.

$$L = \sum^N_{m=1}a_n-\frac{1}{2}\sum^N_{n=1}\sum^N_{m=1}a_na_my_ny_mk(x_n,x_m)$$ $$y = w^Tx - w_0 = \sum^N_{n-1}a_ny_nk(x_n,x)-w_0$$

두 벡터를 내적하는 것은 두 벡터 사이의 유사도를 측정하는 것과 같으므로 커널함수는 두 표본데이터 간의 유사도를 측정하는 기준으로 볼 수도 있다.

커널 사용의 장점

커널을 사용하면 기저함수를 하나하나 생각해내는 수고를 덜 수 있고, 변환과 내적에 들어가는 계산도 줄어든다.

예를 들어,

$$\phi(x_i) = \phi([x_{i,1},x_{i,2}])= (x_{i,1}^2, \sqrt{2}x_{i,1}x_{i,2},x_{i,2}^2)$$

총 11번의 곱셈을 필요로 하는 위 기저함수는 다음과 같은 커널함수로 대체 가능하다.

$$\begin{eqnarray} k(x_1,x_2) &=& (x_1^Tx_2)^2\\ &=& (x_{1,1}x_{2,1} + x_{1,2}x_{2,2})^2\\ &=& x^2_{1,1}x^2_{2,1} + 2x_{1,1}x_{2,1}x_{1,2}x_{2,2} + x^2_{1,2}y^2_{2,2}\\ &-& (x_{1,1}^2,\sqrt{2}x_{1,1}x_{1,2},x_{1,2}^2)(x_{2,1}^2,\sqrt{2}x_{2,1}x_{2,2},x_{2,2}^2)^T\\ &=& \phi(x_1)^T\phi(x_2) \end{eqnarray}$$

여기서는 같은 계산을 하는 데 3번의 곱셈이면 된다.

커널의 확장생성

다음 규칙을 통해 두 개의 커널함수 $k_1(x_1,x_2), k_2(x_1,x_2)$로부터 새로운 커널을 쉽게 만들어내 사용할 수 있다.

1. 커널함수를 양수인 상수배한 함수는 커널함수다. (단위를 바꾸는 것에 지나지 않기 때문이다.)

   $$k(x_1,x_2) = ck_1(x_1,x_2) \,\,\,(c>0)$$

2. 커널함수에 양수인 상수를 더한 함수는 커널함수다.(기준점이 달라질 뿐 같은 함수다.)

   $$k(x_1,x_2) = k_1(x_1,x_2) + c \,\,\,\,(c>0)$$

3. 두 커널함수를 더한 함수는 커널함수다.

   $$k(x_1,x_2) = k_1(x_1,x_2) + k_2(x_1,x_2)$$

4. 두 커널함수를 곱한 함수는 커널함수다. (하나의 커널함수를 몇제곱해도 커널함수다.)

5. $$k(x_1,x_2) k_1(x_1,x_2)k_2(x_1,x_2)$$
6. $$k(x_1,x_2) k_1(x_1,x_2)k_2(x_1,x_2)$$

8. 단조증가(monotonically increasing)하는 $\exp$, $\text{sigmoid}$ 등의 함수에 집어넣은 커널함수도 커널함수다.

   $$k(x_1,x_2) = (k_1(x_1,x_2))^n\,\,\,(n=1,2,\cdots)\\ k(x_1,x_2) = \exp(k_1(x_1,x_2))\\ k(x_1,x_2) = \text{sigmoid}(k_1(x_1,x_2))$$

9. x1, x2 각각의 커널함수 값의 곱도 커널함수다.

$$k(x_1,x_2) = k_1(x_1,x_1)k_2(x_2,x_2)$$

위 규칙에 따르면 무한히 많은 커널함수를 생성해낼 수 있다.

많이 사용되는 커널

아래 소개하는 커널은 scikit learn에 구현되어있는 커널함수들로, 대부분의 비선형성을 처리할 수 있다. 기본 커널함수 형태에 해당하는 선형 서포트벡터머신에 위 규칙들을 적용해보면 아래 커널들이 다 생성될 수 있음을 알 수 있다.

• 선형 서포트벡터머신

  $$k(x_1, x_2) = x_1^T x_2$$

• 다항 커널

  $$k(x_1,x_2) = (\gamma(x_1^T x-2)+\theta)^d$$

• RBF(Radial Basis Kernel) 또는 가우시안 커널(Gaussian Kernel)

  $$k(x_1,x_2) = \exp(-\gamma||x_1-x_2||^2)$$

• 시그모이드 커널(Sigmoid Kernel)

  $$k(x_1, x_2) = \tanh(\gamma(x_1^Tx_2)+\theta)$$

1) 다항 커널

위에서 소개한 다항 커널(Polynomial Kernel)은 벡터의 내적으로 정의된 커널을 1번, 2번, 4번 규칙을 통해 확장하여 만들 수 있는 커널이다.

$$k(x_1,x_2) = (\gamma(x_1^Tx_2)+\theta)^d$$

간단한 예로 $\gamma = 1, \theta = 1, d = 3$ 이고 $x$ 가 스칼라인 경우,

$$\begin{eqnarray} k(x_1,x_2) &=& (x^T_1x_2+1)^4\\ &=& x_1^4x_2^4 + 4x_1^3x_2^3 + 6x_1^2x_2^2 + 4x_1x_2 + 1\\ &=& (x_1^4,2x_1^3,\sqrt6 x_1,2x_1,1)^T(x_2^4,2x_2^3,\sqrt6 x_2,2x_2,1) \end{eqnarray}$$

와 같이 기저함수의 내적으로 표현되는 4차 다항커널이 된다. 여기서 기저함수는 다음 5개가 된다.

$$\begin{eqnarray} \phi_1(x) &=& x^4\\ \phi_2(x) &=& 2x^3\\ \phi_3(x) &=& \sqrt6 x^2\\ \phi_4(x) &=& 2x\\ \phi_5(x) &=& 1 \end{eqnarray}$$

이 커널과 기저함수들을 그래프로 나타내면 아래와 같다.

2) RBF 커널

가우시안 커널이라고도 불리는 RBF 커널은 차수가 무한대인 다항커널과 같다.

간단하게 하기 위해 $\gamma = \frac{1}{2}$ 로 놓았을 때 다음과 같은 RBF 커널이 나온다.

$$\begin{eqnarray} k(x_1,x_2) &=& \exp\left(-\dfrac{||x_1-x_2||^2}{2}\right)\\ &=&\exp\left(-\frac{x_1^Tx_1}{2} - \frac{x_2^Tx_2}{2} + 2x_1^Tx_2\right)\\ &=&\exp\left(-\frac{x_1^Tx_1}{2}\right)\exp\left(-\frac{x_2^Tx_2}{2}\right)\exp(x_1^Tx_2)\\ &=&C\exp(x_1^Tx_2)\\ &\approx& C\left(1 + (x_1^Tx_2) + \frac{1}{2!}(x_1^Tx_2)^2 + \frac{1}{3!}(x_1^Tx_2)^3 + \cdots\right) \end{eqnarray}$$

이 RBF 커널함수를 그래프로 보면 다음과 같다.

x1 = 0.0
x2 = np.linspace(-7, 7, 100)

def rbf(x1, x2, gamma):
    return np.exp(-gamma * np.abs(x2 - x1) ** 2)

plt.figure(figsize=(8, 4))
plt.subplot(121)
plt.plot(x2, rbf(x1, x2, 1), ls="-", label="gamma = 1")
plt.plot(x2, rbf(x1, x2, 0.5), ls=":", label="gamma = 0.5")
plt.plot(x2, rbf(x1, x2, 5), ls="--", label="gamma = 5")
plt.xlabel("x2 - x1")
plt.xlim(-3, 7)
plt.legend(loc=1)
plt.title("RBF 커널")

plt.subplot(122)
plt.plot(x2, rbf(-4, x2, 1))
plt.plot(x2, rbf(-2, x2, 1))
plt.plot(x2, rbf(0, x2, 1))
plt.plot(x2, rbf(2, x2, 1))
plt.plot(x2, rbf(4, x2, 1))
plt.xlabel("x2")
plt.title("RBF 커널의 기저함수들")

plt.show()

scikit-learn의 커널 SVM

scikit-learn의 SVM 클래스에서는 kernel 인수를 지정하여 커널을 설정할 수 있다.

• kernel = 'linear' : 선형 SVM 커널

• kernel = 'poly' : 다항 커널

  • gamma : $\gamma$
  • coef0 : $\theta$
  • degree : $d$

• kernel = 'rbf' : RBF 커널(디폴트값이 rbf라서 써주지 않아도 된다.)

• kernel = 'sigmoid' : 시그모이드 커널

polysvc = SVC(kernel="poly", degree=2, gamma=1, coef0=0).fit(X_xor, y_xor)
rbfsvc = SVC(kernel="rbf").fit(X_xor, y_xor)
sigmoidsvc = SVC(kernel="sigmoid", gamma=2, coef0=2).fit(X_xor, y_xor)

plt.figure(figsize=(8, 12))
plt.subplot(311)
plot_xor(X_xor, y_xor, polysvc, "다항커널 SVC를 사용한 분류 결과")
plt.subplot(312)
plot_xor(X_xor, y_xor, rbfsvc, "RBF커널 SVC를 사용한 분류 결과")
plt.subplot(313)
plot_xor(X_xor, y_xor, sigmoidsvc, "시그모이드커널 SVC를 사용한 분류 결과")
plt.tight_layout()
plt.show()

커널 파라미터의 영향

$\gamma$ 값이 작으면 $x_2$와 $x_1$의 유사도에 따라 커널함수의 기울기와 값이 많이 달라진다.

$\gamma$ 값이 크면 $x_2$와 $x_1$이 멀리 떨어져있든 가까이 있든 커널함수 값이 별로 차이 나지 않는다.

svm은 서포트벡터라는 대표값과의 유사도를 측정하여 가까이 있는 애들을 기준으로 클래스를 판별하는 거였다. 커널 svm에서는 그 유사도의 계산기준이 커널이기 때문에 감마값이 작으면 새로운 데이터와 기존 애들과의 유사도를 측정할 때 넓은 영역 안에서 유사도가 있다고 판단하지만, 감마값이 커지면 서포트벡터(기존의 빨간 점들)와의 유사도가 진짜 가깝지 않으면 없다고 판단하므로 오버피팅이 된다.

위에서 $\gamma$가 2인 것은 정규화된 것이고 100인 것은 오버피팅된 것이다.