《机器学习中用到的数值分析报告》由会员分享，可在线阅读，更多相关《机器学习中用到的数值分析报告（16页珍藏版）》请在金锄头文库上搜索。
1、 . 第四章 背景知识condition number从优化或者数值计算的角度来说，L2 数有助于处理 condition number 不好的情况下矩阵求逆很困难的问题。如果方阵 A 是奇异的，那么 A 的 condition number 就是正无穷大了。实际上，每一个可逆方阵都存在一个 condition number。对condition number来个一句话总结：condition number 是一个矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的 condition number 在1附近，那么它就是well-conditioned的，如果远大于1，那么它
2、就是 ill-conditioned 的，如果一个系统是 ill-conditioned 的，它的输出结果就不要太相信了。应用如果当我们的样本 X 的数目比每个样本的维度还要小的时候，矩阵X T X 将会不是满秩的，也就是X T X 会变得不可逆，所以w 就没办法直接计算出来了。如果加上L2规则项，就变成了下面这种情况，就可以直接求逆了：condition number一般在矩阵里被定义做最大singular value和最小singular value的比值。一般说来，如果一个矩阵的condition number大于1000，数值计算inv(A)或者解线性方程AX=Y可能会遇到严重的舍入问
3、题，这样的问题通常被称为ill-conditioned。最简单的解决方法是把A的diagonal entries都加上一个微小量delta以后再计算这样做虽然会引入误差，但是可以改善ill-condition。梯度设体系中某处的物理参数(如温度、速度、浓度等)为w，在与其垂直距离的dy处该参数为w+dw，则称为该物理参数的梯度，也即该物理参数的变化率。如果参数为速度、浓度、温度或空间，则分别称为速度梯度、浓度梯度、温度梯度或空间梯度。其中温度梯度在直角坐标系下的表达式如右图。在向量微积分中，标量场的梯度是一个向量场。标量场中某一点上的梯度指向标量场增长最快的方向，梯度的长度是这个最大的变化率。
4、更严格的说，从欧氏空间Rn到R的函数的梯度是在Rn某一点最佳的线性近似。在这个意义上，梯度是雅戈比矩阵的一个特殊情况。在单变量的实值函数的情况，梯度只是导数，或者，对于一个线性函数，也就是线的斜率。梯度一词有时用于斜度，也就是一个曲面沿着给定方向的倾斜程度。可以通过取向量梯度和所研究的方向的点积来得到斜度。梯度的数值有时也被称为梯度。在二元函数的情形，设函数z=f(x,y)在平面区域D具有一阶连续偏导数，则对于每一点P(x,y)D，都可以定出一个向量(f/x)*i+(f/y)*j这向量称为函数z=f(x,y)在点P(x,y)的梯度，记作gradf(x,y)类似的对三元函数也可以定义一个：(f/
5、x)*i+(f/y)*j+(f/z)*k 记为gradf(x,y,z)梯度的本意是一个向量（矢量），表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。方向导数（directional derivative）的通俗解释是：我们不仅要知道函数在坐标轴方向上的变化率方向导数（即偏导数），而且还要设法求得函数在其他特定方向上的变化率。而方向导数就是函数在其他特定方向上的变化率。定义方向导数的精确定义（以三元函数为例）：设三元函数f在点P0（x0，y0，z0）的某邻域有定义，l为从点P0出发的射线，P（x，y，z）为l上且含
6、于邻域的任一点，以（rou）表示P和P0两点间的距离。若极限lim（ (f(P)-f(P0) / ）= lim （l f / ）（当0时）存在，则称此极限为函数f在点P0沿方向l的方向导数。雅可比矩阵二阶导数的集合意义：（1）斜线斜率变化的速度（2）函数的凹凸性.二阶导数是比较理论的、比较抽象的一个量,它不像一阶导数那样有明显的几何意义,因为它表示的是一阶导数的变化率.在图形上,它主要表现函数的凹凸性,直观的说,函数是向上突起的,还是向下突起的.应用：如果一个函数f(x)在某个区间I上有f(x)（即二阶导数）0恒成立,那么对于区间I上的任意x,y,总有：f(x)+f(y)2f(x+y)/2,如
7、果总有f(x)0恒成立,那么在区间I上f(x)的图象上的任意两点连出的一条线段,这两点之间的函数图象都在该线段的下方,反之在该线段的上方.机器学习中梯度下降法和牛顿法的比较在机器学习的优化问题中，梯度下降法和牛顿法是常用的两种凸函数求极值的方法，他们都是为了求得目标函数的近似解。在逻辑斯蒂回归模型的参数求解中，一般用改良的梯度下降法，也可以用牛顿法。由于两种方法有些相似，我特地拿来简单地对比一下。下面的容需要读者之前熟悉两种算法。梯度下降法梯度下降法用来求解目标函数的极值。这个极值是给定模型给定数据之后在参数空间中搜索找到的。迭代过程为：可以看出，梯度下降法更新参数的方式为目标函数在当前参数取
8、值下的梯度值，前面再加上一个步长控制参数alpha。梯度下降法通常用一个三维图来展示，迭代过程就好像在不断地下坡，最终到达坡底。为了更形象地理解，也为了和牛顿法比较，这里我用一个二维图来表示：懒得画图了直接用这个展示一下。在二维图中，梯度就相当于凸函数切线的斜率，横坐标就是每次迭代的参数，纵坐标是目标函数的取值。每次迭代的过程是这样：1. 首先计算目标函数在当前参数值的斜率（梯度），然后乘以步长因子后带入更新公式，如图点所在位置（极值点右边），此时斜率为正，那么更新参数后参数减小，更接近极小值对应的参数。2. 如果更新参数后，当前参数值仍然在极值点右边，那么继续上面更新，效果一样。3. 如果更
9、新参数后，当前参数值到了极值点的左边，然后计算斜率会发现是负的，这样经过再一次更新后就会又向着极值点的方向更新。根据这个过程我们发现，每一步走的距离在极值点附近非常重要，如果走的步子过大，容易在极值点附近震荡而无法收敛。解决办法：将alpha设定为随着迭代次数而不断减小的变量，但是也不能完全减为零。牛顿法原理是利用泰勒公式，在x0处展开，且展开到一阶，即f(x) = f(x0)+(xx0)f(x0)求解方程f(x)=0，即f(x0)+(x-x0)*f(x0)=0，求解x =x1=x0f(x0)/f(x0)，因为这是利用泰勒公式的一阶展开，f(x) = f(x0)+(xx0)f(x0)处并不是完
10、全相等，而是近似相等，这里求得的x1并不能让f（x）=0，只能说f(x1)的值比f(x0)更接近f（x）=0，于是乎，迭代求解的想法就很自然了，可以进而推出x(n+1)=x(n)f(x(n)/f(x(n)，通过迭代，这个式子必然在f（x*）=0的时候收敛。整个过程如下图：2、牛顿法用于最优化在最优化的问题中，线性最优化至少可以使用单纯行法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法。假设任务是优化一个目标函数f，求函数f的极大极小问题，可以转化为求解函数f的导数f=0的问题，这样求可以把优化问题看成方程求解问题（f=0）。剩下的问题就和第一部分提到的牛顿法求解很相似了。这次为了求解f
11、=0的根，把f（x）的泰勒展开，展开到2阶形式：这个式子是成立的，当且仅当x 无线趋近于0。此时上式等价与：求解：得出迭代公式：一般认为牛顿法可以利用到曲线本身的信息，比梯度下降法更容易收敛（迭代更少次数），如下图是一个最小化一个目标方程的例子，红色曲线是利用牛顿法迭代求解，绿色曲线是利用梯度下降法求解。在上面讨论的是2维情况，高维情况的牛顿迭代公式是：其中H是hessian矩阵，定义为：高维情况依然可以用牛顿迭代求解，但是问题是Hessian矩阵引入的复杂性，使得牛顿迭代求解的难度大大增加，但是已经有了解决这个问题的办法就是Quasi-Newton methond，不再直接计算hessian
12、矩阵，而是每一步的时候使用梯度向量更新hessian矩阵的近似。Quasi-Newton method的详细情况我还没完全理解，且听下回分解吧。首先得明确，牛顿法是为了求解函数值为零的时候变量的取值问题的，具体地，当要求解 f()=0时，如果 f可导，那么可以通过迭代公式来迭代求得最小值。通过一组图来说明这个过程。当应用于求解最大似然估计的值时，变成()=0的问题。这个与梯度下降不同，梯度下降的目的是直接求解目标函数极小值，而牛顿法则变相地通过求解目标函数一阶导为零的参数值，进而求得目标函数最小值。那么迭代公式写作：当是向量时，牛顿法可以使用下面式子表示：其中H叫做海森矩阵，其实就是目标函数对
13、参数的二阶导数。通过比较牛顿法和梯度下降法的迭代公式，可以发现两者与其相似。海森矩阵的逆就好比梯度下降法的学习率参数alpha。牛顿法收敛速度相比梯度下降法很快，而且由于海森矩阵的的逆在迭代中不断减小，起到逐渐缩小步长的效果。牛顿法的缺点就是计算海森矩阵的逆比较困难，消耗时间和计算资源。因此有了拟牛顿法。最优化问题中，牛顿法为什么比梯度下降法求解需要的迭代次数更少？牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考
14、虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。wiki上给的图很形象，我就直接转过来了：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。利普希茨连续在在数学中，特别是实分析，利普希茨连续（Lipschitz continuity）以德国数学家鲁道夫利普希茨命名，是一个比通常连续更强的光滑性条件。直觉上，利普希
15、茨连续函数限制了函数改变的速度，符合利普希茨条件的函数的斜率，必小于一个称为利普希茨常数的实数（该常数依函数而定）。在微分方程中，利普希茨连续是皮卡-林德洛夫定理中确保了初值问题存在唯一解的核心条件。一种特殊的利普希茨连续，称为压缩应用于巴拿赫不动点定理。利普希茨连续可以定义在度量空间上以与赋向量空间上；利普希茨连续的一种推广称为赫尔德连续。定义对于在实数集的子集的函数，若存在常数K，使得，则称f符合利普希茨条件，对于f最小的常数K称为f的利普希茨常数。1若K 1，f称为收缩映射。利普希茨条件也可对任意度量空间的函数定义：给定两个度量空间。若对于函数，存在常数K使得则说它符合利普希茨条件。2若存在K 1使得则称f为双普希茨(bi-Lipschitz)的。深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件p.94在求取有约束条件的优化问题时，拉格朗日乘
