multiclass svm, one vs rest, one vs one

기본적으로 svm은 이진 분류기이다. 

이진분류법을 확장해서 멀티클래스 분류를 하는 방법이 있는데 대표적으로 

one vs one approach 그리고 one vs rest approach(또는 one vs all 라고 부르기도함) 이 있다 .

1. one vs rest

전체 class의 수가 M개 라고 하면 i 번째 class의 부류 와 i클래스를 제외한 나머지 M-1개의 클래스가 속하는 클래스 로 이진화 시키고 분류기를 만들고, 이와 같은 작업을 M번 만큼 한다. 그러면 총 M 개의 이진분류기가 만들어 지게 된다.  즉 i class에 속하는 샘플을 +1 라벨을 붙이고 나머지 샘플에 -1라벨을 붙인다. 그래서 훈련집합(training set)을 만들게 된다.  svm의 결정 초평면도 M개가 만들어 지는데 j  번째 초평면을 d(j)라 할 수 있다. 

실제 Test를 할때에는 M개의 초평면에 모두 test를 하게 되는데 m번의 분류에서 1가지만 양수를 출력하고 나머지는 모두 음수를 출력한다면 문제될것이 전혀 없지만, 항상 그렇게 된다는 보장은 없다 .

따라서, m번의 test중 가장 큰 d(j)를 갖는것을 예측된 class로 한다. 

이 방법은 크게 2가지 문제를 가지고 있다. 첫번째로, 초평평값 d(j)의 크기를 단순 비교해서 값을 찾는다는것이 비합리적일 수 있다. 두번째로는 이진 분류기의 훈련집합이 불균형을 이룬다는 것이다. (1 : m-1)

2. one vs one

두번째 멀티클래스 분류방법인데 

m개의 클래스 중 2개를 선택하여 2클래스에 대한 결정 초평면을 만든다. 그렇게 되면 결정초평면과 분류기는 mC2개만큼 생기게 된다.M(M-1)/2 개 된다. 

이제 test 할때는 투표개념을 도입하여 분류하는데 새로들어온 sample x에 대해서 초평면 dij(x)가 x를 class i로 분류하면 class i에 +1점, j로 분류하면 class j에 +1 점을 준다. 즉 mC2개의 분류기가 M개의 class에 대해서 투표를 하는 것이다.  이렇게 모든 초평면에 대해서 분류하였을때 가장 높은 점수를 획득한 class가 predicted된 클래스이다. 

이때 얻을 수 있는 최대 표값은 M-1개 이고 이방법은 one vs rest가 가지고 있는 문제를 가지진 않는다. 

그러나, 클래스의 개수 M이 커지면 이진 분류기의 수가 많아지고 결국 learning 과 test에 걸리는 시간이 많아진다.

실제적으로 가장 많이 사용되는 분류방법은 2가지 단점에도 불구 하고  one vs rest 방법이다. 이진 svm을 멀티클래스 svm으로 확장하는 방법에 대한 연구도 많이 논의 중이다.