서포트 벡터 머신(Support Vector Machine, SVM)
`서포트 벡터 머신(Support Vector Machine, SVM)`은 고차원 데이터의 분류 문제에 굉장한 성능을 보이는 모델이다. 또한 SVM은 2차 방정식으로 formulation을 한다. 즉, `2차 계획법(quadratic programming)`으로 문제를 해결한다. 대부분 문제를 풀때 training data에 대하여 분류 성능을 최대화하기 위해 노력한다. 그러나 training data에 너무 맞춰진 모델은 과적합의 위험이 있으며, 알려지지 않은 데이터에 대한 성능(generalization ability)도 좋아야 한다. 여기서 generalization ability와 fitting to the training data에는 trade-off 관계에 있다. SVM은 훈련 데이터에 대한 성능이 높아질수록, generalization ability 또한 최대화할 수 있는 모델이다.
Separating Hyperplane
이진 분류 문제를 생각해보면, 두 개의 클래스를 나누는 `hyperplane`을 찾는 것이 목적이다. 2차식에선 직선이 되며, 3차식에선 면이 되며, 4차식부터는 이를 hyperplane이라고 부른다. hyperplane의 일반식은 다음과 같다. 이진 분류 문제에서 두 class를 나누는 hyperplane은 무한히 많은데, 어떤 hyperplane이 가장 "좋은" hyperplane이 되는지의 기준이 필요하다.
SVM에서 추구하는 이 기준은 바로 `margin`이다. 즉, training data에서 margin을 최대화하는 hyperplane을 찾는 것이며, 이는 곧 generalization error는 최소화는 hytperplane이다. 여기서 margin은 각 클래스에서 가장 가까운 관측치 사이의 거리를 말한다. margin은 w(기울기)로 표현이 가능하다. class 2를 +1, class 1을 -1이라고 했을 때의 hyperplane은 다음과 같이 표현이 가능하다. 이 상황에서 좋은 hyperplane은 각 클래스에서 가장 가까운 관측치의 plus-plane, minus-plane과의 margin이 최대가 되는 것이다.
이를 수학적으로 풀이하면 다음과 같다.
결국 SVM은 margin을 최대화하는 W와 b를 찾는 모델이다. 그러나 W의 L2-norm이 제곱근을 포함하고 있기 때문에 계산이 어려워 계산상의 편의를 위해 다음과 같은 형태로 목적함수를 변경한다. 목적함수를 변경하여도 답은 모두 동일하다.
Convex Optimization Problem
- Decision variable은 W와 b
- Objective function은 separating hyperplane으로부터 정의된 margin의 역수
- constraint는 training data를 완벽하게 separating하는 조건
- Objective function은 quadratic, 제약식은 linear → quadratic programming → convex optimization → 전역최적해 존재
- Training data가 linearly separable한 경우에만 해가 존재함
Lagrangian Formulation
SVM의 Convex Optimization Problem은 `Lagrangian mulitplier`를 이용하여 `Lagrangian Primal` 문제로 변환이 가능하다. minimum 부분이 Lagrangian Primal에 해당하며 Convex, continuous이기 때문에 미분 = 0에서 최소값을 가진다. 따라서 이를 미분하면 다음과 같다.
이제 max에 해당하는 Lagragian multiplier 부분을 확인한다.
Lagrangian Dual
W가 결국 목적 함수에서 없어지면서 maxmin 문제는 Dual 문제로 바뀌게 되었다.
- Original problem formulation(primal formulation)보다 풀기 쉬운 형태
- Objective function은 quadratic, constraint는 linear → quadratic programming → convex optimization → globally optimal solution exists(전역최적해 존재)
- Optimization 문제가 x들의 `inner product`만으로 표현됨 → `Nonlinear SVM`으로 확장할 때 좋은 성질
Lagrangian dual problem의 최적해가 되기 위해선 `KKT(Karush-Kuhn-Tucker) conditions`를 만족해야 한다.
Characteristics of the Solutions
x가 `support vector`인 경우에만 alpha 값이 0보다 크거나 같아지므로 다음과 같이 나타낼 수 있다. 즉, support vector만을 이용하여 `optimal hyperplane(decision boundary)`를 구할 수 있다.
또한 다음과 같이 임의의 support vector 하나를 이용하여 b 값을 구할 수 있다.
Classifying New Data Points
Training Data를 통해 W와 b를 계산하였으면 새로운 데이터에 대한 분류를 시행할 수 있다.
이를 수학적으로 표현하면 다음과 같다.
이 포스팅은 고려대학교 산업경영공학부 김성범 교수님 유튜브의 핵심 머신러닝 강의를 듣고 작성한 글입니다.
(이미지 출처 : 핵심 머신러닝)
