数学基础

几乎所有的机器学习算法最后都归结为求一个目标函数的极值，即最优化问题，例如对于有监督学习，我们要找到一个最佳的映射函数f(x)，使得对训练样本的损失函数最小化（最小化经验风险或结构风险）：

在这里，N为训练样本数，L是对单个样本的损失函数，w是要求解的模型参数，是映射函数的参数，为样本的特征向量，为样本的标签值。

或是找到一个最优的概率密度函数p(x)，使得对训练样本的对数似然函数极大化（最大似然估计）：

在这里， θ是要求解的模型参数，是概率密度函数的参数。

对于无监督学习，以聚类算法为例，算法要使得每个类的样本离类中心的距离之和最小化：

在这里k为类型数，x为样本向量，为类中心向量，为第i个类的样本集合。

对于强化学习，我们要找到一个最优的策略，即状态s到动作a的映射函数（确定性策略，对于非确定性策略，是执行每个动作的概率）：

使得任意给定一个状态，执行这个策略函数所确定的动作a之后，得到的累计回报最大化，这里使用的是状态价值函数：

总体来看，机器学习的核心目标是给出一个模型（一般是映射函数），然后定义对这个模型好坏的评价函数（目标函数），求解目标函数的极大值或者极小值，以确定模型的参数，从而得到我们想要的模型。在这三个关键步骤中，前两个是机器学习要研究的问题，建立数学模型。第三个问题是纯数学问题，即最优化方法。

对于最优化方法，可以给出一个最优化问题精确的公式解，但也有求极值点的精确计算公式非常困难的情况，那么就需要用数值计算方法近似求解来得到最优点。除此之外，还有其他一些求解思想，如分治法，动态规划等。一个好的优化算法需要满足：速度快，且能正确的找到各种情况下的极值点。

对于一个可导函数，寻找其极值的统一做法是寻找导数为0的点，即费马定理。对于多元函数，则是梯度为0。需要注意的是，导数为0只是函数取得极值的必要条件而不是充分条件，它只是疑似极值点。在多元函数中，驻点对应的就是鞍点。除鞍点外，最优化算法可能还会遇到另外一个问题：局部极值问题，即一个驻点是极值点，但不是全局极值。

如果我们对最优化问题加以限定，可以有效的避免这两种问题。在最优化中，凸优化是最为常见而又最为重要的，因为凸优化有一个良好的性质：局部最优是全局最优，这个性质使得我们不需要去证明解是否会收敛到全局最优，或者如何避免局部最优。因此凸优化有广泛应用，在优化问题不是凸的时候，往往也会尝试将其变为凸问题便于求解。

最速下降法是一种常用的一阶优化方法，是求解无约束优化问题最简单、最经典的方法之一。从数学上的角度来看，梯度的方向是函数增长速度最快的方向，那么梯度的反方向就是函数减少最快的方向。那么，如果想计算一个函数的最小值，就可以使用最速下降法的思想来做。

牛顿法是用目标函数的二阶泰勒展开近似该目标函数，通过求解这个二次函数的极小值来求解凸优化的搜索方向。牛顿法非常快，对于正定二次函数迭代一次就可以达到目标函数的最值。

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。