[机器学习-2]梯度下降法及实现(python)
样例(Example)利普西斯连续(L-continuity)利普西斯光滑(L-smoothness)凸集(Convex Set)凸函数(Convex Function)强凸(Strong Convexity)方向导数泰勒展开局部与全局最优解梯度下降法回溯线算法(backtracking line search)精确线算法(exact line search)样例(Example)
!!想看实现,直接跳转回溯线算法与精确线算法。
今天,在做机器学习的作业的时候,我的室友和我说线性回归那道题目应该用步长来做,如果大于步长减半,后来我实现这种算法以后,发现和题目要求不一样。我室友说的是回溯线算法(backtracking line search),而我最后实现的是精确线算法(exact line search)。现在和大家介绍这两种经典算法
Figure 1
题目长这样,就是用线性回归求一个二范数的最小值.
下面简单介绍一下GD所需的数学知识
利普西斯连续(L-continuity)
利普西斯光滑(L-smoothness)
由利普西斯光滑我们可以得到一个重要的结论
凸集(Convex Set)
凸函数(Convex Function)
需要说明的是,目前仍有许多数提到上凸与下凸的概念,这种定义已经过时而且明显没有搞清楚凸函数的真正定义是什么,凸函数指的是从函数上任意两点连线,线段与函数包围的区域为凸集
强凸(Strong Convexity)
类似的,根据强凸性,我们又可以得到机器学习中一些比较好的性质
方向导数
泰勒展开
机器学习中常见的泰勒展开为二阶,二阶导为海森矩阵,根据精度要求可能会高阶展开
局部与全局最优解
以最小解为例
对于凸集,有一个非常好的性质,也是机器学习里非常关心的一个性质就是局部最优解即全局最优解,所以很多时候会把一个集合拆成多个凸集进行优化
梯度下降法
梯度下降法通俗地讲就是沿负梯度方向迭代
在步长不变时可能会出现这种问题
回溯线算法(backtracking line search)
import pandas as pdimport numpy as npimport matplotlib.pyplot as pltimport mathdef load_csv(path, data):data_read = pd.read_csv(path)list = data_read.values.tolist()data = np.array(list)# print(data)return datadef f(x,A,b):func = np.dot(A,x)-bresult = 0.5*np.linalg.norm(func, ord = 2)return resultdef step_gradient(func, start, A, b, array1, array2, array3):alpha = 1step = 0index = []for i in range(0, 1000):index.append(i)alpha = 1step =alphagrad = np.dot(A.T,(np.dot(A,start)-b)) # 1000*500 * 1000 *500while(func(start,A,b)<func(start-step*grad,A,b)):step = step*0.5start = start - step*gradarray1 = np.append(array1, step)array2 = np.append(array2, np.linalg.norm(grad))array3 = np.append(array3, func(start, A, b))plt.figure(figsize=(4,3))plt.semilogy(index,array1)plt.figure(figsize=(4,3))plt.semilogy(index,array2)plt.figure(figsize=(4,3))plt.semilogy(index,array3)plt.show()return 1if __name__ == '__main__':initi = np.zeros((1000,1)).reshape(1000,1)b = np.zeros((500,1)).reshape(500,1)A = np.zeros((500,1000)).reshape(500,1000)b = load_csv('b.csv', b)A = load_csv('A.csv', A)function = f(initi, A, b)arr_1 = np.array([])arr_2 = np.array([])arr_3 = np.array([])step_gradient(f, initi, A, b, arr_1, arr_2, arr_3)
输出如下
第一张是步长的变化,第二章是向量模的变化,最后是函数值得变化
精确线算法(exact line search)
先求出目标函数的梯度为A.T(Ax-b)
然后我才用了近似算法,其实严格来说固定变量以后,就是一个二次函数求极值的问题,只是我这里方便起见采用了近似
import pandas as pdimport numpy as npimport matplotlib.pyplot as pltimport mathdef load_csv(path, data):data_read = pd.read_csv(path)list = data_read.values.tolist()data = np.array(list)# print(data)return datadef f(x,A,b):func = np.dot(A,x)-bresult = 0.5*np.linalg.norm(func, ord = 2)return resultdef step_gradient(func, start, A, b, array1, array2, array3, matrix):step = 0index = []for i in range(0, 1000):index.append(i)step =0grad = np.dot(A.T,(np.dot(A,start)-b)) # 1000*500 * 1000 *500up = np.dot(grad.T,grad)down = np.dot(grad.T, matrix)down = np.dot(down, grad)step = up/downstart = start - step*gradarray1 = np.append(array1, step)array2 = np.append(array2, np.linalg.norm(grad))array3 = np.append(array3, func(start, A, b))plt.figure(figsize=(4,3))plt.semilogy(index,array1)plt.figure(figsize=(4,3))plt.semilogy(index,array2)plt.figure(figsize=(4,3))plt.semilogy(index,array3)plt.show()return 1if __name__ == '__main__':initi = np.zeros((1000,1)).reshape(1000,1)b = np.zeros((500,1)).reshape(500,1)A = np.zeros((500,1000)).reshape(500,1000)hessian = np.zeros((1000,1000)).reshape(1000,1000)b = load_csv('b.csv', b)A = load_csv('A.csv', A)hessian = np.dot(A.T,A)function = f(initi, A, b)arr_1 = np.array([])arr_2 = np.array([])arr_3 = np.array([])step_gradient(f, initi, A, b, arr_1, arr_2, arr_3, hessian)
输出如下,可以看到下降的非常快