XGBoost

Input: training set ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{N}}$, a differentiable loss function ${\displaystyle L(y,F(x))}$, a number of weak learners ${\displaystyle M}$ and a learning rate ${\displaystyle \alpha }$.

Algorithm:

1. Initialize model with a constant value:

   ${\displaystyle {\hat {f}}_{(0)}(x)={\underset {\theta }{\arg \min }}\sum _{i=1}^{N}L(y_{i},\theta ).}$

2. For m = 1 to M:
   1. Compute the 'gradients' and 'hessians':

      ${\displaystyle {\hat {g}}_{m}(x_{i})=\left[{\frac {\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}}\right]_{f(x)={\hat {f}}_{(m-1)}(x)}.}$

      ${\displaystyle {\hat {h}}_{m}(x_{i})=\left[{\frac {\partial ^{2}L(y_{i},f(x_{i}))}{\partial f(x_{i})^{2}}}\right]_{f(x)={\hat {f}}_{(m-1)}(x)}.}$

   2. Fit a base learner (or weak learner, e.g. tree) using the training set ${\displaystyle \displaystyle \{x_{i},-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}\}_{i=1}^{N}}$ by solving the optimization problem below:

      ${\displaystyle {\hat {\phi }}_{m}={\underset {\phi \in \mathbf {\Phi } }{\arg \min }}\sum _{i=1}^{N}{\frac {1}{2}}{\hat {h}}_{m}(x_{i})\left[-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}-\phi (x_{i})\right]^{2}.}$

      ${\displaystyle {\hat {f}}_{m}(x)=\alpha {\hat {\phi }}_{m}(x).}$

   3. Update the model:

      ${\displaystyle {\hat {f}}_{(m)}(x)={\hat {f}}_{(m-1)}(x)+{\hat {f}}_{m}(x).}$

3. Output ${\displaystyle {\hat {f}}(x)={\hat {f}}_{(M)}(x)=\sum _{m=0}^{M}{\hat {f}}_{m}(x).}$