2 Search Results for "Roth, Dan"

Document
DOI: 10.4230/DagRep.9.4.124
Multi-Document Information Consolidation (Dagstuhl Seminar 19182)

Authors: Ido Daga, Iryna Gurevych, Dan Roth, and Amanda Stent

Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19182 "Multi-Document Information Consolidation". At this 5-day Dagstuhl seminar, an interdisciplinary collection of leading researchers discussed and develop research ideas to address multi-documents in machine learning and NLP systems. In particular, the seminar addressed four major topics: 1) how to represent information in multi-document repositories; 2) how to support inference over multi-document repositories; 3) how to summarize and visualize multi-document repositories for decision support; and 4) how to do information validation on multi-document repositories. General talks as well as topic-specific talks were given to stimulate the discussion between the participants, which lead to various new research ideas.
Cite as

Ido Daga, Iryna Gurevych, Dan Roth, and Amanda Stent. Multi-Document Information Consolidation (Dagstuhl Seminar 19182). In Dagstuhl Reports, Volume 9, Issue 4, pp. 124-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{daga_et_al:DagRep.9.4.124,
  author =	{Daga, Ido and Gurevych, Iryna and Roth, Dan and Stent, Amanda},
  title =	{{Multi-Document Information Consolidation (Dagstuhl Seminar 19182)}},
  pages =	{124--139},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{4},
  editor =	{Daga, Ido and Gurevych, Iryna and Roth, Dan and Stent, Amanda},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.4.124},
  URN =		{urn:nbn:de:0030-drops-113572},
  doi =		{10.4230/DagRep.9.4.124},
  annote =	{Keywords: Information Consolidation, Multi-Document, NLP}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.81
Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost

Authors: Barna Saha and Sanjay Subramanian

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algorithm in this setting has access to an oracle with full knowledge of an optimal clustering, and the algorithm can ask the oracle queries of the form, "Does the optimal clustering put vertices u and v in the same cluster?" Due to its simplicity, this querying model can easily be implemented in real crowd-sourcing platforms and has attracted a lot of recent work. In this paper, we study the popular correlation clustering problem (Bansal et al., 2002) under the same-cluster querying framework. Given a complete graph G=(V,E) with positive and negative edge labels, correlation clustering objective aims to compute a graph clustering that minimizes the total number of disagreements, that is the negative intra-cluster edges and positive inter-cluster edges. In a recent work, Ailon et al. (2018b) provided an approximation algorithm for correlation clustering that approximates the correlation clustering objective within (1+epsilon) with O((k^{14} log{n} log{k})/epsilon^6) queries when the number of clusters, k, is fixed. For many applications, k is not fixed and can grow with |V|. Moreover, the dependency of k^14 on query complexity renders the algorithm impractical even for datasets with small values of k. In this paper, we take a different approach. Let C_{OPT} be the number of disagreements made by the optimal clustering. We present algorithms for correlation clustering whose error and query bounds are parameterized by C_{OPT} rather than by the number of clusters. Indeed, a good clustering must have small C_{OPT}. Specifically, we present an efficient algorithm that recovers an exact optimal clustering using at most 2C_{OPT} queries and an efficient algorithm that outputs a 2-approximation using at most C_{OPT} queries. In addition, we show under a plausible complexity assumption, there does not exist any polynomial time algorithm that has an approximation ratio better than 1+alpha for an absolute constant alpha > 0 with o(C_{OPT}) queries. Therefore, our first algorithm achieves the optimal query bound within a factor of 2. We extensively evaluate our methods on several synthetic and real-world datasets using real crowd-sourced oracles. Moreover, we compare our approach against known correlation clustering algorithms that do not perform querying. In all cases, our algorithms exhibit superior performance.
Cite as

Barna Saha and Sanjay Subramanian. Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 81:1-81:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{saha_et_al:LIPIcs.ESA.2019.81,
  author =	{Saha, Barna and Subramanian, Sanjay},
  title =	{{Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{81:1--81:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.81},
  URN =		{urn:nbn:de:0030-drops-112020},
  doi =		{10.4230/LIPIcs.ESA.2019.81},
  annote =	{Keywords: Clustering, Approximation Algorithm, Crowdsourcing, Randomized Algorithm}
}
  • Refine by Author
  • 1 Daga, Ido
  • 1 Gurevych, Iryna
  • 1 Roth, Dan
  • 1 Saha, Barna
  • 1 Stent, Amanda
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Unsupervised learning and clustering

  • Refine by Keyword
  • 1 Approximation Algorithm
  • 1 Clustering
  • 1 Crowdsourcing
  • 1 Information Consolidation
  • 1 Multi-Document
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2019

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 Imprint Privacy Contact