Adaptive Boosting의 약자.
Ensemble-based Classifier의 일종으로 본다.
영상을 인식하기 위하여 영상의 특징을 weak classifier를 반복적으로 적용하는 방법으로 찾아나가는 알고리즘이다. 이렇게 하면, weak classifier가 strong classifier가 된다.
아다부스트는 다음과 같이 작동한다.
처음에는 weak classifier가 아무(random) data N개를 training하고서 testing을 수행한다. 이 때 data들의 weight은 모두 동일하게 1/N. 이렇게 해서 하나의 선을 그릴 수 있게 된다. 우리는 이 선을 h1(x)라고 부를 수 있다.
이 때 제대로 분류해내지 못하는 데이터들이 발생할 것이다. 이 때의 오류값을 1이라고 부른다. 그리고 오류값에 의해 해당 classifier의 신뢰도인 1도 구할 수 있게 된다. 이 신뢰도는 기하학적으로 그래프상의 선h1(x)의 기울기를 결정한다고 생각한다.(따라서 1*h1(x)) 어쨌든 이 신뢰도에 따라 잘 분류해내지 못한 데이터들의 가중치(weight)가 높아지게 된다. 즉 신뢰도와 가중치는 같은 말이다. (== weight) 이러한 특징 때문에 adaptive라는 이름이 붙었다. 잘못 검출된 데이터에 가중치를 주어 정확도를 높이려는 것이다. 약분류기들을 한 번에 하나씩 순차적으로, 단계적으로 학습시킬 때, 먼저 학습된 분류기가 잘못 분류한 것에 대한 정보를 다음 분류기의 학습 시 사용하여 이전 분류기의 단점을 보완한다. 즉, 이전 분류기가 오분류한 샘플의 가중치를 adaptive하게 바꾸어가면서 잘못 분류되는 데이터에 더 집중하게 된다.
첫번째 단계의 마지막으로 강분류기를 업데이트하여 첫번째 weak classifier의 결과를 반영한다.
두번째 단계에서도 weak classifier들이 데이터들을 training하고 testing하여 선 h2(x)를 결정한다.
이 때의 데이터들은 weight가 조금씩 다를 것이다. 즉 선 h2(x)는 weight가 더 높은 데이터로 조금씩 더 편향된다. 이렇게 함으로써 이전 단계에서 잘 구분해내지 못한 데이터에 대해 조금씩 잘 구분해나가는 방향으로 변화되어 간다.
하지만 이 단계에서도 여전히 제대로 구분하지 못하는 데이터들이 발생할 것이다. 그것이 기존의 데이터일수도 있고 새로운 데이터에 대해서 그럴 수도 있다. 어쨌든 이렇게 발생한 데이터에 대해서도 오류값과 신뢰도를 구하여 다시 weight를 조정하게 된다. 마지막으로 이 단계에서의 결과가 강분류기에 다시 업데이트된다.
이러한 과정을 계속 반복하여 최종적으로 강분류기의 성능이 높아지게 된다. 예측 성능이 조금 낮은 약한 분류기들을 조합하여 최종적으로 좀 더 좋은 성능을 발휘하는 하나의 강한 분류기를 만들게 되는 것이다. 약분류기들이 상호보완적인 방식(adaptive한 방식)으로 학습해나가고, 이 약분류기들을 조합하여 하나의 강력한 성능을 가진 강분류기를 만들어내는 것. 이러한 특징 때문에 boosting이라는 이름이 붙었다.
강분류기를 수식으로 나타내면 다음과 같다.
신뢰도를 의미하는 수식은 다음과 같다.
이므로 ㄱ의 범위를 01이라고 가정한다면, 신뢰도는 -22의 값의 범위를 가진다.
결과적으로,
미검출되는 표지판의 개수가 점차 감소한다고 볼 수 있다.
AdaBoost 역시 Random Forest처럼 의사 결정 트리 기반의 (tree-based) 모델이다. 하지만 Random Forest처럼 각각의 트리들이 독립적으로 존재하지는 않는다. 예를 들어, 아래의 상황에서 ‘+’와 ‘-’들을 구분해 내는 것이 목적이라고 가정하자.
AdaBoost는 첫 번째 의사 결정 트리를 생성한다. 좌측에서부터 약 1/5 지점을 기준으로 왼쪽은 ‘+’, 오른쪽은 ‘-’라는 아주 단순한 결정을 내린다. 한번 그은 선으로는 최선의 결과이긴 하지만, 이 결정은 두 기호를 완벽하게 분리하지 못한다. 세 개의 ‘+’들이 ‘-’라고 잘못 지정되었다. 우리는 틀린 것을 또 틀리고 싶지는 않다. 다음번에는 저 세 개의 ‘+’들을 정확하게 맞추기 위해서 ‘가중치’를 크게 조정한다. ‘가중치’가 상향되었으니, 틀리면 다른 이미 맞춘 기호들을 틀리는것보다 피해가 크다. 재조정된 ‘가중치’로 AdaBoost는 두번째 의사 결정 트리를 생성한다.
저번에 놓친 +들이 더 커진 것을 볼 수 있다.
이번에는 우측에서 약 1/5 지점을 기준으로 왼쪽은 ‘+,’ 오른쪽은 ‘-’라는 결정을 내린다. 역시 한 번의 선으로 나눌 수 있는 최선의 결과이고, 세 개의 ‘+’들을 모두 맞추기는 했지만, 이번에는 세 개의 ‘-’가 +라고 잘못 지정되었다. AdaBoost는 같은 과정을 반복한다.
이번에는 상단으로부터 약 1/3 지점의 가로선을 기준으로 기호들이 나뉜다! 기호들의 ‘배점'을 주의 깊게 살펴본다. 첫번째와 두번째 의사 결정 트리에서 성공적으로 맞춘 세 개의 기호들의(원으로 표시되어있는) 배점은 줄어든 반면에, 두번째 트리가 틀린 기호들의 배점은 또다시 상향 조정되었다.
이처럼 트리들이 생성되었으니, 이제는 Random Forest와 같이 생성한 트리들을 합칠 차례다. 세가지 트리들을 합친다면 …
위와 같은 다소 복잡한 경계들이 형성되고, 훨씬 더 정확한 예측을 할 수 있게 된다.
Random Forest와 AdaBoost의 근본적인 차이는 각각의 트리를 생성하는 방식에 있다. Random Forest는 각각의 트리들이 상당히 우수하다. 퀴즈 프로그램에 나간다고 생각한다면, 국어, 수학, 역사, 음악, 미술, 체육 등 각기 다른 분야에 우수한 전교 5등과 함께 출전하는 것과 같은 원리다. Random Forest 같은것은 필요 없고, AdaBoost만 쓰면 될까? 그것은 아니다. AdaBoost, 확실히 정확도는 높지만 팀을 구성하는데 오래 걸린다. Random Forest의 트리들은 여러 대의 컴퓨터로 만들 수 있어서 연산적인 측면의 어드밴티지가 있다. 그래서 시간적인 제약이 많은 현실 세계에서는 Random Forest가 많이 사랑받고 있는 이유다.
Cascade Algorithms (케스케이드 알고리즘)
- 계산 시간을 줄이면서 검출 성능 또한 높이기 위한 방법
- 기본 아이디어
- Positive sample과 Negative sample을 구분해야 하는 경우, Adaboost에서는 여러개의 약분류기를 사용하여 결과 값을 보고 임계값 이상이면 Positive, 반대의 경우라면 Negative로 정의한다. 간단하게 비유적으로 설명하자면, 산을 걸어가고 있다고 치자. 산을 오르는 이유는 산속에 사는 다람쥐를 연구하기 위함이다. 그런데 100m 전방에 매우 큰 동물이 있다. 무엇인지는 모르겠지만, 일단 크기가 고양이 또는 맷돼지, 기타 등등.. 일 것이라고 짐작할만한 크기이다. 그렇다면 나는 다람쥐를 찾는 것이 목표인데, 굳이 100m 앞에 보이는 동물이 다람쥐인지 확인하기 위해 앞으로 가야할까? 그렇다 아예 확인할 필요조차 없다. 케스케이드 방법의 아이디어는 앞에서 설명한 것과 같이, 대충 확실히 구분되는 특징을 사용해서 비교해보고 "이건 100% 아니다"라고 판단이 서면, 굳이 더 이상 자세히 구분해볼 시도조차 하지 않는다는 것이다. 그럼으로써 속도를 높일 수 있기 때문에 케스케이드 방법을 사용한다.
reference
참고가 될 수도 있을 법한 것들
