Sample Complexity of Composite Likelihood

Joseph Bradley, Carlos Guestrin
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:136-160, 2012.

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 this Paper

BibTeX
@InProceedings{pmlr-v22-bradley12, title = {Sample Complexity of Composite Likelihood}, author = {Bradley, Joseph and Guestrin, Carlos}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {136--160}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/bradley12/bradley12.pdf}, url = {https://proceedings.mlr.press/v22/bradley12.html}, 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.} }
Endnote
%0 Conference Paper %T Sample Complexity of Composite Likelihood %A Joseph Bradley %A Carlos Guestrin %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-bradley12 %I PMLR %P 136--160 %U https://proceedings.mlr.press/v22/bradley12.html %V 22 %X 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.
RIS
TY - CPAPER TI - Sample Complexity of Composite Likelihood AU - Joseph Bradley AU - Carlos Guestrin BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-bradley12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 136 EP - 160 L1 - http://proceedings.mlr.press/v22/bradley12/bradley12.pdf UR - https://proceedings.mlr.press/v22/bradley12.html AB - 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. ER -
APA
Bradley, J. & Guestrin, C.. (2012). Sample Complexity of Composite Likelihood. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:136-160 Available from https://proceedings.mlr.press/v22/bradley12.html.

Related Material