量化共轭梯度法,如何理解共梯度

本文为 AI 研习社编译的技术博客，原标题 ：

The base of deep reinforcement learning-Conjugate Gradient

作者 | Jonathan Hui

翻译 | 斯蒂芬•二狗子

校对 | 斯蒂芬•二狗子 审核| 酱番梨 整理 | 菠萝妹

原文链接：

https://medium.com/@jonathan_hui/rl-conjugate-gradient-5a644459137a

我们可以使用共轭梯度法（conjugate gradient）解线性方程或优化二次方程。并且，针对这两种问题，共轭梯度法比比梯度下降的效果更好。

其中矩阵A是对称正定矩阵

在线搜索方法中，我们确定上升的最陡方向，然后选择步长。举个例子，例如在梯度上升方法中， 我们采用的步长大小等于梯度乘以学习率。看下面左图， 根据梯度的轮廓（用点图圈成椭圆的部分），该点的最大梯度方向是向右的。对应当前点最陡的方向，下一点（迭代）的最陡方向可能是向上并略微偏左。如何我们这次梯度有点微微向左，那么不是给第一步（向右梯度）过程的作用取消了吗？

共轭梯度法是一种线性搜索方法，对于每次的移动，他不会撤销（影响）之前完成的部分。在优化二阶方程上，共轭梯度法比梯度下降需要更少的迭代步数。如果x是N维(N个参数），我们可以在最多N步迭代内找到最优值。因为对于每步移动，希望移动方向与之前的所有的移动方向保存共轭的关系。这一点保证了我们不会撤销所做的移动。简单说，若x是4维的向量，则需要最多4次移动就可以到达最优点。

Modified from source

在一个指定的方向做梯度上升

我们在这个方向的最佳点处停下来。

我们找到了一个新方向dj ，它与任何先前的移动方向 di 共轭。

从在数学上来讲，这表示任何新的方向dj 必须与所有 d(i)^TA 共轭，即

其中A是二次方程的系数矩阵。下面是A共轭（A-conjugate）矩阵在二维空间中的例子。

这些A共轭向量相互之间是独立的。因此，N个A共轭向量可以张成一个N维空间。

该共轭梯度算法（CG）的关键是找到α 和 d。

共轭梯度算法

让我先预览一下该算法。我们从一个随机数X(x0)开始猜测问题的解，并计算下一步X1（包括 α 和 d ）。

d 是下一步移动的方向（共轭向量）。 让我们看看它的工作原理。首先，我们定义两项：

e 表示当前猜测点和最佳点之间的误差。

r 测量的是我们当前值与正确值b（Ax = b）的距离。我们可以把r看成将A投影到b所在空间后与b的误差 e（Ax距离b的距离）。

r,e分别定义为：

函数为

对函数求导

下一个点的计算为（其中α是标量，d是方向，是向量）：

为了保证未来的移动方向不会削减之前移动所做的工作，让我尝试保证e 和 d 是相互正交。也就是，采取该步迭代后的残差应该与当前移动方向保持正交的关系。为了保证之后迭代动作不会消减我们刚刚做的工作，因此保持这种正交关系是有道理的。

因此α取决于e，但我们不知道e的实际值是多少。所以使用其他方法代替正交，让我们尝试另一种猜测（估计方法）。也就是新的搜索方向应与前一个方向正交。 A-orthogonal的定义是：

为了满足这些条件，下一个迭代步的点 xi 必须是搜索方向d上的最佳点。

Modified from source

根据A正交要求时，α计算如下：

Modified from source

wikipedia上的证明:

这里不会完整证明。但有兴趣的人可以看看：

en.wikipedia.org/wiki/Derivation_of_the_conjugate_gradient_method

想要继续查看该篇文章相关链接和参考文献？

长按链接点击打开或点击【强化学习基础：共轭梯度】：

https://ai.yanxishe.com/page/TextTranslation/1428

【点击跳转】强化学习基础-对偶梯度上升

AI研习社每日更新精彩内容，观看更多精彩内容：雷锋网雷锋网雷锋网

盘点图像分类的窍门动态编程：二项式序列如何用Keras来构建LSTM模型，并且调参一文教你如何用PyTorch构建 Faster RCNN

等你来译：

如何在神经NLP处理中引用语义结构 你睡着了吗？不如起来给你的睡眠分个类吧！ 高级DQNs：利用深度强化学习玩吃豆人游戏深度强化学习新趋势：谷歌如何把好奇心引入强化学习智能体

人工智能一些术语总结

随着智能时代慢慢的到来，有一些基本概念都不知道真的是要落伍了，作为正在积极学习向上的青年，我想总结一份笔记，此份笔记会记录众多AI领域的术语和概念，当然，学一部分记录一部分，并且可能会夹杂着自己的一些理解，由于能力有限，有问题希望大家多多赐教。当然，由于内容太多，仅仅只是记录了中英名对照，有的加上了简单的解释，没加的后续大家有需求，我会慢慢完善~~。目录暂定以首字母的字典序排序。可以当作目录方便以后查阅~~建议收藏加点赞哈哈哈

------------------------------------------------这里是分割线--------------------------------------------------

A

准确率（accuracy）

分类模型预测准确的比例。

二分类问题中，准确率定义为：accuracy = (true positives +true negatives)/all samples

多分类问题中，准确率定义为：accuracy = correctpredictions/all samples

激活函数（activation function）

一种函数，将前一层所有神经元激活值的加权和 输入到一个非线性函数中，然后作为下一层神经元的输入，例如 ReLU 或 Sigmoid

AdaGrad

一种复杂的梯度下降算法，重新调节每个参数的梯度，高效地给每个参数一个单独的学习率。

AUC（曲线下面积）

一种考虑到所有可能的分类阈值的评估标准。ROC 曲线下面积代表分类器随机预测真正类（Ture Positives）要比假正类（False Positives）概率大的确信度。

Adversarial example（对抗样本）

Adversarial Networks（对抗网络）

Artificial General Intelligence/AGI（通用人工智能）

Attention mechanism（注意力机制）

Autoencoder（自编码器）

Automatic summarization（自动摘要）

Average gradient（平均梯度）

Average-Pooling（平均池化）

B

反向传播（Backpropagation/BP）

神经网络中完成梯度下降的重要算法。首先，在前向传播的过程中计算每个节点的输出值。然后，在反向传播的过程中计算与每个参数对应的误差的偏导数。

基线（Baseline）

被用为对比模型表现参考的简单模型。

批量（Batch）

模型训练中一个迭代（指一次梯度更新）使用的样本集。

批量大小（Batch size）

一个批量中样本的数量。例如，SGD 的批量大小为 1，而 mini-batch 的批量大小通常在 10-1000 之间。

偏置（Bias）

与原点的截距或偏移量。

二元分类器（Binary classification）

一类分类任务，输出两个互斥类别中的一个。比如垃圾邮件检测。

词袋（Bag of words/Bow）

基学习器（Base learner）

基学习算法（Base learning algorithm）

贝叶斯网络（Bayesian network）

基准（Bechmark）

信念网络（Belief network）

二项分布（Binomial distribution）

玻尔兹曼机（Boltzmann machine）

自助采样法／可重复采样／有放回采样（Bootstrap sampling）

广播（Broadcasting）

C

类别（Class）

所有同类属性的目标值作为一个标签。

分类模型（classification）

机器学习模型的一种，将数据分离为两个或多个离散类别。

收敛（convergence）

训练过程达到的某种状态，其中训练损失和验证损失在经过了确定的迭代次数后，在每一次迭代中，改变很小或完全不变。

凸函数（concex function）

一种形状大致呈字母 U 形或碗形的函数。然而，在退化情形中，凸函数的形状就像一条线。

成本（cost）

loss 的同义词。深度学习模型一般都会定义自己的loss函数。

交叉熵（cross-entropy）

多类别分类问题中对 Log 损失函数的推广。交叉熵量化两个概率分布之间的区别。

条件熵（Conditional entropy）

条件随机场（Conditional random field/CRF）

置信度（Confidence）

共轭方向(Conjugate directions)

共轭分布(Conjugate distribution)

共轭梯度(Conjugate gradient)

卷积神经网络（Convolutional neural network/CNN）

余弦相似度（Cosine similarity）

成本函数（Cost Function）

曲线拟合（Curve-fitting）

D

数据集（data set）

样本的集合

深度模型（deep model）

一种包含多个隐藏层的神经网络。深度模型依赖于其可训练的非线性性质。和宽度模型对照（widemodel）。

dropout 正则化（dropoutregularization）

训练神经网络时一种有用的正则化方法。dropout 正则化的过程是在单次梯度计算中删去一层网络中随机选取的固定数量的单元。删去的单元越多，正则化越强。

数据挖掘（Data mining）

决策树/判定树（Decisiontree）

深度神经网络（Deep neural network/DNN）

狄利克雷分布（Dirichlet distribution）

判别模型（Discriminative model）

下采样（Down sampling）

动态规划（Dynamic programming）

E

早期停止法（early stopping）

一种正则化方法，在训练损失完成下降之前停止模型训练过程。当验证数据集（validationdata set）的损失开始上升的时候，即泛化表现变差的时候，就该使用早期停止法了。

嵌入（embeddings）

一类表示为连续值特征的明确的特征。嵌入通常指将高维向量转换到低维空间中。

经验风险最小化（empirical risk minimization，ERM）

选择能使得训练数据的损失函数最小化的模型的过程。和结构风险最小化（structualrisk minimization）对照。

集成（ensemble）

多个模型预测的综合考虑。可以通过以下一种或几种方法创建一个集成方法：

设置不同的初始化；

设置不同的超参量；

设置不同的总体结构。

深度和广度模型是一种集成。

样本（example）

一个数据集的一行内容。一个样本包含了一个或多个特征，也可能是一个标签。参见标注样本（labeledexample）和无标注样本（unlabeled example）。

F

假负类（false negative，FN）

被模型错误的预测为负类的样本。例如，模型推断一封邮件为非垃圾邮件（负类），但实际上这封邮件是垃圾邮件。

假正类（false positive，FP）

被模型错误的预测为正类的样本。例如，模型推断一封邮件为垃圾邮件（正类），但实际上这封邮件是非垃圾邮件。

假正类率（false positive rate，FP rate）

ROC 曲线（ROC curve）中的 x 轴。FP 率的定义是：假正率=假正类数/(假正类数+真负类数)

特征工程（feature engineering）

在训练模型的时候，挖掘对模型效果有利的特征。

前馈神经网络（Feedforward Neural Networks/FNN ）

G

泛化（generalization）

指模型利用新的没见过的数据而不是用于训练的数据作出正确的预测的能力。

广义线性模型（generalized linear model）

最小二乘回归模型的推广/泛化，基于高斯噪声，相对于其它类型的模型（基于其它类型的噪声，比如泊松噪声，或类别噪声）。广义线性模型的例子包括：

logistic 回归

多分类回归

最小二乘回归

梯度（gradient）

所有变量的偏导数的向量。在机器学习中，梯度是模型函数的偏导数向量。梯度指向最陡峭的上升路线。

梯度截断（gradient clipping）

在应用梯度之前先修饰数值，梯度截断有助于确保数值稳定性，防止梯度爆炸出现。

梯度下降（gradient descent）

通过计算模型的相关参量和损失函数的梯度最小化损失函数，值取决于训练数据。梯度下降迭代地调整参量，逐渐靠近权重和偏置的最佳组合，从而最小化损失函数。

图（graph）

在 TensorFlow 中的一种计算过程展示。图中的节点表示操作。节点的连线是有指向性的，表示传递一个操作（一个张量）的结果（作为一个操作数）给另一个操作。使用 TensorBoard 能可视化计算图。

高斯核函数（Gaussian kernel function）

高斯混合模型（Gaussian Mixture Model）

高斯过程（Gaussian Process）

泛化误差（Generalization error）

生成模型（Generative Model）

遗传算法（Genetic Algorithm/GA）

吉布斯采样（Gibbs sampling）

基尼指数（Gini index）

梯度下降（Gradient Descent）

H

启发式（heuristic）

一个问题的实际的和非最优的解，但能从学习经验中获得足够多的进步。

隐藏层（hidden layer）

神经网络中位于输入层（即特征）和输出层（即预测）之间的合成层。一个神经网络包含一个或多个隐藏层。

超参数（hyperparameter）

连续训练模型的过程中可以拧动的「旋钮」。例如，相对于模型自动更新的参数，学习率（learningrate）是一个超参数。和参量对照。

硬间隔（Hardmargin）

隐马尔可夫模型（Hidden Markov Model/HMM）

层次聚类（Hierarchical clustering）

假设检验（Hypothesis test）

I

独立同分布（independently and identicallydistributed，i.i.d）

从不会改变的分布中获取的数据，且获取的每个值不依赖于之前获取的值。i.i.d. 是机器学习的理想情况——一种有用但在现实世界中几乎找不到的数学构建。

推断（inference）

在机器学习中，通常指将训练模型应用到无标注样本来进行预测的过程。在统计学中，推断指在观察到的数据的基础上拟合分布参数的过程。

输入层（input layer）

神经网络的第一层（接收输入数据）。

评分者间一致性（inter-rater agreement）

用来衡量一项任务中人类评分者意见一致的指标。如果意见不一致，则任务说明可能需要改进。有时也叫标注者间信度（inter-annotator agreement）或评分者间信度（inter-raterreliability）。

增量学习（Incremental learning）

独立成分分析（Independent Component Analysis/ICA）

独立子空间分析（Independent subspace analysis）

信息熵（Information entropy）

信息增益（Information gain）

J

JS 散度（Jensen-ShannonDivergence/JSD）

K

Kernel 支持向量机（KernelSupport Vector Machines/KSVM）

一种分类算法，旨在通过将输入数据向量映射到更高维度的空间使正类和负类之间的边际最大化。例如，考虑一个输入数据集包含一百个特征的分类问题。为了使正类和负类之间的间隔最大化，KSVM 从内部将特征映射到百万维度的空间。KSVM 使用的损失函数叫作 hinge 损失。

核方法（Kernel method）

核技巧（Kernel trick）

k 折交叉验证／k 倍交叉验证（K-fold cross validation）

K - 均值聚类（K-MeansClustering）

K近邻算法（K-Nearest NeighboursAlgorithm/KNN）

知识图谱（Knowledge graph）

知识库（Knowledge base）

知识表征（Knowledge Representation）

L

L1 损失函数（L1 loss）

损失函数基于模型对标签的预测值和真实值的差的绝对值而定义。L1 损失函数比起 L2 损失函数对异常值的敏感度更小。

L1 正则化（L1regularization）

一种正则化，按照权重绝对值总和的比例进行惩罚。在依赖稀疏特征的模型中，L1 正则化帮助促使（几乎）不相关的特征的权重趋近于 0，从而从模型中移除这些特征。

L2 损失（L2 loss）

参见平方损失。

L2 正则化（L2regularization）

一种正则化，按照权重平方的总和的比例进行惩罚。L2 正则化帮助促使异常值权重更接近 0 而不趋近于 0。（可与 L1 正则化对照阅读。）L2 正则化通常改善线性模型的泛化效果。

标签（label）

在监督式学习中，样本的「答案」或「结果」。标注数据集中的每个样本包含一或多个特征和一个标签。在垃圾邮件检测数据集中，特征可能包括主题、发出者何邮件本身，而标签可能是「垃圾邮件」或「非垃圾邮件」。

标注样本（labeled example）

包含特征和标签的样本。在监督式训练中，模型从标注样本中进行学习。

学习率（learning rate）

通过梯度下降训练模型时使用的一个标量。每次迭代中，梯度下降算法使学习率乘以梯度，乘积叫作 gradient step。学习率是一个重要的超参数。

最小二乘回归（least squares regression）

通过 L2 损失最小化进行训练的线性回归模型。

线性回归（linear regression）

对输入特征的线性连接输出连续值的一种回归模型。

logistic 回归（logisticregression）

将 sigmoid 函数应用于线性预测，在分类问题中为每个可能的离散标签值生成概率的模型。尽管 logistic 回归常用于二元分类问题，但它也用于多类别分类问题（这种情况下，logistic回归叫作「多类别 logistic 回归」或「多项式 回归」。

对数损失函数（Log Loss）

二元 logistic 回归模型中使用的损失函数。

损失（Loss）

度量模型预测与标签距离的指标，它是度量一个模型有多糟糕的指标。为了确定损失值，模型必须定义损失函数。例如，线性回归模型通常使用均方差作为损失函数，而 logistic 回归模型使用对数损失函数。

隐狄利克雷分布（Latent Dirichlet Allocation/LDA）

潜在语义分析（Latent semantic analysis）

线性判别（Linear Discriminant Analysis/LDA）

长短期记忆（Long-Short Term Memory/LSTM）

M

机器学习（machine learning）

利用输入数据构建（训练）预测模型的项目或系统。该系统使用学习的模型对与训练数据相同分布的新数据进行有用的预测。机器学习还指与这些项目或系统相关的研究领域。

均方误差（Mean Squared Error/MSE）

每个样本的平均平方损失。MSE 可以通过平方损失除以样本数量来计算。

小批量（mini-batch）

在训练或推断的一个迭代中运行的整批样本的一个小的随机选择的子集。小批量的大小通常在10 到 1000 之间。在小批量数据上计算损失比在全部训练数据上计算损失要高效的多。

机器翻译（Machine translation/MT）

马尔可夫链蒙特卡罗方法（Markov Chain Monte Carlo/MCMC）

马尔可夫随机场（Markov Random Field）

多文档摘要（Multi-document summarization）

多层感知器（Multilayer Perceptron/MLP）

多层前馈神经网络（Multi-layer feedforward neuralnetworks）

N

NaN trap

训练过程中，如果模型中的一个数字变成了 NaN，则模型中的很多或所有其他数字最终都变成 NaN。NaN 是「Not aNumber」的缩写。

神经网络（neural network）

该模型从大脑中获取灵感，由多个层组成（其中至少有一个是隐藏层），每个层包含简单的连接单元或神经元，其后是非线性。

神经元（neuron）

神经网络中的节点，通常输入多个值，生成一个输出值。神经元通过将激活函数（非线性转换）应用到输入值的加权和来计算输出值。

归一化（normalization）

将值的实际区间转化为标准区间的过程，标准区间通常是-1 到+1 或 0 到 1。例如，假设某个特征的自然区间是 800 到 6000。通过减法和分割，你可以把那些值标准化到区间-1 到+1。参见缩放。

Numpy

Python 中提供高效数组运算的开源数学库。pandas 基于 numpy 构建。

Naive bayes（朴素贝叶斯）

Naive Bayes Classifier（朴素贝叶斯分类器）

Named entity recognition（命名实体识别）

Natural language generation/NLG（自然语言生成）

Natural language processing（自然语言处理）

Norm（范数）

O

目标（objective）

算法尝试优化的目标函数。

one-hot 编码（独热编码）（one-hotencoding）

一个稀疏向量，其中：一个元素设置为 1，所有其他的元素设置为 0。。

一对多（one-vs.-all）

给出一个有 N 个可能解决方案的分类问题，一对多解决方案包括 N 个独立的二元分类器——每个可能的结果都有一个二元分类器。例如，一个模型将样本分为动物、蔬菜或矿物，则一对多的解决方案将提供以下三种独立的二元分类器：

动物和非动物

蔬菜和非蔬菜

矿物和非矿物

过拟合（overfitting）

创建的模型与训练数据非常匹配，以至于模型无法对新数据进行正确的预测

Oversampling（过采样）

P

pandas

一种基于列的数据分析 API。很多机器学习框架，包括 TensorFlow，支持 pandas 数据结构作为输入。参见 pandas 文档。

参数（parameter）

机器学习系统自行训练的模型的变量。例如，权重是参数，它的值是机器学习系统通过连续的训练迭代逐渐学习到的。注意与超参数的区别。

性能（performance）

在软件工程中的传统含义：软件运行速度有多快／高效？

在机器学习中的含义：模型的准确率如何？即，模型的预测结果有多好？

困惑度（perplexity）

对模型完成任务的程度的一种度量指标。例如，假设你的任务是阅读用户在智能手机上输入的单词的头几个字母，并提供可能的完整单词列表。该任务的困惑度（perplexity，P）是为了列出包含用户实际想输入单词的列表你需要进行的猜测数量。

流程（pipeline）

机器学习算法的基础架构。管道包括收集数据、将数据放入训练数据文件中、训练一或多个模型，以及最终输出模型。

Principal component analysis/PCA（主成分分析）

Precision（查准率／准确率）

Prior knowledge（先验知识）

Q

Quasi Newton method（拟牛顿法）

R

召回率（recall）

回归模型（regression model）

一种输出持续值（通常是浮点数）的模型。而分类模型输出的是离散值。

正则化（regularization）

对模型复杂度的惩罚。正则化帮助防止过拟合。正则化包括不同种类：

L1 正则化

L2 正则化

dropout 正则化

early stopping（这不是正式的正则化方法，但可以高效限制过拟合）

正则化率（regularization rate）

一种标量级，用 lambda 来表示，指正则函数的相对重要性。从下面这个简化的损失公式可以看出正则化率的作用：

minimize(loss function + λ(regularization function))

提高正则化率能够降低过拟合，但可能会使模型准确率降低。

表征（represention）

将数据映射到有用特征的过程。

受试者工作特征曲线（receiver operatingcharacteristic/ROC Curve）

反映在不同的分类阈值上，真正类率和假正类率的比值的曲线。参见 AUC。

Recurrent Neural Network（循环神经网络）

Recursive neural network（递归神经网络）

Reinforcement learning/RL（强化学习）

Re-sampling（重采样法）

Representation learning（表征学习）

Random Forest Algorithm（随机森林算法）

S

缩放（scaling）

特征工程中常用的操作，用于控制特征值区间，使之与数据集中其他特征的区间匹配。例如，假设你想使数据集中所有的浮点特征的区间为 0 到 1。给定一个特征区间是 0 到 500，那么你可以通过将每个值除以 500，缩放特征值区间。还可参见正则化。

scikit-learn

一种流行的开源机器学习平台。网址：www.scikit-learn.org。

序列模型（sequence model）

输入具有序列依赖性的模型。例如，根据之前观看过的视频序列对下一个视频进行预测。

Sigmoid 函数（sigmoid function）

softmax

为多类别分类模型中每个可能的类提供概率的函数。概率加起来的总和是 1.0。例如，softmax 可能检测到某个图像是一只狗的概率为 0.9，是一只猫的概率为 0.08，是一匹马的概率为 0.02。（也叫作 full softmax）。

结构风险最小化（structural risk minimization/SRM）

这种算法平衡两个目标：

构建预测性最强的模型（如最低损失）。

使模型尽量保持简单（如强正则化）。

比如，在训练集上的损失最小化 + 正则化的模型函数就是结构风险最小化算法。更多信息，参见 http://www.svms.org/srm/。可与经验风险最小化对照阅读。

监督式机器学习（supervised machine learning）

利用输入数据及其对应标签来训练模型。监督式机器学习类似学生通过研究问题和对应答案进行学习。在掌握问题和答案之间的映射之后，学生就可以提供同样主题的新问题的答案了。可与非监督机器学习对照阅读。

Similarity measure（相似度度量）

Singular Value Decomposition（奇异值分解）

Soft margin（软间隔）

Soft margin maximization（软间隔最大化）

Support Vector Machine/SVM（支持向量机）

T

张量（tensor）

TensorFlow 项目的主要数据结构。张量是 N 维数据结构（N 的值很大），经常是标量、向量或矩阵。张量可以包括整数、浮点或字符串值。

Transfer learning（迁移学习）

U

无标签样本（unlabeled example）

包含特征但没有标签的样本。无标签样本是推断的输入。在半监督学习和无监督学习的训练过程中，通常使用无标签样本。

无监督机器学习（unsupervised machine learning）

训练一个模型寻找数据集（通常是无标签数据集）中的模式。无监督机器学习最常用于将数据分成几组类似的样本。无监督机器学习的另一个例子是主成分分析（principal componentanalysis，PCA）

W

Word embedding（词嵌入）

Word sense disambiguation（词义消歧）

优化算法总结

本文介绍一下机器学习和深度学习中常用的优化算法和优化器以及一些其他我知道的优化算法,部分算法我也没有搞懂,就先记录下来以后慢慢研究吧.*_*.

1.梯度下降算法(Gradient Descent)

梯度下降法可以参考我另一篇文章 机器学习-线性回归 里的讲解,这里就不在重复叙述.这里需要强调一下,深度学习里常用的SGD,翻译过来是随机梯度下降,但是实质是mini-batch梯度下降(mini-batch-gd),或者说是两者的结合更准确一些.

SGD的优点是,算法简单,计算量小,在函数为凸函数时可以找到全局最优解.所以是最常用的优化算法.缺点是如果函数不是凸函数的话,很容易进入到局部最优解而无法跳出来.同时SGD在选择学习率上也是比较困难的.

2.牛顿法

牛顿法和拟牛顿法都是求解无约束最优化问题的常用方法,其中牛顿法是迭代算法,每一步需要求解目标函数的海森矩阵的逆矩阵,计算比较复杂.

牛顿法在求解方程根的思想:在二维情况下,迭代的寻找某一点x,寻找方法是随机一个初始点x_0,目标函数在该点x_0的切线与x坐标轴的交点就是下一个x点,也就是x_1.不断迭代寻找x.其中切线的斜率为目标函数在点x_0的导数(梯度),切必过点(x_0,f(x_0)).所以迭代的方程式如图1,为了求该方程的极值点,还需要令其导数等于0,也就是又求了一次导数,所以需要用到f(x)的二阶导数.

在最优化的问题中,牛顿法提供了一种求解的办法. 假设任务是优化一个目标函数f, 求函数ff的极大极小问题, 可以转化为求解函数f导数等于0的问题, 这样求可以把优化问题看成方程求解问题(f的导数等于0). 剩下的问题就和牛顿法求解方程根的思想很相似了.

目标函数的泰勒展开式:

化简后:

这样就得到了与图1相似的公式,这里是二维的,在多维空间上,求二阶导数就是求海森矩阵,因为是分母,所以还需要求海森矩阵的逆矩阵.

牛顿法和SGD的区别:

牛顿法是二阶求导,SGD是一阶求导,所以牛顿法要收敛的更快一些.SGD只考虑当前情况下梯度下降最快的方向,而牛顿法不仅考虑当前梯度下降最快,还有考虑下一步下降最快的方向.

牛顿法的优点是二阶求导下降速度快,但是因为是迭代算法,每一步都需要求解海森矩阵的逆矩阵,所以计算复杂.

3.拟牛顿法(没搞懂,待定)

考虑到牛顿法计算海森矩阵比较麻烦,所以它使用正定矩阵来代替海森矩阵的逆矩阵,从而简化了计算过程.

常用的拟牛顿法有DFP算法和BFGS算法.

4.共轭梯度法(Conjugate Gradient)

共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法计算海森矩阵并求逆的缺点.共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一.

5.拉格朗日法

参考SVM里的讲解 机器学习-SVM

6.动量优化法(Momentum)

动量优化法主要是在SGD的基础上,加入了历史的梯度更新信息或者说是加入了速度更新.SGD虽然是很流行的优化算法,但是其学习过程很慢,因为总是以同样的步长沿着梯度下降的方向.所以动量是为了加速学习的方法.

其中第一行的减号部分是计算当前的梯度,第一行是根据梯度更新速度v,而α是新引进的参数,在实践中,α的一般取值为 0.5,0.9 和 0.99.和学习率 一样,α 也会随着时间不断调整.一般初始值是一个较小的值,随后会慢慢变大.

7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)

NAG是在动量优化算法的基础上又进行了改进.根据下图可以看出,Nesterov 动量和标准动量之间的区别体现在梯度计算上, Nesterov 动量中,梯度计算在施加当前速度之后.因此,Nesterov 动量可以解释为往标准动量方法中添加了一个校正因子

8.AdaGrad算法

AdaGrad算法,自适应优化算法的一种,独立地适应所有模型参数的学习率,缩放每个参数反比于其所有梯度历史平均值总和的平方根.具有代价函数最大梯度的参数相应地有个快速下降的学习率,而具有小梯度的参数在学习率上有相对较小的下降.通俗一点的讲,就是根据实际情况更改学习率,比如模型快要收敛的时候,学习率步长就会小一点,防止跳出最优解.

其中g是梯度,第一行的分母是计算累计梯度的平方根, 是为了防止分母为0加上的极小常数项,α是学习率.

Adagrad的主要优点是不需要人为的调节学习率,它可以自动调节.但是依然需要设置一个初始的全局学习率.缺点是随着迭代次数增多,学习率会越来越小,最终会趋近于0.

9.RMSProp算法

RMSProp修改 AdaGrad 以在非凸设定下效果更好,改变梯度积累为指数加权的移动平均.AdaGrad旨在应用于凸问题时快速收敛.

10.AdaDelta算法

11.Adam算法

Adam是Momentum和RMSprop的结合体,也就是带动量的自适应优化算法.

12.Nadam算法

13.模拟退火算法

14.蚁群算法

15.遗传算法

动量是为了加快学习速度,而自适应是为了加快收敛速度,注意学习速度快不一定收敛速度就快,比如步长大学习速度快,但是很容易跳出极值点,在极值点附近波动,很难达到收敛.

未完待定....

参考:

《统计学习方法》 李航 著

《深度学习》 花书