Gradient-based One-Side Sampling is a sample technique used in light GBM to increase training speed while maintaining performance, and it is useful when dealing with large data sets. In basic vanilla GBM, the gradient represents the direction and rate of the steepest descent in the error function. Larger gradient values indicate higher prediction errors meaning, they are harder to predict accurately. GOSS performs sampling based on the gradient of each data instance, retaining all instances with large gradient values and randomly sampling instances with small gradient values. This means that the model focuses more on data with high gradient values that require more attention during training, while only selecting a portion of the data with low gradient values, that is, data with smaller prediction errors. This reduces the size of the training dataset, thus speeding up the training process. Let's examine GOSS with an example. Suppose there are 10 instances. We sort them in descending order based on their gradients and set the hyperparameters A and B. GoSS selects all the top data with high gradient values,and randomly selects the lower data. The value of A represents the proportion of the top part with large gradient values, and B represents the proportion of the bottom part with small gradient values. If A is set to 0.2 and B to 0.8, 20% of the top and 80% of the bottom are selected, meaning all data is selected without omission. On the other hand, if A is set to 0.2 and B to 0.4, 20% of the top with large gradient values is entirely selected and only 40% of the bottom instances with small gradient values are randomly selected. By applying this to (1 - A) / B, we get a value of 1 when A is 0.2 and B is 0.8, and a value of 2 when A is 0.2 and B is 0.4, resulting in a two-fold amplification. This way, the model is trained by focusing on the poorly trained data. Therefore, the model performance can vary depending on how the hyperparameters A and B are adjusted. LightGBM uses GOSS to sample data. Sampling is performed considering the size of the absolute value of the residuals, which is the first-order gradients. Performance does not drop significantly. The core idea is as follows. The data points with small residuals can be excluded from training in the next iteration round. This is because the predictions are already reliable. Those that do not should be selected for further training in the next round. This is the core idea. Let me give you an example.We have the following dataset. There are feature x and target y values, and there are absolute values of residuals as follows. The total number of data points is 20. Sort the absolute values of the residuals in descending order. The result is as follows. And we set two parameters, a and b, as follows. Set top-rate, a, and other-rate, b, to 0.15 and 0.3, respectively. Let's multiply the total number of data points, 20, by the top-rate of 0.15. Then we get 3. This means that when sampling data, the top 3 with the largest residuals are definitely selected. Next, let's multiply the total number of data points, 20, by the other-rate of 0.3. Then we get 6. This means that 6 of the remaining 17 data points are randomly sampled. The top 3 data points are in topSet and the other 6 are in randSet. Training is performed using 9 sampled data points out of a total of 20 data points. Here, the residual is the first-order gradient, g. This is what Gradient-based means. Sampling is performed only on the data points with small residuals. This is what One-Side means. Sigma g is required to use the histogram-based algorithm seen in the previous video. The data ID's are 1 to 20. However, we only use 9 data points. 3 data points in the topSet and 6 data points in the randSet. To make these two similar, multiply the second term by 17 sixths. This is a kind of correction term. 6 in the denominator is 20 times b. And 17 in the numerator is 20 times 1 minus a. This correction term becomes 1 minus a over b. This is the formula, fact, in the algorithm on the left. We get a result of 2.83.The data points in topSet are given a weight of 1.0, and the data points in randSet are given a weight of 2.83. When calculating the sigma g, we apply the weights and calculate it like this. This result will be similar to the sigma g for all data points. As we saw in the previous video, we use these values to create a histogram and find the best split point. Now let's look at the Algorithm 2 presented in the paper. The capital I denotes the training data. d is the number of iteration rounds. a and b are sampling parameters.a is the ratio applied to data points with large gradient, and b is the ratio applied to data points with small gradient. And the fact is defined as 1 minus a over b. The topN is the number of data points to definitely choose. In the example on the right, it is 3. And the randN is like this. In the example on the right, it is 6. Repeat the following process d times. The preds is the prediction from the previous iteration round. And g is residual, which is the first-order gradient. Initialize the weights to 1.0. Next, we sort the absolute values of the residuals in descending order. And we construct the topSet with the topN data points with large residuals. Next, we construct the randSet by sampling randN data points from the subset consisting of small residuals. In the example on the right, we sampled 6 out of 17 data points. Then we combine topSet and randSet. And we update the weights for the data points in the randSet. In the example on the right, the w was calculated like this. We then create a new model using the sampled data, residuals, and weights.Repeating this process is the GOSS algorithm.