[Artificial Intelligence / Machine Learning] Support Vector Machine - Theory

이번 글에서는 Support Vector Machine(이하 SVM)의 개념과 간단한 이론에 대해 이해하고자 한다.

1. SVM의 개념

SVM의 개념은 매우 간단한데, 특징에 따라 서로 유사한 그룹끼리 칸막이를 쳐서 나누는 것이다.

이 칸막이를 초평면(Hyperplane)이라고 부른다.

SVM의 기초가 되는 수학적 이론은 수십년에 걸쳐 정리가 되었지만, 최근이 되어서야 주목을 받게 되었는데, 그 이유는 첫번째로 성능이 월등히 개선되었고, 이에 따라 여러 프로그래밍 언어를 지원하는 잘 정돈된 라이브러리가 등장했기 때문이다.

SVM은 분류 및 수치 예측 등 거의 모든 학습 문제에 잘 대처할 수 있는데 특히 알고리즘의 성공적인 열쇠가 되는 것은 패턴 인식이다.

주목할 만한 응용분야는 다음과 같다:

• 바이오인포매틱스 분야에서 암 또는 유전병을 진단하기 위한 유전자 표현 데이터의 분류

• 문서에 사용된 언어 식별과 같은 문자 분류 또는 주제별 문서 분류

• 비행기 엔진의 결함, 보안 균열, 지진 등과 같은 잘 일어나지는 않지만 매우 중요한 이벤트 감지
  

[장점]

• 에러율이 낮다.

• 계산량이 많지 않다.

• 결과를 해석하기 용이하다.

[단점]

• 튜닝 파라미터 및 커널 선택에 민감하다.

• 선천적으로 이진 분류(Binary Classification)만 다룰 수 있다.

2. 초평면을 이용한 분류

앞서 특징이 유사한 그룹끼리 분류하는 칸막이를 초평면이라고 하였는데, 2차원 공간에 선(Line)으로 분리되거나 3차원 공간에서 평면으로 분리되는 것을 선형 분리 가능(Linearly Separable)이라고 한다.

개념의 이해를 돕기 위해 선형 분리 가능한 것을 예로 들겠지만, SVM은 선형 분리 가능이 아닌 경우에도 적용이 가능하다.

[그림 1.] 초평면의 도식화.

위의 그림과 같이 2차원에서는 초평면은 선이 되며, 3차원에서는 평면이 된다.

[그림 2.] 초평면 후보.

위의 그림과 같이 네모 그룹과 동그라미 그룹을 나누는 여러 개의 초평면에 대한 가능성이 있는데 ①, ②, ③ 중 과연 무엇으로 나눌 것인가를 고민하게 된다.

이에 대한 답을 하기 위해 최대 마진 초평면(Maximum Margin Hyperplane; MMH)이라는 연구가 있는데 이는 그룹 간의 최대 분리를 할 수 있도록 하는 것이다.

즉, 위의 이미지에서 ①, ②, ③ 모두 그룹 간 분리를 할 수 있는 선이지만 이 중 최대 마진을 형성하는 선이 새로운 개체가 들어왔을 때 가장 잘 분리할 수 있는 선이 되는 것이다.

최대 마진은 약간의 노이즈가 있더라도 점들은 경계를 벗어나지 않을 것이다.

초평면을 수학적으로 표현하면,

을 만족하는 x의 집합이며, n-차원 공간에서

,  

이다. 특히 w₀를 편향(Bias)라고 하며 이는 마치 2차원 평면 내 직선의 방정식에서 y-절편과도 같다.

초평면은 두 그룹을 나누는 기준이 되며, 초평면에 의해 나뉘어지는 두 그룹을 다음과 같이 정의할 수 있다:

[CLASS (+1)]

  

[CLASS (-1)] 

  

선형 초평면일 경우 아래 그림과 같이 Data Flow를 도식화 할 수 있다.

[그림 3.] 초평면 네트워크.

활성 함수를 Sigmoid 함수를 사용할 수 있으며 이 함수의 미분 연산을 통하여 Gradient 방법을 사용하여 가중치를 학습시킬 수 있다.

Support Vectors는 MMH에 가장 근접한 각 그룹의 개체들이다. 각 그룹은 최소 1개의 Support Vector(s)를 갖는다.

Support Vectors만으로 MMH를 정의할 수 있으며 이것이 SVM의 핵심이 되는 특징이다. 즉, Support Vectors는 각 개체가 아무리 많은 특징들을 갖고 있더라도 분류 모델을 저장하는 매우 간편한 방법이다.

아래 이미지에서 MMH는 녹색 경계선을 중심을 d_- 및 d₊ 사이의 공간이며, Support Vectors는 MMH에 상에 있는 각 그룹의 개체이다.

[그림 4.] 최대마진 초평면의 개념.

3. 선형 분리가능(Linearly Separable) 데이터

그룹을 선형 분리 가능하다고 가정할 경우, 최대 마진을 찾는 것은 수월하다. 이 경우, MMH는 두 그룹의 경계(Boundary)가 가장 멀리 떨어지도록 하며, 이 경계를 Convex Hull이라고 부른다.

이 때, MMH는 두 Convex Hull 사이의 가장 짧은 선에 대한 수직 이등분선이며, 최대 마진을 찾는 알고리즘은 2차 형식에 대한 최적화 기법(Quadratic Optimisation)을 사용한다.

[그림 5.] Convex Hull.

가장 가능성 있는 방안은 균일한 그룹으로부터 가장 멀리 떨어지도록 두 개의 칸막이(Hyperplane)를 세우는 것이다.

이 탐색 과정을 이해하려면 도대체 초평면이 어떻게 정의되는지 알아야 한다.

초평면은 간단하게는 i-번째 데이터셋 x_i에 대하여 다음 제한조건을 만족하는 가중치를 구하는 문제로 정의할 수 있다:

[Linear Program Solution]

모든 i에 대하여 y_i = +1인 w^Tx_i + w₀ ≥ 0
모든 i에 대하여 y_i = -1인 w^Tx_i + w₀ ≤ 0

만약 그룹을 분리할 수 있는 초평면을 찾는다면 선형 프로그램(Linear Program)의 해가 존재하는 것이다.

이제 최대 마진을 만족하는 초평면을 찾는 문제를 생각해 보자.

y_i ∈ {+1, -1}인 학습 데이터셋 (x_i, y_i)에 대하여 다음 조건을 만족한다고 가정하자:

(1) y_i = +1에 대하여 w^Tx_i + w₀ ≥ 1

(2) y_i = -1에 대하여 w^Tx_i + w₀ ≤ -1

위의 두 개의 부등식은 다음 식으로 합칠 수 있으며,

모든 i에 대하여 y_i(w^Tx_i +w₀) - 1 ≥ 0

다음의 등식은 두 개의 초평면을 정의한다:

(1) w^Tx_i + w₀ = 1

(2) w^Tx_i + w₀ = -1

다음과 같이 정의되는 기하학적인 마진 ρ는

ρ_{w, w0}(x, y) = y(w^Tx_i + w₀)/||w||

점 x의 초평면으로부터의 거리를 의미하며, 여기서 w는 초평면의 법선 벡터이다.

[그림 4.]에서 보는 바와 같이, 다음 식을 만족하는 점들에 대하여,

y_i(w^Tx_i + w₀₎ -1 = 0

초평면으로부터 Support Vector까지의 거리는 1/||w||이므로,

마진의 넓이는

d₊ + d_- = 2/||w||

이다. 따라서, 최대 마진을 구하려면, d₊ + d_- = 2/||w|| 을 최대화하면 되고, 이를 최대화한다는 것은 1/||w||와 동등하므로 또한 ||w||를 최소화하는 것과 동등하다.

다음과 같이 문제를 바꾸어 정의할 수 있다:

변수 w, w₀에 대하여 ||w||² / 2 = w^Tw / 2 를 최소화하라.
제한조건은 y_i(w^Tx + w₀) - 1 ≥ 0 이다.

또는 좀 더 간단하게 수학적으로 표현하면,

subject to  

와 같으며, 이 문제는 다시 다음과 같은 Lagrange 문제로 변환할 수 있다:

여기서 λ는 Lagrange Multiplier이며,  λ_i ≥ 0를 만족한다.

이 문제는 Primal 문제와 Dual 문제로 분리할 수 있으며, 각각의 문제는 다음과 같다:

Primal Problem: max J w.r.t. w, w₀

Dual Problem: max J w.r.t. λ

Lagrange Multipliers는 다음과 같은 제한조건을 만족시키도록 한다:

y_i(w^Tx + w₀) - 1 > 0 이면 λ_i → 0

y_i(w^Tx + w₀) - 1 ≤ 0 (Active Constraint) 이면 λ_i > 0

Active Constraint라는 것은 제한조건의 경계값에 걸리는 경우이다.

이제 Kuhn-Tucker 조건에 의해 (편의 상 Tensor Notation을 사용하며, 같은 첨자의 반복은 Summation이다.)

을 만족한다.

다시 이 문제는 Wolfe Duality에 의해  Lagrange 변수에 대하여 최대화하는 문제로 바꿀 수 있다:

subject to  

                   

위의 문제를 Quadratic Optimization 문제라고 하며, 모든 i에 대하여 해 를 찾는 것이 목표이다.(Hat을 씌운 것은 해를 의미한다.)

결과 가중치 벡터는 

이며, 여기서  는 Dual Problem의 해이다.

또한 w_o는 Karusch-Kuhn-Tucker 조건(KKT Condition),

으로부터 얻을 수 있다.

마진에 있지 않은 모든 점에 대하여

이며, 는 Support Vector들에 대해서만 선형 조합(Linear Combination)한 것이다.

따라서 결정 경계(Decision Boundary)는 다음 식으로 표현할 수 있으며,

결정값은 결정 경계에 대한 부호로 표현할 수 있다:

4. 선형 분리불가능(Linearly Non-separable) 데이터

선형 분리가능한 경우를 살펴보면 문득 이런 궁금증이 생겼을지 모른다: 만약 데이터가 선형 분리할 수 없는 경우라면 어떻게 해야 할까?

이러한 경우가 당연히 실제로 있을 수 있다. 다음 그림을 살펴보도록 하자.

[그림 6.] 선형 분리불가능 예.

위의 그림에서 보는 바와 같이, 네모와 원을 나눌 수 있는 어떤 라인도 정의할 수 없다.

이 문제를 풀기 위해 부가변수(Slack Variables)를 사용하는데, 이들은 몇몇 점들이 마진의 잘못된 그룹에 속하는 것을 허용하는 소프트 마진(Soft Margin)을 생성한다. 위의 그림에서 ξ_i가 부가변수이다. 이는 완화 조건(Relaxation Condition)을 도입하는 일종의 페널티 방법(Penalty Method)이다. 

이에 대하여 다음과 같이 문제를 정의할 수 있다:

모든 y_i = +1에 대하여, w^Tx_i + w₀ ≥ 1 - ξ_i

모든 y_i = -1에 대하여, w^Tx_i + w₀ ≤ -1 + ξ_i

비용 변수(Cost Parameter) 또는 페널티 변수(Penalty Parameter) C는 제한조건을 위반하는 모든 점들에 적용되며, 최대 마진을 찾는 대신, 전체 비용 변수를 최소화하는 문제로 정의할 수 있다.

이 문제에 대한 Lagrange 승수 형식(Primal 문제)은

Dual 형식에 의해 다음과 같이 정의되며,

subject to

               

이에 대한 해는

이다.
분리가능한 경우와의 차이는,

0 ≤ λ_i ≤ C

이며, w₀는 KKT 조건으로부터 구할 수 있다.

5. 비선형 공간

선형 분리가능한 데이터에 대해 읽으면서 많은 이들이 질문을 하게 될 것이다: 그렇다면 선형으로 분리할 수 없는 경우에는 어떻게 처리할 것인가?

대부분의 실제 응용 문제의 경우 변수들의 관계는 비선형이다. 앞서 다루었듯이 SVM은 부가변수를 도입하여 약간 잘못 분류된 데이터를 허용하여 비선형 공간에 대하여도 대처할 수 있었다. 그러나, 이게 다는 아니다. SVM의 핵심은 커널 트릭(Kernel Trick)이라는 프로세를 이용하여 주어진 문제를 고차원으로 맵핑할 수 있다. 이 방법을 통해 비선형 관계를 약간 선형적으로 보이도록 할 수 있다.

이해를 돕기 위해 실제 예를 들어보도록 하겠다. 아래 그림에서 왼쪽 그림은 위도 및 경도에 따른 날씨 분포인데, 위도와 경도에 따른 날씨와의 뚜렷한 상관관계를 발견하기 어렵다. 그런데 오른쪽 그림과 같이 고도에 따른 날씨를 측정결과를 확인해보니 고도-위도 상에서는 데이터가 선형 분리가능한 상태임을 알 수 있다. 왼쪽 상태에서 오른쪽 상태로 변환하는(새로운 데이터 공간으로 맵핑(Mapping)) 함수를 커널 함수라고 하며, 데이터 공간 변환을 위해 다양한 커널 함수가 사용되고 있다.

 

[그림 7.] 비선형 공간 데이터 예.

왼쪽 그림은 위에서 아래로 내려다보는 시각으로 표현된 것이며, 오른쪽 그림은 지면에서 관찰된 데이터인데, 이처럼 데이터를 보는 시각에 따라 분리 가능한 상태로 변환할 수 있다. 이런 식으로 SVM은 비선형 커널을 이용하여 데이터를 분리할 수 있는 상태로 변환하기 위해 데이터에 새로운 차원을 추가한다. 즉, 커널 트릭은 관찰된 데이터의 특징 사이에 수학적 관계를 표현하는 새로운 특징을 구성하는 과정이라고 생각할 수 있다. 예를 들어, 고도라는 특징은 위도와 경도의 상호작용에 의해 수학적으로 표현된 것이라고 할 수 있는데, 위도-경도로 표현되는 것을 등고선에 비유할 수 있고 중심으로 갈수록 고도가 높은 것으로 해석할 수 있다는 것이다. 이렇게 하면 SVM이 원래의 데이터에서는 명시적으로 표현되지 않은 특징들을 학습할 수 있도록 한다.

아래 그림은 선형 및 비선형 데이터 공간에서의 선형 분리자(Linear Separator)와 비선형 분리자(Nonlinear Separator)를 표현한 것이다.

[그림 8.] 선형 데이터 공간 및 비선형 데이터 공간의 분리자.

비선형 커널함수를 이용한 SVM의 장점과 단점은 다음과 같다:

강점	약점
분류 또는 수치 예측 문제에 사용할 수 있다. 노이즈 데이터에 크게 영향을 받지 않으며, 오버피팅(Overfitting)의 경향이 낮다. 다수의 잘 정립된 SVM 알고리즘이 있기 때문에 신경망보다 사용하기 쉽다. 데이터 마이닝 대회에서 높은 정확도와 이목을 끄는 승리로 명성을 얻었다.	최고의 모델을 찾으려면 다양한 조합의 커널과 모델 파라미터들을 테스트해야 한다. 학습하는데 시간이 오래 걸릴 수 있다. 특히 입력 데이터세트의 특징이 너무 많으면 매우 느리다. 해석하기 불가능하지 않다면 매우 어려운 복잡한 블랙박스 모델이 될 수 있다.

커널 함수는 일반적으로 다음과 같은 형태를 갖는다. 함수 Φ(x)는 데이터 x를 다른 공간으로 맵핑한다:

x → φ(x)

즉, 일반적인 커널 함수는 두 개의 특징 벡터  x와 x'를 변환하여 벡터 내적(Dot Product)하여 스칼라값을 계산한다:

K(x,x') = φ(x)^Tφ(x')

이러한 형식으로 많은 유형의 데이터에 대한 커널 함수가 개발되어 왔다. 커널 함수로 널리 사용되는 목록들을 아래에 열거하였으며, 거의 모든 SVM 소프트웨어 패키지들은 이 커널 함수들을 지원한다.

우선 선형 커널 함수를 살펴보자. 선형 커널 함수는 데이터를 변환하지 않으며, 단순히 두 데이터 벡터의 내적이다:

K(x,x') = φ(x)^Tφ(x')

k차 다항 커널 함수는 데이터의 간단한 비선형 변환을 추가한다:

K(x,x') = (1 + x·x')^k

예를 들어 2차(k = 2) 다항 비선형 커널은 다음과 같다:

x = [x₁, x₂]^T

x → φ(x) = [x₁^T,  x₂^T, √2, x₁x₂, √2, x₁, √2, x₂, 1]

K(x, x') = φ(x)^Tφ(x') = x₁²x₁'² + x₂²x₂'² + 2x₁x₂x'₁x'₂ + 2x₁x'₁ + 2x₂x'₂ + 1

                                  = (x₁x₁' + x₂x₂' + 1)²

                                  = (1 + x^Tx')²

Sigmoid 커널 함수는 Sigmoid 활성함수를 이용하는 신경망과 유사한 SVM 모델이다. κ와 δ는 커널 파라미터이다:

K(x,x') = tanh(κx^Tx' - δ)

가우시안 RBF(Radial Basis Function)는 RBF 신경망과 유사하다. RBF 커널은 많은 유형의 데이터에 적합하며 다양한 학습 작업의 적합한 시작점으로 여겨진다:

K(x,x') = exp[-||x - x'||²/(2σ²)]

 

특정 학습 작업에 대하여 어떤 커널 함수가 적합한지에 대한 신뢰할만한 규칙은 존재하지 않는다. 적합도는 학습 데이터량, 특징들 사이의 관계, 학습 컨셉을 따른다. 대부분의 경우 검증용 데이터세트에 대한 다양한 SVM 알고리즘을 학습시키고 평가하는 약간의 시행착오가 요구된다. 많은 사실 커널의 선택은 임의로 이루어지는 경우가 많은데 커널들 사이의 성능 차이가 그리 크지 않기 때문이다.