Generalization bounds for metric and similarity learning

详细信息    查看全文

• 作者：Qiong Cao ; Zheng-Chu Guo ; Yiming Ying
• 关键词：Metric learning ; Similarity learning ; Generalization bound ; Rademacher complexity
• 刊名：Machine Learning
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：102
• 期：1
• 页码：115-132
• 全文大小：539 KB
• 参考文献：Bar-Hillel, A., Hertz, T., Shental, N., & Weinshall, D. (2005). Learning a mahalanobis metric from equivalence constraints. Journal of Machine Learning Research, 6, 937–965.MATH MathSciNet
  Bartlett, P. L., & Mendelson, S. (2002). Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3, 463–482.MathSciNet
  Bousquet, O., & Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499–526.MATH MathSciNet
  Chechik, G., Sharma, V., Shalit, U., & Bengio, S. (2010). Large scale online learning of image similarity through ranking. Journal of Machine Learning Research, 11, 1109–1135.MATH MathSciNet
  Chen, D. R., Wu, Q., Ying, Y., & Zhou, D. X. (2004). Support vector machine soft margin classifiers: Error analysis. Journal of Machine Learning Research, 5, 1143–1175.MATH MathSciNet
  Clémencon, S., Lugosi, G., & Vayatis, N. (2008). Ranking and empirical minimization of U-statistics. The Annals of Statistics, 36, 844–874.MATH MathSciNet CrossRef
  Davis, J., Kulis, B., Jain, P., Sra, S., & Dhillon, I. (2007). Information-theoretic metric learning. In ICML.
  De La Peña, V. H., & Giné, E. (1999). Decoupling: From dependence to independence. New York: Springer.CrossRef
  Globerson, A., & Roweis, S. (2005). Metric learning by collapsing classes. In NIPS.
  Goldberger, J., Roweis, S., Hinton, G., & Salakhutdinov, R. (2004). Neighbourhood component analysis. In NIPS.
  Guillaumin, M., Verbeek, J., & Schmid, C. (2009). Is that you? Metric learning approaches for face identification. In ICCV.
  Hoi, S. C. H., Liu, W. , Lyu, M. R. , & Ma, W.-Y. (2006). Learning distance metrics with contextual constraints for image retrieval. In CVPR.
  Jin, R., Wang, S., & Zhou, Y. (2009). Regularized distance metric learning: Theory and algorithm. In NIPS.
  Kar, P., & Jain, P. (2011). Similarity-based learning via data-driven embeddings. In NIPS.
  Koltchinskii, V., & Panchenko, V. (2002). Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30, 1–5.MATH MathSciNet
  Ledoux, M., & Talagrand, M. (1991). Probability in Banach spaces: Isoperimetry and processes. New York: Springer Press.MATH CrossRef
  Maurer, A. (2008). Learning similarity with operator-valued large-margin classifiers. Journal of Machine Learning Research, 9, 1049–1082.MATH
  McDiarmid, C. (1989). Surveys in combinatorics, chapter on the methods of bounded differences. Cambridge, UK: Cambridge University Press.
  McFee, B., & Lanckriet, G. (2011). Learning multi-modal similarity. Journal of Machine Learning Research, 12, 491–523.MATH MathSciNet
  Rosales, R., & Fung, G. (2006). Learning sparse metrics via linear programming. In KDD.
  Shalit, O., Weinshall, D., & Chechik, G. (2010). Online learning in the manifold of low-rank matrices. In NIPS.
  Shen, C., Kim, J., Wang, L., & Hengel, A. (2009). Positive semidefinite metric learning with boosting. In NIPS.
  Weinberger, K. Q., & Saul, L. K. (2008). Fast solvers and efficient implementations for distance metric learning. In ICML.
  Xing, E., Ng, A., Jordan, M., & Russell, S. (2002). Distance metric learning with application to clustering with side information. In NIPS.
  Yang, L., & Jin, R. (2007). Distance metric learning: A comprehensive survey. Technical report, Department of Computer Science and Engineering, Michigan State University.
  Ying, Y., & Campbell. (2009). Generalization bounds for learning the kernel. In COLT.
  Ying, Y., & Campbell, C. (2010). Rademacher chaos complexity for learning the kernel problem. Neural Computation, 22, 2858–86.MATH MathSciNet CrossRef
  Ying, Y., Huang, K., & Campbell, C. (2009). Sparse metric learning via smooth optimization. In NIPS.
  Ying, Y., & Li, P. (2012). Distance metric learning with eigenvalue optimization. Journal of Machine Learning Research, 13, 1–26.MATH MathSciNet
  
• 作者单位：Qiong Cao (1)
  Zheng-Chu Guo (2)
  Yiming Ying (3)
  
  1. College of Engineering, Mathematics and Physical Sciences, University of Exeter, Harrison Building, Exeter, EX4 4QF, UK
  2. Department of Mathematics, Zhejiang University, Hangzhou, 310027, China
  3. Department of Mathematics and Statistics, State University of New York at Albany, Albany, NY, 12222, USA
  
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Automation and Robotics
  Computing Methodologies
  Simulation and Modeling
  Language Translation and Linguistics
  
• 出版者：Springer Netherlands
• ISSN：1573-0565

文摘

Recently, metric learning and similarity learning have attracted a large amount of interest. Many models and optimization algorithms have been proposed. However, there is relatively little work on the generalization analysis of such methods. In this paper, we derive novel generalization bounds of metric and similarity learning. In particular, we first show that the generalization analysis reduces to the estimation of the Rademacher average over “sums-of-i.i.d.” sample-blocks related to the specific matrix norm. Then, we derive generalization bounds for metric/similarity learning with different matrix-norm regularizers by estimating their specific Rademacher complexities. Our analysis indicates that sparse metric/similarity learning with \(L^1\)-norm regularization could lead to significantly better bounds than those with Frobenius-norm regularization. Our novel generalization analysis develops and refines the techniques of U-statistics and Rademacher complexity analysis.