scikit-learn/scikit-learn — pull request #778 by jaquesgrobler (2012-04-17 13:40:01+00:00)
Title: W.I.P - Add a Non-negative Garotte module to sklearn

I'm still working on this, and there's a lot to still do, but I thought I'd leave it open to
reviewing so long, seeing as I'm still finding my feet with a lot of this stuff..

The code still has lots of comments that will removed later and cleaned up.
The ``__main__`` function currently houses a little script that I'll turn into an example later.
All the documentation still needs to be done

I'd appreciate any inputs and suggestions with this :)

Here's some exerts from the discussion which lead to this (*from the Scikit-learn mailing list*)

From **Alexandre Gramfort**

>hi,
>
>as soon as we have Immanuel's branch with positive lasso [1] merged we
>could have a non-negative
>Garotte in the scikit. A quick gist (hopefully not too buggy):
>
>https://gist.github.com/2351057
>
>Feed back welcome and if someone is willing to cleanly merge this …
>
>Alex

From **Jaques Grobler**

>Here's a wee summary on the non-negative garrote (NG) i pieced together:
>
>The original non-negative garrote from Breiman (1995) is basically a scaled version of the least square >estimate.
>Basically take a OLS estimator and then shrink that estimator to obtain a more sparse representation.
>The shrinkage is done by multiplying the OLS estimator by some shrinkage factor, say `d`,
>which is found by minimising the sum of square residuals, under the restriction that the `d`'s are positive
>and that some are bound by a certain shrinkage parameter.
>
>The algorithm proposed in this paper, is rather similar to that of the Lars LASSO, but with a complicating
>factor being a non-negative constraint on the shrinkage factor. (See eq. (2) in this paper)
>Once you've computed your shrinkage factor, you basically have your regression coefficients
>seeing as your `NG coefficient` = `shrinkage factor` * `regression coefficient`
>
>He showed it to be a stable selection method and often outperforms it's competitors like
>subset regression and ridge regression.
>The solution path of the NG is piece-wise linear and it's whole path can be computed quickly.
>It is also path-consistent (A solution that contains at least one desirable estimate) given an appropriate >initial estimate. The path-consistency of the NG is highlighted to be in contrast to the fact that the `LASSO` >is not always path consistent (Peng Zhao & Hui Zou, personal communication). It is argued that the NG has >the ability to turn
>a consistent estimate into an estimate that is both consistent in terms of estimation and in terms of variable >selection.
>
>A drawback is the NG's explicit reliance on the full least square estimate, as a small sample size may >cause it to perform poorly - however a ridge regression is suggested as an initial estimate for defining the >NG estimate, instead
>of the least square estimate.

From **Jaques Grobler**

>
>Appart from trying it ourselves to see how it fares, here're some findings:
>
>The simulations that are done in the last mentioned paper by Ming Yuan and Yi Lin,
>http://www2.isye.gatech.edu/statistics/papers/05-25.pdf, they find that the NG seems to do
>generally better than the LASSO (figure 1)
>
>Their second simulations they consider the 4 different models used in the original LASSO paper (Tibshirani, >1996)
>which they use to compare the NG with several other popular methods, inluding the LASSO.
>The results are shown in Table 2 of the above-mentioned paper from which the NG does very well, often >outperforming the other models and being the most successful in variable selection.
>
>They also include one real example using the prostate cancer dataset from Stamey (1989) - the results of >which
>they use to confirm the theory that the path consistency of LASSO depends on the correlationo of the >design matrix whilst that of the NG is always path consistent.
>
>Thought it may be of interest

from **Alexandre Gramfort**

>if you can reproduce this figure 1 using my gist
>
>it would be a sufficient argument for adding this estimator to the scikit.
>