StatSnowball: a statistical approach to extracting entity relationships

ABSTRACT

Traditional relation extraction methods require pre-specified relations and relation-specific human-tagged examples. Bootstrapping systems significantly reduce the number of training examples, but they usually apply heuristic-based methods to combine a set of strict hard rules, which limit the ability to generalize and thus generate a low recall. Furthermore, existing bootstrapping methods do not perform open information extraction (Open IE), which can identify various types of relations without requiring pre-specifications. In this paper, we propose a statistical extraction framework called Statistical Snowball (StatSnowball), which is a bootstrapping system and can perform both traditional relation extraction and Open IE.

StatSnowball uses the discriminative Markov logic networks (MLNs) and softens hard rules by learning their weights in a maximum likelihood estimate sense. MLN is a general model, and can be configured to perform different levels of relation extraction. In StatSnwoball, pattern selection is performed by solving an l₁-norm penalized maximum likelihood estimation, which enjoys well-founded theories and efficient solvers. We extensively evaluate the performance of StatSnowball in different configurations on both a small but fully labeled data set and large-scale Web data. Empirical results show that StatSnowball can achieve a significantly higher recall without sacrificing the high precision during iterations with a small number of seeds, and the joint inference of MLN can improve the performance. Finally, StatSnowball is efficient and we have developed a working entity relation search engine called Renlifang based on it.

REFERENCES

• 1: Eugene Agichtein , Luis Gravano, Snowball: extracting relations from large plain-text collections, Proceedings of the fifth ACM conference on Digital libraries, p.85-94, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336644]
• 2: Galen Andrew , Jianfeng Gao, Scalable training of L¹-regularized log-linear models, Proceedings of the 24th international conference on Machine learning, p.33-40, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273501]
• 3: M. Banko, M. Cafarella, S. Soderland, M. Broadhead, and O. Etzioni. Open information extraction from the web. In IJCAI, 2007.
• 4: M. Banko and O. Etzioni. The tradeoffs between open and traditional relation extraction. In ACL, 2008.
• 5: Sergey Brin, Extracting Patterns and Relations from the World Wide Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.172-183, March 27-28, 1998
• 6: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 7: Oren Etzioni , Michael Cafarella , Doug Downey , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Unsupervised named-entity extraction from the web: an experimental study, Artificial Intelligence, v.165 n.1, p.91-134, June 2005 [doi>10.1016/j.artint.2005.03.001]
• 8: C. Giuliano, A. Lavelli, and L. Romano. Exploiting shallow linguistic information for relation extraction from biomedical literature. In EACL, 2006.
• 9: A. Harabagiu, C. A. Bejan, and P. Morcheckarescu. Shallow semantics for relation extraction. In IJCAI, 2005.
• 10: Tuyen N. Huynh , Raymond J. Mooney, Discriminative structure and parameter learning for Markov logic networks, Proceedings of the 25th international conference on Machine learning, p.416-423, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390209]
• 11: Ata Kabán, On Bayesian classification with Laplace priors, Pattern Recognition Letters, v.28 n.10, p.1271-1282, July, 2007 [doi>10.1016/j.patrec.2007.02.010]
• 12: Stanley Kok , Pedro Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning, p.441-448, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102407]
• 13: Stanley Kok , Pedro Domingos, Statistical predicate invention, Proceedings of the 24th international conference on Machine learning, p.433-440, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273551]
• 14: Stanley Kok , Pedro Domingos, Extracting Semantic Networks from Text Via Relational Clustering, Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87479-9_59]
• 15: 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
• 16: A. McCallum. Efficiently inducing features of conditional random fields. In UAI, 2003.
• 17: A. McCallum and D. Jensen. A note on the unification of information extraction and data mining using conditional probability, relational models. In IJCAI-2003 Workshop on Learning Statistical Models from Relational Data, 2003.
• 18: Z. Nie, J.-R. Wen, and W.-Y. Ma. Object-level vertical search. In CIDR, 2007.
• 19: 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]
• 20: H. Poon and P. Domingos. Joint inference in information extraction. In AAAI, 2007.
• 21: Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [doi>10.1007/s10994-006-5833-1]
• 22: Yusuke Shinyama , Satoshi Sekine, Preemptive information extraction using unrestricted relation discovery, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.304-311, June 04-09, 2006, New York, New York [doi>10.3115/1220835.1220874]
• 23: P. Singla and P. Domingos. Discriminative training of markov logic networks. In AAAI, 2005.
• 24: Choon Hui Teo , Alex Smola , S. V.N. Vishwanathan , Quoc Viet Le, A scalable modular convex solver for regularized risk minimization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281270]
• 25: R. Tibshirani. Regression shrinkage and selection via the LASSO. J. Royal. Statist. Soc., B(58):267--288, 1996.
• 26: Dmitry Zelenko , Chinatsu Aone , Anthony Richardella, Kernel methods for relation extraction, The Journal of Machine Learning Research, 3, 3/1/2003
• 27: G. Zhou, M. Zhang, D. H. Ji, and Q. Zhu. Tree kernel-based relation extraction with context-sensitive structured parse tree information. In EMNLP-CoNLL, 2005.
• 28: Jun Zhu , Zaiqing Nie , Ji-Rong Wen , Bo Zhang , Wei-Ying Ma, Simultaneous record detection and attribute labeling in web data extraction, 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.1150457]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Experimentation

Keywords:
Markov logic networks, relationship extraction, statistical models