1、最优化问题的数学描述
最优化的基本数学模型如下：本质上就是求得函数的极值
这里可以引出最优化问题的三个基本要素：
实数域R上（或复数C上）的向量空间中，如果集合S中任两点的连线上的点都在S内，则称集合S为凸集，如下图所示：
数学定义为：
设集合
，若对于任意两点
，及实数
都有：
则称集合 D 为凸集。
2、超平面和半空间
实际上，二维空间的超平面就是一条线（可以使曲线），三维空间的超平面就是一个面（可以是曲面）。其数学表达式如下：
超平面：
半空间：
3、凸集分离定理
所谓两个凸集分离，直观地看是指两个凸集合没有交叉和重合的部分，因此可以用一张超平面将两者隔在两边，如下图所示：
3、凸函数
凸函数就是一个定义域在某个向量空间的凸子集 C 上的实值函数。
数学定义为：
对于函数 f(x)，如果其定义域 C 是凸的，且对于∀x,y∈C，
，
有：
则 f(x) 是凸函数。
注：如果一个函数是凸函数，则其局部最优点就是它的全局最优点。这个性质在机器学习算法优化中有很重要的应用，因为机器学习模型最后就是在求某个函数的全局最优点，一旦证明该函数（机器学习里面叫 “损失函数”）是凸函数，那相当于我们只用求它的局部最优点了。
4、梯度下降算法
4.1、梯度
在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。函数f(x,y), 梯度向量就是
,简称
或者
(哈密顿算子▽)。
从几何意义上讲，函数变化增加最快的地方就是梯度，也就是一种高维导数。具体来说，对于函数f(x,y),在点(x,y)，沿着梯度向量的方向就是的方向是f(x,y)增加最快的地方。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，也就是 
的方向，梯度减少最快，也就是更加容易找到函数的最小值。
梯度下降法和梯度上升法是可以互相转化的。比如我们需要求解损失函数f(θ)的最小值，这时我们需要用梯度下降法来迭代求解。但是实际上，我们可以反过来求解损失函数 -f(θ)的最大值，这时梯度上升法就派上用场了。 
4.2、梯度下降的直观解释与推导过程
比如我们在一座大山上的某处位置，由于我们不知道怎么下山，于是决定走一步算一步，也就是在每走到一个位置的时候，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。这样一步步的走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能我们不能走到山脚，而是到了某一个局部的山峰低处。
从上面的解释可以看出，梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。
推导过程
令为多元函数
,则
可以视作两个向量的内积
又因为梯度指向的是最大值的方向，所以需要相反
，此时的
称作学习率
4.3、梯度下降的相关概念
- 步长/学习率（Learning rate）：步长决定了在梯度下降迭代的过程中，每一步沿梯度负方向前进的长度。用上面下山的例子，步长就是在当前这一步所在位置沿着最陡峭最易下山的位置走的那一步的长度。可以保持恒定或者采用一位搜索等方法进行不断的变化。
- 特征（feature）：指的是样本中输入部分，比如2个单特征的样本
则第一个样本特征为
，第一个样本输出为
。 - 假设函数（hypothesis function）：在监督学习中，为了拟合输入样本，而使用的假设函数，记为
。比如对于单个特征的m个样本
,可以采用拟合函数如下：
。 - 损失函数（loss function）：为了评估模型拟合的好坏，通常用损失函数来度量拟合的程度。损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。在线性回归中，损失函数通常为样本输出和假设函数的差取平方。比如对于m个样本
，采用线性回归，损失函数为： 
其中
表示第 i 个样本特征，
表示第 i 个样本对应的输出，
为假设函数。4.4、梯度下降的详细算法
梯度下降法的算法可以有代数法和矩阵法（也称向量法）两种表示，如果对矩阵分析不熟悉，则代数法更加容易理解。不过矩阵法更加的简洁，且由于使用了矩阵，实现逻辑更加的一目了然。这里先介绍代数法，后介绍矩阵法。4.4.1、 梯度下降法的代数方式描述
- 先决条件： 确认优化模型的假设函数和损失函数。
比如对于线性回归，假设函数表示为
, 其中
为模型参数，
为每个样本的n个特征值。这个表示可以简化，我们增加一个特征
，这样
。
同样是线性回归，对应于上面的假设函数，损失函数为：
2. 算法相关参数初始化：主要是初始化
,算法终止距离
以及步长
。在没有任何先验知识的时候，我喜欢将所有的
初始化为0， 将步长初始化为1。在调优的时候再优化。
3. 算法过程：
1）确定当前位置的损失函数的梯度，对于
,其梯度表达式如下：
2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即
对应于前面登山例子中的某一步。
3）确定是否所有的,梯度下降的距离都小于，如果小于则算法终止，当前所有的
即为最终结果。否则进入步骤4.
4）更新所有的，对于，其更新表达式如下。更新完毕后继续转入步骤1.
下面用线性回归的例子来具体描述梯度下降。假设我们的样本是
,损失函数如前面先决条件所述：
则在算法过程步骤1中对于
的偏导数计算如下：
由于样本中没有
上式中令所有的
为1.
步骤4中的更新表达式如下：
从这个例子可以看出当前点的梯度方向是由所有的样本决定的，加
是为了好理解。由于步长也为常数，他们的乘机也为常数，所以这里
可以用一个常数表示。
在下面第4节会详细讲到的梯度下降法的变种，他们主要的区别就是对样本的采用方法不同。这里我们采用的是用所有样本。4.4.2、梯度下降法的矩阵方式描述
这一部分主要讲解梯度下降法的矩阵方式表述，相对于3.3.1的代数法，要求有一定的矩阵分析的基础知识，尤其是矩阵求导的知识。
1. 先决条件： 和3.3.1类似， 需要确认优化模型的假设函数和损失函数。对于线性回归，假设函数的矩阵表达方式为：
，其中， 假设函数
为m×1的向量,
为(n+1)×1的向量，里面有n个代数法的模型参数。
为m×(n+1)维的矩阵。m代表样本的个数，n+1代表样本的特征数。
损失函数的表达式为：
, 其中
是样本的输出向量，维度为m×1.
2. 算法相关参数初始化:向量可以初始化为默认值，或者调优后的值。算法终止距离，步长和3.3.1比没有变化。
3. 算法过程：
1）确定当前位置的损失函数的梯度，对于
向量,其梯度表达式如下：
2）用步长乘以损失函数的梯度，得到当前位置下降的距离，即
对应于前面登山例子中的某一步。
3）确定
向量里面的每个值,梯度下降的距离都小于，如果小于则算法终止，当前
向量即为最终结果。否则进入步骤4.
4）更新向量，其更新表达式如下：
。更新完毕后继续转入步骤1
还是用线性回归的例子来描述具体的算法过程。
损失函数对于向量的偏导数计算如下：
步骤4中向量的更新表达式如下：
对于3.3.1的代数法，可以看到矩阵法要简洁很多。这里面用到了矩阵求导链式法则，和两个矩阵求导的公式。
公式1：
公式2：
如果需要熟悉矩阵求导建议参考张贤达的《矩阵分析与应用》一书。4.5、梯度下降的算法调优
在使用梯度下降时，需要进行调优。哪些地方需要调优呢？
- 算法的步长选择。在前面的算法描述中，我提到取步长为1，但是实际上取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果。可以采用一维搜索等别的方法让步长随着梯度的变化自动更改。
- 算法参数的初始值选择。 初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。
归一化。由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征x，求出它的期望
和标准差std(x)，然后转化为：
这样特征的新期望为0，新方差为1，迭代次数可以大大加快。
4.6、梯度下降法大家族（BGD，SGD，MBGD）
4.6.1、批量梯度下降法（Batch Gradient Descent）
批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新，这个方法对应于线性回归的梯度下降算法，也就是说之前的梯度下降算法就是批量梯度下降法。
由于我们有m个样本，这里求梯度的时候就用了所有m个样本的梯度数据。4.6.2、随机梯度下降法（Stochastic Gradient Descent）
随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的m个样本的数据，而是仅仅选取一个样本j来求梯度。对应的更新公式是：
（没有
）
随机梯度下降法，和批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。
那么，有没有一个中庸的办法能够结合两种方法的优点呢？有！这就是小批量梯度下降法。4.6.3、小批量梯度下降法（Mini-batch Gradient Descent）
小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用x个样子来迭代，1
4.7、梯度下降法和其他无约束优化算法的比较
在机器学习中的无约束优化算法，除了梯度下降以外，还有前面提到的最小二乘法，此外还有牛顿法和拟牛顿法。
梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。
梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解。相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长。
5、牛顿法
1、牛顿法介绍
牛顿法也是求解无约束最优化问题常用的方法，最大的优点是收敛速度快。
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。通俗地说，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法 每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以， 可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。
或者从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
2、牛顿法的推导
将目标函数
在
处进行二阶泰勒展开，可得：
因为目标函数
有极值的必要条件是在极值点处一阶导数为 0，即：
所以对上面的展开式两边同时求导（注意
才是变量，
是常量
都是常量），并令
可得：
即：
于是可以构造如下的迭代公式：
这样，我们就可以利用该迭代式依次产生的序列
才逐渐逼近
的极小值点了。
牛顿法的迭代示意图如下：
上面讨论的是 2 维情况，高维情况的牛顿迭代公式是：
式中， ▽
是
的梯度，即：
H 是 Hessen 矩阵，即：
3、牛顿法的过程
6-7、阻尼牛顿法
1、引入
注意到，牛顿法的迭代公式中没有步长因子，是定步长迭代。对于非二次型目标函数，有时候会出现
的情况，这表明，原始牛顿法不能保证函数值稳定的下降。在严重的情况下甚至会造成序列发散而导致计算失败。
为消除这一弊病，人们又提出阻尼牛顿法。阻尼牛顿法每次迭代的方向仍然是
，但每次迭代会沿此方向做一维搜索，寻求最优的步长因子
，即：
2、算法过程
6-8、拟牛顿法
1、概述
由于牛顿法每一步都要求解目标函数的Hessen 矩阵的逆矩阵，计算量比较大（求矩阵的逆运算量比较大），因此提出一种改进方法，即通过正定矩阵近似代替 Hessen 矩阵的逆矩阵，简化这一计算过程，改进后的方法称为拟牛顿法。
2、拟牛顿法的推导
先将目标函数在
处展开，得到：
两边同时取梯度，得：
取上式中的
，得：
即：
可得：
上面这个式子称为“拟牛顿条件”，由它来对 Hessen 矩阵做约束。
6、拉格朗日乘子法与KKT条件
对于一般的求极值问题我们都知道，求导等于 0 就可以了。但是如果我们不但要求极值，还要求一个满足一定约束条件的极值，那么此时就可以构造 Lagrange 函数，其实就是把约束项添加到原函数上，然后对构造的新函数求导。
对于一个要求极值的函数
，图上的蓝圈就是这个函数的等高图，就是说 
分别代表不同的数值 (每个值代表一圈，等高图)，我要找到一组
，使它的
值越大越好，但是这点必须满足约束条件
（在黄线上）。
也就是说
和
相切，或者说它们的梯度▽
和▽
平行，因此它们的梯度（偏导）成倍数关系；那我么就假设为
倍，然后把约束条件加到原函数后再对它求导，其实就等于满足了下图上的式子。
在支持向量机模型（SVM）的推导中一步很关键的就是利用拉格朗日对偶性将原问题转化为对偶问题。
7、最小二乘法
dashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzcdashdkashdjkahsdlkjahsdkjahstesxzc
8、最大似然估计
最大似然也称为最大概似估计，即：在 “模型已定，参数θ未知” 的情况下，通过观测数据估计未知参数θ 的一种思想或方法。
其基本思想是： 给定样本取值后，该样本最有可能来自参数
为何值的总体。即：寻找
使得观测到样本数据的可能性最大。
举个例子，假设我们要统计全国人口的身高，首先假设这个身高服从服从正态分布，但是该分布的均值与方差未知。由于没有足够的人力和物力去统计全国每个人的身高，但是可以通过采样（所有的采样要求都是独立同分布的），获取部分人的身高，然后通过最大似然估计来获取上述假设中的正态分布的均值与方差。
求极大似然函数估计值的一般步骤：
- 1、写出似然函数；
- 2、对似然函数取对数；
- 3、两边同时求导数；
- 4、令导数为 0 解出似然方程。
在机器学习中也会经常见到极大似然的影子。比如后面的逻辑斯特回归模型（LR），其核心就是构造对数损失函数后运用极大似然估计。
若有收获，就点个赞吧
0 人点赞
