Nonlinear Evidence Fusion and Propagation for Hyponymy Relation Mining

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1159–1168, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Nonlinear Evidence Fusion and Propagation for Hyponymy Relation Mining Fan Zhang2* Shuming Shi1 Jing Liu2 Shuqi Sun3* Chin-Yew Lin1 1Microsoft Research Asia 2Nankai University, China 3Harbin Institute of Technology, China {shumings, cyl}@microsoft.com Abstract This paper focuses on mining the hypon- ymy (or is-a) relation from large-scale, open-domain web documents. A nonlinear probabilistic model is exploited to model the correlation between sentences in the aggregation of pattern matching results. Based on the model, we design a set of ev- idence combination and propagation algo- rithms. These significantly improve the result quality of existing approaches. Ex- perimental results conducted on 500 mil- lion web pages and hypernym labels for 300 terms show over 20% performance improvement in terms of P@5, MAP and R-Precision. 1 Introduction1 An important task in text mining is the automatic extraction of entities and their lexical relations; this has wide applications in natural language pro- cessing and web search. This paper focuses on mining the hyponymy (or is-a) relation from large- scale, open-domain web documents. From the viewpoint of entity classification, the problem is to automatically assign fine-grained class labels to terms. There have been a number of approaches (Hearst 1992; Pantel & Ravichandran 2004; Snow et al., 2005; Durme & Pasca, 2008; Talukdar et al., 2008) to address the problem. These methods typi- cally exploited manually-designed or automatical- * This work was performed when Fan Zhang and Shuqi Sun were interns at Microsoft Research Asia ly-learned patterns (e.g., “NP such as NP”, “NP like NP”, “NP is a NP”). Although some degree of success has been achieved with these efforts, the results are still far from perfect, in terms of both recall and precision. As will be demonstrated in this paper, even by processing a large corpus of 500 million web pages with the most popular pat- terns, we are not able to extract correct labels for many (especially rare) entities. Even for popular terms, incorrect results often appear in their label lists. The basic philosophy in existing hyponymy ex- traction approaches (and also many other text- mining methods) is counting: count the number of supporting sentences. Here a supporting sentence of a term-label pair is a sentence from which the pair can be extracted via an extraction pattern. We demonstrate that the specific way of counting has a great impact on result quality, and that the state-of- the-art counting methods are not optimal. Specifi- cally, we examine the problem from the viewpoint of probabilistic evidence combination and find that the probabilistic assumption behind simple count- ing is the statistical independence between the ob- servations of supporting sentences. By assuming a positive correlation between supporting sentence observations and adopting properly designed non- linear combination functions, the results precision can be improved. It is hard to extract correct labels for rare terms from a web corpus due to the data sparseness prob- lem. To …

Content truncated to 500 words