MAP Estimation · Logistic Regression · Support Vector Machines

§5.6.1 Maximum a posteriori (MAP) estimation

Full Bayesian posteriors are principled but usually intractable. The compromise keeping some of the prior’s benefit: MAP estimation — a point estimate at the posterior’s peak:

Term by term

\boldsymbol{\theta}_{\mathrm{MAP}} = \arg\max_{\boldsymbol{\theta}}\, p(\boldsymbol{\theta} \mid \boldsymbol{x}) = \arg\max_{\boldsymbol{\theta}}\, \log p(\boldsymbol{x} \mid \boldsymbol{\theta}) + \log p(\boldsymbol{\theta})

$\log p(\boldsymbol{x} \mid \boldsymbol{\theta})$	the familiar log-likelihood — the data’s vote	ML term
$\log p(\boldsymbol{\theta})$	the prior’s vote: with a Gaussian prior N(0, (1/λ)I²) this term IS the weight-decay penalty λwᵀw (plus a w-free constant) — MAP with a Gaussian prior ≡ weight decay	prior term
$\text{trade}$	the prior information reduces the estimate’s VARIANCE relative to plain ML — at the price of added BIAS (§5.4.4’s trade, enacted)	bias↔variance

Aside — which regularizers are MAP?

Many regularized estimations are MAP in disguise: any extra objective term corresponding to $\log p(\boldsymbol{\theta})$ qualifies, and the view is generative — e.g. a mixture-of-Gaussians prior yields complicated yet interpretable penalties. But NOT all: some regularizer terms are not the log of any distribution, and others depend on the data — which a prior, by definition, cannot.

§5.7.1 Probabilistic supervised learning

Most supervised learning in this book = estimate $p(y \mid \boldsymbol{x}; \boldsymbol{\theta})$ by maximum likelihood. Linear regression was the family $p(y \mid \boldsymbol{x}) = \mathcal{N}(y; \boldsymbol{\theta}^\top\boldsymbol{x}, \boldsymbol{I})$ . For two classes, the mean of a binary variable must live in (0, 1) — so squash the linear score with §3.10’s sigmoid: logistic regression , $p(y = 1 \mid \boldsymbol{x}; \boldsymbol{\theta}) = \sigma(\boldsymbol{\theta}^\top\boldsymbol{x})$ (a classification algorithm, despite the name):

The linear score θᵀx, squashed into a probability — drag the probe along the score axis

p(y=1|x) = σ(θᵀx)= 0.769

score θᵀx1.20

Unlike linear regression there is no closed form for the optimal weights — one searches, minimizing the negative log-likelihood by gradient descent. The same recipe — write a parametric family of conditionals, maximize likelihood — extends to essentially any supervised problem.

§5.7.2 Support vector machines

The SVM is also driven by a linear score $\boldsymbol{w}^\top\boldsymbol{x} + b$ — but outputs only a class identity (positive score → positive class), no probabilities. Its great gift to ML is the kernel trick :

Term by term

\boldsymbol{w}^\top\boldsymbol{x} + b = b + \sum_{i=1}^m \alpha_i\, \boldsymbol{x}^\top\boldsymbol{x}^{(i)} \;\;\rightsquigarrow\;\; f(\boldsymbol{x}) = b + \sum_i \alpha_i\, k(\boldsymbol{x}, \boldsymbol{x}^{(i)})

$\alpha_i$	dual coefficients: the model rewritten EXCLUSIVELY in dot products between examples	m×1
$k(\boldsymbol{x}, \boldsymbol{x}^{(i)}) = \boldsymbol{\phi}(\boldsymbol{x}) \cdot \boldsymbol{\phi}(\boldsymbol{x}^{(i)})$	swap every dot product for a KERNEL: a dot product in a feature space φ you never construct	the trick
$f(\boldsymbol{x})$	nonlinear in x, yet LINEAR in φ(x) and in α — so convex optimization still converges efficiently	best of both

You have already seen a feature map: chapter 2’s Cartesian→polar morph is exactly $\boldsymbol{\phi}$ turning a linearly-inseparable problem into a separable one —

The feature-map idea, revisited: φ(x) = (r, θ) makes the inseparable separable — kernels do this without ever computing φ

In Cartesian coordinates no straight line can separate the two classes.

class A (inner)class B (ring)

Why the trick is powerful: (1) nonlinear models via convex optimization (φ is fixed; only α is learned); (2) $k$ is often far cheaper than building φ — which can even be infinite-dimensional. The book’s example: over non-negative integers, φ(x) = x ones followed by infinitely many zeros has the perfectly tractable kernel $k(x, x^{(i)}) = \min(x, x^{(i)})$ . The most-used kernel is the Gaussian (RBF) kernel $k(\boldsymbol{u}, \boldsymbol{v}) = \mathcal{N}(\boldsymbol{u} - \boldsymbol{v};\, \boldsymbol{0},\, \sigma^2\boldsymbol{I})$ — corresponding to an infinite-dimensional space, and acting as template matching: a training example near the test point fires strongly, and the prediction blends training labels weighted by similarity.

Costs, support vectors — and the torch-passing

Prediction costs O(m) — one kernel term per training example — mitigated because SVMs learn mostly-zero α: only the support vectors matter at test time. Training, though, builds an m×m Gram matrix: O(m²), hopeless for billions of examples. Generic kernels also generalize poorly on AI tasks (§5.11 explains why). The modern deep-learning era opened precisely here: Hinton et al. (2006) showed a neural network beating the RBF SVM on MNIST.

Next: the remaining simple learners — nearest neighbors and decision trees — and the unsupervised side: k-NN, trees, PCA and k-means.

Check yourself — MAP, logistic regression, kernels

1.How does MAP estimation relate ML estimation and Bayesian inference?

2.Which regularizers can NOT be interpreted as MAP inference?

3.Why does binary classification need the sigmoid where linear regression needed nothing?

4.What are the kernel trick's two claimed powers?

5.Why did kernel machines cede the stage to deep learning?

5 questions