출처 : http://zhanpengfang.github.io/418home.html
GBDT방법은 무조건 순차적으로 모델을 개선해나가는 부스팅 방법이 핵심이다. 하지만 XGBoost는 병렬로 처리되는것을 알수있다.
위의 그림은 하나의 모델을 훈련하는 사진으로써, 비교적 고르게 Core를 모두 쓰는것을 알수있다. 모두가 100% 풀로 돌고 있지는 않지만, 이정도면 훌륭했기 때문에 그 당시에는 시대를 풍미하는 알고리즘이 될수 있었다.
그렇다면 대체 어떻게 병렬처리가 가능한것일까?
가능성 1. 분기 나뉜것을 각각 병렬처리한다.
![](http://machinelearningkorea.com/wp-content/uploads/2019/07/스크린샷-2019-07-25-오후-8.48.16.png)
바로 떠올릴수있는 방법은, 결정나무에서 위와같은 식으로 분기가 뻗쳐나갈때, 분기마다 CPU코어를 할당해서 병렬처리가 가능할수 있다. 하지만 이 방법은 효율이 좋지 않다. 분기별로 깊이가 다르기 때문에 저걸 쪼개서 할당해주는게 오히려 시간이 많이들수 있기 때문이다.
일을할때 별거아닌일을 나눠서 하는데 결국 하는놈만 하는 구조다.
![](http://machinelearningkorea.com/wp-content/uploads/2019/07/스크린샷-2019-07-25-오후-8.50.34.png)
가능성 2. 분기가 나뉘는 지점 계산을 병렬처리한다.
노드별 feature를 먼저 정렬하고 이를 통해 제일 엔트로피가 낮아지는 지점을 계산해야 하는바, 이 정렬을 하고 나누는 작업을 병렬처리 하는것이다. 차원이 어느정도 크다면, feature별로 병렬처리가 들어가니 도움이 많이 될것같다.
![](http://machinelearningkorea.com/wp-content/uploads/2019/07/스크린샷-2019-07-25-오후-8.59.13.png)
다만, 다시한번 병렬처리가 완벽히 되지는 못하고 있고 아까보다는 나은 양상이 되었다.
가능성 3. 처음부터 feature별 정렬을 한다.
생각해보면 분기가 된 상태에서 리프노드에서 정렬을 할 필요가 없다. 왜냐면 feature별 정렬은 이미 루프 밖에서도 가능하기 때문이다. 적은 양을 여러번 소팅하는것보다 많은양을 한번에 소팅한다고 의미를 이해하면 되겠다.
![](http://machinelearningkorea.com/wp-content/uploads/2019/07/스크린샷-2019-07-25-오후-9.01.07-1024x287.png)
즉 위처럼, 각 feature별로 미리 소팅을 해놓고 그다음에 추후에 잎사귀 노드에서 정렬이 필요할때 바로 쓰면 된다. 또한 처음부터 소팅을 한다면, 각 feature별로 instance(데이터의 row)는 같을 수밖에 없다. 따라서 병렬처리 해서 각각의 feature에 대한 계산을 할때 시간도 동일하게 소요가 되기 때문에, 병렬처리의 효과가 크다.
![](http://machinelearningkorea.com/wp-content/uploads/2019/07/스크린샷-2019-07-25-오후-9.02.03.png)