Multiclass SVM - one vs all / one vs one

출처 : http://ddiri01.tistory.com/category/machíne%20lèarning

위의 사이트에서 가져 왔습니다.

 

speech corpora를 제작함에 있어 DB생성 후 error detection을 할때 쓰려고 classifier를 사용하려 한다. 오류를 분류하려고 svm 을 사용할 때 방법을 검색해 보았더니 아래 방법이 나왔다.

----------------------------------------------------------------------------------------

 

기본적으로 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으로 확장하는 방법에 대한 연구도 많이 논의 중이다. 

 

-------------------------------------------------------------------------------------------

 

하지만 성능은 one vs one(ovo) 방법이 더 좋다고 한다. 또한 ovo 방법은 class 별로 모델을 모두 만들어야 하기때문에 복잡한 계산과정이 진행되어 test시 연산량이 많다. 이에 속도가 개선된 방법으로 DAG SVM(directed acyclic graph SVM) 방법이 있다고 하니 그것도 살펴 봐야 되겠다.