24:null 25:["$","title",null,{"children":"ML | 7 Ensemble Learning | Zhihao Yao | Observable"}] 2a:T61e,> **Parameters in Random Forest** >
> * The number of weak classifiers. Generally speaking, if the number of weak classifiers is too small, the model will be easily underfitted, and if the number is too large, the computation will be too large.

> * m features (m ${tex`\ll`} M) are randomly selected from M (total number of the features in the original data) at the time of each node splitting, and the best feature among these m features (maximizing information gain) is used to split the nodes. The value of m is kept constant during the model training.

> * The key problem in constructing a random forest is how to choose the optimal number of features m as a parameter, and to solve this problem is mainly based on calculating the out-of-bag (OOB) error rate. One important advantage of Random Forest is that it is not necessary to conduct cross-validation or use an independent test set to obtain an unbiased estimate of the error. It can be evaluated internally, which means that an unbiased estimate of the error can be created during the generation process by using OOB (${tex`\approx 36.8`}%).

> * Random Forest can be used for both classification and regression with different loss functions. For classification Random Forest model, the loss function criterion is the Gini index, and another optional criterion is the information gain. For regression Random Forest model, the loss function criterion is the mean squared difference MSE (L2 norm), and another optional criterion is the absolute value difference MAE (L1 norm).2b:T904,### Gradient Boosting > Given a training data ${tex`D = \{(x^{(1)}, y^{(1)}) \ \cdots \ (x^{(N)}, y^{(N)})\} `}

> In boosting, we aim to git residual of pprevious weak classifier:
> ${tex.block` F_{m+1}(x) = F_m (x) + h(x) \\~\\ `} > Our goal is to learn ${tex`h(x^{(i)})`} that:
>${tex.block` F_{m+1}(x^{(i)}) = F_m (x^{(i)}) + h(x^{(i)}) = y^{(i)} \\~\\ `} > In supervised learning, the goal is to find an approximation ${tex`\hat{F}(x)`} to the function ${tex`F(x)`} that minimize the expected value of the loss function.

> ${tex.block` \hat{F} = \underset{F}{\operatorname{argmin}} E_{x,y} [L(y, F(x))] \\~\\ F(x) = \sum_{i=1}^M \alpha_i h_i (x) \\~\\ F_0(x) = \underset{C}{\operatorname{argmin}} \sum_{i=1}^N L(u^{(i)}, C) \\~\\ F_m(x) = F_{m-1}(x) + \underset{h_m}{\operatorname{argmin}} \sum_{i=1}^N L(y^{(i)}, F_{m-1}(x^{(i)}) + h_m(x^{(i)})) \\~\\ `} > where loss function ${tex`L(y,f(x)) = \sum_i (y^{(i)} - f(x^{(i)}))^2`}

> If we use tree model (CART), for ${tex`m=1,2, \ \cdots \ M`}, calculate pseudo-residuals training on ${tex` \{x^{(i)}, r_m^{(i)}\} \quad i=1,2 \ \cdots \ N`}

> ${tex.block` r_m^{{i}} = - [\frac{\partial L (y^{(i)}, F(x^{(i)}))}{\partial F(x^{(i)})}]_{F(x) = F_{m-1}(x)} \\~\\ `} > ${tex`r_m^{(i)}`} is the residual of data ${tex`x^{(i)}`} given ${tex`F_{m-1}(x^{(i)})`}

> Learn a CART (with best j,s) to fit ${tex`r_m^{(i)}`} (It is like we are learning a CART given a new training data: ${tex`D = \{ (x^{(1)}, r_m^{(1)}), \ \cdots \ (x^{(N)}, r_m^{(N)}) \} \text { for } m = 1,2, \ \cdots \ M `})

> ${tex.block` C_{mj} = \underset{C}{\operatorname{argmin}} \sum_{x \in R(m,j)} L (y^{(i)}, F_{m-1}(x^{(i)})+c) \\~\\ F_m(x) = F_{m-1}(x) + \sum_{j=1}^J C_{mj} I (x \in R(m,j)) \\~\\ `} > The final tree is
> ${tex.block` F_m(x) = \sum_{m=1}^M \sum_{j=1}^{J_m} C_{mj} I (x \in R(m,j)) \\~\\ `} > That is what we call GBDT (Gradient Boosting Decision Tree)

> Shrinkage
> In updating of ${tex`F_m(x): F_m(x) = F_{m-1}(x) + \sum_{j=1}^J C_{mj} I \\~\\`} > If we add a learning rate ${tex`\theta \ (\theta > 0)`}
> ${tex.block` F_m(x) = F_{m-1}(x) + {\color{red} \theta} \sum_{j=1}^J C_{mj} I (x \in R(m,j)) \\~\\ `} > Usually, ${tex`\theta \in [0.001, 0.01]`} to reduce the fitting speed.2c:[] 28:{"id":"3931c34997ef50b7","slug":"ml-7-ensemble-learning","title":"ML | 7 Ensemble Learning","thumbnail":"444404f69cc10356b40d7ce900bba2838fa99293a42052b236d85922868b82a3","access_level":"public","create_time":"$D2022-04-15T19:53:44.078Z","update_time":"$D2022-04-22T20:05:10.106Z","view_time":null,"first_public_time":"$D2022-04-21T02:32:58.108Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":"starter_2024"},"version":295,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"01b5d984f2428b1a","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":null}],"members":[{"type":"individual","id":"01b5d984f2428b1a","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":null,"role":"editor"},{"type":"team","id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao","avatar_url":"https://avatars-next.observableusercontent.com/0bac389abf8df9b4d7c6e09e8f96b464d2c01a64946e8b88cd7e143da5750c0e","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"102982dc3961aa5a","slug":"machine-learning-notes","title":"Machine Learning Notes","owner":{"id":"610db6fe9b10a76c","login":"howardyao","name":"Zhihao Yao"}},"type":"notebook","body":{"title":"ML | 7 Ensemble Learning","cells":[{"id":0,"value":"# ML | 7 Ensemble Learning\n

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":6,"value":"## Bootstrap Aggregation (Bagging)\n\n> Bootstrap is any test or metric that relies on random sampling with replacement. For the training set containing m samples, m random sampling operations with replacement are performed to obtain a sampling set of m samples, so that nearly 36.8% of the samples in the training set are not collected. Repeating in the same way, we can collect T data sets containing m samples, thus train T basic classifier, and finally combine the outputs of these T basic classifier.\n>

\n> ${tex.block`\n\\lim_{m \\to +\\infty} \\left(1 - \\frac{1}{m} \\right)^m \\to \\frac{1}{e} \\approx 0.368 \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":21,"value":"mermaid`graph LR\n\nA[Training Dataset] --> |Bootstrap| B[Resampling Dataset1]\nA[Training Dataset] --> |Bootstrap| C[Resampling Dataset2]\nA[Training Dataset] --> |Bootstrap| D[Resampling Dataset3]\n\nB[Resampling Dataset1] --> |train| E[weak classifier1]\nC[Resampling Dataset2] --> |train| F[weak classifier2]\nD[Resampling Dataset3] --> |train| G[weak classifier3]\n\nE[weak classifier1] --> |combine| H[strong classifier]\nF[weak classifier2] --> |combine| H[strong classifier]\nG[weak classifier3] --> |combine| H[strong classifier]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"> The idea of **Random Forest** is to do another random sampling of the features on top of bagging (Bagging with CARTs).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":55,"value":"mermaid`graph LR\n\nA[Training Dataset] --> |Bootstrap| B[Resampling Dataset1]\nA[Training Dataset] --> |Bootstrap| C[Resampling Dataset2]\nA[Training Dataset] --> |Bootstrap| D[Resampling Dataset3]\n\nB[Resampling Dataset1] --> |Random Feature| X[New Dataset1]\nC[Resampling Dataset2] --> |Random Feature| Y[New Dataset2]\nD[Resampling Dataset3] --> |Random Feature| Z[New Dataset3]\n\nX[New Dataset1] --> |train| E[weak classifier1]\nY[New Dataset2]--> |train| F[weak classifier2]\nZ[New Dataset3]--> |train| G[weak classifier3]\n\nE[weak classifier1] --> |combine| H[strong classifier]\nF[weak classifier2] --> |combine| H[strong classifier]\nG[weak classifier3] --> |combine| H[strong classifier]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"$2a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":85,"value":"

\n## Boosting\n\n> Given the training data\n> ${tex.block`\nD = \\{ (X_1,y_1), (X_2,y_2), \\quad \\cdots \\quad (X_N, y_N) \\} \\\\~\\\\\nX_{i} \\in \\mathbb{R}^{p}, \\quad y \\in \\{+1, -1 \\} \\\\~\\\\\n`}\n\n\n### Adaptive Boosting (AdaBoost)\n> For each data ${tex`X_i`}, there is an associated weight ${tex`w_i \\in \\mathbb{R}`}

\n> **Initialization**\n> ${tex.block`\nW = \\left(w_1, w_2, \\ \\cdots \\ w_N \\right) \\\\~\\\\\nw_i = \\frac{1}{N} \\quad i=1,2,\\cdots N \\\\~\\\\\n`}\n> **Weak classifier ${tex`G_k(x)`}**

\n> For ${tex`k = 1,2, \\cdots K`}
\n> The error for each ${tex`G_k(x)`}\n> ${tex.block`\ne_k = P(G_k(x_i) \\neq y_i) \\\\~\\\\\n= \\sum_{i} w_i I(G_k(x_i) \\neq y_i) \\\\~\\\\\n`}\n> The weight for classifier ${tex`G_k(x)`} is updated by:\n> ${tex.block`\n\\alpha_k = \\frac{1}{2} \\ln (\\frac{1-e_k}{e_k}) \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":168,"value":"{\n let w = 600;\n let p = plotter({ \n xDomain: [-0.01, 0.6],\n yDomain: [2.5,-0.1],\n height: w / 2,\n grid: false,\n xLabel:'e(k)', \n yLabel: 'α(k)'\n });\n\n\n p.func(x => 0.5 * Math.log((1-x)/x), {\n stroke: 'steelblue',\n width: 2,\n defined: x => x > 0.01 & x < 0.5\n });\n\n return p.node;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"> **Updating ${tex`w_k`}, the weights of data at round k**
\n> ${tex.block`\nw_k = \\left( w_{k}^{(1)}, w_{k}^{(1)}, \\ \\cdots \\ w_{k}^{(N)} \\right) \\\\~\\\\\nw_{k+1}^{(i)} = \\frac{w_{k}^{(i)}}{Z_k} \\exp (-\\alpha_k y^{(i)} G_k(x^{(i)})) \\\\~\\\\\n\\text {if} \\quad y^{(i)} = G_k(x^{(i)}) \\quad w_{k+1}^{(i)} = w_{k}^{(i)} \\cdot \\frac{1}{e^{\\alpha_k}} \\\\~\\\\\n\\text {if} \\quad y^{(i)} \\neq G_k(x^{(i)}) \\quad w_{k+1}^{(i)} = w_{k}^{(i)} \\cdot e^{\\alpha_k} \\\\~\\\\\n`}\n> We tend to enlarge the weights of misclassified data. Decrease the weights of data with correct classification.
\n> ${tex`Z_k`} is the normalization factor:\n> ${tex.block`\nZ_k = \\sum_{i=1}^N w_{k}^{(i)} \\exp (-\\alpha_k G_k (x^{(i)})) \\\\~\\\\\n\n\\therefore \\quad f(x^{(i)}) = \\sum_{k=1}^K \\alpha_k G_k (x^{(i)}) \\\\~\\\\\nG(x) = sign(f(x)) \\quad \\text {in final classification} \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":228,"value":"$2b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":117,"value":"

\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":217,"value":"data7 = [\n {x:0, y:1},\n {x:1, y:1},\n {x:2, y:1},\n {x:3, y:1},\n {x:4, y:-1},\n {x:5, y:-1},\n {x:6, y:-1},\n {x:7, y:1},\n {x:8, y:1},\n {x:9, y:-1}\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"import { plotter } from '50dadfdec01c15a8'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2c","stdlib":"1","titling":"auto"}} 29:"$28:body"