Proceedings

Non-Metric Label Propagation

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1357-1361.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

In many applications non-metric distances are better than metric distances in reflecting the perceptual distances of human beings. Previous studies on non-metric distances mainly focused on supervised setting and did not consider the usefulness of unlabeled data. In this paper, we present probably the first study of label propagation on graphs induced from non-metric distances. The challenge here lies in the fact that the triangular inequality does not hold for non-metric distances and therefore, a direct application of existing label propagation methods will lead to inconsistency and conflict. We show that by applying spectrum transformation, non-metric distances can be converted into metric ones, and thus label propagation can be executed. Such methods, however, suffer from the change of original semantic relations. As a main result of this paper, we prove that any non-metric distance matrix can be decomposed into two metric distance matrices containing different information of the data. Based on this recognition, our proposed NMLP method derives two graphs from the original non-metric distance and performs a joint label propagation on the joint graph. Experiments validate the effectiveness of the proposed NMLP method.Yin Zhang, Zhi-Hua Zhou

  1. [Bahlmann et al., 2002] C. Bahlmann, B. Haasdonk, and H. Burkhardt. On-line handwriting recognition with sup- port vector machines -a kernel approach. In IWFHR, pages 49-54, 2002.
  2. [Chapelle et al., 2006] O. Chapelle, B. Schölkopf, and A. Zien, ed- itors. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.
  3. [Fujino et al., 2007] A. Fujino, N. Ueda, and K. Saito. Semi- supervised learning for multi-component data classification. In IJCAI, pages 2754-2759, 2007.
  4. [Graepel et al., 1999] T. Graepel, R. Herbrich, and K. Obermayer. Classification on pairwise proximity data. In NIPS 11, pages 438-444. 1999.
  5. [Jacobs et al., 2000] D. W. Jacobs, D. Weinshall, and Y. Gdalyahu. Classification with non-metric distances: Image retrieval and class representation. IEEE Trans. Pattern Analysis and Machine Intelligence, 22(6):583-600, 2000.
  6. [Keysers et al., 2004] D. Keysers, W. Macherey, H. Ney, and J. Dahmen. Adaptation in statistical pattern recognition using tangent vectors. IEEE Trans. Pattern Analysis and Machine In- telligence, 26(2):269-274, 2004.
  7. [Kondor and Lafferty, 2002] R. I. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In ICML, pages 315-322, 2002.
  8. [Laub and Müller, 2004] J. Laub and K.-R. Müller. Feature discov- ery in non-metric pairwise data. Journal of Machine Learning Research, 5:801-818, 2004.
  9. [Laub et al., 2007] J. Laub, J. Macke, K.-R. Müller, and F. A. Wich- mann. Inducing metric violations in human similarity judge- ments. In NIPS 19, pages 777-784. 2007.
  10. [Pe ¸kalska et al., 2001] E. Pe ¸kalska, P. Paclík, and R. P. W. Duin. A generalized kernel approach to dissimilarity-based classification. Journal of Machine Learning Research, 2:175-211, 2001.
  11. [Roth et al., 2003] V. Roth, J. Laub, M. Kawanabe, and J. M. Buh- mann. Optimal cluster preserving embedding of nonmetric prox- imity data. IEEE Trans. Pattern Analysis and Machine Intelli- gence, 25(12):1540-1551, 2003.
  12. [Santini and Jain, 1999] S. Santini and R. Jain. Similarity mea- sures. IEEE Trans. Pattern Analysis and Machine Intelligence, 21(9):871-883, 1999.
  13. [Tan et al., 2006] X. Tan, S. Chen, Z.-H. Zhou, and J. Liu. Learning non-metric partial similarity based on maximal margin criterion. In CVPR, pages 138-145, 2006.
  14. [Tan et al., 2009] X. Tan, S. Chen, Z.-H. Zhou, and J. Liu. Face recognition under occlusions and variant expressions with par- tial similarity. IEEE Trans. Information Forensics and Security, 2009.
  15. [Tversky, 1977] A. Tversky. Features of similarity. Psychological Review, 84(4):327-352, 1977.
  16. [Typke et al., 2003] R. Typke, P. Giannopoulos, R. C. Veltkamp, F. Wiering, and R. van Oostrum. Using transportation distances for measuring melodic similarity. In ISMIR, pages 107-114, 2003.
  17. [Wu et al., 2005] G. Wu, E. Y. Chang, and Z. Zhang. Learning with non-metric proximity matrices. In ACM Multimedia, pages 411- 414, 2005.
  18. [Young and Householder, 1938] G. Young and A. S. Householder. Discussion of a set of points in terms of their mutual distances. Psychometrika, 3:19-22, 1938.
  19. [Zhou and Burges, 2007] D. Zhou and C. J. C. Burges. Spectral clustering and transductive learning with multiple views. In ICML, pages 1159-1166, 2007.
  20. [Zhou et al., 2004] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In NIPS 16, pages 321-328. 2004.
  21. [Zhu et al., 2003] X. Zhu, Z. Ghahramani, and J. Lafferty. Semisu- pervised learning using gaussian fields and harmonic functions. In ICML, pages 912-919, 2003.
  22. [Zhu, 2005] X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Department of Computer Sciences, Uni- versity of Wisconsin at Madison, Madison, WI, 2005.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards