Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle

Adela Frances DePavia, Olga Medrano Martín del Campo, Erasmo Tani
5/22/2023
cs.DScs.LGstat.ML

No confident code implementation found for this paper.

Abstract

This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error. We first highlight a novel connection between learning partitions and correlation clustering. Then we use this connection to build a Rényi-Ulam style analytical framework for this problem, and prove upper and lower bounds on its worst-case query complexity. Further, we bound the expected performance of a relevant randomized algorithm. Finally, we study the relationship between adaptivity and query complexity for this problem and related variants.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Query-Efficient Correlation Clustering with Noisy Oracle

80% match2024

Clustering with Non-adaptive Subset Queries

78% match2026

Learning Augmented Graph k-Clustering

78% match2025

Correlation Clustering with Active Learning of Pairwise Similarities

77% match2023

Graph-based Active Learning for Entity Cluster Repair

77% match2024

Replicable Clustering

77% match2023

Cite this paper

@article{depavia2023errortolerant,
  title  = {Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle},
  author = {Adela Frances DePavia and Olga Medrano Martín del Campo and Erasmo Tani},
  year   = {2023},
  eprint = {2305.13402},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2305.13402v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2305.13402.svg)](https://codeofpaper.com/paper/2305.13402)

Discussion