Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle
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\'enyi-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.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningClusteringSimilar Papers 제목 키워드 기반
On Leveraging Large Language Models for Enhancing Entity Resolution: A Cost-efficient Approach
Entity resolution, the task of identifying and merging records that refer to the same real-world entity, is crucial in sectors like e-commerce, healthcare, and law enforcement. Large Language Models (LLMs) introduce an i…
Entity ResolutionQCMUQ@QALB-2015 Shared Task: Combining Character level MT and Error-tolerant Finite-State Recognition for Arabic Spelling Correction
Queries With Exact Truth Values in Paraconsistent Description Logics
We present a novel approach to querying classical inconsistent description logic (DL) knowledge bases by adopting a~paraconsistent semantics with the four Belnapian values: exactly true ($\mathbf{T}$), exactly false ($\m…
Abstraction-Free Control Synthesis to Satisfy Temporal Logic Constraints under Sensor Faults and Attacks
We study the problem of synthesizing a controller to satisfy a complex task in the presence of sensor faults and attacks. We model the task using Gaussian distribution temporal logic (GDTL), and propose a solution approa…
State EstimationGTAC: A Generative Transformer for Approximate Circuits
Targeting error-tolerant applications, approximate computing relaxes rigid functional equivalence to significantly improve power, performance, and area. Traditional approximate logic synthesis (ALS) relies on incremental…