Search Results

Documents authored by Ihara, Diego

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.45
Learning Lines with Ordinal Constraints

Authors: Bohan Fan, Diego Ihara, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, and Mina Valizadeh

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
We study the problem of finding a mapping f from a set of points into the real line, under ordinal triple constraints. An ordinal constraint for a triple of points (u,v,w) asserts that |f(u)-f(v)| < |f(u)-f(w)|. We present an approximation algorithm for the dense case of this problem. Given an instance that admits a solution that satisfies (1-ε)-fraction of all constraints, our algorithm computes a solution that satisfies (1-O(ε^{1/8}))-fraction of all constraints, in time O(n⁷) + (1/ε)^{O(1/ε^{1/8})} n.
Cite as

Bohan Fan, Diego Ihara, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, and Mina Valizadeh. Learning Lines with Ordinal Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fan_et_al:LIPIcs.APPROX/RANDOM.2020.45,
  author =	{Fan, Bohan and Ihara, Diego and Mohammadi, Neshat and Sgherzi, Francesco and Sidiropoulos, Anastasios and Valizadeh, Mina},
  title =	{{Learning Lines with Ordinal Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.45},
  URN =		{urn:nbn:de:0030-drops-126486},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.45},
  annote =	{Keywords: metric learning, embedding into the line, ordinal constraints, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.45
Algorithms for Metric Learning via Contrastive Embeddings

Authors: Diego Ihara, Neshat Mohammadi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{ihara_et_al:LIPIcs.SoCG.2019.45,
  author =	{Ihara, Diego and Mohammadi, Neshat and Sidiropoulos, Anastasios},
  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 =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.45},
  URN =		{urn:nbn:de:0030-drops-104492},
  doi =		{10.4230/LIPIcs.SoCG.2019.45},
  annote =	{Keywords: metric learning, contrastive distortion, embeddings, algorithms}
}
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