基于多图的交替优化图直推方法

doi:10.11772/j.issn.1001-9081.2015.06.1611

计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1611-1616.DOI: 10.11772/j.issn.1001-9081.2015.06.1611

基于多图的交替优化图直推方法

修宇¹, 王骏², 王忠群¹, 刘三民¹

1. 安徽工程大学计算机与信息学院, 安徽芜湖 241000;
2. IBM T J Watson 研究中心, 纽约州约克城高地 10598

收稿日期:2014-12-31 修回日期:2015-04-01 发布日期:2015-06-12
通讯作者: 修宇(1976-),男,山东单县人,讲师,硕士,CCF会员,主要研究方向:机器学习、数据挖掘;xiuyu1860@126.com
作者简介:王骏(1976-),男,安徽芜湖人,研究员,博士,主要研究方向:机器学习、数据挖掘;王忠群(1965-),男,安徽芜湖人,教授,主要研究方向:商务智能;刘三民(1978-),男,安徽岳西人,副教授,博士,主要研究方向:模式识别、网络安全。
基金资助:
国家自然科学基金资助项目(71371012,71171002);教育部人文社科规划项目(13YJA630098);安徽省优秀青年人才基金重点项目(2013SQRL034Z);安徽省高校省级科学研究项目(TSKJ2014B10);安徽工程大学计算机应用技术重点实验室开放基金资助项目(JSJKF201510)。

Graph transduction via alternating minimization method based on multi-graph

XIU Yu¹, WANG Jun², WANG Zhongqun¹, LIU Sanmin¹

1. College of Computer and Information Engineering, Anhui Polytechnic University, Wuhan Anhui 241000, China;
2. IBM T. J. Watson Research Center, Yorktown Heights New York 10598, USA

Received:2014-12-31 Revised:2015-04-01 Published:2015-06-12

摘要/Abstract

摘要：

针对基于单图的半监督学习(GSSL)算法的性能受单个图质量的影响,且在单视图数据下,大多数基于多图的GSSL算法难以使用的问题,提出了一种基于多图的交替优化图直推方法(MG-GTAM)。首先,使用不同的图构建参数来构建单视图数据下的多个图,利用多个图来表达数据间关系;然后,借助交替迭代方式综合多个图的信息,选择置信度高的未标记样本进行伪标记并通过权重权衡各图的重要程度,以优化多图上的预测函数的一致性和平滑性;最后通过组合每个图的预测函数完成对所有未标记样本的标记。仿真实验表明,与经典的局部和全局一致(LGC)、高斯随机场和调和函数(GFHF)、交替优化直推(GTAM)、组合图拉普拉斯(CGL)算法相比,在COIL20目标物体数据集和NEC Animal数据集上,MG-GTAM的分类错误率比这些经典算法均有下降,表明了该方法具有良好的性能。实验结果表明, MG-GTAM能有效地利用多个图来表达数据之间的关系,获得更低的分类错误率。

关键词: 图半监督学习, 图直推, 图构建, 多图, 交替优化

Abstract:

The performance of the Graph-based Semi-Supervised Learning (GSSL) method based on one graph mainly depends on a well-structured single graph and most algorithms based on multiple graphs are difficult to be applied while the data has only single view. Aiming at the issue, a Graph Transduction via Alternating Minimization method based on Multi-Graph (MG-GTAM) was proposed. Firstly, using different graph construction parameters, multiple graphs were constructed from data with one single view to represent data point relation. Secondly,the most confident unlabeled examples were chosen for pseudo label assignment through the integration of a plurality of map information and imposed higher weights to the most relevant graphs based on alternating optimization,which optimized agreement and smoothness of prediction function over multiple graphs. Finally, more accurate labels were given over the entire unlabeled examples by combining the predictions of all individual graphs. Compared with the classical algorithms of Local and Global Consistency (LGC), Gaussian Fields and Harmonic Functions (GFHF), Graph Transduction via Alternation Minimization (GTAM), Combined Graph Laplacian (CGL), the classification error rates of MG-GTAM decrease on data sets of COIL20 and NEC Animal. The experimental results show that the proposed method can efficiently represent data point relation with multiple graphs, and has lower classification error rate.

Key words: Graph-based Semi-Supervised Learning (GSSL), graph transduction, graph construction, multi-graph, alternating minimization

中图分类号:

TP181

修宇, 王骏, 王忠群, 刘三民. 基于多图的交替优化图直推方法[J]. 计算机应用, 2015, 35(6): 1611-1616.

XIU Yu, WANG Jun, WANG Zhongqun, LIU Sanmin. Graph transduction via alternating minimization method based on multi-graph[J]. Journal of Computer Applications, 2015, 35(6): 1611-1616.

参考文献

[1] ZHU X. Semi-supervised learning literature survey, TR 1530 [R]. Madison: University of Wisconsin-Madison, 2005.
[2] OLIVER C, BERNHARD S, ALEXANDER Z. Semi-supervised learning [M]. Cambridge: MIT Press, 2006: 9-10.
[3] LIU J, LIU Y, LUO X. Study on semi-supervised learning methods [J/OL]. Chinese Journal of Computers, 2014, 37. [2014-12-02]. http://www.cnki.net/kcms/detail/11.1826.TP.20140828.1917.005.html.(刘建伟, 刘媛, 罗雄麟.半监督学习方法研究综述[J/OL].计算机学报, 2014, 37.[2014-12-02].http://www.cnki.net/kcms/detail/11.1826.TP.20140828.1917.005.html.)
[4] JEBARA T, WANG J, CHANG S-F. Graph construction and b-matching for semi-supervised learning [C]//Proceedings of the 26th Annual International Conference on Machine Learning. New York: ACM, 2009: 441-448.
[5] de SOUSA C A R, REZENDE S O, BATISTA G E A P A. Influence of graph construction on semi-supervised learning [C]//Proceedings of the 2013 European Conference on Machine Learning and Knowledge Discovery in Databases, LNCS 8190. Berlin: Springer-Verlag, 2013: 160-175.
[6] SINDHWANI V, NIYOGO P, BELKIN M. A co-regularized approach to semi-supervised learning with multiple views [C]//Proceedings of the 22th International Conference on Machine Learning. Cambridge: MIT Press, 2005: 823-831.
[7] SINDHWANI V, ROSENBERG D S. An RKHS for multi-view learning and manifold co-regularization [C]//Proceedings of the 25th International Conference on Machine Learning. New York: ACM, 2008: 976-983.
[8] ZHANG D, WANG F, ZHANG C, et al. Multi-view local learning [C]//Proceedings of the 23th AAAI Conference on Artificial Intelligence.Menlo Park: AAAI Press, 2008, 2: 752-757.
[9] DU Y, LI Q, CAI Z, et al.Multi-view semi-supervised Web image classification via co-graph [J]. Neurocomputing, 2013, 122: 430-440.
[10] ARGYRIOU A, HERBSTER M, PONTIL M. Combining graph Laplacians for semi-supervised learning [C]//Advances in Neural Information Processing Systems 18. Cambridge: MIT Press, 2006: 67-74.
[11] ZHOU Z. Disagreement-based semi-supervised learning [J].Acta Automatica Sinica, 2013, 39(11): 1871-1878. (周志华.基于分歧的半监督学习[J].自动化学报, 2013, 39(11):1871-1878.)
[12] MAIER M, von LUXBURG U, HEIN M. Influence of graph construction on graph-based clustering measures [EB/OL]. [2014-12-03]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.143.8751&rep=rep1&type=pdf.
[13] SHE Q, YU Y, JIANG Y, et al.Large-scale image annotation via random forest based label propagation [J]. Journal of Computer Research and Development, 2012, 49(11): 2289-2295.(佘俏俏, 俞扬, 姜远, 等. 一种基于标记传播的大规模图像分类方法[J].计算机研究与发展, 2012, 49(11):2289-2295.)
[14] WANG J, JEBARA T, CHANG S-F. Graph transduction via alternation minimization [C]//Proceedings of the 25th Annul International Conference on Machine Learning. New York: ACM, 2008: 1144-1151.
[15] WANG J, JEBARA T, CHANG S-F. Semi-supervised learning using greedy max-cut [J]. Journal of Machine Learning Research, 2013, 14(1): 771-800.
[16] ZHU X, GHAHRAMANI Z, LAFFERTY J. Semi-supervised learning using Gaussian fields and harmonic functions [C/OL]//Proceedings of the 20th International Conference on Machine Learning. [2014-12-03]. http://www.aaai.org/Papers/ICML/2003/ICML03-118.pdf.
[17] ZHOU D, BOUSQUET O, LAL T N, et al. Learning with local and global consistency [C]//Proceedings of the 2004 Conference on Neural Information Processing Systems. Cambridge:MIT Press, 2004:321-328.
[18] MURASE H, NENE S K.Visual learning and recognition of 3-D objects from appearance [J]. International Journal of Computer Vision, 1995, 14(1): 5-24.
[19] MOBAHI H, COLLOBERT R, WESTON J. Deep learning from temporal coherence in video [C]//Proceedings of the 26th International Conference on Machine Learning. New York: ACM, 2009: 737-744.

基于多图的交替优化图直推方法

Graph transduction via alternating minimization method based on multi-graph

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陆国庆, 孙昊. 基于随机行走的群机器人二维地图构建[J]. 计算机应用, 2021, 41(7): 2121-2127.
[2]	南宁, 杨程屹, 武志昊. 基于多图神经网络的会话感知推荐模型[J]. 计算机应用, 2021, 41(2): 330-336.
[3]	付豪, 徐和根, 张志明, 齐少华. 动态场景下基于语义和光流约束的视觉同步定位与地图构建[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3337-3344.
[4]	郑思诚, 孔令华, 游通飞, 易定容. 动态环境下基于深度学习的语义SLAM算法[J]. 计算机应用, 2021, 41(10): 2945-2951.
[5]	吕亚丽, 苗钧重, 胡玮昕. 基于标签进行度量学习的图半监督学习算法[J]. 计算机应用, 2020, 40(12): 3430-3436.
[6]	赵宏, 刘向东, 杨永娟. 基于RGB-D图像的室内机器人同时定位与地图构建[J]. 计算机应用, 2020, 40(12): 3637-3643.
[7]	席志红, 王洪旭, 韩双全. 基于ORB-SLAM2系统的快速误匹配剔除算法与地图构建[J]. 计算机应用, 2020, 40(11): 3289-3294.
[8]	丁斗建, 赵晓林, 王长根, 高关根, 寇磊. 基于视觉的机器人自主定位与障碍物检测方法[J]. 计算机应用, 2019, 39(6): 1849-1854.
[9]	黄帅, 付光远, 伍明, 岳敏. 未知环境基于单目次优视差的多模滤波目标跟踪算法[J]. 计算机应用, 2019, 39(3): 864-868.
[10]	席志红, 韩双全, 王洪旭. 基于语义分割的室内动态场景同步定位与语义建图[J]. 计算机应用, 2019, 39(10): 2847-2851.
[11]	胡章芳, 鲍合章, 陈旭, 范霆铠, 赵立明. 基于改进闭环检测算法的视觉同时定位与地图构建[J]. 计算机应用, 2018, 38(3): 873-878.
[12]	侯荣波, 魏武, 黄婷, 邓超锋. 基于ORB-SLAM的室内机器人定位和三维稠密地图构建[J]. 计算机应用, 2017, 37(5): 1439-1444.
[13]	林辉灿, 吕强, 王国胜, 张洋, 梁冰. 基于VSLAM的自主移动机器人三维同时定位与地图构建[J]. 计算机应用, 2017, 37(10): 2884-2887.
[14]	沈辉, 袁晓彤, 刘青山. 基于预测稀疏编码的快速单幅图像超分辨率重建[J]. 计算机应用, 2015, 35(6): 1749-1752.
[15]	赵亮陈敏李洪臣. 基于视觉同时定位与地图构建数据关联优化算法[J]. 计算机应用, 2014, 34(2): 576-579.