Post-mortem on Baidu's Entity Linking Competition: Behavior Modeling and Entity Linking

百度实体链接比赛后记：行为建模和实体链接 苏剑林 · 2019-09-03 · Machine Learning model NLP NER

A few months ago I took part in Baidu's entity linking competition, one of the evaluation tasks of CCKS2019, officially called "entity linking." The competition wrapped up completely a few weeks ago. My final F1 was around 0.78 (the champion scored 0.80), placing 14th — not a standout result (the one distinctive feature of my model is that it's very lightweight; it runs comfortably on a GTX1060). So this post is purely a record of the process — big shots, please take it with a grain of salt.

Task Introduction

Entity linking, broadly speaking, refers to predicting which knowledge-base id a query's entity corresponds to, given an existing knowledge base. In other words, the knowledge base records many entities, and an entity with a given name may have several possible interpretations, each identified by a unique id. What we need to do is predict which interpretation (id) the entity mentioned in the query actually refers to. This is a necessary step in knowledge-graph-based question answering systems. more

Data Format

Entity linking exists to serve knowledge-graph-based QA, so first we need a knowledge base (kb_data), an example of which looks like this:

{"alias": ["胜利"], "subject_id": "10001", "subject": "胜利", "type": ["Thing"], "data": [{"predicate": "摘要", "object": "英雄联盟胜利系列皮肤是拳头公司制作的具有纪念意义限定系列皮肤之一。拳头公司制作的具有纪念意义限定系列皮肤还包括英雄联盟冠军系列皮肤、MSI季中冠军赛征服者系列以及英雄联盟全球总决赛冠军系列皮肤。每到赛季结束时，拳头公司都会制作胜利系列皮肤作为赛季奖励来认可那些在排位赛中勇猛拼搏达到黄金段位的玩家。"}, {"predicate": "制作方", "object": "Riot Games"}, {"predicate": "外文名", "object": "Victorious"}, {"predicate": "来源", "object": "英雄联盟"}, {"predicate": "中文名", "object": "胜利"}, {"predicate": "属性", "object": "虚拟"}, {"predicate": "义项描述", "object": "游戏《英雄联盟》胜利系列限定皮肤"}]}
{"alias": ["张三的歌"], "subject_id": "10002", "subject": "张三的歌", "type": ["CreativeWork"], "data": [{"predicate": "摘要", "object": "《张三的歌》这首经典老歌，词曲作者是张子石。最早收录于李寿全的专辑《8又二分之一》当中。李寿全作为台湾民谣时代的推动人，在80年代中后期有着举足轻重的地位，而这首《张三的歌》出现在当时的背景之下，带来了无可比拟的社会效应，也为那个年代留下了无法抹去的回忆。随着时间的推移，陈翔、齐秦、吴宗宪、蔡琴、青鸟飞鱼等歌手都曾翻唱过。"}, {"predicate": "歌曲原唱", "object": "李寿全"}, {"predicate": "谱曲", "object": "张子石"}, {"predicate": "歌曲时长", "object": "3分58秒"}, {"predicate": "歌曲语言", "object": "普通话"}, {"predicate": "音乐风格", "object": "民谣"}, {"predicate": "唱片公司", "object": "飞碟唱片"}, {"predicate": "翻唱", "object": "齐秦、苏芮、南方二重唱等"}, {"predicate": "填词", "object": "张子石"}, {"predicate": "发行时间", "object": "1986-08-01"}, {"predicate": "中文名称", "object": "张三的歌"}, {"predicate": "所属专辑", "object": "8又二分之一"}, {"predicate": "义项描述", "object": "李寿全演唱歌曲"}, {"predicate": "标签", "object": "单曲"}, {"predicate": "标签", "object": "音乐作品"}]}
...
...

The knowledge base contains many entities, and the information for each entity includes a unique entity id, aliases, and properties/attribute values related to the entity — in short, this is essentially a knowledge graph. A notable feature of this knowledge base is that "entities" aren't necessarily proper nouns — they also include common nouns, verbs, adjectives, etc., such as "victory" or "beauty." Moreover, there are many entities sharing the same name (which is exactly why the entity linking task exists) — for instance, in the knowledge base provided for this competition, there are 15 entities named "胜利" (Victory), as shown below:

{"alias": ["胜利"], "subject_id": "10001", "subject": "胜利", "type": ["Thing"], "data": [{"predicate": "摘要", "object": "英雄联盟胜利系列皮肤是拳头公司制作的具有纪念意义限定系列皮肤之一。拳头公司制作的具有纪念意义限定系列皮肤还包括英雄联盟冠军系列皮肤、MSI季中冠军赛征服者系列以及英雄联盟全球总决赛冠军系列皮肤。每到赛季结束时，拳头公司都会制作胜利系列皮肤作为赛季奖励来认可那些在排位赛中勇猛拼搏达到黄金段位的玩家。"}, {"predicate": "制作方", "object": "Riot Games"}, {"predicate": "外文名", "object": "Victorious"}, {"predicate": "来源", "object": "英雄联盟"}, {"predicate": "中文名", "object": "胜利"}, {"predicate": "属性", "object": "虚拟"}, {"predicate": "义项描述", "object": "游戏《英雄联盟》胜利系列限定皮肤"}]}
{"alias": ["胜利"], "subject_id": "19044", "type": ["Vocabulary"], "data": [{"predicate": "摘要", "object": "胜利，汉语词汇。拼音：shèng lì胜利，指达到预期的目的。与“失败”相对。有“成功”的意思，古代打仗成功称胜利，比赛夺冠胜利称“成功”。其他寓意也很广泛(如：一件事坚持到了最后也称胜利)。胜利在英语中都为victory [Victory ]"}, {"predicate": "外文名", "object": "win"}, {"predicate": "反义词", "object": "失败"}, {"predicate": "拼音", "object": "shèng lì"}, {"predicate": "中文名", "object": "胜利"}, {"predicate": "释义", "object": "获得成功或达到目的"}, {"predicate": "义项描述", "object": "汉语词语"}, {"predicate": "标签", "object": "文化"}], "subject": "胜利"}
{"alias": ["胜利"], "subject_id": "37234", "type": ["Thing"], "data": [{"predicate": "摘要", "object": "《胜利》是由[英] 约瑟夫·康拉德所著一部讽喻小说，新华出版社出版发行。"}, {"predicate": "作者", "object": "[英] 约瑟夫·康拉德"}, {"predicate": "ISBN", "object": "9787516620762"}, {"predicate": "书名", "object": "胜利"}, {"predicate": "出版社", "object": "新华出版社"}, {"predicate": "义项描述", "object": "[英] 约瑟夫·康拉德所著小说"}], "subject": "胜利"}
...
...

Besides the knowledge base, we also have a batch of annotated samples, formatted as follows:

{"text_id": "1", "text": "南京南站:坐高铁在南京南站下。南京南站", "mention_data": [{"kb_id": "311223", "mention": "南京南站", "offset": "0"}, {"kb_id": "341096", "mention": "高铁", "offset": "6"}, {"kb_id": "311223", "mention": "南京南站", "offset": "9"}, {"kb_id": "311223", "mention": "南京南站", "offset": "15"}]}
{"text_id": "2", "text": "比特币吸粉无数,但央行的心另有所属|界面新闻 · jmedia", "mention_data": [{"kb_id": "278410", "mention": "比特币", "offset": "0"}, {"kb_id": "199602", "mention": "央行", "offset": "9"}, {"kb_id": "215472", "mention": "界面新闻", "offset": "18"}]}
{"text_id": "3", "text": "解读《万历十五年》", "mention_data": [{"kb_id": "131751", "mention": "万历十五年", "offset": "3"}]}
{"text_id": "4", "text": "《时间的针脚第一季》迅雷下载_完整版在线观看_美剧...", "mention_data": [{"kb_id": "NIL", "mention": "时间的针脚第一季", "offset": "1"}, {"kb_id": "57067", "mention": "迅雷", "offset": "10"}, {"kb_id": "394479", "mention": "美剧", "offset": "23"}]}
...
...

This training data annotates the entity mention in the query text (mention), the position of that mention (offset), and the corresponding entity id in the knowledge base (kb_id). Each query text may have multiple entities identified. Since only the query text is provided at prediction time, we need to perform both entity recognition and entity linking simultaneously.

Basic Approach

As mentioned above, in this Baidu competition we not only need to find the knowledge-base id corresponding to an entity, but also need to first locate the entity itself — in other words, we need to do entity recognition first, and then entity linking. In this section, we'll analyze both tasks in light of the competition data, in order to arrive at an approach for solving the problem.

The technology for entity recognition is clearly quite mature by now — the standard recipe is BiLSTM+CRF, and recently fine-tuning with Bert+CRF has also become popular. In the model presented in this post, the entity recognition model is "LSTM + half-pointer/half-tagging structure," plus some hand-crafted features. This choice was made both for speed considerations and to match the characteristics of the annotated data itself.

As for the entity linking step, we observe that each entity in the knowledge base is associated with multiple "attribute–value" pairs. Handling these attribute–value pairs separately would be quite cumbersome, so I simply concatenated all the "attribute–value" pairs into a single string, treating it as the entity's complete description. For example, below is the concatenated description of a particular entity named "胜利" (Victory):

Summary: The League of Legends Victory series of skins is one of the commemorative limited-edition skin series produced by Riot Games. Other commemorative limited-edition series produced by Riot Games include the League of Legends Champion series, the MSI Mid-Season Invitational Conqueror series, and the League of Legends World Championship series. At the end of each season, Riot Games produces the Victory series skins as a season reward to recognize players who fought their way to Gold rank in ranked play.
Producer: Riot Games
Foreign name: Victorious
Source: League of Legends
Chinese name: 胜利 (Victory)
Attribute: Virtual
Sense description: Limited-edition Victory series skin in the game League of Legends
Name: Victory

In this way, each entity corresponds to a (usually fairly long) descriptive text, and doing entity linking essentially becomes a matter of matching the query text and the entity span against this entity description. Broadly speaking, this is fairly close to a text-matching problem between two pieces of text, so the approach I took was to encode the query text and the entity description text separately, mark the position of a given entity within the query text, then fuse the query text encoding and the entity description encoding via attention, ultimately turning this into a binary classification problem.

The advantage of this approach is that the training cost is relatively low; the drawback is that each pass processes just one entity from the query text, and each time we can only traverse a single entity in the knowledge base — overall the sampling efficiency is low, and training time is correspondingly longer. At prediction time, we iterate over all entities sharing the same name, run binary classification against the query text and entity span for each one in turn, and finally output the one with the highest probability.

Model Details

Here I'll walk through my processing and modeling steps one by one. In my implementation, the entity tagging and entity linking components are trained jointly and share some modules. The overall idea of the model (including the training scheme) is similar to the one described in A Lightweight Information Extraction Model Based on DGCNN and Probabilistic Graphs, and readers can consult that post for comparison.

Overall diagram of this post's entity linking model (click to enlarge)

Entity Recognition

First, the entity recognition part, introduced in two sections: the "base model" and "hand-crafted features."

Base Model

This post's entity recognition model

The "base model" refers to the neural network component, which performs character-level tagging using a mixed character/word embedding along with hand-crafted features. The tagging structure is still the "half-pointer/half-tagging structure" I devised previously (see here and here).

Departing from my usual habit of using all-CNN architectures, this model mainly relies on bidirectional LSTMs, since this time I didn't intend to make the model too deep. When the model is very shallow (only one or two layers), bidirectional LSTMs tend to outperform both CNNs and attention.

Hand-Crafted Features

Since the knowledge base is given, and the recognized entity names are guaranteed to appear in the knowledge base (in the alias field — if not, it would be considered an annotation error), one baseline for entity recognition is to simply pull out all the aliases from the knowledge base to form a dictionary, and then build a maximum-matching model based on this dictionary. This achieves an entity recall of about 92%, but the precision is low, only around 30%, giving an overall F1 of about 40%.

Next, we can observe that the entity annotations in the training data are quite "arbitrary" — overall, there's a strong subjective element to them. One could say this isn't really semantics-based entity recognition at all, but rather "modeling the annotator's labeling trajectory" — that is, we're mainly trying to fit the annotators' labeling habits, rather than building entity recognition grounded in semantic understanding.

For example, in the query shown in the earlier diagram, "《暗警》迅雷下载/在线观看 -犯罪/历史" ("Dark Cop" Thunder Download/Watch Online - Crime/History), only "暗警" (Dark Cop), "迅雷" (Thunder), and "历史" (History) were annotated as entities. In fact, "下载" (Download), "在线" (Online), "观看" (Watch), and "犯罪" (Crime) are all entities present in the knowledge base, and there exist entity ids that would fit this query. So why weren't they tagged? The only explanation is that the annotators didn't feel like tagging them / didn't want to / ran out of energy. There's also a case like "高清视频" (HD Video): in some queries "高清视频" is tagged as a single entity as a whole, while in others it's tagged as two separate entities, "高清" (HD) and "视频" (Video) — because "高清视频," "高清," and "视频" are all entities present in the knowledge base.

So, a lot of entity recognition outcomes don't really have any principled explanation — they're simply a matter of annotator habit. In order to better fit the annotators' labeling habits, we can run some statistics over the training set to figure out which entities in the knowledge base tend to get tagged often and which rarely do. This lets us apply a basic filter to the knowledge base's entities (see the open-source code below for filtering details), and then build a maximum-matching model using this filtered entity set as the dictionary. The final entity recall comes out to about 91.8%, but the precision reaches 60%, giving an F1 of 70%+.

In other words, simple statistics combined with maximum matching alone can push the entity recognition F1 up to 70%+. We convert this maximum-matching result into a 0/1 feature and feed it into the base model, which is equivalent to using the base model to further filter the maximum-matching results. The final F1 for entity recognition came out to about 81% (I don't remember the exact figure).

Entity Linking

Now for the entity linking step, again introduced in two parts: "base model" and "hand-crafted features" — once again, a fairly simple baseline model boosted by hand-crafted features.

Base Model

In the entity linking model, what we need to do is "determine whether a given entity in the query matches a same-named entity in the knowledge base." To do this, we need to sample randomly: pick one entity at random from all the entities recognized in the query, and then pick one at random from all the same-named entities in the knowledge base.

This post's entity linking model

For the query, we first reuse the encoded sequence of the query text from the entity recognition step, then mark the sampled entity with a 0/1 sequence and concatenate it onto this encoded sequence. Some hand-crafted features are also concatenated onto the encoded sequence. After concatenation, we run this through a BiLSTM to obtain the final encoded sequence $\boldsymbol{Q}$. On the same-named-entity side, we take the description of the same-named entity, pass it through an embedding layer (shared with the query embedding), and then through another BiLSTM to obtain the encoding of the entity description $\boldsymbol{D}$.

Once we have both encoded sequences, we can apply attention. As explained in A Brief Reading of "Attention Is All You Need" (Introduction + Code), the three key elements of attention are query, key, and value. Here we first use $\boldsymbol{Q}$ as the query and $\boldsymbol{D}$ as both key and value to perform one round of attention, and then use $\boldsymbol{D}$ as the query and $\boldsymbol{Q}$ as both key and value to perform a second round of attention. We apply max pooling to each of the two attention outputs separately to obtain fixed-length vectors, concatenate them, and then feed the result into a fully connected layer for binary classification.

Hand-Crafted Features

The hand-crafted features used in entity linking are centered on the query, and the final output is a vector sequence with the same length as the query, which is concatenated onto the query's encoded representation. In this post's model, three hand-crafted features are used:

1. Whether each character of the query has appeared in the entity description (yielding a 0/1 sequence);
2. Both the query and the entity description are tokenized into words, and then we check whether each word of the query appears in the entity description (yielding a 0/1 sequence, where the tag for each word is repeated as many times as the word's character length, to ensure a sequence of the usual length);
3. Whether each word/segment in the query is some "object" of the entity in question (yielding a 0/1 sequence; see the knowledge-base example given at the start of the post for the meaning of "object").

As I recall, these three features gave a fairly noticeable boost to entity linking accuracy (though I don't remember the exact magnitude).

In addition, at prediction time, we also made use of a statistical result. As already emphasized above, the entity recognition step is really more like "modeling annotation behavior" than "semantic understanding," and involves quite a lot of randomness — and the same is true of the entity linking step. We can observe from statistics that for certain entities, while they may have many same-named counterparts in the knowledge base, only a handful of those ids might actually get tagged in practice — the annotators may not have even looked at the rest. In other words, what might originally be a 1-out-of-50 problem effectively becomes, in the annotators' actual labeling habits, a 1-out-of-5 problem.

So we can gather statistics over all the entities that appear in the training set along with their corresponding entity ids, which gives us, for each entity name, a distribution describing how the annotated ids are distributed for entities with that name. If this distribution is heavily concentrated on just a few ids, then we might as well keep only those ids and discard all the other same-named entities. In practice, this turned out to both speed up prediction and improve accuracy.

Code

GitHub: https://github.com/bojone/el-2019

The code was tested with Python 2.7 + Keras 2.2.4 + Tensorflow 1.8. The whole model can be run comfortably on a single GTX1060 6GB — no trouble at all. Everything else is much like the previous experimental "alchemy" for the information extraction model; in fact, this code was adapted from that codebase, so naturally there isn't much difference.

Summary

This post shared my experience competing in an entity linking competition. Model-wise, the overall architecture is fairly simple, and the main performance gains came from the hand-crafted features I proposed. These features were mainly statistical features derived from manually observing characteristics of the data — competition tricks, in essence. In fact, these tricks smack of opportunism and might not be applicable in a real production environment, but they closely matched the particular characteristics of this competition's data.

To repeat what I said earlier: I tend to think of this more as a competition in modeling annotation behavior than one in genuine semantic understanding — especially at the entity recognition step, where the subjectivity is so strong that it became one of the main bottlenecks of the whole competition. To push up the final score, we had to invest considerable effort into getting entity recognition right — but doing well at entity recognition only means you've better fit the annotators' behavior, not that you've actually achieved the best semantic entity recognition. And it doesn't do much to help with the original goal of the competition — entity linking — either.

Moreover, in a genuine production setting, entity recognition usually has standard methods already available, so typically all that's really needed is to do entity linking well. This, I think, is where this competition's design fell short.

That said, annotated data doesn't come easily — many thanks to the folks at Baidu for organizing the competition and providing the annotated data.