Adaboost

ㅇ Adaboost 예제 동영상

ㅇ Learning Classification Functions

- 대부분의 학습 알고리즘은 분류 함수(Classification function)을 학습 시키는데 사용이 된다. 하지만 본 논문에서 사용하는 Adaboost는 주어진 특징 약 160000개 중에서 좋은 특징을 선택하는 과정이 학습 과정인 것이다. 

- Freund 와 Schapire는 강분류기의 에러는 학습 과정의 반복 횟수가 증가함에 따라 Exponentially하게 0에 접근한다는 것을 증명하였다.

- 또한 일반화 성능에 대한 더 많은 결과들이 증명되었다.(Schapire et al., 1997)

- 전통적인 Adaboost 과정은 greedy Feature 선택 과정으로 쉽게 이해 가능하다.

ㅇ Consider the general problem of boosting, in which a large set of classification functions are combined using a weighted majority vote. The challenge is to associate a large weight with each good classification function and a smaller weight with poor functions. AdaBoost is an aggressive mechanism for selecting a small set of good classification functions which nevertheless have significant variety. Drawing an analogy between weak classifiers and features, AdaBoost is an effective procedure for searching out a small number of good “features” which nevertheless have significant variety.

- 부스팅의 일반적인 문제를 고려해봤을 때 가중치를 이용해서 수 많은 특징들 중에서 좋은 특징을 찾는 것이 문제인 것이다. 수 많은 특징들은 좋은 특징도 있고 안좋은 특징도 있는데, Adaboost는 수 많은 분류기(특징 또는 약분류기)중에서 좋은 특징을 선택하는 매우 적극적인 메카니즘이다. 결론적으로 Adaboost는 수 많은 특징들 중에 작은 수의 좋은 특징을 찾기 위한 매우 효율적인 과정인 것이다.

ㅇ Weak Classifier

- 초기 과정에 선택된 특징은 0.1~0.3 사이의 에러율을 갖고, 다음 반복과정에서 선택된 특징은 분류가 더 어렵기 때문에 0.4~0.5 사이의 에러율을 가지게 된다.

--> 왜 반복하다보면 분류가 어려울까? 이유는 간단하다. adaboost에서는 매 반복마다 가중치를 갱신해주는데, 그 방법이 이전 분류기에서 제대로 분류가 안된 샘플에 대해서 가중치를 증가시켜준다. 따라서 어려운 문제를 가중치를 증가시키게 되므로 전체적으로 봤을 때 좀 더 어려운 작업을 하게 된다는 의미이다.

- 위의 수식은 약분류기를 함수 형태로 표현한 것이다.

- x는 영상의 sub-window라고 보면 될 것이다. 문제에 따라서 변경될 수 있으며, 일반적으로 입력이라고 생각하면 되겠다.

- f는 특징이다. 즉 f1(x)는 본 논문을 예제로 들면 Haar-like 특징을 x라는 부분에 씌어서 나온 결과 값이다.

- p는 부호를 의미한다. 이를 사용하는 이유는 어떤 함수에 의해 두 클래스를 분류할 경우 왼쪽이 Positive, 오른쪽이 Negative 일 수도 있으며, 그 반대의 경우일 수도 있기 때문이다. 상황에 따라서 p는 -1이거나 1이 될 것이다.

-는 임계값이다. f에 의해 획득한 값을 세타를 이용하여 positive인지 negative인지 판단하기 위한 경계값이라고 보면 되겠다. 이 값을 구하는 수식은 다음과 같다.

- 결국 의미적으로는 에러가 최소가 되는 경계값을 찾는다는 의미이다. 실제로 구현할 때는 정렬을 이용해서 구하게 된다. 자세한 사항은 위의 세미나 자료 참조..

※ 주의 : 약분류기의 성능은 에러율이 0.5보다 작아야 한다. 두 클래스 문제에서 에러율이 0.5라는 이야기는 랜덤하게 찍는다는 의미. 결국 랜덤하게 찍는 것들로 학습을 시킨듯 무슨 의미가 있겠는가? 

   

ㅇ Cascade Algorithms (케스케이드 알고리즘)

- 계산 시간을 줄이면서 검출 성능 또한 높이기 위한 방법

- 기본 아이디어

- Positive sample과  Negative sample을 구분해야 하는 경우, Adaboost에서는 여러개의 약분류기를 사용하여 결과 값을 보고 임계값 이상이면 Positive, 반대의 경우라면 Negative로 정의한다. 간단하게 비유적으로 설명하자면, 산을 걸어가고 있다고 치자. 산을 오르는 이유는 산속에 사는 다람쥐를 연구하기 위함이다. 그런데 100m 전방에 매우 큰 동물이 있다. 무엇인지는 모르겠지만, 일단 크기가 고양이 또는 맷돼지, 기타 등등.. 일 것이라고 짐작할만한 크기이다. 그렇다면 나는 다람쥐를 찾는 것이 목표인데, 굳이 100m 앞에 보이는 동물이 다람쥐인지 확인하기 위해 앞으로 가야할까? 그렇다 아예 확인할 필요조차 없다. 케스케이드 방법의 아이디어는 앞에서 설명한 것과 같이, 대충 확실히 구분되는 특징을 사용해서 비교해보고 "이건 100% 아니다"라고 판단이 서면, 굳이 더 이상 자세히 구분해볼 시도조차 하지 않는다는 것이다. 그럼으로써 속도를 높일 수 있기 때문에 케스케이드 방법을 사용한다.

결정 트리는 해당 논문을 보면 케스케이드와 관련하여 자주 등장한다. 사실 처음에는 본인도 케스케이드와 결정트리가 무슨 관련이 있을까 의문을 품었었다.

헌데  좀 더 생각해보면 매우 관련성이 깊은 것을 알 수 있다.

먼저 결정 트리의 경우 어떤 트리가 좋을까..

깊이가 깊은 즉, 트리의 차수가 높은 결정 트리가 좋은 것인가. 아니면 깊이는 낮지만 트리의 폭?이 넓은 것이 좋은것인가?

케스케이드는 어찌보면 결정트리라고도 볼 수 있다. 단 트리를 만드는 방법이 다르다고 생각한다. 먼저, 결정 트리의 경우에는 어떤 문제에 대해서 최대한 적은 분류과정을 통해 정확도 높은 분류를 하기 위한 과정이라 볼 수 있다고 한다면, 케스케이드의 경우에는 전체적으로 봤을때 최대한 적은 분류를 통해 모든 집합을 빨리 분류해보자는 의미인 듯 하다.

이해하기 힘들 수 있겠지만, 문제에 따라서 케스케이드 구조를 활용할 수도 있고, 결정트리 구조를 사용할 수도 있단 얘기이다. 항상 다 좋을 수는 없다는 것이 알고리즘의 매력인 듯하다.

우리는 남들이 말하는 머가 어디에 좋다더라. 머가 최고다. 이런 말들을 맹신하기 보다는 알고리즘의 특성과, 원리를 잘 파악해야 한다. 이러한 특성과 원리를 파악하였다면, 아마도 직접 실험하지 않아도 어떤 문제는 이걸로 풀면 잘 될 것이다 라는 예측이 가능해진다. 이 케스케이드와 결정트리에 대해서는 상당히 깊은 고찰이 필요할 것이다. 이에 대한 정확한 이해를 한다면, 아마도 어떤 문제를 부딪쳤을 경우 둘 중에 무엇으로 해결해야할지 보이지 않을까?