머신 러닝의 그라디언트 부스팅 알고리즘에 대한 친절한 소개

원문

• https://machinelearningmastery.com/gentle-introduction-gradient-boosting-algorithm-machine-learning/

 

• 그라디언트 부스팅은 예측 모델을 만드는데 있어서 가장 강력한 기술 중 하나임.
• 이 포스트에서, 당신은 그라디언트 부스팅 머신 러닝을 발견하고 어디서 파생됐는지, 어떻게 작동하는지에 대해 친절하게 소개할 것임.
• 이 포스트를 읽고 난 뒤, 당신은 알게 될 것임.
  1. 학습 이론으로 부터 부스팅의 기원과 AdaBoost.
  2. Loss function (손실 함수), Weak Learners (약한 학습기), additive model (추가적인 모델) 을 포함하여 그라디언트 부스팅이 어떻게 작동하는지.
  3. 다양한 Regularization schemes (규제 상황) 을 사용하여 기본 알고리즘보다 성능을 향상시키는 방법.

 

부스팅의 기원

• 부스팅의 아이디어는 약한 학습기를 더 좋게 되도록 수정될 수 있는지에 대한 생각에서 비롯됨.
• Michael Kearns는 목표를 "가설 부스팅 문제"라고 말하면서 실용적인 관점에서 다음과 같이 표현했음.

상대적으로 열악한 가설들을 아주 좋은 가설들로 전환하는 효율적인 알고리즘.

— Thoughts on Hypothesis Boosting [PDF], 1988

 

• 약한 가설과 약한 학습기는 성능이 무작위적인 Chance (기회) 보다 약간 더 나은 것으로 정의됨.
• 이러한 아이디어는 머신 러닝 문제의 복잡성을 조사하기 위한 framework (프레임워크) 인 확률 정확도 교정 (Probability Approxima -tely Correct (PAC))  또는 Leslie Valiant의 무료 배포 작업을 바탕으로 작성됨.
• 가설 부스팅은 관측치들을 Filtering (거르는) 아이디어였으며, 약한 학습기가 다룰 수 있는 그러한 관측치들을 남기고 남겨진 어려운 관측치들을 다룰 수 있는 새로운 약한 학습들을 개발하는데 집중함.

이 아이디어는 약한 학습 방법을 여러 번 사용하여 일련의 가설들을 얻는 것임. 각 가설은 이전의 가설들이 어렵고 잘못 분류한 것들에 집중한 예들에 다시 집중함. ... 그러나 이러한 것들이 어떻게 행해질 수 있는지 명백하지 않음.

— Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, page 152, 2013

 

AdaBoost, 첫 번째 부스팅 알고리즘

• 응용프로그램에서 좋은 성공으로 보는 부스팅의 첫 번째 구현은 Adaptive (적응할 수 있는) 부스팅 또는 줄여서 AdaBoost임.

부스팅은 거칠고 중간 정도의 부정확한 규칙을 결합하여 매우 정확한 예측 규칙을 만드는 일반적인 문제를 나타냄.

— A decision-theoretic generalization of on-line learning and an application to boosting [PDF], 1995

 

• AdaBoost의 약한 학습기들은 스스로의 결점에 대한 의사결정 단속 (decision stumps) 이라고 하는 단일 분할 (single split) 을 가진 의사결정나무 (decision tree)임.
• AdaBoost는 관측치들에 가중치를 가함으로써 작동하며, 분류하기 어려운 instances에 가중치를 더하고 이미 잘 다뤄진 instances는 가중치를 덜 함.
• 새로운 약한 학습기들가 연속적으로 추가되어 더 어려운 패턴에 대한 학습에 집중함.

이러한 점은 분류하기 어려운 샘플들이 알고리즘이 이러한 샘픋를을 정확하게 분류하는 모델을 정의할 때 까지 더 크게 증가하는 가중치를 받는 다는 것을 의미함.

— Applied Predictive Modeling, 2013

 

• 예측들은 약한 학습기들의 예측의 다중 투표 (majority vote) 에 의해 만들어지며, 약한 학습기의 예측들은 각 약한 학습기의 정확도에 의해 가중치가 적용된 것임.
• AdaBoost 알고리즘의 가장 성공적인 형식은 이진 분류 문제들에 대한 것이고, AdaBoost.M1이라고 불렸음.
• 아래의 Post에서 AdaBoost 알고리즘에 대해 더 배울 수 있음.

Boosting and AdaBoost for Machine Learning.

 

그라디언트 부스팅으로써 AdaBoost의 일반화

• AdaBoost, 그리고 그와 관련된 알고리즘들은 Breiman이 ARCing 알고리즘이라고 부르는 통계 프레임워크에서 재구성됨.

Arcing은 Adaptive Reweighting과 Combining을 합친 단어의 약자임. arcing 알고리즘의 각 단계는 [분류기]와 [가중치 입력]의 재계산 (recomputation) 에 이어 가중치 최소화로 구성됨.

— Prediction Games and Arching Algorithms [PDF], 1997

• 이 프레임워크는 Friedman에 의해 추가로 개발됐으며, 그라디언트 부스팅 머신이라고 불렸음.
• 나중에 그라디언트 부스팅 또는 그라디언트 트리 부스팅이라고 불림.
• 통계 프레임워크는 절차 (Procedure) 와 같은 Gradient descent (기울기 하강) 을 사용하여 약한 학습자를 추가함으로써 모델의 손실을 최소화하는 수치 최적화 문제로 cast (부양) 함.
• 이 클래스의 알고리즘은 단계별 추가 모델로 설명되었음. 이는 한 번에 하나의 새로운 약한 학습기가 추가 되고 모델 내 기존의 약한 학습기가 동결되어 변경되지 않은 상태로 유지되기 때문임.

이런 단계별 전략은 새로운 단계가 추가될 때 이전에 입력한 단계를 재조정하는 단계별 방법과 다른 것을 주목해야함.

— Greedy Function Approximation: A Gradient Boosting Machine [PDF], 1999

 

• 이 일반화를 통해 회귀 분석, 다중 클래스 분류 등을 지원하기 위해 이진 분류 문제를 뛰어 넘는 기술로 확장하여 임의적으로 미분가능한 손실 함수들이 사용되도록 하였음.

 

그라디언트 부스팅이 어떻게 작동하는지

• 그라디언트 부스팅은 세 가지 요소를 수반함.
  1. 최적화되는 손실 함수
  2. 예측을 만드는 약한 학습기
  3. 손실 함수를 최소화하는 약한 학습기를 추가하는 추가적인 모델

1. 손실 함수

• 사용된 손실 함수는 해결되는 문제의 유형에 따라 다름. 손실 함수는 미분가능 해야하지만, 많은 표준 손실 함수가 지원하며 당신 스스로 정의할 수 있음.
• 예를 들어, 회귀분석은 Squared error (제곱 오류) 를 사용할 수 있으며 분류는 대수 (logarithmic) 손실을 사용할 수 있음.
• 그라디언트 부스팅 프레임워크의 이점은 새로운 부스팅 알고리즘은 사용될 수 있는 각각의 손실 함수에 의해 도출 될 필요가 없으며, 대신 미분할 수 있는 손실 함수가 사용될 수 있는 충분히 일반적이라는 것임.

2. 약한 학습기

• 의사결정나무는 그라디언트 부스팅에서 약한 학습기로써 사용됨.
• 특히 회귀 나무를 사용하여 분할에 대한 실제 결과 값을 출력하고   예측에서 잔차를 수정할 수 있음.

Specifically regression trees are used that output real values for splits and whose output can be added together, allowing subsequent models outputs to be added and “correct” the residuals in the predictions.

• 나무들은 탐욕적 방식으로 만들어지며, 손실을 최소화하거나 Gini 같은 순수지표를 기반으로 가장 좋은 분할 지점들을 선택함.
• 초기에 AdaBoost의 사례 같은, 매우 짧은 의사결정나무에서 decision stump (의사결정 단속) 단일 분할만 사용됐음.
• 더 큰 나무들은 일반적으로 4 ~ 8 수준으로 사용될 수 있음.
• 약한 학습기들을 계층, 노드, 분할 또는 잎 노드의 최대 갯수와 같은 특정한 방법으로 제한하는 것이 일반적임.
• 이 것은 학습기들을 약하게 남아 있게 하지만, 여전히 탐욕적 방식으로 만들어질 수 있음을 보장하기 위한 것임.

3. 추가적인 모델

• 나무들은 한 번에 하나만 추가되고, 모델 내 기존 나무들은 바뀌지 않음.
• 기울기 하강 절차는 나무가 추가될 때 손실을 최소화하는 데 사용됨.
• 전통적으로, 기울기 하강은 회귀방정식의 계수들 또는 신경망의 가중치들 같은 파라미터들의 집합을 최소화하는 데 사용됨.
• 에러 또는 손실을 계산한 후에, 가중치들은 해당 에러를 최소화하도록 갱신됨.
• 파라미터들 대신에, 우리는 약한 학습자 하위 모델 또는 더 구체적인 의사결정나무를 가지고 있음.
• 손실을 계산한 후에 기울기 하강 절차를 수행하기 위해서, 우리는 손실을 감소시키는 모델 (그라디언트를 따르는 모델) 에 나무를 추가해야함.
• 우리는 트리를 파라미터화 한 다음 파라미터를 수정하고 잔차 손실을 감소시킴으로써 올바른 방향으로 이동하여 이 작업을 수행함.
• 일반적으로 이 방법은 기능적 (functional) 기울기 하강 또는 함수 (function) 를 이용한 기울기 하강이라고 불림.

비용을 최적화 하는 분류기의 가중치 조합을 만드는 한 가지 방법은 함수 (function) 공간안에서 기울기 하강 하는 것임.

— Boosting Algorithms as Gradient Descent in Function Space [PDF], 1999

 

• 그런 다음 새로운 나무에 대한 결과 값은 모델의 최종 결과를 수정하거나 향상시키기 위해 기존 일련의 나무들의 결과에 추가됨.
• 고정된 수의 트리들은 일단 손실이 수용가능한 수준까지 도달하거나 외부 validation 데이터셋에서도 더이상 향상되지 않으면 추가되거나 훈련을 멈춤.

 

기본 그라디언트 부스팅의 향상

• 그라디언트 부스팅은 탐욕적 알고리즘이며, 훈련 데이터셋에서 빠르게 과적합될 수 있음.
• 알고리즘의 여러 부분에서 패널티를 주고 일반적으로 과적합을 감소시킴으로써 알고리즘의 성능을 향상시키는 Regularization (정규화) 방법의 이점을 얻을 수 있음.
• 이 구역에서 우리는 기본적인 그라디언트 부스팅의 4가지 향상된 기능을 볼 것임.
  1. 나무 제한
  2. 축소 (Shrinkage)
  3. 무작위 샘플링
  4. 패널티 학습

1. 나무 제한

• 약한 학습자가 기술을 가지고 있지만 약함을 유지하는 것이 중요함. 나무들을 제한 할 수 있는 많은 방법이 있음.
• 좋은 일반적인 휴리스틱 (Heuristic, 발견적 방법) 은 더 제한된 나무의 생성은 모델에 더 많은 나무가 필요 할 것이며, 반대로 덜 제한된 나무들일수록 더 적은 나무가 필요할 것이라는 사실임.
• 다음은 의사 결정 나무의 구성에 도입될 수 있는 몇 가지 제한들임.
  1. 나무의 수 : 일반적으로 모델에 더 많은 나무들을 추가하는 것은 천천히 과적합 될 수 있음. 조언은 향상이 더 이상 관찰되지 않을 때까지 나무 추가를 유지하는 것임.
  2. 나무 깊이 : 더 깊은 나무들은 더 복잡한 나무들이며, 더 짧은 나무들이 선호됨. 일반적으로, 더 좋은 결과들은 4 ~ 8 수준에서 관찰됨.
  3. 노드 또는 잎의 수 : 깊이 처럼, 이 것은 나무의 크기를 제한 할 수 있지만, 다른 제한들이 사용된다면 대칭 구조로 제한 되지 않음.
  4. 분할 별 관측치의 수 : 분할을 고려하기 전에 훈련 노드에서 훈련 데이터의 양에 대한 최소 제한을 부과함.
  5. 손실의 최소 향상도 : 추가되는 나무의 모든 분할의 향상에 대한 제한임.

2. 가중치 갱신

• 각 나무의 예측들은 연속적으로 함께 추가됨.
• 이 합계에 대한 각 나무의 기여도는 알고리즘에 의한 학습 속도를 늦추기 위해 가중치를 적용할 수 있음.
• 이 가중치는 축소 (Shrinkage) 또는 학습률이라고 함.

각 갱신은 간단하게 "학습률 파라미터 v"의 값에 의해 조정됨.

— Greedy Function Approximation: A Gradient Boosting Machine [PDF], 1999

 

• 그 영향은 학습이 느려진다는 것이며, 결국 모델에 더 많은 나무들을 필요로 하고, 결국 훈련하는 데 더 오래 걸리며, 나무의 수와 학습률 사이에 트레이드-오프 구성이 제공될 것임. 

[학습률] v의 값이 감소하는 것은 [나무의 수] M에 대한 가장 좋은 값이 증가함.

— Greedy Function Approximation: A Gradient Boosting Machine [PDF], 1999

 

• 0.1 ~ 0.3 범위의 작은 값 뿐만 아니라 0.1보다 더 작은 값을 가지는 것이 흔함.

확률적인 (Stochastic) 최적화에서 학습률과 유사하게,
축소는 각 나무의 영향을 감소시키고 모델을 향상시키는 미래의 나무에 대한 공간을 남김.

— Stochastic Gradient Boosting [PDF], 1999

 

3. 확률적 그라디언트 부스팅

• 배깅 앙상블과 랜덤 포레스트에 대한 큰 통찰력은 훈련 데이터셋의 하위샘플들에서 나무들이 탐욕적으로 만들어질 수 있도록 해줌.
• 이 동일한 이점은 그라디언트 부스팅 모델들내 일련의 나무들 사이의 상관관계를 감소시키기 위해 사용될 수 있음.
• 이 부스팅의 다른 형태를 확률적 그라디언트 부스팅이라고 부름.

매 반복마다 훈련 데이터의 하위 샘플이 전체 훈련 데이터셋에서 무작위로 (비복원추출로) 뽑혀짐. 그런다음 무작위로 선택된 하위샘플은 기존 학습기에 적합시키 위해서 전체 샘플 대신에 사용됨.

— Stochastic Gradient Boosting [PDF], 1999

 

• 사용될 수 있는 확률적 부스팅의 몇 개 다른형태가 있음.
  1. 각 나무를 만들기 전에 행을 서브샘플링.
  2. 각 나무를 만들기 전에 열을 서브샘플링.
  3. 각 분할을 고려하기 전에 열을 서브샘플링.
• 일반적으로 데이터의 절반만 선택하는 것과 같은 공격적인 서브 샘플링은 이득이 되는 것으로 나타남.

사용자 피드백에 따르면, 열 서브샘플링 사용은 전통적인 행 서브샘플링 보다 과적합을 예방함.

— XGBoost: A Scalable Tree Boosting System, 2016

 

4. 패널티 받은 (Penalized) 그라디언트 부스팅

• 추가적인 제한들은 파라미터화된 나무들에 부과될 수 있음.
• CART와 같은 고전적인 의사결정나무는 약한 학습기로써 사용되지 않음. 대신에 잎 노드 (또는 터미널 노드) 에 수치형 값들을 가지고 있는 회귀 트리라고 불리는 수정된 형태가 사용됨.
• 나무 잎의 값들은 일부 문서에서 가중치라고 불리기도 함.
• 이와 같이, 나무의 잎 가중치 값들은 다음과 같은 유명한 규제 함수들을 사용하여 규제될 수 있음.
  1. L1 가중치 규제
  2. L2 가중치 규제

추가적인 규제 용어 (Term) 는 과적합을 피하기 위해 최종 학습된 가중치를 부드럽게 하는 데 도움이 됨. 직관적으로 규제된 목적은 간단하고 예측있는 함수를 실행하는 모델을 선택하려고 할 것임.

— XGBoost: A Scalable Tree Boosting System, 2016

 

요약

• 이 포스트에서 당신은 머신 러닝의 예측 모델링을 위한 그라디언트 부스팅 알고리즘을 발견했음.
• 구체적으로 당신은 다음과 같은 것들을 배웠음
  1. 학습 이론의 부스팅과 AdaBoost의 역사.
  2. 어떻게 그라디언트 부스팅 알고리즘이 손실 함수, 약한 학습기와 추가적인 모델을 가지고 동작하는지.
  3. 규제를 가지고 그라디언트 부스팅의 성능을 향상시키는 방법.