最优化理论——机器学习基础

2019/04/10 10:10
阅读数 29

[toc]

前言

最优化理论研究的问题是判定给定目标函数的最大值(最小值)是否存在,并找到令目标函数取到最大值(最小值)的数值。

人工智能问题最后都会归结为一个优化问题的求解:在复杂环境与多体交互中做出最优决策。 最优化算法可能找到全局最小值,也可能找到局部最小值,理想情况下,最优化算法的目标就是找到全局最小值。

当目标函数的输入参数较多、解空间较大时,绝大多数算法都不能满足全局搜索,只能求出局部最小值。 人工智能和深度学习的应用,只要目标函数的取值足够小,就可以把这个值当作最小值使用,作为对性能和复杂度的折中。

常见概念

目标函数(objective function)

目标函数就是实现最小化或最大化的目标函数,也被称为评价函数。

收敛(convergence)

指经过多步迭代之后得出的数值不应该无限的增大,而是趋于某个数值,

局部最小值(local mininum)

局部最小值只是比所有邻近点的函数值都小

全局最小值(global mininum)

比定义域内所有其他点的函数值都小,包括了和所有的局部最小值对比

导数(derivative)

微积分中重要基础概念,是函数的局部性质,又名微商、导函数值。 导数在几何中可以求切线,在代数中可求瞬时变化率,在物理中可求速度、加速度。 一个函数在某一点的导数描述了这个函数在这一点也附近的变化率。 概念如下 >当函数y=f(x)的自变量x在一点x0上产生一个增量Δx时,函数输出值的增量Δy与自变量增量Δx的比值在Δx趋于0时的极限a如果存在,a即为在x0处的导数,记作f'(x0)或df(x0)/dx。

一阶导数(first-order derivative)

描述的是目标函数随输入的变化而变化

二阶导数(second-order derivative)

描述的是一阶导数随输入的变化而变化,提供了关于目标函数曲率(curvature)的信息

梯度(gradient)

梯度的本意是一个向量,表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该点处沿着该方向(此梯度的方向)变化最快,变化率最大(为该梯度的模)。

曲率影响的是目标函数的下降速度。曲率为正,目标函数会比梯度下降法预期下降得更慢,曲率为负反之。

无约束优化(unconstrained optimization)

对自变量的取值没有限制 。例如:梯度下降法(gradient descent)

约束优化(constrained optimization)

对x变量取值限制在特定的集合内。例如:线性规划(linear programming)

常见算法

梯度下降法(gradient descent)

直观地说,就是沿着目标函数下降最快的方向寻找最小值, 举例:爬山时沿着坡度最陡的路径寻找山顶。 在数学上,梯度的方向是目标函数导数(derivative)的反方向 当输入为向量时,目标函数的图像就变成了高维空间的曲面,这时的梯度就是垂直于曲面等高线并指向高度增加方向的向量,要上目标函数以最快的速度下降,就要让自变量在负梯度的方向移动 另一个重要的是步长,也就是每次更新f(x)时x的变化值。较小的步长会导致收敛过程较慢,步长过大可能会导致一步迈过了最小值点。 以上是针对单个样本的梯度下降法,当可用的训练样本有多个时,样本的使用批处理模式和随机梯度下降法模式。

批处理模式梯度下降法(batch processing)

计算出每个样本上目标函数的梯度,再将不同样本的梯度进行求和,求和的结果作为本次更新中目标函数的梯度。

随机梯度下降法(stochastic gradient descent)

在每次更新中只使用一个样本,下一次更新中使用另一样本,在不断迭代更新过程中实现对所有样本的遍历。在训练集规模较大时,随机梯度下降法的性能更好。 把求解最优化问题想象成爬山,随机梯度下降法,就是每走一步换一个方向。

牛顿法(Newton's method)

牛顿法是将二阶导数引入优化过程,对二阶近似后的目标函数求导,并让导数为0,得到向量表示的就是下降最快的方向,牛顿法比梯度下降法快收敛速度更快

算法分类

线性搜索法(line search)

寻找最小值是先确定方向,再确定步长,需要使用目标函数的一阶导数和二阶导数

置信域算法(trust region)

寻找最小值是先确定步长,再确定搜索方向。以步长为参数划定一个区域,再在这个区域内寻找最快下降的方向。

启发式算法(heuristics)

灵感来源于20世纪50年代诞生的仿生学,将生物进化等自然现象的机理应用于现实世界复杂问题的优化之中,并取得了不俗的效果。核心是大自然中的“优胜劣汰”的生存法则,在算法的实现中添加了选择和突变等经验因素。

启发式算法的实例包括

  • 模拟生物进化规律的遗传算法(genetic algorithm)
  • 模拟统计物理中固体结晶过程的模拟退火算法(simulated annealing)
  • 模拟低等运动产生集群智能的蚁群算法(ant colony optimization)

启发式算法其实也是搜索,是依赖经验的碰运气式的搜索,相比之下,基于梯度的这些方法更像是地毯式搜索,两者相结合的话,就是在搜索效率和解的最优性上做些折中。 神经网络算法就是一类启发式算法,模拟的是大脑中神经元竞争和协作的机制。

比喻说明

梯度下降:找出最优的路到达山顶

以山峰为例,全局最小值对应着山脉中最高的顶峰。 找到这个顶峰最好的办法是站在更高的位置上,将所有的山峰尽收眼底,再在其中找到最高的一座。 但是我们没有这样的上帝视角,都是在山脚下,一步一步地寻找着附近的高峰,但是受视野的限制,最终找到的可能只是方圆十里之内的顶峰(局部最小值)

收敛:体重称算法

在体重秤上称量时,当人站上去时指针就开始抖动,抖动幅度越来越小,最后基本稳定在一个值,读取这个数字即可。 假设体重秤称量是有算法控制的,那么这个摆动几下很快就能稳定在一个值的就是收敛性比较快(比较好)的算法;要摆动很久才能稳定的就是收敛性比较慢(比较差)的算法; 如果摆幅随着时间的推移反而越来越大,那收敛性就非常不好,通常就没有解。

原文出处:https://www.cnblogs.com/chenqionghe/p/12566709.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部