[ML / Andrew Ng] Support Vector Machines - Large Margin Classification

우리는 이번 챕터에서 새로운 알고리즘인 SVM(Support Vector Machine)에 대해 알아볼 것이다. 이 알고리즘은 Logistic Regression을 응용해서 변형한 형태로 복잡한 비선형 함수에 대해 Logistic Regression이나 Neural Network에 비해 더 명확히 해결할 수 있는 알고리즘이다.

우선 Logistic Regression의 Cost Function을 보자. 원래는 y = 0, 1 일 때 두 상황에 다른 함수를 적용해 그래프를 곡선으로 그렸다. 하지만 SVM 에서는 조금 다른 함수를 사용하는데 cost1(z) 함수부터 확인하자면 z가 1 이상일때는 0으로 수렴시켜 대략적으로 cost를 계산한다. cost0(z) 함수는 z가 -1 이하일때만 0으로 수렴시키는 형태이다.

 

이렇게 대략적으로 함수를 표현시키는 이유는 계산상 편리함도 있고 문제를 더 최적화할 수 있기 때문이다. 자세한 내용은 후에 더 설명한다. 이렇게 부분적으로 linear하고 어느 값으로 수렴시키는 함수를 piecewise-linear 한 함수라고 하고 이를 hinge loss function 이라 부른다.

그러면 이제 SVM의 cost function을 재정의 해보자면 최적화와 별개인 m을 제거하고 lambda를 전체항에 한 번 나눠준다. 그리고 이를 C로 다시 치환시키고 첫째항을 A, 둘째항을 B라 두어 CA + B 형태의 함수가 정의된다. 이렇게 하면 C의 기울기에 따라 그래프가 그려지고 이는 최적화할때 편리하게 작동한다. 

그렇게 정의된 SVM 의 Hypothesis 함수는 위 그림과 같다. Logsitic Regression과 같이 확률로 나오는게 아닌 1 또는 0 처럼 바로 결과로 확인할 수 있다.

SVM은 Large Margin Classifier 라고도 불린다. 그 이유는 SVM의 h 함수가 Margin 이라는 여분을 갖기 때문인데 Margin이 생기는 이유는 위 그림과 같이 z가 1 이상, -1 이하일때만 cost가 0을 가지기 때문에 Logistic Regression의 기준이 0인 것과 다르게 -1과 1 사이의 margin이 생기게 되는 것이다.

만약 C를 매우 크다고 가정하면 첫번째 항인 A항은 0에 가까워져야할 것이다. 그렇게 A가 0이되는 지점이 바로 SVM의 Decision Boundary가 된다. A항이 0이 되면 cost function의 형태가 매우 단순해 지는데 theta항만 남게되어 우리는 이를 최소화시키는 방향으로 최적화하게 된다.

그렇게 생성된 Decision Boundary가 위의 검은색 직선인데 그 양옆의 파란 직선이 앞서 말했던 Margin을 결정하는 선이며 그 차이가 Margin이라 불린다. SVM은 이 Margin을 최대화하는 방향으로 최적화가 되며 직관적으로 보이듯이 분홍색, 연두색 선분보다 검은색 선분을 Decision Boundary로 결정했을때 Margin이 최대화되는 것을 확인할 수 있다.

보통 데이터와 크게 다른 데이터를 Outlier 라고 한다. 여기서 Outlier는 왼쪽 아래 빨간 X 데이터라고 할 수 있다. SVM은 이 Outlier를 얼마나 신경쓰냐에 따라서 성능이 변하게 되는데 만약 이 Outlier 까지 고려한 SVM을 설계하면 그만큼 lambda값을 줄여서 더 잘 fitting되게 해야할 것이고 그러면 C 값이 매우 커지게 된다.

 

그러면 분홍색 그래프처럼 Outlier를 잘 분류할 수는 있지만 그만큼 Margin이 작아지게 되고 Overfitting 될 가능성도 높아진다. 반대로 이를 고려하지 않은 SVM을 설계하면 lambda값을 크게 정하게 되고 C 값은 작아질 것이다. 그러면 Margin은 커지지만 그만큼 Underfitting 될 가능성도 높아진다.