最近由于赶论文的deadline专栏一直没有更新，也没怎么看书，所以还是只能吃老底，上次写了数学估计方法，这次就来写一下数学优化方法吧

还有一点就是下面马上就该讲线性回归，感知机，决策树什么的了，我一直没有什么好点子该怎么把这部分写出来，我的想法是不推导和写公式，直接撸代码，如果看到这篇文的人能够给出建议就好了。

封面：电影《幽灵公主》

1.最小二乘

最小二乘法也是我最近看一个论文的实现才注意的方法，之前很多人说线性最小二乘怎么怎么不好，但在我自己测试了随机梯度下降和线性最小二乘的效果之后，发现线性最小二乘的效果竟然比梯度下降好。现在numpy等科学计算库这么多，求个逆求个点积分分钟的事，在线性优化问题上，最小二乘法还是一个值得有限考虑的选择。

考虑线性优化问题如下：

obj(eta^{T}) = frac{1}{n}sum_{i=1}^{n}{(eta^{T}x_{i}-y_{i})^{2}}

然后我们把问题矩阵化，可以写成这样的形式：

obj(eta^{T})=||eta^{T}X-Y||^{2}

这里X是所有列向量x组成的矩阵，我们需要求得线性函数obj的最值，而我们知道当函数对参数beta的导数为0时，函数取得最值，因此只要求obj(eta)=0 时beta的值即可。

即求：

2（eta^TX-Y）X^{T}=0

至于这个式子怎么求导来的，下次我想写一写矩阵求导的法则来好好整理一下。

当XX^T是一个可逆矩阵时，就可以解出来啦：

eta^{T}=YX^{T}(XX^{T})^{-1}

当然如果XXT是不可逆的怎么办？那么可以通过增加正则项的方法，让XX_t变成满秩矩阵的方法来解决。

2. 梯度下降

梯度下降法可以说是最常用的优化方法了，它可以解决线性或非线性优化问题，亦可以解决凸优化或非凸优化问题，梯度下降法还有很多变种包括随机梯度下降，牛顿法，拟牛顿法，共轭梯度下降。

2.1 梯度下降

相同的优化问题：

obj(eta^{T}) = frac{1}{n}sum_{i=1}^{n}{(eta^{T}x_{i}-y_{i})^{2}}

对于该目标函数，我们采用一种迭代的思路一步一步走，最终到达一个极值点，然后求得使其最小或者最大的参数，像这样

额

那么我们去过要走到那个想要去的地方，就得知道往哪里走和走多少，这时想起我们在高数中学到的梯度的概念：

梯度的本意是一个向量（矢量），表示某一函数在该点处的方向导数沿著该方向取得最大值，即函数在该点处沿著该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。

那么我们只要每一步都沿著梯度方向走，就可以走到我们想要去的那个点。

梯度的计算方法说白了就是求偏导：

grad(obj(eta^T))=2(eta^TX-Y)X^T

然后我们设置一个步长alpha，也就是在这个梯度方向上每一步我们走多少，然后我们就有了迭代公式：

eta^Tleftarroweta^T+alpha*grad(obj(eta^T))

在几何上导数就是斜率嘛，这样一直迭代到低谷的时候，斜率就靠近0了，所以最后参数是可以收敛到一个值的。

2.2 随机梯度下降

和梯度下降不同的地方是，梯度下降每次迭代要计算所有样本的平均梯度，而随机梯度下降，每次只算一个样本的梯度，这样就会变得很快，因为我们假设样本是独立同分布的，所以这样还可以避免冗余的梯度计算。

grad(obj(eta^T))=2(eta^Tx_{i}-y_i)x_{i}^T

其中x_i是每次随机选一个样本，这样实际上可能所有的样本就用不完就迭代完了。

2.3 共轭梯度下降

共轭梯度法的思想就是找到n个两两共轭的共轭方向，每次沿著一个方向优化得到该方向上的极小值，后面再沿其它方向求极小值的时候，不会影响前面已经得到的沿哪些方向上的极小值，所以理论上对n个方向都求出极小值就得到了n维问题的极小值。

它要求新的搜索方向与前面所有的搜索方向是共轭的……共轭是啥

两向量间的一种特殊关系.设A为n×n对称正定矩阵，向量p1，p2∈R.若满足条件p1Ap2=0，则称p1和p2关于A是共轭方向，或称p1和p2关于A共轭.

我们的obj(beta_T)可以把二范数展开变成，最后两项是常数：

eta^TXX^Teta-2YX^T-YY^T

然后对于参数beta，y可以由XXT的n个共轭向量表示，其中di是XX_T的基，ai是系数：

eta=sum_{i=1}^na_id_i

然后目标函数可以展开为:

min_{a_1,...,a_nin R^n}frac{1}{2}sum_{i=1}^n(a_i^2d_i^TXX^Td_i)

然后我们分别优化a_i，最后再通过上面的表达式把beta加出来。

3. 牛顿法

3.1 原始牛顿法

牛顿法据说是牛顿提出的优化方法，和梯度下降一样也是一种迭代优化方法，但是比梯度下降要快很多，因为它是一种使用二阶导数的方法，以前一直搞不懂二阶在哪里，现在才刚刚看懂。

牛顿法迭代思路在于使用泰勒展开，假设我们要求 f(x)=0 ，我们可以通过一阶泰勒展开在附近选择一个点x_0使得：

f(x)=f(x_0)+(x-x_0)f(x_0)=0

这里一阶导数就是：

2(eta^TX-Y)X^T

虽然一阶泰勒展开只是一个粗略的拟合，但是求得的x一定比x_0所在的点更接近于0，然后下一步我们继续这样做，最终就能迭代收敛。

让我困惑的是这个方法哪里用到二阶导数了，然后才反应过来是这样的道理。

我们要求的是函数的最值，最值就是导数等于零的点，求让导数等于零的点就要对导数进行一阶泰勒展开，也就有了二阶导数。

f(x)=f(x_0)+(x-x_0)f(x_0)=0

这样就可以迭代求出参数了。

3.2 拟牛顿法

很麻烦的一个东西是二阶导数是对偏导的偏导，在特征特征维度很高的时候这个方法根本没法用，这个二阶导数会是个m*m的矩阵，因为最后化简形式是一阶导除以二阶导，所以我们要求这个大矩阵的逆，非常麻烦。这个大矩阵其中的某个元素是：

H_{i,j}=frac{partial^2 (obj(eta^T))}{partialeta^T_1 partialeta^T_2}

其实这个求出来就是XX_T (小声逼逼

然后拟牛顿法就是用一个正定矩阵去代替这个海森矩阵H的逆，具体这个正定矩阵怎么求，有两个方法DFP演算法和BFGS演算法，有兴趣可以去查一查。


推荐阅读：
查看原文 >>
相关文章