Efficient Structure Learning for CRFs and MRFs
Three CMU papers by Ni Lao, Jun Zhu, and Eric P. Xing on efficient methods for learning structure and features in graphical models.
Papers Merged
- Conditional Topical Coding: An Efficient Topic Model Conditioned on Rich Features — Zhu, Lao, Chen, Xing (CMU + Tsinghua)
- Contrastive Feature Induction for Efficient Structure Learning of Conditional Random Fields — Lao, Zhu (CMU)
- Grafting-Light: Fast, Incremental Feature Selection and Structure Learning of Markov Random Fields — Zhu, Lao, Xing (CMU)
Key Contributions
Conditional Topical Coding (CTC)
Non-probabilistic conditional topic model that avoids hard-to-compute partition functions. Uses sparse coding and coordinate descent with closed-form solutions. Faster than LDA while incorporating richer features for improved topic discovery.
Contrastive Feature Induction (CFI)
Fast feature evaluation for L1-regularized CRF structure learning using Mean Field Contrastive Divergence. Only evaluates features with high signals (deviation from mean) or errors (prediction residue). Proves gradient of candidate features is solely a function of signals and errors.
Grafting-Light
Extends the Grafting algorithm for L1-regularized MRF parameter estimation. Uses orthant-wise gradient descent for more efficient incremental feature selection compared to greedy parameter optimization.
Common Thread
All three papers address the computational challenge of working with high-dimensional feature spaces in structured prediction — finding ways to efficiently select and evaluate features without exhaustive enumeration.
Connection to Vault
Foundational ML work by Ni Lao at CMU, preceding his Path Ranking Algorithm and ProPPR research on knowledge base reasoning.