[미완성][ML/이론] Support Vector Machine 에 대한 공부

Support Vector Machine

오늘 다뤄볼 주제는 SVM이다. 여러 분야에서 가장 기초적인 수준의 분류기로 쓰이고,
또 복잡한 문제에서도 적용가능하므로 그 성능이 탁월하다.

다른분들이 정리해둔 글들 중 Yoo Jaejun님의 블로그 글이 요약이 잘 되어있다.

* 주소 : http://jaejunyoo.blogspot.com/2018/01/support-vector-machine-1.html

이 분은 MIT OCW를 보고 내용을 정리하셨다고 한다. 

(https://www.youtube.com/watch?v=_PwhiWxHK8o&t=6s)

내가 주로 참고한 자료는 크리스토퍼 비숍의 '패턴 인식과 머신 러닝'이고,

그 중 챕터 7. 희박한 커널 머신이다.

'희박한' 커널 머신의 서론

우선, SVM은 희박한(sparse) 해를 갖는 커널 기반 알고리즘이며, 새 입력값에 대한 예측은 훈련 데이터 포인트의 부분집합에 대해 계산한 커널 함숫값에만 종속적이게 된다. 

'희박한' 해를 갖는다는 것의 의미가 뭘까? 때에 따라 희박한 모델이라는 표현은 어떤 계수가 0이 되는 형태의 모델을 일컫기도 한다. SVM이 희박한 해를 갖는 것은 SVM이 훈련집합의 subset, 그러니까 서포트 벡터들에 의존적인 성질을 갖는 것으로부터 기인한다.

이러한 희박성(sparsity)은 ML 알고리즘에서 유리한 성질이 되는데, 문제 크기가 증가하더라도 선형 알고리즘에 비해 coefficient가 0이 되는 변수의 수가 더 천천히 증가하기 때문에 계산이 빠르다는 장점이 있다. 응용에 있어서는, 어쨌건 SVM은 고차원에서도 효율적인 연산이 가능하다는 것을 떠올리면 좋을 것 같다. 이런 점에서 앞서 언급한 sparse와는 다소 의미가 다르지만, 추천시스템에서의 경우 high dimensional sparse dataset을 훈련집합으로 사용하게 되므로, FM 계열의 알고리즘과 마찬가지로 효율적이라고 한다. 이 건은 추후 프로그래밍을 통해 비교해보는 것은 어떨까 싶다.

SVM의 중요한 성질 중 하나는 볼록 최적화(convex optimization) 문제를 푸는 것을 바탕으로 모델 매개변수를 결정할 수 있다는 점이라고 한다. 풀어서 설명하면, local optima가 global optima가 될 수 있다는 것으로 설명된다. 사실, 이 부분을 완전히 이해하지는 못했으므로 읽어봄직한 자료를 미리 첨부해둔다. (https://wikidocs.net/book/1896)
현재 수강중인 '비선형최적화' 과목을 위해서도 해당 내용은 따로 정리할 필요가 있다.

SVM은 라그랑주 승수법(Lagrange multiplier)을 광범위하게 사용하는 머신이다. 라그랑주 승수법은 하나 또는 그 이상의 제약 조건하에서 여러 변수에 대한 함수의 임계점을 찾는 데 사용된다. 라그랑주 승수법 또한 한번 쯤 다루고 넘어가야 할 주제이다. 특히 부등식 조건에서 Karush-Kuhn-Tucker 조건을 다루게 되는데, 여러 논문에서 종종 등장하므로 관련해서 정리해보아야겠다.

SVM은 결정론적 알고리즘이다. 때문에 사후 확률을 내놓지는 않으므로, 사후 확률에 대한 출력값이 필요하다면 동일한 희박한 커널 테크닉에서는 베이지안 기반의 RVM(relevance vector machine)을 사용하거나 확률적 알고리즘을 사용해야한다.

최대 마진 분류기

아래 형태의 2클래스 분류 문제를 예시로 들도록 한다.

\[y(x)=w^T\phi(x)+b\]

\(\phi(x)\)는 고정된 특징 공간 변환을 지칭(쉽게 말해 특징벡터라고 생각하자)하며, \b는 편향 매개변수이다. 이 문제를 듀얼 표현법을 이용해 표현하면, 결과적으로는 모델 전체를 커널에 의한 표현으로 바꿔줄 수 있다는 점을 기억해두자.

일단 훈련 데이터 집합은 특징 공간상에서 선형적으로 분류가 가능하다는 가정이 필요하다. SVM은 이 가정하에 클래스 분류 문제의 해를 margin의 콘셉트를 바탕으로 접근한다. margin이란 결정 경계(decision boundary)와 표본 사이의 최소 거리를 지칭한다. SVM은 이 margin이 최대가 되는 결정 경계를 선택한다. 결과적으로 이렇게 결정된 결정 경계의 위치는 데이터 포인트들의 부분집합을 바탕으로 결정되는 것인데, 이 부분 집합을 서포트 벡터라고 한다.

\(y(x)=0\)에 해당하는 초평면으로부터 포인트 \(x\)까지의 수직 거리는 \(|y(x)/||w||\)로 주어지게 된다. 우리는 2클래스 분류 문제에서 '모든' 데이터 포인트들이 올바르게 분류될 수 있는 해에만 관심이 있다. 결과적으로 포인트 \(x_n\)으로부터 결정 표면까지의 거리는 다음과 같다. :

\[\frac{t_ny(x_n)}{||w||} = \frac{t_n(w^T\phi(x_n)+b)}{||w||}\]

margin은 데이터 집합의 포인트들 중 결정 표면에 가장 가까운 \(x_n\)으로부터 결정 표면까지의 수직 거리로 주어지며, 이 거리를 최대화하는 방식으로 매개변수 \(w\)와 \(b\)를 최적화한다. 

(추후 내용 추가)