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 = {Joseph Bradley and Carlos Guestrin}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {136--160}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 136--160 %U http://proceedings.mlr.press %V 22 %W PMLR %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 PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-bradley12 PB - PMLR SP - 136 DP - PMLR EP - 160 L1 - http://proceedings.mlr.press/v22/bradley12/bradley12.pdf UR - http://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 PMLR 22:136-160

Related Material