[ML/DL 스터디] <Classification - 2> Support Vector Machine (SVM)

Reference

https://iai.postech.ac.kr/teaching/machine-learning
https://iai.postech.ac.kr/teaching/deep-learning
위 링크의 강의 내용에 기반하여 중요하거나 이해가 어려웠던 부분들을 정리하여 작성하였고,
모든 강의 슬라이드의 인용은 저작권자의 허가를 받았습니다.

또한, 모든 내용은 아래 Notion에서 더 편하게 확인하실 수 있습니다.
>>노션 링크<<

 

Keywords

• SVM
• band, slack variable, margin

 

오른쪽의 그림과 같이 Perceptron은 초평면(hyperplane)을 separate할 수 있는 많은 경우의 수 중 단 하나만을 찾아낼 수 있을 뿐임.

⇒ 이러한 방식으로 찾아낸 Linear Separator가 가장 좋은 기준이라고는 장담할 수 없다.
따라서, 더 나은 separator를 찾기 위해 SVM, Logisitic Regression이라는 방법을 이용.

 

SVM → distance(거리) 개념을 이용해 separator가 max margin을 가지도록 함.

Logistic Regression → 모든 data point에 대해 distance가 최대가 되도록 Optimize하여 Regression 수행.

 

SVM

그래서 $g(x)=0$ 으로부터 양쪽으로 일정 크기의 margin(band, slab)를 가지는 그러한 $\omega$를 찾는 문제로 바꾸는 것이 SVM의 아이디어.

위와 같은 식처럼, margin이 b인 부등식에서 b를 넘겨 $\omega$ 만 찾는 것으로 바꿀 수 있음. (unknown의 개수 줄임)

 

그래서 결국 문제는 training data에 포함되는 모든 data point가
$g(x)<-1, g(x)>1$ 을 달성하도록 하는 것으로 변경되었다.

이렇게 문제를 설정하게 되면 모든 data point가 $g(x)=0$ 로부터 항상 일정 거리만큼 떨어짐을 만족한다.

 

그리고 위 사진과 같이 Perceptron과 크게 다를 것 없는 결과를 얻을 수 있다.

위에서 정의한 문제는 Outlier에 대한 고려가 없다.

현재 상태로는 outlier가 존재할 경우 답이 나오지 않기 때문에, outlier를 고려하여 문제를 설정하기 위해
Slack variable이라는 것을 정의하여 contraints를 relax할 필요가 있다.

Outlier가 존재한다는 것을 여기서 다른 말로, non-separable하다는 것이다.

 

여기서의 Slack variable인 $u, v$는, outlier에 대한 constraint를 relax하기 위한 방침.

위의 식에서 볼 수 있듯, $u_1, u_2…u_N$ 같이 해당 class의 모든 data point에 대한 slack variable이 존재하고,

그 linear한 합을 minimize하는 문제로 변경된다.

이러한 문제 설정에 따라 optimization을 수행하면 다음과 같은 결과가 나온다.

 

outlier를 고려하여 적절한 위치에 separator가 배치되었으나, margin이 너무 작은 것이 문제.

margin이 작으면 generalize가 부족한 것. (new data에 대한 prediction 능력 부족)

 

따라서, 위에서 이용했던 거리 개념을 다시 상기하며,

margin인 $\frac{2}{||\omega||_2}$도 같이 최대화시키는 문제로 변경한다.

 

최종적으로 위와 같은 문제가 되고, 저러한 결과가 나오는 것.

(여기서 $\gamma$는 어느 정도의 margin과 outlier를 포용할 것인지에 대한 trade-off의 강도를 조절하는 parameter라 생각하면 되겠다.)

margin은 separator에서 가장 가까운 각 class의 하나의 data point까지의 거리임.
(minimum distance)
따라서 SVM은 각 class의 하나의 data point에 따라 결정된다고 보면 됨.