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
- Initialise $f_0(\mathbf{x}_i) = \underset{\gamma}{\text{arg min}} \sum_{i=1}^{N} l(y_i, \gamma)$.
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$.
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)}))$.
