【数学应用】机器学习常用最优化算法小结

本文主要是从通俗直观的角度对机器学习中的无约束优化算法进行对比归纳,详细的公式和算法过程可以看最后附的几个链接,都是干货。

机器学习基本概念

统计机器学习整个流程就是:基于给定的训练数据集,由实际需求,需要解决的问题来选择合适的模型;再根据确定学习策略,是最小化经验风险,还是结构风险,即确定优化目标函数;最后便是采用什么样的学习算法,或者说优化算法来求解最优的模型。参照《统计机器学习方法》所讲,统计机器学习(特指有监督学习)的三要素为:

1)模型

模型是指基于训练数据集,所要学习到的概率分布或者决策函数,比如线性模型(线性回归,逻辑回归等),非线性模型(决策树,神经网络)。还有个重要概念,就是模型的假设空间。比如需要学习的决策函数为线性函数,则所有的线性函数构成了该模型的假设空间。

2) 策略

确定了需要学习哪种模型,接下来任务的便是从该类模型的假设空间中选择出最优的模型。模型的优劣需要通过一定的准则来评价,直观来讲,选用模型的预测误差作为评判标准比较合理。而不同的模型基于模型原理或解优化的便利性,往往对应着不同的误差函数,也叫损失函数,如:

-平方损失函数,对应线性回归;

-对数损失函数,对应logistic回归;

-指数损失函数,对应boosting;

-hinge损失函数,对应SVM;

这里所说的策略就是指:当目标函数仅含有损失函数时,对应经验风险最小化策略,即选择的最优模型在训练集上的平均损失最小;而当目标函数由损失函数项和正则化项构成时,对应结构风险最小化策略,即选择的最优模型不仅在训练集上平均误差比较小,同时在测试集上也能有不错的表现,也就是说得到的模型 要有较好的泛化能力。

当样本集数目足够大时,由于样本的覆盖量足够大,能较好地体现实际数据的分布,直接采用经验风险最小化策略就能保证有很好的学习效果;但当样本 容量不够充足时,并不能很好的体现真实的数据分布,因此过于追求减小模型在训练集上的误差,就容易导致“过拟合”现象,即学习到的模型在未知测试数据上效果不理想。

3)算法

算法便是对应上面最后一步最优模型的具体求解方法,称为最优化算法。

优化算法小结

在机器学习模型求解过程中,一般采用迭代法。常见的迭代优化算法有梯度下降,牛顿法,拟牛顿,高斯-牛顿,BFGS,L-BFGS。。。

1)梯度下降

梯度下降也称为最速下降法,属于一阶优化算法。我们知道,梯度方向对应着函数值变化最快的方向,而目标是寻找局部最小值,若当前初始点的梯度值为正时,最小值应该位于该点的左边,则应该给当前点坐标加上一个负值,故参数的调整量与梯度值的符号是相反的。故,沿着当前点梯度的负方向以合适的步长更新至下一个参数状态是合理的,而且保证以较快速度收敛到局部最小值。而当优化函数为凸函数时,找到的局部最小值就是全局最小值,该点对应的参数集便是全局最优解。

2)牛顿法

牛顿法属于二阶优化算法,来源于数值分析中对方程f(x)=0求根的近似解法,即对f(x)在当前点x0进行一阶泰勒展开式:

f(x)=f(x0)+(x-x0)f’(x0)+O(x-x0)

令展开式为0即可得到增量(x-x0)。在目标函数J(x)的最优化过程中,试图求解J’(x)=0的解,J’(x)便对应上式中的f(x)。这里重点讲下个人对牛顿法的直观理解,函数局部最小值对应的梯度为0,即J’(x)=0。牛顿法的核心思想是采用近似、迭代求解的方式,就是用一个简单的二次曲面模型(或者称抛物线模型,为严格凸的)来拟合当前参数点所对应的局部误差曲面,并且以该二次近似曲面极小值对应的参数增量作为下一次的参数更新量。这样的好处是不仅考虑了当前点的梯度方向,同时考虑了更新后的点的梯度情况,对于比简单的梯度下降法更加快速和稳定。

3)高斯-牛顿法

高斯-牛顿法是一种针对模型优化策略为非线性最小二乘法(LMA)时所设计的特定最优化算法。在上述的牛顿法中,由于需要求解函数Hessian矩阵以及其逆矩阵,不仅计算量大,且并不能保证Hessian矩阵一定是正定的(即不能保证参数更新的方向是梯度下降的)。因此,在高斯牛顿法中,用一阶导Jacobian矩阵的内积来近似二阶导hessian矩阵。

4)拟牛顿法

拟牛顿法的提出就是为了解决牛顿法中求解Hessian矩阵计算量大以及Hessian矩阵可能不可逆的问题,通过建立拟牛顿方程可以方便地获得一个Hessian矩阵的近似矩阵,该矩阵必定为正定矩阵。

5)BFGS算法

上述拟牛顿法中,仍然涉及到近似矩阵的求逆过程,计算量仍然很大。BFGS算法就是进一步对上述的近似矩阵的逆求取一个近似矩阵,求取的过程也是通过建立一系列等式展开的。

6)L-BFGS算法

BFGS法比较适合于解决参数规模适中的无约束最优化问题,而当参数维度特别大时,由于上述获得的近似矩阵随着迭代更新次数的增加将越来越变得稠密,便将导致存储空间不足和计算复杂度过高的问题。L-BFGS算法正是为了解决以上问题提出来的,为了减少矩阵所占的存储空间,L-BFGS利用最近几次迭代过程中的曲率信息来构建当前迭代所需的Hessian近似矩阵;而为了减少计算量,L-BFGS则是首先给当前迭代过程一个Hessian近似矩阵的初始估计H0,在利用前面几代所保存的曲率信息对H0进行修正即得到当前迭代过程的Hessian近似矩阵。

原文发布于微信公众号 - 数据科学与人工智能(DS_AI_shujuren)

原文发表时间:2015-11-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

入门 | 神经网络训练中,Epoch、Batch Size和迭代傻傻分不清?

选自Medium 机器之心编译 参与:刘晓坤 你肯定经历过这样的时刻,看着电脑屏幕抓着头,困惑着:「为什么我会在代码中使用这三个术语,它们有什么区别吗?」因为它...

447110
来自专栏Python数据科学

【算法面经】:机器学习面试算法梳理

机器学习算法面试一直是大家比较苦恼的事情,各种算法经常弄混,或者无法透彻理解。分享一篇非常好的机器学习算法面试干货总结,梳理算法原理,优缺点。

15020
来自专栏PPV课数据科学社区

【学习】数据挖掘中分类算法小结

数据仓库,数据库或者其它信息库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识。分类与预测是两种数据分析形式,它们可以用来抽取能够描述重要数据集...

332110
来自专栏量子位

一文看懂迁移学习:怎样用预训练模型搞定深度学习?

瀚宸 编译自 Analytics Vidhya 量子位 出品 | 公众号 QbitAI 引言 跟传统的监督式机器学习算法相比,深度神经网络目前最大的劣势是什么?...

1.1K50
来自专栏量子位

一文看懂自动驾驶中应用的机器学习算法

安妮 唐旭 编译自 KDnuggets 量子位出品 | 公众号 QbitAI 机器学习算法已经被广泛应用于自动驾驶各种解决方案,电控单元中的传感器数据处理大大提...

35970
来自专栏用户2442861的专栏

机器学习&数据挖掘笔记_16(常见面试之机器学习算法思想简单梳理)

http://www.cnblogs.com/tornadomeet/p/3395593.html

12210
来自专栏深度学习入门与实践

【深度学习系列】用PaddlePaddle和Tensorflow实现GoogLeNet InceptionV2/V3/V4

上一篇文章我们引出了GoogLeNet InceptionV1的网络结构,这篇文章中我们会详细讲到Inception V2/V3/V4的发展历程以及它们的网络结...

227100
来自专栏智能算法

常见面试之机器学习算法思想简单梳理

来源: tornadomeet 的博客(@tornadomeet) 链接: www.cnblogs.com/tornadomeet/p/3395593.htm...

391100
来自专栏目标检测和深度学习

推荐|改变你对世界看法的五大计算机视觉技术!

计算机视觉是当前最热门的研究之一,是一门多学科交叉的研究,涵盖计算机科学(图形学、算法、理论研究等)、数学(信息检索、机器学习)、工程(机器人、NLP等)、生物...

29880
来自专栏AI科技评论

学界 | 美图云联合中科院提出基于交互感知注意力机制神经网络的行为分类技术 | ECCV 2018

以往注意机制模型通过加权所有局部特征计算和提取关键特征,忽略了各局部特征间的强相关性,特征间存在较强的信息冗余。为解决此问题,来自美图云视觉技术部门和中科院自动...

12820

扫码关注云+社区

领取腾讯云代金券