Select Lab Publications


Sample Complexity of Composite Likelihood (2012)

By: Joseph K. Bradley and Carlos Guestrin

Abstract: We present the first PAC bounds for learning parameters of Conditional Random Fields (CRFs) (Lafferty et al., 2001) with general structures over discrete and real-valued variables. Our bounds apply to composite likelihood (Lindsay, 1988), which generalizes maximum likelihood and pseudolikelihood (Besag, 1975). Moreover, we show that the only existing algorithm with a PAC bound for learning high-treewidth discrete models (Abbeel et al., 2006) 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.

Download Information
Joseph K. Bradley and Carlos Guestrin (2012). "Sample Complexity of Composite Likelihood." In Artificial Intelligence and Statistics (AISTATS). pdf   talk poster  
BibTeX citation

@inproceedings{Bradley-Guestrin:aistats12crfs,
title = {Sample Complexity of Composite Likelihood},
author = {Joseph K. Bradley and Carlos Guestrin},
booktitle = {In Artificial Intelligence and Statistics (AISTATS)},
month = {April},
year = {2012},
address = {La Palma, Canary Islands},
wwwfilebase = {aistats2012-bradley-guestrin},
wwwtopic = {Parameter Learning}
}



full list