Structure compilation: trading structure for features

ABSTRACT

Structured models often achieve excellent performance but can be slow at test time. We investigate structure compilation, where we replace structure with features, which are often computationally simpler but unfortunately statistically more complex. We analyze this tradeoff theoretically and empirically on three natural language processing tasks. We also introduce a simple method to transfer predictive power from structure to features via unlabeled data, while incurring a minimal statistical penalty.

REFERENCES

• 1: Cristian Buciluǎ , Rich Caruana , Alexandru Niculescu-Mizil, Model compression, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150464]
• 2: Collins, M. (2001). Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. International Workshop on Parsing Technologies.
• 3: Crammar, K., Kearns, M., & Wortman, J. (2007). Learning from multiple sources. Advances in Neural Information Processing Systems (NIPS).
• 4: Mark William Craven , Jude W. Shavlik, Extracting comprehensible models from trained neural networks, The University of Wisconsin - Madison, 1996
• 5: Imre Csiszár , Paul C. Shields, Information theory and statistics: a tutorial, Communications and Information Theory, v.1 n.4, p.417-528, December 2004 [doi>10.1561/0100000004]
• 6: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 7: Petrov, S., & Klein, D. (2008). Discriminative log-linear grammars with latent variables. Advances in Neural Information Processing Systems (NIPS).
• 8: Pollard, D. (1984). Convergence of stochastic processes. Springer-Verlag.
• 9: Punyakanok, V., Roth, D., Yih, W., & Zimak, D. (2005). Learning and inference over constrained output. International Joint Conference on Artificial Intelligence (IJCAI).
• 10: Sutton, C., & McCallum, A. (2005). Piecewise training of undirected models. Uncertainty in Artificial Intelligence (UAI).
• 11: Tong Zhang, Covering number bounds of certain regularized linear function classes, The Journal of Machine Learning Research, 2, p.527-550, 3/1/2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory