CS6140 Machine Learning — Fall 2026

HW1 — Basic Classic Methods: Closed-form Regression, Decision Trees & KNN

Make sure you check the syllabus for the due date. Please use the notations adopted in class.

Instructions. Submit your code (Jupyter notebook encouraged) together with a short report of results (tables + plots). You may use libraries (numpy, sklearn, matplotlib) for data loading, preprocessing, plotting, and basic math. Where a problem says "from scratch", the core algorithm must be your own — do not call a library implementation of it. Write your Decision Tree (PROBLEM 2) as a reusable fit() / predict() module: you will import it again in HW2.

Requirements.

• Fill in every TODO_STUDENT blank according to the algorithm steps covered in lecture and the linked materials, and make sure the notebook runs top to bottom without errors.
• Understand the whole notebook — including the provided/given code, not just the blanks you filled in — well enough to explain any part of it during office hours.

Datasets. Links below are relative to the course data folder (../../data/...). Core datasets: Housing (regression; train, test, description), Spambase (binary classification; data, description), and MNIST (10-class digit classification, used for KNN) (train images, train labels, test images, test labels; or extracted HAAR features).

Starter code. For each problem, the starter notebook gives you the full data/eval pipeline and asks you to fill in two things: a short library-call baseline (a quick sanity-check number, using a well-known library function) and the from-scratch algorithm steps, evaluated the same way — your from-scratch number should land on or near the library one. Answers to the (THEORY) problems may be written directly in the notebook (e.g. a markdown cell) rather than a separate document, as long as they include any equation, plot, or illustration the answer depends on — not prose alone.

PROBLEM 1 — Closed-form Linear Regression + Ridge   [40 points]

Implement linear regression via the normal equations (closed form) from scratch, and its Ridge variant (L2 penalty, also closed form). Train and test on both datasets and report train/test error.

• Housing — report train/test MSE.
• Spambase — use regression for classification with a fixed threshold; report train/test accuracy.

Library calls: sklearn.linear_model.LinearRegression, sklearn.linear_model.Ridge.

PROBLEM 2 — Decision / Regression Tree from scratch   [70 points]

Implement a decision tree from scratch. Features are numeric, so you need a threshold mechanism at each node (sort feature values, remove duplicates, use midpoints between successive values as candidate splits).

• Spambase — classification tree using Information Gain (entropy) as the split criterion.
• Housing — regression tree using variance / MSE reduction as the split criterion.
• Limit the tree depth to get comparable train and test error (avoid the overfitting typical of deep trees). Report train/test error for a few depth settings.

Write this as a reusable module — HW2 reuses it as the weak learner for boosting.

Library calls: sklearn.tree.DecisionTreeClassifier, sklearn.tree.DecisionTreeRegressor.

PROBLEM 3 — Boosted Trees for Regression   [50 points]

Boost your regression tree by fitting successive trees to the residuals (no AdaBoost, no re-weighting). For rounds i = 1..T on the Housing dataset:

• Start with labels Y_x = original targets.
• Train a shallow regression tree T_i (e.g. depth 2) on (X, Y_x).
• Update residuals: Y_x ← Y_x − T_i(x).
• Repeat. The overall predictor is the sum of the trees.

Plot train and test error as a function of T (number of trees).

Library calls: sklearn.ensemble.GradientBoostingRegressor.

PROBLEM 4 — Similarity & KNN from scratch   [60 points]

Implement k-nearest-neighbor classification that works with different distance / similarity functions. There is no training phase — all the work happens at query time.

• (A) Fixed k (k = 1, 3, 7): Spambase with Euclidean distance; MNIST with cosine distance, Gaussian kernel, and degree-2 polynomial kernel.
• (B) Fixed window: instead of a fixed count k, use all training points within a radius R around the test point and predict by majority/average. Spambase (Euclidean), MNIST (cosine).
• (C) Kernel density estimation   [optional, no credit]: per class, estimate P(z|C) with a kernel restricted to that class's training points, then predict via P(C|z) ∝ P(C)·P(z|C). Spambase with a Gaussian kernel.

Library calls: sklearn.neighbors.KNeighborsClassifier, sklearn.neighbors.RadiusNeighborsClassifier, sklearn.metrics.pairwise.rbf_kernel, sklearn.metrics.pairwise.polynomial_kernel.

PROBLEM 5 (THEORY) — Feature Importance Stability: Single Tree vs. Boosted Ensemble   [25 points]

Consider a simple "feature importance" score for each feature: how often it is used as a split, weighted by the impurity reduction at that split — this applies directly to your PROBLEM 2 decision tree, and sums naturally over the weak learners of your PROBLEM 3 boosted ensemble. Suppose you retrain your single tree from scratch on a random 90% subsample of the same training data (Spambase) and recompute importances from the new tree: the top-5 most "important" features change substantially between the two runs. Repeating the same experiment with the boosted ensemble (summing importances over all weak learners) instead gives nearly identical top-5 features across the two subsamples.

In a short written answer, explain why the single tree's importances are so much less stable than the ensemble's, even though both models achieve similar accuracy.

PROBLEM 6 (THEORY) — Fixed-k vs. Fixed-Window KNN Under Non-Uniform Density   [25 points]

Your PROBLEM 4 KNN classifier supports both a fixed-k mode and a fixed-window (fixed-radius) mode. Suppose a dataset has regions where points are densely packed and regions where points are very sparse. Fixed-window KNN fails in the sparse regions: many query points there have zero training points within the chosen radius, so the classifier cannot predict at all. Fixed-k KNN never has this problem, but in the sparse regions the "k nearest" neighbors it finds can be very far away — arguably not meaningfully similar to the query point at all.

In a short written answer, propose which of the two you would use as the default for such a dataset, and describe one concrete modification to the other approach that would address its specific failure.

PROBLEM 7 — Self Study: Second-order (Newton) Boosting, from the XGBoost paper   [optional, no credit, substantial]

This one is a self-study mini-project, not a normal problem — budget real time, and expect several rounds of back-and-forth with an LLM before it actually works.

1. Read. Chen & Guestrin, "XGBoost: A Scalable Tree Boosting System" (KDD 2016), §2.1–2.3 — the regularized learning objective, the additive (boosting) model, and the exact greedy split-finding algorithm (their Eq. 5–7, Algorithm 1). PROBLEM 3 above fits trees to raw residuals (first-order); this is the second-order generalization that made XGBoost XGBoost.
2. Implement (LLM-assisted). Extend your PROBLEM 3 boosting to classification on Spambase, using log-loss:
   • Each round, compute per-point gradient g_i and Hessian h_i of the log-loss at the current prediction.
   • Replace variance/entropy split-scoring with the regularized structure score: for a candidate split, gain = G_L²/(H_L+λ) + G_R²/(H_R+λ) − G²/(H+λ) − γ, where G/H are the summed gradients/Hessians in a node.
   • Replace the leaf value with the closed-form optimal weight w* = −G/(H+λ).
   • Add λ (L2 leaf-weight regularization) and γ (minimum-gain-to-split) as tunable hyperparameters.
3. Validate. Plot train/test log-loss vs. boosting round, and compare against xgboost.XGBClassifier (or sklearn's HistGradientBoostingClassifier) on the same Spambase split. They should track closely if your math is right — if they don't, that's your signal to go back to the paper (or the LLM) and find the mismatch.
4. Bonus: more than two classes (library only). Your from-scratch structure-score tree and boosting loop above assume binary log-loss; generalizing them to multiclass (softmax loss, a gradient/Hessian per class, one tree per class per round) is a substantially bigger build and is not required. Instead, just fit sklearn's (multiclass) GradientBoostingClassifier on MNIST, plot its train/test log-loss vs. round the same way, and note how accuracy/log-loss compare to the binary Spambase case — this is purely a "how does the library behave with more classes" check, no from-scratch code needed for MNIST.
5. Deliverables.
   • Code, plus a short prompt log: paste the 2–3 key prompts you gave the LLM, and one sentence each on where its first answer was wrong and what you had to correct.
   • A 1-page, bullet-point write-up — written without any LLM assistance — answering, in your own words:
     • What does second-order boosting get you that PROBLEM 3's first-order boosting doesn't?
     • Concretely, what are g_i and h_i for log-loss?
     • What does the structure score measure, and why does dividing by (H+λ) regularize it?
     • Why is w* = −G/(H+λ) the optimal leaf weight for a fixed tree structure?
     • What do λ and γ each control? What breaks if you set both to 0?
     • Where did your validation plot first diverge from the library's, and what did that tell you was wrong?

Library calls: sklearn.ensemble.GradientBoostingClassifier, xgboost.XGBClassifier (or sklearn.ensemble.HistGradientBoostingClassifier).

PROBLEM 8 — Does Boosting Confidence Track KNN Neighborhood Consistency?   [optional, no credit]

This one connects PROBLEM 3/PROBLEM 7 (boosted trees) with PROBLEM 4 (KNN). Almost no new training is needed — reuse what you already built.

Hypothesis. Shallow trees split the same feature space k-NN measures proximity in. A test point sitting in a locally pure/consistent neighborhood should tend to land on the "easy" side of most trees in a boosted ensemble, so their contributions reinforce rather than cancel, giving a confident prediction. In a mixed/sparse neighborhood, different trees disagree and partially cancel, so the ensemble's output stays close to "unsure."

Run this on all three datasets: Spambase, Housing, and MNIST.

• Spambase (classification). Confidence = boosting margin |p(z) − 0.5| × 2, from your PROBLEM 7 classifier (or PROBLEM 3-style boosting adapted to classification, if you skipped PROBLEM 7). Neighborhood consistency = k-NN purity: the majority-class fraction among the k nearest Spambase training points, computed the same way as PROBLEM 4's distance calls.
• Housing (regression). There's no decision boundary to be far from here, so a large prediction doesn't mean "confident." Use predictive uncertainty instead: bootstrap-resample the training set several times (10–20 resamples), refit your PROBLEM 3 boosted regressor each time, and use the std of predictions across resamples as an uncertainty score. Neighborhood consistency = k-NN target spread: the std of y among the k nearest Housing training points.
• MNIST (10-class classification). Don't reuse PROBLEM 4's train/test split for this — instead, pool the MNIST data and draw a fresh random 90/10 split, stratified per class (not k-fold; e.g. train_test_split(..., test_size=0.10, stratify=y)). Confidence generalizes the Spambase margin to multiclass: p_top1(z) − p_top2(z), the gap between the top two predicted-class probabilities (this is exactly the binary margin when there are only 2 classes, not just an analogy). Reuse the MNIST GradientBoostingClassifier from PROBLEM 7's bonus step as the confidence source — full multiclass second-order boosting from scratch is not required here either. Neighborhood consistency = k-NN purity, exactly as for Spambase (the same purity function works for any number of classes).

Report:

• Pearson and Spearman correlation between the two quantities, for a few choices of k (e.g. 5, 15, 31), for each of the three datasets — is the relationship stable across k, or k-sensitive?
• A scatter plot (confidence/uncertainty vs. neighborhood consistency) for each dataset, with a trend line.
• For Spambase and MNIST: bin test points by k-NN purity (e.g. quintiles) and plot classifier accuracy per bin. Does neighborhood purity — a quantity computed with no reference to the model at all — predict where the model is more likely to be wrong?
• Compare all three datasets. Does the relationship hold equally well for all of them, or is one much cleaner than the others? Give a concrete, data-grounded explanation for whatever you find — e.g. dataset/test-set size, discreteness of the confidence measure, number of classes (does purity become a sharper signal with more classes to be "impure" across?), whether bootstrap variance is a noisier proxy for "confidence" than a direct margin, outliers, or something else you notice in your own scatter plots.

PROBLEM 9 — 1-D Normal Equations   [optional, no credit]

Derive explicit formulas for the normal equations solution presented in class for the case of one input dimension.

(Essentially assume the data is (x_i,y_i), i=1,2,...,m, and you are looking for h(x) = ax+b that realizes the minimum mean square error. The problem asks you to write down explicit formulas for a and b.)

HINT: Do not simply copy the formulas from here (but do read the article): either take the general formula derived in class and make the calculations (inverse, multiplications, transpose) for one dimension, or derive the formulas for a and b from scratch; in either case show the derivations. You can compare your end formulas with the ones linked above.

PROBLEM 10 — Convex Hulls and Linear Separability   [optional, no credit]

DHS chapter 5. The convex hull of a set of vectors x_i, i = 1,...,n is the set of all vectors of the form ∑ α_i x_i, where the coefficients α_i are nonnegative and sum to one. Given two sets of vectors, show that either they are linearly separable or their convex hulls intersect.

Hint on easy part: that the two conditions cannot happen simultaneously. Suppose that both statements are true, and consider the classification of a point in the intersection of the convex hulls.

[Difficult] Hard part: that at least one of the two conditions must hold. Suppose that the convex hulls don't intersect; then show the points are linearly separable.

PROBLEM 11 — Entropy Decrease is Bounded   [optional, no credit]

DHS chapter 8. Consider a binary decision tree using entropy splits (splits have 2 branches, labels have K classes).

A) Prove that the decrease in entropy by a split on a binary yes/no feature can never be greater than 1 bit. HINT: use the mutual information formula I(X,Y) = H(Y) − H(Y|X), and use its symmetric property.

B) [Optional, no credit] Generalize this result to the case of arbitrary branching B>1.

PROBLEM 12 — Read a Paper   [optional, no credit]

Pick one of the two (or find your own, on a similar theme):

• Read prof. Andrew Ng's lecture on ML practice advice. Write a brief summary (1 page) explaining the quantities in the lecture and the advice.
• Read prof. Pedro Domingos's paper "A Few Useful Things to Know about Machine Learning". Write a brief summary (1 page), with bullet points.

PROBLEM 13 — Self Study: Implement LambdaMART for Learning-to-Rank   [optional, no credit, substantial]

Like PROBLEM 7, this is a self-study mini-project, not a normal problem — budget real time, and expect several rounds of back-and-forth with an LLM before it actually works. It revisits PROBLEM 3's residual-boosting loop a third time, now for ranking instead of regression or classification.

1. Read. Burges, "From RankNet to LambdaRank to LambdaMART: An Overview" (Microsoft Research technical report MSR-TR-2010-82) — the pairwise RankNet cost, the LambdaRank gradient λ_ij that weights each pair by |ΔNDCG_ij|, and the LambdaMART algorithm that fits MART-style trees to these λ's instead of raw residuals. The lecture notes' own LambdaMART section derives the same algorithm end-to-end, including a fully worked ΔNDCG/λ_ij numeric example — read that first if the paper's notation is heavy going.
2. Dataset. Microsoft's LETOR 4.0 MQ2007 dataset (or its smaller sibling MQ2008, if you want faster iteration) — pre-extracted 46-dimensional query–document feature vectors with graded relevance labels {0,1,2} and standard train/vali/test folds.
3. Implement (LLM-assisted).
   • Implement NDCG@k for a single ranked list (as defined in the lecture notes).
   • For each query, compute the pairwise λ_ij for every crucial (wrongly-ordered) pair, weighted by |ΔNDCG_ij| from swapping that pair's ranks.
   • Aggregate each document's total pull λ_i and its Newton weight w_i = ∂λ_i/∂F(x_i).
   • Reuse your PROBLEM 2/3 regression-tree machinery (or PROBLEM 7's XGBoostStyleTree, if you did it) to fit a shallow tree to (X, λ_i) each round, with leaf value γ_km = ∑λ_i / ∑w_i (the same Newton-step ratio as PROBLEM 7, just built from λ-gradients instead of log-loss gradients), and shrink-and-add as usual.
4. Validate. Report NDCG@1 and NDCG@10 on the test fold. As a baseline, also fit a plain regression-tree ensemble directly to the raw relevance labels (i.e. PROBLEM 3's ordinary residual boosting, ignoring ranking structure entirely) and show LambdaMART's NDCG beats it — this isolates what the λ-gradient actually buys you over "just boost the labels." If you want a sanity-check magnitude: the lecture notes cite MQ2007 NDCG@1 numbers around 0.41–0.42 for RankBoost and (bagged) LambdaMART in the literature; you're not expected to match those exactly (different feature sets, folds, and hyperparameters), but you should be in the same ballpark, not wildly off.
5. Deliverables.
   • Code, plus a short prompt log: paste the 2–3 key prompts you gave the LLM, and one sentence each on where its first answer was wrong and what you had to correct.
   • A 1-page, bullet-point write-up — written without any LLM assistance — answering, in your own words:
     • Why can't you just fit a regression tree directly to the relevance labels and call it a ranker? What does optimizing NDCG specifically buy you?
     • Concretely, what is λ_ij for one pair in your data, and what does its sign tell the tree-fitting step to do?
     • Why does |ΔNDCG_ij| matter — what would go wrong (which algorithm from lecture would you get back) if you dropped it and just used the plain RankNet λ_ij without the NDCG weighting?
     • Where did your NDCG numbers first look wrong, and what did that tell you was broken?

PROBLEM 14 — Ridge Regression via Data Augmentation   [optional, no credit]

The lecture notes (see REGRESSION_ADVANCED_claude_0910.pdf, “An Alternate Derivation of Ridge, via Data Augmentation”) show that fitting ridge regression on your N real training points is identical to fitting ordinary, unregularized least squares on those same N points plus m synthetic “pseudo-rows,” one per feature, each pulling that feature's coefficient toward 0.

Using your PROBLEM 1 centered design matrix Z and label vector y, build the augmented system Z_λ = [Z; √λ·I_m], y_λ = [y; 0_m], and solve for w via your PROBLEM 1 (unregularized) normal-equations code on (Z_λ, y_λ) — no penalty term anywhere in this solve. Confirm numerically that this w matches your PROBLEM 1 ridge solution to numerical precision, on both Housing and Spambase, for at least two different λ values.

Library calls: none beyond what PROBLEM 1 already uses — this problem is entirely about reusing your own normal-equations solver on a different (augmented) dataset.

PROBLEM 15 — Ridge Is a Biased Estimator, Verified Empirically   [optional, no credit]

The lecture notes (see REGRESSION_ADVANCED_claude_0910.pdf, “Ridge Is a Biased Estimator”) prove that E[w_ridge] ≠ w* for λ ≠ 0, unlike ordinary least squares, which is unbiased. This problem asks you to observe that bias directly, by simulation, rather than just take the proof's word for it.

• Pick a true weight vector w* (a handful of nonzero values of your choice) and a fixed design matrix X (e.g. a subsample of Housing's features, sampled once and reused for every simulation below).
• Repeat many times (200+): generate y = Xw* + noise (i.i.d. Gaussian, your choice of variance), fit w_ridge for a few fixed λ values — including λ=0, i.e. plain OLS — and record each fitted w.
• For each λ, average the fitted w across all simulations and compare it to the true w*. Report ‖average(w_ridge) − w*‖ as a function of λ, and confirm it is (numerically) 0 at λ=0 and grows as λ increases.
• Briefly comment: does the direction and rough size of the bias you observe match what the note's formula, E[w_ridge] − w* = −λ(R+λI)⁻¹w*, predicts?

Library calls: none required beyond PROBLEM 1's own ridge solver and numpy.random for the simulation.