Linear and Parallel Learning of Markov Random Fields
This addresses the challenge of scalable parameter estimation in probabilistic graphical models for researchers and practitioners in machine learning, though it appears incremental as it builds on existing methods with a focus on parallelism and efficiency.
The authors tackled the problem of parameter learning for Markov random fields by introducing a new parallel algorithm that is efficient for a large class of models, achieving linear complexity in the number of cliques for bounded-degree graphs.
We introduce a new embarrassingly parallel parameter learning algorithm for Markov random fields with untied parameters which is efficient for a large class of practical models. Our algorithm parallelizes naturally over cliques and, for graphs of bounded degree, its complexity is linear in the number of cliques. Unlike its competitors, our algorithm is fully parallel and for log-linear models it is also data efficient, requiring only the local sufficient statistics of the data to estimate parameters.