PAC-Bayesian Generalization Bound for Density Estimation with Application to Co-clustering


Yevgeny Seldin, Naftali Tishby ;
Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:472-479, 2009.


We derive a PAC-Bayesian generalization bound for density estimation. Similar to the PAC-Bayesian generalization bound for classification, the result has the appealingly simple form of a tradeoff between empirical performance and the KL-divergence of the posterior from the prior. Moreover, the PAC-Bayesian generalization bound for classification can be derived as a special case of the bound for density estimation. To illustrate a possible application of our bound we derive a generalization bound for co-clustering. The bound provides a criterion to evaluate the ability of co-clustering to predict new co-occurrences, thus introducing a supervised flavor to this traditionally unsupervised task.

Related Material