梯度下降法（1）

1.梯度下降法基本原理

1.1 什么是梯度

梯度下降法(gradient descent)是一种常用的一阶(first-order)优化方法，是求解无约束优化问题最简单、最经典的方法之一。

梯度下降最典型的例子就是从山上往下走，每次都寻找当前位置最陡峭的方向小碎步往下走，最终就会到达山下（暂不考虑有山谷的情况）。

首先来解释什么是梯度？

这就要先讲导数和微分的区别：导数是函数在某一点处的斜率，是Δy和Δx的比值；而微分是指函数在某一点处的切线在横坐标取得增量Δx以后，纵坐标取得的增量，一般表示为dy。

梯度就是由微分结果组成的向量，令

有，

那么，函数在处的微分为

，，

因此，函数在处的梯度为。

梯度是一个向量，对于一元函数，梯度就是该点处的导数，表示切线的斜率。对于多元函数，梯度的方向就是函数在该点上升最快的方向。

1.2 为什么按照梯度的反方向能达到局部最低点

给出数学证明:

对于连续可微函数，从某个随机点出发，想找到局部最低点，可以通过构造一个序列，能够满足

那么我们就能够不断执行该过程即可收敛到局部极小点，可参考下图。

那么问题就是如何找到下一个点,并保证呢？我们以一元函数为例来说明。

对于一元函数来说，是会存在两个方向：要么是正方向，要么是负方向，如何选择每一步的方向，就需要用到泰勒公式，先看一下下面这个泰勒展式：

注：

其中，表示在处的导数。

若想，就需要保证，令

，

步长是一个较小的正数，从而有

因此，有

每一步我们都按照更新，这就是梯度下降的原理。

1.3 对参数的认识

对参数解释一下，在梯度下降算法中被称作为学习率或者步长，意味着我们可以通过来控制每一步走的距离。既要保证步子不能太小，还没下到山底太阳就下山了；也要保证步子不能跨的太大，可能会导致错过最低点。

在梯度前加负号就是朝梯度的反方向前进，因为梯度是上升最快的方向，所以方向就是下降最快的方向。

2.梯度下降法实例

2.1 一元函数梯度下降法

设一元函数为

函数的梯度(微分)：

设迭代起点为，步长，依据梯度下降法公式有

2.2 多元函数梯度下降法

设二元函数为

函数的梯度

设起点为(2,3)，步长,根据梯度下降的公式,经过多次迭代后，有

......

3.损失函数

3.1 什么是损失函数

损失函数也叫代价函数(cost function)，是用来衡量模型预测出来的值h(θ)与真实值y之间的差异的函数，如果有多个样本，则可以将所有代价函数的取值求均值，记做J(θ)。代价函数有下面几个性质:

1. 对于每种算法来说，代价函数不是唯一的；
2. 代价函数是参数θ的函数；
3. 总的代价函数J(θ)可以用来评价模型的好坏，代价函数越小说明模型和参数越符合训练样本(x, y)；
4. J(θ)是一个标量

3.2 最常见损失函数

最常见的代价函数是均方误差函数

其中，m：为训练样本个数

：函数表示估计值，表达式为

y：原训练样本中的值

我们需要做的就是找到θ的值，使得J(θ)最小。代价函数的图形跟我们上面画过的图很像，如下图所示。

看到这个图，也就知道了我们可以用梯度下降算法来求可以使代价函数最小的θ值。

3.3 损失函数的梯度

其中，

​

​这里有两个变量，为了方便矩阵表示，我们给增加一维，这一维的值都是1，并将会乘到上，则成为矩阵X即如下形式：

将两个变量也写成矩阵形式有

相应地，矩阵有

那么cost function的矩阵形式为：

这样写出来后再去对应上面的公式，就很容易理解了。

4.梯度下降算法实现线性回归

下面我们来举一个用梯度下降算法来实现线性回归的例子。

有一组数据如下图所示，我们尝试用这组数据求出这些点的线性回归模型。

4.1产生矩阵X和矩阵y

m = 18; %18个数据样本
X0 = ones(m,1);
X1 = (1:m)';
X = [X0, X1]; %矩阵X
y = [2,3,3,5,8,10,10,13,15,15,16,19,19,20,22,22,25,28]';%矩阵y
alpha = 0.01;
theta = gradient_descent(X, y, alpha, m); %更新theta，求最优权值矩阵

4.2用梯度下降法公式定义梯度函数

function [grad_res] =  gradient_function(theta, X, y, m)
    diff = X * theta - y;
    grad_res = X' * diff / m;
end

4.3梯度下降算法

接下来就是最重要的梯度下降算法，我们的初始值都为1，再进行梯度下降过程。

function [theta_res] =  gradient_descent(X, y, alpha, m)
    theta = [1;1];
    gradient = gradient_function(theta, X, y, m);
    while sum(abs(gradient)>1e-5)>=1
        theta = theta - alpha * gradient;
        gradient = gradient_function(theta, X, y, m);
    end
    theta_res = theta;
end

通过该过程，最终求出的线性回归的曲线如下

5.附录Source Code

5.1matlab一元函数的梯度下降程序

clc;
close all;
clear all;
%% 
delta = 1/100000;
x = -1.1:delta:1.1;
y = x.^2;
dot = [1, 0.2, 0.04, 0.008];
figure;plot(x,y);
axis([-1.2, 1.2, -0.2, 1.3]);
grid on
hold on
plot(dot, dot.^2,'r');
for i=1:length(dot)
    text(dot(i),dot(i)^2,['\theta_{',num2str(i),'}']);
end
title('一元函数的梯度下降过程');

5.2matlab多元函数的梯度下降程序

pecision = 1/100;
[x,y] = meshgrid(-3.1:pecision:3.1);
z = x.^2 + y.^2;
figure;
mesh(x,y,z);
dot = [[2,3];[1.6,2.4];[1.28,1.92];[5.09e-10, 7.64e-10]];
hold on
scatter3(dot(:,1),dot(:,2),dot(:,1).^2+dot(:,2).^2,'r*');
for i=1:4
   text(dot(i,1)+0.4,dot(i,2),dot(i,1).^2+0.2+dot(i,2).^2+0.2,['\theta_{',num2str(i),'}']);
end
title('二元函数的梯度下降过程')

5.3matlab梯度下降的线性回归

m = 18;
X0 = ones(m,1);
X1 = (1:m)';
X = [X0, X1];
y = [2,3,3,5,8,10,10,13,15,15,16,19,19,20,22,22,25,28]';
alpha = 0.01;
theta = gradient_descent(X, y, alpha, m); %更新theta，求最优权值矩阵

function [grad_res] =  gradient_function(theta, X, y, m)
    diff = X * theta - y;
    grad_res = X' * diff / m;
end

function [theta_res] =  gradient_descent(X, y, alpha, m)
    theta = [1;1];
    gradient = gradient_function(theta, X, y, m);
    while sum(abs(gradient)>1e-5)>=1
        theta = theta - alpha * gradient;
        gradient = gradient_function(theta, X, y, m);
    end
    theta_res = theta;
end

_______________END_______________