梯度下降算法的理解(计算机是如何处理问题的)

现在,虽说很多的算法和模型已经被开源的算法库包含进去了,但我们不仅仅需要了解如何调用算法库,还需要知道算法的估算过程和原理。

本篇就是介绍梯度下降算法和随机梯度下降算法,这也是计算机解决最优化问题的算法中最核心的算法。

思路引入-模拟下山

我们知道,实际上求拟合程度,也就是求损失函数(目标函数)最小值。而算法的优劣,就是找到最小值的最快路径。

可以把过程理解为,人们上下山时,选择最快的路。我们首先就是找到最陡峭的地方,然后走一步。再以当前位置找最陡峭的位置,走一步。依次类推。

详细步骤如下:

  1. 第一步,明确自己现在所处的位置
  2. 第二步,找到相对于该位置而言下降最快的方向
  3. 第三步, 沿着第二步找到的方向走一小步,到达一个新的位置,此时的位置肯定比原来低
  4. 第四步, 回到第一步
  5. 第五步,终止于最低点

梯度下降

我们知道基本原理了,那么我们来用数学的方式表达出来。在计算机中,我们的目的,就是通过迭代找到目标函数的最小值。

在一元函数中,斜率就是我们这里要用到的方向。

f^{‘}(x_{0})=\lim\limits_{\Delta\to0}\dfrac{\Delta y}{\Delta x} =\lim\limits_{\Delta\to0}\dfrac{f(x_0+\Delta x)-f(x_0)}{\Delta x}

同理,在多元函数中,这里指的就是偏导数,对每个变量分别进行微分,那么最终所求出来的便是一个有方向的向量。

梯度的方向是函数在给定点上升最快的方向,那么梯度的反方向就是函数在给定点下降最快的方向,这正是我们所需要的

所以我们只要沿着梯度的方向一直走,就能走到局部的最低点!

步长

我们知道了原理,下面我就就说说影响计算的因素,步长。可以直观理解为我们下山时迈的步子大小,假设是一个巨人,和一个蚂蚁同时找最低点。就会出现两种极端,一种太费时,一种很可能迈过了最低的凹池。

所以,步长大小的选择,在计算机计算的过程中,也至关重要。在数学上可以理解为,步长是一个有方向和模长的矢量。

实例

设有一个单变量函数

J(\theta)=\theta^2

则函数直接求导可得

J^{‘}(\theta)=2\theta
设随机点:\theta^{0}=1
设步长 \alpha=0.4

则有梯度下降公式:

\theta^1=\theta^0-\alpha \nabla J(\theta)

那么计算过程就为:

\theta^0 = 1
\theta^1=\theta^0-\alpha*J^{‘}(\theta^0)=1-0.4*0.2=0.2
\theta^2=\theta^1-\alpha*J^{‘}{(\theta^1)}=0.04
\theta^3=0.008
\theta^4=0.0016

如上图示,经过四次计算便得到最低点了。同理,多变量的梯度也是如此。

我们假设一个二元函数为:

J(\theta)=\theta^{2}_{1}+\theta^{2}_2

那么其梯度函数为:

\nabla J(\theta)=\lang 2\theta_1,2\theta_2 \rang

具体迭代方式可参考一元函数。

代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @FileName: gradient_descent.py
# @Software: PyCharm

from numpy import *

# 数据集大小 即20个数据点
m = 20
# x的坐标以及对应的矩阵
X0 = ones((m, 1))  # 生成一个m行1列的向量,也就是x0,全是1
X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量,也就是x1,从1到m
X = hstack((X0, X1))  # 按照列堆叠形成数组,其实就是样本数据
# 对应的y坐标
Y = array([
    3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
    11, 13, 13, 16, 17, 18, 17, 19, 21
]).reshape(m, 1)
# 学习率
alpha = 0.01


# 定义代价函数
def cost_function(theta, X, Y):
    diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘,就需要用到dot()
    return (1/(2*m)) * dot(diff.transpose(), diff)


# 定义代价函数对应的梯度函数
def gradient_function(theta, X, Y):
    diff = dot(X, theta) - Y
    return (1/m) * dot(X.transpose(), diff)


# 梯度下降迭代
def gradient_descent(X, Y, alpha):
    theta = array([1, 1]).reshape(2, 1)
    gradient = gradient_function(theta, X, Y)
# 当小于0.00005时,认为趋于平滑,跳出循环
    while not all(abs(gradient) <= 1e-5):
        theta = theta - alpha * gradient
        gradient = gradient_function(theta, X, Y)
    return theta


optimal = gradient_descent(X, Y, alpha)
print('optimal:', optimal)
print('cost function:', cost_function(optimal, X, Y)[0][0])


# 根据数据画出对应的图像
def plot(X, Y, theta):
    import matplotlib.pyplot as plt
    ax = plt.subplot(111)  # 这是我改的
    ax.scatter(X, Y, s=30, c="red", marker="s")
    plt.xlabel("X")
    plt.ylabel("Y")
    x = arange(0, 21, 0.2)  # x的范围
    y = theta[0] + theta[1]*x
    ax.plot(x, y)
    plt.show()


plot(X1, Y, optimal)

随机梯度算法

在梯度算法中,有一个致命的缺点,就是当这个人所在的不是一座山,而是一座山脉时就会出现问题,所找到的知识某一个山谷。但并不能保证这个山谷是最低的。

解决办法就是随机生成多个出发点,然后分别求出最低点,把生成的不同最低点相比较,取出最小值。

参考链接:
https://blog.csdn.net/qq_41800366/article/details/86583789
https://baijiahao.baidu.com/s?id=1639202882632470513&wfr=spider&for=pc

赞 (0)