Unit 3.7 · about 3 h
150 / 324Kernels, bandwidth and kernel matrix cost
Kernels buy nonlinearity without paying for explicit features, then charge it back as a dense \(n \times n\) matrix. The same similarity-versus-cost trade returns in every neighbor and attention method.
- derive
- measure
You can now
- Derive the kernel-trick substitution with the polynomial and RBF forms, and predict how degree and \(\gamma\) move bias and locality.
- Explain the RBF similarity geometry: far points contribute near zero and \(\gamma\) sets the meaning of far.
- Measure kernel matrix time and memory scaling and state the largest \(n\) you would run dense.
Covers
- Polynomial and RBF kernels, bandwidth and similarity geometry
- Kernel matrix time and memory cost
Study, in this order
5 steps
- ISLP Chapter 9: kernels and the radial basis functionISLP - tree-based methods and support vector machines
Sections 9.3.1 and 9.3.2 (pp. 377 to 382): feature enlargement, the kernel trick with equations 9.18 to 9.23, the polynomial kernel 9.22, the radial kernel 9.24 and \(\gamma\) locality
- HoML Appendix C: polynomial, similarity and RBF kernelsHands-On Machine Learning with Scikit-Learn and PyTorch - nonlinear classical models
Polynomial Kernel, Similarity Features with the
gaussian_rbfgamma0.3 cells, Gaussian RBF Kernel with thegammaandCgrid, Under the hood - sklearn SVM kernel functions and RBF parametersscikit-learn - neighbors, SVMs, trees and ensembles
1.4.6 Kernel functions with 1.4.6.1 Parameters of the RBF Kernel:
Cfor smoothness againstgammafor influence, with exponential grid search over both - sklearn SVM complexityscikit-learn - neighbors, SVMs, trees and ensembles
1.4.4 Complexity: libsvm quadratic to cubic in \(n\) with cache dependence, against near-linear
LinearSVC - ISLP lab: nonlinear support vector machinesISLP - tree-based methods and support vector machines
9.6.2 Support Vector Machine: the radial kernel at \(\gamma\) 1 and \(C\) 1e5 overfitting, then the \(C\) and \(\gamma\) grid choosing \(C\) 1 and \(\gamma\) 0.5; 9.6.3 ROC Curves: the tuned model against \(\gamma\) 50 on training and test data
Focus on
- The trick replaces every inner product with \(K\), so \(f(x)\) equals bias plus a sum of \(\alpha_i K(x, x_i)\) over support vectors only. The RBF form \(\exp(-\gamma \|x - z\|^2)\) makes far points contribute near zero, which is what locality means.
- \(\gamma\) sets the ruler: large values spike the similarity and overfit, small values smooth everything toward underfit. The HoML grid crosses \(\gamma\) 0.1 with 5 against \(C\) 0.001 with 1000 to show both failures.
gammascaleequals 1 over (n_featurestimesX.var()), verified exactly against sklearn internals. It is data-dependent, so rescaling silently retunes the kernel.- The Gram matrix holds \(n^2\) floats: 10000 rows in
float64need 763 MiB. Measured on the reference i9 CPU under sklearn 1.9.1, \(n = 1000\) takes 0.025 seconds and 7.6 MiB while \(n = 4000\) takes 0.171 seconds and 122.1 MiB.
Reproduce closed-book
pairwise.rbf_kernel, then time the Gram matrix at \(n = 1000\) and \(n = 4000\) and confirm the 16x memory step.Traps
- sklearn \(\gamma\) is \(1/(2 \sigma^2)\), not \(\sigma\). Porting \(\sigma\) 0.5 from problem 21 means setting \(\gamma\) 2.0.
- Kernel methods inherit the scaling requirement twice: distances and \(\gamma\) both assume comparable units.
- Tiny \(\gamma\) makes every point similar to every other through a near-constant Gram matrix and underfits. Read the grid, never the default alone.
Practice
Deep-ML 280: Implement RBF (Gaussian) Kernel Function
Implement rbf_kernel(X1, X2, gamma); the visible tests check the \(2 \times 2\) \(\gamma\) 0.5 matrix and the \(1 \times 1\) \(\gamma\) 1.0 case at 4 decimals
Use the squared-norm identity with no Python loops. Identical inputs must give exactly 1.0 on the diagonal.
Self-test
-
Write the RBF matrix for \(X_1 = \left[\begin{smallmatrix}0&0\\1&1\end{smallmatrix}\right]\) against \(X_2 = \left[\begin{smallmatrix}0&0\\2&2\end{smallmatrix}\right]\) at \(\gamma\) 0.5.
Squared distances are 0, 8, 2 and 2, so the matrix is \(\left[\begin{smallmatrix}1.0&0.0183\\0.3679&0.3679\end{smallmatrix}\right]\). -
How much memory does a float64 Gram matrix need at \(n = 10000\), and about how many rows fill 16 GiB?
\(10000^2 \times 8\) bytes = 763 MiB. 16 GiB holds about 46000 rows, since \(46000^2 \times 8\) bytes is near 15.8 GiB. -
Same data, \(\gamma\) 5 versus \(\gamma\) 0.1. Which risks overfitting and why?
\(\gamma\) 5: similarity decays within tiny radii, so each point predicts itself and noise becomes boundary. \(\gamma\) 0.1 smooths distant points together and risks underfitting. -
Why not expand RBF features explicitly instead of using the kernel?
The RBF expansion is infinite-dimensional. The kernel evaluates that inner product in closed form from pairwise distances.
Completion criterion
Stop when
You reproduce the test matrix by hand, your timings show the quadratic memory step, and problem 280 passes.
Mark passed, then open 3.8 Only mark this when you can do it without notes.Leads to
- 3.8 Feature importance caveats and class weighting effects Close the section with interpretation and weighting caveats.
Comes after
- 3.5 k-nearest neighbors, search cost and the curse of dimensionalitySmooth the vote with RBF similarity.
- 3.6 Support vector machines: margins, hinge loss and slackExtend the margin to nonlinear boundaries with kernels.
Resources for this unit
- Hands-On Machine Learning with Scikit-Learn and PyTorch - nonlinear classical models Read Chapters 3, 5 and 6 and the online Appendix C notebook as the first pass through performance measures, trees, ensembles and SVMs, running notebooks 03, 05 and 06 alongside. Vary depth, estimators, learning rate, k, C and RBF width under fixed splits.
- scikit-learn - neighbors, SVMs, trees and ensembles Check official estimator constraints, complexity, preprocessing needs, missing-value behavior and probability caveats. Do not use library calls as the mechanism implementation.
- ISLP - tree-based methods and support vector machines Use Chapters 8 and 9 with their Python labs for the statistical account of trees, bagging, random forests, boosting and SVMs that the notebooks leave implicit, and for model-choice and feature-importance arguments.
Also in this section
- Deep-ML - tree, ensemble and kernel problems Use 138 Best Gini-Based Split, 20 Decision Tree Learning, 307 Bagging Classifier, 21 Pegasos Kernel SVM and 280 RBF Kernel as unit checks after the local implementation passes. Their tests were read in review; each card states what they pin, including tie and update-order conventions.
- Probabilistic Machine Learning, Chapter 16: exemplar-based methods Read Sections 16.1 to 16.1.3 for the KNN decision rule, the curse of dimensionality with the growing-hypercube example, and the speed section on k-d trees, hashing and approximate search.
- XGBoost parameters and sklearn estimator interface Read the tree-booster parameter list for
eta, depth, sampling and regularization names and defaults, and the sklearn page for early stopping witheval_set. - LightGBM parameters Read
learning_rate,num_leaves,max_depth,min_data_in_leaf,feature_fraction,bagging_fractionwithbagging_freq,lambda_l2and early stopping defaults. - CatBoost common parameters and categorical features Read
iterations,learning_rate,l2_leaf_reg,depth,grow_policy,subsample,rsm,boosting_type,use_best_modelandone_hot_max_sizedefaults, plus native categorical handling.