ML_5最优化方法：梯度下降

机器学习就是需找一种函数f(x)并进行优化，且这种函数能够做预测、分类、生成等工作。

关于“如何找到函数f(x)”的方法论。可以看作是机器学习的“三板斧”：

第一步：定义一个函数集合（define a function set）——模型
第二步：判断函数的好坏（goodness of a function）——策略：损失函数，期望风险，经验风险
第三步：选择最好的函数（pick the best one）——算法，归结为最优化

一、梯度下降法

在绝大多数的情况下，损失函数是很复杂的（比如逻辑回归），根本无法得到参数估计值的表达式。因此需要一种对大多数函数都适用的方法。这就引出了“梯度算法”。

是一种基于搜索的最优化方法。梯度下降(Gradient Descent, GD)优化算法，其作用是用来对原始模型的损失函数进行优化，以便寻找到最优的参数，使得损失函数的值最小。

从损失值出发，去更新参数，且要大幅降低计算次数。

梯度下降算法作为一个聪明很多的算法，抓住了参数与损失值之间的导数，也就是能够计算梯度（gradient），通过导数告诉我们此时此刻某参数应该朝什么方向，以怎样的速度运动，能安全高效降低损失值，朝最小损失值靠拢。

梯度：导数就是变化率。梯度是向量，和参数维度一样。梯度是一个向量，向量有方向，梯度的方向就指出了函数在给定点的上升最快的方向。梯度指向误差值增加最快的方向，导数为0（梯度为0向量）的点，就是优化问题的解。

梯度下降算法：随机选择一个方向，然后每次迈步都选择最陡的方向，直到这个方向上能达到的最低点。

为什么要梯度要乘以一个负号？

梯度的方向就是损失函数值在此点上升最快的方向，是损失增大的区域，而我们要使损失最小，因此就要逆着梯度方向走，自然就是负的梯度的方向，所以此处需要加上负号

关于参数 η :

梯度对应的是下山的方向，而参数对应的是步伐的长度。在学术上，我们称之为“学习率”(learning rate)，是模型训练时的一个很重要的超参数，能直接影响算法的正确性和效率：

首先，学习率不能太大。因此从数学角度上来说，一阶泰勒公式只是一个近似的公式，只有在学习率很小，也就是很小时才成立。并且从直观上来说，如果学习率太大，那么有可能会“迈过”最低点，从而发生“摇摆”的现象（不收敛），无法得到最低点
其次，学习率又不能太小。如果太小，会导致每次迭代时，参数几乎不变化，收敛学习速度变慢，使得算法的效率降低，需要很长时间才能达到最低点。

致命问题

梯度算法有一个比较致命的问题：

从理论上，它只能保证达到局部最低点，而非全局最低点。在很多复杂函数中有很多极小值点，我们使用梯度下降法只能得到局部最优解，而不能得到全局最优解。那么对应的解决方案如下：首先随机产生多个初始参数集，即多组；然后分别对每个初始参数集使用梯度下降法，直到函数值收敛于某个值；最后从这些值中找出最小值，这个找到的最小值被当作函数的最小值。当然这种方式不一定能找到全局最优解，但是起码能找到较好的。

对于梯度下降来说，初始点的位置，也是一个超参数。

算法实现

二、随机梯度下降法

在之前介绍的梯度下降法的步骤中，在每次更新参数时是需要计算所有样本的，通过对整个数据集的所有样本的计算来求解梯度的方向。这种计算方法被称为：批量梯度下降法BGD(Batch Gradient Descent)。但是这种方法在数据量很大时需要计算很久。

针对该缺点，有一种更好的方法：随机梯度下降法SGD（stochastic gradient descent），随机梯度下降是每次迭代使用一个样本来对参数进行更新。虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近。但是相比于批量梯度，这样的方法更快

随机梯度下降法的过程中，学习率的取值很重要，这是因为如果学习率一直取一个固定值，所以可能会导致点已经取到最小值附近了，但是固定的步长导致点的取值又跳去了这个点的范围。因此我们希望在随机梯度下降法中，学习率是逐渐递减的

批量梯度下降法BGD(Batch Gradient Descent)。

优点：全局最优解；易于并行实现；
缺点：当样本数据很多时，计算量开销大，计算速度慢。

针对于上述缺点，其实有一种更好的方法：随机梯度下降法SGD（stochastic gradient descent），随机梯度下降是每次迭代使用一个样本来对参数进行更新。

优点：计算速度快；跳出局部最优解
缺点：收敛性能不好

三、对梯度下降法中求梯度的公式推导进行调试

以一维为例，求某一点（红色）相应的梯度值（导数），就是曲线在这个点上切线的斜率。我们可以使用距离该点左右两侧的两个蓝色点的连线的斜率，作为红点处切线斜率。

#%%求导
#python中有两种常见求导的方法，一种是使用Scipy库中的derivative方法，另一种就Sympy库中的diff方法。
import numpy as np
from scipy.misc import derivative
def f(x): 
    return x**5
for x in range(1, 4):
    print(derivative(f, x, dx=1e-6))

#sympy是符号化运算库，能够实现表达式的求导。所谓符号化，是将数学公式以直观符号的形式输出
from sympy import diff,symbols
t = symbols('x', real=True)
for i in range(1, 4):
    print(diff(t**5, t, i))
    print(diff(t**5, t, i).subs(t, i),i)
#%%封装函数
import numpy as np
import matplotlib.pyplot as plt
from scipy.misc import derivative
def lossFunction(x):
    return (x-2.5)**2-1
plot_x = np.linspace(-1,6,141)
# plot_y 是对应的损失函数值
plot_y = lossFunction(plot_x)
plt.plot(plot_x,plot_y)
plt.show()
def dLF(theta):
    return derivative(lossFunction, theta, dx=1e-6)
theta = 0.0
eta = 0.1
epsilon = 1e-6
while True:
    # 每一轮循环后，要求当前这个点的梯度是多少
    gradient = dLF(theta)
    last_theta = theta
    # 移动点，沿梯度的反方向移动步长eta
    theta = theta - eta * gradient
    # 判断theta是否达到最小值
    # 因为梯度在不断下降，因此新theta的损失函数在不断减小
    # 看差值是否达到了要求
    if(abs(lossFunction(theta) - lossFunction(last_theta)) < epsilon):
        break
print(theta)
print(lossFunction(theta))
#下面可以创建一个用于存放所有点位置的列表，然后将其在图上绘制出来
def gradient_descent(initial_theta, eta, epsilon=1e-6):
    theta = initial_theta
    theta_history.append(theta)
    while True:
        # 每一轮循环后，要求当前这个点的梯度是多少
        gradient = dLF(theta)
        last_theta = theta
        # 移动点，沿梯度的反方向移动步长eta
        theta = theta - eta * gradient
        theta_history.append(theta)
        # 判断theta是否达到损失函数最小值的位置
        if(abs(lossFunction(theta) - lossFunction(last_theta)) < epsilon):
            break
def plot_theta_history():
    plt.plot(plot_x,plot_y)
    plt.plot(np.array(theta_history), lossFunction(np.array(theta_history)), color='red', marker='o')
    plt.show()
#调整学习率    
eta=0.1
theta_history = []
gradient_descent(0., eta)
plot_theta_history()
print("梯度下降查找次数：",len(theta_history))

eta=0.01#变小后计算次数增加
theta_history = []
gradient_descent(0., eta)
plot_theta_history()
print("梯度下降查找次数：",len(theta_history))
eta=0.9 #步长调大
theta_history = []
gradient_descent(0., eta)
plot_theta_history()
print("梯度下降查找次数：",len(theta_history))
#如果学习率调的过大， 一步迈到“损失函数值增加”的点上去了，
#在错误的道路上越走越远（如下图所示），就会导致不收敛，会报OverflowError的异常。
def lossFunction(x):
    try:
        return (x-2.5)**2-1
    except:
        return float('inf')
#设定条件，结束死循环
def gradient_descent(initial_theta, eta, n_iters, epsilon=1e-6):
    theta = initial_theta
    theta_history.append(theta)
    i_iters = 0
    while i_iters < n_iters:
        gradient = dLF(theta)
        last_theta = theta
        theta = theta - eta * gradient
        theta_history.append(theta)
        if(abs(lossFunction(theta) - lossFunction(last_theta)) < epsilon):
            break
        i_iters += 1
#%%线性回归中的梯度下降
#用向量化的方式编写代码，但是发现在真实数据中效果比较差，这是因为数据的规模不一样，因此在梯度下降之前需要使用归一化。
from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()
standardScaler.fit(X_train)
X_train_std = standardScaler.transform(X_train)
lin_reg3 = LinearRegression()
lin_reg3.fit_gd(X_train_std, y_train)
X_test_std = standardScaler.transform(X_test)
lin_reg2.score(X_test, y_test)