Pedagogy: add 15_optimization/038 — optimization on a histogram surrogate (classification example)

[kwlee2025cpp]

Summary

Build 15_optimization/038_optimization_on_histogram_surrogate.ipynb as a companion to the existing 030_Classification_Optimization.ipynb. The new notebook teaches a general numerical-methods pattern: when iterative parameter optimization is expensive over $N$ raw data points, replace the per-point sum in the cost function with a per-cell sum over a multi-dimensional histogram of the feature space, optimize on the surrogate, then verify the final result on the full dataset.

The pattern was used in Ch. 6 of:

Lee, K. (2004). Longitudinal Driver Model and Collision Warning and Avoidance Algorithms Based on Human Driving Databases. Ph.D. dissertation, Mechanical Engineering, University of Michigan.

There, two 5D histograms reduced 3.4 M data points (~400 MB) to ~1.9 MB while approximating the confusion matrix used by fmincon with 1000 random initial conditions. The same pattern transplants cleanly to a 2D classification example for teaching.

Pedagogical arc

• Motivate the problem: iterative optimization (multi-start, hyperparameter sweeps) makes the per-point cost-function scan the bottleneck
• Build per-class histograms from a 2D training set (two overlapping Gaussians, ~$10^6$ points) — visualize side-by-side heatmaps analogous to the dissertation's Fig. 6.2 "Threatening" / "Safe" panels
• Surrogate confusion matrix: $\widehat{TP}, \widehat{FP}, \widehat{TN}, \widehat{FN}$ as weighted sums over cell centroids (the algebra of Eqs. 38–39 in Ch. 6, restated for classification)
• Train a logistic regression model two ways — on raw data vs on the surrogate — and overlay the decision boundaries
• Bias-vs-speed tradeoff via an ipywidgets slider on grid resolution $n \times n$, with a live Pareto plot
• Verify-on-truth step: re-evaluate the surrogate-trained model point-by-point on the full dataset; tabulate the confusion matrix both ways
• Train / evaluation split for overfitting check (mirrors Ch. 6 §6.1's split-half analysis)

Scope decisions

• Classifier: logistic regression (clean weighted log-loss on the surrogate) — likely. SVM is more visual but heavier.
• Grid: uniform for the first notebook. Log-spaced (per dimension) and quantile-spaced are mentioned as alternatives but not implemented in 038.
• Cost function: choose one of (a) the geometric mean of TP and precision, mirroring Ch. 6 Eq. 40, or (b) sklearn-style weighted log-loss. Signpost the other in the closing.

Curricular hooks

• Bridges 20_probability/ histograms (per-class joint densities) and 15_optimization/ (optimization on a surrogate)
• Direct follow-on to 030_Classification_Optimization.ipynb
• Train-on-surrogate, verify-on-truth pattern is a general engineering-numerical-methods lesson reusable elsewhere

Out of scope (parked as future threads)

• Adaptive $C$-groups (k-means coreset) — extends the rectangular grid to data-adaptive cells, the move that escapes the curse of dimensionality. Would live as a sibling notebook (~039) once 038 lands.
• Soft-assignment / Gaussian-mixture surrogate
• Boundary-aware adaptive refinement (cluster misclassified points after a first pass)
• Sufficient-statistics-per-cell extension (Bradley, Fayyad, Reina 1998), the high-D successor to histograms

[kwlee2025cpp]

Prior art surfaced and ported on 07898a93: substantial work on this idea already existed on the local data-rasterization branch.

What was on the branch:

• 15_optimization/038_Classification_Optimization-Rasterization.ipynb (136 cells, full pedagogical arc)
• 15_optimization/038_raster.py (jupytext-paired view)
• Helper API: calc_2d_histograms, edges_to_nodes, nodes_and_weights_from_histogram
• Four cost-function iterations (linear → step → sigmoid → cross-entropy)
• Histogram-based data-compression optimization section
• Off-the-shelf comparisons: sklearn LDA, TensorFlow, PyTorch

The branch had stalled with mostly lateral fix commits (typo cleanups, Korean-removed-from-matplotlib elsewhere in repo). Notebook was substantively complete.

Ported as-is on 07898a93 — no refactor on the way in. The hook caught some newer-nbformat cell-id residue at commit time, but otherwise the port was a straight copy.

Updated scope after the port lands:

• Notebook on main
• Helper module on main
• Cross-check against feedback_no_korean_in_plots.md — verify no Korean in matplotlib strings
• Add dissertation citation in the notebook body (currently only in commit message + this issue)
• Resolve any WIP comments / TODOs in the ported notebook
• Verify notebook executes top-to-bottom (CI in progress at time of port)
• Adaptive C-groups extension (parked sibling) — separate future thread

Closing this issue blocked on the four cross-checks above.

[kwlee2025cpp]

Trim landed on `0c2e56cb` (refactor(15_optimization/038): trim to histogram-rasterization core, drop 030 duplication).

Reason for the trim: the freshly-ported 038 (07898a93) duplicated about 85 cells of content with 030_Classification_Optimization.ipynb — the same four-cost-function evolution (linear → step → sigmoid → cross-entropy) and the same sklearn / TensorFlow / PyTorch classifier comparisons. Both pedagogies belong in 030, not here.

After trim: 137 → 58 cells, -1310 / +134 lines.

038 now teaches only the histogram-rasterization idea:

• Brief intro pointing to 030 for the cost-function progression
• Bare-minimum definitions (wx, sigmoid, cross-entropy, get_callback, plot_decision_boundary) so the notebook still runs standalone in Colab
• Baseline: optimize cross-entropy on raw data
• Histogram-compression: helpers, weighted cost function, optimize on rasterized data
• Compare convergence + decision boundary + results table side by side
• References (with Lee 2004 dissertation entry)

Verified executes top-to-bottom locally in CI mode (~5 s), produces the expected plots.

Open follow-ups:

• Validate against current CI (run in progress on 0c2e56cb)
• Adaptive C-groups (k-means coreset) extension — parked sibling for the high-D follow-up; separate future issue when ready

After CI confirms green, this issue is close-ready.