# Simplistic Write-Up of XGBoost Algorithm

I was wondering whether anybody could check through my very simplistic (e.g., no detail of greedy split finding algorithm) write-up of the XGBoost algorithm for binary classification.

Algorithm: XGBoost for Binary Classification

Input: $\mathbf{X}$, $N \times p$ feature matrix
Input: $B$, number of iterations
Input: $\eta$, learning rate
Input: $\gamma$, minimum loss reduction required to make a split
Input: $\lambda$, weight regularisation parameter
Input: $d$, maximum tree depth
Input: $s$, subsample ratio of columns

1. Initialise $f_0(\mathbf{x}_i) = \underset{\gamma}{\text{arg min}} \sum_{i=1}^{N} l(y_i, \gamma)$.
2. For $b=1$ to $B$:

(i) Randomly subsample $\lfloor sp \rfloor$ of the $p$ covariates.

(ii) Use a greedy split finding algorithm to grow a tree $f_b$ from the subsampled covariates of max-depth $d$ which minimises $\sum_{i=1}^N l(y_i, \hat{y}_i^{(b-1)} + f_b(\mathbf{x}_i)) + \gamma T_b + \frac{1}{2} \lambda ||\mathbf{w}_b||^2$.

3. The log-odds predictions are given by $\hat{y}_i = \sum_{b=1}^B \eta f_b(\mathbf{x}_i)$.

Notationally, $\hat{y}_i^{(b)}$ represents the prediction of $y_i$ at the b-th iteration, $T_b$ represents then number of leaves on the b-th tree and $\mathbf{w}_b$ represents the weights of the leaves on the b-th tree. The differentiable convex loss function is given by $l(y_i, \hat{y}_i^{(b)}) = y_i \hat{y}_i^{(b)} - \log(1 + \exp(\hat y_i^{(b)}))$.

• First of all: the 'X' is one certain implementation of Gradient Boosting so I would rather recommend to name your code 'GBoost for classification' (there are others like H2O by amazon and you do not name it H2OGBoost either, right?). Secondly: You could write it down that way but then the question is: where is the gradient in your gradient boosting? Until now you abstractly say: choose the next tree so that it compensates the error of the 'model so far' as good as possible. How exactly do you want to do that? What is the target variable with which you train the next tree? Commented Apr 25, 2018 at 10:17