lasso

感谢博客：http://blog.sina.com.cn/s/blog_e386b39f0102vzsj.html
概要：前文已经分析完岭回归在多元线性回归分析中的作用和使用方法，也发现其存在大量不足，在本博文中会介绍和学习岭回归的改进方法：Lasso。
    先来看一下Lasso的官方定位：
LASSO ​
Tibshirani(1996)提出了Lasso(The Least Absolute Shrinkage and  Selectionator operator)算法。 ​
    通过构造一个一阶惩罚函数获得一个精炼的模型；通过最终确定一些指标（变量）的系数为零（岭回归估计系数等于0的机会微乎其微，造成筛选变量困难），解释力很强. 擅长处理具有多重共线性的数据，跟岭回归一样是有偏估计。
    来解释一下主要表达的意思，首先Lasso是一种最小绝对收缩选择算法（直译），跟岭回归一样是有偏估计，但比岭回归好的是可以方便删除无效变量（系数为零即无效），因此不用靠人眼去主观筛选变量。
 
LASSO vs 岭回归   
                 
                   
      图3.41和3.42是岭回归的两种表现形式，3.51和3.52图是Lasso的两种表达方式，这里的λ就是岭参数k。我们发现Lasso与岭回归的区别就是约束条件（subject to）不一样，但Lasso的约束条件是线性的，肯定比非线性计算方便。因此我们选择Lasso作为删选方法。（Lasso的解比岭回归容易最为判断依据，但求解构过程也很复杂，具体求解方法会在下文提及）。
 
    来看一下岭回归岭迹图
                                   λ即k，该图的纵坐标表示不同变量（指标）的系数，横坐标表示λ的变化
 
   Lasso的岭迹图
横坐标收缩因子s即λ

性质：变量系数为0即可说明该变量无效。
分析两个岭迹图，结论：
1，岭回归的变量无效删选更复杂。
2，岭回归存在变量系数从0变大又变0的无用过程（变量无贡献到有贡献又回到无贡献）。
3，Lasso岭迹图的0点明显，容易挑选。
综上所述，用Lasso作为删选变量的工具更有可实际操作性。那么问题又来了，如何求出Lasso的解呢？或如何得到Lasso的岭迹图？这里就要介绍一个求解Lasso的机智方法：LAR。
 
 
        在介绍LAR之前，先要说明一下有关相关系数的知识补充（自信的朋友可以略过）：


       r表示X，Y的相关性，r越高，X，Y就越相关，若X，Y是二维向量，就说明X，Y两个向量越接近（可以被互相表示）
通常情况下通过以下取值范围判断变量的。
相关系数     相关强度：
0.8-1.0     极强相关   
0.6-0.8     强相关                
0.4-0.6     中等程度相关                
0.2-0.4     弱相关              
0.0-0.2     极弱相关或无相关
 
 
    好了，如果这里我们假设Xi，Yi与，计算的结果为二维单位向量，再反观r的计算公式：
 

        该手稿转自http://f.dataguru.cn/thread-448966-1-1.html（炼数成金），可以发现r最终就是X，Y标准化后的夹角余弦值。 所以夹角越小，cosθ就越大，越接近1，即表示相关系数越大。（也可以解释相关系数的取值范围[-1,1]）
 
 
好了解释完相关系数，就让我们正式进入LAR的学习。
 
LAR（最小角回归） 
 
    Least Angel Regression Efron于2004年提出的一种变量选择的方法，类似于向前逐步回(Forward Stepwise)的形式。是lasso regression的一种高效解法。
与向前逐步回归(Forward Stepwise)不同点在于，Forward Stepwise 每次都是根据选择的变量子集，完全拟合出线性模型，计算出RSS，再设计统计量（如AIC）对较高的模型复杂度作出惩罚。
而LAR是每次先找出和因变量相关度最高的那个变量, 再沿着LSE的方向一点点调整这个predictor的系数，在这个过程中，这个变量和残差的相关系数会逐渐减小，等到这个相关性没那么显著的时候，就要选进新的相关性最高的变量，然后重新沿着LSE的方向进行变动。而到最后，所有变量都被选中，就和LSE相同了。
这里的LSE我觉得就是Least-Squares Coefficient

翻译算法：
1，样本因变量r=Y-向量（中心化），.
2，找到和r向量夹角最小的向量Xi，记最初夹角为θ0（图中即角1），βi记为(r-Xi）和Xi的余弦值记为cosθi=。当βi（Xi的系数，用于控制Xi的长短）从cosθ0到cos90的范围内变化时（途中X1长度由0到垂直交点），θ也会变大。
3，这时，当夹角θj （图中角2） βiXi,Xj> 和θi（角3）一样大时（三维坐标），就把Xj向量也加入模型。同时改变βi，βj的系数，即在θj  >的角平分线上继续前进。
4，重复3步骤，直到所有X分量都被包含。
解释图：


 
   这里说明一个问题，由于开始找的X1向量是与r夹角最小的，在角3变化时，一定能达到角2的值（假设X分量与r都是正相关）。
 
        如此如此，就可以依次求出相关性由高到低的X变量，得到最优解。观察过程图可以发现几个变量正好是逐个合并，按照新的方向前进。
        解释完LAR算法，我们来比较一下，Lasso的普通求解方式和LAR的区别：
        发现两种求解的结果近似相同，但LAR的求解方法效率更高，速度更快。至于背后的原理，这里略过不提。
接下来，我们用统计语言R进行实际操作一下。​
 
 
    首先要在R语言中安装LARS包​​
>install.packages("lars")​
>library(lars)​
    用Longley数据​​
>w=as.matrix(longley)
> laa=lars(x=w[, 2:7],y=w[,1])​
> plot(laa)​
    得到lasso图​
填写图片摘要（选填）
可以调用laa模型，观察去除的变量的过程。​
>laa​
填写图片摘要（选填）
上图可以发现，在第6步后，出现反复进出的变量值，说明这些变量存在震荡，应该去除。最后观察残差值​
>summary(laa)​
填写图片摘要（选填） 
cp​值越小越好，最后看第8步，去掉5,6号变量。至此，删选变量过程结束。最终我们需要的变量是1,2,3,4。
 
 
    部分内容参考《炼数成金》机器学习，M03课程pdf。炼数成金网站：http://www.dataguru.cn/
 
 
 

Lasso(Least absolute shrinkage and selection operator, Tibshirani(1996))方法是一种压缩估计。它通过构造一个罚函数得到一个较为精炼的模型，使得它压缩一些系数，同时设定一些系数为零。因此保留了子集收缩的优点，是一种处理具有复共线性数据的有偏估计。

　　Lasso 的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下，使残差平方和最小化，从而能够产生某些严格等于0 的回归系数，得到可以解释的模型。




lasso回归：

lasso回归的特色就是在建立广义线型模型的时候，这里广义线型模型包含一维连续因变量、多维连续因变量、非负次数因变量、二元离散因变量、多元离散因变，除此之外，无论因变量是连续的还是离散的，lasso都能处理，总的来说，lasso对于数据的要求是极其低的，所以应用程度较广；除此之外，lasso还能够对变量进行筛选和对模型的复杂程度进行降低。这里的变量筛选是指不把所有的变量都放入模型中进行拟合，而是有选择的把变量放入模型从而得到更好的性能参数。
 复杂度调整是指通过一系列参数控制模型的复杂度，从而避免过度拟合(Overfitting)。 对于线性模型来说，复杂度与模型的变量数有直接关系，变量数越多，模型复杂度就越高。 更多的变量在拟合时往往可以给出一个看似更好的模型，但是同时也面临过度拟合的危险。




lasso的复杂程度由λ来控制，λ越大对变量较多的线性模型的惩罚力度就越大，从而最终获得一个变量较少的模型。除此之外，另一个参数α来控制应对高相关性(highly
 correlated)数据时模型的性状。 LASSO回归α=1，Ridge回归α=0，这就对应了惩罚函数的形式和目的。我们可以通过尝试若干次不同值下的λ，来选取最优λ下的参数，还可以结合CV选择最优秀的模型。




1.
代码版
Comparison of the LASSO and adaptive LASSO estimators





2.中文版
http://blog.csdn.net/xbinworld/article/details/44276389




如前面的ridge regression，对w做2范式约束，就是把解约束在一个l2-ball里面，放缩是对球的半径放缩，因此w的每一个维度都在以同一个系数放缩，通过放缩不会产生稀疏的解——即某些w
的维度是0。而实际应用中，数据的维度中是存在噪音和冗余的，稀疏的解可以找到有用的维度并且减少冗余，提高回归预测的准确性和鲁棒性（减少了overfitting）？




3.写的最好
http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/

lasso的由来和python实现
lasso 的目标函数
Subgradient
aka shooting algorithm
python 实现AK 射击算法
实验结果


lasso源自Least Absolute Selection and Shrinkage Operator，讲的是通过lasso回归选择了全部变量的一个子集，通过引入绝对值惩罚项来收缩系数。如果你只想知道题目，下面的内容其实可以不用看咧。

lasso 的目标函数
lasso最小化函数如下，特点就是在0不可导，需要用到subgradient.

，
Subgradient
subgradient 即如下图在两边取极限的中间地带，即不能保证最快下降但是只是是下降的。可以得到一个lasso目标函数实例的subgradient。




aka shooting algorithm
这个射击算法是根据subgradient设计的，soft 展开其实就是上面$f(\theta$的subgradient。为啥叫soft threshoding呢？threshoding好理解就搞个阈值弄个平台出来，是否对应的也有hard thresholding？答案是肯定的，区别见下图（左边是soft,右边是hard）。




python 实现AK 射击算法
实现ak 射击算法主要要注意利用numpy 基于一个个元素的广播乘法，尽可能并行计算，还有就是w每个维度更新都会影响下一个维度的取值，因此这办法我只能选择写成一个loop,无法使用numpy广播。
	def shooting(self,obj,w_0,X,y,max_num_pass_through=100,fitness=10**(-8)):

		num_pass_through = 0
		n, num_ftrs = X.shape
		w = w_0.copy()
		a = 2 * np.sum(X ** 2, 0)
		while num_pass_through < max_num_pass_through:
			for j in range(0, num_ftrs):
				pre_dict = np.dot(X, w)
				yi = y - pre_dict
				c = 2 * np.sum(X[:, j] * (yi + w[j] * X[:, j]))
				if a[j] == 0:
					w[j] = 0
				else:
					para_1 = c / a[j]
					para_2 = self.l1reg / a[j]
					sign = para_1 / abs(para_1)
					diff = abs(para_1) - para_2
					soft_diff = (abs(diff) + diff) / 2
					w[j] = sign * soft_diff
			num_pass_through = num_pass_through + 1
		return w

实验结果
看一下不同l1正则化参数的回归效果吧