数优化

梯度下降

字数统计: 2k字   |   阅读时长: 9分
, , ,

摘要: 梯度下降的原理和代码模板

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文介绍梯度下降的算法原理和代码模板。在梯度概念的基础上，介绍梯度下降的算法，以及批梯度下降、随机梯度下降、小批量梯度下降这三个变种。最后用梯度下降解决力扣 1515，题解的代码可以作为梯度下降的代码模板。

$0 梯度

对于可微的 $f(x, y, z)$，向量场 $(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z})$ 为 $f$ 的梯度。

$1 梯度下降

目标函数 $f(\vec{x})$，梯度 $\nabla = (\frac{\partial f}{\partial x_{0}}, \frac{\partial f}{\partial x_{1}}, …, \frac{\partial f}{\partial x_{n-1}})$。

算法

  • 对于给定初始点 $\vec{\theta}$
  • 迭代 $\vec{\theta}$，直到两次迭代之间的 $f(\vec{\theta})$ 差值足够小，例如 EPS=1e-9
    • 求 $ \vec{\theta}$ 点的梯度 $\nabla$
    • 将 $\vec{\theta}$ 向梯度相反方向移动
      • $\vec{\theta} \leftarrow \vec{\theta} - \gamma \cdot \nabla$

如果学习速率 $\gamma$ 保持不变，迭代的结果将会在最小值点的周围来回震荡，无法继续接近最小值点。因此，我们需要设置学习率衰减，在迭代的过程中逐步减小学习率，向最小值点逼近。

批梯度下降

在每次更新时用所有样本，在梯度下降中，对于的 $\theta$ 更新，所有的样本都有贡献，计算得到的是完整的梯度，更新幅度比较大。对于凸优化问题，肯定可以达到全局最优。如果样本不多的情况下，这样是收敛的速度最快的。但是样本很多的时候更新一次要很久。

随机梯度下降

在每次更新时用随机的1个样本，即用样本集合中的一个样本来近似所有的样本，用于调整 $\theta$，计算得到的并不是完整梯度。对于凸优化问题，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是整体的方向是走向全局最优的，最终的结果一般是在全局最优附近。相比于批梯度，这样的方法更快，更快收敛，虽然不是全局最优，但很多时候是可以接受的。

小批量梯度下降

在每次更新时用 batch_size 个样本，这个批量可以反映样本的分布情况。在深度学习中，这种方法用的是最多的，因为这个方法收敛也不会很慢，收敛的局部最优也基本上可以接受。

$2 题目

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。

给你一个数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和 。

换句话说，请你为服务中心选址，该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值：

与真实值误差在 1e-5 之内的答案将被视作正确答案。

示例 1：
输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。

示例 2：
输入：positions = [[1,1],[3,3]]
输出：2.82843
解释：欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843

提示：

1
2
3
1 <= positions.length <= 50
positions[i].length == 2
0 <= xi, yi <= 100

算法：梯度下降

目标函数

梯度 $\nabla = (\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y})$

有一个实现细节需要注意：分母加上 EPS，避免分母为零。

梯度下降算法

  • 选定初始点 $\vec{x} = (x, y)$
  • 迭代 $\vec{x}$，直到两次迭代之间的 $f(\vec{x})$ 差值足够小，例如 EPS=1e-9
    • 计算梯度 $\nabla$
    • 更新 $\vec{x} \leftarrow \vec{x} - \gamma \cdot \nabla$

实现梯度下降时使用向量的模板：向量的实现。

代码 (C++) 批梯度下降

参数设置：

  • 初始点 : 所有带你的算术平均值
  • 学习率 : $\gamma = 1$
  • 学习率衰减 : $\eta = 1e-3$
  • EPS : 1e-9
  • batch_size : n(每次求梯度都使用全部数据)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
struct Function
{
    // 二元函数
    vector<Vector2> points;
    Function(vector<vector<int>>& p)
    {
        int n = p.size();
        points = vector<Vector2>(n);
        for(int i = 0; i < n; ++i)
        {
            points[i].y = p[i][1];
            points[i].x = p[i][0];
        }
    }
    double operator()(Vector2& p0) const
    {
        double ans = 0;
        for(const Vector2 &p: points)
            ans += (p0 - p).norm();
        return ans;
    }
};

struct Gradient
{
    // 二元函数的梯度
    vector<Vector2> points;
    Gradient(vector<vector<int>>& p)
    {
        int n = p.size();
        points = vector<Vector2>(n);
        for(int i = 0; i < n; ++i)
        {
            points[i].y = p[i][1];
            points[i].x = p[i][0];
        }
    }
    Vector2 operator()(const Vector2& p0) const
    {
        Vector2 nabla;
        for(const Vector2 &p: points)
        {
            nabla.x += (p0.x - p.x) / ((p0 - p).norm() + EPS);
            nabla.y += (p0.y - p.y) / ((p0 - p).norm() + EPS);
        }
        return nabla;
    }
};

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        int n = positions.size();
        Vector2 vec; // 初始值
        vector<Vector2> data; // 训练数据
        Gradient grad(positions); // batch_size 为 n
        Function f(positions);
        for(vector<int>& p: positions)
        {
            vec.x += p[0];
            vec.y += p[1];
            data.emplace_back(p[0], p[1]);
        }
        vec = vec * (1 / (double)n);
        double gamma = 1.0; // 学习率
        double decay = 1e-3; // 学习率衰减
        while(true)
        {
            // g 中持有全部训练数据，相当于 batch_size 为 n
            Vector2 g = grad(vec);
            Vector2 new_vec = vec - g * gamma; // 更新
            gamma *= (1.0 - decay); // 每一轮学习率衰减 1 次
            if(vec == new_vec)
                break;
            vec = new_vec;
        }
        return f(vec);
    }
};

代码 (C++) 小批量梯度下降

参数设置：

  • 初始点 : 所有带你的算术平均值
  • 学习率 : $\gamma = 1$
  • 学习率衰减 : $\eta = 1e-3$
  • EPS : 1e-9
  • batch_size : 16 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct Function
{
    // 二元函数
    vector<Vector2> *points;
    Function(vector<Vector2>* p):points(p){}
    double operator()(Vector2& p0) const
    {
        double ans = 0;
        for(Vector2 p: *points)
            ans += (p0 - p).norm();
        return ans;
    }
};

struct Gradient
{
    // 二元函数的梯度
    vector<Vector2> *points;
    Gradient(vector<Vector2>* p):points(p){}
    Vector2 operator()(const Vector2& p0, vector<int>& batch_data_idx) const
    {
        Vector2 nabla;
        for(int idx: batch_data_idx)
        {
            Vector2 p = (*points)[idx];
            nabla.x += (p0.x - p.x) / ((p0 - p).norm() + EPS);
            nabla.y += (p0.y - p.y) / ((p0 - p).norm() + EPS);
        }
        return nabla;
    }
};

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        int n = positions.size();
        Vector2 vec; // 初始值
        vector<Vector2> data; // 训练数据
        for(vector<int>& p: positions)
        {
            vec.x += p[0];
            vec.y += p[1];
            data.emplace_back(p[0], p[1]);
        }
        Gradient grad(&data);
        Function f(&data);
        vec = vec * (1 / (double)n);
        double gamma = 1.0; // 学习率
        double decay = 1e-3; // 学习率衰减
        int batch_size = 16;
        std::default_random_engine dre(6);
        vector<int> data_idx(n);
        for(int i = 0; i < n; ++i)
            data_idx[i] = i;
        Vector2 iter_vec = vec;
        vector<int> batch_data_idx;
        while(true)
        {
            shuffle(data_idx.begin(), data_idx.end(), dre);
            for(int i = 0; i < n; i += batch_size)
            {
                int j = min(i + batch_size, n);
                batch_data_idx.assign(j - i, 0);
                for(int k = i; k < j; ++k)
                    batch_data_idx[k - i] = data_idx[k];
                Vector2 g = grad(iter_vec, batch_data_idx);
                iter_vec = iter_vec - g * gamma; // 更新
                gamma *= (1.0 - decay); // 每一轮学习率衰减 1 次
            }
            if(vec == iter_vec)
                break;
            vec = iter_vec;
        }
        return f(vec);
    }
};
Share