lr

constrain

就像我们往常一样，我们这里从一个最实际的例子来进行切入。本文的行文主要是借鉴 Tibshirani 的 lasso 的那篇论文进行介绍的。

回归问题在计算机视觉这个领域是非常非常重要的一个问题。对于一个实际应用的问题，如何设计 loss function 可以说是对问题很好的阐述。而我们最常使用的回归函数主要是：
（1）最小均方，
（2） logistic 回归。本文这里主要从最小均方误差进行切入。

还有就是这里并不着重介绍如何去设计一个损失函数，这里主要是关注一个问题的约束项，也可以说是正则项。需要注意的是，这里要把约束和先验好好地区分一下。大致目的已经阐述完了，我们下面开始进入正题吧。

OLS估计

OLS 估计，也就是 ordinary least square 估计。为了很好的阐述这个问题，我们来定义一下这个问题吧。给定一个$Y$回归子（我们可以认为是数据的标签，或是待表示的数据），一个数据（或是一组基，码本，聚类中心等）$X$，我们需要最小化这个问题：
\begin{equation}\label{OLS}
\beta=argmin_\beta || Y - \beta X ||_F^2
\end{equation}

这就是原始的最小均方估计的形式了，这个问题是有解析解的，这里我们使用$\beta^0$来表示。
\begin{equation}\label{beta0}
\beta^0=(X^T X)^{-1} Y X^T
\end{equation}

但是问题不能简简单的就这么解决了，毕竟问题往往不像是看起来这么简单。

第一个问题：prediction accuracy这里主要涉及的问题就很多了。首先是数据的问题，数据很可能是一个非常相关的（可以说是低秩的），还有就是噪声的问题。还有就是 OLS 通常具有很小的偏置却又很大的方差，也就是我们所说的 overfitting 。

第二个问题：interpretation问题学习到的参数通常是 dense 的，就是说，一个回归子需要很多参数的作用，这样就很难解释到底是在这个问题中起到更重要的作用。利用我们的直觉，我们一般也会认为只有少量的变量才会起到很重要的作用。

before lasso

根据这些问题，前人做了一些列的改进，还有一些问题的重新阐述，定义。下面我们先介绍 lasso 诞生之前的一些解决方案：
（1）subset selection
（2）ridge regression
（3）non negative garotte

subset selection

这个问题来源于矩阵的表示：怎么用原始矩阵中的一些列来表示原来的矩阵，使得误差最小。下面我们用公式可以表示为：
\begin{equation}\label{ss}
A \prod = (A_1 A_2)
\end{equation}

这里的$\prod$是一个置换矩阵，什么意思呢？就是说，我们从原始矩阵中选取一些列组合成矩阵$A_1$，剩下的组合成矩阵$A_2$。然后我们最小化函数：
\begin{equation}\label{ss2}
|| A_1 z - A_2 ||_F^2
\end{equation}

这里我还没有看完就不细说了，不过这个通过数据本身的特性，来进行数据的选取，可以用来 unsupervised feature selection 。

但是这个算法还是存在很多问题的： subset selection 很好的的为模型提供了解释性，但是由于是知识从原来的矩阵选取一个一些列，也就是扔掉一些列，这即使得选取的过程造成这个模型的不鲁棒，同时还降低了预测精度。

ridge regression

这个使我们最熟悉不过的东西了，几乎可以说是无处不在。这个在避免模型过拟合时，最常使用了。那我们就来看看为什么这个会避免过拟合。根据我的习惯，我们还是从函数来看：
\begin{equation}
\begin{split}\label{ridre}
\beta &= argmin_\beta ||Y - \beta X ||_F^2\\
&subject to:\sum ||\beta_j || \leq t
\end{split}
\end{equation}
一般我们还会写作：
\begin{equation}\label{rigre2}
\beta = argmin_\beta ||Y - \beta X ||_F^2 + \lambda || \beta ||
\end{equation}

如果我们使用拉格朗日乘子法，可以发现这两问题是等价的，但是这里肯定是在$t$在某个条件下等价的，这里就不在这里一一赘述了。

PS ：为了表示方面我们这里假设$X$矩阵是规范正交矩阵，也就是说$X^T X = I$对于实际中，这个也是能获取的，例如降维的时候，我们使用 PCA 获取的就是正交基。也就是说之前的$$\beta^0 = Y X^T $$。

那么经过二范数的约束的岭回归的解和原来的 OLS 的解之间有什么关系呢？下面我们给出 Tibshirani 给出的结果：
\begin{equation}\label{ridge-ols}
\beta^2_j=\left( \frac{1}{1+\lambda}\right)\beta^0
\end{equation}

如下图：

The parameters in ridge regression is linearly scaling the OLS

我们可以看到这个问题对参数有了很好的抑制，但是这里的参数还是很 dense 的，因为这里实现了一个缩放的功能，还是不能提供一个很 easily 的解释性。

non negative garotte

这也是比较陌生的东西，因为这个比一般的回归多了一些参数，估计这也是不受大众欢迎的原因吧。那这个东西就近是什么东西呢。来看一下定义吧。
\begin{equation}
\begin{split}\label{garotte}
\beta &= argmin_\beta ||Y - C \beta^0 X ||_F^2\\
&subject to:C_j \geq 0 \sum C_j \leq t
\end{split}
\end{equation}

这里可以看做是对原有的参数的一些缩放，这里可以起到一些参数的抑制的作用。那这里的参数和之前的参数有什么关系呢？

\begin{equation}\label{ridgess-ols}
\beta^g_j=\left( 1-\frac{\lambda}{||\beta^0||}\right)^+\beta^0
\end{equation}

如下图：

The parameters in garotte regression is nonlinearly scaling the OLS

这个抑制已经很接近 lasso ，那我们来看看最后，但是由于这个$C$即取决于原始参数的方向，还取决于其大小，这样的结果是不是很理想的。

lasso

lasso 其实是 least absolute shrinkage and selection operator 。就是字面意思了。问题可以简单的定义为：
\begin{equation}
\begin{split}\label{lassoeq}
\beta &= argmin_\beta ||Y - \beta X ||_F^2\\
&subject to:\sum |\beta_j | \leq t
\end{split}
\end{equation}

这里的参数和之前的参数有什么关系呢？
\begin{equation}\label{l-ols}
\beta^l=sign(\beta^0)(|\beta^0|-\lambda)^+
\end{equation}

如图所示：

The parameters in lasso regression is nonlinearly scaling the OLS

这个就可以很容易的看出这个这个的抑制效果比之前的几种方法都好。

下面我们来证明一下这个$\beta^1$和$\beta^0$之间的关系。由于一范数存在没有单数的点，所以这里我们要给出几个定义。

Definition.1 （subgradient;subdifferential）对于在$p$ 维欧式空间中的凸开子集$\mathcal{U}$上定义的实值函数$f:\mathcal{U}\rightarrow \mathbb{R}$，一个$p$ 维向量$v$称为$f$在点$x_0 \in \mathcal{U}$处的$subgradient$，对于任意的$x \in \mathcal{U}$，满足：
$$ f(x) - f(x_0) \geq v \cdot (x- x_0)$$
由在点$x_0$出所在的$subgradient$所组成的集合称为$x_0$处的$subdifferential$，记作$\partial f(x_0)$。

这里我们讨论的是凸函数，一范数的情况下，我们来看一个简单地一维的情况$f(x)=|x|$，在$x=0$这个点的$subgradient$在$[-1,+1]$这个区间里。

根据这个概念，我们来定义一个全局最优的新定义：

Definition.2（condition for global minimizer）点$x_0$是凸函数$f$的一个全局最小点，当且仅当$0 \in \partial f(x_0)$。

既然做了这么多的铺垫，那我们就开始我们的证明。

首先我们来回忆一下我们的在最小二乘的时候的解是$\beta^0=Y X^T$。由于是一范数我们来分情况证明这个问题吧：

（1）$gradient$存在，也就是说这一点$\overline{\beta}_j \neq 0$:

\begin{equation}\label{r1}
\frac{\partial f(x_0)}{\partial \beta_j} \big |_{\overline{\beta}_j}=0
\end{equation}

也就是说：

\begin{equation}\label{r2}
-2(Y X^T - X^T X \overline{\beta})_j+\lambda sign(\overline{\beta}_j)=0
\end{equation}

然后根据我们之前的正交化的工作，我们可以得到：

\begin{equation}\label{r3}
\overline{\beta}_j=\beta_j^0-\frac{\lambda}{2}sign(\overline{\beta}_j)
\end{equation}

根据这个公式，我们可以很容易的证明一个现象，那就是$\overline{\beta}_j$和$\beta_j^0$是同号的。也就是说：

\begin{equation}\label{r4}
\overline{\beta}_j=sign(\beta_j^0)\left(|\beta_j^0|-\frac{\lambda}{2}\right)=sign(\beta_j^0)|\overline{\beta}_j|
\end{equation}

然后呢，我们就可以得到一个很直观的结果：

\begin{equation}\label{r5}
|\beta_j^0|-\frac{\lambda}{2}=|\overline{\beta_j^0}| \geq 0
\end{equation}

所以呢，在梯度存在的情况下，我们得到的是这样的的结果：

\begin{equation}\label{r6}
\overline{\beta}_j=sign(\beta_j^0)\left( |\beta_j^0 | -\frac{\lambda}{2} \right)_+
\end{equation}

（2）$gradient$不存在，这个时候$\overline{\beta}_j=0$：

这个时候我们就可以用到我们之前的那两个定义了：
\begin{equation}\label{rr6}
\begin{split}
0&=\overline{\beta}_j=\partial f(x_0)={-2(Y X^T -X^T X \overline{\beta})_j+\lambda e:e \in[-1,+1]}\\
&={2\overline{\beta}_j-2\beta_j^0+\lambda e:e\in[-1,+1]}
\end{split}
\end{equation}

然后我们还知道$\overline{\beta}_j=0$，
于是乎：

\begin{equation}\label{r7}
|\beta_j^0|=\frac{\lambda}{2}|e_0| \leq \frac{\lambda}{2} e_0\in[-1,+1]
\end{equation}

然后我们把这两部分统一起来就得到了上面我们我们的所画的图。

Norm ball

下面我们用一个很直观的形式来讲解这些之间的问题。那就是 Donoho 大牛提出了一个很有趣的东西： Norm ball 。其实就是范数的等高线。那我们就来看看这个等高线到底长什么样子呢？

L4,L2,L1,L0.5 Norm ball

Donoho 给了我们一个直观的方式去选着我们需要的约束，为什么这个说，如果我们在这里显式的给出能量函数的等高线，就会一目了然了。我在这里就简要介绍这些问题吧。但是我们通过观测得到一些结论

L1 和 L0.5 范数的图像是具有“尖”的，而且这些“尖”位于坐标轴上，也就是说具有这种性质的是具有稀疏性约束的。$[0,1]$之间的范数都具有稀疏性，现在也有人在研究这些范数，这里就不一一给出了。

L2 范数是不具有上面的性质的，因为这个 Norm ball 是极致光滑的，用一个很形象的描述就是这个范数不偏向任何一方，各个分量的比值只和能量函数的中心有关。

还有就是 L4 范数，这个范数可以看到和 L1 范数有个可以说是相反的约束，这个范数更希望这个分量是均匀，也就是每一个分量尽可能的差不多。

PS： 这里我就不列文献了$>. <$。