引子：欠定线性等式 (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\}\)
