有监督的距离度量学习算法研究进展

沈媛媛; 严严; 王菡子

doi:10.3724/SP.J.1004.2014.02673

有监督的距离度量学习算法研究进展

doi: 10.3724/SP.J.1004.2014.02673

1.
厦门大学信息科学与技术学院厦门 361005

基金项目:

国家自然科学基金(61201359,61170179),福建省自然科学基金(2012J05126),高等学校博士学科点专项科研基金(20110121110033)资助

详细信息

作者简介:
沈媛媛厦门大学信息科学与技术学院硕士研究生. 2010 年获安徽大学学士学位.主要研究方向为距离度量学习和模式识别.E-mail:shenyuanyuan1989@gmail.com

通讯作者:
严严厦门大学信息科学与技术学院助教. 主要研究方向为计算机视觉和模式识别. 本文通信作者.E-mail: yanyan@xmu.edu.cn

计量
- 文章访问数: 3117
- HTML全文浏览量: 152
- PDF下载量: 4053
- 被引次数: 0
出版历程
- 收稿日期: 2014-01-20
- 修回日期: 2014-04-10
- 刊出日期: 2014-12-20

Recent Advances on Supervised Distance Metric Learning Algorithms

1.
School of Information Science and Technology, Xiamen University, Xiamen 361005

Funds:

Supported by National Natural Science Foundation of China (61201359, 61170179), Natural Science Foundation of Fujian Province (2012J05126), and Specialized Research Fund for the Doctoral Program of Higher Education of China (20110121110033)

摘要

摘要: 近年来, 距离度量学习已成为计算机视觉和模式识别等领域最为活跃的研究课题之一. 如何利用训练数据学习得到有效的距离度量来衡量目标之间的相似性是该类研究的关键问题. 针对有监督的距离度量学习问题,目前已提出了大量的研究算法. 结合近年已发表相关文献对有监督的距离度量学习算法进行了详细的介绍和讨论. 根据样本信息利用方式的不同, 将其划分成基于成对约束和非成对约束的距离度量学习算法, 重点介绍了一些常用的典型算法, 分析了每种算法的原理和优缺点, 最后是未来发展方向和趋势的展望.
- 距离度量学习 /
- 马氏距离 /
- 成对约束 /
- 非成对约束
Abstract: Recently, distance metric learning has become one of the most attractive research areas in computer vision and pattern recognition. How to learn an effective distance metric to measure the similarity between subjects is a key problem. A large number of algorithms have been proposed to deal with supervised distance metric learning. This paper reviews and discusses recently developed algorithms for supervised distance metric learning. Based on the partition of pairwise constraints and non-pairwise constraints, some representative algorithms are introduced and their respective pros and cons are analyzed. The prospects for future development and suggestions for further research work are presented in the end.
- Distance metric learning /
- Mahalanobis distance /
- pairwise constraints /
- non-pairwise constraints

HTML全文

参考文献(87)

[1]	Xing E P, Ng A Y, Jordan M I, Russell S. Distance metric learning with application to clustering with side-information. In: Proceedings of the 2003 Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2003. 521-528
[2]	Goldberger J, Roweis S, Hinton G, Salakhutdinov R. Neighbourhood components analysis. In: Proceedings of the 2004 Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2004. 513-520
[3]	Xiang S M, Nie F P, Zhang C S. Learning a Mahalanobis distance metric for data clustering and classification. Pattern Recognition, 2008, 41(12): 3600-3612
[4]	Weinberger K Q, Saul L K. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 2009, 10: 207-244
[5]	Mensink T, Verbeek J, Perronnin F, Csurka G. Metric learning for large scale image classification: generalizing to new classes at near-zero cost. In: Proceedings of the 12th European Conference on Computer Vision. Florence, Italy: IEEE, 2012. 488-501
[6]	Feng Z, Jin R, Jain A. Large-scale image annotation by efficient and robust kernel metric learning. In: Proceedings of the 2013 International Conference on Computer Vision. Sydney, Australia: IEEE, 2013. 1609-1616
[7]	Wang X Y, Hua G, Han T X. Discriminative tracking by metric learning. In: Proceedings of the 11th European Conference on Computer Vision. Heraklion, Greece: Springer, 2010. 200-214
[8]	Chen J H, Zhao Z, Ye J P, Liu H. Nonlinear adaptive distance metric learning for clustering. In: Proceedings of the 2007 International Conference on Knowledge Discovery and Data Mining. California, USA: ACM, 2007. 123-132
[9]	Ye J P, Zhao Z, Liu H. Adaptive distance metric learning for clustering. In: Proceeding of the 2007 Computer Society Conference on Computer Vision and Pattern Recognition. Minnesota, USA: IEEE, 2007. 1-7
[10]	Cinbis R G, Verbeek J, Schmid C. Unsupervised metric learning for face identification in TV video. In: Proceedings of the 2011 International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011. 1559-1566
[11]	Wang B, Jiang J Y, Wang W, Zhou Z H, Tu Z W. Unsupervised metric fusion by cross diffusion. In: Proceedings of the 2012 Conference on Computer Vision and Pattern Recognition. Providence, RI, USA: IEEE, 2012. 2997-3004
[12]	Mignon A, Jurie F. CMML: a new metric learning approach for cross modal matching. In: Proceedings of the 11th Asian Conference on Computer Vision. Daejeon, Korea: Springer, 2012. 14-27
[13]	Cao B, Ni X C, Sun J T, Wang G, Yang Q. Distance metric learning under covariate shift. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Barcelona, Spain: AAAI, 2011. 1204-1210
[14]	Guillaumin G, Verbeek J, Schmid C. Multiple instance metric learning from automatically labeled bags of faces. In: Proceedings of the 11th European Conference on Computer Vision. Heraklion, Greece: Springer, 2010. 634-647
[15]	Baghshah M S, Shouraki S B. Non-linear metric learning using pairwise similarity and dissimilarity constraints and the geometrical structure of data. Pattern Recognition, 2010, 43(8): 2282-2292
[16]	Yang L, Jin R, Sukthankar R. Bayesian active distance metric learning. In: Proceedings of the 23th Conference on Uncertainty in Artificial Intelligence. Vancouver, Canada: AUAI Press, 2007. 442-449
[17]	Cevikalp H. Distance metric learning by quadratic programming based on equivalence constraints. In: Proceedings of the 20th International Conference on Pattern Recognition. Istanbul, Turkey: IEEE, 2010. 3352-3355
[18]	Davis J V, Kulis B, Jain P, Sra S, Dhillon I S. Information-theoretic metric learning. In: Proceedings of the 24th International Conference. Oregon, USA: ACM, 2007. 209-216
[19]	Wang J, Do H, Woznica A, Kalousis A. Metric learning with multiple kernels. In: Proceedings of the 2001 Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2011. 1170-1178
[20]	Baghshah M S, Shouraki S B. Semi-supervised metric learning using pairwise constraints. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence. California, USA: IJCAI, 2009. 1217-1222
[21]	Zhang Y, Yeung D Y. Transfer metric learning by learning task relationships. In: Proceedings of the 16th International Conference on Knowledge Discovery and Data Mining. Washington, USA: ACM, 2010. 1199-1208
[22]	Li W, Zhao R, Wang X G. Human reidentification with transferred metric learning. In: Proceedings of the 11th Asian Conference on Computer Vision. Daejeon, Korea: Springer, 2012. 31-44
[23]	Parameswaran S B, Weinberger K Q. Large margin multi-task metric learning. In: Proceedings of the 2010 Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2010. 1867-1875
[24]	Yang P P, Huang K Z, Liu C L. A multi-task framework for metric learning with common subspace. Neural Computing and Applications, 2013, 22(7-8): 1337-1347
[25]	Yang P P, Huang K Z, Liu C. Geometry preserving multi-task metric learning. Machine Learning, 2013, 92(1): 133-175
[26]	Jin R, Wang S J, Zhou Y. Regularized distance metric learning: theory and algorithm. In: Proceedings of the 23rd Annual Conference on Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2009. 862-870
[27]	Hoi S C H, Liu W, Chang S F. Semi-supervised distance metric learning for collaborative image retrieval. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Alaska, USA: IEEE, 2008. 1-7
[28]	Shen C H, Kim J, Wang L. Scalable large-margin Mahalanobis distance metric learning. IEEE Transactions on Neural Networks, 2010, 21(9): 1524-1530
[29]	Shen C H, Kim J, Wang L. A scalable dual approach to semidefinite metric learning. In: Proceedings of the 24th Conference on Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2011. 2601-2608
[30]	Huang K Z, Ying Y M, Campbell C. GSML: a unified framework for sparse metric learning. In: Proceedings of the 9th International Conference on Data Mining. Florida, USA: IEEE, 2009. 189-198
[31]	Huang K Z, Ying Y M, Campbell C. Generalized sparse metric learning with relative comparisons. Knowledge and Information Systems, 2011, 28(1): 25-45
[32]	Liu W, Hoi S C H, Liu J Z. Output regularized metric learning with side information. In: Proceedings of the 10th European Conference on Computer Vision. Marseille, France: Springer, 2008. 358-371
[33]	Yang L, Jin R. Distance Metric Learning: A Comprehensive Survey, Technical Report, Michigan State University, USA. 2006, 1-51
[34]	Bar-Hillel A, Hertz T, Shental N, Weinshall D. Learning a Mahalanobis metric from equivalence constraints. Journal of Machine Learning, 2005, 6: 937-965
[35]	Mignon A, Jurie F. PCCA: a new approach for distance learning from sparse pairwise constraints. In: Proceedings of the 2012 International Conference on Computer Vision and Pattern Recognition. Providence RI: IEEE, 2012. 2666-2672
[36]	Kostinger M, Hirzer M, Wohlhart P, Roth P M, Bischof H. Large scale metric learning from equivalence constraints. In: Proceedings of the 2012 Computer Vision and Pattern Recognition. Providence, RI: IEEE, 2012. 2288-2295
[37]	Boyd S P, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004.
[38]	Ying Y M, Li P. Distance metric learning with eigenvalue optimization. Journal of Machine Learning Research, 2013, 13(1): 1-26
[39]	Davis J V, Dhillon I S. Structured metric learning for high dimensional problems. In: Proceedings of the 14th International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA: ACM, 2008. 195-203
[40]	Kulis B, Sustik M A, Dhilon I S. Learning low-rank kernel matrices. In: Proceedings of the 23rd International Conference on Machine Learning. USA: ACM, 2006. 505-512
[41]	Qi G J, Tang J H, Zha Z J, Chua T S, Zhang H J. An efficient sparse metric learning in high-dimensional space via l1-penalized log-determinant regularization. In: Proceedings of the 26th Annual International Conference on Machine Learning. New York: ACM, 2009. 841-848
[42]	Cui Z, Li W, Xu D, Shan S G, Chen X L. Fusing robust face region descriptors via multiple metric learning for face recognition in the wild. In: Proceedings of the 2013 Computer Vision and Pattern Recognition. Portland, USA: IEEE, 2013. 3554-3561
[43]	Guillaumin M, Verbeek J, Schmid C. Is that you? Metric learning approaches for face identification. In: Proceedings of the 12th International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009. 498-505
[44]	Nguyen H V, Bai L. Cosine similarity metric learning for face verification. In: Proceedings of the 10th Asian Conference on Computer Vision. Queenstown, New Zealand: Springer, 2010. 709-720
[45]	Huang G B, Mattar M, Berg T, Erik L M. Labeled Faces in the Wild: A Database for Studying Face Recognition in Unconstrained Environments. Technical Report, University of Massachusetts, Amherst, USA. 2007, 1-11
[46]	Ojala T, Pietikäinen M, Mäenpää T. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 971-987
[47]	Cao Q, Ying Y M, Li P. Similarity metric learning for face recognition. In: Proceedings of the 2013 International Conference on Computer Vision. Sydney: IEEE, 2013. 2408-2415
[48]	Wang S J, Jin R. An information geometry approach for distance metric learning. In: Proceedings of the 2009 International Conference on Artificial Intelligence and Statistics. Florida, USA: AISTATS, 2009. 591-598
[49]	Samaria F S, Harter A C. Parameterisation of a stochastic model for human face identification. In: Proceedings of the 2nd IEEE Workshop on Applications of Computer Vision. Sarasota, USA: IEEE, 1994. 138-142
[50]	Verma Y, Jawahar C V. Image annotation using metric learning in semantic neighbourhoods. In: Proceedings of the 12th European Conference on Computer Vision. Florence, Italy: Springer, 2012. 836-849
[51]	Shen C H, Kim J, Wang L, Hengel A. Positive semidefinite metric learning using boosting-like algorithms. Journal of Machine Learning Research, 2012, 13: 1007-1036
[52]	Bi J B, Wu D J, Lu L, Liu M Z, Tao Y M, Wolf M. AdaBoost on low-rank PSD matrices for metric learning. In: Proceedings of the 24th International Conference on Computer Vision and Pattern Recognition. Colorado Springs, USA: IEEE, 2011. 2617-2624
[53]	Rosales R, Fung G. Learning sparse metrics via linear programming. In: Proceedings of the 12th International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2006. 367-373
[54]	Huang R Q, Sun S L. Kernel regression with sparse metric learning. Journal of Intelligent and Fuzzy Systems, 2013, 24(4): 775-787
[55]	Bah B, Becker S, Cevher V, Gozcu B. Metric learning with rank and sparsity constraints. In: Proceedings of the 2014 International Conference on Acoustics, Speech, and Signal Processing. Florence, Italy: IEEE, 2014, 21-25
[56]	Bilenko M, Basu S, Mooney R J. Integrating constraints and metric learning in semi-supervised clustering. In: Proceedings of the 21th International Conference on Maching Learning. New York: ACM, 2004. 81-88
[57]	Zou Peng-Cheng, Wang Jian-Dong, Yang Guo-Qing. Distance metric learning based on side information autogeneration for time series. Journal of Software, 2013, 24(11): 2642-2655(邹朋成, 王建东, 杨国庆. 辅助信息自动生成的时间序列距离度量学习. 软件学报, 2013, 24(11): 2642-2655)
[58]	Wang J, Woznica A, Kalousisi A. Parametric local metric learning for nearest neighbor classification. In: Proceedings of the 2012 Annual Conference on Neural Information Processing Systems. Nevada, USA: MIT Press, 2012. 1610-1618
[59]	Liu Song-Hua, Zhang Jun-Ying, Xu Jin, Jia Hong-En. Kernel-kNN: a new kNN algorithm based on informational energy metric. Acta Automatica Sinica, 2010, 36(12): 1681-1688(刘松华, 张军英, 许进, 贾宏恩. Kernel-kNN: 基于信息能度量的核k--最近邻算法. 自动化学报, 2010, 36(12): 1681-1688)
[60]	Gao Jun, Wang Shi-Tong, Wang Xiao-Ming. Contextual-distance metric based Laplacian maximum margin criterion. Acta Automatica Sinica, 2010, 36(12): 1661-1673(皋军, 王士同, 王晓明. 基于语境距离度量的拉普拉斯最大间距判别准则. 自动化学报, 2010, 36(12): 1661-1673)
[61]	Chang H, Yeung D Y. Locally smooth metric learning with application to image retrieval. In: Proceedings of the 11th IEEE International Conference on Computer Vision. Rio de Janeiro, Brazil: IEEE, 2007. 1-7
[62]	Yang L, Jin R, Mummert L, Sukthankar R, Goode A, Zheng B, Hoi S C H, Satyanarayanan M. A boosting framework for visuality-preserving distance metric learning and its application to medical image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(1): 30-44
[63]	Zhao K, Liu W, Liu J Z. Optimal semi-supervised metric learning for image retrieval. In: Proceedings of the 20th Multimedia Conference. New York: ACM, 2012. 893-896
[64]	Cong Y, Yuan J S, Tang Y D. Object tracking via online metric learning. In: Proceedings of the 19th International Conference on Image Processing. Orlando, USA: IEEE, 2012. 417-420
[65]	Jiang N, Liu W Y, Wu Y. Order determination and sparsity-regularized metric learning adaptive visual tracking. In: Proceedings of the 2012 International Conference on Computer Vision and Pattern Recognition. Providence, USA: IEEE, 2012. 1956-1963
[66]	Yao Zhi-Jun, Liu Jun-Tao, Lai Zhong-Yuan, Liu Wen-Yu. An improved Jensen-Shannon divergence based spatiogram. Acta Automatica Sinica, 2011, 37(12): 1464-1473(姚志均, 刘俊涛, 赖重远, 刘文予. 一种改进的JSD距离的空间直方图相似度度量及目标跟踪. 自动化学报, 2011, 37(12): 1464-1473)
[67]	Tran D, Sorokin A. Human activity recognition with metric learning. In: Proceedings of the 2008 European Conference on Computer Vision. Marseille, France: Springer, 2008. 548-561
[68]	Kliper-Gross O, Hassner T, Wolf L. One shot similarity metric learning for action recognition. In: Proceedings of the 2011 Similarity-Based Pattern Recognition. Berlin, Heidelberg: Springer, 2011. 31-45
[69]	Lebanon G. Metric learning for text documents. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 497-508
[70]	Jiang N, Liu W Y, Wu Y. Adaptive and discriminative metric differential tracking. In: Proceedings of the 2011 International Conference on Computer Vision and Pattern Recognition. CO, USA: IEEE, 2011. 1161-1168
[71]	Zhang Y N, Zhang H C, Nasrabadi N M, Huang T S. Multi-metric learning for multi-sensor fusion based classification. Information Fusion, 2013, 14(4): 431-440
[72]	Yan Yan, Zhang Yu-Jin. State-of-the-art on video-based face recognition. Chinese Journal of Computers, 2009, 32(5): 878-886)(严严, 章毓晋. 基于视频的人脸识别研究进展. 计算机学报, 2009, 32}(5): 878-886)
[73]	Gao Quan-Xue, Gao Fei-Fei, Hao Xiu-Juan, Cheng Jie. Image Euclidean distance-based two-dimensional local diversity preserving projection. Acta Automatica Sinica, 2013, 39(7): 1062-1070(高全学, 高菲菲, 郝秀娟, 程洁. 基于图像欧氏距离的二维局部多样性保持投影. 自动化学报, 2013, 39(7): 1062-1070)
[74]	Liu M Z, Vemuri B C. A robust and efficient doubly regularized metric learning approach. In: Proceedings of the 12th European Conference on Computer Vision, Florence, Italy: Springer, 2012. 646-659
[75]	Ebert S, Fritz M, Schiele B. Active metric learning for object recognition. In: Proceedings of the 2012 Pattern Recognition. Graz, Austria: Springer, 2012. 327-336
[76]	Tsagkatakis G, Savakis A E. Online distance metric learning for object tracking. IEEE Transactions on Circuits and Systems for Video Technology, 2011, 21(12): 1810-1821
[77]	Yu J, Wang M, Tao D C. Semi-supervised multiview distance metric learning for cartoon synthesis. IEEE Transactions on Image Processing, 2012, 21(11): 4636-4648
[78]	Niu G, Dai B, Yamada M. Information-theoretic semi-supervised metric learning via entropy regularization. In: Proceedings of the 29th International Conference on Machine Learning. Edinburgh, UK: ACM, 2012. 89-96
[79]	Chechik G, Sharma V, Shalit U, Bengio S. Large scale online learning of image similarity through ranking. The Journal of Machine Learning, 2010, 11: 1109-1135
[80]	Adrián P S, Francesc J F, Miguel A H. Passive-aggressive online distance metric learning and extensions. Progress in Artificial Intelligence, 2013, 2(1): 85-96
[81]	Cong Y, Liu J, Yuan J S, Luo J B. Self-supervised online metric learning with low rank constraint for scene categorization. IEEE Transactions on Image Processing, 2013, 22(8): 3179-3191
[82]	Jain P, Kulis B, Dhillon I S, Grauman K. Online metric learning and fast similarity search. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2009. 761-768
[83]	Ying Y M, Huang K Z, Compbell C. Sparse metric learning via smooth optimization. In: Proceedings of the 23rd Annual Conference on Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2009. 2214-2222
[84]	Li Z C, Liu J, Yu J, Tang J H, Lu H Q. Low rank metric learning for social image retrieval. In: Proceedings of the 20th ACM International Conference on Multimedia. Japan: ACM, 2012. 853-856
[85]	Zha Z J, Mei T, Wang M, Wang Z F, Hua X S. Robust distance metric learning with auxiliary knowledge. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence. San Francisco: AISTATS, 2009. 1327-1332
[86]	Huang K H, Jin R, Xu Z L, Liu C L. Robust metric learning by smooth optimization. In: Proceedings of the 26th Uncertainty in Artificial Intelligence. California, USA: AUAI Press, 2010. 244-251
[87]	Lim D, McFee B, Lanckriet G R G. Robust structural metric learning. In: Proceedings of the 2013 International Conference on Machine Learning. Atlanta, USA: ACM, 2013. 615-623