[MXML-11-07] Extreme Gradient Boosting (XGBoost) [7/9] - Approximate Algorithm for Split Finding

*** Dubbing: [ English ] [ 한국어 ] This is part 7 of a series on XGBoost. In this video, we'll look at the Approximate Algorithm for Split Finding. In the previous videos, we looked at the Exact Greedy algorithm for regression and classification. The Exact Greedy algorithm has the advantage of being able to find accurate optimal split points. However, if there is a lot of data, it takes a long time, and if the data is too large to fit all in memory, the optimal split points cannot be found. In the paper, the Approximate Algorithm and Weighted Quantile Sketch Algorithm were proposed to solve this problem. In this video, we will look at the Approximate Algorithm and implement it in code to see the effects of this algorithm. First, let's look at what was presented in the XGBoost paper. In Chapter 2, the Exact Greedy Algorithm for Split Finding is presented as Algorithm 1. Chapter 3 introduces Split Finding Algorithms, and section 3.2 introduces the Approximate Algorithm. The exact greedy algorithm is very powerful since it enumerates over all possible splitting points greedily. However, it is impossible to efficiently do so when the data does not fit entirely into memory. And section 3.3 introduces the Weighted Quantile Sketch Algorithm. We'll look at this algorithm in the next video. In this video, we will look at the Algorithm 2, Approximate Algorithm for Split Finding. #ExtremeGradientBoosting #XGBoost #GreedyAlgorithmforSplitFinding #Approximate Algorithm #ApproximateAlgorithmforSplitFinding