📂머신러닝

서포트 벡터 머신

모델 ¹

쉬운 정의

이진분류^{binary Classification} 가능한 데이터를 가장 잘 구분하도록하는 직선이나 평면을 구하는 방법을 서포트 벡터 머신이라 한다.

어려운 정의

내적공간 $X = \mathbb{R}^{p}$ 와 라벨링^labeling $Y = \left\{ -1, +1 \right\}$ 에 대해 $n$ 개의 데이터를 모아놓은 학습 데이터셋^{training Dataset}을 $D = \left\{ \left( \mathbf{x}_{k} , y_{k} \right) \right\}_{k=1}^{n} \subset X \times Y$ 라 두고, $$ \begin{align*} X^{+} :=& \left\{ \mathbf{x}_{k} \in X : y_{k} = +1 \right\} \\ X^{-} :=& \left\{ \mathbf{x}_{k} \in X : y_{k} = -1 \right\} \end{align*} $$

라 하자. 어떤 웨이트^weight $\mathbf{w} \in \mathbb{R}^{p}$ 와 바이어스^bias $b \in \mathbb{R}$ 를 가지는 선형함수 $f \left( \mathbf{x} \right) = \mathbf{w}^{T} \mathbf{x} + b$ 로 만들어지는 초평면을 $H : \mathbf{w}^{T} \mathbf{x} + b = 0$ 라 할 때, $H$ 와 가장 거리가 가까운 $\mathbf{x}^{+} \in X^{+}$ 들과 $\mathbf{x}^{-} \in X^{-}$ 들을 서포트 벡터^{support Vector}라 하고, 이들 사이의 거리 $\delta$ 를 마진^margin이라 한다. 이에 대해 $$ \begin{align*} f \left( \mathbf{x}^{+} \right) =& +1 \\ f \left( \mathbf{x}^{-} \right) =& -1 \end{align*} $$

을 만족하면서 마진이 가장 커지도록 하는 $\mathbf{w} , b$ 를 찾는 머신러닝 기법을 서포트 벡터 머신^{sVM, Support Vector Machine}이라한다.

---

• $\mathbb{R}$ 은 실수의 집합으로, $\mathbb{R}^{p}$ 는 $p$차원 유클리드 공간이다.
• $X \times Y$ 는 두 집합의 데카르트 곱을 의미한다.
• $\mathbf{w}^{T}$ 은 $\mathbf{w}$ 의 전치행렬로, $\mathbf{w}^{T} \mathbf{x}$ 는 두 벡터 $\mathbf{w}, \mathbf{x}$ 의 내적 $\left< \mathbf{w} , \mathbf{x} \right>$ 이다.

설명

쉽게 말해서 다음 그림처럼 주황색과 하늘색 데이터를 양분하는 선이나 평면을 찾는 것이다. 평면 그림에서 빨간 화살표로 표시해놓은 것이 바로 서포트 벡터에 해당한다.

그림에서는 $2$차원이니까 선을 찾았고 $3$차원이니까 평면을 찾았지만 더 큰 $p$차원이 된다면 초평면을 찾아야하고, 그림으로 나타내기는 좀 어려워진다. 그래도 이렇게 공간을 둘로 자른다는 점은 달라지지 않는다. 학습 데이터셋으로 이진분류가 끝났다면 새로운 데이터를 받았을 때도 $f$ 에 집어넣어서 선형분류기^{linear Classifier}로 쓰면 된다.

당연하지만 똑같이 데이터를 이진분류하더라도 왼쪽이 오른쪽보다 더 좋은데, 오른쪽의 경우 하늘색 데이터에 대한 마진이 지나치다. 구체적으로 이를 구하는 방법은 어차피 패키지가 알아서 다 해주기 때문에 몰라도 된다.

학부생 수준이라면 딱 여기까지, 쉬운 정의만 받아들이고 그림으로 대강 이해하기만 해도 앞으로 직접 사용하거나 용어를 알아듣는데에는 크게 문제 없다. 이보다 살짝 더 어려운 내용, 실전압축 요점정리, 파이썬 예제코드 등은 국내 웹에서만해도 잘 정리된 문서가 한 트럭은 된다^{2 3}. ⁴

내적공간

보다시피 SVM 자체는 개념적으로 별로 어렵지도 않지만, 굳이 수학적 정의를 끌어오고 수식을 적어놓은 이유는 이후 구체적으로, 이론적으로 이야기할 것이 많기 때문이다.

유클리드 공간 $\mathbb{R}^{p}$ 은 당연히 벡터공간이고, 내적공간이며 내적공간은 거리공간이므로 거리공간이기도 하다. 이를 강조하는 것은 실제 데이터의 세계에서 내적공간이라는 것이 생각보다 꽤 좋은 가정이기 때문인데, 당장 이미지라든가 문서, 분자구조라고만 해도 이를 무작정 SVM에 집어넣어도 되는지 골치가 아파온다. 정의에서는 은연중에 ‘거리가 가까운’이라든가 벡터의 내적이 포함된 선형함수 $f$ 를 사용하고 있는데, 이론에 가까울수록 이런 가정들을 당연하게 여기면 안 된다.

서포트 벡터

원래 이런 기하문제에서는 테두리^boundary에 있는 걸 서포트라 부르는데, 예를 들어 최소내포디스크 문제에서도 원을 결정하게끔 하는 원둘레 위의 점들을 서포트라 한다. SVM의 어원이 된 서포트 벡터 역시 마찬가지로, $\mathbf{x}^{+}, \mathbf{x}^{-}$ 는 두 집합 $X^{+}, X^{-}$ 의 입장에서 보나 $\delta/2$ 만큼 떨어져있는 경계에 위치하고 있다.

서포트 벡터가 $X^{+}, X^{-}$ 각각에서 유일하다는 보장은 없지만, 앞으로 이어지는 논의에서 유일성이 중요하지는 않기 때문에 일반성을 잃지 않고 유일하다고 가정하자. $H$ 의 마진에는 데이터가 존재하지 않고, $$ f \left( \mathbf{x} \right) \begin{cases} \ge +1 & , \text{if } \mathbf{x} \in X^{+} \\ \le -1 & , \text{if } \mathbf{x} \in X^{-} \end{cases} $$ 이므로 모든 $\left\{ \mathbf{x}_{k} \right\}_{k=1}^{n}$ 들에 대해 $\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1$ 이어야 한다.

마진의 최대화

서포트 벡터는 $H$ 와 가장 가까운 점이므로 $H$ 와의 거리 $\delta/2$ 는 서포트 벡터가 $H$ 에 수직인 $\mathbf{w}$ 방향으로 떨어질 때의 거리일 것이다. 이 마진은 $\mathbf{x}^{+}$ 든 $\mathbf{x}^{-}$ 이든 같고, 둘 다 초평면 $H$ 와의 거리가 $\delta/2$ 라는 것은 두 서포트 벡터 사이의 거리가 $$ \delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-} $$ 와 같이 나타난다는 것이다. 여기서 $\mathbf{x}^{+} - \mathbf{x}^{-}$ 와 같은 연산은 $X$ 가 벡터공간이라는 가정에 따라 허용된다. $\delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-}$ 의 양변을 $\mathbf{w}$ 과 내적하면, 다시 말해 $\mathbf{w}^{T}$ 를 왼쪽에 곱하면 $f$ 의 정의에 따라 $$ \begin{align*} & \delta \mathbf{w} = \mathbf{x}^{+} - \mathbf{x}^{-} \\ \implies & \delta \mathbf{w}^{T} \mathbf{w} = \mathbf{w}^{T} \mathbf{x}^{+} - \mathbf{w}^{T} \mathbf{x}^{-} \\ \implies & \delta \left\| \mathbf{w} \right\|_{2}^{2} = \left( \mathbf{w}^{T} \mathbf{x}^{+} + b \right) - \left( \mathbf{w}^{T} \mathbf{x}^{-} + b \right) \\ \implies & \delta \left\| \mathbf{w} \right\|_{2}^{2} = +1 - (-1) \\ \implies & \delta \left\| \mathbf{w} \right\|_{2}^{2} = 2 \\ \implies & \delta = {{ 2 } \over { \left\| \mathbf{w} \right\|_{2}^{2} }} \end{align*} $$ 를 얻는다. 즉 마진을 최대화하는 것은 목적 함수 $\left\| \mathbf{w} \right\|_{2}^{2} / 2$ 를 최소화하는 것이고, 정리하자면 SVM이란 다음과 같은 최적화 문제를 푸는 최적화기^optimizer다. $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 \end{matrix} \\ k = 1, \cdots , n $$

파생모델

어려운 정의에 따르면 SVM은 직선이든 초평면이든 어쨌든 선형함수를 찾으므로 선형회귀모델인데, 당연히 여기서 만족할 리가 없다.

소프트 마진 SVM

가령 다음과 같은 데이터가 들어왔다고 생각해보면 SVM은 데이터가 섞여있는 가운데 부분 때문에 이를 완벽하게 이진분류 해낼 수 없다.

여기서 서포트 벡터의 마진에 데이터가 존재할 수 없다는 제약 하에서 $\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1$ 라는 조건을 만족시켜야 했음에 주목해보자. 이 부등식을 $1$ 보다 작은 값으로 허용해준다면 완벽한 이진분류는 아니라도 아예 포기하는 것보단 나은 결과를 줄 것이고, 그 허용을 각 데이터별로 $\xi_{k} \ge 0$ 라 둔다면 새로운 제약조건 $\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k}$ 를 얻는다. 이렇게 조건이 약화된 마진을 소프트 마진^{soft Margin}이라 한다.

물론 제약이 조금 느슨해지긴 했지만 그렇다고 죄다 $\xi_{l} = \cdots = \xi_{n} = 1$ 로 풀어버리면 SVM 자체를 포기하게 된다. 이를 방지하기 위해서는 목적 함수에 $\sum_{k} \xi_{k}$ 와 같은 항을 넣는 수가 있다. 이는 불가능한 이진분류를 가능하게 만든 것에 대한 대가^penalty다. 물론 이렇게 단순한 페널티는 데이터의 스케일에 따라 전혀 의미가 없거나 너무 민감할 수 있으니 $0 \le \sum_{k} \xi_{k} \le n$ 그대로 쓰는 게 아니라 적당한 양수 $\lambda > 0$ 를 곱해서 추가해보자. $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} + \lambda \sum_{k=1}^{n} \xi_{k} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 - \xi_{k} \\ & \xi_{k} \ge 0 \end{matrix} \\ k = 1, \cdots , n $$

커널 트릭

가령 위와 같은 데이터가 주어져 있다면 소프트마진이고 뭐고 SVM으로는 절대로 이진분류를 할 수 없을 것 같다. 그런데 잘 보면 $0$에 가까운 쪽에 하늘색 점들이 모여있고 바깥쪽에 주황색점들이 나타나 있음이 명백하다. 이러한 정보를 써먹기 위해 다음과 같이 $z$-축을 새로이 만들어보자. $$ \phi (x,y) := (x,y, x^{2} + y^{2}) $$

위 그림은 아래 그림을 적절히 캡쳐한 것이다. 아래는 마우스로 상호작용할 수 있는 3D 공간이니 이리저리 돌려가며 살펴보아라.

원래 $\mathbb{R}^{2}$ 에서 데이터를 양분할 직선은 찾기 곤란했지만, 이렇게 데이터를 설명하는 차원을 늘린 $\mathbb{R}^{3}$ 에서는 적당한 평면으로 데이터를 분류하는 SVM을 사용할 수 있게 되었다. 이쯤에서 자연스레 떠오르는 질문은 ‘그럼 이렇게 좋은 변환 $\phi$ 을 커널^kernel이라고 부르고, 커널을 쓰는 방법을 커널 트릭^{kernel Trick}이라 부르는건가?‘일 것이다. 반은 맞고 반은 틀렸다. $\phi$ 에 한 단계 더, 내적까지 들어간 것이 커널이다.

다시 마진의 최대화로 돌아가서, 우리에게 주어진 최적화 문제를 다시 살펴보자. $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} \\ \text{subject to} & \left| f \left( \mathbf{x}_{k} \right) \right| \ge 1 \end{matrix} \\ k = 1, \cdots , n $$

제약조건 $\left| f \left( \mathbf{x}_{k} \right) \right| \ge 1$ 이 보기에는 깔끔하지만 사실 이 문제를 풀 때는 별로 도움이 되질 않는다. 원래 학습 데이터셋에서의 꼴로 바꿔보면 $k = 1 , \cdots , n$ 에 대해 $$ \begin{cases} f \left( \mathbf{x}_{k} \right) \ge 1 & , \text{if } y_{k} = 1 \\ f \left( \mathbf{x}_{k} \right) \le -1 & , \text{if } y_{k} = -1 \end{cases} \\ \implies \begin{cases} y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) \ge 1 & , \text{if } y_{k} = 1 \\ y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) \ge 1 & , \text{if } y_{k} = -1 \end{cases} \\ \implies y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) \ge 1 $$ 이어야한다. 이러한 제약조건 자체를 목적 함수에 반영시켜 제약조건이 없는 것처럼 다루는 방법이 라그랑주 승수법이다. $y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \ge 0$ 에 $\alpha_{k} \ge 0$ 을 곱한 항들을 원래의 목적 함수에서 뺀 $L(\mathbf{w}, b)$ 에 대해 다음의 최적화 문제를 얻는다. $$ \begin{matrix} \text{Minimize} & {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} - \sum_{k=1}^{n} \alpha_{k} \left[ y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \right] \\ \text{subject to} & \alpha_{k} \ge 0 \end{matrix} \\ k = 1, \cdots , n $$

다시 한 번 상기시키자면 우리는 이 목적 함수를 최소화하는 $\mathbf{w}, b$ 를 찾는 것이 목적이었다. $\mathbf{w}, b$ 에 대한 목적 함수의 편미분이 $0$ 이 되도록 하는 조건은 다음과 같다. $$ \begin{align*} {{ \partial L } \over { \partial \mathbf{w} }} = 0 \implies & \mathbf{w} = \sum_{k=1}^{n} \alpha_{k} y_{k} \mathbf{x}_{k} \\ {{ \partial L } \over { \partial b }} = 0 \implies & 0 = \sum_{k=1}^{n} \alpha_{k} y_{k} \end{align*} $$

이걸 이제 그대로 $L$ 에 대입해보면 $$ \begin{align*} & L(\mathbf{w},b) \\ =& {{ 1 } \over { 2 }} \left\| \mathbf{w} \right\|_{2}^{2} - \sum_{k=1}^{n} \alpha_{k} \left[ y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) - 1 \right] \\ =& {{ 1 } \over { 2 }} \mathbf{w}^{T} \mathbf{w} - \sum_{k=1}^{n} \alpha_{k} y_{k} \left( \mathbf{w}^{T} \mathbf{x}_{k} + b \right) + \sum_{k=1}^{n} \alpha_{k} \\ =& {{ 1 } \over { 2 }} \mathbf{w}^{T} \sum_{k=1}^{n} \alpha_{k} y_{k} \mathbf{x}_{k} - \sum_{k=1}^{n} \alpha_{k} y_{k}\mathbf{w}^{T} \mathbf{x}_{k} - b \sum_{k=1}^{n} \alpha_{k} y_{k} - \sum_{k=1}^{n} \alpha_{k} \\ =& - {{ 1 } \over { 2 }} \sum_{k=1}^{n} \alpha_{k} y_{k} \mathbf{w}^{T} \mathbf{x}_{k} - b \cdot 0 + \sum_{k=1}^{n} \alpha_{k} \\ =& \sum_{k=1}^{n} \alpha_{k} - {{ 1 } \over { 2 }} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} y_{i} a_{j} y_{j} \mathbf{x}_{i}^{T} \mathbf{x}_{j} \\ =& \sum_{k=1}^{n} \alpha_{k} - {{ 1 } \over { 2 }} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} a_{j} y_{i} y_{j} \mathbf{x}_{i}^{T} \mathbf{x}_{j} \\ =& L \left( \alpha_{1} , \cdots , \alpha_{n} \right) \end{align*} $$

을 얻는다. 당연하다면 당연하지만, 결국 구체적인 $\mathbf{w}$ 와 $b$ 를 계산하기 위해선 학습데이터 $\left\{ \left( \mathbf{x}_{k}, y_{k} \right) \right\}_{k=1}^{n}$ 가 필요한 것이다.

여기서 주목할 점은 수식에서 $\mathbf{x}_{i}$ 와 $\mathbf{x}_{j}$ 의 내적이 쓰였다는 것이다. 끝끝내, 결국에, 우리는 내적을 해야만 하며 $X$ 가 내적공간이 아니라면 이렇게 순탄한 길을 수 있다는 보장이 없다. 반대로 말해, $X$ 가 내적공간이 아니라도 변환 $\phi$ 이 $X$ 를 내적공간으로 보내줄 수만 있다면 그 목적 함수가 $$ \sum_{k=1}^{n} \alpha_{k} - {{ 1 } \over { 2 }} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} a_{j} y_{i} y_{j} \phi \left( \mathbf{x}_{i} \right) ^{T} \phi \left( \mathbf{x}_{j} \right) $$ 인 SVM을 고려해봄직하다. 머신러닝에서는 이렇듯 두 벡터에 대한 변환, 내적까지 들어간 함수 $$ K \left( \mathbf{x}_{i}, \mathbf{x}_{j} \right) := \left< \phi \left( \mathbf{x}_{i} \right) , \phi \left( \mathbf{x}_{j} \right) \right> $$ 를 커널^kernel이라 부를 때도 있다. [ NOTE: 데이터 과학에서만 해도 이것과 혼동되는 다른 커널도 있다. 원래 수학 전반에서의 커널은 이름만 같고 전혀 다른 기능의 함수다. ]

수식적으로 여기까지의 내용을 받아들일 수 있다면 이제 왜 커널도 아닌 변환 $\phi$ 를 도입하는 것을 커널 트릭이라고 부르며, 변환 이후에 내적공간임이 보장되는 게 중요한지 이해한 것이다.

참고로 몇가지 조건을 만족하는 한 커널은 여러 종류를 생각할 수 있다. 특히 원래의 SVM 역시 선형커널^{linear Kernel} $$ K \left( \mathbf{x}_{i}, \mathbf{x}_{j} \right) = \left< \mathbf{x}_{i}, \mathbf{x}_{j} \right>^{1} = \mathbf{x}_{i}^{T} \mathbf{x}_{j} $$ 을 쓴 것으로 볼 수도 있다.

같이보기

커널 트릭 파트에서 수학적으로 간단한 내용을 다루었는데, 더 깊은 이론에 관심이 있다면 SVM을 넘어 다음의 내용을 공부해보자.

• 머신러닝에서의 커널과 재생 커널 힐베르트 공간
• 표현자 정리 증명

코드

다음은 커널 트릭을 구현한 줄리아 코드다.

struct Sphere
    d::Int64
end
Sphere(d) = Sphere(d)

import Base.rand
function rand(Topology::Sphere, n::Int64)
    direction = randn(Topology.d, n)
    boundary = direction ./ sqrt.(sum(abs2, direction, dims = 1))
    return boundary
end

using Plots
A = 0.3rand(Sphere(2), 200) + 0.1randn(2, 200)
B = rand(Sphere(2), 200) + 0.1randn(2, 200)

scatter(A[1,:],A[2,:], ratio = :equal, label = "+1")
scatter!(B[1,:],B[2,:], ratio = :equal, label = "-1")
png("raw.png")

Plots.plotly()
ϕ(z) = z[1]^2 + z[2]^2
scatter(A[1,:],A[2,:],ϕ.(eachcol(A)), ms = 1, label = "+1")
scatter!(B[1,:],B[2,:],ϕ.(eachcol(B)), ms = 1, label = "-1")
savefig("kernel.html")