Semisupervised Clustering by Queries and Locally Encodable Source Coding
Source coding is the canonical problem of data compression in information theory. In a locally encodable source coding, each compressed bit depends on only few bits of the input. In this paper, we show that a recently popular model of semi-supervised clustering is equivalent to locally encodable source coding. In this model, the task is to perform multiclass labeling of unlabeled elements. At the beginning, we can ask in parallel a set of simple queries to an oracle who provides (possibly erroneous) binary answers to the queries. The queries cannot involve more than two (or a fixed constant number of) elements. Now the labeling of all the elements (or clustering) must be performed based on the noisy query answers. The goal is to recover all the correct labelings while minimizing the number of such queries. The equivalence to locally encodable source codes leads us to find lower bounds on the number of queries required in a variety of scenarios. We provide querying schemes based on pairwise `same cluster' queries - and pairwise AND queries and show provable performance guarantees for each of the schemes.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringData CompressionSimilar Papers 제목 키워드 기반
Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding
Source coding is the canonical problem of data compression in information theory. In a locally encodable source coding, each compressed bit depends on only few bits of the input. In this paper, we show that a recently p…
ClusteringData CompressionA New Homogeneity Inter-Clusters Measure in SemiSupervised Clustering
Many studies in data mining have proposed a new learning called semi-Supervised. Such type of learning combines unlabeled and labeled data which are hard to obtain. However, in unsupervised methods, the only unlabeled da…
ClusteringRobust Graph Learning from Noisy Data
Learning graphs from data automatically has shown encouraging performance on clustering and semisupervised learning tasks. However, real data are often corrupted, which may cause the learned graph to be inexact or unreli…
ClusteringGeneral Classificationgraph constructionGraph Learning+5MiSiSUn: Minimum Simplex Semisupervised Unmixing
This paper proposes a semisupervised geometric unmixing approach called minimum simplex semisupervised unmixing (MiSiSUn). The geometry of the data was incorporated for the first time into library-based unmixing using a …
Citations as Queries: Source Attribution Using Language Models as Rerankers
This paper explores new methods for locating the sources used to write a text, by fine-tuning a variety of language models to rerank candidate sources. After retrieving candidates sources using a baseline BM25 retrieval …
RerankingRetrieval