Shooting Algorithm

Shooting算法是Wenjiang提出的一种优化Lasso(L1 Regularization)和Bridge Regression的算法, 本文以Lasso为例.

对于线性回归问题$\mathbb{y}=X\mathbb{\beta}+\epsilon$, 普通最小二乘法(OLS, ordinary least-square regression)最小化$RSS=(\mathbb{y}-X\mathbb{\beta})^T(\mathbb{y}-X\mathbb{\beta})$, 得到的无偏估计为$\hat{\mathbb{\beta}_{ols}}=(X^TX)^{-1}X^T\mathbb{y}$.

Bridge regression在满足$\sum|\beta_j|^{\gamma}\leq t, \gamma\geq 0$, 当$\gamma=0$时, 得到的就是lasso(L1 Regularization).

现在考虑一下两个问题:

$\min_{\mathbb{\beta}} RSS\hspace{2 pt} subject \hspace{2 pt}to \hspace{2 pt}\sum|\beta_j|^{\gamma}\leq t, \gamma\geq 1, t\geq 0 \tag{P1}$

$\min_{\mathbb{\beta}}(RSS+\lambda\sum|\beta_j|^{\gamma}) \tag{P2}$

$P1$和$P2$是等价的, 亦即对于任意$0\leq \lambda \leq +\infty$存在一个$t\geq 0$, 使得这两个问题有相同的解. $P1$被称作constrained regression, $P2$被称作penalized regression.

令$G(\mathbb{\beta}, X, \mathbb{y}, \lambda, \gamma)=RSS+\lambda\sum|\beta_j|^{\gamma}$. $G$对于$\mathbb{\beta}$是凸的, 并且当$\|\mathbb{\beta}\|\to +\infty$时$G\to +\infty$, 所以$G$是可以被最小化的. 亦即存在$\hat{\mathbb{\beta}}$使得$\hat{\mathbb{\beta}}=arg\hspace{1 pt}\min_{\mathbb{\beta}}G(\mathbb{\beta}, X, \mathbb{y}, \lambda, \gamma)$. 对$G$基于$\beta_j$求偏导, 令$S_j(\mathbb{\beta}, X, \mathbb{y})=\partial RSS / \partial \beta_j$, $d(\beta_j, \lambda, \gamma)=\lambda \gamma|\beta_j|^{\gamma-1}sign(\beta_j)$, 令偏导为0, 得到

$\begin{cases}
S_1(\mathbb{\beta}, X, \mathbb{y}) + d(\beta_1, \lambda, \gamma) = 0 \\

\dots\\

S_p(\mathbb{\beta}, X, \mathbb{y}) + d(\beta_p, \lambda, \gamma) = 0
\end{cases}\tag{P3}$

$P2$可以通过$P3$而求解.

我们考虑$P3$的第$j$个等式:

$S_j(\mathbb{\beta}, X, \mathbb{y}) =  -d(\beta_j, \lambda, \gamma) \tag{1}$

上式的左边为

$LHS=2\mathbb{x}_j^T\mathbb{x}_j\beta_j+\sum_{i\neq j}\mathbb{x}_j^T\mathbb{x}_i\beta_i - \mathbb{x}_j^T\mathbb{y}$

对于固定的$\mathbb{\beta}^{-j}$, 上式是$\beta_j$的线性函数, 其斜率为$2\mathbb{x}_j^T\mathbb{x}_j$.

$(1)$式的右边为$RHS=-\lambda \gamma|\beta_j|^{\gamma-1}sign(\beta_j)$.

$RHS$对于不同的$\gamma$有不同的形状, 如下图所示:



除了在$0<\gamma<2$的$\beta_j=0$处是不可微的, $RHS$在$\gamma>1$都是连续, 可微和单调递减的. 对于$\gamma=1$, 在$\beta_j=0$处有一个跳变. 因此, 等式$(1)$对于$\gamma>1$有唯一解, 对于$\gamma=1$有可能有唯一解, 有可能没有解(跳变处没有解).

Shooting算法(Lasso)

初始解定义为OLS的估计$\hat{\beta_0}$, 从$(\hat{\beta_0}, 0)$点开始, 沿斜率$2\mathbb{x}_j^T\mathbb{x}_j$进行移动. 当碰触到$RHS=-\lambda sign(\beta_j)$的顶部(右上图)或者底部(右下图)时, 等式$P3$有唯一解$\hat{\beta}$, 如果没有碰触到任何点(左下图), 等式$P3$没有解. 可以取值为bridge估计的理论值的极限$\lim_{\gamma\to 1+}\hat{\beta}(\lambda,\gamma)=0$, 所以, 设置$\hat{\beta}=0$



Lasso的Shooting算法为

1. 以OLS估计值为初始值$\hat{\mathbb{\beta}}_0=\hat{\mathbb{\beta}}_{OLS}=(\hat{\beta}_1,...,\hat{\beta}_p)^T$
2. 在第$m$步, 对于$j=1,...,p$, 令$S_0=S_j(0,\hat{\mathbb{\beta}}^{-j},X,\mathbb{y})$, 设置$\hat{\beta}_j=\begin{cases}
   \frac{\lambda-S_0}{2\mathbb{x}_j^T\mathbb{x}_j} & if \hspace{2 pt}S_0>\lambda \\\frac{-\lambda-S_0}{2\mathbb{x}_j^T\mathbb{x}_j} & if\hspace{2 pt} S_0<\lambda \\
   
   0 & if \hspace{2 pt}|S_0|\leq \lambda
   \end{cases}\tag{P3}$在更新了所有的$\hat{\beta_j}$后生成新的估计$\hat{\mathbb{\beta}}_m=(\hat{\beta}_1,...,\hat{\beta}_p)^T$
3. 重复第二步直到$\hat{\mathbb{\beta}}_m$收敛

参考文献:

[1]. Wenjiang J .Fu. Penalized Regressions: The Bridge Versus the Lasso.

Shooting Algorithm

原文：http://www.cnblogs.com/kemaswill/p/4395954.html