04 Trees

Note

📝 Սլայդերը պատրաստ են (ներքևում)։ [17]–[21] դասերը ձայնագրված են — տեսանյութերի հղումները ներքևում են։

🎲 Random

image.png

📚 Նյութը

Սլայդերը ml/04_trees/ պանակում․

• [17] Decision trees — anatomy of a tree, Gini / entropy + information gain, the CART algorithm, greedy (not optimal) splits, overfitting → pruning (ccp_alpha), axis-aligned staircases, and why trees cannot extrapolate. PDF · PDF (նշումներով) · ▶️ [17] Decision tree | Մեքենայական ուսուցում
• [18] Random forests — bootstrap aggregating, the variance formula (the \(\rho\sigma^2\) floor), OOB score, max_features as the decorrelation knob, importances, and smoother boundaries than one tree. PDF · ▶️ [18] Random Forest | Մեքենայական ուսուցում
• [19] Boosting — AdaBoost, gradient boosting as gradient descent in function space, the residual animation, learning rate + early stopping, and classification in log-odds. PDF · ▶️ [19] Gradient Boosting | Մեքենայական ուսուցում
• [20] Advanced boosting — XGBoost (regularized objective → structure score), LightGBM (leaf-wise, GOSS, EFB), CatBoost (ordered target statistics), monotonic constraints, and stacking. PDF · ▶️ [20] Advanced Boosting | Մեքենայական ուսուցում

📝 Թեմայի վերաբերյալ հարցաշար (Google Form): TBD

🏡 Տնային

▶️ [21] Ծառեր, գործնական — ներքևի երկու առաջադրանքների կոդային walkthrough-ը (գինի + census income)՝ տեսանյութ | Մեքենայական ուսուցում։

Chapter project — the wine-quality running score 🧀🧀

Build one classifier three ways and keep a running scoreboard on the same train/test split: a single tree (HW1) → a random forest (HW2) → gradient boosting (HW3). Report accuracy + F1 / ROC-AUC at each step and watch how - and whether - each ensemble beats the last.

Unlike the lectures’ Titanic (where one feature, gender, dominates so the ensembles barely help), here you use a richer dataset - wine quality (~6,500 wines, 12 numeric features, no single dominant one) - so the ensembles have real room to win. Task: predict a “good” wine (quality score ≥ 7). About 20% are good, so it is imbalanced - always predicting “not good” already scores ~0.80 accuracy, which is why you report ROC-AUC and F1, not accuracy.

Starter notebook: 21_trees_project.ipynb (download) · view on GitHub. Data: data/wine.csv (UCI wine quality, red + white combined, pinned so no live fetch needed).

HW1 — grow, prune, read a tree ([17])

1. By hand (Play Tennis): build the decision stump on Outlook and compute the information gain of one other split (Humidity or Wind).
2. sklearn (wine): fit a DecisionTreeClassifier; plot the depth train/test U-curve (ROC-AUC vs max_depth).
3. Prune via ccp_alpha chosen by cross-validation; visualize the final tree (plot_tree).
4. Confirm scale-invariance: rescale a feature (e.g. alcohol), refit, show the tree is unchanged.

Bonus: fit a logistic-regression baseline on the same split and compare; refit the single tree as LGBMClassifier(n_estimators=1, learning_rate=1.0) and check it matches. Further reading: the r2d3 visual intro to machine learning.

HW2 — bag the tree ([18])

1. Fit a RandomForestClassifier; report the OOB score vs 5-fold CV, and compare accuracy + F1 / ROC-AUC to your HW1 single tree (the running score). On this richer data the forest should clearly beat the tree - a real jump, not Titanic’s flat result.
2. Sweep n_estimators and plot the plateau; sweep max_features and watch it matter.
3. The importance trap. Add two columns of pure junk (Gaussian noise + a random high-cardinality id), refit, and compare the default impurity feature_importances_ against permutation importance (on the test set). Impurity hands the junk more importance than the real is_red feature; permutation sends it to the bottom. Explain why (cardinality bias).
4. Decision boundaries. On two features (e.g. alcohol × volatile_acidity), plot the decision regions of the single tree vs the forest vs boosting - watch the blocky staircase ([17]) smooth out ([18]).
5. Regression: RandomForestRegressor on the Yerevan rent toy; plot error vs n_estimators.

Bonus: swap in ExtraTreesClassifier and compare; argue from the variance formula why averaging cannot beat the \(\rho\sigma^2\) floor.

HW3 — boost the tree ([19]–[20])

1. By hand (Yerevan rent toy): do 3 rounds of gradient boosting — init \(= \text{mean}(y)\), compute residuals, fit a stump, update with \(\eta\). Show the residuals shrinking.
2. sklearn (wine): fit a GradientBoostingClassifier / HistGradientBoostingClassifier with early stopping; compare to your HW2 random forest on the same score (accuracy + F1 / ROC-AUC).
3. Tune learning_rate (with early stopping picking n_estimators). Then try LightGBM and add a monotonic constraint on a feature whose effect you expect to be monotone (e.g. alcohol).
4. Threshold tuning ([13]). The scoreboard’s F1 uses the default 0.5 cutoff, but only ~20% of wines are “good” - pick the F1-optimal threshold out-of-fold (never on the test set) and re-report F1.

Bonus: the AdaBoost \(\alpha = \tfrac12\ln\frac{1-\text{err}}{\text{err}}\) arithmetic for one round; force overfitting (train \(\to\) 0, test U-turn) then early-stop; try subsample \(< 1\).

Practical — LightGBM on Census Income 🧀🧀🧀

A minimal-scaffold capstone: use LightGBM as one lens on the whole chapter — the same library gives you a single tree, a random forest, and gradient boosting, so the only thing that changes between them is the ensembling strategy (not the implementation, the preprocessing, or the metric). Dataset: UCI Adult / Census Income (~48,800 people; predict income >$50K), which is imbalanced (~24% positive) with categorical features and missing values. Because ~76% earn <=50K, report ROC-AUC and F1, not accuracy.

Starter notebook (loader + task list only — you do the cleaning and all the modelling): 21_adult_lightgbm.ipynb (download) · view on GitHub. Data loads live via fetch_openml("adult", version=2) (UCI Adult).

• Part 0 — clean & explore: binary target + imbalance; missing values (LightGBM handles NaN natively, no imputation needed); drop fnlwgt (a census sampling weight) and the duplicated education / education-num; mark the 8 categoricals (incl. native-country, 41 levels); one stratified split reused everywhere.
• Part 1 — baselines, one library (+ a linear reference): a logistic-regression baseline (it needs imputation + one-hot + scaling, unlike the trees) plus single tree (n_estimators=1, learning_rate=1), random forest (boosting_type='rf'), gradient boosting (default gbdt) — all scored on the same test split (ROC-AUC + F1). Then native categorical_feature vs one-hot (watch native-country blow up the column count). Expect logreg ≈ tree < RF ≲ GBDT.
• Part 2 — make the GBDT win: early stopping; tune in the [20] order (learning_rate ↔︎ trees → num_leaves / min_data_in_leaf → lambda_l1/l2 → subsampling); handle imbalance (is_unbalance / scale_pos_weight) and pick the decision threshold by F1.
• Part 3 — read it & audit it: gain vs permutation importance; optional monotonic constraint on education-num; a subgroup slice-check - report test ROC-AUC and positive rate by sex and comment on the gap (a strong overall metric can hide very different per-group behavior); then a short reflection on whether tree < RF < GBDT actually held, and by how much.

Bonus: add XGBoost and compare; build a stacking ensemble (LightGBM + logistic regression) with out-of-fold predictions.

NoteԱյս գլխի եզրակացությունը սահման ունի

Այս գլուխը փակվում է «Trees + ensembles dominate tabular data» տողով։ Դա ճիշտ է, և մնում է ճիշտ տարածության մեծ մասում — բայց ոչ ամենուր։

Փոքր, մաքուր աղյուսակների վրա մի transformer, որը երբեք չի սովորել ձեր տվյալների վրա, հաղթում է 4 ժամ tuning արած ensemble-ին՝ 2.8 վայրկյանում (Nature, 2025, մինչև 10,000 տող)։

Եվ այդ սահմանը արագ շարժվում է՝ 2026-ի TabPFN-3-ը հայտարարում է մինչև 1,000,000 տող։ Այսինքն՝ մի՛ անգիր արեք շեմը, ստուգեք ընթացիկը։ Մանրամասները՝ գլուխ 14 — Tabular Foundation Models։