Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle
This addresses a theoretical problem in active learning for clustering, with incremental contributions to query complexity analysis.
The paper tackles the problem of exactly learning set partitions using a same-cluster oracle with adversarial errors, establishing a connection to correlation clustering and providing worst-case query complexity bounds and analysis of adaptivity.
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.