具有双重稀疏机制的在线学习算法

doi:10.3969/j.issn.0372-2112.2019.10.023

电子学报 ›› 2019, Vol. 47 ›› Issue (10): 2202-2210.DOI: 10.3969/j.issn.0372-2112.2019.10.023

具有双重稀疏机制的在线学习算法

魏波^1,2, 吴瑞峰¹, 张文生², 吕敬钦¹, 王莹莹³, 夏学文¹

1. 华东交通大学软件学院, 江西南昌 330013;
2. 中国科学院自动化研究所, 北京 100190;
3. 华东交通大学人文社会科学学院, 江西南昌 330013

收稿日期:2018-08-18 修回日期:2019-01-05 出版日期:2019-10-25
- 通讯作者:
- 夏学文
- 作者简介:
- 魏波男,1983年出生,湖北天门人.博士、中国自动化学会会员.2010年、2013年在武汉大学分别获得硕士和工学博士学位.现为中国科学院自动化研究所博士后,主要从事智能计算、在线机器学习等方面的研究工作.E-mail:weibo_wh@163.com;吴瑞峰 男,1993年生,湖北京山人.硕士研究生.主要从事智能计算与智能信息处理方面的研究;张文生 男,1966年出生,河南郑州人.中国科学院自动化研究所研究员,博士生导师,研究方向为模式识别、机器学习、深度神经网络等;吕敬钦 男,1984年出生,江西上饶人.博士.主要从事模式识别、视频图像处理方面的研究工作;王莹莹 女,1983年生,湖北襄阳人.硕士.研究方向为智能政务管理、电子政务.
- 基金资助:
- 国家自然科学基金 (No.61806204，No.61463017，No.61663009）; 国家自然科学基金重点项目 (No.U61432008）; 江西省高校教改课题 (No.JXJG-18-5-19）

An Online Learning Algorithm with Dual Sparse Mechanisms

WEI Bo^1,2, WU Rui-feng¹, ZHANG Wen-sheng², Lü Jing-qin¹, WANG Ying-ying³, XIA Xue-wen¹

1. School of Software, East China Jiaotong University, Nanchang, Jiangxi 330013, China;
2. Institute of Automation, Chinese Academy of Science, Beijing 100190, China;
3. School of Humanities and Social Sciences, East China Jiaotong University, Nanchang, Jiangxi 330013, China

Received:2018-08-18 Revised:2019-01-05 Online:2019-10-25 Published:2019-10-25

摘要/Abstract

摘要： 针对大数据背景下数据分类问题，已有的在线学习算法通常引入L₁范数正则化增强预测模型的稀疏性，但单一的正则化约束不能高效的获取稀疏模型.基于此，提出了一种具有双重稀疏机制的在线学习算法（an online learning algorithm with dual sparse mechanisms，DSOL）.在DSOL算法中，一方面利用L_1/2正则化项约束目标函数以增强预测模型的稀疏性，提高算法的泛化性能.另一方面用改进的梯度截取法对数据特征进行选择，有效稀疏化预测模型.通过L_1/2正则化与改进的梯度截取策略的有机融合，有效利用了历史数据信息，提高了算法分类数据的性能.通过与另4种代表性稀疏在线学习算法在9个公开数据集的实验对比表明DSOL算法对数据分类的准确性更高.

关键词: 大数据, 在线学习, 稀疏性, L_1/2范数, 平均梯度

Abstract: To deal with data classification problems under the background of big data,many existing online learning algorithms usually take advantage of L₁ norm regularization to enhance the sparsity of the prediction model.However,a sparse prediction model cannot be obtained efficiently by a single regularization constraint.In this paper,an online learning algorithm with dual sparse mechanisms (DSOL) is proposed.In DSOL algorithm,the objective function is constrained by L_1/2 regularization in order to enhance the prediction model's sparsity,and then improve the generalization ability of DSOL.Furthermore,an improved truncated gradient method is applied to enhance the sparsity of the prediction model through properly selecting the features of data.By the organic integration of the above two sparse mechanisms,including the L_1/2 regularization and the improved truncated gradient method,some historical data information can be effectively utilized,and then the performance of the algorithm in data classification can be greatly improved.Extensive experiments between DSOL and other 4 popular sparse online learning algorithms on 9 open data sets manifest that DSOL algorithm yields more favorable performance on data classification.

Key words: big data, online learning, sparsity, L_1/2 norm, average gradient

中图分类号:

TP391

魏波, 吴瑞峰, 张文生, 吕敬钦, 王莹莹, 夏学文. 具有双重稀疏机制的在线学习算法[J]. 电子学报, 2019, 47(10): 2202-2210.

WEI Bo, WU Rui-feng, ZHANG Wen-sheng, Lü Jing-qin, WANG Ying-ying, XIA Xue-wen. An Online Learning Algorithm with Dual Sparse Mechanisms[J]. Acta Electronica Sinica, 2019, 47(10): 2202-2210.

参考文献

[1] Rosenblatt F.A probabilistic model for information storage and organization in the brain[J].Psychological Review,1958,65(6):386-408.
[2] 仵博,郑红燕,冯延蓬,等.一种基于模型的可分解贝叶斯在线强化学习[J].电子学报,2014,42(7):1429-1434. Wu B,Zheng H Y,Feng Y P,et al.Model-based factored Bayesian online reinforcement learning[J].Acta Electronica Sinica,2014,42(7):1429-1434.(in Chinese)
[3] Rakhlin A,Sridharan K,Tewari A.Online learning via sequential complexities[J].Journal of Machine Learning Research,2015,16(1):155-186.
[4] Langford J.Sparse online learning via truncated gradient[J].Journal of Machine Learning Research,2008,10(2):777-801.
[5] Xiao L.Dual averaging methods for regularized stochastic learning and online optimization[J].Journal of Machine Learning Research,2010,10(11):2543-2596.
[6] Xu Z B,Zhang H,Wang H,et al.L1/2 regularization[J].Science China Information Sciences,2010,53(6):1159-1169.
[7] Li Y,Long P M.The relaxed online maximum margin algorithm[J].Machine Learning,2002,46(1-3):361-387.
[8] Gentile C.A new approximate maximal margin classification algorithm[J].Journal of Machine Learning Research,2001,2(12):213-242.
[9] Zhou Z,Zheng W S,Hu J F,et al.One-pass online learning:A local approach[J].Pattern Recognition,2016,51:346-357.
[10] Cesa-Bianchi N,Conconi A,Gentile C.A second-order perception algorithm[J].SIAM Journal on Computing,2005,34(3):640-668.
[11] Crammer K,Kulesza A,Dredze M.Adaptive regularization of weight vectors[A].Advances in Neural Information Processing Systems[C].USA:MIT Press,2009.414-422.
[12] Orabona F,Crammer K,Cesa-Bianchi N.A generalized online mirror descent with applications to classification and regression[J].Machine Learning,2015,99(3):411-435.
[13] Shalev-Shwartz S.Online learning and online convex optimization[J].Foundations and Trends in Machine Learning,2012,4(2):107-194.
[14] Dekel O,Shalev-Shwartz S,Singer Y.The forgettron:a kernel-based perceptron on a budget[J].Siam Journal on Computing,2008,37(5):1342-1372.
[15] Orabona F,Keshet J,Caputo B.Bounded kernel-based online learning[J].Journal of Machine Learning Research,2009,10(6):2643-2666.
[16] Lu J,Hoi S,Wang J,et al.Large scale online kernel learning[J].Journal of Machine Learning Research,2016,17(1):1613-1655.
[17] 罗大鹏,罗琛,魏龙生,等.基于在线随机蕨分类器的实时视觉感知系统[J].电子学报,2016,44(5):1139-1148. Luo D P,Luo C,Wei L S,et al.Real time visual perception system based on online fern classifier[J].Acta Electronica Sinica,2016,44(5):1139-1148.(in Chinese)
[18] Duchi J,Singer Y.Efficient online and batch learning using forward backward splitting[J].The Journal of Machine Learning Research,2009,10(18):2899-2934.
[19] Lu J,Sahoo D,Zhao P,et al.Sparse passive-aggressive learning for bounded online kernel methods[J].ACM Transactions on Intelligent Systems and Technology,2018,9(4):1-27.
[20] Wang D,Wu P,Zhao P,et al.High-dimensionalxz data stream classification via sparse online learning[A].2014 IEEE International Conference on Data Mining[C].Piscataway:IEEE Press,2014.1007-1012.

具有双重稀疏机制的在线学习算法

An Online Learning Algorithm with Dual Sparse Mechanisms

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陆克中, 陈超凡, 蔡桓, 吴定明. 面向概念漂移和类不平衡数据流的在线分类算法[J]. 电子学报, 2022, 50(3): 585-597.
[2]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[3]	高琛, 张帆, 高彦钊. 利用数据稀疏性的LSTM加速器设计[J]. 电子学报, 2021, 49(2): 209-215.
[4]	罗大鹏, 杜国庆, 曾志鹏, 魏龙生, 高常鑫, 陈应, 肖菲, 罗琛. 基于少量样本学习的多目标检测跟踪方法[J]. 电子学报, 2021, 49(1): 183-191.
[5]	杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.
[6]	陆佳炜, 吴涵, 陈烘, 张元鸣, 梁倩卉, 肖刚. 一种基于动态拓扑的流计算性能优化方法及其在Storm中的实现[J]. 电子学报, 2020, 48(5): 878-890.
[7]	徐超, 陈勇, 葛红美, 何炎祥. 基于大数据的审计技术研究[J]. 电子学报, 2020, 48(5): 1003-1017.
[8]	江小玉, 李贵洋, 周悦, 胡金平, 李慧. 基于负载均衡的纠删码修复流水线[J]. 电子学报, 2020, 48(5): 930-936.
[9]	廖祝华, 张健, 刘毅志, 肖浩, 赵肄江, 刘建勋. 基于稀疏轨迹数据的出租车载客区域推荐[J]. 电子学报, 2020, 48(11): 2178-2185.
[10]	张鹏, 叶剑, 张鹏. 基于概念漂移检测的大数据交易过程模型优化方法[J]. 电子学报, 2019, 47(7): 1465-1474.
[11]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[12]	吴林煌, 苏凯雄, 王琳, 陈志峰, 陈平平. 正交匹配追踪和BIC准则的自适应双频段预失真模型优化算法[J]. 电子学报, 2018, 46(9): 2149-2156.
[13]	郭艺, 叶剑, 张鹏. 基于偏差约减的大数据交易模型分析与修复方法[J]. 电子学报, 2018, 46(7): 1754-1761.
[14]	尹鑫, 田有亮, 王海龙. 面向大数据定价的委托拍卖方案[J]. 电子学报, 2018, 46(5): 1113-1120.
[15]	丁琳琳, 崔子强, 尹显坤, 王俊陆, 宋宝燕. 基于MapReduce的增广动态Skyline查询处理方法[J]. 电子学报, 2018, 46(5): 1062-1070.