作者 | 小小挖掘机
泉源 | SIGAI
数学1.枚举 常用的最优化要领
梯度下降法
牛顿法，
拟牛顿法
坐标下降法
梯度下降法的刷新 型如AdaDelta，AdaGrad，Adam，NAG等。
2.梯度下降法的要害点
梯度下降法沿着梯度的反偏向举行 搜索，使用 了函数的一阶导数信息。梯度下降法的迭代公式为：
凭证 函数的一阶泰勒睁开 ，在负梯度偏向，函数值是下降的。只要学习率设置的足够小，而且没有到达梯度为0的点处，每次迭代时函数值一定会下降。需要设置学习率为一个很是小的正数的缘故原由 是要保证迭代之后的xk+1位于迭代之前的值xk的邻域内，从而可以忽略泰勒睁开 中的高次项，保证迭代时函数值下降。
梯度下降法只能保证找到梯度为0的点，不能保证找到极小值点。迭代终止的判断 依据是梯度值充实靠近 于0，或者到达最大指定迭代次数。
梯度下降法在机械学习中应用普遍 ，尤其是在深度学习中。AdaDelta，AdaGrad，Adam，NAG等刷新 的梯度下降法都是用梯度结构更新项，区别在于更新项的结构方式差异。
3.牛顿法的要害点
牛顿法使用 了函数的一阶和二阶导数信息，直接寻找梯度为0的点。牛顿法的迭代公式为：
其中H为Hessian矩阵，g为梯度向量。牛顿法不能保证每次迭代时函数值下降，也不能保证收敛到极小值点。在实现时，也需要设置学习率，缘故原由 和梯度下降法相同，是为了能够忽略泰勒睁开 中的高阶项。学习率的设置通常接纳直线搜索（line search）手艺 。
在实现时，一样平常 不直接求Hessian矩阵的逆矩阵，而是求解下面的线性方程组：
其解d称为牛顿偏向。迭代终止的判断 依据是梯度值充实靠近 于0，或者到达最大指定迭代次数。
牛顿法比梯度下降法有更快的收敛速率 ，但每次迭代时需要盘算Hessian矩阵，并求解一个线性方程组，运算量大。另外，若是 Hessian矩阵不行逆，则这种要领失效。
4.拉格朗日乘数法
拉格朗日乘数法是一个理论效果 ，用于求解带有等式约束的函数极值。对于如下问题：
结构拉格朗日乘子函数：
在最优点处对x和乘子变量的导数都必须为0：
解这个方程即可获得最优解。对拉格朗日乘数法更详细的解说可以阅读任何一本高等数学课本 。机械学习中用到拉格朗日乘数法的地方有：
主因素 剖析
线性判别剖析
流形学习中的拉普拉斯特征映射
隐马尔科夫模子
5.凸优化
数值优化算法面临两个方面的问题：局部极值，鞍点。前者是梯度为0的点，也是极值点，但不是全局极小值；后者连局部极值都不是，在鞍点处Hessian矩阵不定，即既非正定，也非负定。
凸优化通过对目的 函数，优化变量的可行域举行 限制 ，可以保证不会遇到上面两个问题。凸优化是一类特殊的优化问题，它要求：
优化变量的可行域是一个凸集
目的 函数是一个凸函数
凸优化最好的一个性子 是：所有局部最优解一定是全局最优解。机械学习中典型的凸优化问题有：
线性回归
岭回归
LASSO回归
Logistic回归
支持向量机
Softamx回归
6.拉格朗日对偶
对偶是最优化要领里的一种要领，它将一个最优化问题转换成另外一个问题，二者是等价的。拉格朗日对偶是其中的典型例子。对于如下带等式约束和不等式约束的优化问题：
与拉格朗日乘数法类似，结构广义拉格朗日函数：
必须知足
的约束。原问题为：
即先牢靠 住x，调整拉格朗日乘子变量，让函数L取极大值；然后控制变量x，让目的 函数取极小值。原问题与我们要优化的原始问题是等价的。
对偶问题为：
和原问题相反，这里是先控制变量x，让函数L取极小值；然后控制拉格朗日乘子变量，让函数取极大值。
一样平常 情形 下，原问题的最优解大于即是对偶问题的最优解，这称为弱对偶。在某些情形 下，原问题的最优解和对偶问题的最优解相等，这称为强对偶。
强对偶建设的一种条件是Slater条件：一个凸优化问题若是 存在一个候选x使得所有不等式约束都是严酷 知足 的，即对于所有的i都有gi (x)0，不等式不取等号，则强对偶建设，原问题与对偶问题等价。注重 ，Slater条件是强对偶建设的充实条件而非须要条件。
拉格朗日对偶在机械学习中的典型应用是支持向量机。
7.KKT条件
KKT条件是拉格朗日乘数法的推广，用于求解既带有等式约束，又带有不等式约束的函数极值。对于如下优化问题：
和拉格朗日对偶的做法类似，KKT条件构如下乘子函数：
λ和μ称为KKT乘子。在最优解处
应该知足 如下条件：
等式约束
和不等式约束
是自己应该知足 的约束，
和之前的拉格朗日乘数法一样。唯一多了关于gi (x)的条件：
KKT条件只是取得极值的须要条件而不是充实条件。
8.特征值与特征向量
对于一个n阶矩阵A，若是 存在一个数λ和一个非0向量X，知足 ：
则称λ为矩阵A的特征值，X为该特征值对应的特征向量。凭证 上面的界说有下面线性方程组建设：
凭证 线性方程组的理论，要让齐次方程有非0解，系数矩阵的行列式必须为0，即：
上式左边的多项式称为矩阵的特征多项式。矩阵的迹界说为主对角线元素之和：
凭证 韦达定理，矩阵所有特征值的和为矩阵的迹：
同样可以证实 ，矩阵所有特征值的积为矩阵的行列式：
使用 特征值和特征向量，可以将矩阵对角化，即用正交变换将矩阵化为对角阵。实对称矩阵一定可以对角化，半正定矩阵的特征值都大于即是0，在机械学习中，许多矩阵都知足 这些条件。特征值和特征向量在机械学习中的应用包罗：正态贝叶斯分类器、主因素 剖析 ，流形学习，线性判别剖析 ，谱聚类等。
9.奇异值剖析
矩阵对角化只适用于方阵，若是 不是方阵也可以举行 类似的剖析，这就是奇异值剖析，简称SVD。假设A是一个m x n的矩阵，则存在如下剖析：
其中U为m x m的正交矩阵，其列称为矩阵A的左奇异向量；
为m x n的对角矩阵，除了主对角线
以外，其他元素都是0；V为n x n的正交矩阵，其行称为矩阵A的右奇异向量。U的列为AAT的特征向量，V的列为AT A的特征向量。
10.最大似然预计
有些应用中已知样本听从的概率漫衍，可是 要预计漫衍函数的参数
，确定这些参数常用的一种要领是最大似然预计。
最大似然预计结构一个似然函数，通过让似然函数最大化，求解出θ。最大似然预计的直观诠释 是，追求 一组参数，使得给定的样本集泛起的概率最大。
假设样本听从的概率密度函数为
，其中X为随机变量，θ为要预计的参数。给定一组样本xi,i =1,...,l，它们都听从这种漫衍，而且相互自力 。最大似然预计结构如下似然函数：
其中xi是已知量，这是一个关于θ的函数，我们要让该函数的值最大化，这样做的依据是这组样本发生了，因此应该最大化它们发生的概率，即似然函数。这就是求解如下最优化问题：
乘积求导不易处置赏罚 ，因此我们对该函数取对数，获得对数似然函数：
最后要求解的问题为：
最大似然预计在机械学习中的典型应用包罗logistic回归，贝叶斯分类器，隐马尔科夫模子 等。
基本看法1.有监视学习与无监视学习
凭证 样本数据是否带有标签值，可以将机械学习算法分成有监视学习和无监视学习两类。有监视学习的样本数据带有标签值，它从训练样本中学习获得一个模子 ，然后用这个模子 对新的样本举行 展望 推断。有监视学习的典型代表是分类问题和回归问题。
无监视学习对没有标签的样本举行 剖析 ，发现样本集的结构或者漫衍纪律。无监视学习的典型代表是聚类，体现学习，和数据降维，它们处置赏罚 的样本都不带有标签值。
2.分类问题与回归问题
在有监视学习中，若是 样本的标签是整数，则展望 函数是一个向量到整数的映射，这称为分类问题。若是 标签值是一连 实数，则称为回归问题，此时展望 函数是向量到实数的映射。
3.天生 模子 与判别模子
分类算法可以分成判别模子 和天生 模子 。给定特征向量x与标签值y，天生 模子 对团结 概率p(x,y)建模，判别模子 对条件概率p(y|x)举行 建模。另外，不使用概率模子 的分类器也被归类为判别模子 ，它直接获得展望 函数而不体贴样本的概率漫衍：
判别模子 直接获得展望 函数f(x)，或者直接盘算概率值p(y|x)，好比SVM和logistic回归，softmax回归，判别模子 只体贴决议 面，而不管样本的概率漫衍的密度。
天生 模子 盘算p(x, y)或者p(x|y) ，通俗来说，天生 模子 假设每个类的样本听从某种概率漫衍，对这个概率漫衍举行 建模。
机械学习中常见的天生 模子 有贝叶斯分类器，高斯混淆模子 ，隐马尔可夫模子 ，受限玻尔兹曼机，天生 反抗网络等。典型的判别模子 有决议 树，kNN算法，人工神经网络，支持向量机，logistic回归，AdaBoost算法等。
4.交织验证
交织验证（cross validation）是一种统计准确率的手艺 。k折交织验证将样本随机、匀称 的分成k份，轮流用其中的k-1份训练模子 ，1份用于测试模子 的准确率，用k个准确率的均值作为最终的准确率。
5.过拟合与欠拟合
欠拟合也称为欠学习，直观体现是训练获得的模子 在训练集上体现差，没有学到数据的纪律。引起欠拟合的缘故原由 有模子 自己过于简朴，例如数据自己是非线性的但使用了线性模子 ；特征数太少无法准确 的建设映射关系。
过拟合也称为过学习，直观体现是在训练集上体现好，但在测试集上体现欠好，推普遍 化性能差。过拟合发生的基础缘故原由 是训练数据包罗抽样误差，在训练时模子 将抽样误差也举行 了拟合。所谓抽样误差，是指抽样获得的样本集和整体数据集之间的误差 。引起过拟合的可能缘故原由 有：
模子 自己过于重大 ，拟合了训练样本集中的噪声。此时需要选用更简朴的模子 ，或者对模子 举行 裁剪。训练样本太少或者缺乏代表性。此时需要增添 样本数，或者增添 样本的多样性。训练样本噪声的滋扰，导致模子 拟合了这些噪声，这时需要剔除噪声数据或者改用对噪声不敏感的模子 。
6.误差 与方差剖析
模子 的泛化误差可以剖析成误差 和方差。误差 是模子 自己导致的误差，即错误的模子 假设所导致的误差，它是模子 的展望 值的数学期望和真实值之间的差距。
方差是由于对训练样本集的小颠簸敏感而导致的误差。它可以明确 为模子 展望 值的转变 规模，即模子 展望 值的颠簸水平。
模子 的总体误差可以剖析为误差 的平方与方差之和：
若是 模子 过于简朴，一样平常 会有大的误差 和小的方差；反之若是 模子 重大 则会有大的方差但误差 很小。
7.正则化
为了防止过拟合，可以为损失函数加上一个处罚项，对重大 的模子 举行 处罚，强制让模子 的参数值尽可能小以使得模子 更简朴，加入处罚项之后损失函数为：
正则化被普遍 应用于种种机械学习算法，如岭回归，LASSO回归，logistic回归，神经网络等。除了直接加上正则化项之外，尚有 其他强制让模子 变简朴的要领，如决议 树的剪枝算法，神经网络训练中的dropout手艺 ，提前终止手艺 等。
8.维数灾难
为了提高算法的精度，会使用越来越多的特征。当特征向量维数不高时，增添 特征确实可以带来精度上的提升；可是 当特征向量的维数增添 到一定值之后，继续增添 特征反而会导致精度的下降，这一问题称为维数灾难。
贝叶斯分类器贝叶斯分类器将样本判断 为后验概率最大的类，它直接用贝叶斯公式解决分类问题。假设样本的特征向量为x，种别 标签为y，凭证 贝叶斯公式，样本属于每个类的条件概率（后验概率）为：
分母p(x)对所有类都是相同的，分类的规则是将样本归到后验概率最大的谁人 类，不需要盘算准确的概率值，只需要知道属于哪个类的概率最大即可，这样可以忽略掉分母。分类器的判别函数为：
在实现贝叶斯分类器时，需要知道每个类的条件概率漫衍p(x|y)即先验概率。一样平常 假设样本听从正态漫衍。训练时确定先验概率漫衍的参数，一样平常 用最大似然预计，即最大化对数似然函数。
若是 假设特征向量的各个分量之间相互自力 ，则称为质朴 贝叶斯分类器，此时的分类判别函数为：
实现时可以分为特征分量是离散变量和一连 变量两种情形 。贝叶斯分分类器是一种天生 模子 ，可以处置赏罚 多分类问题，是一种非线性模子 。
决议 树决议 树是一种基于规则的要领，它用一组嵌套的规则举行 展望 。在树的每个决议 节点处，凭证 判断效果 进入一个分支，重复执行这种操作直到到达叶子节点，获得展望 效果 。这些规则通过训练获得，而不是人工制订 的。
决议 树既可以用于分类问题，也可以用于回归问题。分类树的映射函数是多维空间的分段线性划分，用平行于各坐标轴的超平面临 空间举行 切分；回归树的映射函数是分段常数函数。决议 树是分段线性函数而不是线性函数。只要划分的足够细，分段常数函数可以迫近闭区间上恣意 函数到恣意 指定精度，因此决议 树在理论上可以对恣意 重大 度的数据举行 拟合。对于分类问题，若是 决议 树深度够大，它可以将训练样本集的所有样本准确 分类。
决议 树的训练算法是一个递归的历程，首先建设根节点，然后递归的建设左子树和右子树。若是 练样本集为D，训练算法的流程为：
1.用样本集D建设根节点，找到一个判断 规则，将样本集破碎 成D1和D2两部门，同时为根节点设置判断 规则。
2.用样本集D1递归建设左子树。
3.用样本集D2递归建设右子树。
4.若是 不能再举行 破碎 ，则把节点标志为叶子节点，同时为它赋值。
对于分类树，若是 接纳Gini系数作为怀抱准则，决议 树在训练时寻找最佳破碎 的依据为让Gini不纯度最小化，这等价于让下面的值最大化：
寻找最佳破碎 时需要盘算用每个阈值对样本集举行 破碎 后的纯度值，寻找该值最大时对应的破碎 ，它就是最佳破碎 。若是 是数值型特征，对于每个特征将l个训练样本凭证 该特征的值从小到大排序，假设排序后的值为：
接下来从x1最先 ，依次用每个xi作为阈值，将样天职成左右两部门，盘算上面的纯度值，该值最大的谁人 破碎 阈值就是此特征的最佳破碎 阈值。在盘算出每个特征的最佳破碎 阈值和上面的纯度值后，较量 所有这些破碎 的纯度值巨细，该值最大的破碎 为所有特征的最佳破碎 。
决议 树可以处置赏罚 属性缺失问题，接纳的要领是使用替换 破碎 规则。为了防止过拟合，可以对树举行 剪枝，让模子 变得更简朴。
决议 树是一种判别模子 ，既支持分类问题，也支持回归问题，是一种非线性模子 ，它支持多分类问题。
随机森林随机森林是一种集成学习算法，是Bagging算法的详细 实现。集成学习是机械学习中的一种头脑 ，而不是某一详细 算法，它通过多个模子 的组合形成一个精度更高的模子 ，加入组合的模子 称为弱学习器。在展望 时使用这些弱学习器模子 团结 举行 展望 ，训练时需要依次训练出这些弱学习器。
随机森林用有放回抽样（Bootstrap抽样）组成出的样本集训练多棵决议 树，训练决议 树的每个节点时只使用了随机抽样的部门特征。展望 时，对于分类问题，一个测试样本会送到每一棵决议 树中举行 展望 ，然后投票，得票最多的类为最终分类效果 。对于回归问题，随机森林的展望 输出是所有决议 树输出的均值。
假设有n个训练样本。训练每一棵树时，从样本集中有放回的抽取n个样本，每个样本可能会被抽中多次，也可能一次都没抽中。若是 样本量很大，在整个抽样历程中每个样本有0.368的概率不被抽中。由于样本集中各个样本是相互自力 的，在整个抽样中所有样本约莫有36.8%没有被抽中。这部门样本称为包外（Out Of Bag，简称OOB）数据。
用这个抽样的样本集训练一棵决议 树，训练时，每次寻找最佳破碎 时，还要对特征向量的分量采样，即只思量 部门特征分量。由于使用了随机抽样，随机森林泛化性能一样平常 较量 好，可以有用 的降低模子 的方差。
若是 想更详细的相识 随机森林的原理，请阅读SIGAI之前的民众号文章“随机森林概述”。随机森林是一种判别模子 ，既支持分类问题，也支持回归问题，而且支持多分类问题，这是一种非线性模子 。
AdaBoost算法AdaBoost算法也是一种集成学习算法，用于二分类问题，是Boosting算法的一种实现。它用多个弱分类器的线性组合来展望 ，训练时重点关注错分的样本，准确率高的弱分类器权重大。AdaBoost算法的全称是自顺应 ，它用弱分类器的线性组合来结构强分类器。弱分类器的性能不用太好，仅比随机推测强，依赖 它们可以结构出一个很是准确的强分类器。强分类器的盘算公式为：
其中x是输入向量，F(x)是强分类器，ft(x)是弱分类器，at是弱分类器的权重，T为弱分类器的数目 ，弱分类器、的输出值为+1或-1，划分对应正样本和负样本。分类时的判断 规则为：
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
强分类器的输出值也为+1或-1，同样对应于正样本和负样本。
训练时，依次训练每一个若分类器，并获得它们的权重值。训练样本带有权重值，初始时所有样本的权重相等，在训练历程中，被前面的弱分类器错分的样本会加大权重，反之会减小权重，这样接下来的弱分类器会越发关注这些难分的样本。弱分类器的权重值凭证 它的准确率结构，精度越高的弱分类器权重越大。
给定l个训练样本(xi,yi )，其中xi是特征向量，yi为种别 标签，其值为+1或-1。训练算法的流程为：
凭证 盘算公式，错误率低的弱分类器权重大，它是准确率的增函数。AdaBoost算法在训练样本集上的错误率会随着弱分类器数目 的增添 而指数级降低。它能有用 的降低模子 的误差 。
AdaBoost算法从广义加法模子 导出，训练时求解的是指数损失函数的极小值：
求解时接纳了分阶段优化，先获得弱分类器，然后确定弱分类器的权重值，这就是弱分类器，弱分类器权重的泉源 。除了离散型AdaBoost之外，从广义加法模子 还可以导出其他几种AdaBoost算法，划分是实数型AdaBoost，Gentle型AdaBoost，Logit型AdaBoost，它们使用了差异的损失函数和最优化算法。
尺度的AdaBoost算法是一种判别模子 ，只能支持二分类问题。它的刷新 型可以处置赏罚 多分类问题。
搜索进入我们的小法式，解锁更多新鲜资讯和优质内容，尚有 许多免费试听课程，不要错过哟！