skip to main content
10.1145/1553374.1553467acmotherconferencesArticle/Chapter ViewAbstractPublication PagesicmlConference Proceedingsconference-collections
research-article

Partial order embedding with multiple kernels

Published: 14 June 2009 Publication History

Abstract

We consider the problem of embedding arbitrary objects (e.g., images, audio, documents) into Euclidean space subject to a partial order over pair-wise distances. Partial order constraints arise naturally when modeling human perception of similarity. Our partial order framework enables the use of graph-theoretic tools to more efficiently produce the embedding, and exploit global structure within the constraint set.
We present an embedding algorithm based on semidefinite programming, which can be parameterized by multiple kernels to yield a unified space from heterogeneous features.

References

[1]
Agarwal, S., Wills, J., Cayton, L., Lanckriet, G., Kriegman, D., & Belongie, S. (2007). Generalized non-metric multi-dimensional scaling. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics.
[2]
Aho, A. V., Garey, M. R., & Ullman, J. D. (1972). The transitive reduction of a directed graph. SIAM Journal on Computing, 1, 131--137.
[3]
Bilenko, M., Basu, S., & Mooney, R. J. (2004). Integrating constraints and metric learning in semi-supervised clustering. Proceedings of the Twenty-first International Conference on Machine Learning (pp. 81--88).
[4]
Cox, T. F., & Cox, M. A. (1994). Multidimensional scaling. Chapman and Hall.
[5]
Geusebroek, J. M., Burghouts, G. J., & Smeulders, A. W. M. (2005). The Amsterdam library of object images. Int. J. Comput. Vis., 61, 103--112.
[6]
Globerson, A., & Roweis, S. (2007). Visualizing pairwise similarity via semidefinite embedding. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics.
[7]
Hadsell, R., Chopra, S., & LeCun, Y. (2006). Dimensionality reduction by learning an invariant mapping. Computer Vision and Pattern Recognition.
[8]
Kruskal, J. (1964). Nonmetric multidimensional scaling: a numerical method. Psychometrika, 29.
[9]
Lanckriet, G. R. G., Cristianini, N., Bartlett, P., Ghaoui, L. E., & Jordan, M. I. (2004). Learning the kernel matrix with semidefinite programming. J. Mach. Learn. Res., 5, 27--72.
[10]
Löfberg, J. (2004). Computer Aided Control Systems Design, 2004 IEEE International Symposium on, 284--289.
[11]
Opatrny, J. (1979). Total ordering problem. SIAM J. Computing, 111--114.
[12]
Roth, V., Laub, J., Buhmann, J. M., & Müüller, K.-R. (2003). Going metric: denoising pairwise data. Advances in Neural Information Processing Systems 15 (pp. 809--816). Cambridge, MA: MIT Press.
[13]
Schölkopf, B., Herbrich, R., Smola, A. J., & Williamson, R. (2001). A generalized representer theorem. Proceedings of the 14th Annual Conference on Computational Learning Theory (pp. 416--426).
[14]
Schultz, M., & Joachims, T. (2004). Learning a distance metric from relative comparisons. Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press.
[15]
Song, L., Smola, A., Borgwardt, K., & Gretton, A. (2008). Colored maximum variance unfolding. Advances in Neural Information Processing Systems (pp. 1385--1392). Cambridge, MA: MIT Press.
[16]
Sturm, J. F. (1999). Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization methods and software, 11--12, 625--653.
[17]
Tsang, I. W., & Kwok, J. T. (2003). Distance metric learning with kernels. International Conference on Artificial Neural Networks (pp. 126--129).
[18]
Varga, R. (2004). Geršgorin and his circles. Springer-Verlag.
[19]
Wagstaff, K., Cardie, C., Rogers, S., & Schroedl, S. (2001). Constrained k-means clustering with background knowledge. Proceedings of the Eighteenth International Conference on Machine Learning (pp. 577--584).
[20]
Weinberger, K. Q., Blitzer, J., & Saul, L. K. (2006). Distance metric learning for large margin nearest neighbor classification. Advances in Neural Information Processing Systems 18 (pp. 451--458). Cambridge, MA: MIT Press.
[21]
Weinberger, K. Q., Sha, F., & Saul, L. K. (2004). Learning a kernel matrix for nonlinear dimensionality reduction. Proceedings of the Twenty-first International Conference on Machine Learning (pp. 839--846).
[22]
Xing, E. P., Ng, A. Y., Jordan, M. I., & Russell, S. (2003). Distance metric learning, with application to clustering with side-information. Advances in Neural Information Processing Systems 15 (pp. 505--512). Cambridge, MA: MIT Press.

Cited By

View all
  • (2022)Design patterns mining using neural sub-graph matchingProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507073(1545-1553)Online publication date: 25-Apr-2022
  • (2022)A Chinese L2 Learners' Dynamic Vocabulary Growth Network Model Based on Graph Deep Learning2022 4th International Conference on Computer Science and Technologies in Education (CSTE)10.1109/CSTE55932.2022.00035(156-163)Online publication date: May-2022
  • (2022)Approximating Permutations with Neural Network Components for Travelling Photographer Problem2022 Asia Conference on Algorithms, Computing and Machine Learning (CACML)10.1109/CACML55074.2022.00036(171-180)Online publication date: Mar-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning
June 2009
1331 pages
ISBN:9781605585161
DOI:10.1145/1553374

Sponsors

  • NSF
  • Microsoft Research: Microsoft Research
  • MITACS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2009

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

ICML '09
Sponsor:
  • Microsoft Research

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)1
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Design patterns mining using neural sub-graph matchingProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507073(1545-1553)Online publication date: 25-Apr-2022
  • (2022)A Chinese L2 Learners' Dynamic Vocabulary Growth Network Model Based on Graph Deep Learning2022 4th International Conference on Computer Science and Technologies in Education (CSTE)10.1109/CSTE55932.2022.00035(156-163)Online publication date: May-2022
  • (2022)Approximating Permutations with Neural Network Components for Travelling Photographer Problem2022 Asia Conference on Algorithms, Computing and Machine Learning (CACML)10.1109/CACML55074.2022.00036(171-180)Online publication date: Mar-2022
  • (2017)Learning a Distance Metric from Relative Comparisons between Quadruplets of ImagesInternational Journal of Computer Vision10.1007/s11263-016-0923-4121:1(65-94)Online publication date: 1-Jan-2017
  • (2016)Hubbub-scaleProceedings of the 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing10.1109/CCGrid.2016.71(233-244)Online publication date: 16-May-2016
  • (2016)Sparsity analysis versus sparse representation classifierNeurocomputing10.1016/j.neucom.2015.06.052171:C(387-393)Online publication date: 1-Jan-2016
  • (2016)Linear unsupervised hashing for ANN search in Euclidean spaceNeurocomputing10.1016/j.neucom.2015.06.036171:C(283-292)Online publication date: 1-Jan-2016
  • (2016)Evaluating the classifier behavior with noisy data considering performance and robustnessNeurocomputing10.1016/j.neucom.2014.11.086176:C(26-35)Online publication date: 2-Feb-2016
  • (2016)On random hyper-class random forest for visual classificationNeurocomputing10.1016/j.neucom.2014.10.101172:C(281-289)Online publication date: 8-Jan-2016
  • (2016)Semi-supervised image clustering with multi-modal informationMultimedia Systems10.1007/s00530-014-0433-622:2(149-160)Online publication date: 1-Mar-2016
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media