Spanning Tree Approximations for CRFs

In this project we consider approximations for computationally intractable Conditional Random Fields (CRFs). In this setting it is important to better understand the interplay between the parameter estimation and the probabilistic inference used for the prediction.

Publications

Patrick Pletscher, Cheng Soon Ong & Joachim M. Buhmann
Spanning Tree Approximations for Conditional Random Fields
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS), 2009.
[PDF] [BibTeX]

@inproceedings{Pletscher:SpanningCRF:2009,
  author    = {Pletscher, Patrick and Ong, Cheng Soon and
               Buhmann, Joachim M.},
  title     = {Spanning Tree Approximations for Conditional Random Fields},
  booktitle = {Proceedings of the Twelfth International Conference on
               Artificial Intelligence and Statistics ({AISTATS})},
  year      = {2009},
}

Software

We implemented the spanning tree approach as part of stroll. Scripts that perform experiments similar to the ones presented in the paper are available below. This also demonstrates the usage of stroll.

spantree-aistats-0.1.1.tar.gz (Release date: 2009/04/03)

Please note: The results in the paper were generated using a prototype implementation in Matlab and C++. After the submission we decided to reimplement everything from scratch in C++ and Python. Some aspects like the parameterization of models changed slightly and thus the results obtained using the Python scripts from above might be slightly different than the ones presented in the paper. If you are interested in the original Matlab implementation, please contact the first author by email.

Data

The data used in the experiments was obtained from

We converted the multilabel data to Matlab arrays, which can be downloaded from here. You'll have to set the paths appropriately in the Python scripts.