핸즈 온 머신러닝 :: 5. 서포트 벡터 머신

핸즈 온 머신러닝 (Hands-On Machine Learning with Scikit-Learn & TensorFlow) / 오렐리앙 제론 지음 , 박해선 옮김

을 읽고, 추후 기억을 되살릴 수 있게끔 나만의 방법으로 내용을 리뷰한다. 따라서 리뷰의 내용 별 비중이 주관적일 수 있다.

챕터 5. 서포트 벡터 머신

Support Vector machine은 매우 강력하고 많은 경우에 사용할 수 있는 머신러닝 모델이다. 딥 러닝이 유행하기 전에 SVM 모델이 크게 유행했다.

 

5.1 선형 SVM 분류

SVM 분류기는 데이터들을 선형 기준으로 구분하는 것을 목적으로 한다. 이 때에, 기준 선에 가장 가까운 데이터가 최대한 멀어지도록 기준 선을 긋는다면 더 잘 그은 기준선이 될 것이다. 따라서 이를 large margin classification 이라고 부른다. margin 을 정하였는데 이 바깥쪽에 새로운 데이터가 추가된다면 전혀 영향을 끼치지 않는다. 즉 margin에 위치한 샘플에 의해 결정되므로 이런 샘플들을 support vector 라고 한다.

 

SVM은 특성의 스케일에 민감하므로 StandardScaler를 사용하여 정규화해주는 것이 좋다.

 

 

5.1.1 소프트 마진 분류

모든 샘플이 기준 선과 그 margin 밖에 있따면 이를 hard margin classifcation 이라고 한다. 하지만 데이터가 애초에 선형 구분이 되지 않는다면 하드 마진 분류는 불가능하다. 따라서 margin을 최대한 넓게 잡는 것과 margin에 대한 오류를 줄이는 것을 동시에 진행하여야 하므로 soft margin classification 문제를 풀게 된다. 두 목적 사이의 균형을 하이퍼 파라미터를 사용하여 조절할 수 있다.

 

https://scikit-learn.org/stable/modules/generated/sklearn.svm.LinearSVC.html

sklearn.svm.LinearSVC — scikit-learn 0.22.1 documentation

 

혹은 SVC에서 kernel을 linear로 해도 되지만, LinearSVC가 최적화 되어있더 더 빠르다.

5.2 비선형 SVM 분류

선형적으로 분류할 수 없는 데이터를 해결하여야 한다. 기존에 언급하였던 PolynomialFeatures를 사용하여 다항 특성을 추가해주어도 된다.

 

5.2.1 다항식 커널

하지만 단순히 많은 다항 특성들을 추가하는 것은 속도를 느리게 만든다. 다행히도 SVM에서는 kernel trick 이라는 것을 사용할 수 있는데, 커널이 SVM의 발전에 핵심적으로 기여하였다. kernel trick은 실제로 다항 특성을 추가하지는 않지만 cost function 을 최적화 할 때에 함수를 변형하여 특성을 추가한 것과 같은 효과를 내는 것이다.

 

https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html

sklearn.svm.SVC — scikit-learn 0.22.1 documentation

 

5.2.2 유사도 특성 추가

특성을 추가 할 때에 다항 특성 뿐만 아니라 유사도 특성을 추가하는 방법도 있다. 예를 들어, 샘플들에 대한 RBF (Radial Basis Function)을 특성으로 추가하여 활용하면 선형이 아닌 데이터도 선형으로 구분할 수 있게 된다. 하지만 이는 샘플 만큼의 특성을 추가하게 되므로 매우 비효율적이게 된다.

 

5.2.3 가우시안 RBF 커널

위의 유사도 특성도 마찬가지로 kernel trick을 사용할 수 있다. SVC에서 kernel="rbf" 를 인자로 보내면 된다.

 

5.2.4 계산 복잡도

LinearSVC와 SGDClassifier의 시간 복잡도는 O(mn) 이고, SVC의 시간 복잡도는 경우에 따라 O(m^2 n) ~ O(m^3 n) 이다. 이 때 m은 샘플의 수이고 n은 특성의 수이다. 세 모델 모두 스케일을 전처리해주어야하며 SVC의 경우에만 커널 트릭 적용이 가능하다.

 

5.3 SVM 회귀

분류 문제는 margin이 가장 큰 기준을 찾는 것이었다면 회귀 문제는 margin 안에 최대한 많은 데이터가 들어가도록 하는 것이다. 하이퍼 파라미터 C가 커질수록 마진 오차에 민감해지므로 과대적합된다. SVC와 마찬가지로 LinearSVR과 SVR 을 지원한다.

 

https://scikit-learn.org/stable/modules/generated/sklearn.svm.LinearSVR.html

sklearn.svm.LinearSVR — scikit-learn 0.22.1 documentation

https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVR.html

sklearn.svm.SVR — scikit-learn 0.22.1 documentation

5.4 SVM 이론

SVM의 훈련 알고리즘은 수학적으로 어떻게 작동하는지 알아보는 단원이다. 중요한 부분이지만 블로그 특성상 식을 입력하는 것이 번거로워 간단하게 설명하겠다. 최적화 분야에 대해 잘 안다면 쉽게 넘어갈 수 있을 것이다.

 

5.4.1 결정 함수와 예측

오류를 발생시키지 않거나, 제한적인 오류를 가지며 최대한 마진을 크게 하는 기준선과 크기를 정하는 것이다. (w^t x + b <= 1)

 

5.4.2 목적 함수

w와 b의 비율은 유지하되 스케일이 바뀐다면 기준선은 그대로지만 마진의 폭이 바뀌게 된다. 즉 w가 작을수록 마진이 커지므로 w의 크기를 최소화하는 것이 중요하다. (minimize 1/2 w^t w + C * margin error)

 

5.4.3 콰드라틱 프로그래밍

이는 선형 제약 조건의 볼록 이차 최적화 문제이므로 Quadratic Programming Problem 이라고 부를 수 있다. 이런 문제를 푸는 알고리즘은 이미 존재하므로 SVM 문제를 적당히 변형하여 해당 알고리즘에 전달할 수 잇다.

 

5.4.4 쌍대 문제

최적화 분야에서는 primal problem과 dual problem이라는, 서로 대응되는 관계의 문제가 존재한다. dual problem의 해는 primal problem의 하한 (혹은 상한)이 되는데, 특정 경우에서는 하한 뿐만아니라 실제 최솟값이 된다. SVM은 이 조건을 만족하므로 dual problem을 푸는것이 primal problem을 푸는 것과 같다. SVM의 dual problem의 목적함수에는 두 데이터 간의 내적이 포함된다.

 

5.4.5 커널 SVM

dual problem을 푸는 이유는 커널 SVM을 적용할 수 있게 해주기 때문이다. 우리가 기존의 벡터를 다항 변환하여 여러 특성을 만들었다고 하자. 구체적으로 x 가 (x1, x2)일 때에 f(x)가 (x1^2, sqrt(2) x1 x2, x2^2) 인 변환 f를 생각하자. 이 때 a,b를 f(a), f(b)로 변환하면 f(a)와 f(b)의 내적값이 a와 b 내적값의 제곱이 된다. 즉 f를 생각하지 않고도 변환 후 두 점의 내적을 알 수 있다. 

 

위의 변환 f 뿐만 아니라, 다양한 변환에 대해 Kernal 함수가 주어져있다. 대표적으로 선형 커널, 다항 커널, 가우시안 RBF 커널 (무한 차원의 다항 변환과 동일), sigmoid 커널이 있다.

 

커널 함수를 이용하여 최적화 문제를 풀었다면, 예측에 이를 적용할 수 있어야 한다. 다행히도 수학적인 계산을 통하여 f변환과 마진 벡터 w, b를 모르더라도 dual problem의 해를 가지고 예측을 해낼 수 있다.

 

5.4.6 온라인 SVM

선형 SVM 분류기의 cost function을 hinge loss를 이용하여 정의한다면 경사 하강법도 적용할 수 있으므로 online SVM classifier를 정의할 수 있다.