QCon全球软件开发大会让你与150+位一线国内外技术专家深度交流,购票立减 ¥880 了解详情
写点什么

一种针对非线性数据的局部在线学习方法

2019 年 9 月 05 日

一种针对非线性数据的局部在线学习方法

小蚂蚁说:

亚太知识发现和数据挖掘会议(PAKDD,Pacific-Asia Conference on Knowledge Discovery and Data Mining)是知识发现和数据挖掘(KDD)领域的国际领先会议。它为研究人员和行业从业人员提供了一个国际论坛,分享他们的所有 KDD 相关领域的新想法,原创研究成果和实践开发经验,包括数据挖掘,数据仓库,机器学习,人工智能,数据库,统计学,知识工程,可视化,决策系统和新兴应用程序。

本文是蚂蚁金服录用于 2018PAKDD research track 长论文《A Local Online Learning Approach for Non-linear Data》(录取率仅为 10%)的简要介绍。


由于在线学习(online learning)的高效性和可扩展性使其成为解决超大规模数据的实时学习问题的热门选择。


现阶段大多数在线学习方法都是基于全局模型的方法,即使用一个全局模型来处理所有数据,而且大多都假设流入的数据都是线性可分的。然而这种假设在实践中并非总是如此,因此基于局部在线学习框架被提出来解决非线性可分的问题。并且这种方法无需引入 kernel, 从而降低了模型的复杂度。之前一些局部在线学习框架中的模型的参数大多数仅仅利用了特征的一阶信息,因此将严重限制分类器的性能。为了提高提高分类器的性能,许多二阶信息的模型被提出,比如典型的二阶在线学习算法 SCW(Soft Confidence Weighted)。


受到以上信息的启发,我们提出了一个基于 SCW 算法的局部(Local)在线学习(Onlinelearning)算法(SCW-LOL)。该算法将单个 SCW 分类器扩展到多个 SCW 分类器,组成一个多分类器模型。我们还研究了各个分类器之间的更新和预测关系以及算法的理论预测误差上界。广泛的实验结果表明,我们提出所提出的 SCW-LOL 算法是收敛的,并且相对目前主流的在线学习方法,几乎在所有数据集都能达到最佳效果。


近年来,在线学习算法在数据挖掘和机器学习中扮演越来越重要的角色。与通过学习整个训练数据产生最佳预测的传统机器学习技术相反,在线学习模型通过流式数据,每次只处理一个实例,根据预测结果实时更新当前模型,一直重复循环。由于在线学习不需要跟踪任何历史示例,因此避免了昂贵的训练成本并减少了大量的内存消耗。同时在线学习能实时将最新的数据反馈至模型中,减少了模型的延时性。这些优势使其在工业界有较多应用,例如搜索排序、协作过滤和异常检测等。


很早就有一些在线学习算法被提出和应用,如 Perceptron Algorithm 和 Passive Aggressive(PA)算法。由于一阶在线学习算法仅仅使用一阶信息,往往称这些算法为一阶在线学习算法。后来又出现了大量的二阶在线学习算法来进一步提高分类器的性能。最具代表性有 Confidence Weight(CW),Adaptive Regularization of Weights(AROW)和 Soft Confidence Weight(SCW-I,SCW-II)算法等。二阶在线学习使用了二阶信息,其效果往往要优于一阶在线学习模型效果。一阶和二阶在线学习算法都假设传入的实例几乎是线性可分的,然而在实践中有些实例是线性不可分的,甚至是非线性的。


为了解决在线学习中的非线性可分问题,一些基于核的在线学习算法被广泛应用,但是这些基于核在线学习方法需要消耗更多的计算和内存资源。同时另一方面,为了解决线性不可分的任务,一些局部分类器已经在离线学习中提出。比如:局部线性支持向量机和局部深度核学习。这些局部分类器避免了内核建模,并且比内核方法快得多,但它们并不合适应用于在线学习任务中。为了解决在线学习的非线性数据的问题,一种基于多个局部分类器的联合在线学习框架被提出,并显示了良好的效果。为了提高模型的效果,我们进一步扩展地提出了基于 SCW 算法的局部在线学习算法(SCW-LOL)。稍后我们将详细描述该算法的细节以及实验结果。


问题分析


方法介绍




与其他传统的在线学习不同,在样本与子分类器的选择上,我们采用一种 onlineKMeans 算法,将样本分配到离样本距离最近的子分类器。每个子分类器维护自己的一个质心 Pi,t,通过质心来计算与样本的距离。同时,当样本分配到该子分类器时,更新质心如下公式:



其中 ni,t 表示 t 时刻分配到 i 个子分类器的总样本数。


同理,主分类器和子分类器模型的参数可表示如下形式:




那么公式(5)可以写成如下公式:



公式(9)和 SCW 算法的目标函数类似,模型参数的更新公式如下:



其中相关系数的计算如下:



其中 SCW-LOL 算法训练和更新的流程如下图:



实验结果

我们采用两个主要指标来衡量在线学习的性能,一个是累积错误率,



该指标反映了模型从开始到现在的整体准确率。另一个指标是测试错误率,这个指标表示模型训练结束后,在未知的测试集上的错误率,该指标反映了模型的泛化能力。


我们在 10 个不同数据集(5 个 2 分类数据集,5 个多分类数据集)上测试了我们的 SCW-LOL 算法,并同时与其他主要的在线学习算法比较,其结果如下:





从实验结果来看,SCW-LOL 算法在大部分数据集上都取得了最好的性能。尤其在多分类预测中,在所有算法中的错误率最小。


总结

为解决在线学习中非线性数据的问题,我们提出了一种基于 SCW 算法的局部在线学习(SCW-LOL)算法。该算法从流数据中学习并更新全局模型和局部模型。传入的样本将被分配到相应的局部模型,通过多个局部线性模型来逼近非线性模型,从而解决数据非线性可分问题。此外,我们的方法模型参数维护了二阶信息,比一阶在线学习方法的准确度更高。通过损失界限的理论分析,SCW-LOL 算法的损失界限不会高于 SCW 算法的损失界限,也就意味着该在线学习算法是收敛的。实验结果显示,SCW-LOL 算法在流式数据预测中性能十分突出,尤其在多类分类预测任务上。


本文转载自公众号蚂蚁金服科技(ID:Ant-Techfin)。


原文链接:


https://mp.weixin.qq.com/s/Gf4Z2wyOQIlEate_5LfTvQ


2019 年 9 月 05 日 17:451216
用户头像

发布了 150 篇内容, 共 22.1 次阅读, 收获喜欢 16 次。

关注

评论

发布
暂无评论
发现更多内容

0互联网工作经验的我,面对字节跳动产品岗1723个招聘岗位慌了起来….

Geek_fe4aa7

产品经理训练营 极客大学产品经理训练营

产品经理调研备忘录(何先生的梦呓)

小蜜蜂

产品经理 能力模型 产品经理训练营 何先生的梦呓 数据能力

产品经理岗位对比

思亭

产品训练营-作业1

简小一

产品经理训练营_Chapter1

芃芃

产品经理训练营

如何给产品团队更好地提出设计反馈

Justin

心理学 产品设计 团队协作 28天写作

产品经理岗位需求总结

Geek_a32093

行业产品经理岗位分析

Shine

产品

把我自己做成产品交付给目标岗位

havaguday

产品经理岗位对比分析

DwToretto

如果公司要招⼀个⾼级版你

向日葵

产品经理训练营

极客时间产品训练营-第一周学习总结(上)

Trigger

极客大学产品经理训练营

产品经理第一周第二课总结(第一课手贱删除了,回头再补)

克比

ACC是如何实现的(28天写作 Day12/28)

mtfelix

自动驾驶 28天写作

产品经理笔记1-1

🍑

极客大学产品经理训练营

产品经理训练营第0期-第一周作业

🍑

极客大学产品经理训练营

第一章学习总结

Kasn

产品经理 产品经理训练营

HDFS杂谈:数据读写原理

罗小龙

hadoop hdfs 28天写作

Dubbo源码解析-开始篇

冰三郎

Java 分布式 dubbo RPC

甲方日常 87

句子

工作 随笔杂谈 日常

产品训练营作业1-李沂秾

克比

极客大学产品训练营作业(第1周)

朱航

三个有意思的产品作业(第一次)

李钊悌

Job Model

·大蕾同学

第一章作业:认识产品经理

隋泽

产品经理训练营

HTML(三)——在网页中使用图像img

程序员的时光

程序员 28天写作

第一节课总结

Jove

Week1:按图索骥—从JD入手做能力建设

Y.

产品 产品经理训练营 极客大学产品经理训练营 求职岗位要求

应聘&招聘

skylar

用户增长产品经理招聘帖

梁媛

产品经理

assignment 01

Jove

一种针对非线性数据的局部在线学习方法-InfoQ