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