Difference between Primal, Dual and Kernel Ridge Regression

Question

What is the difference between Primal, Dual and Kernel Ridge Regression? People are using all three, and because of the different notation that everyone uses at different sources is difficult for me to follow.

So can someone tell me in simple words what is the difference between these three? In addition what could be some advantages or disadvantages of each, and what can be their complexity?

Answer 1

Short answer: no difference between Primal and Dual - it's only about the way of arriving to the solution. Kernel ridge regression is essentially the same as usual ridge regression, but uses the kernel trick to go non-linear.

Linear Regression

First of all, a usual Least Squares Linear Regression tries to fit a straight line to the set of data points in such a way that the sum of squared errors is minimal.

We parametrize the best fit line with $\mathbb w$ and for each data point $(\mathbf x_i, y_i)$ we want $\mathbf w^T \mathbf x_i \approx y_i$. Let $e_i = y_i - \mathbf w^T \mathbf x_i$ be the error - the distance between predicted and true values. So our goal is to minimize the sum of squared errors $\sum e_i^2 = \| \mathbf e \|^2 = \| X \mathbf w - \mathbf y \|^2$ where $X = \begin{bmatrix} — \mathbf x_1 \,— \\ — \mathbf x_2 \,— \\ \vdots \\ — \mathbf x_n \,— \end{bmatrix}$ - a data matrix with each $\mathbf x_i$ being a row, and $\mathbf y = (y_1 , \ ... \ , y_n)$ a vector with all $y_i$'s.

Thus, the objective is $\min\limits_{\mathbf w} \| X \mathbf w - \mathbf y \|^2$, and the solution is $\mathbf w = (X^T X)^{-1} X^T \mathbf y$ (known as "Normal Equation").

For a new unseen data point $\mathbf x$ we predict its target value $\hat y$ as $\hat y = \mathbf w^T \mathbf x$.

Ridge Regression

When there are many correlated variables in linear regression models, the coefficients $\mathbf w$ can become poorly determined and have lots of variance. One of the solutions to this problem is to restrict weights $\mathbf w$ so they don't exceed some budget $C$. This is equivalent to using $L_2$-regularization, also known as "weight decay": it will decrease the variance at the cost of sometimes missing the correct results (i.e. by introducing some bias).

The objective now becomes $\min\limits_{\mathbf w} \| X \mathbf w - y \|^2 + \lambda \, \| \mathbf w \|^2$, with $\lambda$ being the regularization parameter. By going through the math, we obtain the following solution: $\mathbf w = (X^T X + \lambda \, I )^{-1} X^T \mathbf y$. It's very similar to the usual linear regression, but here we add $\lambda$ to each diagonal element of $X^T X$.

Note that we can re-write $\mathbf w$ as $\mathbf w = X^T \, (X X^T + \lambda \, I)^{-1} \mathbf y$ (see here for details). For a new unseen data point $\mathbf x$ we predict its target value $\hat y$ as $\hat y = \mathbf x^T \mathbf w = \mathbf x^T X^T \, (X X^T + \lambda \, I)^{-1} \mathbf y$. Let $\boldsymbol \alpha = (X X^T + \lambda \, I)^{-1} \mathbf y$. Then $\hat y = \mathbf x^T X^T \boldsymbol \alpha = \sum\limits_{i=1}^{n} \alpha_i \cdot \mathbf x^T \mathbf x_i$.

Ridge Regression Dual Form

We can have a different look at our objective - and define the following quadratic program problem:

$\min\limits_{\mathbf e, \mathbf w} \sum\limits_{i = 1}^n e_i^2$ s.t. $e_i = y_i - \mathbf w^T \mathbf x_i$ for $i = 1 \, .. \, n$ and $\| \mathbf w \|^2 \leqslant C$.

It's the same objective, but expressed somewhat differently, and here the constraint on the size of $\mathbf w$ is explicit. To solve it, we define the Lagrangian $\mathcal L_p(\mathbf w, \mathbf e ; C)$ - this is the primal form that contains primal variables $\mathbf w$ and $\mathbf e$. Then we optimize it w.r.t. $\mathbf e$ and $\mathbf w$. To get the dual formulation, we put found $\mathbf e$ and $\mathbf w$ back to $\mathcal L_p(\mathbf w, \mathbf e ; C)$.

So, $\mathcal L_p(\mathbf w, \mathbf e ; C) = \| \mathbf e \|^2 + \boldsymbol \beta^T (\mathbf y - X \mathbf w - \mathbf e) - \lambda \, (\| \mathbf w \|^2 - C)$. By taking derivatives w.r.t. $\mathbf w$ and $\mathbf e$, we obtain $\mathbf e = \cfrac{1}{2} \boldsymbol \beta$ and $\mathbf w = \cfrac{1}{2 \lambda} X^T \boldsymbol \beta$. By letting $\boldsymbol \alpha = \cfrac{1}{2 \lambda} \boldsymbol \beta$, and putting $\mathbf e$ and $\mathbf w$ back to $\mathcal L_p(\mathbf w, \mathbf e ; C)$, we get dual Lagrangian $\mathcal L_d(\boldsymbol \alpha, \lambda; C) = -\lambda^2 \| \boldsymbol \alpha \|^2 + 2 \lambda \, \boldsymbol \alpha^T y - \lambda \| X^T \boldsymbol \alpha \| - \lambda C$. If we take a derivative w.r.t. $\boldsymbol \alpha$, we get $\boldsymbol \alpha = (XX^T - \lambda I)^{-1} \mathbf y$ - the same answer as for usual Kernel Ridge regression. There's no need to take a derivative w.r.t $\lambda$ - it depends on $C$, which is a regularization parameter - and it makes $\lambda$ regularization parameter as well.

Next, put $\boldsymbol \alpha$ to the primal form solution for $\mathbf w$, and get $\mathbf w = \cfrac{1}{2 \lambda} X^T \boldsymbol \beta = X^T \boldsymbol \alpha$. Thus, the dual form gives the same solution as usual Ridge Regression, and it's just a different way to come to the same solution.

Kernel Ridge Regression

Kernels are used to calculate inner product of two vectors in some feature space without even visiting it. We can view a kernel $k$ as $k(\mathbf x_1, \mathbf x_2) = \phi(\mathbf x_1)^T \phi(\mathbf x_2)$, although we don't know what $\phi(\cdot)$ is - we only know it exists. There are many kernels, e.g. RBF, Polynonial, etc.

We can use kernels to make our Ridge Regression non-linear. Suppose we have a kernel $k(\mathbf x_1, \mathbf x_2) = \phi(\mathbf x_1)^T \phi(\mathbf x_2)$. Let $\Phi(X)$ be a matrix where each row is $\phi(\mathbf x_i)$, i.e. $\Phi(X) = \begin{bmatrix} — \phi(\mathbf x_1) \,— \\ — \phi(\mathbf x_2) \,— \\ \vdots \\ — \phi(\mathbf x_n) \,— \end{bmatrix}$

Now we can just take the solution for Ridge Regression and replace every $X$ with $\Phi(X)$: $\mathbf w = \Phi(X)^T \, (\Phi(X) \Phi(X)^T + \lambda \, I)^{-1} \mathbf y$. For a new unseen data point $\mathbf x$ we predict its target value $\hat y$ as $\hat y= \mathbf \phi(\mathbf x)^T \Phi(X)^T \, (\Phi(X) \Phi(X)^T + \lambda \, I)^{-1} \mathbf y$.

First, we can replace $\Phi(X) \Phi(X)^T$ by a matrix $K$, calculated as $(K)_{ij} = k(\mathbf x_i, \mathbf x_j)$. Then, $\phi(\mathbf x)^T \Phi(X)^T$ is $\sum\limits_{i = 1}^n \phi(\mathbf x)^T \phi(\mathbf x_i) = \sum\limits_{i = 1}^n k(\mathbf x, \mathbf x_j)$. So here we managed to express every dot product of the problem in terms of kernels.

Finally, by letting $\boldsymbol \alpha = (K + \lambda \, I)^{-1} \mathbf y$ (as previously), we obtain $\hat y= \sum\limits_{i = 1}^n \alpha_i k(\mathbf x, \mathbf x_j)$

References

• Machine Learning I class at TU Berlin
• Elements of Statistical Learning, http://statweb.stanford.edu/~tibs/ElemStatLearn/
• http://mlwiki.org/index.php/Normal_Equation
• http://stat.wikia.com/wiki/Kernel_Ridge_Regression
• http://stat.rutgers.edu/home/tzhang/papers/ml02_dual.pdf
• http://www.ics.uci.edu/~welling/classnotes/papers_class/Kernel-Ridge.pdf
• http://www.cs.nyu.edu/~mohri/mls/lecture_8.pdf