# GlassBoost: A Lightweight and Explainable Classification Framework for Tabular Datasets
## 3 Decision Trees and Gradient-Boosting Machines (GBMs)
### Decision Tree Ensembles
\[l(y_{i},\hat{y}_{i}^{(t)})\simeq l(y_{i},\hat{y}_{i}^{(t-1)})+g_{i}f_{t}(x_{i} )+\frac{1}{2}h_{i}f_{t}^{2}(x_{i}), \tag{9}\]  
\[g_{i}=\frac{\partial l}{\partial\hat{y}_{i}^{(t-1)}}, \tag{10}\]\[h_{i}=\frac{\partial^{2}l}{\partial(\hat{y}_{i}^{(t-1)})^{2}}. \tag{11}\]  
By substituting Equation (9) into Equation (3), the objective function of the GBM is rewritten as Equation (12). \[\mathcal{L}^{(t)}=\sum_{i=1}^{n}\biggl{[}l(y_{i},\hat{y}_{i}^{(t-1)})+g_{i}f_{t }(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})\biggr{]}+\omega(f_{t}). \tag{12}\]  
As \(l(y_{i},\hat{y_{i}}^{(t-1)})\) is not dependent on \(f_{t}\), thereby not affecting the optimisation process, it can be omitted. A specific regularisation term, \(\omega(f_{t})\), is defined as follows:  
\[\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}\omega_{j}^{2}, \tag{13}\]  
where \(T\) represents the number of leaves in the tree, \(\omega_{j}\) denotes the weight of leaf \(j\), and \(\gamma\) and \(\lambda\) are regularisation parameters for the number of leaves and weights, respectively. A GBM algorithm incorporating this term for regularisation is known as extreme gradient boosting, or XGBoost for short. This enables the objective function to be rewritten as Equation (14). \[\mathcal{L}^{(t)}=\sum_{i=1}^{n}\biggl{[}g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_ {t}^{2}(x_{i})\biggr{]}+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}. \tag{14}\]  
Minor modifications to the optimisation function are required before optimisation. We substitute \(f_{t}(x)\) with \(\omega_{q(x)}\), where \(q(x)\) is a function that maps an input \(x\) to a specific leaf index (from 1 to \(T\)). \(\omega\) is a vector of leaf weights, where \(\omega_{j}\) is the prediction value (score) assigned to the \(j^{th}\) leaf. For example, \(q(x_{i})=j\) indicates that data point \(x_{i}\) belongs to the leaf \(j\), meaning its predicted value is \(\omega_{j}\). The new optimisation function is written as Equation (15). \[\mathcal{L}^{(t)}=\sum_{i=1}^{n}\biggl{[}g_{i}\omega_{q(x_{i})}+\frac{1}{2}h_ {i}\omega_{q(x_{i})}^{2}\biggr{]}+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_ {j}^{2}. \tag{15}\]  
Since all data points in the same leaf \(j\) have the same weight \(\omega_{j}\), we can reorganise the sum to group terms by leaf. To do so, we need to define the following:  
\[I_{j}=\{i|q(x_{i})=j\}, \tag{16}\]  
\[G_{j}=\sum_{i\in I_{j}}g_{i}, \tag{17}\]  
\[H_{j}=\sum_{i\in I_{j}}h_{i}. \tag{18}\]  
Applying Equations (16)-(18) to Equation (15) provides the following:  
\[g_{i}=\frac{\partial l}{\partial\hat{y}_{i}^{(t-1)}}, \tag{10}\]0  
By substituting Equation (21) into Equation (20), Equation (22) is obtained. Equation (22) serves as a metric to assess the quality of the tree structure \(q(x_{i})\). \[g_{i}=\frac{\partial l}{\partial\hat{y}_{i}^{(t-1)}}, \tag{10}\]1  
For a given tree structure, both \(g_{i}\) and \(h_{i}\) are propagated to their respective leaves and summed. Equation (22) evaluates the quality of the tree. This score is similar to the impurity measure in a decision tree but also accounts for the complexity of the model. Ideally, we would enumerate all possible trees and select the best one. However, this is computationally intractable, so the optimisation algorithm refines the tree one level at a time instead. When splitting a leaf into two, the gain score is calculated from Equation (23) (see XGBoost documentation in [31]):  
\[g_{i}=\frac{\partial l}{\partial\hat{y}_{i}^{(t-1)}}, \tag{10}\]2  
In Equation (23), the first term represents the score of the newly created left leaf, the second term corresponds to the score of the right leaf, the third term is the score of the original leaf, and the fourth term accounts for the regularisation of the additional leaf. If the total gain is less than the regularisation parameter, it is preferable not to add the branch. This approach enables pruning to be performed simultaneously during the training of boosting trees.