서포트 벡터 머신 (Support Vector Machine, SVM)

  SVM은 선형이나 비선형 분류, 회귀, 이상치 탐색에도 사용할 수 있는 머신러닝 모델입니다. SVM은 특히 복잡한 분류 문제에 잘 들어맞으며 작거나 중간 크기의 데이터셋에 적합합니다. (왜 작거나 중간 크기의 데이터셋에 적합한지 궁금하네요.)

 

선형 SVM 분류

 SVM의 기본 아이디어는 그림으로 설명하는 것이 가장 좋습니다. 아래 사진을 보시면 IRIS 데이터에 대해서 각각의 선형 분류기가 만든 결정 경계가 나오는데요. 어떤 분류기는 제대로 분류하지 못하기도 하고 또는 너무 한쪽에 가까이 붙어서 새로운 샘플에 대해서는 제대로 동작하기 어려운 경우도 있어 보입니다.

 

 반면에 SVM 분류기의 결정 경계를 보면 이 직선은 두 개의 클래스를 나누고 있을 뿐만 아니라 제일 가까운 훈련 샘플로부터 가능한 한 멀리 떨어져 있습니다. SVM 분류기를 클래스 사이에 가장 폭이 넓은 도로를 찾는 것으로 생각할 수도 있고, 그래서 라지 마진 분류(Large Margin Classification) 라고도 합니다.

Decision Tree와 달리 SVM은 특성의 스케일에 민감합니다. 스케일 작업을 진행하면 기존에는 전체 데이터 비해 매우 좁았던 Margin이 스케일 후 상대적으로 넓어지게 됩니다.

소프트 마진 분류

 모든 샘플이 도로 바깥쪽에 올바르게 분류되어 있다면 이를 하드 마진 분류 라고 합니다. 하지만 데이터가 선형적으로 구분될 수 없거나 이상치가 있다면 하드 마진을 찾을 수 없는 문제가 발생합니다. 

 

 이런 문제를 해결하기 위해 도로의 폭을 가능한 한 넓게 유지하는 것과 마진 오류(Margin Error, 샘플이 도로 중간이나 반대쪽에 있는 경우) 사이에 적절한 균형을 잡아야 합니다. 이를 소프트 마진 분류 라고 합니다.

 

 Sklearn을 활용하여 SVM 모델을 만들 때 C라는 하이퍼파라미터를 지정할 수 있습니다. 이를 낮게 설정하면 도로의 폭이 넓어지고, 높게 설정하면 도로의 폭이 좁아집니다. 일반적으로 도로의 폭이 넓으면 마진 오류가 나쁘게 되고, 도로의 폭이 좁으면 마진 오류가 좋아집니다. 하지만 과대적합이라면 C를 감소시켜 도로의 폭이 넓어지게하여 마진 오류가 많아지게하고, 모델을 규제하여 일반화 시키기도 합니다.

 

비선형 SVM 분류

 선형 SVM 분류기가 효율적이고 잘 작동하기는 하지만 선형적으로 분류할 수 없는 데이터셋이 많습니다. 비선형 데이터셋을 다루는 한 가지 방법은 다항 특성과 같은 특성을 더 추가하는 것입니다. (차원을 추가하여 기존에 1차원에서는 선으로 분리될 수 없었던 데이터를 2차원에서는 선으로 분리할 수 있도록.) 

 

 사이킷런을 사용하여 이를 구현하려면 PolynomialFeatures 변환기와 StandardScaler, LinearSVC를 연결하여 Pipeline을 만듭니다. 이를 moons 데이터셋에 적용하면 마주보는 두 개의 반원 모양의 데이터를 이진 분류할 수 있습니다.

from sklearn.datasets import make_moons
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures

X, y = make_moons(n_samples=100, noise=0.15)
polynomial_svm_clf = Pipeline([
    ("poly_features", PolynomialFeatures(degree=3)),
    ("scaler", StandardScaler()),
    ("svm_clf", LinearSVC(C=10,loss="hinge"))

])

polynomial_svm_clf.fi(X,y)​

1. 다항식 커널

 다항식 특성을 추가하는 것은 간단하고 모든 머신러닝 알고리즘에서 잘 작동합니다. 하지만 낮은 차수의 다항식은 복잡한 데이터셋을 표현하는데 한계가 있고, 높은 차수의 다항식은 모델을 느리게 만듭니다.

 

 SVM을 사용할 땐 커널 트릭(Kernel Trick)을 사용하여 실제로 특성을 추가하지 않으면서 다항식 특성을 많이 추가한 것과 같은 결과를 얻을 수 있습니다. 이 기법은 SVC 파이썬 클래스에 구현되어 있습니다.

from sklearn.svm import SVC

poly_kernel_svm_clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm_clf", SVC(kernel="poly", degree=3,coef0=1, C=5))
])

 이 코드는 3차 다항식 커널을 사용해 SVM 분류기를 훈련시킵니다. 모델이 과대적합이라면 다항식의 차수를 줄여야 하고, 반대로 과소적합이라면 차수를 늘려야 합니다.

 

 매개변수 coef0은 모델이 높은 차수와 낮은 차수에 얼마나 영향을 받을지 조절합니다. 뒤에서 나오는 다항식 커널에 있는 상수항 r이 coef0 매개변수 값입니다. 다항식 커널은 차수가 높아질수록 1보다 작은 값과 1보다 큰 값의 차이가 크게 벌어지므로 coef0을 적절한 값으로 지정하면 고차항의 영향을 줄일 수 있습니다. coef0의 기본값은 0 입니다.

 

2. 유사도 특성

 커널 트릭 뿐만 아니라 비선형 특성을 다루는 또 다른 기법은 각 샘플이 특정 랜드마크와 얼마나 닮았는지 측정하는 유사도 함수로 계산한 특성을 추가하는 것입니다. 예를 들어 앞에서 본 1차원 데이터셋에 두 개의 랜드마크 x1=-2 와 x1=1을 추가합니다. 그리고 r=0.3인 가우시안 방사 기저 함수(Radial Basis Function, RBF)를 유사도 함수로 정의하겠습니다.

 

 

 두 개의 x1일때의 RBF함수와 x2일때의 RBF함수가 각각 만들어졌습니다. 이 함수들을 사용하면 직선위에 놓여있던 데이터를 (x1, x2) 인 2차원 축으로 보낼 수 있고, 이후에 선형적으로 구분이 가능해집니다. 랜드마크를 선택할 때 가장 간단한 방법은 데이터셋에 있는 모든 샘플 위치에 랜드마크를 설정하는 것입니다. 이렇게 하면 차원이 매우 커지고 따라서 변환된 훈련 세트가 선형적으로 구분될 가능성이 높습니다.

 

 단점은 훈련 세트에 있는 n개의 특성을 가진 m개의 샘플이 m개의 특성을 가진 m개의 샘플로 변환된다는 것입니다. 따라서, 훈련 세트가 매우 클 경우 동일한 크기의 아주 많은 특성이 만들어집니다.

 

3. 가우시안 RBF 커널

 유사도 특성 방식도 머신러닝 알고리즘에서 유용하게 사용될 수 있습니다. 다만 추가 특성을 모두 계산하려면 연산 비용이 많이 드는데, 여기에서 커널 트릭을 추가로 사용하면 유사도 특성을 많이 추가하는 것과 같은 비슷한 결과를 얻을 수 있습니다. 

poly_kernel_svm_clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm_clf", SVC(kernel="rbf", gamma=5, C=0.001))
])

rbf_kernel_svm_clf.fit(X,y)

 모델의 파라미터는 gamma(r) 와 C 입니다. gamma를 증가시키면 종 모양 그래프가 좁아져서 각 샘플의 영향 범위가 작아집니다. 따라서, 결정 경계가 조금 더 불규칙해지고 각 샘플을 따라 구불구불하게 휘어져 과대적합을 하게됩니다. 반대로 작은 gamma값은 넓은 종 모양 그래프를 만들며 샘플이 넓은 범위에 걸쳐 영향을 주므로 결정 경계가 더 부드러워집니다. 

 

 결국 gamma(r)가 규제의 역할을 합니다. 모델 과대적합일 경우엔 감소시켜야 하고, 과소적합일 경우엔 증가시켜야 합니다.

 

4. 계산 복잡도

 LinearSVC 파이썬 클래스는 선형 SVM을 위한 최적화된 알고리즘을 구현한 liblinear 라이브러리를 기반으로 합니다. 커널 트릭을 지원하지는 않지만 훈련 샘플과 특성수에 거의 선형적으로 늘어납니다. 이 알고리즘의 훈련 시간 복잡도는 대략 O(m x n) 정도입니다.

 

 SVC는 커널 트릭 알고리즘을 구현한 libsvm 라이브러리를 기반으로 합니다. 훈련의 시간 복잡도는 O(m^2 x n) 과 O(m^3 x n) 사이입니다. 불행하게도 훈련 샘플 수가 커지면 엄청나게 느려진다는 것을 의미합니다. 따라서 복잡하지만 작거나 중간규모의 훈련 세트에 이 알고리즘이 잘 맞습니다.

 

 하지만 데이터셋에서 특성의 값에 0이 많은 희소특성인 경우에는 알고리즘의 성능이 샘플이 가진 0이 아닌 특성의 평균 수에 거의 비례합니다.

 

SVM 회귀

 SVM 알고리즘은 선형, 비선형 분류뿐만 아니라 선형, 비선형 회귀에도 사용할 수 있습니다. SVM을 분류가 아니라 회귀에 적용하는 방법은 목표를 반대로 하는 것입니다. 일정한 마진 오류 안에서 두 클래스 간의 도로 폭이 가능한 한 최대가 되도록 하는 대신, SVM 회귀는 제한 마진 오류 안에서 도로 안에 가능한 한 많은 샘플이 들어가도록 학습합니다. (도로의 폭은 하이퍼파라미터 epsilon(e)으로 조절합니다.)

 

 마진 안에서는 훈련 샘플이 추가되어도 모델의 예측에는 영향이 없습니다. 그래서 이 모델을 e에 민감하지 않다 고 말합니다. (마진안에 있는 데이터들은 훈련에 영향을 끼치지 않음) C는 규제에 해당합니다.

from sklearn.svm import SVR

svm_poly_reg = SVR(kernel="poly", degree=2, C=100, epsilon=0.1)
svm_poly_reg.fit(X, y)

 

SVM 이론

 먼저 선형 SVM 분류기부터 시작하겠습니다. 여기서는 편향을 b라 하고 특성의 가중치 벡터를 w라 하겠습니다.

 

결정 함수와 예측

 선형 SVM 분규리 모델은 단순히 결정 함수 Wtx+b=wx+...+wx+b를 계산하여 새로운 샘플 x의 클래스를 예측합니다. (훈련을 통해 w와 b가 선정) 결과값이 0보다 크면 예측된 클래스는 양성, 그렇지 앞으로 음성 클래스가 됩니다. (이진 분류)

 

 결정 경계는 결정 함수의 값이 0인 점들로 이루어져 있습니다. 이는 두 평면의 교차점으로 직선입니다. 점선은 결정 함수의 값이 1 또는 -1인 점들을 나타냅니다. 이 선분은 결정 경계에 나란하고 일정한 거리만큼 떨어져서 마진을 형성하고 있습니다. 선형 SVM을 분류기를 훈련한다는 것은 마진 오류를 하나도 발생하지 않거나(하드 마진) 제한적인 마진 오류를 가지면서(소프트 마진) 가능한 한 마진을 크게 하는 w와 b를 찾는 것입니다.

 

 n개의 특성이 있을 때 결정 함수는 n차원의 초평면이고 결정 경계는 n-1차원의 초평면입니다.

 

목적함수

 결정함수의 기울기를 생각해보면 이는 가중치 벡터의 노름 ||w|| 와 같습니다. 이 기울기를 2로 나누면 결정 함수의 값이 +-1 되는 점들이 결정 결계로부터 2배만큼 더 멀어집니다. 기울기를 2로 나누는 것은 마진에 2를 곱하는 것과 같습니다. 즉, 가중치 벡터 w가 작을수록 마진은 커집니다.

 

 마진을 크게 하기 위해 ||w||를 최소화해야 합니다. 결정 함수가 모든 양성 훈련 샘플에서는 1보다 커야하고 음성 훈련 샘플에서는 -1 보다 작아야 합니다. (Decision Tree는 불순도를 기반으로 딱 나누기 때문에 확률을 구할 수 있는데, SVM 의 경우 margin이 파라미터에 들어가기 때문에 정확히 확률로 표기하는데는 무리가 있다.)

 

 하드 마진 선형 SVM 분류기의 목적 함수를 제약이 있는 최적화 문제로 표현할 수 있습니다.

||w||를 최소화하는 대신 (1/2)||w||^2 인 (1/2)w^t*w 를 최소화합니다.  (깔끔하고 간단하게 미분하기 위해서.)

 

 소프트 마진 분류기의 목적 함수를 구성하려면 각 샘플에 대해 슬랙 변수(Z, 제타)를 도입해야 합니다. Z는 i번째 샘플이 얼마나 마진을 위반할지 정합니다. 이 소프트 마진 분류기의 목적은 2개의 상충되는 목표를 가지고 있습니다.

1) 마진 오류를 최소화하기 위해 가능한 한 슬랙 변수(Z)의 값을 작게 만드는 것.

2) 마진을 크게 하기 위해 (1/2)||w||^2 를 가능한 한 작게 만드는 것.

 두 목표 사이의 트레이드오프를 정의하기위해 하이퍼파라미터 C를 사용합니다.

쌍대 문제

 원본 문제(Primal Problem)라는 제약이 있는 최적화 문제가 주어지면 쌍대 문제(Dual Problem) 라고 하는 다른 문제로 표현할 수 있습니다. 일반적으로 쌍대 문제의 해는 원본 문제와 똑같은 해를 제공합니다. 

 이 식을 최소화하는 벡터 a를 찾았다면 아래 식을 사용해 원본 문제의 식을 최소화하는 w와 b를 계산할 수 있습니다.

 (훈련 샘플 수) < (특성 개수) 인 상황일 때(데이터보다 특성수가 많아서 차원의 저주 문제를 야기할수도 있는 상황일 때), 원본 문제보다 쌍대 문제를 푸는 것이 더 빠릅니다. 더 중요한 것은 쌍대 문제로 표현하면 원본 문제에서는 적용이 안 되는 커널 트릭을 가능하게 합니다.