Title: Reliable Clustering of Bernoulli Mixture Models,
Abstract: A Bernoulli Mixture Model (BMM) is a finite mixture of random binary vectors
with independent Bernoulli dimensions. The problem of clustering BMM data
arises in a variety of real-world applications, ranging from population
genetics to activity analysis in social networks. In this paper, we have
analyzed the information-theoretic PAC-learnability of BMMs, when the number of
clusters is unknown. In particular, we stipulate certain conditions on both
sample complexity and the dimension of the model in order to guarantee the
Probably Approximately Correct (PAC)-clusterability of a given dataset. To the
best of our knowledge, these findings are the first non-asymptotic (PAC) bounds
on the sample complexity of learning BMMs.