Home

Awesome

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"><HTML><HEAD <META content="IE=9.0000" http-equiv="X-UA-Compatible"> <DIV id="contentArea"> <DIV class="zone" id="mainZone"> <DIV class="compositeModule_1Zone "> <DIV class="zone"> <DIV class="title deM"><H2>Employing Semantic Context for Sparse Information Extraction Assessment</H2> <DIV class="cl"></DIV></DIV> <DIV class="conM ">   We address two problems in this paper. We first want to veri- fy the correctness of hundreds of millions of isA relationships. That is, given a candidate pair <c,e>, we want to evaluate how likely e is an entity of class c. Second, given a candidate pair <e1, e2>, and a known relationship R between classes c1 and c2, we want to evaluate whether relationship R exists between e1 and e2. <H2>Introduction</H2> The explosive growth and popularity of the World Wide Web has resulted in a huge amount of texts on the Internet, which presents an unprecedented opportunity for Information Extraction (IE). IE is at the core of many emerging applications, such as entity search, text mining, and risk analysis using financial reports. In these applications, we can divide the outcome of IE into two categories according to the frequency: heads and tails. The heads are those that occur very frequently in the corpus. For instance, we can extract the fact that "google is a company" from numerous distinct sentences. It is built on the assumption that the higher the frequency, the more likely it is correct. Nevertheless, there are results that occur very infrequently, for instance, suppose from a corpus we extract a statement that says Rhodesia(Rhodesia was an unrecognised state located in southern Africa that existed between 1965 and 1979 following its Unilateral Declaration of Independence from the United Kingdom on 11 November 1965.) is a country, and its occurrences in the corpus are few and far between. In Table 1, we show some frequent and rare candidate countries extracted from a web corpus using Hearst patterns. It turns out that all frequent entities are correct, while the majority of infrequent ones are incorrect. The mistakes come from either the extraction algorithm, or erroneous sentences in the corpus. Table 1: Frequent and infrequent candidate entities of country <table align="center"> <TR> <TD align="center">Frequent Entities</TD> <TD align="center">Rare Entities</TD> </TR> <TR> <TD align="center">India</TD> <TD align="center">Northern</TD> </TR> <TR> <TD align="center">China</TD> <TD align="center">Sabah</TD> </TR> <TR> <TD align="center">Germany</TD> <TD align="center">Yap</TD> </TR> <TR> <TD align="center">Australia</TD> <TD align="center">Parts of sudan</TD> </TR> <TR> <TD align="center">Japan</TD> <TD align="center">Wealthy</TD> </TR> <TR> <TD align="center">France</TD> <TD align="center">Western romania</TD> </TR> <TR> <TD align="center">Canada</TD> <TD align="center">American artists</TD> </TR> <TR> <TD align="center">USA</TD> <TD align="center">South korea japan</TD> </TR> <TR> <TD align="center">Brazil</TD> <TD align="center">New sjaelland</TD> </TR> <TR> <TD align="center">Italy</TD> <TD align="center">Rhodesia</TD> </TR> </table> How to verify the correctness of a tail extraction (also known as sparse extraction) is one of the most important and challenging problems in IE. As we know, the distribution of words and phrases in a corpus of natural language utterances follows the Zipf's law which states that the frequency of any word or phrase is inversely proportional to its rank in the frequency table. Thus, their occurrences in a particular syntactic pattern we use for extraction are very small. Without a good mechanism to identify correct extractions from incorrect ones, sparse information extraction will be plagued by either low precision or low recall. Existing efforts in information extraction or sparse extraction can be divided into the following four classes. Heuristic based approaches start with a set of seed entities given a relation or some prior label distributional knowledge, and identify extraction patterns for the relation iteratively. Redundancy-based approaches require that extractions appear relatively frequently with a limited set of patterns. Knowledge-based approaches identify information extraction in terms of external resources, such as Wikipedia, Freebase and WordNet. In addition, most of popular approaches in handling of sparse extractions are context-based model building approaches. They use one important hypothesis known as the distributional hypothesis, which says that different entities of the same semantic relation (such as the unary and binary relations) tend to appear in similar textual contexts. For example, we may not find many occurrences of Rhodesia in the Hearst pattern "countries such as Rhodesia". But if Rhodesia appears in similar context where terms such as India, USA, and Germany occur, then we will be more certain about the claim that Rhodesia is a country according to the distributional hypothesis. This hypothesis is beneficial to assess sparse extractions.However, the challenge lies in modeling contexts and measuring the semantic similarity of two contexts. <H2>Our Semantic Context based Approach for Assessing Sparse Information Extractions</H2> We now analyze the challenges in the tasks. The first challenge is the scale. For example, there are hundreds of millions of isA relationships (formed among 2.7 million categories and 5.5 million entities in Probase[1][2]). It is impossible to learn the generative model (such as the HMM model and the deep learning model) based on the contexts of all entities, it is very time-consuming. The second challenge lies in improving the effectiveness of the verifier. As we mentioned, the feature representation based on the contexts of words are very different that based on the contexts of entities. Meanwhile, neither a bag of words nor a set of hidden states can provide good semantics to understand the relationship between a candidate pair. Motivated by this, in this paper, we introduce a semantic, scalable, and effective approach for sparse information extraction assessment. <H3>The main contributions of this paper are as follows.</H3> First, we introduce a semantic approach for solving the two problems. More precisely, we come up with a semantic representation of the contexts. This approach is natural because we are dealing with a large semantic network, which provides semantic information in various aspects. Using these information, we are able to introduce semantic features to describe a context, which leads to a lightweight and effective solution of context learning. Second, we scan billions of web documents using MapReduce6 to capture the contexts of millions of entities and pairs of entities in Probase, and then compare the similarity between their contexts and the contexts of seeds7. We further use the similarity evaluated by our three semantic context based approaches to represent the feature space given a pair, and then train a binary-class classifier on a small number of labeled data varying with different base classifiers to select the best one for predicting sparse extractions. Extensive studies show that our approach can achieve better performance than state-of-the-art approaches in sparse extraction assessment. <H2>Data Sets </H2> Considering the experimental data sets, we randomly selected about 1800 entities that belong to 12 classes in Probase. Tables 2 and 3 show the descriptions and some examples in each class respectively. Each entity has no more than 10 occurrences in Hearst patterns and we call them sparse extractions. This is because more than 90% entities of the above 12 concepts have no more than 10 occurrences in Probase, namely lying in the long tail of the entity distribution curves. For example, Figure 2 shows the frequency distribution varying the number of entities in country. We can clearly see the long tail phenomenon under the dotted line with no more than 10 occurrences. We asked human judges to evaluate their correctness.We also looked into three binary relations: is- CapitalOf, isCurrencyOf, and headquarteredIn. We randomly picked 315 sparse extractions that have no more than 10 occurrences, and we also picked the 10 most frequent extractions for each relation which serve as seeds. Details of all test relationships are shown in Table 2. Table 2: Data sets used in experiments <TABLE align="center" class=" borderColumns borderRows tableBorder" cellSpacing="0" cellPadding="0"> <TBODY> <TR> <TD align="center"></TD> <TD align="center">total pairs in Probase</TD> <TD align="center">paris with frequency < 10 </TD> <TD align="center">pairs in experiments</TD> <TD align="center">#bad pairs</TD> <TD align="center">#good pairs</TD> </TR> <TR> <TD align="center" colspan="6">isA relationships</TD> </TR> <TR> <TD align="center">country</TD> <TD align="center">5534</TD> <TD align="center">92.81% </TD> <TD align="center">415</TD> <TD align="center">226</TD> <TD align="center">189</TD> </TR> <TR> <TD align="center">sport</TD> <TD align="center">2866</TD> <TD align="center">92.18% </TD> <TD align="center">335</TD> <TD align="center">67</TD> <TD align="center">268</TD> </TR> <TR> <TD align="center">city</TD> <TD align="center">8815</TD> <TD align="center">90.05% </TD> <TD align="center">231</TD> <TD align="center">33</TD> <TD align="center">198</TD> </TR> <TR> <TD align="center">animal</TD> <TD align="center">5562</TD> <TD align="center">92.38% </TD> <TD align="center">186</TD> <TD align="center">37</TD> <TD align="center">149</TD> </TR> <TR> <TD align="center">seasoning</TD> <TD align="center">531</TD> <TD align="center">92.47% </TD> <TD align="center">169</TD> <TD align="center">41</TD> <TD align="center">128</TD> </TR> <TR> <TD align="center">company</TD> <TD align="center">59734</TD> <TD align="center">96.84%</TD> <TD align="center">82</TD> <TD align="center">9</TD> <TD align="center">73</TD> </TR> <TR> <TD align="center">painter</TD> <TD align="center">1097</TD> <TD align="center">98.09% </TD> <TD align="center">81</TD> <TD align="center">5</TD> <TD align="center">76</TD> </TR> <TR> <TD align="center">currency</TD> <TD align="center">330</TD> <TD align="center">91.82%</TD> <TD align="center">78</TD> <TD align="center">8</TD> <TD align="center">70</TD> </TR> <TR> <TD align="center">disease</TD> <TD align="center">8280</TD> <TD align="center">92.60%</TD> <TD align="center">69</TD> <TD align="center">9</TD> <TD align="center">60</TD> </TR> <TR> <TD align="center">film</TD> <TD align="center">10859</TD> <TD align="center">96.62%</TD> <TD align="center">65</TD> <TD align="center">25</TD> <TD align="center">40</TD> </TR> <TR> <TD align="center">language</TD> <TD align="center">2703</TD> <TD align="center">93.53% </TD> <TD align="center">51</TD> <TD align="center">6</TD> <TD align="center">45</TD> </TR> <TR> <TD align="center">river</TD> <TD align="center">1924</TD> <TD align="center">97.77%</TD> <TD align="center">40</TD> <TD align="center">2</TD> <TD align="center">38</TD> </TR> <TR> <TD align="center">total</TD> <TD align="center">108235</TD> <TD align="center">92.25%</TD> <TD align="center">1802</TD> <TD align="center">468</TD> <TD align="center">1334</TD> </TR> <TR> <TD align="center" colspan="6">Binary relationships</TD> </TR> <TR> <TD align="center" colspan="3">isCapitalOf(country, city)</TD> <TD align="center">160</TD> <TD align="center">39</TD> <TD align="center">121</TD> </TR> <TR> <TD align="center" colspan="3">isCurrencyOf(country, currency)</TD> <TD align="center">80</TD> <TD align="center">19</TD> <TD align="center">61</TD> </TR> <TR> <TD align="center" colspan="3">headquarteredIn(company, city)</TD> <TD align="center">75</TD> <TD align="center">22</TD> <TD align="center">235</TD> </TR> <TR> <TD align="center" colspan="3">total</TD> <TD align="center">315</TD> <TD align="center">80</TD> <TD align="center">235</TD> </TR> </TBODY></TABLE> Table 3: Examples of isA relations <TABLE align="center" class=" borderColumns borderRows tableBorder" cellSpacing="0" cellPadding="0"> <TR> <TD align="center">isA relation</TD> <TD align="center">#bad pair</TD> <TD align="center">#good pair</TD> </TR> <TR> <TD align="center">country</TD> <TD align="center"><country, democratic people></TD> <TD align="center"><country, g77></TD> </TR> <TR> <TD align="center">city</TD> <TD align="center"><city, santa martha></TD> <TD align="center"><city, amadora></TD> </TR> <TR> <TD align="center">sport</TD> <TD align="center"><sport, trafalgar park></TD> <TD align="center"><sport, girls golf></TD> </TR> <TR> <TD align="center">animal</TD> <TD align="center"><animal, cauquenes></TD> <TD align="center"><animal, moon snail></TD> </TR> <TR> <TD align="center">seasoning</TD> <TD align="center"><seasoning, bacon bit></TD> <TD align="center"><seasoning, five spice></TD> </TR> <TR> <TD align="center">company</TD> <TD align="center"><company, institute></TD> <TD align="center"><company, hasbro></TD> </TR> <TR> <TD align="center">painter</TD> <TD align="center"><painter, robert young></TD> <TD align="center"><painter, childe hassam></TD> </TR> <TR> <TD align="center">film</TD> <TD align="center"><film, forest gump></TD> <TD align="center"><film, breach></TD> </TR> <TR> <TD align="center">language</TD> <TD align="center"><language, francophone></TD> <TD align="center"><language, micmac></TD> </TR> <TR> <TD align="center">river</TD> <TD align="center"><river, manda></TD> <TD align="center"><river, missouri river></TD> </TR> <TR> <TD align="center">isCapitalOf(country, city)</TD> <TD align="center"><dili, east timor></TD> <TD align="center"><andorra, andorra la Vella></TD> </TR> <TR> <TD align="center">isCurrencyOf(country, currency)</TD> <TD align="center"><baht, thailand></TD> <TD align="center"><colombia, colombian peso></TD> </TR> <TR> <TD align="center">headquarteredIn(company, city);</TD> <TD align="center"><espoo, general electric></TD> <TD align="center"><michelin, clermont-ferrand></TD> </TR> </TABLE> <DIV style="clear: both;"></DIV> <DIV class="conM "> <H2>Used Data Sets: Download</H2> More Details Refer to <A onclick="stc(this, 26)" href="https://github.com/peipeilihfut/AssessSparseIE/blob/master/AllDataSets.pdf" target="_new"> Used Data Sets (1) </A>. More Details Refer to <A onclick="stc(this, 26)" href="https://github.com/peipeilihfut/AssessSparseIE/blob/master/New-labeled-data-sets.pdf" target="_new"> Used Data Sets (new) </A>.</DIV> <DIV style="clear: both;"></DIV> <DIV class="conM "> <H2>Source codes: Download</H2> Our project is implemented by C# and SQL Server. Base classifiers used in our approach are from <A onclick="stc(this, 26)" href="http://www.cs.waikato.ac.nz/ml/weka/downloading.html" target="_new"> Weka-3.8.1.jar</A>. Souce codes of this project refer to <A onclick="stc(this, 26)" href="https://github.com/peipeilihfut/AssessSparseIE/blob/master/AssessSparseIEProject.rar" target="_new"> Source codes</A>. </DIV> Our AM (attribute-based context), CM (concept-based context) and IM (Isa-based context) approaches have similar parametes, we explain the parameter list of CM as an example. Main functions of these three approaches are called AMMain(string[] args), SuperConceptBasedMain(string[] args) and IMBasedMain(string[] args) in the file of "CleaningMain.cs". Parameter list for our CM approach <TABLE align="center" class=" borderColumns borderRows tableBorder" cellSpacing="0" cellPadding="0"> <TBODY> <TR><TD align="center" colspan="2">Parameter list for our CM approach</TD> </TR> <TR> <TD align="center">Variable</TD> <TD align="left">Description</TD> </TR> <TR> <TD align="center">databaseServer</TD> <TD align="left">the name of database;</TD> </TR> <TR> <TD align="center">databaseName</TD> <TD align="left">the name of database;</TD> </TR> <TR> <TD align="center">testEntityTable</TD> <TD align="left">the table of conceptualization;</TD> </TR> <TR> <TD align="center">isSelectedTopK</TD> <TD align="left">whether select Top tokens or not, 1: yes, 0: no;</TD> </TR> <TR> <TD align="center">classNumThres</TD> <TD align="left">the maximum number of concepts in conceptualization;</TD> </TR> <TR> <TD align="center">distEvalType</TD> <TD align="left">the type of distance evaluation;</TD> </TR> <TR> <TD align="center">seedsNum</TD> <TD align="left">the number of seeds;</TD> </TR> <TR> <TD align="center">bUseClustering</TD> <TD align="left">whether use clustering or not, default: false;</TD> </TR> <TR> <TD align="center">pathStr</TD> <TD align="left">directory of files;</TD> </TR> </TBODY> </TABLE> <DIV style="clear: both;"></DIV> <DIV class="conM "> <H2>References</H2> [1] Knowledgebase Probase: http://research.microsoft.com/en-us/projects/probase/release.aspx [2] W. Wu, H. Li, H. Wang, and K. Q. Zhu. Probase: a probabilistic taxonomy for text understanding. In Proceedings of SIGMOD'12, pages 481-492, 2012.<H2>Please cite the following references if you use this source code</H2> [1] Peipei Li, Haixun Wang, Hongsong Li, and Xindong Wu, Employing Semantic Context for Sparse Information Extraction Assessment, ACM Transactions on Knowledge Discovery from Data,12(5): 54:1-36, July 2018. [2] Peipei Li, Haixun Wang, Hongsong Li, and Xindong Wu, Assessing Sparse Information Extraction using Semantic Contexts, In: Proceedings of 22nd ACM International Conference on Information and Knowledge Management (CIKM’13), pp.1709-1714, San Francisco, CA, USA, 2013.10.28-11.01 </DIV> <DIV class="conM "> <H2>Contact</H2> <A title="" style="zoom: 1;" onclick="stc(this, 30)" href="http://ci.hfut.edu.cn/index/teacherinfo/tid/522" target="_new" alt="">Peipei Li</A> (peipeili@hfut.edu.cn): Hefei University of Technology, China <A title="" style="zoom: 1;" onclick="stc(this, 30)" href="http://haixun.olidu.com/" target="_new" alt="">Haixun Wang</A> (haixun@google.com): Google Research, USA <A title="" style="zoom: 1;" onclick="stc(this, 29)" target="_new" alt="">Hongsong Li</A> (hongsong.lhs@alibaba-inc.com): Alibaba Group, China <A title="" style="zoom: 1;" onclick="stc(this, 30)" href="http://www.ucs.louisiana.edu/~xxw8007/" target="_new" alt="">Xindong Wu</A> (xwu@uvm.edu): University of Louisiana at Lafayett, USA  </DIV> <DIV style="clear: both;"></DIV></DIV> <DIV style="clear: left;"></DIV></DIV></DIV></DIV> <DIV class="cl"></DIV> <DIV class="bt" id="bGrad"></DIV></DIV></DIV> </DIV> </DIV></BODY></HTML>