2
$\begingroup$

For homework I have been given a 20-dimensional input $x \in \mathbb{R}^{20}$, many of which are suspected to be irrelevant. I tried using L1-norm Lasso regularization to uncover which dimensions contribute to the output:

$$L(\beta) = \sum_{i=1}^n (y_i - \phi(x_i)^T \cdot \beta)^2 + \lambda \sum_{j = 1}^k l(\beta_j)$$

Please note, that instead of $|\beta_j|$ another function is used, where

$$l(\beta_j) = \begin{cases} |\beta_j| - \varepsilon/2 & \textbf{if } |\beta_j| \geq \varepsilon\\ |\beta_j^2| / (2\varepsilon) & \textbf{if } |\beta_j| < \varepsilon\\ \end{cases}$$

With the resulting gradient:

$$\frac{\partial}{\partial\beta} L(\beta) = -2 \sum_{i=1}^n - \phi(x_i) \cdot (y_i - \phi(x_i)^T \cdot \beta) + \frac{\partial}{\partial\beta_m}\sum_{j=1}^kl(\beta_j)$$

$$ \frac{\partial}{\partial\beta_m}\sum_{j=1}^kl(\beta_j)= \begin{cases} 0&m\gt k\;,\\ sign(\beta_m)&m\le k\;,|\beta_m|\ge\epsilon\;,\\ sign(\beta_m)/\epsilon&m\le k\;,|\beta_m|\lt\epsilon\;. \end{cases} $$

In order to find the minimum I applied gradient descent on the differentiated Lasso function and received a $\beta$ vector after 6 to 10 iterations. However, I don't see how this helps me to uncover the irrelevant dimensions. How should I proceed?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Why don't you do principal component analysis since the first few compoents may explain most of the variation in the data? You can look at those componets and see which variables have coefficients significantly larger than 0 ( not speaking of statistical significance here). $\endgroup$
    – Michael R. Chernick
    Commented May 7, 2012 at 15:34
  • $\begingroup$ Because sadly this is not my assignment (mind the homework tag). But thanks anyway for the hint, but can this not applied to this method as well? Unfortunately the resulting $\beta$ vectors components are all quite similar. $\endgroup$
    – Mahoni
    Commented May 7, 2012 at 15:43
  • 2
    $\begingroup$ I think you've left out a term, $\lambda$ below, that scales the relative importance of the penalty function and the fitting function: $$L(\beta) = \sum_{i=1}^n (y_i - \phi(x_i)^T \cdot \beta)^2 + \lambda \sum_{j = 1}^k l(\beta_j)$$ By varying $\lambda$ you can drive varying numbers of the $\beta_j$ to zero. As TenaliRaman has observed (+1), "the dimensions corresponding to which there is a zero entry in the $\beta$ vector are your irrelevant ones." This may be beyond the scope of your assignment, but $\lambda$ can be chosen via cross-validation or some such. $\endgroup$
    – jbowman
    Commented May 7, 2012 at 17:04
  • 3
    $\begingroup$ Is that $l(\beta_j) =$ first line correct? Or should it be $|\beta_j| - \varepsilon/2$? (That might also account for the difficulty you mentioned in the comments responding to @TenaliRaman.) $\endgroup$
    – jbowman
    Commented May 7, 2012 at 22:46
  • 2
    $\begingroup$ Great! I'll also point out that the quadratic nature of the penalty function near 0 means that you won't have the parameters being driven all the way to zero, just to some number less than $\epsilon$. Assuming $\epsilon$ is small, basically there just to ensure differentiability at $\beta_j=0$, you could use $|\beta_j| \leq \epsilon$ as your criterion for irrelevance of dimension $j$. That would explain the findings you observed in one of your comments to TenaliRaman's answer. $\endgroup$
    – jbowman
    Commented May 9, 2012 at 17:03

1 Answer 1

Reset to default
5
$\begingroup$

Since you are doing L1-norm regularization, the $\beta$ vector that you will get will be very sparse. The dimensions corresponding to which there is a zero entry in the $\beta$ vector are your irrelevant dimensions.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Sounds reasonable, and with which $\beta$ should I start the gradient descent? Using a zero vector leads only to a zero vector in result. Currently I use the optimal $\beta$, computed as: $$\beta = (X^T X)^{-1} X^T y$$ $\endgroup$
    – Mahoni
    Commented May 7, 2012 at 20:07
  • $\begingroup$ Unfortunately there are no zero entries, but entries which are very little. In my 20-dim $\beta$ vector, there are $3$ entries with values $\leq -1$. the rest is more or less $\geq -0.25$. I hope it can be interpreted in that way, that these $3$ entries contribute to the result and the rest more or less not. $\endgroup$
    – Mahoni
    Commented May 7, 2012 at 20:32
  • 1
    $\begingroup$ @Mahoni What you say doesn't sound quite right. You have a convex optimization problem here, so it shouldn't matter where you start. I would suggest checking your code and your derivations again. Also, the optimal $\beta$ that you state is optimal only for the unregularized convex optimization problem and not for the regularized as in your case. $\endgroup$
    – TenaliRaman
    Commented May 7, 2012 at 20:33
  • $\begingroup$ So there was a mistake with the function definition $l(x)$ as you can read in the comments of jbowman in my original question. It works now at last. $\endgroup$
    – Mahoni
    Commented May 9, 2012 at 15:12
  • $\begingroup$ @Mahoni Excellent! :-) $\endgroup$
    – TenaliRaman
    Commented May 9, 2012 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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