目录
前言
常见概念
常见算法
算法分类
比喻说明
前言
最优化理论研究的问题是判定给定目标函数的最大值 (最小值) 是否存在, 并找到令目标函数取到最大值 (最小值) 的数值.
人工智能问题最后都会归结为一个优化问题的求解: 在复杂环境与多体交互中做出最优决策.
最优化算法可能找到全局最小值, 也可能找到局部最小值, 理想情况下, 最优化算法的目标就是找到全局最小值.
当目标函数的输入参数较多, 解空间较大时, 绝大多数算法都不能满足全局搜索, 只能求出局部最小值.
人工智能和深度学习的应用, 只要目标函数的取值足够小, 就可以把这个值当作最小值使用, 作为对性能和复杂度的折中.
常见概念
目标函数(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)
常见算法
梯度下降法(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