30:T6b6,## Elements of Tree Learning

> ### Objective > ${tex.block` Obj = \underbrace{\sum_{i=1}^n l(y_i, \hat{y}_i)}_{\text {Loss Function}} + \underbrace{\sum_{k=1}^K \Omega (f_k)}_{\text {Regularization}} \\~\\ `} > * Loss function: measures how well model fit on training data. Optimizing training loss encourages predictive models. Fitting well in training data at least get you close to training data which is hopefully close to the underlying distribution. > * Regularization: measures complexity of trees. Optimizing regularization encourages simple models. Simpler models tends to have smaller variance in future predictions, making prediction stable.

> > ### Model
> assume there are K trees > ${tex.block` \hat{y_i} = \sum_{k=1}^K f_k (x_i) \quad f_k \in \mathcal{F} \leftarrow \text {Space of Regression trees } \\~\\ `} > ### Complexity of a Tree > In xgboost, we continuously perform feature splitting to grow a tree. Each time a tree is added, it is actually learning a new function to fit the residual of the last prediction. After k trees have been trained, each leaf node on different trees will have a corresponding score. We only need to add up the scores corresponding to each tree to obtain the predictvie value. > ${tex.block` \hat{y} = \phi (x_i) = \sum_{k=1}^k f_k (x_i) \\~\\ where \quad \mathcal {F} = \left\{ f(x) = w_{q(x)} \right\}, \ w \in R^T, \ q: R^d \to \left\{1,2, \cdots, T \right\} \\~\\ `} > * ${tex`w_{q(x)} `}: the leaf weight of the tree > * ${tex`q `}: the structure of the tree > ${tex.block` \Omega (f_t) = \gamma \underbrace{T}_{\text {number of leaves}} + \frac{1}{2} \lambda \underbrace{\sum_{j=1}^T w_j^2}_{\text {L2 norm of leaf scores}} \\~\\ `}31:Td08,

## Additive training > Similar to GBDT, xgboost also needs to accumulate the scores of multiple trees to obtain the final prediction score (each iteration is to add a tree to fit the residual between the predictive result of the previous tree and the true value).

> ### Start from constant prediction, add a new function each time > ${tex.block` \hat{y_i}^{(0)} = 0 \\~\\ \hat{y_i}^{(1)} = f_1(x_i) = \hat{y_i}^{(0)} + f_1(x_i) \\~\\ \hat{y_i}^{(2)} = f_1(x_i) + f_2(x_i) = \hat{y_i}^{(1)} + f_2(x_i) \\~\\ \cdots \\~\\ \hat{y_i}^{(t)} = \sum_{k=1}^t f_k(x_i) = \hat{y_i}^{(t-1)} + f_t(x_i) \\~\\ `} > * ${tex`\hat{y_i}^{(t)}`}: Model at training round t > * ${tex`\hat{y_i}^{(t-1)}`}: Keep functions added in previous round > * ${tex`f_t(x_i)`}: New function at training round t >

> ### Find a function ${tex`f`} to optimize the objective > ${tex.block` Obj^{(t)} = \sum_{i=1}^n l(y_i, \hat{y_i}^{(t)}) + \sum_{i=1}^t \Omega (f_i) \\~\\ = \underbrace{\sum_{i=1}^n l \left(y_i, \ \hat{y_i}^{(t-1)} + f_t(x_i) \right) + \Omega (f_t)}_{{\color{red} \text {Goal: find } f_t \text { to minimize this part} }} + constant \\~\\ `} > > When we consider square loss as the loss function, the formula above can be transferred to: > ${tex.block` Obj^{(t)} = \sum_{i=1}^n \left(y_i - (\hat{y_i}^{(t-1)} + f_t(x_i)) \right)^2 + \Omega (f_t) + constant \\~\\ = \sum_{i=1}^n \left[(\hat{y_i}^{(t-1)} -y_i)^2 + 2(\hat{y_i}^{(t-1)} -y_i) f_t (x_i) + f_t (x_i)^2 \right] + \Omega (f_t) + constant \\~\\ `} > > ${tex`(\hat{y_i}^{(t-1)} -y_i)`} is usually called residual from previous round.

> ### Taylor Expansion Approximation of Loss function

> ${tex.block` f(x+\Delta x) \simeq f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2} \\~\\ f(x)\Rightarrow l\left(y_{i}, \ \hat{y}_{i}^{(t-1)}\right) \mapsto \left(\hat{y}^{(t-1)}-y_{i}\right)^{2}, \quad \Delta x \Rightarrow f_{t}\left(x_{i}\right) \\~\\ `} > Take Taylor expansion of the objective > ${tex.block` O b j^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}\left(x_{i}\right)^{2}\right]+\Omega\left(f_{t}\right)+ constant \\~\\ `} > > where ${tex`g_i`} and ${tex`h_i`} are first and second order gradient statistics on the loss function: > ${tex.block` g_{i}=\partial_{\hat{y}^{(t-1)}} l\left(y_{i}, \hat{y}^{(t-1)}\right) \\~\\ h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right) `} > > In terms of square loss > ${tex.block` g_{i}=\partial_{\hat{y}^{(t-1)}}\left(\hat{y}^{(t-1)}-y_{i}\right)^{2}=2\left(\hat{y}^{(t-1)}-y_{i}\right) \\~\\ h_{i}=\partial_{\hat{y}^{(t-1)}}^{2}\left(\hat{y}^{(t-1)}-y_{i}\right)^{2}=2 \\~\\ `} > _Note: In round t, ${tex`y_i`} is a actual value. ${tex`\hat{y_i}^{(t-1)}`} can be calculated by ${tex`\hat{y_i}^{(t-2)} + f_{t-1} (x_i)`} in round t-1. ${tex`f_t`} is the function that the model learns._ > After removing the constants from the objective function: > ${tex.block` \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}\left(x_{i}\right)^{2}\right] + \Omega\left(f_{t}\right) \\~\\ where \quad g_{i}=\partial_{\hat{y}^{(t-1)}} l\left(y_{i}, \hat{y}^{(t-1)}\right), \quad h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right) \\~\\ `}32:T434,> ### Structure Score > ${tex.block` O b j^{(t)} \simeq \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\~\\ =\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\lambda \frac{1}{2} \sum_{j=1}^{T} w_{j}^{2} \\~\\ =\sum_{j=1}^{T}\left[\left(\sum_{i \subset I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \subset I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \\~\\ `} > where ${tex`I_j`} is the set of samples on each leaf node j (${tex`I_j = \left\{i|q_{(x_i)} = j \right\}`})

> Define ${tex`G_j = \sum_{i \in I_j} g_i \quad H_j = \sum_{i \in I_j} h_i \\~\\`} > The final objective function: > ${tex.block` \sum_{j=1}^T \left[ G_jw_j + \frac{1}{2} (H_j + \lambda) w_j^2 \right] + \gamma T \\~\\ \Rightarrow w_j^{*} = - \frac{G_j}{H_j + \lambda} \\~\\ `} > Put ${tex`w_j^{*}`} back in the objective function: > ${tex.block` \large Obj = - \frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j + \lambda} + \gamma T \\~\\ `}33:[] 2e:{"title":"ML | 8 XGBoost","cells":[{"id":0,"value":"# ML | 8 XGBoost\n

","pinned":false,"hidden":false,"mode":"md"},{"id":17,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":66,"value":"plot_8_1 = dot`graph {\nN1 [label=\"age < 15\" id=\"node1\" fontsize=18 style=filled color=lightgrey ];\nN2 [label=\"is male?\" id=\"node2\" fontsize=18 style=filled color=lightgrey ];\nN3 [label=\"${groupIcons.boy} \\nLeaf 1 \\nw1=2\" id=\"node3\" fontsize=14 ];\nN4 [label=\"${groupIcons.girl} \\nLeaf 2 \\nw2=0.1\" id=\"node4\" fontsize=14 ];\nN5 [label=\"${groupIcons.gp + groupIcons.gm + groupIcons.mom} \\nLeaf 3 \\nw3=-1\" id=\"node5\" fontsize=14 ];\n\nN1 -- N2 [label=\"Y\"];\nN2 -- N3 [label=\"Y\"]; \nN2 -- N4 [label=\"N\"]; \nN1 -- N5 [label=\"N\"];\n\n}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"> ${tex.block`\n\\Omega = \\gamma 3 + \\frac{1}{2} \\lambda (2^2 + 0.1^2 + (-1)^2) \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md"},{"id":115,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":226,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":250,"value":"table_8_1 = {\n const table = d3.create(\"table\");\n table.append(\"tbody\")\n .selectAll(\"tr\")\n .data(tableData)\n .join(\"tr\")\n .selectAll(\"td\")\n .data(row => row)\n .join(\"td\")\n .text(d => d)\n .style(\"text-align\", \"center\") \n .style('font-size', '18px')\n return table.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":272,"value":"plot_8_2 = dot`graph {\nN1 [label=\"age < 15\" id=\"node1\" fontsize=18 style=filled color=lightgrey ];\nN2 [label=\"is male?\" id=\"node2\" fontsize=18 style=filled color=lightgrey ];\nN3 [label=\"I1 = {1} \\nG1=g1 \\nH1=h1\" id=\"node3\" fontsize=14 ];\nN4 [label=\"I2 = {4} \\nG2=g4 \\nH2=h4\" id=\"node4\" fontsize=14 ];\nN5 [label=\"I3 = {2,3,5} \\nG3=g2+g3+g5 \\nH3=h2+h3+h5\" id=\"node5\" fontsize=14 ];\n\nN1 -- N2 [label=\"Y\"];\nN2 -- N3 [label=\"Y\"]; \nN2 -- N4 [label=\"N\"]; \nN1 -- N5 [label=\"N\"];\n\n}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":279,"value":"$${tex.block`\nObj = - \\frac{1}{2} \\sum_j \\frac{G_j^2}{H_j + \\lambda} + 3 \\gamma \\\\~\\\\\n`}\n> The result value of the objective function is called \"Structure Score\", which is used to measure how good a tree structure is. The smaller the score is, the better the structure is.\n>

\n> ### Greedy Learning of the Tree

\n> For each leaf node of the tree, try to add a split. The change of objective after adding the split is:\n> ${tex.block`\nGain = \\frac{1}{2} \\left[ \\underbrace{\\frac{G_L^2}{H_L + \\lambda}}_{\\text {the score of left child}} + \\underbrace{\\frac{G_R^2}{H_R + \\lambda}}_{\\text {the score of right child}} - \\underbrace{\\frac{(G_L+G_R)^2}{H_L + H_R + \\lambda}}_{\\text {the score of no split}} \\right] - \\underbrace{\\gamma}_{\\text {complexity cost by adding additional leaf}} \\\\~\\\\\n`}\n> For all features Xs, we can enumerate the gradients as well as GL and GR of all segmentations by scanning from left to right. Then use the Gain formula to calculate the score of each partitioning.","pinned":false,"hidden":false,"mode":"md"},{"id":312,"value":"

\n## Reference\n> * Tianqi Chen's XGBoost paper\n> * Tianqi Chen's XGBoost slides","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"

\n## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":253,"value":"tableData = [\n ['Instance Index', '1' + groupIcons.boy, '2' + groupIcons.mom, '3' + groupIcons.gp, '4' + groupIcons.girl, '5'+ groupIcons.gm,],\n ['Gradient Statistics', 'g1, h1', 'g2, h2', 'g3, h3', 'g4, h4', 'g5, h5',]\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"groupIcons = {\n const all = '👦👩👧👵👴';\n const boy = '👦';\n const girl = '👧';\n const mom = '👩';\n const gm = '👵';\n const gp = '👴';\n\n return {all:all, boy:boy, girl:girl, mom:mom, gm:gm, gp:gp};\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":268,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}