DART: Dropouts meet Multiple Additive Regression Trees

DART: Dropouts meet Multiple Additive Regression Trees

K. V. Rashmi

Department of Electrical Engineering and Computer Science

UC Berkeley

Ran Gilad-Bachrach

Machine Learning Department

Microsoft Research

https://arxiv.org/pdf/1505.01866.pdf

ABSTRACT

MART(Friedman, 2001, 2002)는 Boosting된 Regression Tree의 Ensemble모델로 다양한 task에 대해 높은 예측 정확도를 제공하는 것으로 알려져 있으며, 실제로 널리 사용됩니다. 그러나, 이후의 iteration에서 tree가 추가될 때 몇 개의 instance의 prediction에 영향을 주고, 나머지 instance 예측에 무시하는 over-specialization 문제가 발생합니다. 이는 training data에 없는 데이터에 대해 모델의 성능이 부정적인 영향을 미치며, 초기에 추가된 training data에 모델이 overfitting하게 됩니다. 이러한 over-specialization 문제를 완화하고 해결하고자 합니다.

이 연구에서는 최근에 DNN(Deep Neural Network)에서 Training에서 제안된 dropouts을 사용하여 문제를 해결하고자 합니다. MART에서 dropout을 사용하여 DART 알고리즘을 사용하는 새로운 방법을 제안합니다. 공개적으로 이용 가능한 data-set을 사용해 ranking, regression, classification에서 DART를 평가하였으며,  MART보다 월등한 performance를 보였습니다. 또한, DART가 over-specialization 문제를 상당 극복한 것을 확인할 수 있습니다.

1 INTRODUCTION

Ensemble 기반 알고리즘은 여러 가지 ML 문제에 대해 높은 정확도를 달성하는 것으로 나타났습니다. Ensemble이 만들어진 개별 예측자(predictor)보다 더 나은 정확도를 달성하려면, predictor가 정확(accurate)해야 하며, 서로 상관 관계(uncorrelated)가 없어야 합니다. 이는 predictor가 존재할 수 있는 특정 feature 또는 instance에 대한 sensitivity를 줄임으로써, 모델의 정확성(accuracy)를 높여줍니다.

Random Forest와 같은 Ensemble 알고리즘의 일부 class는 독립적으로 ensemble하는 반면, MART나, AdaBoost는 반복적으로 predictor를 합쳐갑니다.

Boosting 알고리즘은 현재 모델을 개선하는데 중점을 둔 predictor를 추가하며, iteration 사이의 training 문제를 수정함으로써 달성됩니다. 추가된 predictor가 ensemble 모델과 다를지라도, 새로운 predictor는 일반적으로 문제의 작은 subset 초점을 맞추므로, 원래의 문제에서 측정할 때 강력한 예측력을 갖지 않습니다.

즉, 이 경우 특정 instance에 overfit하는 위험이 높아집니다. 이것은 MART와 Boosting Regression Tree에서 잘 알려진 문제 입니다. 나중에 추가되는 Tree는 단지 몇 가지 instance 예측에만 영향을 미치고, 나머지 instace에 대해서는 무시하는 상황이 발생합니다. 이는 training error에 크게 개선하지 않고, 알고리즘의 성능에 부정적인 영향을 미칠 수 있습니다. 이것은 초기에 추가된 tree에 대해서 모델이 over-sensitive하게 만듭니다. 이것은 Section 2에서 실제 data-set에서 regression 모델을 통해 자세히 설명합니다.

MART의 over-specialization의 문제를 해결하기 위해 shrinkage를 사용합니다. 여기서 새로운 tree의 contribution은 shrinkage factor라는 일정한 값(constant variable) 만큼 감소합니다. 첫 번째 tree의 영향을 줄이는 데 도움을 주지만, ensemble의 모델이 커질 수록 다시 over-specialization이 재발생합니다.

최근에 제안된 DNN에서 training 시에 사용된 dropout을 이용합니다. training 과정 중에 neural 연결의 random fraction을 줄이기 위해 dropout을 사용합니다. 따라서 network의 상위 계층 node는 prediction에 필요한 정보를 전달하기 위해 몇 개의 connection에 의존해야 합니다. 이 방법은 image processing에서 object classification에 높은 정확도를 기여했습니다.

dropout의 기법은 Logistic Regression 모델에서 성공적으로 사용되었습니다. 이 경우 dropout은 training 단계에서 입력 feature의 random fraction을 제거합니다. 이러한 접근법은 ensemble의 각 tree가 서로 다른 random 부분을 사용하여 독립적으로 training되는 Random Forest가 채택한 접근 방식과 유사합니다.

본 논문에서는 tree의 ensemble에서 dropout을 사용하는 새로운 방법을 제안한다. MART에서 이 방법을 사용하여 알고리즘 DART를 호출합니다. DART가 Ranking, Regression, Classification 각 작업에서 MART와 Random Forest 보다 성능이 뛰어남을 보여줍니다(Section 4).  

2 Overcoming the Over-specialization in MART

Section 1에서 논의했듯이, 특히 MART 알고리즘을 강화하면 over-specialization 문제 발생. Section 2에서는 CTSlice 데이터에 대한 Regression 작업의 예를 통해 DART에서 사용되는 dropout의 영향과 문제를 살펴봅니다.

그림 1은 Ensemble에서 Tree의 mean contribution을 나타내며, 주어진 training data에 대한 tree T의 mean contribution |Ex[T(x)]|로 정의된다. shrinkage가 적용되지 않은 MART 알고리즘은 single tree에서 시작되며 중요한 contribution을 가지고, 이후의 tree는 무시되어지고 있다. |Ex[T(x)]|를 사용하면 첫 번째 Tree는 Ensemble의 나머지 Tree보다 큰 contribution을 보여줍니다. 이러한 동작은 알고리즘의 내재되어 있습니다: Training data의 모든 label에 상수 값을 추가하게 되면, 첫 번째 tree만 수정되고(모든 leaves에 추가됩니다), 나머지 tree는 모델에 작은 contribution을 유지합니다. Training data의 모든 label에 constant value를 추가하면, 첫 번째 Tree만 수정되고(이 상수 값은 모든 leaves에 추가됩니다) 나머지 tree은 model에 적은 contribution을 유지합니다. 그러므로, 어떤 의미에서 첫 번째 Tree로 편향된(biased) 모델이 생성되며, ensemble의 나머지 tree는 bias의 deviation을 학습합니다. 이로 인해 ensemble은 첫 번째 Tree의 결정에 매우 민감합니다(sensitive). 이것은 그림 2에서 볼 수 있는데, 위에서 언급한 작업을 위한 3가지 방법으로 훈련된 ensemble의 tree를 묘사합니다. shrinkage를 사용하지 않은 MART 알고리즘은 첫 번째 열의 커다란 yellow 잎에 표시된대로, 대부분의 data-point에 대한 전체 prediction을 무시할 수 있는 tree를 추가한다는 것을 알 수 있습니다.

Section 1에서 논의된 것 처럼 shrinkage는 over-specialization 문제를 해결하기 위해 사용된 가장 일반적인 접근법이다. shrinkage는 각 트리의 영향을 일정한 값만큼 줄이므로, 첫 번째 트리는 문제의 전체 편향을 보완 할 수 없습니다. 그림 1과 그림 2에서 이 방법의 영향을 볼 수 있습니다. Figure 1에서는 이후의 tree의 contribution이 감소하고, shrinkage가 사용되지 않는 경우보다 훨씬 늦은 속도로 진행됩니다. 예를 들어, shrinkage가 없는 MART의 100 번째 트리의 기여도는 첫 번째 트리의 기여도보다 약 15 배 작지만 shrinkage를 포함하는 MART의이 요소는 "단지" 4 배 정도 떨어집니다. 그림 2에서 우리는 Tree가 많은 경우에 "abstains" 한다는 사실을 나타내는 커다란 노란 잎이 앙상블의 뒷부분에 나타남을 알 수 있습니다. 우리가 볼 수 있듯이 shrinkage가 사용되면 앙상블에서 나무의 기여도 차이는 점진적이지만, 여전히 주목할 만합니다.

이제 DART에서 drop-out을 사용했을 때의 효과를 살펴 보겠습니다. 그림 2의 마지막 열은 DART 알고리즘에 의해 학습 된 트리를 보여줍니다. 첫째, shrinkage가 있는 MART와 shrinkage가 없는 MART와 비교할 때, 우리는 큰 노란 잎이 훨씬 더 느리게 출현함으로 인해 상당히 느린 속도로 특화된 tree를 볼 수 있습니다. 이는 그림 1에서도 볼 수 있습니다. 여기서 반복 된 tree에서 예상되는 contribution이 크게 떨어지지는 않습니다. 따라서 개별 tree의 contribution에 대한 sensitivity가 크게 감소합니다. 동시에 Random Forest와 달리 DART는 앙상블에 있는 기존 Tree의 결함을 보완하기 위해 Tree를 계속 학습합니다. 그러나 통제 된 방식으로 다양성과 전문성 간의 균형을 유지합니다. Section 3에서 MART와 RF 모두 DART 알고리즘의 극단적인 경우로 볼 수 있습니다.

3 Description of the DART Algorithm

우리는 MART 알고리즘을 사용하여 DART를 기반으로 프리젠 테이션을 시작합니다. MART는 Gradient descent 알고리즘으로 볼 수 있습니다 : 매 iteration마다 MART는 현재 prediction에 대한 손실 함수(loss function)의 미분을 계산하고, 이러한 미분의 역함을 Ensemble 맞추는 Regression Tree를 추가합니다. 보다 공식적으로, 알고리즘에 대한 입력은 포인트 x와 점 (x, y)의 집합을 포함하며, 점 x는 공간 X에 있고 레이블 y는 레이블 공간에 있습니다. 이 알고리즘은 입력으로 진행중인 작업 (예 : 회귀, 분류, 순위 지정 등)에 맞춰진 loss generating function을 사용합니다. loss generating function과 label을 사용하여 알고리즘은 모든 x에 대해 loss를 정의합니다. 은 prediction 공간, 일반적으로 real 입니다. 예를 들어, 작업이 regression 이면 손실은 로 정의 할 수 있습니다. 여기서 y는 x의 실제 레이블입니다.

모든 반복에서, 현재 모델을 M : X → Y로 표시하고 M(x)는 포인트 x에 대한 현재 모델의 예측을 나타냅니다.

를 M (x)에서 손실 함수의 미분이라고 가정합니다. MART는 새로운 레이블 인 가 training data의 모든 포인트 x와 연관되는 중간 dataset을 생성합니다. Tree는 이 역 미분을 prediction하도록 train되고 (Loss을 최소화하기 위해) 미분의 역방향에서 한 단계로서 ensemble에 추가됩니다.

Loss을 선택하면 MART 알고리즘이 다양한 training 과제에 적용될 수 있습니다. 앞서 논의한 것처럼, squared Loss(제곱)은 Regression에서 사용됩니다. Logistic Loss Function는 Classfication 작업에 사용됩니다. 여기서, Loss function은  λ가 파라미터 인 로 정의된다. Ranking Task의 경우 Loss function은 예상 순위에서 point의 상대적인 순서에 따라 달라집니다. Ranking 작업에 대한 우리의 평가(4 절)에서 우리는 LambdaMart 방법의 정의를 사용합니다. 여기서 주요 아이디어는 Loss function의 gradient를 직접 정의하는 것입니다.

여기서 λ는 매개 변수이고 s(x, x')는 점 x와 x'의 순서를 역전하여 생기는 NDCG Loss이며 합계는 동일한 쿼리와 관련된 모든 점에 대한 것입니다.

Section 1과 2에서 논의한 바와 같이, MART가 채택한 gradient-descent style boosting은 over-specialization으로 이어질 수 있으며, 이 문제를 해결하기 위해 공통적으로 사용되는 방법은 shrinkage을 사용하는 것입니다. 이 방법에서 MART는 모든 iteration에서 새 tree를 학습 할 때 위에서 설명한대로 작동합니다. 그러나 이 새로 학습된 Tree를 ensemble에 추가하기 전에 리프(leaves) 값은 (0, 1)의 상수 값을 곱하여 크기가 감소됩니다. shrinkage은 우리가 Section 2에서 관찰 한 것처럼 특정 분야의 문제를 완화시키는 데 도움이됩니다.

이제 DART 알고리즘을 알고리즘 1로 설명합니다. DART는 두 위치에서 MART와 분기됩니다. 첫째, 다음 Tree가 들어 맞는 Gradient를 계산할 때 기존 ensemble의 random subset 만 고려됩니다. n 개의 반복 이후의 현재 모델 M이와 같다고 말하며, Ti는 i 번째 반복에서 학습 된 Tree입니다. DART는 먼저 random subset 을 선택하고 모델을 생성합니다. 이 모델이 주어지면 중간 dataset 를 생성하여 수정된 모델에 대해 loss function의 역 미분(inverse derivative)을 예측하는 Regression Tree T를 학습합니다.

DART가 MART와 다른 두 번째 위치는 DART가 정규화(normalization) 단계를 수행하는 ensemble에 새로운 tree를 추가 할 때입니다. 정규화(normalization) 단계의 근거는 새로 훈련 된 tree T가 M과 optimal predictor 사이의 gap을 줄이려고 하지만, dropped tree가 동일한 gap을 줄이려고 한다는 것입니다. 따라서 새로운 Tree와 dropped Tree를 모두 도입하면 모델이 대상을 overshooting 하게 됩니다. 또한 모델 M을 생성하는 I를 만들기 위해 ensemble에서 dropped tree 수가 k라고 가정하면 새로운 tree T는 droppend Tree 세트의 개별 tree 각각보다 대략 k 배 더 큰 크기를 가집니다. 따라서 DART는 새로운 tree T를 1 / k의 비율로 스케일링(scaling하여 dropped tree와 동일한 크기의 순서를 갖게됩니다. 다음으로, 새로운 tree와 dropped tree 를 k/(k + 1) 비율로 스케일링하고 새로운 tree를 ensemble에 추가합니다. k/(k + 1) 인수로 scaling하면 새로운 tree가 있는 경우 dropped tree와 결합 효과(effect)가 새 tree가 도입되기 전에 dropped tree의 효과와 동일하게 유지됩니다.

그림 1과 그림 2에서 볼 수 있듯이 DART는 over-specialization 문제를 줄입니다. 따라서 Tree가 drop되면 정규화(regularization)의 양을 조절할 수 있는 정규화로 볼 수 있습니다. 하나의 극단적인 경우 tree가 drop되지 않으면 DART는 MART와 다르지 않습니다. 다른 극단에서는 모든 tree가 drop되면 DART는 random forest과 다를 바 없습니다. 따라서 drop된 세트의 크기로 인해 DART는 "적극적인" MART 모드에서 "보수적 인"임의 포리스트 모드로 다양하게 전환 할 수 있습니다.

4 Evaluation

Ranking, Regression 및 Classification와 같은 세 가지 과제에 대해 DART를 평가했습니다. 각 작업마다 공개적으로 사용 가능한 대규모 데이터 세트를 사용했습니다. 평가에서는 shrinkage가 다른 DART와 MART를 비교합니다. 또한 Random Forest(RF)는 DART의 극단적인 사례로 간주 될 수 있으므로 이 알고리즘을 해당 될 때마다 비교합니다.

4.1 Ranking

MART는 Ranking 작업에 주로 사용됩니다. 예를 들어 Yahoo! learning rank challenge에서는 수상자가 LambdaMart 방법을 기반으로 boosted tree로 진행하였습니다. LambdaMart에 Section 3 에서 설명한 대로 dropout을 도입하고 MSLR-WEB10K dataset에서 이를 테스트했습니다. 이 dataset에는 10K 개의 서로 다른 query에 대해 ~ 1.2M query - URL 쌍이 포함되어 있으며 각 query의 URL을 관련성에 따라 rank를 매기는 작업이 있습니다. 136 가지 사용 가능한 feature을 이용합니다.

dataset의 60 %가 training에 사용되고 20 %는 validation에 사용되고, 20 %는 test로 사용됩니다. 우리는 train data에 대한 train과 validation 데이터에 대한 성능(performance) 비교를 통해 두 알고리즘의 다양한 parameter 값을 검사했습니다. validation 의 점수에 따라 최상의 성능을 가진 모델을 선택하고, 이를 test 세트에 적용하여 보고, 결과를 얻었습니다. 측정된 parameter는 표 1에 요약되어 있습니다. 실험한 각 Parameter 조합에 대해 3 번 위치에서 NDCG 점수를 계산하고 이를 매개 변수 값을 선택하는 기준으로 사용했습니다. NDCG(Burges et al., 2005)는 웹 랭킹 작업을 평가하는 데 사용되는 공통 척도이다. 또한 사용된 loss function은 이 metric을 최적화하도록 설계되었습니다.

표 2는 순위 지정 작업의 주요 결과를 보여줍니다. DART는 MART보다 ~ 0.4 NDCG 포인트를 얻습니다. 또한 1과 2 위치에서 NDCG 점수를 확인하면 상당한 이익을 볼 수 있습니다. (1 위는 0.2 포인트, 2 위는 0.38 포인트).

4.2 Regression

Regression 작업에 dropout을 사용하는 장점을 테스트하기 위해 UCI repository (Bache and Lichman, 2013)에서 CT slices dataset을사용했습니다. 이 dataset에는 74 명의 CT 스캔으로 생성 된 53500개의 히스토그램이 포함되어 있습니다. 작업은 이미지가 찍힌 축의 위치를 추론하는 것입니다. 각 이미지는 386 차원 특징 벡터(feature vector)로 표현됩니다. 우리는 관련된 여러 parameter에 대한 값을 스캔했으며 표 3에 요약되어 있습니다. 알고리즘을 비교하기 위해 10 fold cross validation 를 사용했습니다. 각 fold는 개인의 모든 이미지가 train dataset에 있거나 그 중 모두가 test dataset에 있도록 선택되었습니다.

Regression Tree에 대한 평가 결과는 표 4에 나와 있습니다. 모든 ensemble 크기에 대해 최상의 DART 모델은 최고의 MART와 최고의 RF 모델보다 뛰어난 성능을 나타냅니다. 우리는 DART가 모든 반복에서 하나의 tree 만 drop 하도록 제한되는 경우에도 (즉, 드롭 아웃 비율은 ") MART와 RF를 능가하는 것으로 나타났습니다.

또한 RF는 낮은 loss을 달성하기 위해 large tree가 필요하다는 것을 관찰했습니다. 예를 들어 나무의 크기가 50 및 100 잎으로 제한되는 경우, 최상의 RF 모델은 각각 44.48 및 36.29의 손실을 달성했습니다. 반면 MART와 DART는 50 개의 잎으로 구성된 Tree로 loss 값이 가장 낮습니다.

4.3 Classification

분류 작업에 대한 DART의 성능은 Pascal Large Scale Learning Challenge 5의 얼굴 탐지 (fd)데이터 세트를 사용하여 평가되었습니다.이 데이터 세트에는 30x30 gray-scale image가 포함되어 있으며, 목표는 이미지에 얼굴이 있는지 여부를 추론하는 것입니다. 우리는 훈련을위한 첫 번째 300K 예제, 검증을위한 다음 200K 예제 및 테스트를위한 다음 200K 예제를 사용했습니다. 이 작업에 대해 검사 된 매개 변수는 표 5에 요약되어 있습니다.

MART, DART 및 임의의 포리스트 모델에 대해 최상의 성능 매개 변수를 선택하기 위해 validation 집합을 사용하고 test 집합에서 이를 평가했습니다. 표 6은 분류 과제에 대한 결과를 나타낸다. MART와 DART 모두 250 tree의 ensemble로 최고 정확도를 자랑합니다. 정확도의 차이는 작지만, 두 모델이 test-set에서 1106 건의 prediction에 동의하지 않기 때문에 통계적으로 유의미하며 (P <0.0001), MART 모델은 DART 모델이 625 개가 올바른 반면 MART 모델은 481개 만 맞습니다. 모델 간의 주요 차이점은 MART가 0.665의 recall을 가지고 DART는 0.672의 recall에 있습니다. 이는 비뚤어진(skewed) 특성으로 인해 이 dataset의 중요한 차이입니다. instance의 ~ 8.6 %만이 positive로 label이 지정됩니다. Random Forest 는이 작업에 대한 정확도가 낮습니다.

5 Conclusions

dropout (Hinton et al., 2012)은 신경망 모델의 정확성을 크게 향상시키는 것으로 나타났습니다. 다른 한편, MART는 (Friedman, 2001, Elith et al., 2008)는 많은 작업 (Caruana and Niculescu-Mizil, 2006)에서 가장 정확한 모델로 밝혀졌으며, 특히 웹 (Chapelle and Chang, 2011). MART가 contribution가 크게 감소한 Tree를 추가한다는 관찰에 기인 한 우리는 dropout이 MART에 대한 효율적인 정규화(regularization)를 제공하고 DART 알고리즘을 제안 할 수 있다고 가정합니다. 실험 결과에 따르면 DART에 의해 생성 된 ensemble의 tree는 그림 1에서와 같이 최종 예측에 보다 균등하게 기여합니다. 또한 Ranking, Regression 및 Classification 작업의 정확도가 상당히 향상되었습니다.