求解大规模机器学习问题的优化方法

摘要

科学技术的飞速发展为数据采集带来了便利，各行各业都产生了大量的高维数据.但是，这些数据往往包含大量的冗杂信息，如何处理这些数据，将数据信息进行有效分类，并剔除冗余，进一步从中提取有用的信息已成为机器学习中最基本也是最重要的问题. 而机器学习中很多问题的求解最终都归结为求解大规模优化问题. 本文基于机器学习这一热点话题，研究“正则化项+损失函数”的机器学习算法框架.我们将上述问题分两类情况进行讨论，即光滑经验损失问题和结构风险最小化问题两种情形. 对这两类问题的求解，本文主要使用随机优化方法，具体安排如下： 对于光滑的经验损失函数问题，我们在已有随机梯度法的基础上进行改进. 由于随机梯度法受噪声梯度估计的影响，当使用固定步长时，它无法收敛到最优解，即使取递减步长，它也只能满足缓慢的次线性收敛. 对此，我们探讨了两种方法. 其一，我们探究了一种随机梯度降噪法随机受控的随机梯度法(SCSG). 该方法在随机方差减少梯度(SVRG)方法的基础上使用自动参数调整系统. 其收敛性与SVRG方法相似，但其计算复杂度较SVRG大大降低，而且所需的存储空间也大大减少. 其二，我们探究了一种修正的随机L-BFGS方法，该方法在随机牛顿法的基础上，用近似二阶导数信息处理非线性和病态的目标优化，并采用经典的BFGS校正公式对Hessian逆矩阵的近似矩阵进行修正，它结合了大规模优化中的有限记忆思想和随机梯度降噪法的思想，是随机拟牛顿方法的一种变式. 该方法大大降低了内存空间的存储，有较好的稳定性与收敛性. 我们通过理论分析得出该算法满足线性收敛速率. 对于结构风险最小化问题，我们通过考虑将正则化项作为一个独立体处理的思想，将其分情况研究. 当损失项光滑但正则化项非光滑时，我们提出邻近随机L-BFGS算法，将问题分为光滑与非光滑两部分处理，对于光滑损失项，我们用随机L-BFGS处理，对非光滑部分引入邻近算子，进行邻近点迭代，两步迭代交替进行. 对此，我们给出了理论分析，并得出算法满足线性收敛速率. 而当损失函数非光滑时，我们提出带有加权平均的随机次梯度镜面下降算法，该方法的主要创新之处是平均权重的选择，它不是人为给定而是由算法迭代产生. 这样随着迭代进行，权值会相应的调整，从而达到自适应的效果. 同样，我们对该算法的收敛性进行了理论分析，并验证了算法的收敛性.

目录

第一个书签之前

摘要

Abstract

第一章 绪论

1.1 研究背景

1.2 研究目的及意义

1.3 国内外研究现状

1.4 内容结构安排

2.1大规模机器学习问题的基本模型

2.2 相关概念

2.3 基本方法简述

2.3.1 批梯度与随机梯度下降法

2.3.2 随机牛顿法

第三章 光滑经验损失问题的优化方法

3.1 随机梯度法的降噪方法

3.1.1 SVRG方法的基本思想

3.1.2 随机受控的随机梯度(SCSG)方法的导出

3.2 修正的随机L-BFGS方法

3.2.1 拟牛顿法的基本原理

3.2.2 随机L-BFGS方法的导出

3.2.3 随机L-BFGS方法的收敛性分析

3.3 数值分析及分析

3.3.1 SCSG方法的数值实验比较与分析

3.3.2 SL-BFGS方法的数值实验比较与分析

第四章 结构风险最小化问题的优化方法

4.1 邻近随机L-BFGS方法

4.1.1 邻近随机L-BFGS算法的基本思想

4.1.2 邻近随机L-BFGS算法的收敛性分析

4.1.3 小结

4.2 随机次梯度镜面下降方法

4.2.1 镜面下降算法的基本原理

4.2.2 随机镜面下降算法的基本思想

4.2.3 算法的收敛性分析

4.2.4 小结

第五章 总结与展望

5.1 工作总结

5.2 展望

参考文献

致谢

附录：攻读硕士学位期间的研究成果

原 创 性 声 明