前言

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

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

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

常见概念

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

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

  • 局部最小值(local mininum)
    局部最小值只是比所有邻近点的函数值都小

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

  • 导数
    微积分中重要基础概念,是函数的局部性质,又名微商、导函数值,一个函数在某一点的导数描述了这个函数在这一点也附近的变化率。 概念如下

当函数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)的信息
    曲率影响的是目标函数的下降速度。曲率为正,目标函数会比梯度下降法预期下降得更慢,曲率为负反之。

  • 无约束优化(unconstrained optimization)
    对自变量的取值没有限制 。例如:梯度下降法(gradient descent)

  • 约束优化(constrained optimization)
    对x变量取值限制在特定的集合内。例如:线性规划(linear programming)

常见算法

  • 梯度下降法
    直观地说,就是沿着目标函数下降最快的方向寻找最小值,
    举例:爬山时沿着坡度最陡的路径寻找山顶。
    在数学上,梯度的方向是目标函数导数(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)

神经网络算法就是一类启发式算法,模拟的是大脑中神经元竞争和协作的机制。

比喻说明

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

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

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

版权声明:本文为chenqionghe原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/chenqionghe/p/12566709.html