[머신러닝]SVM(Support Vector Machine) by MIT

MIT에서 진행된 Patrick Winston 교수님의 Artificial Intelligence, Fall 2010 Lec.16을 듣고 정리한 내용입니다.

 

---

들어가기에 앞서

머신러닝에서 사용되는 분류 방법은 여러가지가 있다. NN, Dicision tree(Random forest), Logistic or probit regression 등등, 그 중 SVM은 역사가 오래된 알고리즘이지만 그 논리 구조가 상당히 매력적이고 탄탄하므로 이 알고리즘이 어떠한 아이디어로 부터 유도되었는지 하나씩 알아보자. 비선형 SVM도 있지만 이 글에서는 Linear SVM만을 다룸을 미리 밝힌다.

 

 

---

Support Vector Machine

SVM이 궁극적으로 풀고 싶은 문제는 다음과 같이 정의된다. 

"How do we divide the space with decision boundaries?"

즉, 적절한 결정경계(decision boundary)를 찾아 그것을 기준으로 어떻게 공간을 나눌 것인가에 대한 고민에서 출발한다. 다음의 그림을 보자. 

그림에 보이는 +와 -를 구분하려면 어떻게 나눠야 할까? 가장 쉽게 직관적으로 생각할 수 있는 답은 아래 그림에 빨간 점선 같이 가운데 선을 긋는 것이다.

 

이 때, 노란색 선들은 두 class를 구분하는 gutter가 되고 그 사이를 street로 정의한다. 즉, street의 중앙선이 우리가 그었던 빨간 점선이 되는 것이다. SVM의 기본 아이디어는 이 street를 최대로하는 Widest Street Strategy에 기반한다. 자 이제, 위에서 정의했던 문제로 돌아 가, 적절한 결정경계(dicision boundary)는 어떻게 정하는지부터 알아보자.

 

---

Decision rule

우선은 우리가 그은 street 중심선(빨간 점선)에 수직인 벡터 w를 정의한다. 그리고 임의의 data에 대한 벡터 u를 정의한다. 우리가 궁금한 것은 이 임의의 data u가 street 기준으로 어디로 분류될지 이다. 여기서 벡터 u를 w위로 projection한 벡터의 값이 어떤 특정 상수 c보다 큰지를 기준으로 잡아보자 수식으로 쓰면 다음과 같다. 

 

좀 더 general하게 표현하면,

 

(1)

여기서 projection 개념은 사용하는데 projection 벡터가 아닌 두 벡터의 내적을 사용하는 이유는 내적을 하면 상수가 되어 위와 같이 특정 값과 직접 비교가 가능하기 때문이다. 벡터의 내적은 projection 벡터의 계수이므로 해당 내적이 특정값보다 크다는 것은 그 값을 기준으로 +로 분류되고, 작으면 -로 분류됨을 의미한다.

 

따라서 위에 수식 (1)이 우리의 decision rule이 된다. 어떤 data u가 들어왔을 때, 이 decision rule에 의해 분류되려면 w와 b를 계산할 수 있어야 한다. 이를 위해 수식 (1) 제약 조건을 추가해가는 과정을 보도록 하자.

 

---

Design constraints