서포트 벡터 머신과 커널(Support vector machines and kernels)

두 무리를 가르는 직선이 여럿이라면 어느 것이 좋을까요? 퍼셉트론⁠(perceptron)⁠은 가르는 직선을 하나 찾으면 멈추는데, 그 직선이 어느 한 무리에 바짝 붙어 있을 수도 있습니다. 그러면 새 점이 조금만 비껴 와도 틀립니다. 서포트 벡터 머신(SVM)은 두 무리 사이에 놓을 수 있는 가장 넓은 빈 띠를 찾아 그 한가운데로 경계를 긋습니다. 경계에서 가장 가까운 점까지의 거리를 마진이라 하고, 띠의 폭은 마진의 두 배입니다.

점 $\vec x$에서 직선 $\vec w\cdot\vec x + b = 0$까지의 거리는 $|\vec w\cdot\vec x + b|/\lVert\vec w\rVert$입니다. 점을 $\vec w$ 방향으로 정사영⁠(orthogonal projection)⁠한 길이를 재는 셈이라 내적이 들어갑니다. w와 b에 같은 수를 곱해도 직선은 그대로이므로, 가장 가까운 점에서 $|\vec w\cdot\vec x + b| = 1$이 되게 크기를 맞추면 마진은 $1/\lVert\vec w\rVert$, 띠의 폭은 $2/\lVert\vec w\rVert$입니다. 그러니 가장 넓은 띠를 찾는 일은 노랑을 $y = +1$, 파랑을 $y = -1$로 적을 때 다음 문제가 됩니다.

$$\min_{\vec w,\, b}\ \tfrac12\lVert\vec w\rVert^2 \quad\text{조건: 모든 } i\text{에 대해 } y_i(\vec w\cdot\vec x_i + b) \ge 1$$

목적 함수⁠(function)⁠는 그릇 모양의 이차식이고 조건은 모두 일차 부등식이라 볼록 최적화⁠(optimization)⁠ 문제입니다. 가를 수 있는 자료라면 답이 꼭 하나 있고, 효율적으로 풀 수 있습니다. 아래 점들을 끌어 보세요. 점을 누르면 색이 바뀝니다. 벌점의 세기는 $\log_{10} C$ = 입니다(C는 잠시 뒤에 설명합니다). 지금 띠의 폭은 , 서포트 벡터는 개입니다.

고리를 두른 점들만이 답을 정합니다. 고리가 없는 점은 띠 밖에 머무는 한 아무리 옮겨도 경계가 꿈쩍하지 않습니다. 까닭은 라그랑주 승수법을 부등식 조건으로 넓힌 KKT 조건⁠(KKT conditions)⁠에 있습니다. 점마다 승수 $\alpha_i \ge 0$를 두고 풀면 답은 $\vec w = \sum_i \alpha_i y_i \vec x_i$ 꼴이고, 조건이 빡빡하지 않은 점($y_i(\vec w\cdot\vec x_i + b) > 1$)의 승수는 반드시 0입니다(상보 여유성⁠, complementary slackness⁠). 가를 수 있는 자료라면 w를 받치는 것은 띠의 가장자리에 닿은 점들뿐이고, 그래서 이 점들을 '받치는 벡터⁠(vector)⁠', 서포트 벡터라 부릅니다. 서포트 벡터가 아닌 점을 빼고 다시 풀어도 답이 같으므로, 한 점씩 빼 보는 교차 검증⁠(cross-validation)⁠에서 틀릴 수 있는 점은 서포트 벡터뿐이고, 오류율은 (서포트 벡터 수)/n을 넘지 않습니다.

이제 파란 점 하나를 노란 무리 깊숙이 끌어 보세요. 어떤 직선으로도 가를 수 없게 되어 위의 조건을 모두 만족할 수 없습니다. 그래서 점마다 조건을 어길 여유 $\xi_i \ge 0$를 허락하되, 그만큼 벌점을 줍니다.

$$\min_{\vec w,\, b,\, \xi}\ \tfrac12\lVert\vec w\rVert^2 + C\sum_i \xi_i \quad\text{조건: } y_i(\vec w\cdot\vec x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0$$

가장 좋은 여유는 $\xi_i = \max(0,\ 1 - y_i f(\vec x_i))$이므로($f(\vec x) = \vec w\cdot\vec x + b$), 이 문제는 힌지 손실⁠(hinge loss)⁠ $\max(0, 1 - yf)$의 합에 C를 곱하고 정규화 벌점 $\tfrac12\lVert\vec w\rVert^2$을 더한 것을 줄이는 문제와 같습니다. C가 크면 띠를 좁혀서라도 어기는 점을 줄이고, C가 작으면 몇 점의 침범을 받아들이는 대신 띠를 넓힙니다. C를 1보다 작게 줄여 보세요. 띠가 넓어지고 서포트 벡터가 늘어납니다. 손실을 나란히 놓으면 차이가 보입니다. 로지스틱 회귀⁠(logistic regression)⁠의 손실은 $\log(1 + e^{-yf})$, 퍼셉트론은 $\max(0, -yf)$, 힌지는 $\max(0, 1 - yf)$입니다. 힌지 손실은 띠 밖에서 정확히 0이라 멀리 떨어진 점은 답에 아무 영향을 주지 않고, 로지스틱 손실은 어디서도 0이 아니라 모든 점이 조금씩 당깁니다.

이 문제는 승수 α에 대한 문제(쌍대 문제⁠, dual problem⁠)로 바꿔 쓸 수 있고, 두 문제는 같은 분류기를 줍니다.

$$\max_{\alpha}\ \sum_i \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\,(\vec x_i\cdot\vec x_j), \quad 0 \le \alpha_i \le C,\ \ \sum_i \alpha_i y_i = 0$$

자료는 내적 $\vec x_i\cdot\vec x_j$로만 나오고, 분류 함수도 $f(\vec x) = \sum_i \alpha_i y_i\,(\vec x_i\cdot\vec x) + b$로 내적만 씁니다. 그러니 점들을 더 높은 차원으로 옮겨 놓고 거기서 직선(평면)으로 가를 수 있다면, 옮긴 점들의 내적만 계산할 수 있으면 됩니다. 수직선 위의 예를 봅시다. −3, −2, 2, 3은 노랑, −1, 0, 1은 파랑이면 문턱⁠(threshold)⁠ 하나로는 가를 수 없습니다. 그런데 x를 평면의 점 $(x, x^2)$로 옮기면 노랑은 $x^2 \ge 4$, 파랑은 $x^2 \le 1$이라 가로선 $x^2 = 2.5$가 둘을 가르고, 원래 직선으로 돌아오면 '|x| < 1.58이면 파랑'이라는 두 문턱이 됩니다.

평면의 점이라면 $\varphi(x_1, x_2) = (x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2,\ \sqrt2\,x_1,\ \sqrt2\,x_2,\ 1)$로 6차원에 옮길 수 있는데, 전개해 보면 $\varphi(\vec x)\cdot\varphi(\vec z) = (\vec x\cdot\vec z + 1)^2$입니다. 6차원의 내적을 2차원 내적 한 번으로 계산하는 것입니다. 6차원 공간의 평면(초평면⁠, hyperplane⁠)은 원래 평면에서 타원⁠(ellipse)⁠이나 쌍곡선⁠(hyperbola)⁠ 같은 이차곡선이 됩니다. 이렇게 내적을 커널 함수 $k(\vec x, \vec z)$로 바꿔 넣고 φ는 한 번도 계산하지 않는 것이 커널 트릭입니다. 가장 널리 쓰는 가우스(RBF) 커널 $k(\vec x, \vec z) = e^{-\gamma\lVert\vec x - \vec z\rVert^2}$에 해당하는 φ는 무한 차원입니다.

어떤 k가 커널이 될 수 있을까요? k가 어떤 공간의 내적이 될 필요충분조건은, k가 대칭이고 어떤 점들을 몇 개 고르든 $k(\vec x_i, \vec x_j)$를 늘어놓은 행렬⁠(matrix)⁠ K가 양의 준정부호(모든 벡터 c에 대해 $c^{\mathsf T}Kc \ge 0$)인 것입니다. 필요한 쪽은 한 줄로 보입니다. k가 φ의 내적이면 $c^{\mathsf T}Kc = \lVert \sum_i c_i\varphi(\vec x_i)\rVert^2 \ge 0$이기 때문입니다. 반대로 이 조건만 있으면 그런 공간과 φ를 실제로 만들 수 있다는 쪽이 더 깊은 정리이고, 머서(1909)와 아론샤인(1950)의 작업에서 나왔습니다.

아래 자료는 가운데 원반의 노랑을 둘레의 파랑이 감싸고 있습니다. 커널을 로 바꿔 보세요. 가우스 커널⁠(Gaussian kernel)⁠의 폭은 $\log_{10}\gamma$ = 입니다. 지금 학습 자료 정확도는 , 서포트 벡터는 개입니다.

직선 커널로는 가를 수 없어서 정확도가 61.1%, 곧 모든 점을 파랑이라 답할 때와 같은 값에 머뭅니다. 이차 다항 커널은 C가 1 이상이면 서포트 벡터 5개만으로 타원 경계를 찾습니다. 가우스 커널에서 γ를 키우면 커널이 좁아져 점마다 제 섬을 두르는 경계가 되고, 서포트 벡터가 거의 모든 점⁠(almost everywhere)⁠으로 늘어납니다. 학습 자료는 다 맞히지만 새 점에서는 믿기 어려운 과적합⁠(overfitting)⁠입니다. γ와 C는 교차 검증으로 고릅니다. 가우스 커널의 f는 $\sum_i \alpha_i y_i e^{-\gamma\lVert\vec x - \vec x_i\rVert^2} + b$, 곧 서포트 벡터들이 가까울수록 크게 던지는 가중 투표라서 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠와도 닮았습니다.

무한 차원으로 옮겨도 괜찮은 까닭은 마진에 있습니다. 바프니크의 이론에 따르면 반지름 R인 공 안의 자료를 마진 γ 이상으로 가르는 분류기들의 복잡도(VC 차원⁠, VC dimension⁠)는 차원 d와 $(R/\gamma)^2$ 가운데 작은 쪽에 1을 더한 값을 넘지 않습니다(여기서 γ는 커널의 γ가 아니라 마진입니다). 퍼셉트론이 고치는 횟수의 상한⁠(upper bound)⁠ $(R/\gamma)^2$과 같은 양입니다. 마진이 넓으면 차원의 저주⁠(curse of dimensionality)⁠를 어느 정도 피할 수 있다는 뜻입니다. 최적의 경계 초평면은 1960년대 바프니크와 체르보넨키스가 연구했고, 커널을 '퍼텐셜 함수⁠(potential function)⁠'로 쓰는 생각은 1964년 소련의 아이제르만, 브라베르만, 로조노에르가 냈습니다. 1992년 벨 연구소의 보저, 가이언, 바프니크가 둘을 합쳤고, 1995년 코르테스와 바프니크가 소프트 마진⁠(soft margin)⁠을 더했습니다. 이 그림의 계산은 1998년 존 플랫이 낸 SMO(승수를 둘씩 풀어 가는 방법)를 따랐습니다. SVM은 2000년대 글 분류, 손글씨 인식, 생물 정보학 등에서 가장 널리 쓰인 방법 가운데 하나였습니다.

이어지는 곳. 목적 함수의 $\tfrac12\lVert\vec w\rVert^2$은 릿지 벌점 그 자체라 정규화와 같은 자리에 있습니다. 조건이 있는 최적화를 승수로 바꾸는 일은 라그랑주 승수법에서, 원래 문제와 쌍대 문제의 답이 같아지는 이유는 볼록 최적화의 쌍대성⁠(duality)⁠에서 옵니다. 커널은 두 점의 비슷함을 재는 함수라서 코사인 유사도⁠(cosine similarity)⁠ 같은 유사도⁠(similarity)⁠와 같은 줄기에 있고, 자료를 커널로 옮긴 뒤 퍼진 방향을 찾으면 커널 주성분 분석⁠(principal component analysis)⁠이 됩니다. 커널을 고르는 것은 점들을 옮겨 놓을 특성 공간을 사람이 미리 정하는 셈인데, 신경망⁠(neural network)⁠은 그 특성 자체를 자료에서 배웁니다. 2010년대 이후 이미지와 음성에서는 신경망이 SVM을 앞질렀습니다.