Document Open Access Logo

Algorithms for Metric Learning via Contrastive Embeddings

Authors Diego Ihara, Neshat Mohammadi, Anastasios Sidiropoulos

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.45.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Diego Ihara
  • University of Illinois at Chicago, USA
Neshat Mohammadi
  • University of Illinois at Chicago, USA
Anastasios Sidiropoulos
  • University of Illinois at Chicago, USA

Funding

Supported by NSF under award CAREER 1453472, and grants CCF 1815145 and CCF 1423230.

Cite As Get BibTex

Diego Ihara, Neshat Mohammadi, and Anastasios Sidiropoulos. Algorithms for Metric Learning via Contrastive Embeddings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.45

Abstract

We study the problem of supervised learning a metric space under discriminative constraints. Given a universe X and sets S, D subset binom{X}{2} of similar and dissimilar pairs, we seek to find a mapping f:X -> Y, into some target metric space M=(Y,rho), such that similar objects are mapped to points at distance at most u, and dissimilar objects are mapped to points at distance at least l. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasi-polynomial time (QPTAS). We also present an exact algorithm for learning line metric spaces with perfect information in polynomial time. Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • metric learning
  • contrastive distortion
  • embeddings
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nir Ailon and Moses Charikar. Fitting tree metrics: Hierarchical clustering and phylogeny. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 73-82. IEEE, 2005. Google Scholar
  2. Noga Alon, Mihai Bădoiu, Erik D Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos. Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. ACM Transactions on Algorithms (TALG), 4(4):46, 2008. Google Scholar
  3. Sanjeev Arora, James Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society, 21(1):1-21, 2008. Google Scholar
  4. Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):5, 2009. Google Scholar
  5. Mihai Badoiu. Approximation algorithm for embedding metrics into a two-dimensional space. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 434-443. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  6. Mihai Bădoiu, Erik D Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam. Ordinal embedding: Approximation algorithms and dimensionality reduction. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 21-34. Springer, 2008. Google Scholar
  7. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56(1-3):89-113, 2004. Google Scholar
  8. Nikhil Bansal and Ryan Williams. Regularity lemmas and combinatorial algorithms. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 745-754. IEEE, 2009. Google Scholar
  9. Yair Bartal. Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193. IEEE Computer Society, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548477.
  10. Yonatan Bilu and Nati Linial. Monotone maps, sphericity and bounded second eigenvalue. Journal of Combinatorial Theory, Series B, 95(2):283-299, 2005. Google Scholar
  11. Heinz Breu and David G Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry, 9(1-2):3-24, 1998. Google Scholar
  12. Mihai Bǎdoiu, Piotr Indyk, and Anastasios Sidiropoulos. Approximation algorithms for embedding general metrics into trees. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 512-521. Society for Industrial and Applied Mathematics, 2007. Google Scholar
  13. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. Approximating a finite metric by a small number of tree metrics. In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 379-388. IEEE, 1998. Google Scholar
  14. Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning a similarity metric discriminatively, with application to face verification. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 539-546. IEEE, 2005. Google Scholar
  15. Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures &Algorithms, 22(1):60-65, 2003. Google Scholar
  16. Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon. Information-theoretic metric learning. In Proceedings of the 24th international conference on Machine learning, pages 209-216. ACM, 2007. Google Scholar
  17. Alan Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 12-20. IEEE, 1996. Google Scholar
  18. Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175-220, 1999. Google Scholar
  19. Sariel Har-Peled. Geometric approximation algorithms, volume 173. American mathematical society Boston, 2011. Google Scholar
  20. Piotr Indyk, Jiří Matoušek, and Anastasios Sidiropoulos. Low-Distortion Embeddings of Finite Metric Spaces. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Toth, editors, Handbook of Discrete and Computational Geometry, Second Edition. Chapman and Hall/CRC, 2017. Google Scholar
  21. Philip Klein, Serge A Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682-690. ACM, 1993. Google Scholar
  22. Robert Krauthgamer and Tim Roughgarden. Metric Clustering via Consistent Labeling. Theory OF Computing, 7:49-74, 2011. Google Scholar
  23. Brian Kulis et al. Metric learning: A survey. Foundations and Trendsregistered in Machine Learning, 5(4):287-364, 2013. Google Scholar
  24. Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  25. Jiří Matoušek. Lectures on discrete geometry, volume 212. Springer Science &Business Media, 2002. Google Scholar
  26. Jiří Matoušek and Anastasios Sidiropoulos. Inapproximability for metric embeddings into ℝ^d. Transactions of the American Mathematical Society, 362(12):6341-6365, 2010. Google Scholar
  27. Amir Nayyeri and Benjamin Raichel. Reality distortion: Exact and approximate algorithms for embedding into the line. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 729-747. IEEE, 2015. Google Scholar
  28. Amir Nayyeri and Benjamin Raichel. A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 724-736. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.46.
  29. Gregory Shakhnarovich. Learning task-specific similarity. PhD thesis, Massachusetts Institute of Technology, 2005. Google Scholar
  30. Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(Feb):207-244, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact