Cross Lingual Entity Linking with Bilingual Topic Model

1 Introduction

The web is growing rapidly, which can be reflected by the number of Internet user and the amount of web content on the Internet. It has become a central goal for search engine company to maximize the user's satisfaction. Moreover, since a user's query useually expresses the information need of a named entity, it would be very useful if a general search engine could automatically discover information about named entities. The emergence of large scale knowledge base like Wikipedia and DBpedia has facilitated this problem. These knowledge bases are usually written in English. However, according to a report of August, 2008 1 , there are 90

1

http://www.imakenews.com/lweaver/e_article001189962.cfm?x=b dhk3s9,b4wmV4K7

billion web pages on Internet and 31% of them are written in other languages. This report tells us that the percentage of web pages written in English are decreasing, which indicates that English pages are becoming less dominant compared with before. Therefore, it becomes more and more important to maintain the growing knowledge base by discovering and extracting information from all web contents written in different languages. Also, inserting new extracted knowledge derived from the information extraction system into a knowledge base inevitably needs a system to map the entity mentions in one language to their entries in a knowledge base which may be another language. This task is known as cross-lingual entity linking.

Intuitively, to resolve the cross-lingual entity linking problem, the key is how to define the similarity score between the context of entity mention and the document of candidate entity. Once the similarity score is defined, the system can select the entity with the highest score as the answer in an unsupervised way or use it as a feature in a supervised framework. However, the context of the entity mention and the document associated with the entity are described using different languages. Thus, the traditional BOW model, which is based on exact matching of terms between the query and candidate entity, is not suitable for the cross-lingual entity linking task.

To overcome this problem, many methods have been proposed. Previous studies [McNamee et al., 2011] usually use statistical machine translation tool to first translate the original document contexts into English equivalents and transform the cross-lingual problem into a monolingual entity linking problem. However, the performance of the entity linking system is highly depended on the performance of the statistical machine translation system. In order to train the statistical machine translation system, one must obtain parallel corpora in which texts in one language and their translation in other language are well aligned at word or sentence level. Such corpora are usually edited by human editors in specific domain. Obtaining such corpora is expensive. Therefore, the machine translation based method is not easy to adapt to other languages.

Other researchers develop explicit semantic model for this problem [Fahrni et al., 2011]. They regard the entity linking problem as an information retrieval problem and believe that the cross-lingual entity linking is the extreme case of the vocabulary mismatch problem. To overcome this, they map texts with respect to the given Wikipedia concepts using ESA method [Gabrilovich and Markovitch, 2007] and do entity linking in the space of Wikipedia concept. Multilingual knowledge base is needed for this method. However, the size of different knowledge base is different. For example, the English version Wikipedia in 2009 contains 3,000,000 articles, while the Chinese version Wikipedia only contain 300,000 articles, which is far small from the English version. This will cause the problem that large percentage of English Wikipedia concept have no corresponding Chinese concept, thus influence the performance of the method.

Inspired by the idea of using external data source mentioned above, we present a general framework for building cross lingual entity linking system with hidden topics discovered from large-scale parallel corpora. Wikipedia, which was launched in 2001, has become a very big multilingual data resource. In Wikipedia, each article describes a concept and each concept is usually described by different languages. The articles written in different language but describing the same concept are quite related in their hidden topic. It is interesting to use topic modeling algorithms to mine cross lingual topics from Wikipedia. Topic modeling has been widely used by various text applications [Phan et al., 2008; Titov and McDonald, 2008]. Typical topic modeling methods include LDA [Blei et al., 2003]. LDA can be seen as a typical probabilistic approach to latent topic computation. Each topic is represented by a distribution of words (probabilistic language model) and each word has a probability score used to measure its contribution to the topic.

In this paper, we propose a novel bilingual topic model to modeling bilingual topics from Wikipedia data in two different languages. A topic is inherently bilingual: each has two types of representation and each representation corresponds to one language. The same Wikipedia concept described by different language follows that constrain of sharing one identical topic distribution. Based on this framework, we represent the query and the candidate entity using as the distribution of semantic topic. The similarity of a query and an candidate entity is computed as the cosine similarity between their vectors in the semantic space. This is illustrated in Figure 1. Experiments on the standard cross-lingual entity linking dataset show that our approach is promising. Different from previous research work, our approach does not require additional linguistic resources like dictionaries or translation tools. In addition, once the topic model is estimated, it can be applied to other cross lingual task provided that they are consistent.

The reminder of this paper is organized as follows. In the next section we briefly discuss related work on entity linking task. Section 3 describes our bilingual topic model in detail. Cross-lingual entity linking is presented in Section 4. We then present the experimental results in section 5. Section 6 concludes the paper and presents the future work.

2 Related Work

The first type of research related to our work is about entity linking. Many researchers developed entity linking systems based on the context similarity between the query and the candidate entities. Various approaches represent different methods in computing the similarity. Cucerzan [2007] developed a disambiguation approach based on the agreement between the contextual information of candidate entities and the query, as well as the agreement among the category tags associated with candidate entities. Bunescu and Pasca [2006] trained a disambiguation SVM kernel on the Wikipedia data, the similarity between query and candidate entity was computed based on the SVM kernel, the linking system thus selected the entity with the highest similarity as the answer. Han and Zhao [2009] constructed a large-scale semantic network from Wikipedia, and computed the similarity between query and candidate entity based on the constructed semantic network. Radford et al. [2010] applied a Graph-Based ranking method in their entity linking system, context entities were taken into account in order to reach a global optimized solution. Han and Sun [2011] proposed a generative probabilistic model, which can leverage the entity popularity knowledge, name knowledge, and context knowledge for the entity linking task. Other researchers developed supervised learning approach for the entity linking task. Milne and Witten [2008] proposed a machine learning approach to disambiguation that use the links found within Wikipedia articles for training. The two main features they used in their classifier were the commonness of each candidate entity and its relatedness to the surrounding context. Dredze et al. [2010] employed a learning to rank method to disambiguate candidate entities. A comprehensive feature set was used in their system. Zhang et al. [2010] proposed a method to automate generate a large-scale corpus, which were used to train a binary classifier. Zhang et al. [2011] employed a Wikipedia-LDA model to model the contexts as the probability distributions over Wikipedia categories and used this model to compute the similarity between the query and the candidate entities. Such semantic similarity was considered as an important feature in their framework. Dai et al. [2011] employed a Markov logic network in handling this task, but they only conducted experiments in biomedical domain. Shen et al. [2012] proposed a system called LINDEN that can leverage the rich semantic knowledge embedded in the Wikipedia and the taxonomy of the knowledge base. For cross-lingual entity linking task, McNamee et al. [2011] use statistical machine translation tool to first translate the original document contexts into English equivalents and transform the cross-lingual problem into a monolingual entity linking problem. Fahrni et al. [2011] they map texts with respect to the given Wikipedia concepts and do entity linking in the space of Wikipedia concept.

The second type of research related to our work is about the use of topic model in text application. Phan et al. [2008] utilized the LDA models estimated from Wikipedia to help classify short text segment. Ni et al. [2011] utilized LDA models to extract topics from Wikipedia documents and use these topics to do cross lingual text classification. Titov and McDonald [2008] present a novel multi-grain topic model for extracting the ratable aspects of objects from online user reviews. Similay to our work in [Mimmo et al., 2009], they propose a polylingual topic model that discovers topics aligned across multiple languages and demonstrate its usefulness in supporting machine translation..

3 Bilingual Topic Modeling

As discussed in the preceding section, our goal is to provide a method for computing similarity score between the context of entity mention and the document of an entity in different languages. We use bilingual topic model method, which represent document as mixtures of latent topics, to address this problem. In this section, we will first introduce LDA briefly. And then, we describe the bilingual topic model and its estimation method.

3.1 Latent Dirichlet Allocation (LDA)

We will give a brief introduction to Latent Dirichlet Allocation (LDA). LDA is a generative graphical model as shown in Figure 2. It can be used to model and discover underlying topic structure of any kind of discrete data in which text is a typical example. In LDA, generation of a collection is started by sampling a word distribution from a prior Dirichlet distribution dir( ) for each latent topic. Then a document is first generated by picking a distribution over topics from a dirichlet distribution dir( ), which determines topic assignment for words in that document. Then the topic assignment for each word is performed by sampling a topic from topic distribution Mult( ). And finally, a particular word w is generated from the distribution of multionmial distribution.

According to the generative graphical model depicted in Figure 2, the joint distribution of all known and hidden variables can be written as:

And the marginal distribution of a document can be obtained by integrating over and , and summing over z as follows

Finally, the probability of the whole collection W={ , ,…, }can be obtained by taking the product of the likelihood of all single document as follows:

The parameters of LDA can be estimated by directly and exactly maximizing the likelihood of the whole data collection. However, exact inference is intractable. The solution to this is to use approximate estimation methods such as Variational EM and Gibbs Sampling [Heinrich, 2005]. Gibbs Sampling is a special case of Markov-chain Monte Carlo (MCMC) and often yields relatively simple algorithms for approximate inference in high-dimensional models such as LDA.

K: the number of hidden (latent) topics

M: the total number of documets

:hyper parameters for Dirichlet distribuation

:topic distribuation for document m

: the length of document m

: topic index of the n-th word in document m

: a particular word in document m

: word distribuation for topic k

: a particular document

Table 1: Notations of LDA

3.2 Bilingual Latent Dirichlet Allocation

In this section, we introduce bilingual Latent Dirichlet Allocation model. The bilingual LDA model is an extension of latent Dirichlet allocation (LDA) for modeling bilingual document tuple. Each tuple is a pair of documents that are semantically related to each other, but written in different languages. We assume all documents in a tuple share the same topic distribution. Also, BLDA assumes that each "topic" consists of a set of discrete distributions over words, which corresponds each language. Figure 2 presents the graphical model of BLDA.

A new document is generated by first drawing a tuple-specific topic distribution from a Dirichlet prior. Then for each word in document, a latent topic distribution is drawn from multinomial distribution. Finally, the observed word is drawn using the language-specific topic multinomial distribution. The generation process of BLDA is shown in Figure 4

For each tuple-specifc topic z, z=1,2,…,K For each language l Sample word distribution For each tuple in a corpus Sample topic distribution For each document in tuple For each word in document Sample topic from distribution Mult( ) Sample word from distribution Mult( )

From the generative process in Figure 3, we can write the joint distribution of all known and hidden variables given the Dirichlet parameters for a specific language j as follows:

The marginal distribution of a document w for a specific language j can be obtained as follows:

3.3 BLDA Estimation

In this section, we will present a modification of Gibbs Sampling method for the estimation of BLDA.

The first use of Gibbs Sampling for estimating LDA is reported in [Griffiths and Steyvers, 2004] and a more comprehensive description of this method is from the technical report [Heinrich, 2005]. One can refer to these papers for a better understanding of this sampling technique. Here, we only show the most important formula that is used for topic sampling for words. In order to apply Gibbs Sampling, we need to compute the conditional probability , where means the vector of all words in language of the whole data collection D and denotes the vector of topic assignment except the considered word at position i in the document item written in language of tuple m. The topic assignment for a particular word depends on the current topic assignment of all the other word positions in the same language. More specifically, the topic assignment of a particular word t of language is sampled from the following multinomial distribution:

Where is the number of times word t of language j is assigned to topic k except the current assignment; is the total number of words in language assigned to topic k except the current assignment; and is the number of words in tuple-unit m assigned to topic k except the current assignment; and is the total number of words in tuple-unit m except the current word t.

After finishing Gibbs Sampling, we can obtain the multionmil parameter sets and as follows:

We can obtain the marginal distribution of a tuple as follows:

Where denotes a tuple document set.

Finally, the probability of the whole document collection W = is obtained as follows:

4 Cross-lingual Entity Linking

Choosing an appropriate document-aligned comparable training data is extremely important for mining bilingual topics in bilingual LDA model. The data should large enough and should balanced distributions over words and topics, and more importantly, should deal well with the diversity of future unseen data. In this section, we will empirically investigate the effectiveness of BLDA for mining bilingual topics from Wikipedia.

4.1 Hidden Topics from Wikipedia

Today, the growth of the web, and in particular Wikipedia, has made comparable text corpora-documents that are topically similar of one another. In our work, we first build a document-aligned comparable corpus from Wikipedia. We downloaded XML copies of all Wikipedia articles in two languages: Chinese, English. The corpus is available at this address: http://download.wikipedia.org. We preprocessed the data by removing tables, references, images and info-boxes. We dropped articles which are written in only one language. Finally, we got a total of 750M with more than 150,000 parallel Wikipedia articles. This collection covers a lot of concepts and domains, such as sport, computer science, internet, business, political and so on. It is reasonable to use it as a bilingual comparable dataset. Our BLDA model is general enough and can be easily applied on multilingual corpus without additional efforts.

We estimated our BLDA models for the Wikipedia data using JGibbLDA, which is a java implementation of LDA using Gibbs Sampling. We set the hyper parameters alpha and beta to be 50/k and 0.1 respectively, where k is the number of topics. The number of topics ranges from 10 to 150, with 10 as the step size. We estimated the model using 1000 Gibbs Sampling iterations. Figure 5 shows some example universal-topics produced by BLDA with K=100. We oberved that the outputs are impressive and satisfy our exception.

4.2 Topic Inference for New Documents

Given a new document in language j, we need to do topic inference using our BLDA model. Gibbs Sampling is performed for topic inference, however, the number of sampling iterations for inference is much smaller than that for the parameter estimation. We observed that 20 iterations are enough for topic inference.

Let and be the vectors of all words and their topic assignment of the document-aligned comparable corpus in language . And and are the vectors of all words and their topic assignment of the new document. The topic assignment for a particular word in t in depends on the current topics of all the other words in and the topics of all words in as follows:

Where is the number of times t is assigned to topic k in d except the current assignment; is the number of words in d assigned to topic k except the current assignment; is the number of words in d that are assigned to topic k except the current assignment; is the total number of words in d except the current word t.

After performing topic sampling, the document in any language can be represented as , where each distribution is computed as follows:

4.3 Cross Lingual Entity Linking

The first step in our cross lingual entity linking framework is to find candidate entity in a Knowledge Base for a given entity mention. The candidate entity means the entity in the knowledge base that this entity mention may refer to. We leverage the knowledge sources in Wikipedia to find candidate entity, including "entity pages", "disambiguation pages", "redirect pages" and "anchor text". After obtaining the candidate entity in one language, we can obtained its other language form using existing translated link in Wikipedia. For example, given an entity mention in Chinese " (Jordan)", we can obtain its candidate entity in English knowledge such as "Michael Jeffrey Jordan", "Michael I. Jordan" and so on.

The second step is to define a similarity score for each candidate entity. Our system selects the candidate entity with the biggest score as the answer. Even though the document of entity and the context of the query are written in different language, we can represent them in the same semantic topic space using BLDA model. Thus, the similarity score can be computed by the inner product of their topic distribution vector.

5 Experiments and Results

In this section, we evaluate our method in the KBP dataset to demonstrate the effectiveness of our approach.

5.1 Dataset

In our experiment, the knowledge base is derived from Wikipedia pages that contain an infobox. It consists of roughly 818 thousand distinct entities. The KBP 2011 dataset is used as our test dataset. The dataset contains 2176 queries and query document come from news wire and Web pages. Micro-Averaged Accuracy is adopted as the performance measure in our experiment. It was used in KBP 2011 [Ji et al., 2011] as the official metric to evaluate the performance of entity linking.

5.2 Parameters Turning

There are several parameters that need to be determined in our models. The first is the number of universal-topics. The second is the number of Gibbs Sampling iterations.

The first experiment is to see how entity linking accuracy change if we change the universal-topic number.We estimated many BLDA models for the wikipedia data with different number of topics (from 10 to 150). The change of the entity linking accuracy is depicted in Figure 6.We can see that the optimal results can be obtained with 100 universal-topics. Moreover, the accuracy is quite stable when the number of topic change from 100 to 150.

The next experiment is to see how Gibbs Sampling influences the performance of the entity linking system. We trained different BLDA models using the Wikipedia data with different numbers of topics. We ran 1000 Gibbs iterations to estimate the parameters, and saved the estimated model at every 200 iterations. At these saving point, we used the estimaed model to performe topic inference for the entity mention document and the candidate entity, and then performed cross-lingual entity linking using their topic distribuation vector. The results are shown in Figure 7. From Figure 7, we can see that the performance of the cross-lingual entity linking system is robust with respect to the number of different numbers of Gibbs Sampling iterations. Although it is hard to control the number of Gibbs Sampling iterations, we found that it yields stable results after 200 iterations.

5.3 Comparison with other state-of-art method

In order to further demonstarte the effectiveness of our proposed approach, we compared it with other two other recently proposed methods in KBP 2011. The first approach [McNamee et al., 2011] is a translation based approach. To accomplish the cross-lingual entity linking task, they relied on name transliteration to match the Chinese entities to English names, and they used statistical machine translation and cross-lingual information retrieval to transform entity mention document into English equivalents. The second approach [Fahrni et al., 2011] is an explicit semantic model approach. They first build a multilingual knowledge base from Wikipeida. And then, they use the multilingual knowledege base to obtain a concpet-based language-independent representation of the entity mention document and the candidate entity.

Table 2 shows the comparison results of BLDA approach with translation based approach and explicit semantic model approach. From the table, we can see that the BLDA approach outperformes explicit semantic model approach. This indicates the effectiveness of our BLDA approach. Althrough the translation based approach gets a slighty better result than BLDA method, their method need parallel corpora which are well aligned at word or sentence level. It is expensive to obtain such parallel corpora.

6 Conclusion and Future Work

In this paper, we propose a BLDA model to mine bilingual topics from Wikipedia to address the problem of cross-lingual entity linking. Experimental results show that the proposed method is suitable for discovering bilingual topic and obtain competitive results on the standard KBP dataset.

In the future of our work, we plan to investigate the use of category link structure in Wikipedia and combine it into our method.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 61070106, No. 61272332 and No. 61202329), the National High Technology Development 863 Program of China (No. 2012AA011102), the National Basic Research Program of China (No. 2012CB316300), the Strategic Priority Research Program of the Chinese Academy of Sciences (Grant No. XDA06030300), We thank the anonymous reviewers for their insightful comments.