커널 서포트 백터머신 기초개념

2019-04-09

.

그림, 실습코드 등 학습자료 출처 : https://datascienceschool.net

# 커널 서포트 백터머신

  • 서포트 벡터머신은 판별함수 모형이다. 판별함수 모형이기 때문에 영역을 가를 수 있는 경계선의 위치를 찾아내는 문제이다. 문제는 이 경계선은 직선이다. 만약에 데이터가 나누어지는 영역이 직선이 아니라 곡선이나 다른 복잡한 형태이면 직선으로 되어있는 판별모형은 사용할수가 없다.

  • 많은 예시가 있겠지만 대표적으로 직선형태의 판별함수가 풀 수 없는 문제가 ‘XOR 문제’이다. 1 & 3사분면이 같은 클래스인 데이터고, 2 & 4사분면이 같은 클래스인 데이터이다. 이런경우에는 직선인 라인 하나로는 풀 수 없다.

  • 이렇게 비선형인 데이터에 대해서는 기저함수를 사용하면 된다. 기저함수를 사용해서 비선형인 데이터를 x가 아니라 파이라고하는 새로운 특징함수를 쓰는데 이 파이는 x를 비선형변환시킨것이다. 그때 이 비선형 변환시키는 함수가 기저함수이다. 가장 대표적인것이 다항함수이다. 다항함수는 x라는 벡터가 하나 있을때 x, x제곱, x세제곱, x네제곱… 이런식으로 여러가지 함수를 생각을 하는것이다. 피쳐가 d개가 있는데 기저함수를 이용해서 이 피쳐를 변형시키면 이 피쳐의 갯수는 내가 생각해낸 기저함수의 갯수만큼 피쳐의 수가 늘어나게 된다.

  • 다시말해 아래의 수식처럼 원래의 D 차원 독립 변수 벡터 x 대신 기저함수 으로 변환한 M차원 벡터 \(\ \phi(x)\)를 독립변수 벡터로 사용하는 것이다.

\[\ \phi(\cdot): {R}^D \rightarrow {R}^M\] \[\ x=(x_1, x_2, \cdots, x_D) \;\;\; \rightarrow \;\;\; \phi(x) = (\phi_1(x), \phi_2(x), \cdots, \phi_M(x))\]

x자체는 D개의 피쳐가 있었는데 그 피쳐를 갖고 파이라고 하는 기저함수로 변형해서 새로운 피쳐를 하나 만드는 것이다. 여기서 주의해야할 점은 x가 벡터로 들어가는 것이다. 즉 벡터입력을 받아서 파이1이라는 스칼라 값을 출력하게 된다. 만약에 내가 M개의 기저함수를 생각해냈다면 파이1 ~ 파이M이라는 스칼라 값(총 M개의 스칼라값)까지 출력을 하게 된다. 그러면 결과적으로 M차원의 벡터가 된다.

  • 아래 수식과 같이 cross-multiplication항을 추가한 기저함수를 사용하면 XOR 문제를 풀 수 있다. XOR문제에서는 피쳐가 x1,x2 두개가 있었다. 얘를 어떻게 비선형을 시켜서 분리를 해낼 수 있는 새로운 피쳐를 만들자는 것이다. x1을 제곱하는 방법, x1과 x2를 곱하는 방법, x2를 제곱하는 방법 총 세가지의 기저함수를 생각해 낸 것이다.
\[\ (x_1, x_2) \;\;\; \rightarrow \;\;\; \phi(x) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)\]

위와 같은 수식으로 실제로 xor문제를 풀 수 있는데 이거는 사람이 생각해 내는 만큼 이 수식 말고도 이 문제를 풀 수 있는 수식이 더 있을 수 있다.

파이1, 파이2, 파이3 공간에서는 직선인데 파이하고 x사이에 비선형 관계가 있다보니까 그거를 도로 x공간으로 살리면 휘어져보이는 것이다.

  • 결국에는 비선형 문제를 푸는 것은 파이를 찾는 것이다. 원래 있던 x를 비선형 변환해서 제대로 분류할 수 있는 파이를 생각해 내야한다. 그래서 보통 할 수 있는 것은 우리가 생각해 낸 수식들을 다 넣는 방법이다. 그리고 생각해 낸 수식중에서 하나는 걸리겠지 하는 생각으로 다 집어넣으면 된다. 다항회귀에서 했던것처럼..

  • 그런데 그렇게 무식하게 하다보면 문제가 있는데 기저함수를 여러개를 자꾸 많이 만들수록 그중에 걸릴 가능성이 높아지니까 자꾸 많이 만들어야 한다. 그러면 차원이 커져서 계산량이 많아지게 된다. 계산양이 많아도 그중에 하나만 걸려도 다행인데 안걸릴수도 있다.

  • 사람이 없는 것을 새롭게 생각해내는것이 어렵다. 그래서 사람들이 고민하다가 생각해 낸것이 커널이라는 개념이다. 이 커널이 어떻게 나왔는지 알아보기 위해 서포트벡터머신의 문제의 수식을 아래와 같이 리마인딩했다.

\[\ L = \sum_{n=1}^N a_n - \dfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^N a_n a_m y_n y_m x_n^T x_m\]

위의 수식은 서포트벡터머신을 피팅하는 수식으로 듀얼형식은 위와같은 qp문제를 푸는것인데 왜 이게 듀얼형식이냐 an,am 이것은 스칼라 값이고, yn하고 ym은 +1 또는 -1 만 가질수 있는 스칼라 값이다. 뒤에는 xn과 xm의 내적으로 된 스칼라값이다. 이런문제를 풀어야 했고 그리고 나중에 푼 다음에 그것을 사용해 prediction을 할때는 아래와 같은 수식으로 prediction을 한다.

\[\ y = w^T x - w_0 = \sum_{n=1}^N a_n y_n x_n^T x - w_0\]

위의 수식은 서포트벡터 머신을 이용해 prediction하는 수식으로

an,yn,xn과 내가 새로 테스트 하려는 새로운 x사이에 내적을해서 계산을 한다.

  • 위의 수식을 기저함수로 변환한다면 아래의 수식과 같이 x가 전부 파이라고 하는 새로운 피쳐벡터로 바뀌게 된다. 이렇게 하면 기저함수를 사용하는 서포트벡터머신을 푸는 것이다.
\[\ L = \sum_{n=1}^N a_n - \dfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^N a_n a_m y_n y_m \phi(x_n)^T \phi(x_m)\] \[\ y = w^T x - w_0 = \sum_{n=1}^N a_n y_n \phi(x_n)^T \phi(x) - w_0\]
  • 근데 위처럼 해보니까 무슨생각이 들었냐면 피팅하는 수식이나 프리딕션하는 수식이나 파이라는 벡터가 혼자서 쓰이지는 않았다.

다시말해서 \(\ \phi(x_i)^T\phi(x_j)\) 로 계산되어 스칼라형태로 사용이 되었다.

그러면 비선형성을 캐치할때까지 파이들을 만드느냐고 고생하냐 파이들을 만들면 뭐하냐 결국에는 이렇게 하나로 묶여서 스칼라로 나오는데,

그러면 처음부터 \(\ \phi(x_i)^T\phi(x_j)\)를 하나의 함수로 만들어서 서포트벡터머신 수식에 끼워넣어도 똑같지 않느냐. 그래서 나온 것이 아래의 수식과 같은 커널이라는 개념이다. 파이벡터를 m개 만드는 짓하지말고 스칼라 함수 하나를 만들자. 그러면 함수를 하나만 만들면된다.

\[\ k(x_i, x_j) = \phi(x_i)^T \phi(x_j)\]

  • 이렇게하면 우리는 함수 하나만 만들면 되는 것이다. 과거에는 함수를 파이1도 만들어야하고, 파이2도 만들어야 하고, 각각 다 만들어야 했지만 차피 이 파이들이 내적으로 계산되어 쓸건데 뭐하로 이렇게 따로따로 만드냐. 그냥 이 파이들이 내적으로 계산되어 나온 값과 동일한 값을 내는 스칼라 함수 하나만 만들자는 것이다.

  • 커널함수만 내가 서포트벡터머신에 주게되면 서포트백터머신이 이것을 갖고 베이시스 방식의 서포트 벡터머신 프리딕션이나 피팅을 하는데 문제가 없다.

  • 그러면 이 커널이라는 함수만 만들면 되는데 이 함수는 어떤함수인가 의미를 따져보면 이 커널함수는 내적이 된 함수이다. 내적이라는 것은 xi와 xj의 유사도를 측정하는 것과 같다. 그러면 커널함수는 xi와 xj의 유사도를 측정하는 어떤 다른 함수를 넣으면 혹시 이것도 작동하지 않을까라는 아이디어가 나왔다. 예를들어 코사인 유사도 말고, 유클리디안 유사도를 넣는다거나 이런식으로 다른 유사도를 계산하는 수식을 커널함수로 집어넣어도 되지 않을까라는 힌트를 얻어서 아래 수식과 같이 k함수를 넣은 것이다.

  • 정리하면 커널은 xi라는 벡터와 xj라는 벡터를 입력받아서 스칼라 값을 내보내기만 하면 된다. 다만 커널이 제 역할을 해야하려면 xi와 xj의 유사도를 측정하는 함수여야 한다. 그냥 아무함수나 쓰면 안된다. 그리고 이 커널을 분해했을때 도로 기저함수가 나올 수 있어야한다. 이런 조건을 만족하는 커널을 찾아내면 된다.

예를들어 서포트 벡터머신의 목적함수와 예측모형의 커널을 사용했을때 수식

\[\ L = \sum_{n=1}^N a_n - \dfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^N a_n a_m y_n y_m k(x_n, x_m)\] \[\ y = w^T x - w_0 = \sum_{n=1}^N a_n y_n k(x_n, x) - w_0\]

커널을 사용하지 않는 경우 \(\ k(x, y) = x^Ty\) 라는 점을 고려하면 커널은 다음과 같은 특징이 있다.

1) x 와 y 가 동일한 벡터일 때 가장 크고

2) 두 벡터간의 거리가 멀어질 수록 작아진다.

  • 커널을 사용하면 베이시스 함수를 하나씩 정의하는 수고를 덜 수 있을뿐만 아니라 변환과 내적에 들어가는 계산량도 줄어든다.

예를 들어, 다음과 같은 기저함수의 경우 xi가 들어가면 이 벡터가 xi,1과 xi,2라는 두개의 스칼라 원소로 이루어지는 벡터로 들어가져서 실제로는 파이1, 파이2, 파이3 세개가 결과로 나오는 구조이다.

\[\ \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)\]

커널 방법을 쓰지 않을 경우에 \(\ \phi(x_i)^T \phi(x_j)\)를 계산하려면 x1을 파이로 바꾸는데 곱하기 3번, x2를 파이로 바꾸는데 곱하기 3번, 파이1과 파이2를 내적하는데 곱하기가 3번 총 9번을 해야한다.

그런데 커널을 사용하면 아래와 같이 실제로는 x1이라는 벡터와 x2라는 벡터의 내적해서 만든 스칼라값을 제곱한 것과 같다. 원래 서포트 벡터머신에서는 커널로 그냥 x1과 x2를 내적한것을 커널로 썼다. 이 두방법이 결국은 같다는 것을 아래 수식에서 알 수 있다.

\[\ \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_{1,1}^2x_{2,1}^2 + 2x_{1,1}x_{2,1}x_{1,2}x_{2,2} + x_{1,2}^2y_{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}\]

\(\ \phi(x_i)^T \phi(x_j)\)를 계산하는데 \(\ x_1^Tx_2\) 곱셈 2번 + 제곱에 해당되는 곱셈 1번 총 3번만 계산하면 된다.

  • 위에 언급한 것처럼 커널함수의 조건을 만족하는 함수를 찾는 것은 쉽다. 왜냐하면 얘는 스칼라 함수고 딱 하나만 찾으면 되기 때문이다. 거기에 더 좋은 것은 커널 확장규칙이라는 것이 존재한다.

  • 만약에 내가 커널을 갖다가 어떤 것을 하나 찾아냈다 하면 저 커널의 확장 규칙을 이용할 수 있다. 최초에 커널을 찾아내면 그것을 이용해서 다른 커널을 또 찾아내는 규칙을 말한다. 유사도 함수가 하나 있을때 또 다른 유사도 측정하는 기준을 만드는 방법이다.

  • 예를 들어서 k1(x1,x2)와 k2(x1,x2)라는 두개의 커널을 생각해 냈다고 하자. 그러면 이 두개를 이용해서 아래와 같은 함수의 커널로도 확장해서 쓸 수 있다.

1) 커널함수에 양수를 곱한값도 커널함수이다. 유사도를 구할때 가령 mm를 cm로 변환하는 것과 다르지 않다.

\[\ 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) 두개의 커널함수를 곱함것도 커널함수이다.

\[\ k(x_1, x_2) = k_1(x_1, x_2)k_2(x_1, x_2)\]

5) 원래 있던 함수의 제곱도 커널함수이고, 세제곱해도 커널함수이다. 그리고 커널함수의 n승을해도 커널함수이다.

\[\ k(x_1, x_2) = (k_1(x_1, x_2))^n \;\; (n=1, 2, \cdots)\]

6) 커널함수에 단조증가하는 함수에 집어넣게 된 함수도 커널함수이다. 예를들어 exp, 시그모이드 함수가 있다.

\[\ 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))\]

7) x1,x2 각각의 커널함수값의 곱도 커널함수이다.

\[\ k(x_1, x_2) = k_1(x_1, x_1)k_2(x_2, x_2)\]
  • 아래와 같은 커널들이 많이 사용되는 커널들이다. 이 커널들은 대부분 기저함수로 변환하였을 때 무한대의 차원을 가지는 기저함수가 된다. 따라서 대부분의 비선형성을 처리할 수 있다. 전부 유사도를 측정할때 관련이 있는 함수이다.

1) 선형 서포트 벡터머신

\[\ k(x_1, x_2) = x_1^Tx_2\]

2) 다항커널

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

3) RBF(Radial Basis Function) 또는 가우시안 커널

\[\ k(x_1, x_2) = \exp \left( -\gamma ||x_1-x_2||^2 \right)\]

RBF 커널은 가우시안 정규분포의 pdf를 닮았다고해서 가우시안 커러이라고도 부른다. 문제를 간단하게 하기 위해 감마를 1/2라고 두면 아래와 같이 계산할 수 있다.

\[\ \begin{eqnarray} k(x_1, x_2) &=& \exp{\left(-\frac{||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) + \dfrac{1}{2!}(x_1^Tx_2)^2 + \dfrac{1}{3!}(x_1^Tx_2)^3 + \cdots \right) \\ \end{eqnarray}\]

즉 차수가 무한대인 다항커널과 같다.

4) 시그모이드 커널

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

앞의 xor문제를 푼 기저함수는 \(\ \gamma = 1, \theta= 0, d=2\)인 다항 커널임을 알 수 있다.

  • RBF에서 커널파라미터의 영향(감마값에 따른 영향)

커널이 거리를 측정할때 감마값이 작으면 x1과 x2가 멀리 떨여져 있어도 조금씩 거리가 작아지고 있다는 것으로 인지하는데 감마값이 엄청커지면 이게 어느 인계점만 넘으면 어디에 있던 거리에 대한 차이를 못느끼게 된다.

%matplotlib inline
%config InlineBackend.figure_formats = {'png', 'retina'}
from sklearn.svm import SVC

def plot_xor(X, y, model, title, xmin=-8, xmax=8, ymin=-8, ymax=8):
    XX, YY = np.meshgrid(np.arange(xmin, xmax, (xmax-xmin)/1000), np.arange(ymin, ymax, (ymax-ymin)/1000))
    ZZ = np.reshape(model.predict(np.array([XX.ravel(), YY.ravel()]).T), XX.shape)
    plt.contourf(XX, YY, ZZ, cmap=mpl.cm.Paired_r, alpha=0.5)
    plt.scatter(X[y == 1, 0], X[y == 1, 1], c='r', marker='o', s=50)
    plt.scatter(X[y == 0, 0], X[y == 0, 1], c='g', marker='s', s=50)
    plt.xlim(xmin, xmax)
    plt.ylim(ymin, ymax)
    plt.title(title)
    plt.xlabel("x1")
    plt.ylabel("x2")

np.random.seed(0)
X_xor = 3 * np.random.randn(200, 2)
y_xor = np.logical_xor(X_xor[:, 0] > 0, X_xor[:, 1] > 0)
y_xor = np.where(y_xor, 1, 0)

plt.figure(figsize=(8, 8))
plt.subplot(221)
plot_xor(X_xor, y_xor, SVC(kernel="rbf", gamma=1).fit(X_xor, y_xor), "gamma=1")
plt.subplot(222)
plot_xor(X_xor, y_xor, SVC(kernel="rbf", gamma=5).fit(X_xor, y_xor), "gamma=5")
plt.subplot(223)
plot_xor(X_xor, y_xor, SVC(kernel="rbf", gamma=10).fit(X_xor, y_xor), "gamma=10")
plt.subplot(224)
plot_xor(X_xor, y_xor, SVC(kernel="rbf", gamma=20).fit(X_xor, y_xor), "gamma=20")
plt.tight_layout()
plt.show()

kernel_SVM_1_0

  • 다항커널이랑 시그모이드 커널의 계수만 보고 모양이 어떻게 나올지 예측하는 것은 불가능하다. 그러나 RBF 커널은 대강 예측이 가능하다. 위의 그림처럼 감마값이 커질수록 커널에서 사용하는 커널함수 즉 유사도 측정하는 함수의 폭이 점점 작아진다.

  • 감마값이 너무 커진다는 것은 오버피팅 된다는 것이다. 이 감마값을 잘 조절해서 우리가 오버피팅 시킬건지, 정규화시킬건지 정할 수 있다.

  • 서포트벡터머신은 서포트 벡터라고 부르는 대표값이랑 유사도를 측정해서 가까이 있는 얘들의 클래스로 판단을 하는 것인데 거기서 가까이 있다 없다 측정해주는 것이 커널이다.

  • 커널 서포트벡터머신에서 가장 중요한 것은 basis라는 개념이다 basis function을 사용을 하게되면 이걸 많이 쓰면 많이 쓸 수록 이 데이터가 비선형적이고 복잡한 형태에서도 이 중에 무언가로는 캐치할 수 있다는 것이다. 문제는 이 basis function을 사람이 생각해야 한다. 그래서 파이1, 파이2, 파이3.. 다 생각해줘야 한다. 그게 귀찮으니까 위와같이 커널방법을 이용한 것이고, 이 basis function 생각하는 것까지 기계한테 맡겨보자는 개념이 multi layer perceptrone, 흔히 말하는 신경망이다.

  • 신경망의 개념은 basis funtion을 특정하게 한정하지 않고 컴퓨터가 여러가지로 쓸 수 있게 해준다. 그래서 adaptive basis function이라고도 한다. 이렇게 basis function을 쓰는 거 이후 최종적으로 판단하는 것은 퍼셉트론하고 같은 방식이다. stocastic grediant decent를 써서 여기에 들어가는 어떤 파라미터값 또는 퍼셉트론 자체에 들어가는 파라미터 값을 한꺼번에 찾아낸다.