17
$\begingroup$

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?

$\endgroup$
38
$\begingroup$

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.

enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ I am impressed by the well-organized discussion. However, your early reference to "outliers" confused me. It appears the weights $w$ apply to the variables rather than the cases, so how exactly would ridge regression help make the solution robust to outlying cases, as suggested by the illustration? $\endgroup$ – whuber Jan 19 '15 at 19:02
  • $\begingroup$ Excellent answer, Alexey (though I wouldn't call it "simple words")! +1 with no questions asked. You like to write in LaTeX, don't you? $\endgroup$ – Aleksandr Blekh Jan 19 '15 at 19:20
  • 2
    $\begingroup$ I suspect you might be confusing some basic things here. AFAIK, ridge regression is neither a response to nor a way of coping with "noisy observations." OLS already does that. Ridge regression is a tool used to cope with near-collinearity among regressors. Those phenomena are completely different from noise in the dependent variable. $\endgroup$ – whuber Jan 19 '15 at 19:57
  • 1
    $\begingroup$ +1 whuber. Alexey you are right it is overfitting -ie too many parameters for the available data - not really noise. [ and add enough dimensions for fixed sample size and 'any' data set becomes collinear]. So a better 2-d picture for RR would be all the points clustered around (0,1) with a single point at (1,0) ['justifying' the slope parameter]. See ESL fig 3.9,page 67 web.stanford.edu/~hastie/local.ftp/Springer/OLD/…. also look at primal cost function: to increase weight by 1 unit, error must decrease by $1/\lambda$ unit $\endgroup$ – seanv507 Jan 19 '15 at 21:55
  • 1
    $\begingroup$ I believe you meant add $\lambda$ to diagonal elements of $X^TX$ not subtract(?) in the ridge regression section. I applied the edit. $\endgroup$ – Heteroskedastic Jim Nov 11 '18 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.