5. SVM

신경망을 포함하여 기존의 방법들은 오류율을 최소화하려는 목적으로 설계되었다. 하지만 SVM은 두 부류 사이에 존재하는 여백(margin)을 최대화 하여 일반화 능력을 극대화시키는 개념을 사용한다. SVM은 일반화 측면에서 다른 분류기와 비교하면 대응하거나 우수한 것으로 알려져있다.

5.1 발상

신경망 학습 알고리즘은 초기값에서 출발하여 결정 직선을 이동하며 오류를 줄여가는 과정을 반복한다. 그러다가 오류가 0을 가지게 되면 멈춘다. 오류가 0인 결정 직선이 여러개가 존재할 수 있으나 훈련 집합의 관점에서는 모두 같은 성능의 분류기이다. 하지만 미지의 패턴을 얼마나 잘 분리하느냐를 따지는 일반화(generalization) 능력 측면에서 보면 이들의 성능은 같지 않다.

만약 결정 직선이 두 부류 모두에 대하여 여백(margin)이 크다면 웬만한 변형은 오분류로 이어지지 않을 것이다. 이 여백이라는 개념을 어떻게 공식화할 것인가? 이러한 관점에서 보는 방법이 SVM이다. SVM은 기본적으로 이진 분류기이므로 M 부류 문제에 적용하려면 확장하여야 한다.

5.2 선형 SVM

이진 분류를 위한 결정 초평면(decision hyperplane)은 아래와 같이 표현할 수 있다.

$$d(x) = w^T x + b = 0$$

이 초평면은 SVM을 유도하는데 도움이 되는 몇 가지 수학적 특성을 갖는다.

1. $ d(x) $는 전체 특징 공간을 두 영역으로 분리하여 한 쪽 영역에 속하는 점 x는 $ d(x) \gt 0 $ 이고 다른 쪽에 있는 점은 $ d(x) \lt 0 $ 이다.
2. 하나의 초평면을 표현하는 식을 여러가지라, 위 식에서 0이 아닌 임의의 상수 c를 곱하여도 같은 초평면을 나타낸다.
3. w는 초평면의 법선 벡터(normal vector)로서 초평면의 방향을 나타내고 b는 위치를 나타낸다.
4. 임의의 점 x에서 초평면까지의 거리는 $ h = \frac{|d(x)|}{||w||} $이다.

5.2.1 선형 분리 가능한 상황

선형 분리가 가능한 상황과 어느 한 결정 직선 w를 이미 계산하였다고 생각하여보자. w를 고정한 상태에서 b를 변화시키면 그에 따라 직선의 위치가 변한다. 이 때, 두 부류에 대해 직선으로부터 가장 가까운 샘플까지의 거리가 같게 되는 지점의 b를 결정할 수 있다. 이 때의 결정 직선의 여백(margin)은 직선으로부터 가장 가까운 샘플까지의 거리의 두배로 정의한다. 결정 직선에서 양 부류까지의 여백까지의 영역을 분할 때(separation band)라 부른다.

SVM을 구하기 위해서는 바로 이러한 결정 직선, 여백을 가장 크게 하는 결정 초평면의 방향 w를 찾는 문제를 풀어야 한다.

두 두류에 대해 결정 직선으로부터 가장 가까운 샘플들은 결정 직선을 정의하는데 중요한 역할을 하는데 이들 샘플을 서포트 벡터(support vector)라 부른다. 결정 직선 특성상 w와 b에 상수 c를 곱해도 같은 초평면을 나타내므로, 서포트 벡터에 대하여 $ |d(x)| = 1 $이 되도록 적당한 c를 곱한다면 여백은 다음과 같다.

$$\text{margin} = 2h = \frac{2|d(x)|}{||w||} = \frac{2}{||w||}$$

이제 훈련 집합을 $ X = \{ (x_1, t_1), (x_N, t_N) \} $로 표시하자. t는 부류를 표시하는데 $w_1$에 속하면 1, $ w_2$에 속하면 -1의 값을 갖는다. 이제 모든 샘플을 옳게 분류한다는 조건을 이용하여 조건부 최적화 문제(constrained optimization problem)를 이용하여 결정 초평면을 계산할 수 있다.

$$\arg \max_{w, b} \frac{2}{||w||} = w^T x_i + b \geq 1, \forall x_i \in w_1 \\ w^T x_i + b \ leq -1, \forall x_i \in w_2$$

여기서 조건식의 등호가 성립하는 샘플이 바로 서포트 벡터이다.

$ 1 / ||w|| $의 최대화는 $ ||w||^2 $의 최소화와 같다는 성질을 이용하여 위 식을 변형하여 최소화 문제로 바꾸어 쓸 수 있다.

$$\arg \min J(w) = \frac{1}{2} ||w||^2 = t_i(w^T x_i + b) - 1 \geq 0, i = 1, \dots, N$$

이렇게 변형한 식의 성질을 살펴보자. 먼저 위 식의 목적 함수는 w의 2차 항만을 가지므로 볼록(convex) 함수이다. 또한 N개의 조건 식이 모두 선형이므로 이를 모두 만족하는 영역은 볼록이 된다. 따라서 이 식의 해는 유일하며 전역 최적 점이다. 이 성질은 SVM의 큰 장점이다.

이러한 종류의 조건부 최적화 문제는 라그랑제 승수(Lagrange multiplier)를 이용하여 해결한다. 이 방법은 조건식마다 라그랑제 승수 $ \alpha_i $를 부여한다. 이들의 벡터를 $ \alpha = ( \alpha_1, \dots, \alpha_N) ^T $으로 표현하자. 이제 위 수식의 라그랑제 함수 L은 다음과 같이 정의된다.

$$L(w, b, \alpha) = \frac{1}{2} ||w||^2 - \sum^N_{i=1} \alpha_i (t_i(w^T x_i + b) - 1)$$

라그랑제 함수로 표현한 조건부 최적화 문제는 보통 Karush-Kuhn-Tucker (KKT) 조건을 이용하여 푼다. 이 조건은 아래와 같다.

$$\frac{\partial L(w, b, \alpha)}{\partial w} = 0 \rightarrow w = \sum_{i=1}^N \alpha_i t_i x_i$$

$$\frac{\partial L(w, b, \alpha)}{\partial b} = 0 \rightarrow \sum_{i=1}^N \alpha_i t_i = 0$$

$$\alpha_i \geq 0, i=1, \dots, N$$

$$\alpha_i(t_i (w^T x_i + b) -1) = 0, i=1, \dots, N$$

성질을 살펴보자.

1. 네번째 식에서 모든 샘플에 대해 $\alpha_i = 0 $이거나 $ t_i (w^T x_i + b) -1 = 0 $이어야 한다. 만약 $ \alpha_i \neq 0 $이라면 $ t_i (w^T x_i + b) -1 = 1 $이어야 하는데, 이들이 바로 서포트 벡터이다.
2. 첫번째 식에서 결정 초평면의 매개 변수 w를 구할 수 있다. $t_i, x_i$는 이미 훈련 집합으로 주어진 것이기에 라그랑제 승수만 알게 된다면 결정 초평면을 구할 수 있다. 이제 w대신 라그랑제 승수만 구하는 문제로 쉽게 변화하게 되었다.
3. 네번째 식으로 b를 구할 수 있다. w를 구하게 되면 미지수는 b뿐이므로 쉽게 계산이 가능하다.

볼록 성질을 만족하는 조건부 최적화 문제는 Wolfe 듀얼(dual) 문제로 변형할 수 있다. 이에 따라 식을 바꾸어 쓰면 아래 식으로 변화한다.

$$w = \sum_{i=1}^N \alpha_i t_i x_i$$

$$\sum_{i=1}^N \alpha_i t_i = 0$$

$$\alpha_i \geq 0, i=1, \dots, N$$

위의 세식의 조건 하에 $L(w, b, \alpha) $를 최대화하라.

첫번째 식과 두번째 식을 라그랑제 수식에 대입하면 w와 b를 제거할 수 있고, 결국 라그랑제 승수 $ \alpha $만이 남게 된다. 이 식을 $ \tilde{L}(\alpha) $로 표기하자. 새로운 목적함수를 이용하여 라그랑제 수식을 다시 쓰면 다음과 같다.

$$\sum_{t=1}^N \alpha_i t_i = 0$$

$$\alpha_i \geq 0, i=1,\dots,N$$

의 조건 하에 다음을 최대화하라.

$$\tilde{L}(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha-j t_i t_j x_i^T x_j$$

이 식은 다음과 같은 성질이 있다.

1. 한개의 등식 조건과 N개의 부등식 조건을 가진 2차(quadratic) 목적 함수의 최대화 문제이다.
2. w와 b가 사라지고 라그랑제 승수 $\alpha $를 구하는 문제가 되엇다.
3. 특징 벡터 $ x_i $는 혼자 나타나지 않고 두 개의 특징벡터의 내적 $ x_i^T x_j $로 나타난다.
4. 이중 $\sum$을 가지고 있어 풀어쓰면 $N^2 $의 항이 되어 많은 항을 가진 함수가 된다.

많은 항을 가진 함수를 어떻게 풀지는 잠시 미뤄두고, 선형 불가능한 상황을 생각하여 보자.

5.2.2 선형 분리 불가능한 상황

샘플의 선형 분리가 불가능항 상황이 존재할 수도 있다. 그럴 때에는 분할 때의 내부에 샘플이 존재하도록 허락하는 수밖에 없다. 이제 샘플은 세 가지 경우 중 하나일 것이다.

1. 분할 띠의 바깥에 있다. $ 1 \leq t(w^T x + b) $
2. 분할 띠의 안쪽에 있고 자기가 속한 부류의 영역에 있다. $ 0 \leq t(w^T x + b) $
3. 결정 경계를 넘어 자신이 속하지 않은 부류의 영역에 놓여있다. $ 0 \gt t(w^T x + b) $

이제 새로운 변수 $ \xi $를 도입하여 세가지 경우를 식으로 표현하여 보자.

$$t(w^T x + b ) \geq 1 - \xi$$

여기서 $ \xi $ 는 슬랙 변수(slack variable)이라고 부르며, 위에서 언급한 경우에 따라 $ \xi = 0, 0 \lt \xi \leq 1, 1 \lt \xi $ 의 값을 가진다.

이제 풀어야 하는 문제는,

1. 여백을 될 수 있는 한 크게 하며,
2. 동시에 $ 0 \lt \xi $인 샘플의 수를 가능한 적게 하는,

초평면 w를 찾는 문제로 변한다. 두 목적은 길항(tradeoff) 관계를 갖는다.

이를 풀기 위해 우선 목적 함수를 다시 써보자.

$$J(w, \xi) = \frac{1}{2} ||w ||^2 + C \sum_{i=1}^N \xi_i$$

C는 두 가지 목적 중 어 것에 비중을 둘지를 결정하는 매개 변수로 양수이며 사용자가 설정해야하는 값이다. 이제 조건부 최적화 문제로 정리를 해보자.

$$t_i (w^T x_i + b) \geq 1- \xi_i, i=1,\dots,N$$

$$\xi \geq 0, i=1, \dots, N$$

의 조건에서 $ J(w, \xi) $를 최소화하여야 한다. 앞에서와 마찬가지로 라그랑제 함수를 정의해보면 아래와 같다.

$$L(w, b, \xi, \alpha, \beta) = J(w, \xi) - (\sum_{i=1}^N \alpha_i (t_i (w^T x_i + b) - 1 + \xi_i) + \sum_{i=1}^N \beta_i \xi_i)$$

KKT를 적용하면 아래와 같이 변환된다.

$$w = \sum_{i=1}^N \alpha_i t_i x_i$$

$$\sum_{i=1}^N \alpha_i t_i = 0$$

$$C = \alpha_i + \beta_i$$

$$\alpha_i \geq 0$$

$$\beta_i \geq 0$$

의 조건 에서 $L(w,b,\xi,\alpha,\beta)$ 를 최대화 하라.

수식을 유도하여보면 결국 선형분리 가능한 경우의 수식 조건의 $ 0 \leq \alpha_i $에서 $ 0 \leq \alpha_i \leq C $로 바뀐 것을 제외하는 완전히 같다.

5.3 비선형 SVM

실제 세계에서는 선형 분류기로 높은 성능을 얻기가 힘들다. 이제 선형 SVM을 비선형 SVM (nonlinear SVM)으로 확장하여 보자.

5.3.1 커널 대치

원래 특징 공간 L 에서는 선형 분리가 가능하지 않으나 이를 더 높은 차원 H로 매핑하면 선형 분리가 가능하게 만들 수 있다.

$$\Phi : L \rightarrow H$$

이러한 함수 $\Phi $를 매핑함수라고 한다. SVM에서는 특징벡터가 내적의 형태 $x^T_i x_j $로 나타나는데 여기에 매핑함수를 적용하면 $ \Phi(x_i) \cdot \Phi(x_j) $로 나타낼 수 있다. 그리고 이를 하나의 수식으로 $ K(x_i, x_j ) $로 나타내고, 커널 함수라고 한다. 결국 두 매핑함수의 내적으로 나타낼 수 있는 것이다.

이러한 성질을 갖는 커널 함수 $ K $를 수식에 적용하면 고차원 $ \Phi $에서 직접 작업하는 일 없이, 낮은 차원의 L공간에서 K함수의 계산만으로 고차원에서의 그것과 같은 결과를 얻을 수 있다. 이를 커널 대치(kernel subsitution), 커널 트릭(kernel trick)이라고 한다.

커널 대치 방법은 SVM 뿐만 아니라 PCA, Fisher LD 등의 방법에도 많이 활용된다.

5.3.2 커널 대치를 이용한 비선형 SVM

매핑 함수를 적용한 목적 함수를 나타내어보자.

$$\hat{L}(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j t_i t_j \Phi(x_i)^T \Phi(x_j)$$

여기에 커널 트릭을 적용하면,

$$\hat{L}(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j t_i t_j K(x_i, x_j)$$

와 같아진다. 나머지는 선형 SVM과 같은 방법을 사용하면 된다.

SVM이 사용하는 대표적인 커널 함수는 다음의 것들이 있다.

• 다항식 커널 : $ K(x, y) = (x \cdot y + 1)^p $
• RBF(Radial Basis Function) 커널 : $K(x,y) = e^{-|| x - y ||^2 /2 \sigma^2} $
• 하이퍼볼릭 탄젠트 커널 : $ K(x,y) = \tanh(\alpha x \cdot y + \beta ) $

실제로는 매핑함수를 모르더라도, 어떠한 매핑함수가 존재한다는 커널 함수만 정의할 수 있으면 그 커널을 사용할 수 있다.

5.4 구현

5.4.1 학습

라그랑제 승수는 샘플마다 하나씩 있으므로, N개의 샘플에 해당하는 승수를 구하여야 하며, 목적함수는 총 $(N^2+N)/2$개의 항을 가진 매우 복잡한 수식을 갖는다. 따라서 N이 매우 작을 때는 제외하고는 수치적으로 풀어내는 것이 일반적이다.

개략적인 알고리즘은 다음과 같다.

1. 라그랑제 승수를 초기화한다.
2. 최적화 조건이 만족할 때 까지 3 ~ 6을 반복한다.
3. Y에 속할 q개의 라그랑제 승수를 선택한다. 나머지는 Z에 속한다.
4. $ \alpha_i \in Z $는 상수, $ \alpha_i \in Y $는 변수로 간주한다.
5. 조건부 최적화 문제를 분해한다.
6. 분해된 문제를 풀고 $ \alpha_i \in Y $를 새로운 값으로 변경한다.

여기서 Y는 라그랑제 승수가 활성화되는 집합, Z는 비활성화되는 집합이다. 이 방법에서 q를 얼마로 할 것인지, 그리고 Y를 어떻게 선택할 것인지를 결정하여야 한다. 또한 분해된 문제를 푸는 방법과 최적화 조건이 만족되었는지를 판단하는 기준 또한 있어야 한다. 가장 널리 알려진 알고리즘은 SMO(Sequential Minimal Optimization)이다.

5.4.2 인식

미지의 패턴 x에 대하여 SVM을 분류하려면 w와 b를 계산하여야 한다. 이것은 서포트 벡터로 계산할 수 있는데, 앞에서 Y에 속하는 샘플의 집합이 서포트 벡터이다. 서포트 벡터를 제외하고는 $\alpha_i=0$이 기 때문에 계산은 서포트 벡터인 샘플만으로 쉽게 이루어진다. b의 경우 수학적으로는 하나의 서포트 벡터만으로도 계산이 가능하나, 정확도를 위해 모든 서포트 벡터의 평균을 취한다. w와 b는 미리 계산을 해 둘 수 있는 장점이 있다.

5.4.3 M 부류 SVM

SVM은 이진 분류기로 2 부류 분류를 해결할 수 있다. M 부류에 적용하는 방법은 크게 1 대 M-1, 1 대 1 방법으로 나눌 수 있다.

1 대 M-1방법에서는 각 부류에 대하여 M개의 이진 분류기를 만들어 그 부류와 나머지 모든 부류를 구분하는 분류기를 훈련하여 해결한다. M개의 독립적인 분류기가 존재하므로 그들이 $d_j(x) $이 갖는 값의 크기가 서로 다른 규모를 가질 수 있다. 따라서 가장 큰 값을 갖는 부류를 선택하는 것이 문제가 될 수 있다. 또한 훈련 집합이 불균형을 이루는 문제 또한 포함한다.

1 대 1 방법은, 모든 부류에 대하여 부류 쌍을 분류하는 이진 분류기를 M(M-1)/2 개 만드는 방법이다. 샘플을 모든 분류기에 적용하여 가장 많이 선택된 부류로 분류하면 된다. M-1이 방법의 단점을 가지지 않지만 이진 분류기 수가 많아 학습, 인식에 시간이 많이 걸리는 단점이 있다.

5.5 SVM의 특성

1. 사용자가 설정해야 하는 매개 변수가 적다. 커널의 종류를 제외하면 C가 전부이다.
2. 하지만 최적의 커널을 자동으로 선택하는 알고리즘은 없다.
3. 일반화 능력이 뛰어나다.
4. 비선형 SVM에서는 인식 시간이 서포트 벡터의 수에 비례하므로 많은 수의 서포트 벡터가 나타나면 시간이 길어질 수 있다.
5. 많은 공개 소스 소프트웨어가 있다.

---