一种具有遗忘特性的在线学习算法框架

基于凸优化中的对偶理论,提出了一种具有遗忘特性的在线学习算法框架。其中,Hinge函数的Fenchel对偶变换是将基本学习问题由批量学习转化为在线学习的关键。新的算法过程是通过以不同方式提升含有约束变量的对偶问题实现的:(1)梯度提升;(2)贪婪提升。回顾了以往的相关研究工作,并指出了与之的区别与联系。人造数据集和真实数据集上的实验结果证实了算法框架的有效性。算法可以很好地处理数据流中的分类面漂移问题,为设计和分析新的在线学习算法提供了一个新的思路。

An online learning algorithmic framework with forgetting property

Based on the notion of duality in convex optimization, we propose a novel online learning algorithmic framework with forgetting property. The Fenchel conjugate of hinge functions is a key to transfer the basic learning problem from batch to online. New online learning algorithms are derived by different dual ascending procedures: (1) gradient ascent; (2) greedy ascent. We also recap and draw connections to earlier works. Detailed experiments on synthetic and real-world datasets verify the effectiveness of our approaches. An important conclusion is that our derived online learning algorithms can handle the settings where the target hypothesis is not fixed but drifts with the sequence of examples. This paper paves a way to the design and analysis of online learning algorithms.