서포트 벡터 머신 (SVM) 알고리즘

개요

서포트 벡터 머신 알고리즘, 또는 SVM(Support Vector Machine) 알고리즘은 머신 러닝 분야에서 사용되는 알고리즘 중 하나로, 분류를 위한 기준을 합리적으로 정의하기 위해 고안된 지도 학습 모델이다.

 

작동 원리

분류에 대한 기준은 데이터에 존재하는 속성의 개수에 따라 달라지는데, 두 가지 속성으로 분류하고자 한다면 선으로, 세 가지 속성으로 분류하고자 한다면 면으로 표현할 수 있을 것이다.

 

예를 들어 아래의 [그림 1]과 같이 어떤 데이터 셋을 노란색, 파란색 두 가지 속성(feature)으로 분류하고자 한다면, SVM 알고리즘에서는 그 분류를 위한 기준선을 정의한다. 이 기준선을 결정 경계(Decision Boundary)라고 한다. 그리하여 새로운 데이터가 데이터 셋에 추가될 경우, 결정 경계를 기준으로 어느 쪽 속성에 속하는지 확인하여 해당 데이터 값을 분류할 수 있도록 한다.

[그림 1] 결정 경계와 마진(margin)

결정 경계는 무한히 다양한 방법으로 결정할 수 있는데, 그 중에서 최적의 결정 경계를 얼마나 잘 선정할 수 있느냐에 따라 해당 데이터 셋 분류 모델의 정확성을 판단할 수 있을 것이다.

 

보통 결정 경계는 데이터 값들의 군집으로부터 최대한 멀리 떨어져 있을수록 적합하다고 본다. 결정 경계와 결정 경계로부터 가장 가까운 데이터 값, 즉 서포트 벡터(Support Vector)들의 거리를 마진(margin)이라고 하는데, 최적의 결정 경계를 만들기 위해서는 이 마진을 최대화하는 과정을 필요로 한다. 다시 말하면, 서포트 벡터만 적절하게 선출할 수 있다면 이론적으로는 SVM 알고리즘의 기본적인 목표를 쉽게 달성할 수 있다는 것이다. 이 과정에서 필요한 서포트 벡터의 개수는 데이터에 존재하는 속성의 개수에 따라 달라지는데, n개의 속성을 가진 데이터에는 최소 n + 1개의 서포트 벡터가 존재하게 된다.

 

선형 SVM에서의 이상치 데이터 처리

한편 주어진 데이터들을 완벽하게 두 개의 그룹으로 분리할 수 없는 경우도 발생할 수 있을 것이다. SVM 알고리즘에서는 이 경우 어느 정도의 오분류 에러를 허용할 수도 있다. 선형 분류에서의 이러한 오분류 허용을 소프트 마진(Soft Margin, 또는 C-SVM)이라고 한다.

소프트 마진에서는 오분류를 허용하고, 이를 고려하기 위해 해당 결정 경계로부터 잘못 분류된 데이터의 거리를 측정하는 Slack Variable 이라는 변수를 사용한다. 총합에 한계를 주어 과적하는 제어하는 Slack Variable C(cost)를 추가한 소프트 마진의 목적 함수는 다음과 같이 표현할 수 있다.

C 값이 커지면 학습 오류를 허용하지 않고 마진이 줄어들어 오류가 적어지지만, 과적합의 위험이 생긴다. 반대로 C 값이 작아지면 마진이 커지고, 오류가 증가하며, 과소적합의 위험성이 발생할 수 있다.

 

소프트 마진과는 반대로, 마진의 값을 줄이더라도 오분류 에러를 허용하지 않는 방식을 하드 마진(Hard Margin)이라고 한다. 소프트 마진보다는 더 정확한 분류를 할 수 있는 결정 경계 정의 방식이 특징이지만, 모든 데이터를 선형으로, 오차 없이 분류할 수 있는 경우는 그렇지 않은 경우보다 비교적 적기 때문에 한계가 있다. 하드 마진의 목적 함수는 다음과 같이 표현된다. 

하드 마진은 소프트 마진에서 Slack Variable에 관련된 수식을 뺀 것 뿐이기 때문에 두 가지의 분류 방식을 쉽게 구분할 수 있다.

 

비선형 분리와 커널 트릭

데이터가 1차원, 3차원에 존재하는 등 선형 분리가 불가능한 경우에 해당 입력 공간을 선형 분리가 가능한 고차원 특성공간(주로 2차원)으로 변환하여 선형 분리를 실행하고, 다시 데이터를 기존의 입력 공간으로 변환하는 방식을 비선형 분리라고 한다. 입력 공간을 특성 공간으로 변환하기 위해서는 매핑 함수를 사용하고, 이 매핑 함수는 정의에 따라 달라질 수 있다.

[그림 2] 비선형 분리에서의 커널 트릭

하지만 차원이 커질수록 계산에 대한 부담감이 기하급수적으로 커지는데, 이를 해결하기 위해서 커널 트릭(Kernel Trick)라는 방법이 사용된다.

커널 트릭은 실제로는 데이터의 특성을 확장하지 않았지만, 마치 확장한 것처럼 만들어 계산하는 방식이다. 특성 공간의 차원이나 매핑 관계를 명시적으로 알 필요 없이, 확장된 특성 공간의 두 벡터의 내적만을 계산하면 된다. 고차원의 복잡한 계산을 수행하지 않고도 연산할 수 있다는 장점이 있다.

 

구현

SVM 알고리즘을 구현하는 가장 대표적이고 접근성 높은 방법은 Python의 scikit-learn 라이브러리를 활용하여 코드를 작성하는 것이다.

다음 Python 코드는 [그림 3]과 같은 2차원 데이터 셋에 좌표 (3, 2)를 추가했을 경우, 새로 추가된 좌표 값을 노란색(‘A’)과 파란색(‘B’) 중 어느 쪽으로 분류하는지에 대한 결과를 출력하는 코드이다.

from sklearn.svm import SVC

classifier = SVC(kernel = 'linear')  # 이진 분류
# 훈련 데이터
training_points = [
    [1, 2], [5, 4], [4, 3], [1, 5], [2, 4],
    [7, 5], [4, 1], [8, 2], [9, 4], [8, 4],
]
# 라벨링
labels = [ 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', ]

classifier.fit(training_points, labels)
print(classifier.predict([[3, 2]]))

[그림 3] SVM 알고리즘 구현 예제 데이터

실행 결과, 분류기에서는 (3, 2) 좌표에 위치한 샘플 데이터를 노란색(‘A’) 그룹으로 판별했다고 나온다.

['A']

위에서 설명한 예시 이외에도 다양한 함수와 모듈들을 활용하여 분류 모델을 코드로 구현할 수 있다.