【作者】 薛伟；

【导师】 张文生；

【作者基本信息】 南京理工大学 ， 计算机科学与技术， 2017， 博士

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

【Abstract】 The continuous development of modes of information dissemination and the rise of technologies such as cloud computing and internet of things make the human society enter the era of big data.In this era,due to the characteristics of the continuous and numerous sources as well as low density value of big data,the tools for data processing should be real-time,and they can realize not only the online processing but also the online analysis.Online learning technology uses stream computing model,leading to simple and fast operational procedure,low learning complexity and fast model update rate.All these advantages of online learning make it become a promising tool for big data especially for streaming data.On the premise that data can be processed in real time,the generalization ability of models(e.g.,learning error,complexity of the model space)is also the emphasis of current research.Regularization is a dominant theme in machine learning due to its remarkable ability to address problems like model space controlling and overfitting occurred in the process of modeling.As learning problems widely exist in large-scale data,developing parsimonious models and efficient algorithms are promising and necessary for these problems.For the purpose of handling large-scale learning problems,this dissertation has further studied and explored online learning technology within the framework of regularization.Specifically,we have put forward several online learning algorithms,which have been applied in many problems,such as data classification,prediction,conjoint analysis and image processing.The main results and the innovation of this dissertation are summarized as follows.(1)We propose a coupled linearized online alternating direction method of multipliers,which aims to solve nonsmooth empirical risk minimization problems.The proposed algorithm operates simply,and it is easy to implement.We first transform the primal problem into an equivalent constrained minimization problem with a sepa-rable structure.Then,we split the augmented Lagrangian function of the constrained optimization problem and minimize the resulting subproblems with one variable by fixing another one.This method is easy to execute without calculating matrix inversion by implementing three linearized operations per iteration,and at each iteration we can obtain a closed-form solution.Through detailed theoretical analysis,we obtain the regret bound of the proposed algorithm and its convergence rate.Under some mild conditions,the proposed algorithm can achieve O(1/(?))convergence rate for convex learning problems and O((log T)/(?))for strongly convex learning,where T is the num-ber of samples.The comparative experiments with several current related methods are reported,which demonstrate the feasibility and effectiveness of our approach.(2)We propose an online learning algorithm,named Stochastic Spectral Gradient Descent(S~2GD),for a type of learning problem whose objective function is formulat-ed as an average of a large number of smooth component functions.The difference between the S~2GD algorithm and the traditional stochastic gradient descent(SGD)algorithm is that S~2GD employs the Rayleigh quotient to collect second-order information to construct Hessian inverse approximations,thus designing a new learning stepsize.At each iteration,the generated search direction guarantees descent property.The existing conclusion indicates that the S~2GD method is of convergence.Actually,the S~2GD algorithm can be viewed as an approach that extends the spectral gradient method working in deterministic setting to stochastic setting.Experimental results on standard data sets are reported to demonstrate the feasibility and effectiveness of the proposed algorithm.(3)We propose two weighted multi-task feature selection models to enhance the sparsity of the learning variables and provide two online algorithms to solve these models,respectively.To the best of our knowledge,this work is the first research on the online weighted multi-task feature selection.The main advantages of our approach is that i)it can be applied to the situation that the training data appears sequentially;consequently,the training procedure can be conducted at any time;ii)it can process the data up to any size with any number of features;iii)training the learning model is very efficient because we can derive closed-form solutions to update the weights.The worst-case bounds of the time complexity and the memory cost of this algorithm at each iteration are both in O(N × Q),where N is the number of feature dimensions and Q is the number of tasks.Theoretical analysis for the regret bound of the proposed algorithms is presented,which also guarantees their convergence rates.Experiments indicate that the proposed algorithms can yield better performance,e.g.,in terms of convergence speed and sparsity.(4)By using the characteristic that noise can not be represented sparsely over any dictionary,we propose an online dictionary learning algorithm,named Mini-batch K-sparse Dictionary Learning(MKDL),for large-scale image denoising problems based on sparse representation.We consider the K-sparse optimization model with l0 norm constraint,and solve the proposed model by using alternative optimization.At each iteration of MKDL,only a small number of training samples are used to encode and update dictionary.More precisely,iterative hard thresholding and projected gradient descent schemes are employed to optimize the two above-mentioned stages,respective-ly.The concrete operation flow includes three aspects:i)adding noise to the clean image;ii)extracting a large number of sub-images(samples)from the noisy image to learn a redundant dictionary;iii)using the representation coefficients of the noisy image over the learned dictionary to achieve the noise reduction.Experimental results on image denoising have much better performance than some existing dictionary learning algorithms,which validates the effectiveness of the proposed approach in convergence speed and denoising quality.更多还原