EdX Columbia ML 6. 稀疏线性回归

引子:欠定线性等式 (underdetermined linear equations)

这里考虑的是\(y = Xw, X \in \mathbb{R}^{n \times d} (d >\!\!> n)\)的问题。即数据集的维数大于样本数。此时\(w\)有无穷多个解满足\(y = Xw\)。在这些解中,\(w_{\rm ln} = X^T(XX^T)^{-1}y\)占据着一个重要的地位。如果把这个解加上一个\(X\)的零空间\(\mathcal{N}\)中的向量\(\delta \in \mathbb{R}^d\),得到的新的权重仍然是原始问题的解。 \[ \delta \in \mathcal{N}(X) \Rightarrow X\delta = 0 \land \delta \not= 0 \\ \therefore X(w_{\rm ln} + \delta) = Xw_{\rm ln} + X\delta = y + 0 \] 而因为\(d > n\),因此\(\delta\)可以有无限多个。

下面用两种方法证明\(w_{\rm ln}\)是这些解里\(\ell_2\)范数最小的解,即 \[ w_{\rm ln} = {\rm arg}\min_w |\!|w|\!|^2\ \ \ {\rm subject\ to}\ Xw = y \]

分析法

\(w\)\(Xw=y\)的另一个解,因此\(X(w-w_{\rm ln}) = 0\),且有 $$ \[\begin{align*} (w - w_{\rm ln})^Tw_{\rm ln} &= (w - w_{\rm ln})^TX^T(XX^T)^{-1}y \\ &= (X(w - w_{\rm ln}))^T(XX^T)^{-1}y = 0 \end{align*}\] $$

\(w-w_{\rm ln}\)正交于\(w_{\rm ln}\),这意味着

\[ \begin{align*} |\!|w|\!|^2 &= |\!|w - w_{\rm ln} + w_{\rm ln}|\!|^2 \\ &= |\!|w - w_{\rm ln}|\!|^2 + |\!|w_{\rm ln}|\!|^2 + 2(w - w_{\rm ln})^Tw_{\rm ln} \\ &= |\!|w - w_{\rm ln}|\!|^2 + |\!|w_{\rm ln}|\!|^2 \\ &> |\!|w_{\rm ln}|\!|^2 \end{align*} \] $ $

Lagrange乘子法

为了求解 \[ {\rm arg}\min_w |\!|w|\!|^2\ \ \ {\rm subject\ to}\ Xw = y \] 可以引入Lagrange乘子,即 \[ \mathcal{L}(w, \eta) = w^Tw + \eta^T(Xw - y) \] 分别对\(w\)\(\eta\)求导,得到两个条件 \[ \nabla_w \mathcal{L} = 2w + X^T\eta = 0,\ \nabla_{\eta}\mathcal{L} = Xw - y = 0 \] 由第一个式子可知 \[ w = -X^T\eta / 2 \] 代入到第二个式子解得 \[ \eta = -2(XX^T)^{-1}y \]\(\eta\)代回第一个式子 \[ w_{\rm ln} = X^T(XX^T)^{-1}y \]

稀疏回归

普通最小二乘和岭回归通常只用于理想情况。现实问题中,通常有很多特征,而其中只有一部分与\(y\)相关,非常重要,而普通最小二乘和岭回归对所有特征都是同等对待,重要的特征会被不重要的特征拉低

通常来讲,优化问题都可以抽象为公式 \[ {\rm total\ cost} = {\rm goodness\ of\ fit\ term} + {\rm penalty\ term} \] 前者说明模型\(f\)对数据的近似有多好,后者使得最后的解不会那么“重”。岭回归的惩罚项是\(|\!|w|\!|^2\),而这个惩罚项的特点是,如果\(w\)很大,那么缩小它能够很快地缩小惩罚项;然而如果\(w\)小,那么缩小它的效果就不显著。因此使用这个惩罚项的结果是所有特征的权重都小了

稀疏学习的目的是选出\(d\)维特征的一个子集作为模型,而筛掉其它维度的特征,也就是把不重要的特征权重设为0。常用线性惩罚项——引出了LASSO

LASSO: Least Absolute Shrinkage and Selection Operator,使用\(\ell_1\)正则项 \[ w_{\rm lasso} = {\rm arg}\min_w |\!|y - Xw|\!|^2_2 + \lambda |\!|w|\!|_1 \\ |\!|w|\!|_1 = \sum_{j=1}^d |w_j| \]

正则化可以推广到\(\ell_p\)正则化回归,即 \[ w_{\ell_p} = {\rm arg}\min_w |\!|y - Xw|\!|^2_2 + \lambda |\!|w|\!|_p^p \\ |\!|w|\!|_p^p = \left(\sum_{j=1}^d |w_j|^p \right)^{\frac{1}{p}} \]

其中\(\ell_1\)正则化是LASSO,\(\ell_2\)正则化是岭回归

\(p = \infty\)时,惩罚项只惩罚最大的那一项,\(|\!|w|\!|_\infty = \max_j |w_j|\)\(1 < p < 2\)时,可以找到最优解,但是只能通过迭代方式解出(没有解析解) 当\(0 < p < 1\)时,只能找到近似解,不过可以保证稀疏性 当\(p \rightarrow 0\)时,只记录某一项是否为0,即\(|\!|w|\!|_0 = \sum_j \mathbb{I}\{w_j \not= 0\}\)

坚持原创技术分享,您的支持将鼓励我继续创作!