Sample Complexity of Composite Likelihood
Abstract
We present the first PAC bounds for learning parameters of Conditional Random Fields (CRFs) with general structures over discrete and real-valued variables. Our bounds apply to composite likelihood, which generalizes maximum likelihood and pseudolikelihood. Moreover, we show that the only existing algorithm with a PAC bound for learning high-treewidth discrete models can be viewed as a computationally inefficient method for computing pseudolikelihood. We present an extensive empirical study of the statistical efficiency of these estimators, as predicted by our bounds. Finally, we use our bounds to show how to construct computationally and statistically efficient composite likelihood estimators.
Cite
Text
Bradley and Guestrin. "Sample Complexity of Composite Likelihood." Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.Markdown
[Bradley and Guestrin. "Sample Complexity of Composite Likelihood." Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.](https://mlanthology.org/aistats/2012/bradley2012aistats-sample/)BibTeX
@inproceedings{bradley2012aistats-sample,
title = {{Sample Complexity of Composite Likelihood}},
author = {Bradley, Joseph and Guestrin, Carlos},
booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics},
year = {2012},
pages = {136-160},
volume = {22},
url = {https://mlanthology.org/aistats/2012/bradley2012aistats-sample/}
}