에이다부스트

에이다부스트(: adaptive boosting의 줄임말, 아다부스트는 잘못된 발음)는 Yoav Freund와 Robert Schapire가 개발한 기계 학습 메타 알고리즘이으로 이들은 AdaBoost를 개발한 공로를 인정받아 2003년 괴델상을 받았다. AdaBoost는 성능을 향상시키기 위하여 다른 많은 형태의 학습 알고리즘과 결합하여 사용할 수 있다. 다른 학습 알고리즘(약한 학습기, weak learner)의 결과물들을 가중치를 두어 더하는 방법으로 가속화 분류기의 최종 결과물을 표현할 수 있다. AdaBoost는 이전의 분류기에 의해 잘못 분류된 것들을 이어지는 약한 학습기들이 수정해줄 수 있다는 점에서 다양한 상황에 적용할 수 있다(adaptive). 따라서 에이다 부스트는 잡음이 많은 데이터와 이상점(outlier)에 취약한 모습을 보인다. 그러나 또 다른 경우에는, 다른 학습 알고리즘보다 과적합(overfitting)에 덜 취약한 모습을 보이기도 한다. 개별 학습기들의 성능이 떨어지더라도, 각각의 성능이 무작위 추정보다 조금이라도 더 낫다면(이진 분류에서 에러율이 0.5보다 낮다면), 최종 모델은 강한 학습기로 수렴한다는 것을 증명할 수 있다.
모든 학습 알고리즘이 잘 적용될 수 있는 형태의 문제가 있고 그렇지 않은 문제가 있으며, 일반적으로 주어진 데이터 집합에 대한 최고의 성능을 얻기 위해서 많은 파라미터와 설정을 조절해야 하는 반면, (약한 학습기로서 결정 트리 학습법을 이용한) AdaBoost는 종종 최고의 발군의 분류기로 불린다. 결정 트리 학습법과 함께 사용되었을 때, AdaBoost 알고리즘의 각 단계에서 얻을 수 있는 각 훈련 샘플의 상대적 난이도에 대한 정보가 트리 성장 알고리즘에 반영되어 트리가 분류하기 더 어려운 경우에 집중되는 경향이 있다.
개요.
기계학습의 문제들은 종종 차원수의 저주에 시달린다. 각 샘플은 아주 많은 숫자의 잠재적 특성(예를 들어, Viola-Jones 물체 탐지 체계에서 사용되는 하아 특징(Haar feature)의 경우 24x24픽셀 그림 윈도우에 162336개의 특성이 있을 수 있다.)들로 이루어질 수 있고, 모든 특성을 고려하는 것은 분류기의 훈련과 수행 속도를 늦출 뿐만 아니라 휴즈 효과(Hughes Effect)에 의해 예측 능력까지 떨어트리게 된다. 인공신경망이나 서포트 벡터 머신과는 다르게, AdaBoost 훈련 과정은 모델의 예측 능력을 향상시킬 것으로 생각되는 특성들만 선택하고, 이는 차원수를 줄이는 동시에 필요없는 특성들을 고려하지 않음으로써 잠재적으로 수행 시간을 개선시킨다.
훈련.
AdaBoost는 가속화 분류기를 훈련시키는 한 방법을 이르는 말이다. 가속 분류기는 다음과 같은 형태로 표현된다.
이 때, 각 formula_2는 객체 formula_3를 입력으로 받고, 그 객체가 속한 종류를 나타내는 실수를 돌려주는 약한 학습기이다. 약한 학습기 출력의 부호는 예측된 객체 분류를 나타내고 절대값은 그 분류의 신뢰도를 나타낸다. formula_4번째 분류기는 샘플 분류가 양의 부호로 예상되면 양수를, 그렇지 않은 경우 음수를 반환한다.
각각의 약한 학습기는 훈련 집합의 각각의 샘플에 대해 가설 formula_5를 출력으로 생성한다. 각각의 반복 단계formula_6에서, 하나의 약한 학습기가 선택되고 최종적인 formula_6-단계 가속 분류기의 훈련 오류의 합 formula_8가 최소가 되도록 하는 계수 formula_9가 배정된다.
여기서 formula_11는 직전 훈련 단계까지 생성된 가속화 분류기이고, formula_12는 오류 함수이며 formula_13는 최종 분류기에 더하기 위해 현재 고려하고 있는 약한 학습기이다.
가중치 설정.
훈련 과정의 각 반복 단계에서 훈련 집합의 각각의 샘플에 대한 현재 오류 formula_14와 같은 값의 가중치가 그 샘플에 배정된다. 이러한 가중치는 약한 학습기의 훈련에 영향을 미칠 수 있는데, 예를 들어 결정 트리는 높은 가중치를 가진 샘플의 집합을 나누는 것을 선호하도록 성장할 수 있다.
유도 과정.
formula_15를 가지고 있는 데이터 집합 formula_16과 각 분류기가 각 항목에 대한 분류formula_17를 출력하는 약한 분류기의 집합 formula_18을 가지고 있다고 가정하자. formula_19번째 반복 단계 이후 우리의 가속화 분류기는 다음과 같은 형태의 약한 분류기의
선형 결합(linear combination)으로 표현된다.
formula_21번째 반복 단계에서 우리는 하나의 약한 분류기에 특정 값을 곱한 후 이를 기존의 분류기에 더하여 더 나은 가속화 분류기로 확장하고자 한다.
그러면 어떤 약한 분류기가 formula_23이 되는 데 가장 좋은 선택이고, 어떤 가중치formula_24를 부여해야 하는지 결정하는 문제가 남는다. 우리는 formula_25의 총 오류 formula_26를 각 데이터 포인트에 대한 지수 손실의 합으로 아래와 같이 정의한다.
formula_28에 대하여 formula_29 , formula_30 라 두면, 아래와 같은 식을 얻는다.
우리는 이 식을 formula_23에 의해 정확하게 분류된 데이터 포인트(즉, formula_33)와 잘못 분류된 데이터 포인트(즉, formula_34)로 아래와 같이 나눌 수 있다.
이 식의 우변에서 formula_23에 의존하는 부분은 formula_37뿐이기 때문에, formula_26를 최소화하는 formula_23이 formula_37도 최소한다는 것을 알 수 있다. 즉, formula_23이 가중치를 고려한 가장 낮은 오류를 가진 약한 분류기(가중치 formula_30를 가진 것)인 것이다.
조금 전에 결정한formula_23를 가진 formula_26를 최소화하는 가중치 formula_24를 결정하기 위하여 우리는 아래와 같은 미분을 수행한다.
이를 0으로 놓고 formula_24에 대하여 풀면 다음과 같은 식이 된다.
약한 분류기의 가중치가 고려된 오류율을 formula_49와 같이 계산할 수 있고, 따라서 다음 식이 성립한다.
이렇게 함으로써 우리는 AdaBoost 알고리즘을 유도하였다. 각 반복 단계에서, 가중치가 고려된 총 오류formula_37를 최소화하는 분류기 formula_23을 선택하고, 이를 오류율 formula_53를 계산하는데 이용하고, 이를 가중치formula_50를 계산하는데 이용하며, 이를 마지막으로 가속화 분류기 formula_55 to formula_56를 개선하는데 이용한다.
가속화 개념에 대한 통계적 접근.
가속화(Boosting)는 각 샘플 formula_57의 특성이 어떤 약한 학습기 formula_58의 formula_57에 대한 결과값과 같은 선형회귀 형태를 가진다. 구체적으로, 모든 약한 학습기가 선험값(a priori)일 경우에 AdaBoost는 퇴각 적합화(backfitting) 알고리즘의 한 번의 반복단계와 같으며, 이 때 완곡화 스플라인(smoothing spline)은 formula_60의 최소점과 같다. (formula_61는 측정값에 비례하는 지수비용함수를 나타낸다) 따라서 가속화는 선형회귀의 일종이라고 볼 수 있다.
회귀 방식에서는 최소자승오차(Least square error) formula_62을 활용하여 formula_63를 일반성(generalization)을 잃지 않고 최대한 정확하게 formula_64에 맞추려고 하는 것이 일반적이다. 반면에, AdaBoost 오차함수 formula_65는 마지막 결과의 부호만이 사용된다는 점을 고려하기 때문에 오차의 증가 없이도 formula_66값이 1을 훨씬 웃돌 수 있다. 그러나, formula_67의 증가에 따른 샘플 formula_57 오차의 기하급수적 증가는 이상점에 과도한 가중치를 부여하게 된다.
지수오차함수를 사용하면 최종적응모델의 오차는 formula_69와 같이 각 단계에서의 오차의 곱과 같다. 따라서 AdaBoost 알고리즘에서 가중치 갱신은 각 단계 후에 formula_70의 오차를 재계산하는 것과 같다고 볼 수 있다.
손실함수(Loss function)은 유연하게 선택할 수 있다. 손실함수가 단조적이고 연속적으로 미분가능할 때, 분류기는 항상 알맞은 값(purer solution)에 근접한다. 장(Zhang,2004)은 최소자승을 기반으로하여 수정된 후버 손실함수(Huber loss function)을 제안하였다.
이 함수는 formula_72가 1 또는 -1에 가까울 때 로지스틱 가속(LogitBoost)보다 잘 작동한다. 본래의 최소자승기법과는 달리 신뢰구간을 벗어난 예측(overconfident prediction, formula_73)에는 페널티를 주지 않으며, 선형적으로 신뢰도(confidence)가 1보다 큰 잘못 분류된 샘플에 대해서만 페널티를 준다. 따라서 2차 또는 지수방식과는 달리 이상점에 덜 민감한 경향을 보인다.
기울기 하강(Gradient Descent)을 통한 가속화.
가속화 과정은 함수의 볼록 집합(convex set)에 대한 볼록손실함수(convex loss function)의 최소화 과정으로 볼 수 있다. 구체적으로는, AdaBoost는 지수 함수 formula_74을 통해 손실을 최소화하며, 로지스틱 가속은 로그회귀(logistic regression) formula_75를 통해 최소화를 수행한다.
기울기 하강 유추기법에서, 각 훈련값(training point)에 대한 분류기의 결과는 n차 공간에서의 점formula_76으로 간주되고, 각각의 축은 훈련샘플에, 각 약한 학습기 formula_77는 어떤 벡터의 고정된 방향과 길이에 대응되며, 최종 목적은 최소 반복을 통해 목표점 formula_78(혹은 손실함수값 formula_79)이 근처 다른 점에서보다 작은 지점)에 도달하는 것이다. 따라서 AdaBoost 알고리즘은 훈련오차(training error)의 최적화를 위해 코시 기법(Cauchy, 실험오차를 최소화하는 formula_80를 통한 formula_77를 찾는 급경사(steepest gradient) 기법) 혹은 뉴턴 기법(Newton, 어떠한 목표점에 가장 가까운 formula_82를 가지는 formula_83를 찾는 기법)을 수행하는 셈이다.
알고리즘 예시 (불연속적 AdaBoost).
다음과 같은 조건일 때:
formula_90에 대하여:
가중치 의 선택.
는 불연속적 AdaBoost에서 지수오차함수를 분석적으로(analytically) 최소화하는 값으로 정해진다.
formula_102
formula_103라 가정하였을 때, 지수함수의 볼록성(convexity)를 이용하면 다음과 같은 식을 만족한다.
formula_104
위식을 formula_9에 대하여 미분하고 상한값의 최솟값을 구하기 위해 0으로 설정한다.
formula_106
이러한 관계는 formula_107일 때만 성립한다는 것에 주의해야하지만, 이외의 경우에도 좋은 초기추측이 될 수 있다. 예로, 약한 학습기가 편향되어있거나(formula_108), 여러 결과를 가지거나(formula_109), 아니면 다른 어떤 함수일 경우(formula_110)에도 활용할 수 있다. 이러한 경우 약한 학습기와 계수는 모든 가능한 formula_111로부터 formula_112가 정해지는 단 한 번의 단계를 통해 선택될 수 있으며, 이 때의 formula_111는 어떤 수치적인 탐색기법을 통해 formula_114를 최소화하는 값으로 정해진다.
변형.
실수형 에이다부스트(Real AdaBoost).
이산 AdaBoost에서 쓰이는 분류기는 그 결과를 formula_115 의 형태로 나타낸다. 실수 AdaBoost에서는 분류의 결과를 각 클래스에 포함될 확률 formula_116 로서 나타낸다. 이는 formula_3 라는 원소가 formula_118 클래스에 포함될 확률을 나타낸다. Friedman, Hastie 그리고 Tibshirani는 고정된 formula_119에 대하여 formula_120를 최소화하는 formula_121를 유도하였다(최소제곱법).
이를 이용하면 전체 트리에 대하여 연산을 하는 대신에 잎사귀 값들을 이전 값의 로지스틱 변환의 절반을 취하는 것으로 대체할 수 있다. 이산 AdaBoost와의 가장 큰 차이점은 이산 AdaBoost에서는 결과의 신뢰도를 따로 계산해야 하지만 실수 AdaBoost에서는 약한 분류기의 신뢰도가 확률로써 그대로 표현된다는 것에 있다.
로지스틱 부스트(LogitBoost).
로지스틱 회귀분석을 이용하여 AdaBoost을 실현하는 것이 로지스틱 가속이다. formula_118 의 에러를 직접 감소시키는 대신에 다음 식에서 formula_91를 최소화하는(최소제곱법) 약한 학습기를 사용한다:
formula_129는 뉴턴의 방법를 사용하여 formula_6에 대한 로그 가능도의 오류를 최소화하는 항이다.
또한 formula_2는 최소제곱법에 의해 formula_129를 최소화하는 약한 학습기이다.
formula_133의 값은 0이나 1에 근접하게 된다. 따라서 formula_134 또한 매우 작은 값을 취하게 될 것이다. 만일 formula_135 항이 큰 값을 갖거나 안정적으로 수렴하지 않는다면 이는 샘플 formula_3가 잘못 분류되었음을 의미하게 된다. 이러한 문제는 주로 소수점 연산의 부정확성에 의하여 발생할 수 있다. 이는 formula_135의 절대값의 최댓값이나 formula_138의 최솟값을 강제로 지정함으로써 피할 수 있다.
관대한 에이다부스트(Gentle AdaBoost).
이전의 가속 방법들은 각 반복 과정에서 오류를 최소화하는 formula_2를 구하고 이를 이용해서 전체 오류를 최소화하였다 (탐욕 알고리즘).
반면에 부드러운 AdaBoost에서는 반복 횟수를 제한한다.
formula_2는 formula_141를 최소화하도록 정해진다. 여기서 다른 매개변수는 사용되지 않는다. 그렇기 때문에 약한 학습기가 완벽한 분류를 할 수 있는 상황에서 부드러운 AdaBoost은 정확한 formula_118 값을 구할 수 있다. 한편 기울기 기반의 알고리즘은 formula_143의 formula_9를 무한대에 가깝게 정하게 되고 이는 분류의 정확도를 떨어뜨리게 된다. 관대한 에이다부스트(Gentle AdaBoost)은 이러한 측면에서 Schapire 와 Singer가 지적했듯이 formula_145의 경우에 발생할 수 있는 성능 저하를 보완할 수 있다.
빠른 종료(Early Termination).
가속화 분류기의 속도를 올리는 방법 중 하나는 분류 작업을 끝까지 진행하지 않고 일정 신뢰 구간을 확보한 시점에서 미리 종료하는 것이다. 이 방법은 Viola 와 Jones의 물체 인식 프레임워크에 소개되어 있다.에 소개되어있다. 여기서는 음성 판정의 결과가 양성 판정의 결과보다 현저하게 작아지면 음성 결과들을 제외하고 연산을 수행한다. 각 반복 단계에서 절반의 음성 샘플이 연산에서 제외된다면 전체 분류기에서 연산을 수행하는 항목들은 아주 적어질 것이다. 이를 일반화시키면 원하는 거짓 양성이나 거짓 음성 비율을 달성할 수 있도록 각 단계에서 음성 결과들을 제거하는 한계치를 정할 수 있다.
통계학에서 AdaBoost를 사용할 때에 빠른 종료 기법은 과적합(overfitting)을 방지하기 위해서 쓰인다.
훈련에 사용되는 데이터 이외에 검증을 위한 데이터를 따로 준비하고, 훈련이 진행됨에 따라 검증 데이터의 정확도를 같이 확인한다. 만일 과적화가 일어났다면 훈련 데이터에 대한 판별의 정확도는 더 좋아지지만 검증 데이터에 대한 정확도는 오히려 낮아지게 된다. 이 시점을 기준으로 빠른 종료를 하게 된다.
전체 보정형 알고리즘(Totally Corrective Algorithm).
가파른 경사를 사용하는 AdaBoost화 기법에서 formula_9는 각 계층 "t"에서 테스트 오류를 최소화하도록 정해진다. 그리고 그 다음 계층은 현재 계층과 "최대한" 독립적이다 라고 할 수 있다. 이 말인 즉슨 formula_147과 formula_9이 비슷할 확률이 낮다는 것을 의미한다. 하지만 formula_147이 그 전에 등장하였던 formula_150 들과 비슷할 수는 있다. LP부스트 등의 전체 보정형 알고리즘에서는 각 단계에서의 최적화 값이 그 전에 등장한 모든 단계의 결과와 독립이 되도록 최적화가 진행된다. 이는 퇴각 적합화(backfitting)이나 선형 계획법 등을 이용해서 이루어질 수 있다.
가지치기 (전지 작업, Pruning).
가지치기는 낮은 성능을 내는 약한 분류기를 미리 제거하는 것이다. 이는 가속화 분류기의 연산 속도 및 메모리 사용량을 줄여준다. 간단하게는 낮은- 가중치, 계수, 경계값, 정확도 - 들을 가지는 분류기를 제거할 수 있고, 이는 전체 보정형 알고리즘과 함께 했을 때 효율적일 수 있다. 이 외에도 분류 결과의 다양성이 가장 높은 분류기를 제거하는 방법이 Margineantu 와 Dietterich에 의하여 제시되었다. 또한 비슷한 결과를 내는 두 분류기가 있을 때 하나를 제거하고 계수를 다른 하나에 몰아주는 방법도 있다.