[ML/DL: Prof. Joonseok Lee] Lecture 10: Support Vector Machines

본 포스팅은 서울대학교 이준석 교수님의 M3239.005300 Machine Learning & Deep Learning 1을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.
이준석 교수님에게 강의 자료 사용에 대한 허락을 받았음을 알립니다.

https://youtu.be/yQ7UGAFCU44?si=fbaJcvhBD4Yu13mp

 

 

 지금까지 배운 Discriminant analysis는 각 class가 정규 분포라는 가정하에 p(y|x)를 추정하였고, logistic regression의 경우에는 log odds가 linear하다는 가정으로 decision boundary을 찾아냈었다.

 

 이번 Lecture에서는 Support Vector Machine이라는 확률을 사용하지 않으면서 decision boundary만을 맞추기 위한 방법에 대해 알아보도록 한다.

 

 

1. Support Vector Machine

Support Vector Machine(SVM)을 분류(Classification) 문제를 해결하는 지도 학습(Supervised Learning) 알고리즘이다. 

 

SVM의 핵심 개념

 SVM은 두 Class를 가장 잘 구분하는 경계(초평면, Hyperplane)를 찾는 것이 목표다.

• 초평면(Hyperplane): 데이터를 구분하는 n차원 공간에서의 (n-1)차원 평면
  • 2차원 → 직선
  • 3차원 → 평면
• 마진(Margin): 초평면과 가장 가까운 data point(서포트 벡터)와의 거리
• 목표: 마진을 최대화하는 초평면을 찾는 것

β는 법선 벡터(normal vector)와 같고, hyperplane에서 data point까지의 직선은 직교한다. 이때  β와 x의 내적 값이 0이 되는 방정식이 hyperplane의 형태인데, 이 값이 0을 경계로 크거나 작아지면 한쪽 공간으로 이동하게 된다.

Maximal Margin Classifier 

 

지금 목표는 두 class를 정확히 분류하면서 가장 큰 간격을 가지도록 하는 hyperplane을 구하는 것이 목표이다. 따라서 이때의 간격을 margin이라고 하면, margin은 최대여야 한다.

 

2. Support Vector Machines for Linearly Separable Cases

 Binary Classification이고, training data는 I.I.D를 만족한다고 가정한다. 

 

β와 x의 각도가 90°보다 작은 경우: 내적한 값이 0 이상이 되고, 이는 positive classification임을 의미한다.

β와 x의 각도가 90°보다 큰 경우: 내적한 값이 0 이하가 되고, 이는 negative classification임을 의미한다.

β와 x의 각도가 90°보다 같은 경우: 이 경우에는 data point가 hyperplane에 정확히 일치한 경우이므로 결정할 수 없다. 

 

 지금까지 계속 진행하는 과정은 margin을 최대가 되게 하기 위해서 margin을 표현하는 과정이다. 그러기 위해서는 먼저 decision boundary에 가장 가까운 data point를 찾고 그 거리를 표현해야 한다. 방법은 아래의 전개를 통해 거리 r을 유도할 수 있다.

 

 transposed 벡터와 일반 벡터 사이의 내적은 벡터의 squared norm을 의미하며, 이는 벡터의 크기의 제곱이다.

참고로 전치 연산은 벡터의 형식(차원)을 바꾸는 것일 뿐, 실제 벡터의 값과 공간에서의 위치는 변하지 않는다.

 

 그러면 decision boundary와 datapoint의 거리 r이 최소일 때 계산해 boundary에 가장 가까운 점을 찾아야 한다. 이때 y를 곱하는 이유는 y는 {-1, +1}의 class인데 이를 곱함으로서 값 전체가 절댓값이 되도록 하기 위함이다.(r이 양수일 때는 y = 1을 곱하고, r이 음수일 때는 y = -1을 곱함으로서 절댓값의 효과가 있다.)

 

 그 후 그 점이 최대가 되도록 하는 boundary를 구하는 것이 지금의 목표이다.

 위에서 구한 식을 계산하기 위해 수학적 트릭을 사용한다. decision boundary와 가장 가까운 datapoint 사이의 길이를 1이라고 정의하고, 그 이상 넘어가는 길이는 가중치 α를 곱해 배수배된 길이라고 생각한다.

 

 그렇게 정의하고 식을 정리하면 β의 norm이 가장 작아질 때를 구하면 된다. 단, 최소 길이를 1이라고 가정했으므로, 나머지 길이는 1 이상이라는 조건이 붙게 된다.

방금 구한 β norm의 제곱이 최소화 되는 영역은 아래와 같다. 

 local optimum을 풀려고 할 때 제약조건이 존재해서 미분이 불가능 하다면, Lagrangian Multiplier & KKT Condition을 적용해 미분을 진행할 수 있다.         

이제 Lagrangian를 최소화 시키는 β를 풀면 된다.

 

최종적으로 주어진 함수가 최댓값을 가질 때의  λ를 구하는 식은 아래와 같다.

 

 이때 x끼리의 내적한 값은 만약 각도가 90도내에 있다면 positive이고, 각도가 90도 이상이라면 negative이다. 한편, y_i, y_k는 실제로 같은 class라면 positive이고, 다른 class라면 negative임을 의미한다. 

 

 즉, y_i*y_k*(x_i)T*x_k가 양수라면 λ는 함수를 최대가 되게 하기 위해 0이 되게 된다. 그래서 λ의 역할은 서로 다른 class일 경우 가중치를 주어 최적화 시키는 역할이며, support vectors라 불린다. 이때의 support vectors는 decision boundary 가장 가까운 위치에서 정의하는 data points이다.

 즉, positive class에 해당하는 support vector와 negative class에 해당하는 support vector끼리의 힘겨루기를 통해 test point x를 분류하는 것이다.

 

 

 

3. Support Vector Machines for Linearly Non-separable Cases

 

 이번에는 아까와는 달리 완전히 분리할 수 없는 경우를 다루는 Support Vector Machines에 대해 알아보도록 한다.

  SVM에서 완전히 분리할 수 없는 경우에는 margin을 최대화 시키는 것과 miclassification rate를 줄이는 것을 동시에 하도록 하면 된다. 이때 slack variable이라 불리는 ξ_i을 사용한다. ξ_i의 역할은 각 data point x들이 decision boundary를 넘어갔을 경우에 가중치를 주는 변수이다.

 

ξ_i = 0: margin 안에 있거나 margin에 해당하는 경우

0 < ξ_i < 1: maximum margin을 만족하지는 않지만, 아직 decision boundary 안에 있을 경우

ξ_i >= 1: decision boundary를 넘었을 경우

 

 아까 완전히 분리 가능했던 경우라고 생각하고 구했던 함수에 slack variable를 추가하면 아래와 같다. 이때 상수 C는 slack variables의 중요도를 나타내는 hyper parameter이다. 

 

만약 C가 매우 크다면, 최대한 misclassification rate를 줄이는 것을 중점적으로 진행된다.

만약 C가 매우 작다면, misclassification rate보다는 margin을 크게 하는 것을 중점적으로 진행된다.

 

3. Margin-based Loss

 

 loss function은 machine learning model이 실제 label을 얼마나 잘 맞추고 있는지를 나타내는 척도이다.                             

                                                                                                                                                                                                  지금은 Binary Classification problem이므로 y = {+1, -1} 중 하나이다.

 

Margin-based loss는 model이 예측한 y'과 실제 y를 곱한 것에 기반한다. 이 yy'가 positive하다면 model이 정확히 class를 분류한 것이고, negative하다면 잘못 분류한 것이다. 따라서 yy' > 0이면 loss를 덜 주고, yy' < 0이면 loss를 크게 준다.         

 이 0/1 Loss 함수는 참거짓을 판별하는 0인 지점에서 미분이 불가능하기 때문에 사용할 수 없다.

                                                                                                                                                                                                                                                                                                                                                                                                        이때 Lecture 5: logistic regression에서 배웠던 Log Loss를 사용할 수 있다.                  

 Log Loss는 correct인 경우 loss를 덜 주고, incorrect인 경우 가중치를 점점 크게 주는 형태이다.

 Lecture 9에서 AdaBoost가 exponential loss를 최소화시키는 방향으로 학습을 한다고 했었는데, 이 exponential loss를 그래프로 나타내면 아래와 같다.

 

 exponential loss는 Log loss와는 달리 incorrect인 경우 가중치를 심하게 더 주는 극단적인 형태를 띤다.

 오늘 배웠던 ξ_i를 Hinge Loss라고 부르고 형태를 나타내면 아래와 같다. 

 Hinge Loss의 경우에도 미분이 불가능한 지점이 존재하지만, 참거짓을 판별하는 yy' = 0인 부분에서 미분이 가능하기 때문에 사용할 수 있다.

 

 Exponential loss는 너무 극단적이기 때문에 이상치들에 영향을 많이 받는다.

 Hinge loss는 미분값이 -1 고정이기 때문에 계산할 때 빠르다는 장점이 있다.

 log loss는 확률을 다룰 수 있기 때문에 해석하기가 쉽다는 장점이 있다.

 

4. Nonlinear SVMs and Kernels

 Kernels은 비선형 데이터를 고차원 공간으로 변환하여 선형적으로 분리 가능한 문제로 바꾸는 함수이다. 

커널 함수는 내적(inner product)을 계산하는 방식으로, 데이터를 고차원 공간으로 변환하는 기능을 한다. 커널 함수의 주된 역할은 고차원 공간에서의 내적을 계산하는 것이지만, 실제로는 직접 고차원 공간으로 변환하지 않고 이를 효율적으로 계산하는 방법을 제공한다.

 

1. 다항식 커널 (Polynomial Kernel)

 

 데이터를 비선형적으로 변환하여 고차원 공간으로 매핑하는 커널이다. 여기서 c는 상수, d는 다항식의 차수다.

2. 가우시안 RBF 커널 (Radial Basis Function Kernel, RBF)

 

 Gaussian Function를 기반으로 하는 커널로, 가장 널리 사용되는 커널이다. 데이터가 선형적으로 분리되지 않을 때 효과적이다. 여기서 σ\sigmaσ는 커널의 폭을 조절하는 매개변수이다.

 SVM은 오직 binary classification만을 해결할 수 있다. 만약 class가 2개보다 크다면, 이진 SVM을 여러 개 훈련시켜 다차원 클래스 분류 문제를 해결해야 한다.

 만약 class들이 잘 분리되어져 있다면 Logistic Regression보다 SVM을 사용하는 것이 더 효과적이다.

 

 만약 겹치는 영역이 많다면, Logistic Regression이 SVM보다 더 선호되어진다. SVM도 비슷하게 잘 되긴 한다.

 

또한 확률적 평가를 하고 싶다면, Logistic Regression을 선택해야한다.