Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably

Many equations and formulas look intimidating. However, when you hunt them down, they are definitely not! Just papertigers!

Now let's hunt the papertiger.

We will use this simple data​1​ set in all our tutorials. If we use 4th column as label, the 3rd column will be feature, vice versa.

 (1)

Gradient boost for regression

The loss function of gradient boost defined as

 (2)

Gradient boost for classification

Caveat To avoid heavy notation, we ignored summation symbol.

For a binary classificaton problem, we can define odds as

 (3)

and probability as

 (4)

You might wonder why we define this. In the following developments, you will find this definition will make the result be consistent with regression.

With some simple algebra,

 (5)

We can define our loss function as cross entropy, such that

 (6)

in which

 (7)

We want to find which can minimize the loss, in symbol,

 (8)

We could directly work on Equation 6 with gradient descent or closed-form solution, such that

 (9)

However, this will be quite complex.

We can use Taylor series to approximate the loss fucntion, you should convince yourself this will make things simpler, such that

 (10)

Caveat Caveat Two kinds of derivatives of appeared here, one is w.r.t. and one is w.r.t. .

With Equation 9, and set

 (11)

can be solved that

 (12)

With Equation 6, the first order derivative with respect to can be calculated as

 (13)

with some illustration

The second derivative of with respect to is

 (14)

Reference

1. 1.
Dana D. Sleep Data Personal Sleep Data from Sleep Cycle iOS App. Kaggle. https://www.kaggle.com/danagerous/sleep-data#

Footnotes

There are many excellent tutorials out there. Some tutorials are too intuitive and it's helpful, but you cannot get it straight on the math details. Some focused on dymestifying math. Some focused on code. I found the best tutorials that give you the conceptual ideas and are possible for implementation without being blind to the math details. Drop a comment if I failed. It would be really appreciable.

Lachlan Chen, "Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably," in EarnFromScratch, September 8, 2020, https://www.earnfs.com/en/html/2180.htm.

or

@misc{lachlanchen2020tutorial,
title=Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably,
author={Chen, Lachlan},
year=September 8, 2020
}

EarnFromScratch (September 29, 2020) Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably. Retrieved from https://www.earnfs.com/en/html/2180.htm.
"Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably." EarnFromScratch - September 29, 2020, https://www.earnfs.com/en/html/2180.htm
EarnFromScratch September 8, 2020 Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably., viewed September 29, 2020,<https://www.earnfs.com/en/html/2180.htm>
EarnFromScratch - Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably. [Internet]. [Accessed September 29, 2020]. Available from: https://www.earnfs.com/en/html/2180.htm
"Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably." EarnFromScratch - Accessed September 29, 2020. https://www.earnfs.com/en/html/2180.htm
"Hunt the papertiger from boosting to XGBoost, intuitively, mathematically, implementably." EarnFromScratch [Online]. Available: https://www.earnfs.com/en/html/2180.htm. [Accessed: September 29, 2020]