Sparse higher order conditional random fields for improved sequence labeling

ABSTRACT

In real sequence labeling tasks, statistics of many higher order features are not sufficient due to the training data sparseness, very few of them are useful. We describe Sparse Higher Order Conditional Random Fields (SHO-CRFs), which are able to handle local features and sparse higher order features together using a novel tractable exact inference algorithm. Our main insight is that states and transitions with same potential functions can be grouped together, and inference is performed on the grouped states and transitions. Though the complexity is not polynomial, SHO-CRFs are still efficient in practice because of the feature sparseness. Experimental results on optical character recognition and Chinese organization name recognition show that with the same higher order feature set, SHO-CRFs significantly outperform previous approaches.

REFERENCES

• 1: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 2: Michael Collins, Ranking algorithms for named-entity extraction: boosting and the voted perceptron, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073165]
• 3: Ugo Galassi , Attilio Giordana , Lorenza Saitta, Structured Hidden Markov Model: A General Framework for Modeling Complex Sequences, Proceedings of the 10th Congress of the Italian Association for Artificial Intelligence on AI*IA 2007: Artificial Intelligence and Human-Oriented Computing, September 10-13, 2007, Rome, Italy [doi>10.1007/978-3-540-74782-6_26]
• 4: Jin, G., & Chen, X. (2008). The fourth international chinese language processing bakeoff: Chinese word segmentation, named entity recognition and chinese pos tagging. Proceedings of Sixth Special Interest Group on Chinese Language Processing Workshop (pp. 69--81).
• 5: 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
• 6: Dan Roth , Wen-tau Yih, Integer linear programming inference for conditional random fields, Proceedings of the 22nd international conference on Machine learning, p.736-743, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102444]
• 7: Sarawagi, S., & Cohen, W. (2004). Semi-markov conditional random fields for information extraction. Advances in Neural Information Processing Systems (pp. 1185--1192).
• 8: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin markov networks. Advances in Neural Information Processing Systems (pp. 25--32).
• 9: Yang, F., Zhao, J., & Zou, B. (2008). CRFs-based named entity recognition incorporated with heuristic entity list searching. Proceedings of Sixth Special Interest Group on Chinese Language Processing Workshop (pp. 171--174).
• 10: Yu, X., Lam, W., Chan, S.-K., Wu, Y., & Chen, B. (2008). Chinese NER using CRFs and logic for the fourth sighan bakeoff. Proceedings of Sixth Special Interest Group on Chinese Language Processing Workshop (pp. 102--105).

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.3 Deduction and Theorem Proving
          Subjects: Inference engines
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory