面向在线学习的优化理论及算法研究

摘要

信息发布方式的不断发展以及云计算、物联网等技术的兴起推动人类社会迈进了大数据时代。大数据时代，数据连续不断、来源众多、价值密度低，数据处理工具要兼顾实时性、可在线处理和在线分析。在线学习技术采用流式计算模式，操作流程简洁快速，学习复杂度低，模型更新速度快，为大数据特别是流式数据的处理提供了一种强有力的工具。在数据可实时处理的前提下，模型的泛化能力（如学习误差、模型空间复杂度）也是研究的重点。正则化技术由于具有模型空间控制功能、可解决建模过程中出现的过拟合等问题，是机器学习研究的一条主轴。 目前，大规模数据的学习问题广泛存在，为这些问题量身打造而设计出的简约模型和有效算法将很有前景，也十分必要。为处理大规模数据的学习问题，本论文主要在正则化框架下对在线学习技术进行了进一步的研究和探索，提出了若干在线学习算法，并应用于数据分类、预测、联合分析、图像处理等问题。论文的主要工作与创新点概括如下: (1)提出了基于耦合线性化的在线学习算法。针对目标函数为非光滑的经验风险极小化问题，设计了一种耦合线性化的在线交替方向乘子算法。该算法操作简洁、易于实施。首先，将原问题转化为与之等价的具有可分离结构的等式约束优化问题;接着，对约束优化问题的拉格朗日函数进行分解，得到三个子问题;然后，通过变量固定技巧对子问题分别优化求解。算法每次迭代实施三次线性化操作，求解过程不涉及矩阵求逆运算，且每一步都能得到一个闭式解。通过详尽的理论分析得到了算法的Regret界及收敛速度:对一般的凸学习问题而言，在适当的条件下，其收敛速度为O(1/√T);对于强凸学习问题，其收敛速度为O((log T)/T)，其中T表示样本的个数。与当前一些相关算法的对比实验验证了所提算法的可行性和有效性。 (2)提出了基于谱梯度下降的在线学习算法。针对目标函数可表示为大量组件函数的平均，且每个组件函数都是光滑的这样一类问题，设计了一种随机谱梯度下降的在线学习算法。与传统的随机梯度下降算法不一样的是，该算法利用Rayleigh商收集目标函数的二阶信息，构造海塞矩阵逆的近似，从而设计了新的学习步长。算法每次迭代所产生的搜索方向具有下降性，现有理论保证了算法收敛。所提算法可以看成是谱梯度方法从确定性优化到随机优化的延伸。在基准数据集上的实验结果表明所提算法是可行的、有效的。 (3)提出了面向在线学习的加权多任务特征选择算法。针对特征选择问题中变量稀疏性增强问题，设计了两种加权的多任务特征选择模型，同时给出了求解模型的在线学习算法。据我们所知，该工作是第一个研究在线加权多任务特征选择的工作。这里提出的在线学习算法的优势包括:i）可以应用于训练数据顺序获得的情形，可以在任意时刻执行训练过程;ii)可以处理任意数目和任何维度的数据;iii）推导出更新相应模型权值的闭式解，模型训练相对高效。算法每次迭代在最差情况下的时间复杂度和存储开销成本都是O(N×Q)，其中N代表特征的维度，Q表示任务的个数。此外，分析了算法的Regret界，保证了算法的收敛性。实验表明，在线的加权多任务学习算法能得到更稀疏的解，同时拥有更快的收敛速度。 (4)提出了面向在线学习的字典学习算法并应用于图像去噪。针对基于稀疏表示的大规模图像去噪问题，利用噪声不能在任何字典上稀疏表示的特性，设计了一种小批量K-sparse字典学习算法。考虑具有l0范数约束的K-sparse优化模型，利用交替优化的方式对模型进行求解。所提算法每次迭代只使用少量的训练样本进行编码和字典更新。具体而言，在稀疏编码阶段，采用迭代硬阈值策略更新表示系数;在字典学习阶段，则采用投影梯度下降策略进行字典更新。具体的操作流程是先从含噪图像中提取出大量的子图像作为训练样本，接着采用分块学习技术得到一个冗余的字典，然后通过含噪图像在该字典上的表示系数实现去噪。实验表明，与现有的一些算法相比，所提算法具有较好的性能，不仅可以更好地去除图像中的噪声、提升图像的视觉质量，而且收敛速度快、计算效率高。

目录

声明

摘要

1 绪论

1．1 选题背景与意义

1．2在线学习

1．2．1 监督学习与正则化

1．2．2在线凸规划

1．3国内外研究现状

1．4本文研究内容

1．4．1课题来源

1．4．2研究内容安排

2 基于耦合线性化的在线学习算法

2．1 引言

2．2 批处理ADMM框架，最优性条件及残差

2．2．1 框架

2．2．2 最优性条件及残差

2．3在线耦合线性化交替迭代算法

2．3．1 CLAIM

2．3．2 Regret和收敛性分析

2．4实验分析

2．4．1 实验一

2．4．2 实验二

2．5 CLAIM算法的扩展

2．5．1 伸缩CLAIM

2．5．2 带重启动机制的伸缩CLAIM

2．5．3 扩展CLAIM的性能比较

2．6本章小结

3 基于随机谱梯度的在线学习算法

3．1 引言

3．2 随机谱梯度下降方法

3．2．1 相关知识

3．2．2算法

3．3 实验分析

3．3．1 问题、数据集描述及算法参数设置

3．3．2 实验方法与结果

3．4本章小结

4面向在线学习的加权多任务学习算法

4．1 引言

4．2 准备知识

4．3加权多任务学习

4．3．1 多任务学习问题设置

4．3．2加权多任务学习模型

4．3．3 加权多任务学习模型的在线优化

4．3．4 Regret和收敛性分析

4．3．5 实验分析

4．4 面向特征与任务共选择的加权多任务学习

4．4．1 加权特征与任务共选择模型

4．4．2 加权特征与任务共选择模型的在线优化

4．4．3 Regret和收敛性分析

4．4．4 实验分析

4．5 多任务学习模型的进一步探讨

4．6本章小结

5 面向在线学习的K-sparse字典学习算法

5．1 引言

5．1．1 稀疏表示的数学模型

5．1．2稀疏编码

5．1．3 字典学习

5．1．4 在线字典学习

5．2 基于分块的K-sparse字典学习算法

5．2．1 算法概述

5．2．2 编码更新

5．2．3 字典更新

5．3 实验分析

5．3．1数据集与实验设置

5．3．2 算法性能评估

5．4本章小结

6总结与展望

6．1本文工作总结

6．2未来工作展望

致谢

参考文献

附录