XGBoost(Boosting / Gradient Boosting Algorithm(GBM) / Adaptive boosting)

Boosting

• 약한 분류기를 결합하여 강한 분류기를 만드는 과정
• 어떤 모델이 유효한지, 적절한지를 찾아내는 과정
• 배깅과 유사하게 초기 샘플 데이터로 다수의 분류기를 만들지만 배깅과 다르게 순차적
• 무작위성이 없으며 강력한 사전 가지치기 사용

 * 약한 분류기의 특징은 바로 오분류율이 0.5에 가깝다

 

---

Gradient Boosting Algorithm(GBM)

• examples: LightGBM, CatBoost, XGBoost
• Gradient Boosting = Residual Fitting

Gradient Boosting에서는 Gradient가 현재까지 학습된 모델의 약점을 드러내는 역할을 하고, 다른 모델이 그걸 중점적으로 보완해서 성능을 Boosting한다. 위에서는 L2 손실함수등 미분만 가능하다면 다른 손실함수도 얼마든지 쓸 수 있다는 것이 장점이다. 부스팅 알고리즘의 특성상 계속 약점(오분류/잔차)을 보완하려고 하기 때문에 잘못된 레이블링이나 아웃라이어에 필요 이상으로 민감할 수 있다. 이런 문제에 강인한 L1 Loss나 Huber Loss를 쓰고자 한다면 그냥 손실함수만 교체하면 된다. 손실함수의 특성은 Gradient를 통해 자연스럽게 학습에 반영된다.

 

optimize a cost function over function space by iteratively choosing a function (weak hypothesis) that points in the negative gradient direction. This functional gradient view of boosting has led to the development of boosting algorithms in many areas of machine learning and statistics beyond regression and classification.(wiki)

 

---

Adaptive boosting

• ex: AdaBoost
• 다수결을 통한 정답 분류 및 오답에 가중치 부여
• 가중치를 부여한 약 분류기(Weak Classifier)를 모아서 최종적인 강 분류기(Strong Classifier)를 생성하는 기법
• 학습 과정에서  각각의 샘플들에 대해 가중치를 두고 모델링을 하여 다음 학습시 이전에 처리하지 못한 샘플들을 adaptive하게 더 잘 풀도록 개선하는 특성이 있다. 그래서 Adaptive Boosting 인 것
• adaptive 하게 피쳐에 가중치들이 변하면서 각 스테이지별로 선형 분류가 다르게 나타나도록 함.
•  

---

XGBoost:

gbm 의 속도 문제 해결하기 위해 전산 속도와 모델 성능에 초점 맞춤. gbm에 비해 좀더 좋은 성능을 보여줌.

 

 

장점:

1. 병렬 처리사용 -> 속도빠름. 또한 gbm보다 높은 정확도.

2. 유연성이 좋다. 평가함수를 포함하여 다양한 커스텀 최적화 옵션을 제공. xgboost 분류기 결론부 아래에 다른 알고리즘을 붙여서 앙상블 학습이 가능하다. 

3. 계속 훈련하기 때문에, 이미 적합화된 모델을 새로운 데이터에 적용이 가능.

4. gbm과 다르게 over fitting 방지하기위해 변수의 regularized를 사용 -> 정확도 높여줌.

 

* Let Y = w1 * M1(x) + w2 * M2(x) + w3 * M3(x) + error

Greedy Algorithm 사용, 각각의 classifierM1, M2, M3 을 찾고, 분산처리를 사용하여 빠른 속도로 적합한 weights(w1, w2, w3)를 찾는 알고리즘이다. Classifier은 Regression Score을 사용하여 accuracy score 를 측정하고, 각 순서에 따라 strong classifier부터 weak classifier 까지 랜덤하게 생성된다. 이렇게 만든 classifier를 tree라고하며 각각을 조합한 것을 forest 라고 한다. 이것이 boosting algorithm의 원리이다. 

 

xgboost는 트리를 만들떄 CART(Classification And Regression Trees)라 불리는 앙상블 모델을 사용한다. 이후 tree 부스팅을 사용, weights를 최적화한다. 리프노드 하나에 대해서만 디시젼 벨류를 갖는 decision tree와 달리, CART는 모든 리프들이 모델의 최종 스코어에 연관되어 있다. 따라서 의사결정트리가 분류를 제대로 했는지에 초점을 맞추는것과 달리 CART는 같은 분류 결과를 갖는 모델끼리도 모델의 우위를 비교할 수 있다. (스코어 비교). 모든 트레이닝 세트 X에 대해 포레스트에 넣고, 결과값으로 나오는 스코어의 절대값을 더한다. 많은 데이터를 +와 - 의 방향으로 보낼수록 좋은 분류모델이라 할수 있다. 

 

 

 

              

 

Abstract

• Tree boosting은 매우 효과적이고 머신러닝 방법에서 많이 사용됨
• 유연하고 end-to-end tree bootsting 시스템인 XGBoost
• sparse한 data를 위한novel sparsity-aware algorithm과 approximate tree learning를 위한 weighted quantile sketch를 제안
• cache access 패턴, data compression, sharding에 대한 인사이트 제공
• XGBoost의 가장 중요한 요인 : 모든 시나리오에 대한 확장성
  • 단일 시스템에서 사용한 기존 일반적 솔루션보다 10배 이상 빠르게 실행
  • 분산 또는 메모리가 제한된 상황에서도 수십억 가지의 예제로 확장
• XGBoost의 확장성은 여러 중요한 시스템과 알고리즘 최적화로 구성됩니다
  • Sparse data를 handling하기 위한 novel tree learning algorithms
  • qunatitle sketch procedure를 사용해 approximate tree learning에서 인스턴스 가중치를 처리할 수 있음
  • 병렬 및 분산 컴퓨팅으로 학습 속도가 빨라져 model ex-ploration이 빨라짐
  • out-of-core(core를 벗어난? 넘어선?) 계산을 이용하고 데이터 과학자가 데스크탑에서 수억개의 예시를 처리할 수 있게함
• weight에 기반하면 Adaboost(못 맞추는 것에 대한 weight), error를 미분한 gradient에 기반하면 gradient boost가 됨

• Feature Importance : tree 계열의 알고리즘에서 각 attribute가 얼마나 유용한지를 판단하는 feature importance를 계산할 수 있음. 하나의 decision tree에서 각각의 attribute로 이루어진 split point에 의해 얼마나 트리의 성능이 올라가는지를 계산함. instance가 split point에 의해 영향을 받는지 숫자만큼 가중치를 두어 성능 향상치를 계산함. 앙상블 모델(RF)은 모든 decision tree에 대해 구하고 평균을 냄. 성능 측정은 지니계수 또는 information gain을 사용
• 욕심쟁이 알고리즘을 사용해 분류 모델 M, G, H를 발견하고 분산처리를 통해 적합한 비중 파라미터를 찾음!
• 분류기는 Regression Score를 사용해 정확도 스코어를 측정하고 각 순서에 따라 강한 분류기부터 약한 분류기까지 랜덤하게 생성! => 분류기가 트리임
• xgboost를 tree를 만들 때 CART라 불리는 앙상블 모델을 사용. 모든 리프들이 모델의 최종 스코어와 연관되어 있어서 같은 분류 결과를 갖는 모델끼리도 모델의 우위를 비교할 수 있음
• 트리 가지를 나누는 시점에서 information gain을 순차적으로 계산한 후, 점수가 마이너스일 때 가지를 잘라냄
• xgboost가 빠른 이유는 폭 방향으로 성장하기 때문. 각 레벨에서 한번만 정렬, traverse 가능
  • 또한 sorted features는 cache

 

파라미터

---

2-1. 일반 파라미터

• booster : 어떤 부스터 구조를 쓸지. gbtree, gblinear, dart
• n_jobs : 몇 개의 쓰레드를 동시에 처리. default는 많이
• num_feature : feature 차원의 숫자를 정해야 할 경우. default는 많이

2-2. 부스팅 파라미터 : 트리마다 가지를 칠때 적용하는 옵션 정의.

• eta : learning rate로 boosting step마다 weight를 줘서 부스팅 과정에 오버피팅이 일어나지 않도록 함
• gamma : infromation gain에서 r로 표현한 값. 이 값이 커지면 트리 깊이가 줄어들어 보수적인 모델이 됨
• max_depth : 한 트리의 maximum depth. 커질수록 모델의 복잡도가 커짐. default는 6이고 이 경우 리프 노드의 개수는 최대 2^6
• lambda(l2 reg-form) : l2의 weight로 숫자가 클수록 보수적인 모델
• alpha(l1 reg-form) : l1의 weight로 숫자가 클수록 보수적인 모델

2-3. 학습 과정 파라미터 : 최적화 퍼포먼스 결정.

• objective : 목적함수로 reg:linear(linear - regression), binary:logistic(binary-logistic classification), count:poisson(count data poison regression) 등 다양함
• eval_metric : 모델의 평가 함수, rmse, logloss(log likelihood), map(mean average precision) 등
• seed : 시드값 고정

2-4. 커맨드 라인 파라미터

• num_rounds : boosting 라운드를 결정. 랜덤하게 생성되는 모델이니 만큼 이 수가 적당히 큰게 좋음. epoch 옵션과 동일

3. 실제 동작과 팁

파라메터를 제대로 이해하고 있어야 모델을 구축하는데 시행착오가 적어진다. 

parameter priority tip:

1. boostere (부스터 모양)

2. eval_metric (평가 함수) / objective (목적 함수)

3. eta (러닝 게이트)

4. L1 form (L1 regularization 폼이 L2 보다 아웃라이어에 민감하다)

5. L2 form

 

4. 결론

xgboost는 빠르고, 쓰기 편하고, 직관적인 모델. 실무에서 피쳐를 생성하고, 테스트하고, 튜닝하는 과정에서 쓰기 좋은 툴이다.

 

 

 

 

 

 

 

 

 

참고:

 

 

 

 

 

source:

https://brunch.co.kr/@snobberys/137

XGBoost 사용하기

https://zzsza.github.io/data/2018/07/03/xgboost/

https://m.blog.naver.com/PostView.nhn?blogId=tjdudwo93&logNo=221071886633&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://www.slideshare.net/freepsw/boosting-bagging-vs-boosting

 

https://3months.tistory.com/368

https://4four.us/article/2017/05/gradient-boosting-simply