2
$\begingroup$

I've been using kernel ridge regression. My problem requires predicting some values which I know to be integers. By rounding the results to the nearest decimal, I get excellent results.

However, If there's potential for more improvement - I'd like to try it!

I recalled that the $l_1$ penalty usually results in fewer small errors (possibly at the expense of large errors becoming larger). That is: $$ \min_w \lVert Xw-y\rVert_1 +\frac 1 2w^Tw$$

Might have fewer small errors (or smaller small errors).

However, aside from the lack of a closed-form solution for this problem, I'm actually looking for more small errors, at the expense of large ones, since I can round them off and hopefully get something better.

I figured taking a higher power for the error could do what I want, but then I'd lose the closed-form solution. One of the problems would be that the problem will no longer be quadratic, which means no closed-form minimum.

I can't see a way to get what I want, but I'm hoping there might be one.

A quick overview of Ridge regression (just in case): Ridge regression is a regularized least-squares problem: $$ min_w \frac 1 2 \lVert Xw-y\rVert ^2_2 + \frac 1 2 w^TQw $$ where $X$ is a matrix, with each line representing a different sample, $y$ is a vector of desired values, and $Q$ is a symmetric positive definite matrix.

Deriving by $w$ yields $$X^T Xw-X^Ty +Qw =0$$ This yields $$ w= (X^TX+Q)^{-1}X^Ty$$ As a closed-form solution (Since $Q$ is positive definite, so is $(X^TX+Q)$, meaning it is invertible).

$\endgroup$
  • 1
    $\begingroup$ What don't you use black-box optimization tools (e.g., convex optimization, gradient descent, etc.) instead of looking for a closed-form solution? Usually in practice a closed-form solution is not that important, if you can solve it using other optimization methods. $\endgroup$ – D.W. Jan 16 '15 at 18:21
  • $\begingroup$ I thought that the penalty terms defining ridge/lasso are on the parameter values, rather than the actual fit of the function. That is to say, you wouldn't use $\ell_1$ on $||Xw - y||$, but rathern $\lambda ||w||_1$. Rergardless, l1 minimization can be solved by reformulating as an LP in higher dimension. Make a new variable to hold the positive and negative value for the original parameter. Off-the-shelf LP solvers are super fast and you should be good to go. $\endgroup$ – Nicholas Mancuso Jan 17 '15 at 4:04
  • $\begingroup$ @D.W. I've SVR, and I'm familiar enough with convex optimization to make some variations. However, the problem I'm working on requires real-time learning, which could be impractical for iterative methods. Methods with a closed solution are much easier to implement using optimized linear algebra software (such as LAPACK). I've tried formulating the problem as a LP/QP problem, but since I need to retrain the model (every time new data appears, I retrain. That's how the professor wants it done), It's impractical. $\endgroup$ – user1999728 Jan 17 '15 at 8:20
  • $\begingroup$ @NicholasMancuso You are correct about LASSO. When I've shown isn't LASSO, but more like SVR, which uses $l_1$ penalty for the error, rather than the regularization. $\endgroup$ – user1999728 Jan 17 '15 at 8:21

Your Answer

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

Browse other questions tagged or ask your own question.