week-04

TARGET DECK MachineLearning::Week-04

Lagrangian Duality

What is the Lagrangian of a constrained optimisation problem?

For minimising $F(\mathbf{x})$ subject to $f_i(\mathbf{x})\le 0$ for $i=1,\dots ,N$: $L(\mathbf{x},\mathbf{a})=F(\mathbf{x})+{\sum }_{i=1}^N{a}_i{f}_i(\mathbf{x}),a_i\ge 0$ Each multiplier $a_i\ge 0$ folds an inequality constraint into the objective. When a constraint is violated, $a_i{f}_i>0$ inflates $L$, pushing the optimiser away.

What is the difference between the primal and dual problems?

• Primal: ${\min }_{\mathbf{x}}{\max }_{\mathbf{a}\ge 0}L(\mathbf{x},\mathbf{a})$ — outer min, inner max.
• Dual: ${\max }_{\mathbf{a}\ge 0}{\min }_{\mathbf{x}}L(\mathbf{x},\mathbf{a})$ — outer max, inner min.

Swapping order makes the inner optimisation unconstrained, so we can solve ${\nabla }_{\mathbf{x}}L=0$ in closed form, substitute back, and get a problem purely in $\mathbf{a}$.

What are weak duality and strong duality?

• Weak duality (always holds): ${\max }_{\mathbf{a}}{\min }_{\mathbf{x}}L\le {\min }_{\mathbf{x}}{\max }_{\mathbf{a}}L$. The dual gives a lower bound on the primal.
• Strong duality (holds when the problem is convex and Slater’s condition is satisfied — both true for SVM): equality. Dual and primal have the same optimum.

For SVMs, strong duality means we can solve the dual instead of the primal without losing anything.

What are the four KKT conditions for a primal-dual optimum?

A pair $({\mathbf{x}}^{\ast },{\mathbf{a}}^{\ast })$ is jointly optimal iff:

• Stationarity: ${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\mathbf{a}}^{\ast })=0$
• Complementary slackness: $a_i^{\ast }{f}_i({\mathbf{x}}^{\ast })=0$ for all $i$ — either the multiplier is zero or the constraint is active
• Primal feasibility: $f_i({\mathbf{x}}^{\ast })\le 0$
• Dual feasibility: $a_i^{\ast }\ge 0$

Complementary slackness is what produces SVM’s sparsity.

SVM Dual

Write the SVM dual problem.

$\arg {\max }_{\mathbf{a}}{\sum }_{n=1}^N{a}^{(n)}-\frac{1}{2}{\sum }_{n=1}^N{\sum }_{m=1}^N{a}^{(n)}{a}^{(m)}{y}^{(n)}{y}^{(m)}\varphi ({\mathbf{x}}^{(n)}{)}^{\top }\varphi ({\mathbf{x}}^{(m)})$ subject to $a^{(n)}\ge 0$ and ${\sum }_n{a}^{(n)}{y}^{(n)}=0$. Three things to notice: (1) variables are now $a^{(n)}$ — one per training example, independent of $\dim \varphi$; (2) data appears only through inner products; (3) concave in $\mathbf{a}$, still a QP.

How does the dual recover ${\mathbf{w}}^{\ast }$ from the multipliers $a^{(n)}$?

Setting $\partial L/\partial \mathbf{w}=0$ gives: ${\mathbf{w}}^{\ast }={\sum }_{n=1}^N{a}^{(n)}{y}^{(n)}\varphi ({\mathbf{x}}^{(n)})$ The optimal weights are a linear combination of the training feature vectors, weighted by their multipliers and labels. By complementary slackness, only support vectors have $a^{(n)}>0$ — so ${\mathbf{w}}^{\ast }$ depends only on the support vectors.

Why does KKT complementary slackness force SVM solutions to be sparse?

The condition $a^{(n)}(1-y^{(n)}h({\mathbf{x}}^{(n)}))=0$ requires, for each $n$, either $a^{(n)}=0$ or $y^{(n)}h({\mathbf{x}}^{(n)})=1$ (point on margin). So:

• Points strictly outside the margin: $a^{(n)}=0$, contribute nothing.
• Points on the margin: $a^{(n)}>0$ — these are the support vectors.

Sparsity is a structural consequence of the KKT conditions, not a heuristic.

How do you compute SVM predictions in dual form?

$h(\mathbf{x})={\sum }_{n\in S}{a}^{(n)}{y}^{(n)}\varphi ({\mathbf{x}}^{(n)}{)}^{\top }\varphi (\mathbf{x})+b$ where $S$ is the index set of support vectors. The bias $b$ is recovered from any support vector ($y^{(n)}h({\mathbf{x}}^{(n)})=1$); average over all SVs for stability. Predictions depend only on inner products — the opening for the kernel trick.

Kernel Trick

What is the kernel trick?

Replace every inner product $\varphi (\mathbf{x}{)}^{\top }\varphi (\mathbf{z})$ in the SVM dual with a kernel function $k(\mathbf{x},\mathbf{z})$ that returns the same value computed entirely in the original input space: $k(\mathbf{x},\mathbf{z})=\varphi (\mathbf{x}{)}^{\top }\varphi (\mathbf{z})$ Now $\varphi$ is implicit — the algorithm needs only $k$, often computable in $O(d)$ even when $\dim \varphi$ is huge or infinite. Lets us use very high (even infinite) dimensional embeddings for free.

What is Mercer's condition, and what does it guarantee?

A function $k(\mathbf{x},\mathbf{z})$ is a valid kernel — i.e., corresponds to an inner product in some Hilbert space — iff for every finite set of points $\{{\mathbf{x}}^{(i)}\}$:

• Symmetry: $k(\mathbf{x},\mathbf{z})=k(\mathbf{z},\mathbf{x})$
• Positive semidefiniteness: the Gram matrix $K_{ij}=k({\mathbf{x}}^{(i)},{\mathbf{x}}^{(j)})$ has ${\mathbf{z}}^{\top }K\mathbf{z}\ge 0$ for all $\mathbf{z}$

Mercer’s theorem guarantees the existence of an embedding $\varphi$ such that $k={\varphi }^{\top }\varphi$ without requiring you to construct $\varphi$ explicitly. Algorithmically, PSD keeps the SVM dual a convex QP.

What is the formula for the polynomial kernel, and what does it implicitly compute?

$k(\mathbf{x},\mathbf{z})=(1+{\mathbf{x}}^{\top }\mathbf{z}{)}^p$ Corresponds to an explicit embedding of all monomials of degree $\le p$. For $\mathbf{x},\mathbf{z}\in {\mathbb{R}}^d$ with $p$ small, the implicit feature space has $\left(\genfrac{}{}{0ex}{}{d+p}{d}\right)=O(d^p)$ dimensions — but the kernel is computed in $O(d)$ regardless. Massive speed-up.

What is the formula for the Gaussian (RBF) kernel, and why is its implicit feature space infinite-dimensional?

$k(\mathbf{x},\mathbf{z})=\exp \left(-\frac{\Vert \mathbf{x}-\mathbf{z}{\Vert }^2}{2{\sigma }^2}\right)$ Expanding the exponential as a Taylor series produces all monomial degrees: $e^{{\mathbf{x}}^{\top }\mathbf{z}}={\sum }_{j=0}^{\infty }\frac{({\mathbf{x}}^{\top }\mathbf{z}{)}^j}{j!}$ The implicit $\varphi$ contains monomials of every degree — infinite-dimensional. We could never form $\varphi$ explicitly, but $k$ is computed in $O(d)$.

A polynomial-of-degree-2 kernel for 2D inputs has the explicit feature map $\varphi (\mathbf{x})=(1,\sqrt{2}{x}_1,\sqrt{2}{x}_2,x_1^2,x_2^2,\sqrt{2}{x}_1{x}_2)$. What is $\varphi (\mathbf{x}{)}^{\top }\varphi (\mathbf{z})$ as a single closed-form expression?

Computing the inner product term by term: $\varphi (\mathbf{x}{)}^{\top }\varphi (\mathbf{z})=1+2x_1{z}_1+2x_2{z}_2+x_1^2{z}_1^2+x_2^2{z}_2^2+2x_1{x}_2{z}_1{z}_2=(1+{\mathbf{x}}^{\top }\mathbf{z}{)}^2$ Six multiplications collapse into one inner product plus one square. This is exactly the polynomial kernel of degree 2.

Given valid kernels $k_1,k_2$, list four operations that produce another valid kernel.

Any of:

• $c\cdot k_1$ for $c\ge 0$
• $f(\mathbf{x})\cdot k_1(\mathbf{x},\mathbf{z})\cdot f(\mathbf{z})$ for any function $f$
• $q(k_1)$ for a polynomial $q$ with non-negative coefficients
• $\exp (k_1)$
• $k_1+k_2$
• $k_1\cdot k_2$

These composition rules let you build complex kernels (Gaussian, polynomial-with-bias) without verifying Mercer’s condition from scratch.

Comparison

For an SVM with $N=1,000$ training examples and a polynomial-of-degree-3 kernel for 100-dimensional inputs, how many variables does the primal vs the dual have?

• Primal: $\dim \varphi +1=\left(\genfrac{}{}{0ex}{}{103}{3}\right)+1\approx 176,851$ — one per feature dimension.
• Dual: $N=1,000$ — one per training example.

When $\dim \varphi \gg N$, the dual is dramatically smaller. Plus, the dual depends only on inner products, so the kernel trick avoids ever forming $\varphi$ explicitly.