License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.45
URN: urn:nbn:de:0030-drops-104492
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10449/
Go to the corresponding LIPIcs Volume Portal

Ihara, Diego ; Mohammadi, Neshat ; Sidiropoulos, Anastasios

Algorithms for Metric Learning via Contrastive Embeddings

pdf-format:
LIPIcs-SoCG-2019-45.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{ihara_et_al:LIPIcs:2019:10449,
  author =	{Diego Ihara and Neshat Mohammadi and Anastasios Sidiropoulos},
  title =	{{Algorithms for Metric Learning via Contrastive Embeddings}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10449},
  URN =		{urn:nbn:de:0030-drops-104492},
  doi =		{10.4230/LIPIcs.SoCG.2019.45},
  annote =	{Keywords: metric learning, contrastive distortion, embeddings, algorithms}
}

Keywords: metric learning, contrastive distortion, embeddings, algorithms
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI