推荐优化算法

‘壹’ 机器学习中有哪些重要的优化算法

梯度下降是非常常用的优化算法。作为机器学习的基础知识，这是一个必须要掌握的算法。借助本文，让我们来一起详细了解一下这个算法。

前言

本文的代码可以到我的Github上获取：

https://github.com/paulQuei/gradient_descent

本文的算法示例通过python语言实现，在实现中使用到了numpy和matplotlib。如果你不熟悉这两个工具，请自行在网上搜索教程。

关于优化

大多数学习算法都涉及某种形式的优化。优化指的是改变x以最小化或者最大化某个函数的任务。

我们通常以最小化指代大多数最优化问题。最大化可经由最小化来实现。

我们把要最小化或最大化的函数成为目标函数（objective function）或准则（criterion）。

我们通常使用一个上标*表示最小化或最大化函数的x值，记做这样：

[x^* = arg; min; f(x)]

优化本身是一个非常大的话题。如果有兴趣，可以通过《数值优化》和《运筹学》的书籍进行学习。

模型与假设函数

所有的模型都是错误的，但其中有些是有用的。– George Edward Pelham Box

模型是我们对要分析的数据的一种假设，它是为解决某个具体问题从老洞数据中学习到的，因此它是机器学习最核心的概念。

针对一个问题，通常有大量的模型可以选择。

本文不会深入讨论这方面的内容，关于各种模型请参阅机器学习的相关书籍。本文仅以最简单的线性模型为基础来讨论梯度下降算法。

这里我们先介绍一下在监督学习（supervised learning）中常见的三个符号：

• m，描述训练样本的数量

• x，描述输入变量或特征

• y，描述输出变量或者叫目标值

• 请注意，一个样本笑或可能有很多的特征，因此x和y通常是一个向量。不过在刚开始学习的时候，为了便于理解，你可以暂时理解为这就是一个具体的数值。

训练集会包含很多的样本，我们用 表示其中第i个样本。

x是数据样本的特征，y是其目标值。例如，在预测房价的模型中，x是房子的各种信息，例如：面积，楼层，位置等等，y是房子的价格。在图像识别的任务中，x是图形的所有像素点数据，y是图像中包含的目标对象。

我们是希望寻找一个函数，将x映射到y，这个函数要足够的好，以至于能够预测对应的y。由于历史原因，这个函数叫做假设函数（hypothesis function）。

学习的过程如下图所示。即：首先根据已有的数据（称之为训练集）训练我们的算法模型，然后根据模型的假设函数来进行新数据的预测。

线性模型（linear model）正如其名称那样：是希望通过一个直线的形式来描述模式。线性模型的假设函数如下所示：

[h_{ heta}(x) = heta_{0} + heta_{1} * x]

这个公式对于大家来说应该都是非常简单的。如果把它绘制出来，其实就是一条直线。

下图是一个具体的例子，即： 的图形：

在实际的机器学习工程中碰含伍，你会拥有大量的数据。这些数据会来自于某个数据源。它们存储在csv文件中，或者以其他的形式打包。

但是本文作为演示使用，我们通过一些简单的代码自动生成了需要的数据。为了便于计算，演示的数据量也很小。

import numpy as np

max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2

def get_data:
x = np.linspace(1, max_x, data_size)
noise = np.random.normal(0, 0.2, len(x))
y = theta_0 + theta_1 * x + noise
return x, y


这段代码很简单，我们生成了x范围是 [1, 10] 整数的10条数据。对应的y是以线性模型的形式计算得到，其函数是：。现实中的数据常常受到各种因素的干扰，所以对于y我们故意加上了一些高斯噪声。因此最终的y值为比原先会有轻微的偏离。

最后我们的数据如下所示：

x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [6.66, 9.11, 11.08, 12.67, 15.12, 16.76, 18.75, 21.35, 22.77, 24.56]


我们可以把这10条数据绘制出来这样就有一个直观的了解了，如下图所示：

虽然演示用的数据是我们通过公式计算得到的。但在实际的工程中，模型的参数是需要我们通过数据学习到的。所以下文我们假设我们不知道这里线性模式的两个参数是什么，而是通过算法的形式求得。

最后再跟已知的参数进行对比以验证我们的算法是否正确。

有了上面的数据，我们可以尝试画一条直线来描述我们的模型。

例如，像下面这样画一条水平的直线：

很显然，这条水平线离数据太远了，非常的不匹配。

那我们可以再画一条斜线。

我们初次画的斜线可能也不贴切，它可能像下面这样：

最后我们通过不断尝试，找到了最终最合适的那条，如下所示：

梯度下降算法的计算过程，就和这种本能式的试探是类似的，它就是不停的迭代，一步步的接近最终的结果。


代价函数

上面我们尝试了几次通过一条直线来拟合（fitting）已有的数据。

二维平面上的一条直线可以通过两个参数唯一的确定，两个参数的确定也即模型的确定。那如何描述模型与数据的拟合程度呢？答案就是代价函数。

代价函数（cost function）描述了学习到的模型与实际结果的偏差程度。以上面的三幅图为例，最后一幅图中的红线相比第一条水平的绿线，其偏离程度（代价）应该是更小的。

很显然，我们希望我们的假设函数与数据尽可能的贴近，也就是说：希望代价函数的结果尽可能的小。这就涉及到结果的优化，而梯度下降就是寻找最小值的方法之一。

• 代价函数也叫损失函数。

对于每一个样本，假设函数会依据计算出一个估算值，我们常常用来表示。即 。

很自然的，我们会想到，通过下面这个公式来描述我们的模型与实际值的偏差程度：

[(h_ heta(x^i) - y^i)^2 = (widehat{y}^{i} - y^i)^2 = ( heta_{0} + heta_{1} * x^{i} - y^{i})^2]

请注意， 是实际数据的值， 是我们的模型的估算值。前者对应了上图中的离散点的y坐标，后者对应了离散点在直线上投影点的y坐标。

每一条数据都会存在一个偏差值，而代价函数就是对所有样本的偏差求平均值，其计算公式如下所示：

[L( heta) = frac {1}{m} sum_{i=1}^{m}(h_ heta(x^i) - y^i)^2 = frac {1}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i})^2]

当损失函数的结果越小，则意味着通过我们的假设函数估算出的结果与真实值越接近。这也就是为什么我们要最小化损失函数的原因。

• 不同的模型可能会用不同的损失函数。例如，logistic回归的假设函数是这样的：。其代价函数是这样的：

借助上面这个公式，我们可以写一个函数来实现代价函数：

def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = np.power(t0 + t1 * x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)


这个函数的代码应该不用多做解释，它就是根据上面的完成计算。

我们可以尝试选取不同的 和 组合来计算代价函数的值，然后将结果绘制出来：

import numpy as np
import matplotlib.pyplot as plt

from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D

theta_0 = 5
theta_1 = 2

def draw_cost(x, y):
fig = plt.figure(figsize=(10, 8))
ax = fig.gca(projection='3d')
scatter_count = 100
radius = 1
t0_range = np.linspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = np.linspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = np.zeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = np.meshgrid(t0_range, t1_range)

ax.set_xlabel('theta_0')
ax.set_ylabel('theta_1')
ax.plot_surface(t0, t1, cost, cmap=cm.hsv)


在这段代码中，我们对 和 各自指定了一个范围进行100次的采样，然后以不同的 组合对来计算代价函数的值。

如果我们将所有点的代价函数值绘制出来，其结果如下图所示：

从这个图形中我们可以看出，当 越接近 [5, 2]时其结果（偏差）越小。相反，离得越远，结果越大。


直观解释

从上面这幅图中我们可以看出，代价函数在不同的位置结果大小不同。

从三维的角度来看，这就和地面的高低起伏一样。最高的地方就好像是山顶。

而我们的目标就是：从任意一点作为起点，能够快速寻找到一条路径并以此到达图形最低点（代价值最小）的位置。

而梯度下降的算法过程就和我们从山顶想要快速下山的做法是一样的。

在生活中，我们很自然会想到沿着最陡峭的路往下行是下山速度最快的。如下面这幅图所示：

针对这幅图，细心的读者可能很快就会有很多的疑问，例如：

• 对于一个函数，怎么确定下行的方向？

• 每一步该往前走多远？

• 有没有可能停留在半山腰的平台上？

这些问题也就是本文接下来要讨论的内容。


算法描述

梯度下降算法最开始的一点就是需要确定下降的方向，即：梯度。

我们常常用 来表示梯度。

对于一个二维空间的曲线来说，梯度就是其切线的方向。如下图所示：

而对于更高维空间的函数来说，梯度由所有变量的偏导数决定。

其表达式如下所示：

[ abla f({ heta}) = ( frac{partial f({ heta})}{partial heta_1} , frac{partial f({ heta})}{partial heta_2} , ... , frac{partial f({ heta})}{partial heta_n} )]

在机器学习中，我们主要是用梯度下降算法来最小化代价函数，记做：

[ heta ^* = arg min L( heta)]

其中，L是代价函数，是参数。

梯度下降算法的主体逻辑很简单，就是沿着梯度的方向一直下降，直到参数收敛为止。

记做：

[ heta ^{k + 1}_i = heta^{k}_i - lambda abla f( heta^{k})]

• 这里的下标i表示第i个参数。 上标k指的是第k步的计算结果，而非k次方。在能够理解的基础上，下文的公式中将省略上标k。

这里有几点需要说明：

• 收敛是指函数的变化率很小。具体选择多少合适需要根据具体的项目来确定。在演示项目中我们可以选择0.01或者0.001这样的值。不同的值将影响算法的迭代次数，因为在梯度下降的最后，我们会越来越接近平坦的地方，这个时候函数的变化率也越来越小。如果选择一个很小的值，将可能导致算法迭代次数暴增。

• 公式中的 称作步长，也称作学习率（learning rate）。它决定了每一步往前走多远，关于这个值我们会在下文中详细讲解。你可以暂时人为它是一个类似0.01或0.001的固定值。

• 在具体的项目，我们不会让算法无休止的运行下去，所以通常会设置一个迭代次数的最大上限。


线性回归的梯度下降

有了上面的知识，我们可以回到线性模型代价函数的梯度下降算法实现了。

首先，根据代价函数我们可以得到梯度向量如下：

[ abla f({ heta}) = (frac{partial L( heta)}{ partial heta_{0}}, frac{ partial L( heta)}{ partial heta_{1}}) = (frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) , frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i})]

接着，将每个偏导数带入迭代的公式中，得到：

[ heta_{0} := heta_{0} - lambda frac{partial L( heta_{0})}{ partial heta_{0}} = heta_{0} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) heta_{1} := heta_{1} - lambda frac{partial L( heta_{1})}{ partial heta_{1}} = heta_{1} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i}]

由此就可以通过代码实现我们的梯度下降算法了，算法逻辑并不复杂：

learning_rate = 0.01

def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0.001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
t0_ = t0 - 2 * learning_rate * sum1 / len(x)
t1_ = t1 - 2 * learning_rate * sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1


这段代码说明如下：

• 我们随机选择了 都为10作为起点

• 设置最多迭代1000次

• 收敛的范围设为0.001

• 学习步长设为0.01

如果我们将算法迭代过程中求得的线性模式绘制出来，可以得到下面这幅动态图：

最后算法得到的结果如下：


Times: 657, gradient: [5.196562662718697, 1.952931052920264]
Times: 658, gradient: [5.195558390180733, 1.9530753071808193]
Times: 659, gradient: [5.194558335124868, 1.9532189556399233]
Times: 660, gradient: [5.193562479839619, 1.9533620008416623]
Gradient descent finish


从输出中可以看出，算法迭代了660次就收敛了。这时的结果[5.193562479839619, 1.9533620008416623]，这已经比较接近目标值 [5, 2]了。如果需要更高的精度，可以将delta的值调的更小，当然，此时会需要更多的迭代次数。


高维扩展

虽然我们举的例子是二维的，但是对于更高维的情况也是类似的。同样是根据迭代的公式进行运算即可：

[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=1}^{m}(h_ heta(x^{k})-y^k)x_i^k]

这里的下标i表示第i个参数，上标k表示第k个数据。


梯度下降家族BGD

在上面的内容中我们看到，算法的每一次迭代都需要把所有样本进行遍历处理。这种做法称为之Batch Gradient Descent，简称BGD。作为演示示例只有10条数据，这是没有问题的。

但在实际的项目中，数据集的数量可能是几百万几千万条，这时候每一步迭代的计算量就会非常的大了。

于是就有了下面两个变种。


SGD

Stochastic Gradient Descent，简称SGD，这种算法是每次从样本集中仅仅选择一个样本来进行计算。很显然，这样做算法在每一步的计算量一下就少了很多。

其算法公式如下：

[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - lambda(h_ heta(x^k)-y^k)x_i^k]

当然，减少算法计算量也是有代价的，那就是：算法结果会强依赖于随机取到的数据情况，这可能会导致算法的最终结果不太令人满意。


MBGD

以上两种做法其实是两个极端，一个是每次用到了所有数据，另一个是每次只用一个数据。

我们自然就会想到两者取其中的方法：每次选择一小部分数据进行迭代。这样既避免了数据集过大导致每次迭代计算量过大的问题，也避免了单个数据对算法的影响。

这种算法称之为Mini-batch Gradient Descent，简称MBGD。

其算法公式如下：

[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=a}^{a + b}(h_ heta(x^k)-y^k)x_i^k]

当然，我们可以认为SGD是Mini-batch为1的特例。

针对上面提到的算法变种，该如何选择呢？

下面是Andrew Ng给出的建议：

• 如果样本数量较小（例如小于等于2000），选择BGD即可。

• 如果样本数量很大，选择 来进行MBGD，例如：64，128，256，512。

下表是 Optimization for Deep Learning 中对三种算法的对比

方法准确性更新速度内存占用在线学习BGD好慢高否SGD好（with annealing）快低是MBGD好中等中等是
算法优化

式7是算法的基本形式，在这个基础上有很多人进行了更多的研究。接下来我们介绍几种梯度下降算法的优化方法。


Momentum

Momentum是动量的意思。这个算法的思想就是借助了动力学的模型：每次算法的迭代会使用到上一次的速度作为依据。

算法的公式如下：

[v^t = gamma v^{t - 1} + lambda abla f( heta) heta = heta - v_t]

对比式7可以看出，这个算法的主要区别就是引入了，并且，每个时刻的受前一个时刻的影响。

从形式上看，动量算法引入了变量 v 充当速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称动量来自物理类比，根据牛顿运动定律，负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中，我们假设是单位质量，因此速度向量 v 也可以看作是粒子的动量。

对于可以取值0，而是一个常量，设为0.9是一个比较好的选择。

下图是momentum算法的效果对比：

对原来的算法稍加修改就可以增加动量效果：

def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0.001
v0 = 0
v1 = 0
gamma = 0.9
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
v0 = gamma * v0 + 2 * learning_rate * sum1 / len(x)
v1 = gamma * v1 + 2 * learning_rate * sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1


以下是该算法的输出：


Times: 125, gradient: [4.955453758569991, 2.000005017897775]
Times: 126, gradient: [4.955309381126545, 1.9956928964532015]
Times: 127, gradient: [4.9542964317327005, 1.9855674828684156]
Times: 128, gradient: [4.9536358220657, 1.9781180992510465]
Times: 129, gradient: [4.95412496254411, 1.9788858350530971]
Gradient descent finish


从结果可以看出，改进的算法只用了129次迭代就收敛了。速度比原来660次快了很多。

同样的，我们可以把算法计算的过程做成动态图：

对比原始的算法过程可以看出，改进算法最大的区别是：在寻找目标值时会在最终结果上下跳动，但是越往后跳动的幅度越小，这也就是动量所产生的效果。


Learning Rate 优化

至此，你可能还是好奇该如何设定学习率的值。

事实上，这个值的选取需要一定的经验或者反复尝试才能确定。

• 《深度学习》一书中是这样描述的：“与其说是科学，这更像是一门艺术，我们应该谨慎地参考关于这个问题的大部分指导。”。

关键在于，这个值的选取不能过大也不能过小。

如果这个值过小，会导致每一次迭代的步长很小，其结果就是算法需要迭代非常多的次数。

那么，如果这个值过大会怎么样呢？其结果就是：算法可能在结果的周围来回震荡，却落不到目标的点上。下面这幅图描述了这个现象：

事实上，学习率的取值未必一定要是一个常数，关于这个值的设定有很多的研究。

下面是比较常见的一些改进算法。


AdaGrad

AdaGrad是Adaptive Gradient的简写，该算法会为每个参数设定不同的学习率。它使用历史梯度的平方和作为基础来进行计算。

其算法公式如下：

[ heta_i = heta_i - frac{lambda}{sqrt{G_t + epsilon}} abla f( heta)]

对比式7，这里的改动就在于分号下面的根号。

根号中有两个符号，第二个符号比较好理解，它就是为了避免除0而人为引入的一个很小的常数，例如可以设为：0.001。

第一个符号的表达式展开如下：

[G_t = sum_{i = 1}^{t} abla f( heta){i} abla f( heta){i}^{T}]

这个值其实是历史中每次梯度的平方的累加和。

AdaGrad算法能够在训练中自动的对learning rate进行调整，对于出现频率较低参数采用较大的学习率；相反，对于出现频率较高的参数采用较小的学习率。因此，Adagrad非常适合处理稀疏数据。

但该算法的缺点是它可能导致学习率非常小以至于算法收敛非常的慢。

关于这个算法的直观解释可以看李宏毅教授的视频课程：ML Lecture 3-1: Gradient Descent。


RMSProp

RMS是Root Mean Square的简写。RMSProp是AI教父Geoff Hinton提出的一种自适应学习率方法。AdaGrad会累加之前所有的梯度平方，而RMSProp仅仅是计算对应的平均值，因此可缓解Adagrad算法学习率下降较快的问题。

该算法的公式如下：

[E[ abla f( heta_{i})^2]^{t} = gamma E[ abla f( heta_{i})^2]^{t - 1} + (1-gamma)( abla f( heta_{i})^{t})^{2} heta_i = heta_i - frac{lambda}{sqrt{E[g^2]^{t+1} + epsilon}} abla f( heta_{i})]

类似的，是为了避免除0而引入。 是衰退参数，通常设为0.9。

这里的 是t时刻梯度平方的平均值。


Adam

Adam是Adaptive Moment Estimation的简写。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。

Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。

该算法公式如下：

[m^{t} = eta_{1} m^{t-1} + (1-eta_{1}) abla f( heta) v^{t} = eta_{2} v^{t-1} + (1-eta_{2}) abla f( heta)^2 widehat{m}^{t} = frac{m^{t}}{1 - eta^{t}_1} widehat{v}^{t} = frac{v^{t}}{1 - eta^{t}_2} heta = heta - frac{lambda}{sqrt{widehat{v}^{t}} + epsilon}widehat{m}^{t}]

，分别是对梯度的一阶矩估计和二阶矩估计。， 是对，的校正，这样可以近似为对期望的无偏估计。

Adam算法的提出者建议 默认值为0.9，默认值为0.999，默认值为 。

在实际应用中 ，Adam较为常用，它可以比较快地得到一个预估结果。


优化小结

这里我们列举了几种优化算法。它们很难说哪种最好，不同的算法适合于不同的场景。在实际的工程中，可能需要逐个尝试一下才能确定选择哪一个，这个过程也是目前现阶段AI项目要经历的工序之一。

实际上，该方面的研究远不止于此，如果有兴趣，可以继续阅读 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 这篇论文或者 Optimization for Deep Learning 这个Slides进行更多的研究。

由于篇幅所限，这里不再继续展开了。


算法限制

梯度下降算法存在一定的限制。首先，它要求函数必须是可微分的，对于不可微的函数，无法使用这种方法。

除此之外，在某些情况下，使用梯度下降算法在接近极值点的时候可能收敛速度很慢，或者产生Z字形的震荡。这一点需要通过调整学习率来回避。

另外，梯度下降还会遇到下面两类问题。


局部最小值

局部最小值（Local Minima）指的是，我们找到的最小值仅仅是一个区域内的最小值，而并非全局的。由于算法的起点是随意取的，以下面这个图形为例，我们很容易落到局部最小值的点里面。

这就是好像你从上顶往下走，你第一次走到的平台未必是山脚，它有可能只是半山腰的一个平台的而已。

算法的起点决定了算法收敛的速度以及是否会落到局部最小值上。

坏消息是，目前似乎没有特别好的方法来确定选取那个点作为起点是比较好的，这就有一点看运气的成分了。多次尝试不同的随机点或许是一个比较好的方法，这也就是为什么做算法的优化这项工作是特别消耗时间的了。

但好消息是：

• 对于凸函数或者凹函数来说，不存在局部极值的问题。其局部极值一定是全局极值。

• 最近的一些研究表明，某些局部极值并没有想象中的那么糟糕，它们已经非常的接近全局极值所带来的结果了。


鞍点

除了Local Minima，在梯度下降的过程中，还有可能遇到另外一种情况，即：鞍点（Saddle Point）。鞍点指的是我们找到点某个点确实是梯度为0，但它却不是函数的极值，它的周围既有比它小的值，也有比它大的值。这就好像马鞍一样。

如下图所示：

多类随机函数表现出以下性质：在低维空间中，局部极值很普遍。但在高维空间中，局部极值比较少见，而鞍点则很常见。

不过对于鞍点，可以通过数学方法Hessian矩阵来确定。关于这点，这里就不再展开了，有兴趣的读者可以以这里提供的几个链接继续探索。


参考资料与推荐读物

• Wikipeida: Gradient descent

• Sebastian Ruder: An overview of gradient descent optimization algorithms

• 吴恩达：机器学习

• 吴恩达：深度学习

• Peter Flach：机器学习

• 李宏毅 - ML Lecture 3-1: Gradient Descent

• PDF: 李宏毅 - Gradient Descent

• Intro to optimization in deep learning: Gradient Descent

• Intro to optimization in deep learning: Momentum, RMSProp and Adam

• Stochastic Gradient Descent – Mini-batch and more

• 刘建平Pinard - 梯度下降（Gradient Descent）小结

• 多元函数的偏导数、方向导数、梯度以及微分之间的关系思考

• [Machine Learning] 梯度下降法的三种形式BGD、SGD以及MBGD

• 作者：阿Paul https://paul.pub/gradient-descent/

‘贰’ 优化算法笔记（一）优化算法的介绍

（以下描述，均不是学术用语，仅供大家快乐的阅读）

        我们常见常用的算法有排序算法,字符串遍历算法,寻路算法等。这些算法都是为了解决特定的问题而被提出。

        算法本质是一种按照固定步骤执行的过程。

        优化算法也是这样一种过程，是一种根据概率按照固定步骤寻求问题的最优解的过程。与常见的排序算法、寻路算法不同的是，优化算法不具备等幂性，是一种 概率算法 。算法不断的 迭代 执行同一步骤直到结束，其流程如下图。

        等幂性即 对于同样的输入，输出是相同的 。

        比如图1，对于给定的鱼和给定的熊掌，我们在相同的条件下一定可以知道它们谁更重，当然，相同的条件是指鱼和熊掌处于相同的重力作用下，且不用考虑水分流失的影响。在这些给定的条件下，我们（无论是谁）都将得出相同的结论，鱼更重或者熊掌更重。我们可以认为，秤是一个等幂性的算法（工具）。

        现在把问题变一变，问鱼与熊掌你更爱哪个，那么现在，这个问题，每个人的答案可能不会一样，鱼与熊掌各有所爱。说明喜爱这个算法不是一个等幂性算法。当然你可能会问，哪个更重，和更喜欢哪个这两个问题一个是客观问题，一个是主观问题，主观问题没有确切的答案的。当我们处理主观问题时，也会将其转换成客观问题，比如给喜欢鱼和喜欢熊掌的程度打个分，再去寻求答案，毕竟计算机没有感情，只认0和1（量子计算机我不认识你）。

        说完了等幂性，再来说什么是概率算法。简单来说就是看脸、看人品、看运气的算法。

        有一场考试，考试的内容全部取自课本，同时老师根据自己的经验给同学们划了重点，但是因为试卷并不是该老师所出，也会有考试内容不在重点之内，老师估计试卷中至少80%内容都在重点中。学霸和学渣参加了考试，学霸为了考满分所以无视重点，学渣为了pass，因此只看了重点。这样做的结果一定是score(学霸)>=score(学渣)。

        当重点跟上图一样的时候，所有的内容都是重点的时候，学霸和学渣的学习策略变成了相同的策略，则score(学霸)=score(学渣)。但同时，学渣也要付出跟学霸相同的努力去学习这些内容，学渣心里苦啊。

        当课本如下图时

        学霸？学霸人呢，哪去了快来学习啊，不是说学习一时爽，一直学习一直爽吗，快来啊，还等什么。

        这时，如果重点内容远少于书本内容时，学渣的学习策略有了优势——花费的时间和精力较少。但是同时，学渣的分数也是一个未知数，可能得到80分也可能拿到100分，分数完全取决于重点内容与题目的契合度，契合度越高，分数越高。对学渣来说，自己具体能考多少分无法由自己决定，但是好在能够知道大概的分数范围。

        学霸的学习策略是一种遍历性算法，他会遍历、通读全部内容，以保证满分。

        学渣的学习策略则是一种概率算法，他只会遍历、学习重点内容，但至于这些重点是不是真重点他也不知道。

        与遍历算法相比，概率算法的结果具有不确定性，可能很好，也可能很差，但是会消耗更少的资源，比如时间（人生），空间（记忆）。概率算法的最大优点就是 花费较少的代价来获取最高的收益 ，在现实中体现于节省时间，使用很少的时间得到一个不与最优解相差较多的结果。

        “庄子：吾生也有涯，而知也无涯；以有涯随无涯，殆矣。”的意思是：人生是有限的，但知识是无限的（没有边界的），用有限的人生追求无限的知识，是必然失败的。

        生活中概率算法（思想）的应用其实比较广泛，只是我们很少去注意罢了。关于概率算法还衍生出了一些有趣的理论，比如墨菲定律和幸存者偏差，此处不再详述。

        上面说到，优化算法就是不停的执行同样的策略、步骤直到结束。为什么要这样呢？因为优化算法是一种概率算法，执行一次操作就得到最优结果几乎是不可能的，重复多次取得最优的概率也会增大。

        栗子又来了，要从1-10这10个数中取出一个大于9的数，只取1次，达到要求的概率为10%，取2次，达到要求的概率为19%。

        可以看出取到第10次时，达到要求的概率几乎65%，取到100次时，达到要求的概率能接近100%。优化算法就是这样简单粗暴的来求解问题的吗？非也，这并不是一个恰当的例子，因为每次取数的操作之间是相互独立的，第2次取数的结果不受第1次取数结果的影响，假设前99次都没达到要求，那么再取一次达到要求的概率跟取一次达到要求的概率相同。

        优化算法中，后一次的计算会依赖前一次的结果，以保证后一次的结果不会差于前一次的结果。这就不得不谈到马尔可夫链了。

        由铁组成的链叫做铁链，同理可得，马尔可夫链就是马尔可夫组成的链。

        言归正传, 马尔可夫链（Markov Chain, MC） ,描述的是 状态转移的过程中,当前状态转移的概率只取决于上一步的状态,与其他步的状态无关 。简单来说就是当前的结果只受上一步的结果的影响。每当我看到马尔可夫链时，我都会陷入沉思，生活中、或者历史中有太多太多与马尔可夫链相似的东西。西欧封建等级制度中“附庸的附庸不是我的附庸”与“昨天的努力决定今天的生活，今天的努力决定明天的生活”，你的下一份工作的工资大多由你当前的工资决定，这些都与马尔可夫链有异曲同工之处。

        还是从1-10这10个数中取出一个大于9的数的这个例子。基于马尔可夫链的概率算法在取数时需要使当前取的数不小于上一次取的数。比如上次取到了3，那么下次只能在3-10这几个数中取，这样一来，达到目标的概率应该会显着提升。还是用数据说话。

        取1次达到要求的概率仍然是

        取2次内达到要求的概率为

        取3次内达到要求的概率为

        取4次内……太麻烦了算了不算了

        可以看出基于马尔可夫链来取数时，3次内能达到要求的概率与不用马尔可夫链时取6次的概率相当。说明基于马尔可夫链的概率算法求解效率明显高于随机概率算法。那为什么不将所有的算法都基于马尔可夫链呢？原因一，其实现方式不是那么简单，例子中我们规定了取数的规则是复合马尔可夫链的，而在其他问题中我们需要建立适当的复合马尔科夫链的模型才能使用。原因二，并不是所有的问题都符合马尔科夫链条件，比如原子内电子出现的位置，女朋友为什么会生（lou）气，彩票号码的规律等，建立模型必须与问题有相似之处才能较好的解决问题。

        介绍完了优化算法，再来讨论讨论优化算法的使用场景。

        前面说了优化算法是一种概率算法，无法保证一定能得到最优解，故如果要求结果必须是确定、稳定的值，则无法使用优化算法求解。

        例1，求城市a与城市b间的最短路线。如果结果用来修建高速、高铁，那么其结果必定是唯一确定的值，因为修路寸土寸金，必须选取最优解使花费最少。但如果结果是用来赶路，那么即使没有选到最优的路线，我们可能也不会有太大的损失。

        例2，求城市a与城市b间的最短路线，即使有两条路径，路径1和路径2，它们从a到b的距离相同，我们也可以得出这两条路径均为满足条件的解。现在将问题改一下，求城市a到城市b耗时最少的线路。现在我们无法马上得出确切的答案，因为最短的线路可能并不是最快的路线，还需要考虑到天气，交通路况等因素，该问题的结果是一个动态的结果，不同的时间不同的天气我们很可能得出不同的结果。

        现实生产、生活中，也有不少的场景使用的优化算法。例如我们的使用的美图软件，停车场车牌识别，人脸识别等，其底层参数可能使用了优化算法来加速参数计算，其参数的细微差别对结果的影响不太大，需要较快的得出误差范围内的参数即可；电商的推荐系统等也使用了优化算法来加速参数的训练和收敛，我们会发现每次刷新时，推给我们的商品都有几个会发生变化，而且随着我们对商品的浏览，系统推给我们的商品也会发生变化，其结果是动态变化的；打车软件的订单系统，会根据司机和客人的位置，区域等来派发司机给客人，不同的区域，不同的路况，派发的司机也是动态变化的。

        综上我们可以大致总结一下推荐、不推荐使用优化算法的场景的特点。

        前面说过，优化算法处理的问题都是客观的问题，如果遇到主观的问题，比如“我孰与城北徐公美”，我们需要将这个问题进行量化而转换成客观的问题，如身高——“修八尺有余”，“外貌——形貌昳丽”，自信度——“明日徐公来，孰视之，自以为不如；窥镜而自视，又弗如远甚”，转化成客观问题后我们可以得到各个解的分数，通过比较分数，我们就能知道如何取舍如何优化。这个转化过程叫做问题的建模过程，建立的问题模型实际上是一个函数，这个函数对优化算法来说是一个黑盒函数，即不需要知道其内部实现只需要给出输入，得到输出。

        在优化算法中这个黑盒函数叫做 适应度函数 ， 优化算法的求解过程就是寻找适应度函数最优解的过程 ，使用优化算法时我们最大的挑战就是如何将抽象的问题建立成具体的模型，一旦合适的模型建立完成，我们就可以愉快的使用优化算法来求解问题啦。（“合适”二字谈何容易）

        优化算法的大致介绍到此结束，后面我们会依次介绍常见、经典的优化算法，并探究其参数对算法性能的影响。

——2019.06.20

[目录]

[下一篇 优化算法笔记（二）优化算法的分类]

‘叁’ 如何做好“推荐算法”有哪些常见的错误需要避免

在这里share一下。
1、推荐算法的构成
一套标准的推荐算法，需要四个组成部分
第一：数据源，行为基础数据的筛选；通常，推荐算法来源于用户行为的采集，简单说就是行为数据越丰富，样本覆盖率越全面，结果越准确；如果采样有偏差，那么结果就会有偏差。
举例1：游戏推荐算法，我们之前限于采样技术水平和处理能力，用的是登陆用户玩过的游戏历史，那么推荐结果就会偏重于需要登陆的游戏。而随着技术提升用全部用户玩过的游戏历史，就更全面了。
举例2：在搜索引擎中，对关键词做推荐，有两种方案，一种是基于广告主的竞价记录；另一种是基于网民的搜索行为；前一种专业性更强，噪音小；后一种覆盖面广，噪音大，各有利弊，根据业务诉求选择。
推荐算法，通常来源于用户的行为记录，比如关键词推荐用用户搜索历史，电商推荐用用户购物历史，游戏推荐用玩家玩游戏的历史，然后基于算法给出相关度，再排序展示 ；但这不绝对，也有并非基于用户行为记录的推荐原理，比如基于用户身份特征或其他地区、网络环境等特征，限于篇幅和常见的业务诉求，这里就不展开说明了。
行为基础数据必要时要做一些去除噪音的工作，比如你通过日志分析玩家游戏历史，或用户购物历史，至少知道把各搜索引擎和工具的抓取痕迹过滤出去，否则结果是很难看的。
算法很多种，网上可以搜到很多，就算搜不到，或者搜到了看不懂，自己编也不难的（我就编过，效果自以为还不错，但是的确不如人家专业的算法效果好，所以适合练手，不适合出去吹牛）
不同算法差异还是蛮大的，需要理解一下业务诉求和目标特征来选择。这个我真心不是高手，我们同事讲的算法我都没能理解，就不多说了。微博上的“张栋_机器学习"和"梁斌penny"都是算法高手，大家可以多关心他们的微博。
第三：参数！
绝对不要认为用到了好的算法就可以了！算法往往会基于一些参数来调优，这些参数哪里来？很不好意思的告诉你，大部分是拍脑袋出来的。但是你拍脑袋出来后，要知道去分析结果，去看哪里对，哪里错，哪里可以改，好的算法可以自动调优，机器学习，不断自动调整参数达到最优，但是通常可能需要你不断手工去看，去看badcase，想想是什么参数因素导致的，改一下是否变好？是否引入新的bad case？
第四：校验！
校验一种是人工做盲测，A算法，B算法的结果混淆，选案例集，看哪个效果好；或A参数、B参数混淆，同理测试。通过盲测选择认为更合理的算法、更适宜的参数.
以上是个人认为，做好推荐算法的步骤
下面说一下常见问题
1、以为有了算法就ok了，不对参数优化，不做后续的校验和数据跟踪，效果不好就说算法有问题，这种基本属于工作态度的问题了。
2、对样本数据的筛选有问题，或缺乏必要的噪音筛查，导致结果噪音多。比如你有个推广位天天摆着，导致用户点击多，然后导致后台行为数据里它和谁的关联都高，然后不管用户到哪里都推荐这个玩意，这就是没有足够筛查。
3、热度影响
我说一下最简单的推荐算法
同时选择了A和B的人数作为A与B的关联度。
这个实现最简单，也最容易理解，但是很容易受热度影响
我曾经注意过某个热门图书电商网站，推荐的关联书籍一水的热门书籍，就是这个问题。
这些是非常简单但是又非常容易出现的，关联误区。
4、过于求全
现在也遇到一些朋友，一提到推荐算法或者推荐系统，就说我这个要考虑，那个要考虑，不管是行为记录，还是用户特征，以至于各种节日效应，等等等等，想通过一个推荐系统完全搞定，目标很大，所以动作就极慢，构思洋洋洒洒做了很多，实现起来无从下手，或者难以寸进；我觉得，还是量力而行，从最容易下手的地方开始，先做到比没有强，然后根据不断地数据校验跟踪，逐渐加入其他考虑因素，步步前进，而不要一上来就定一个宏伟的庞大的目标；此外要考虑实现成本和开发周期，对于大部分技术实力没有网络，腾讯，淘宝那么强的公司而言，先把简单的东西搞好，已经足够有效了，然后在运营数据的基础上逐次推进，会越来越好；有些公司是被自己宏大的目标搞的焦头烂额，最后说，哎，没牛人搞不定啊。嗯，反正他们的目标，我显着是搞不定的。就这些，希望有所帮助

‘肆’ 跪求各位数学专业计算机专业高手，列举一下智能优化算法，以及目前最流行的智能优化算法。

智能优化算法有：遗传算法，禁忌搜索，模拟退火，蚁群算法，粒子群优化算法，动态进化等等。学习这些算法主要是用来计算，解决计算机方面的一些NP问题的最佳方法。智能的意思是模拟生物物种的智慧。这个方向的实际应用也很强。只是比较复杂非常难学。

‘伍’ 优化算法是什么

智能优化算法是一种启发式优化算法，包括遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法、粒子群算法等。·智能优化算法一般是针对具体问题设计相关的算法，理论要求弱，技术性强。一般，我们会把智能算法与最优化算法进行比较，相比之下，智能算法速度快，应用性强。

群体智能优化算法是一类基于概率的随机搜索进化算法，各个算法之间存在结构、研究内容、计算方法等具有较大的相似性。

各个群体智能算法之间最大不同在于算法更新规则上，有基于模拟群居生物运动长更新的（如PSO，AFSA与SFLA），也有根据某种算法机理设置更新规则（如ACO）。

(5)推荐优化算法扩展阅读：

优化算法有很多，关键是针对不同的优化问题，例如可行解变量的取值（连续还是离散）、目标函数和约束条件的复杂程度（线性还是非线性）等，应用不同的算法。 对于连续和线性等较简单的问题，可以选择一些经典算法，例如梯度、Hessian 矩阵、拉格朗日乘数、单纯形法、梯度下降法等；而对于更复杂的问题，则可考虑用一些智能优化算法。

‘陆’ 网站优化的234项算法有哪些

在SEO业内人士都知道，影响网络排名的因素有高达234项！如果一下子答庆宽说出来，都要好几分钟清亮，那真正我们日常工作中能否全部都顾及到呢？非常难！ 网络的算法有分大算法和细微的小算法，大算法一般不会有太大的变化而小算法就会随时变动。其实万变不离其宗不管网络怎么变，一个核心永远不会变：那就是用户的需求。如果我们把用户的需求做好了，我们就可以闪电式的坐在比赛的终点等着网络跑过来。记住：我们所做的任何事情有关SEO的事，都要围绕用户需求来做。
在学习234项算法前，要知道网络有8种常见的算法：
超链接算法： 可以识别谁最权威。
绿萝算法 打击买卖链接
原创星火算法 支持原创和优质的站点
起源算法 针对个人差梁优质原创
绿萝算法 加大对外链软文的力度
冰桶算法 强度强行弹窗对用户体验的影响
石榴算法 提高页面的质量
网络星火计划 保护原创的“星火计划”
http://www.luoyuseo.com/?p=30

‘柒’ 推荐算法小结

输入 ：与用户相关的包含众多特征（feature）的数据：

用户的注册信息（职业、年龄、性别等 显信息），行为信息（使用功能、有效使用时长等 隐信息）。

输出 ：推荐给用户的功能列表（根据得分高低排序）

函数 ： 传统算法 、 机器学习算法 （Machine Learning）、 深度学习算法 （Deep Learning）

基于流行度的算法非常简单粗暴，类似于各大新闻、微博热榜等，根据VV、UV、日均PV或分享率等数据来按某种热度（加权）排序来推荐给用户。

访问次数 （VV）：记录1天内所有访客访问了该网站多少次，相同的访客有可能多次访问该网站，且访问的次数累加。

独立访客 （UV）：记录1天内所有访客访问了该网站多少次，虽然相同访客能多次访问网站，但只计算为1个独立访客。

PV访问量 （Page View）：即页面访问量，每打开一次页面或者刷新一次页面，PV值+1。

优点：该算法简单，适用于刚注册的新用户

缺点：无法针对用户提供个性化的推荐

改进：基于该算法可做一些优化，例如加入用户分群的流行度进行排序，通过把热榜上的体育内容优先推荐给体育迷，把政要热文推给热爱谈论政治的用户。

基于用户的协同过滤推荐算法 （UserCF）：针对目标用户（A），先通过兴趣、爱好或行为习惯找到与他相似的“其他用户”（BCD...），然后把BCD...喜欢的并且A没有浏览过的物品或功能推给A。

基于物品的协同过滤推荐算法 （ItemCF）：例如由于我之前看过张艺谋导演的《英雄》这部电影，会给我推荐《红高粱》、《归来》等同导演电影。

1）分析各个用户对物品的评价，通过浏览记录、购买记录等得到用户的隐性评分；

2）根据用户对物品的隐性评分计算得到所有用户之间的相似度；

3）选出与目标用户最相似的K个用户；

4）将这K个用户隐性评分最高并且目标用户又没有浏览过的物品推荐给目标用户。

优点：

基于用户的协同过滤推荐算法是给目标用户推荐那些和他有共同兴趣的用户喜欢的物品，所以该算法推荐较为社会化，即推荐的物品是与用户兴趣一致的那个群体中的热门物品；

适于物品比用户多、物品时效性较强的情形，否则计算慢；

能实现跨领域、惊喜度高的结果。

缺点：

在很多时候，很多用户两两之间的共同评分仅有几个，也即用户之间的重合度并不高，同时仅有的共同打了分的物品，往往是一些很常见的物品，如票房大片、生活必需品；

用户之间的距离可能变得很快，这种离线算法难以瞬间更新推荐结果；   

推荐结果的个性化较弱、较宽泛。

改进：

两个用户对流行物品的有相似兴趣，丝毫不能说明他们有相似的兴趣，此时要增加惩罚力度；

如果两个用户同时喜欢了相同的物品，那么可以给这两个用户更高的相似度；

在描述邻居用户的偏好时，给其最近喜欢的物品较高权重；

把类似地域用户的行为作为推荐的主要依据。

1）分析各个用户对物品的浏览记录；

2）依据浏览记录分析得出所有物品之间的相似度；

3）对于目标用户评价高的物品，找出与之相似度最高的K个物品；

4）将这K个物品中目标用户没有浏览过的物品推荐给目标用户

优点：

基于物品的协同过滤推荐算法则是为目标用户推荐那些和他之前喜欢的物品类似的物品，所以基于物品的协同过滤推荐算法的推荐较为个性，因为推荐的物品一般都满足目标用户的独特兴趣。

物品之间的距离可能是根据成百上千万的用户的隐性评分计算得出，往往能在一段时间内保持稳定。因此，这种算法可以预先计算距离，其在线部分能更快地生产推荐列表。

应用最广泛，尤其以电商行业为典型。

适于用户多、物品少的情形，否则计算慢

推荐精度高，更具个性化

倾向于推荐同类商品

缺点：

不同领域的最热门物品之间经常具有较高的相似度。比如，基于本算法，我们可能会给喜欢听许嵩歌曲的同学推荐汪峰的歌曲，也就是推荐不同领域的畅销作品，这样的推荐结果可能并不是我们想要的。

在物品冷启动、数据稀疏时效果不佳

推荐的多样性不足，形成信息闭环

改进：

如果是热门物品，很多人都喜欢，就会接近1，就会造成很多物品都和热门物品相似，此时要增加惩罚力度；

活跃用户对物品相似度的贡献小于不活跃的用户；

同一个用户在间隔很短的时间内喜欢的两件商品之间，可以给予更高的相似度；

在描述目标用户偏好时，给其最近喜欢的商品较高权重；

同一个用户在同一个地域内喜欢的两件商品之间，可以给予更高的相似度。

（相似度计算：余弦相似度、Jaccard系数、皮尔森相关系数等）

常见经典 ML 分类算法：

逻辑回归 （Logistics Regression）

支持向量机 （SVM）

随机森林 （Random Forest）

提升类算法 （Boosting）：Adaboost、GBDT、XGboost

一般处理流程：数据处理 -> 特征工程 -> 模型选择 -> 交叉验证 -> 模型选择与模型融合

特征清洗 ：剔除不可信样本，缺省值极多的字段不予考虑

特征预处理 ：单个特征（归一化，离散化，缺失值补全，数据变换），多个特征（PCA/LDA降维，特征选择）

使用工具 ：pandas（python开源库）

模型选择与模型融合 ：根据交叉验证得分选择前几名模型，然后进行模型融合（Bagging、Boosting、Stacking）

DL 优势 ：ML 中特征工程是十分重要并且要根据行业经验确定，DL 可以自己从数据中学习特征。DL 能自动对输入的低阶特征进行组合、变换，得到高阶特征。对于公司产品应用领域来说，用户的注册信息（职业、年龄、性别等 显信息），行为信息（使用功能、有效使用时长等 隐信息）。这些就可以作为低阶特征输入。

RNN系列 （处理文本数据）

CNN系列 （处理图像数据）

DNN （处理一般性分类）