Improving discriminative sequential learning by discovering important association of statistics

ABSTRACT

Discriminative sequential learning models like Conditional Random Fields (CRFs) have achieved significant success in several areas such as natural language processing or information extraction. Their key advantage is the ability to capture various nonindependent and overlapping features of inputs. However, several unexpected pitfalls have a negative influence on the model's performance; these mainly come from a high imbalance among classes, irregular phenomena, and potential ambiguity in the training data. This article presents a data-driven approach that can deal with such difficult data instances by discovering and emphasizing important conjunctions or associations of statistics hidden in the training data. Discovered associations are then incorporated into these models to deal with difficult data instances. Experimental results of phrase-chunking and named entity recognition using CRFs show a significant improvement in accuracy. In addition to the technical perspective, our approach also highlights a potential connection between association mining and statistical learning by offering an alternative strategy to enhance learning performance with interesting and useful patterns discovered from large datasets.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Altun, Y., Hofmann, T., and Johnson, M. 2002. Discriminative learning for label sequences via boosting. In Proceedings of Neural Information Processing Systems (NIPS).
• 3: Rie Kubota Ando , Tong Zhang, A high-performance semi-supervised learning method for text chunking, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.1-9, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219841]
• 4: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 5: Carreras, X. and Marquez, L. 2003. Phrase recognition by filtering and ranking with perceptrons. In Proceedings of the Recent Advances in Natural Language Processing (RANLP). 205--216.
• 6: Chen, S. F. and Rosenfeld, R. 1999. A gaussian prior for smoothing maximum entropy models. Tech. Rep. CMU-CS-99-108. Carnegie Mellon University.
• 7: Hai Leong Chieu , Hwee Tou Ng, Named entity recognition with a maximum entropy approach, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.160-163, May 31, 2003, Edmonton, Canada [doi>10.3115/1119176.1119199]
• 8: 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]
• 9: Hal Daumé, III , Daniel Marcu, Learning as search optimization: approximate large margin methods for structured prediction, Proceedings of the 22nd international conference on Machine learning, p.169-176, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102373]
• 10: Thomas G. Dietterich , Adam Ashenfelter , Yaroslav Bulatov, Training conditional random fields via gradient tree boosting, Proceedings of the twenty-first international conference on Machine learning, p.28, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015428]
• 11: Radu Florian , Abe Ittycheriah , Hongyan Jing , Tong Zhang, Named entity recognition through classifier combination, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.168-171, May 31, 2003, Edmonton, Canada [doi>10.3115/1119176.1119201]
• 12: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 13: Dan Klein , Joseph Smarr , Huy Nguyen , Christopher D. Manning, Named entity recognition with character-level models, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.180-183, May 31, 2003, Edmonton, Canada [doi>10.3115/1119176.1119204]
• 14: Kristjansson, T., Culotta, A., Viola, P., and McCallum, A. 2004. Interactive information extraction with constrained conditional random fields. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI). 412--418.
• 15: Taku Kudo , Yuji Matsumoto, Chunking with support vector machines, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania [doi>10.3115/1073336.1073361]
• 16: Sanjiv Kumar , Martial Hebert, Discriminative Random Fields: A Discriminative Framework for Contextual Interaction in Classification, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1150, October 13-16, 2003
• 17: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 18: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 19: He, X., Zemel, R. S., and Carreira-Perpinan, M. A. 2004. Multiscale conditional random fields for image labeling. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 695--702.
• 20: 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
• 21: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 22: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 23: Liu, B., Hsu, W., and Ma, Y. 1998. Integrating classification and association rule mining. In Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD). 80--86.
• 24: Bing Liu , Wynne Hsu , Lai-Fun Mun , Hing-Yan Lee, Finding Interesting Patterns Using User Expectations, IEEE Transactions on Knowledge and Data Engineering, v.11 n.6, p.817-832, November 1999 [doi>10.1109/69.824588]
• 25: Robert Malouf, A comparison of algorithms for maximum entropy parameter estimation, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002 [doi>10.3115/1118853.1118871]
• 26: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 27: McCallum, A. 2003. Efficiently inducing features of conditional random fields. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI). 403--410.
• 28: Padmanabhan, B. and Tuzhilin, A. 1998. A belief-driven method for discovering unexpected patterns. In Proceedings of International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD). 94--100.
• 29: Fuchun Peng , Fangfang Feng , Andrew McCallum, Chinese segmentation and new word detection using conditional random fields, Proceedings of the 20th international conference on Computational Linguistics, p.562-es, August 23-27, 2004, Geneva, Switzerland [doi>10.3115/1220355.1220436]
• 30: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 31: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 32: Xuan-Hieu Phan , Le-Minh Nguyen , Tu-Bao Ho , Susumu Horiguchi, Improving discriminative sequential learning with rare--but--important associations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081906]
• 33: Rabiner, L. R. 1989. A tutorial on hidden markov models and selected applications in speech recognition. In Proceedings of IEEE 77, 2, 257--286.
• 34: Ratnaparkhi, A. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
• 35: Fei Sha , Fernando Pereira, Shallow parsing with conditional random fields, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.134-141, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073473]
• 36: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 37: Suzuki, E. 1997. Autonomous discovery of reliable exception rules. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD). 259--262.
• 38: Suzuki, E. and Shimura, M. 1996. Exceptional knowledge discovery in databases based on information theory. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD). 295--298.
• 39: Torralba, A., Murphy, K. P., and Freeman, W. T. 2004. Contextual models for object detection using boosted random fields. In Proceedings of the Conference on Neural Information Processing Systems (NIPS).
• 40: Gene Yeo , Christopher B. Burge, Maximum entropy modeling of short sequence motifs with applications to RNA splicing signals, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.322-331, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640118]
• 41: Tong Zhang , Fred Damerau , David Johnson, Text chunking based on a generalization of winnow, The Journal of Machine Learning Research, 2, 3/1/2002

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Experimentation

Keywords:
Discriminative sequential learning, association rule mining, feature selection, information extraction, text segmentation