机器学习中的优化算法!
共 6170字,需浏览 13分钟
· 2020-08-09
每日干货 & 每月组队学习,不错过
作者:李祖贤,Datawhale高校群成员,深圳大学
1.1 最速下降法的原理
![](https://filescdn.proginn.com/a97afa0ab05d6c782abe23947f82054f/1c4753fe172d9d147edc399320192d65.webp)
![](https://filescdn.proginn.com/a97afa0ab05d6c782abe23947f82054f/1c4753fe172d9d147edc399320192d65.webp)
![](https://filescdn.proginn.com/da95ca54cab9be9d17269a20817b53d2/99961ad54b93bf4be6b15b5e584e421e.webp)
![](https://filescdn.proginn.com/f1cd8a2ab5ee2f34aead2f7fb12747d2/068e0dbdb869d4fa85a6a577a21dad95.webp)
![](https://filescdn.proginn.com/26165a49add3b6508634a9810d544d47/f5cf82eb0041a53cf1aa4a5ec3fbbf61.webp)
![](https://filescdn.proginn.com/26165a49add3b6508634a9810d544d47/77ed1df9d73a8ebca49720be2c31ddc2.webp)
![](https://filescdn.proginn.com/9c8c960f15b389b575748300e4eeefb8/f16ecd8ba8904fb8354f37ed9cce9b16.webp)
![](https://filescdn.proginn.com/5465d77941aed9a1fe30243770713b31/1f009e6cf1ef6a23699d9776bf1a6cdf.webp)
![](https://filescdn.proginn.com/5465d77941aed9a1fe30243770713b31/1f009e6cf1ef6a23699d9776bf1a6cdf.webp)
![](https://filescdn.proginn.com/11204d75dd0758b978ac82f50674813f/447e4e89deb2308da6e00a3703e75dd3.webp)
![](https://filescdn.proginn.com/cd8643a3b4b2731e32ff7c00cd4b99b8/e2679be5880ed61326aaba2a3aff6973.webp)
![](https://filescdn.proginn.com/720b028d15f1929d26d13635593243a9/ab3711974af46260e4051c92282e108c.webp)
![](https://filescdn.proginn.com/cbfa2997421208575db7b7f13ac31417/9eef4bcee71291d245ca5e1fbe01aa31.webp)
我们从上面可以看到,不同的G矩阵使用最速下降法的迭代速度有明显的差异,原因在后文给出。
1.2 最速下降法的收敛速度
1.2.1 收敛性
向量u在矩阵G度量下的范数:
矩阵G度量下的Cauchy-Schwarz不等式:
Kantorovich不等式:
1.2.3 收敛速度的上界
![](https://filescdn.proginn.com/c0601d066fd318b5059591c9d7c7bc80/eb6b2f71a3affe54ab4aac5b8dd49527.webp)
由此可知,最速下降法的收敛速度是线性的,这个速度依赖于G的最大最小特征值。
我们假设G和b产生了微小扰动变成了 ,正定二次函数:
的导函数方程相应变成了
,方程的解记为
,其中
非奇异,
满足
非零。那么:
条件数与范数有关,因此是G的相对误差与b的相对误差之和的放大倍数。若矩阵G的条件数很大,扰动对解的影响很大,我们称这个问题是病态的,或G是病态的。若矩阵G的条件数不大,扰动对解的影响程度不大,我们就成这样的问题是良性的,或G是良性的。
因此:
![](https://filescdn.proginn.com/afb3824007f09fe06750b6299941e6b0/a3308a32eea378f3adc0f27dfb986195.webp)
这说明最速下降法的收敛速度依赖G的条件数,当G的条件数接近于1时,接近于0,最速下降法的收敛速度接近于超线性收敛;而当G的条件数很大时,
接近于1,则收敛很慢。
![](https://filescdn.proginn.com/53454f963d080debdb162239d80da356/837ad028a49004a3f9d60bd6c4803ac1.webp)
![](https://filescdn.proginn.com/b1435e49290ccef9ef484aa7f5858b50/7acd11ee779a62d55206543c24abf3b2.webp)
缺点:
收敛慢:线性收敛。
Zigzag现象(收敛慢的原因):若迭代步
是
的精确最小点,则
,因此:
,也就是上一步的方向与下一步的方向垂直。
![](https://filescdn.proginn.com/151e2d1bf370663ea1100243ca61af54/946cdb5e411ed7831ebbb3707e39ef17.webp)
没有二次终止性:即不具备对于任意的正定二次函数,从任意点出发,都可以经过有限步迭代取得极小值的性质。
二、Newton方法
2.1 基本Newton方法
设 具有连续二阶偏导数,当前迭代点是
。
在
的泰勒展开为:
![](https://filescdn.proginn.com/800ee06c17a7bfd4a9b15f6b8882c8bc/c719023df2d884f737206107e2164cdc.webp)
![](https://filescdn.proginn.com/a97afa0ab05d6c782abe23947f82054f/1c4753fe172d9d147edc399320192d65.webp)
![](https://filescdn.proginn.com/b950364e71fa4e0526ab1c26218b9688/aaa75571128be5b0bc80745690cb320b.webp)
![](https://filescdn.proginn.com/ee730de29c1e65572a48be080d7811a8/373cbb502605ab123a74b7b196e0764e.webp)
![](https://filescdn.proginn.com/a6591e25284390eb273c75c046d47258/6200d0e966ea2062da4fd1c06f4ee668.webp)
![](https://filescdn.proginn.com/20b195443b81221b117d271440011219/e73774f23bd2a795b6de5ca8c23d5eea.webp)
![](https://filescdn.proginn.com/379934dcc7040ec31268460f81a7af84/c61c7d535052022466e2cba10f6e357a.webp)
![](https://filescdn.proginn.com/379934dcc7040ec31268460f81a7af84/c61c7d535052022466e2cba10f6e357a.webp)
我们来看看牛顿迭代的方向和梯度下降的方向有什么不一样?(黑色为牛顿下降方向,红色为负梯度下降方向)
![](https://filescdn.proginn.com/239a7a7b006a16490503c8be9bf7f143/62388a598dbdcd2da71c364efaeb3889.webp)
下面我们用一个具体的例子来看看牛顿迭代法的效果:
![](https://filescdn.proginn.com/ecd4dc9d3d272d6081d5b3a23bc2e8c5/b00e73c1062d93fcc697d742ba0c36b6.webp)
![](https://filescdn.proginn.com/8cda165be1193d91f1fc239e9197d23a/ce4efcd6bac1452df09d472f57e8ab53.webp)
(3)迭代过程可能会出现奇异矩阵或者病态,以至于求逆很困难,导致迭代失败。
当
的特征值
,
求不出来。
当 的特征值
不一定小于0,牛顿方向未必是下降方向。
(4)每一步迭代需要计算Hesse矩阵,即计算n(n+1)/2个二阶偏导数,相当于求解一个线性方程组,计算量为O()
2.2 阻尼Newton方法
为了改善基本Newton方法的局部收敛准则,我们采用带一维线搜索的的Newton方法,即
![](https://filescdn.proginn.com/f52ea998fb1ac672f45269d8af424f0f/9c4cfa90d2cbbe63e15f16d1a4f75b46.webp)
其中是一维搜索的结果,该方法叫做阻尼Newton方法。此方法能保证对正定矩阵
,
单调下降;即使
离x稍远,由该方法产生的点列
仍能收敛到
。(对严格凸函数具有全局收敛性)
2.3 混合方法
![](https://filescdn.proginn.com/545b44ea7e47126cb0819d4a2ba9c9ff/232a7df46ad6c6c2f64fb89301b4dfed.webp)
![](https://filescdn.proginn.com/20b195443b81221b117d271440011219/e73774f23bd2a795b6de5ca8c23d5eea.webp)
![](https://filescdn.proginn.com/545b44ea7e47126cb0819d4a2ba9c9ff/232a7df46ad6c6c2f64fb89301b4dfed.webp)
![](https://filescdn.proginn.com/5465d77941aed9a1fe30243770713b31/1f009e6cf1ef6a23699d9776bf1a6cdf.webp)
![](https://filescdn.proginn.com/20b195443b81221b117d271440011219/e73774f23bd2a795b6de5ca8c23d5eea.webp)
![](https://filescdn.proginn.com/06723507cbf57b3c7c3aede0149b18ee/5f096da2043ce283f8d03f6229fc1414.webp)
![](https://filescdn.proginn.com/34cb5d36d1e3073a517323faebae951d/c9e8e4da8e0a9936ebc3b070af30b238.webp)
![](https://filescdn.proginn.com/ff1ed6f439b982cb00d1e036f3ea0bbd/8523b29c6e07e6ab4e6a4e134f144ddd.webp)
2.4 LM方法
![](https://filescdn.proginn.com/20b195443b81221b117d271440011219/e73774f23bd2a795b6de5ca8c23d5eea.webp)
![](https://filescdn.proginn.com/05cf518067d3af981a31a3aef3df1ef8/0a89d413a6e71d02b97611b7a61c5648.webp)
![](https://filescdn.proginn.com/ff68d692302b6c6154f6611fbbbed509/b48b4330df8a8228513b25969195ebbe.webp)
![](https://filescdn.proginn.com/3a8f55fc5525c879100ffb632f0400fe/851101ed35fc54960261fcc44ed0efd6.webp)
![](https://filescdn.proginn.com/c59bffe53b5ba3a045ae28f2ac7f50ac/2c62965b432c8837b389978dfd6b71c6.webp)
(1) 的大小对于方向的影响:
当
很小,求出的步长偏向于Newton方向。
当 很大,求出的步长则偏向于负梯度方向。
(2)当不正定时,可以简单取
![](https://filescdn.proginn.com/9b2413b81e9150e8ad8f7d69ebbd9911/3ea55488d1254fe651b3d9c02f241121.webp)
![](https://filescdn.proginn.com/be4b2662ee18674cd1e5f88ecc68b027/98a6bb765a436e53385a52a7f90a2ee6.webp)
![](https://filescdn.proginn.com/9ff3c2b31d9c0114b0950ef3202d6b30/f7e3fdd8afff66b25f2721bfb7c94350.webp)
![](https://filescdn.proginn.com/cac9a0cd93fb0a2acb2ee4b68c6830e9/c6c37ffc379b6b2bca41f0b60c898c95.webp)
三、拟牛顿方法
Newton方法的优缺点:
(1)当初始点接近极小点时,迭代序列收敛于极小点,并且收敛很快(二阶收敛);
(2)当初始点不接近极小点时,迭代序列容易收敛到鞍点或者极大点(局部收敛性而不是全局收敛)。
(3)迭代过程可能会出现奇异矩阵或者病态,以至于求逆很困难,导致迭代失败。
当
的特征值
,
求不出来。
当
的特征值
,
不一定小于0,牛顿方向未必是下降方向。
![](https://filescdn.proginn.com/1990cae61411bde5d12382aac11164b2/c827db5db967d3a99c7bf92f1655283b.webp)
为此,我们考虑构造一种方法,她既不需要计算二阶偏导数,又有较快的收敛速度。
3.1 拟牛顿条件
![](https://filescdn.proginn.com/b8c03e09c63f95ab68aaf1666eff377f/5aa1f562086bc090734a992f56c46f65.webp)
![](https://filescdn.proginn.com/5664b83414f0024e852a6349deb0a274/36baf3d88c18dd5a120bfa92c9920911.webp)
我们可以使用矩阵似
得到
n个方程,n(n+1)/2个变量。
![](https://filescdn.proginn.com/5acf9c94dead6351bfdda3b45412b181/e1d20ea66d6b1d12c6865777e7ca4ca2.webp)
因此拟牛顿条件为:
![](https://filescdn.proginn.com/d7106f7815adbbf87c6e3142532cb520/914d8fa7b4f228d70d6918b3772caab3.webp)
在上述算法中,初始矩阵一般取单位矩阵,第一步迭代方向取为负梯度方向。
那么,算法的核心就是怎么由去修正
,即
,而
的取法是多种多样的,但是他应该具有简单、计算量小、有效的特点。
3.2 拟牛顿方法的修正公式
3.2.1 对称秩1公式
![](https://filescdn.proginn.com/f35e219a6d5db17b284b14f8ae47aa7c/9efbfdd56eb670244b95f52f447c3639.webp)
![](https://filescdn.proginn.com/c333516395b686bc7562447562fcc2a6/5936bf1d52f4f4d82e8e5309148f05ce.webp)
将代入拟牛顿方程
得到:
![](https://filescdn.proginn.com/11992fecfcdcb32d9872013880a8994f/c894bfbffcc7383729fe7c14112f94e0.webp)
![](https://filescdn.proginn.com/b86fd7f0588356d72b8b4f2d122252a9/89641140b30d83821b18a0d6cd9086dc.webp)
![](https://filescdn.proginn.com/af9753ad68af0cfde10930c01655679b/74dbf604f5d1964cde84660ad970a1a4.webp)
![](https://filescdn.proginn.com/91e5a2a25a19152296434864c96d1722/a04c6758be1e7c75ff4d0277e04bc40e.webp)
![](https://filescdn.proginn.com/b6a9c2e4a2570ad64b6a301eeb7a2083/b132f4a26596796f20c16fb51dabe025.webp)
![](https://filescdn.proginn.com/aae8fea39ea79d8dc454c7207d72fdd7/3c707a2820ce4c1ac9fd2c7511217790.webp)
将代入
得到
![](https://filescdn.proginn.com/711ac215ee3917cf02cc0a8cc2ae3601/7e110c3ddc752d37e9b381ce740285bb.webp)
因此,由此得到
![](https://filescdn.proginn.com/1fdbe0ac9000775a0e0f627fd6daf7fa/f2f3b6800dae0df540f722f9b9316d81.webp)
![](https://filescdn.proginn.com/95962ffc15a42f00a8bc36da615ec888/8d5ed75e3c3aa4cbfc966acc6fca31cb.webp)
如果我们想将换成等价的
,则需要用到SMW公式:
![](https://filescdn.proginn.com/56d2afe3385de529f75ba8b39b9d25bc/b1d714aaa13577372765880b43b45a46.webp)
最终得到对称秩1公式:
3.2.2 对称秩2公式
![](https://filescdn.proginn.com/f35e219a6d5db17b284b14f8ae47aa7c/9efbfdd56eb670244b95f52f447c3639.webp)
![](https://filescdn.proginn.com/f0de9218e79900a398cfb8769aa70cef/60f8ef58078d5a768e60081cfa53c9b5.webp)
![](https://filescdn.proginn.com/89b1aeea9fadea80c75a81bec4bfe02a/990b1f0988b2d4a724d6d5daa07d52e5.webp)
将代入
中,得到
的修正公式
。
(1)DFP方法
![](https://filescdn.proginn.com/0a424ec681b687b13e151e14d4043bca/44d4cd1489b3074979d715c92eee017d.webp)
由于的选择不是唯一的,为了计算方便,我们选择:
代入公式中可得 ,得到DFP公式:
![](https://filescdn.proginn.com/2ba4fa7ee337ea77ba965dd879c359c8/2821cf4285646c4dcaa00f8d103636a3.webp)
![](https://filescdn.proginn.com/9e43e321e287ff748ac3f8241586be0e/27501789593697cea879d2467bf6be30.webp)
(2)BFGS公式(对偶)
![](https://filescdn.proginn.com/3fa25e81a9f5b3bc464f73e7ac69a157/43b00e17b87fe599f88b12cf0fc784ae.webp)
![](https://filescdn.proginn.com/dbcfbd63d9e7448467f2d0e4756048e4/5fb51de5c9af01598c7ca0bc1462d263.webp)
根据SMW公式:
(3)Broyden族公式
3.3 三种拟牛顿方法的对比试验
(1)扩展Rosenbrock问题
(BFGS与DFP差异不大,SR1差些)(迭代次数与函数调用次数)
![](https://filescdn.proginn.com/7c513b90a80f267e10aa025c1580ee64/d108a591f8d0b3c69bc7e93ff9d1beab.webp)
![](https://filescdn.proginn.com/beadfcb220a2003bb1b5549776aade02/e6cdbab667799aa4ecb69ab541c55720.webp)
(2)由人工神经网络解微分方程的问题:
![](https://filescdn.proginn.com/2535def02e53ce0cd9434f6ed6056976/1b4896f71524f6995dca37f498dcb524.webp)
![](https://filescdn.proginn.com/791b46dc9905fefcd7b431f42f7e66b2/73350e6941a01e3afcbd43fcb279a994.webp)
![](https://filescdn.proginn.com/86de365280a82360bdfb6e8ba1019364/9f1f5ac9ed673168e0ab4d84965378df.webp)
四、使用牛顿法优化Rosenbrock函数实例(基于python)
![](https://filescdn.proginn.com/710ecaf52ea989f6e944bcfa2e8234de/45ea0e1a5742db29fb1d9e918b16c3e3.webp)
![](https://filescdn.proginn.com/1df0c36c7035b6a34a2f52033aab36c9/28602d8a98607eb7424cb31cd3f987a6.webp)
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import time
%matplotlib inline
from mpl_toolkits.mplot3d import Axes3D
class Rosenbrock():
def __init__(self):
self.x1 = np.arange(-100, 100, 0.0001)
self.x2 = np.arange(-100, 100, 0.0001)
#self.x1, self.x2 = np.meshgrid(self.x1, self.x2)
self.a = 1
self.b = 1
self.newton_times = 1000
self.answers = []
self.min_answer_z = []
# 准备数据
def data(self):
z = np.square(self.a - self.x1) + self.b * np.square(self.x2 - np.square(self.x1))
#print(z.shape)
return z
# 随机牛顿
def snt(self,x1,x2,z,alpha):
rand_init = np.random.randint(0,z.shape[0])
x1_init,x2_init,z_init = x1[rand_init],x2[rand_init],z[rand_init]
x_0 =np.array([x1_init,x2_init]).reshape((-1,1))
#print(x_0)
for i in range(self.newton_times):
x_i = x_0 - np.matmul(np.linalg.inv(np.array([[12*x2_init**2-4*x2_init+2,-4*x1_init],[-4*x1_init,2]])),np.array([4*x1_init**3-4*x1_init*x2_init+2*x1_init-2,-2*x1_init**2+2*x2_init]).reshape((-1,1)))
x_0 = x_i
x1_init = x_0[0,0]
x2_init = x_0[1,0]
answer = x_0
return answer
# 绘图
def plot_data(self,min_x1,min_x2,min_z):
x1 = np.arange(-100, 100, 0.1)
x2 = np.arange(-100, 100, 0.1)
x1, x2 = np.meshgrid(x1, x2)
a = 1
b = 1
z = np.square(a - x1) + b * np.square(x2 - np.square(x1))
fig4 = plt.figure()
ax4 = plt.axes(projection='3d')
ax4.plot_surface(x1, x2, z, alpha=0.3, cmap='winter') # 生成表面, alpha 用于控制透明度
ax4.contour(x1, x2, z, zdir='z', offset=-3, cmap="rainbow") # 生成z方向投影,投到x-y平面
ax4.contour(x1, x2, z, zdir='x', offset=-6, cmap="rainbow") # 生成x方向投影,投到y-z平面
ax4.contour(x1, x2, z, zdir='y', offset=6, cmap="rainbow") # 生成y方向投影,投到x-z平面
ax4.contourf(x1, x2, z, zdir='y', offset=6, cmap="rainbow") # 生成y方向投影填充,投到x-z平面,contourf()函数
ax4.scatter(min_x1,min_x2,min_z,c='r')
# 设定显示范围
ax4.set_xlabel('X')
ax4.set_ylabel('Y')
ax4.set_zlabel('Z')
plt.show()
# 开始
def start(self):
times = int(input("请输入需要随机优化的次数:"))
alpha = float(input("请输入随机优化的步长"))
z = self.data()
start_time = time.time()
for i in range(times):
answer = self.snt(self.x1,self.x2,z,alpha)
self.answers.append(answer)
min_answer = np.array(self.answers)
for i in range(times):
self.min_answer_z.append((1-min_answer[i,0,0])**2+(min_answer[i,1,0]-min_answer[i,0,0]**2)**2)
optimal_z = np.min(np.array(self.min_answer_z))
optimal_z_index = np.argmin(np.array(self.min_answer_z))
optimal_x1,optimal_x2 = min_answer[optimal_z_index,0,0],min_answer[optimal_z_index,1,0]
end_time = time.time()
running_time = end_time-start_time
print("优化的时间:%.2f秒!" % running_time)
self.plot_data(optimal_x1,optimal_x2,optimal_z)
if __name__ == '__main__':
snt = Rosenbrock()
snt.start()
请输入需要随机优化的次数:100
优化的时间:8.10秒!
本文电子版 后台回复 优化算法 获取
“整理不易,点赞三连↓