Entity Discovery and Linking (EDL) in Natural Language Processing (NLP) is the task of matching entity mentions in texts to a unique identifier in linked-data sources, such as CN-DBpedia, and it is becoming a hot topic as the linked data grows. Unlike conventional tasks of Named Entity Recognition (NER), which focus on identifying the occurrence of an entity and its type, but not the specific unique entity that the mention refers to, EDL makes a further step in understanding texts, thus playing a critical role in the construction of the upper applications, such as the Information Retrieval (IR) and Knowledge Based Question Answering (KBQA) systems.
EDL is commonly divided into two sub tasks: Mention Detection (MD) and Entity Linking (EL). MD is concerned with identifying potential mentions of entities in the text and EL involves mapping mentions to semantic entities. EDL is complex and challenging due not only to the ambiguity of word and phrase senses but also entity mentions, which are affected by the context of words and phrases, the similarity of mentions and entities, the prior of entities, the coherence among entities and etc.
Approaches have been proposed in literature to solve EDL. The majorities treat the two tasks in EDL separately, which can be distinguished into two main types: rule-based approaches and machine learning models. Rule-based approaches make good efforts in linguistic analysis [1] [2] [3] and can build practical systems in limited periods, thus getting good performances in the early related shared tasks. Machine learning models such as Maximum Entropy (ME) [4], generative models [5], ranking methods [6] and etc., benefitting from the data explosion in the last decade, good at balancing the precision and recall, is becoming more and more dominate. Suffering from cascade errors, gaps to the theoretical best performance exist for these separate approaches. Some jointly approaches are also reported [7] [8], which are good at taking the affecting factors of EDL to a single model but lack methods for model parameter tuning.
This paper presents our approach for CCKS2017 shared task, Question Entity Discovery and Linking (QEDL) in Chinese. One more sub task is raised, the segmentation of words and phrases in questions, compared to EDL, due to the boundary lack of Chinese words. The three sub tasks are jointly solved by an Integer Linear Program (ILP) based model tuning parameter by the Genetic Algorithm (GA). An f1 score of 0.804 in the mention discovery and 0.56 in the entity linking have been achieved in the evaluation.
The paper is structured as follows. After describing the four steps of the online predicting framework in section 2, we discuss the joint disambiguation step in detail in section 3. Section 4 presents the offline parameter tuning of the online model. The evaluation results are outlined in section 5. Finally, we review the main conclusions and preview the future work.
As shown in figure 1, given a Chinese short question, our online approach takes four steps for QEDL: word detection, mention discovery, entity mapping and joint disambiguation. A question sentence is processed as a sequence of characters, qNL = (t0, t1,… tn) while a word is a contiguous subsequence of the character sequence, wij = (ti, ti+1, … tj) , 0<=i<=j<=n. The input question is handled by the pipeline in figure 1.
Words are detected by "jieba", a common used Chinese text segmentation. In the cut for search mode of "jieba", all the word candidates are generated and put to a word set. For sample question "李娜是在哪一年拿的澳网冠军", the word set contains the following candidates: "李娜","是","在","哪一年","一年","拿","的","澳网" and "冠 军"。
Mentions are discovered using CN-DBpedia, by querying the contiguous subsequences of the questions. Subsequences are made mention candidates, which will be added to the word set containing all the word candidates, by the existence of the query results. For the sample question, the mention candidates, "李"，"李娜"， "一"，"一年" and etc., are added to the word set, with duplication removed.
A mention candidate can be mapped to multiple semantic entities. During this step, a semantic entity mapping space for the mentions is constructed. "李娜" in the above sample question is mapped to "李娜(中国女子网球名将)"，"李娜(南京师范大 学讲师)"，"李娜(2016年陈可辛导演电影)" and etc., in the mapping space.
During this step, the word boundary determination, mention disambiguation and semantic entity disambiguation are solved jointly by calculating a disambiguation graph. For the sample question, by decoding the outcome graph, we can get entity mentions as "李娜" and "澳网" and entity linking as "李娜(中国女子网球名将)" and "澳大利亚网球公开赛". The details of this step is described in section 3.
As the disambiguation of one word, mention and entity can influence the others, a disambiguation graph encoding all possible mappings is constructed. To simplify the problem, we model the problem as an ILP, rather than graph models.
A weighted, undirected Graph DG= (V, E) is defined with words Vw, entities Ve and the word overlap constrains Vo as nodes. The graph for the sample question is shown in figure 2, from which, we can see the edges, in which the word-entity edges tie closely to the final predicting results, are indicated by solid and dashed lines corresponding to 1 and 0 are assigned to variables in ILP.
Features and Constraints are expressed by the weighted edges in the Graph and by optimizing the final objective function, the best word and entity nodes are selected. The features and constraints harnessed in the model are presented below.
Our framework combines mention prior, entity prior, entity-context prior, similarity between entity and mention, and coherences between entities into a combined objective function.
Subject to:
) cxt( i m denotes the context of mentions, ) sum( i m represents the number of all the mentions, do penalize when the number of mentions is over 2, 3 or 4, each feature correspond to one coefficient, which changing by the GA tuning.
) scope( i m is the start position and end position interval of i m in the question sentence. Section 3.2
gives details on each of these components.
We use binary variables to indicate whether the nodes and edges are selected and integrate the features and constraints to the ILP objective function and constraints as shown in equation 1 and make the objective function linear with introducing some new variables and the spinoff constraints. It seems a sophisticated ILP, but for the questions are short, it is within the regime of modern ILP solvers. In Our Experiment, we use Pulp and achieved run-times, usually less than one second.
The parameters in the objective function in ILP, about 30 in quantity, are optimized by GA, a random search and optimization method based on natural selection and genetic mechanism of the living beings [10], without calculating the gradients. As the target parameters are floats, real number coding method are elected.
The CCKS2017 shared task one use f1 score in mention discovery and entity linking, We use score in equation ( 5) as our fitness function in GA, which grows bigger as the f1 scores increase.
Where, alpha is the recognition rate adjustment coefficient, beta is the bonus coefficient, gamma is the fitting coefficient and As Shown in Table 1, our model makes reasonable predictions in the QEDL. Further Experiments show the f1 score of 0.804 in the mention discovery and 0.56 in the entity linking are achieved on the test data, and over 0.10 are obtained on both scores over the second team in the shared task.
In this paper, an ILP based approach has been proposed for CCKS2017 shared task one. The approach harnesses the rich feature types provided by the question context and the linked data source to constrain the semantic-coherence objective function using a GA to tune the parameters, achieving the best performance in the task. Future work includes considering additional feature mining, improving online model calculating efficiency and its universality in other corpus.