{'fraction_non_alphanumeric': 0.040661005602339595, 'fraction_numerical': 0.020365737641379795, 'mean_word_length': 4.29712579320642, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Collective Entity Resolution with Multi-Focal Attention

Entity resolution is the task of linking each mention of an entity in text to the corresponding record in a knowledge base (KB). Coherence models for entity resolution encourage all referring expressions in a document to resolve to entities that are related in the KB. We explore attentionlike mechanisms for coherence, where the evidence for each candidate is based on a small set of strong relations, rather than relations to all other entities in the document. The rationale is that documentwide support may simply not exist for non-salient entities, or entities not densely connected in the KB. Our proposed system outperforms state-of-the-art systems on the CoNLL 2003, TAC KBP 2010, 2011 and 2012 tasks.


Introduction
Entity resolution (ER) is the task of mapping mentions of entities in text to corresponding records in a knowledge base (KB) (Bunescu and Pasca, 2006;Cucerzan, 2007;Kulkarni et al., 2009;Dredze et al., 2010;Hoffart et al., 2011;Hachey et al., 2013). ER is a challenging problem because mentions are often ambiguous on their own, and can only be resolved given appropriate context. For example, the mention Beirut may refer to the capital of Lebanon, the band from New Mexico, or a drinking game (Figure 1). Names may also refer to entities that are not in the KB, a problem known as NIL detection.
Most ER systems consist of a mention model, a context model, and a coherence model (Milne and Witten, 2008;Cucerzan, 2007;Ratinov et al., * Currently at Tel Aviv University † Currently at IIT Bombay 2011; Hoffart et al., 2011;Hachey et al., 2013). The mention model associates each entity with its possible textual representations (also known as aliases or surface forms). The context model helps resolve an ambiguous mention using textual features extracted from the surrounding context. The coherence model, the focus of this work, encourages all mentions to resolve to entities that are related to each other. Relations may be established via the KB, Web links, embeddings, or other resources.
Coherence models often define an objective function that includes local and pairwise candidate scores, where the pairwise scores correspond to some notion of coherence or relation strength. 1 Support for a candidate is typically aggregated over relations to all other entities in the document. One problem with this approach is that it may dilute evidence for entities that are not salient in the document, or not well-connected in the KB. Our work aims to address this issue.
We introduce a novel coherence model with an attention mechanism, where the score for each candidate only depends on a small subset of mentions. Attention has recently been used with considerable empirical success in tasks such as translation (Bahdanau et al., 2014) and image caption generation (Xu et al., 2015). We argue that attention is also desirable for collective ER due to the discussed imbalance in the number of relations for different entities.
Attention models typically have a single focus, implemented using the softmax function. Our model allows each candidate to focus on multiple mentions, and, to implement it, we introduce a novel smooth version of the multi-focus attention  Figure 1: Illustration of the ER problem for three mentions "Beirut", "New Mexico" and "Santa Fe". each mention has three possible disambiguations. Edges link disambiguations that have Wikipedia links between their respective pages.
Our system uses mention and context models similar to those of Lazic et al. (2015), along with our novel multi-focal attention model to enforce coherence, leading to significant performance improvements on CoNLL 2003 (Hoffart et al., 2011) and TAC KBP 2010-2012 tasks (Ji et al., 2010;Ji et al., 2011;Mayfield et al., 2012). In particular, we achieve a 20% relative reduction in error from Chisholm and Hachey (2015) on CoNLL, and a 22% error reduction from Cucerzan (2012) on TAC 2012. Our contributions thus consist of defining a novel multi-focal attention model and applying it successfully to an entity resolution system.

Definitions and notation
We are given a document with n mentions, where each mention i has a set of n i candidate entities C i = {c i,1 , ..., c i,n i }. The goal is to assign a label y i ∈ C i to each mention.
Similarly to previous work, our approach to disambiguation relies on local and pairwise candidate scores, which we denote by s i (y i ) and s ij (y i , y j ) respectively. The local score is based only on local evidence, such as the mention phrase and textual features, while the pairwise score is based on the relatedness of the two candidates. In Sections 3.2 and 3.3 we discuss how these scores may be parameterized and learned. Many systems (Cucerzan, 2007;Milne and Witten, 2008;Kulkarni et al., 2009) simply hardwire pairwise scores.
Coherence models typically attempt to maximize a global objective function that assigns a score to each complete labeling y = (y 1 , . . . , y n ). An example of such a function is the sum of all singleton and pairwise scores for each label: 2 One disadvantage of this approach is that maximizing g corresponds to finding the MAP assignment of a general pairwise Markov random field, and is hence NP hard for the general case (Wainwright and Jordan, 2008). Another limitation is that non-salient entities may be related to very few other entities mentioned in the document, and summing over all mentions may dilute the evidence for such entities. In this paper we explore alternative objectives, relying on attention and tractable inference.

Attention model
We now describe our multi-focal attention model. We first introduce the inference approach and optimization objective, and then provide details on how scores are calculated and learned.

Inference
As noted earlier, the global score function in Eq. (1) is hard to maximize. Here we simplify inference by decomposing the task over mentions, which makes it easy to integrate attention in terms of both inference and learning.

Star model
We start by considering a simple attention-free model in which inference is tractable, which we call a star model. For a particular mention i, the star model is a graphical model that contains y i , y 1 y 2 y 3 y 4 (a) y 1 y 2 y 3 y 4 (b) y 1 y 2 y 3 y 4 (c) Figure 2: (a) The complete graph corresponding to Eq. (1). (b) A star shaped subgraph corresponding to y 2 . This will be used to obtaining the label y 2 . (c) The star graph for y 3 .
all interactions between y i and other labels, and no other interactions, as illustrated in Fig. 2.
While the star graph centered at i contains up to n variables, we will only use it to infer the label of mention i. Let q ij (y i ) be the support for label y i from mention j, defined as follows: and we also define q ii (y i ) = −∞ to simplify notation for later. We define the following score function for mention i: and predict the label y i = arg max y f i (y).
Due to the structure of the star graph, inference is easy and can be done in O(nC 2 ), where C is the maximum number of candidates. A similar decomposition has previously been used in the context of approximate learning for structured prediction (Sontag et al., 2011). Note that we do not view this approach as an approximation to the global problem, but rather as our inference procedure.

Adding attention
The score function in Eq. (3) aggregates pairwise scores for each label y i over all mentions. In this section, we restrict this to only consider K mentions with the strongest relations to y i . 3 Let amx K (z) be the sum of the largest K values in the vector z = (z 1 , . . . , z n ). For each label y i , we redefine the score function to be where q i (y i ) = (q i1 (y i ), . . . , q in (y i )) and q ij (y i ) is as defined in Eq.
(2). The inference rule is again y i = arg max y f i (y), and the computational cost is O(nC 2 + n log n) since sorting is required. 4

Soft attention
Previous work on attention has shown that it is advantageous to use a soft form of attention, where the level of attention is not zero or one, but can rather take intermediate values. Existing attention models focus on a single object, such as a single word (Bahdanau et al., 2014) or a single image window (Xu et al., 2015). In such models, it is natural to change the max function in the attention operator to a soft-max. In our case, the attention beam contains K elements, and we require a different notion of a soft-max, which we develop below.
To obtain a soft version of the function amx K (z), we first use an alternative definition. Denote by S the set u = (u 1 , . . . , u n ) such that 0 ≤ u i ≤ 1 and i u i = K. Then amx K (z) is equivalent to the optimization problem: The optimization problem above is a linear program, whose solution is the sum of top K elements of z as required. This follows since the optimal u i can easily be shown to attain only integral values. Given this optimization view of amx K (z) it is natural to smooth it (Nesterov, 2005) by adding a non-linearity to the optimization. Since the variables are non-negative, one possible choice is an entropy-like regularizer. We shall see that this choice results in a closed form solution, and also recovers the standard soft-max case for K = 1. Consider the optimization problem: where β is a tuned hyperparameter. 5 The following proposition provides a closed form solution for smx K , as well as its gradient. Proposition 3.1. Assume w.l.o.g. that z is sorted such that z 1 ≥ . . . ≥ z n . Denote by R the maximum index r ∈ {1, . . . , K − 1} such that: If this doesn't hold for any r, set R = 0. Then: Proof is provided in the appendix. As noted, K = 1 recovers the standard softmax function. 6 As β → ∞, smx K will approach the sum of the top K elements as expected. For finite β we have a soft version of amx K .
Our soft attention based model will therefore consider the soft-variant of Eq. (4): and maximize f (y i ) to obtain the label.

Score parameterization
Thus far we assumed the singleton and pairwise scores were given. We next discuss how to parameterize and learn these scores. As in other structured prediction work, we will assume that the scores are functions of the features of the input x and labels. Specifically, denote a set of singleton features for mention i and label y i by φ s i (x, y i ) ∈ R ns and a set of pairwise features for mentions i and j and their labels by φ p ij (x, y i , y j ) ∈ R np . Then the model has two sets of weights w s and w p and the scores are obtained as a linear combination of the features. Namely: 7 where we have explicitly denoted the dependence of the scores on the weight vectors. See Sec. 6.2.2 for details on how the features are chosen. It is of course possible to consider non-linear alternatives for the score function, as in recent deep learning . The latter is in fact the gradient of the former (for β = 1). 7 We again omit the dependence of the scores on the input x for brevity. parsing models (Chen and Manning, 2014;Weiss et al., 2015), but we focus on the linear case for simplicity.

Parameter learning
The parameters w s , w p are learned from labeled data, as explained next. Since inference decomposes over mentions, we use a simple hinge loss for each mention. Denote by y * i the ground truth label for mention i, and let s i (y i ) ≡ (s i1 (y i ), . . . , s in (y i )). Then the hinge loss for mention i is: where ∆(y i , y * i ) is zero if y i = y * i and one otherwise. If there are unlabeled mentions in the training data, we add those to the star graph, and maximize over the unknown labels in the positive and negative part of the hinge loss. The overall loss is simply the sum of losses for all the mentions, plus 2 regularization over w s , w p . We minimize the loss using AdaGrad (Duchi et al., 2011) with learning rate η = 0.1.

Single-link model
To motivate our modeling choices of using multifocal attention and decomposed inference, we additionally consider a simple baseline model with single-focus attention and global inference. In this approach, which we name single-link, each mention i attends to exactly one other mention that maximizes the pairwise relation score. The corresponding objective can be written as there is no relation between y i and y j , and we set s ii (y i , y i ) = 0.
While exact inference in this model remains intractable, we can find approximate solutions using max-sum belief propagation (Kschischang et al., 2001). As a reminder, max-sum is an iterative algorithm for MAP inference which can be described in terms of messages sent from model factors g a (y a ) to each of their variables y ∈ y a . At convergence, each variable is assigned to the value that maximizes belief b(y), defined as the sum of incoming messages. The message updates have the following form: where q \a j (y j ) is the sum of all messages to y j except the one from factor g a . While the singlelink model contains high-order factors over n variables, computing the messages from these factors is tractable and requires sorting.

Related work
Ji (2016) and Ling et al. (2015) provide summaries of recent ER research. Here we review work related to the three main facets of our approach.

Coherence scores
Several systems (Milne and Witten, 2008;Kulkarni et al., 2009;Hoffart et al., 2011) use the "Milne and Witten" measure for relatedness between a pair of entities, which is based on the number of Wikipedia articles citing each entity page, and the number of articles citing both; Cucerzan (2007) has also relied on the Wikipedia category structure. Internal links from one entity page to another in Wikipedia also provide direct evidence of relatedness between them. Another (possibly more noisy) source of information are Web pages containing links (Singh et al., 2012) to Wikipedia pages of both entities. Such links have been used in several recent systems (Cheng and Roth, 2013;Chisholm and Hachey, 2015). Yamada et al. (2016) train embedding vectors for entities, and use them to define similarities.

Collective inference for ER
Optimizing most global coherence objectives is intractable. Milne and Witten (2008) and Ferragina and Scaiella (2010) decompose the problem over mentions and select the candidate that maximizes their relatedness score, which includes relations to all other mentions. Hoffart et al. (2011) use an iterative heuristic to remove unpromising mentionentity edges. Cucerzan (2007) creates a relation vector for each candidate, and disambiguates each entity to the candidate whose vector is most similar to the aggregate (which includes both correct and incorrect labels). Cheng and Roth (2013) use an integer linear program solver and Kulkarni et al. (2009) use a convex relaxation. Ratinov et al. (2011) use relation scores as features in a ranking SVM. Belief propagation without attention has been used by Ganea et al. (2015). Personalized PageRank (PPR) (Jeh and Widom, 2003) is another tractable alternative, adopted by several recent systems (Han and Sun, 2011;He et al., 2013;Alhelbawy and Gaizauskas, 2014;Pershina et al., 2015). Laplacian smoothing (Huang et al., 2014) is closely related.

Attention models
Attention models have shown great promise in several applications, including machine translation (Bahdanau et al., 2014) and image caption generation (Xu et al., 2015). We address a new application of attention, and introduce a significantly different attention mechanism, which allows each variable to focus on multiple objects. We develop a novel smooth version of the multi-focus attention function, which generalizes the single focus softmax-function. While some existing entity resolution systems (Jin et al., 2014;Lazic et al., 2015) may be viewed as having attention mechanisms, these are intended for single textual features and not readily extensible to structured inference. 6 Experiments 6.1 Evaluation data CoNLL: The CoNLL dataset (Hoffart et al., 2011) contains 1393 articles with about 34K mentions, and the standard performance metric is mention-averaged accuracy. The documents are partitioned into train, test-a and test-b. Like most authors, we report performance on the 231 test-b documents with 4483 linkable mentions.
TAC KBP: The TAC KBP 2010, 2011, and 2012 evaluation datasets (Ji et al., 2010;Ji et al., 2011;Mayfield et al., 2012) include 2250, 2250, and 2226 mentions respectively, of which roughly half are linkable to the reference KB. The competition evaluation includes NIL entities; participants are required to cluster NIL mentions across documents so that all mentions of each unknown entity are assigned a unique identifier. For these datasets, we report in-KB accuracy, overall accuracy (with all NILs in one cluster), and the competition metric B 3+ F 1 which evaluates NIL clustering.

KB and entity aliases
Our KB is derived from the Wikipedia subset of Freebase (Bollacker et al., 2008), with about 4M entities. To obtain our mention prior (the probability of candidate entities given a mention), we collect alias counts from Wikipedia page titles (including redirects and disambiguation pages), Freebase aliases, and Wikipedia anchor text. 99.31% of CoNLL test-b mentions are covered by the KB, and 96.19% include the gold entity in the candidates.
We optionally use the mapping from aliases to candidate entities released by Hoffart et al. (2011), obtained by extending the "means" tables of YAGO (Hoffart et al., 2013). When released, it had 100% mention and gold recall on CoNLL, i.e. every annotated mention could be mapped to at least one entity, and the set of entities included the gold entity. However, changes in canonical Wikipedia URLs, accented characters and unicode usually result in mention losses over time, as not all URLs can be mapped to the KB (Hasibi et al., 2016, Sec. 4).
For CoNLL only, we experiment with a third alias-entity mapping derived from Hoffart et al. (2011) by Pershina et al. (2015); we call it "HP". It is not known how candidates were pruned, but it has high recall and very low ambiguity: only 12.6 on CoNLL test-b, compared to 22.34 in our KB and 65.9 in YAGO. Unsurprisingly, using only this source of aliases results in high accuracy on CoNLL (Pershina et al., 2015;Yamada et al., 2016). Table 1 lists the statistics of the three alias-entity mappings and some of their combinations on the CoNLL test-b dataset. Table 2 provides the same statistics on the TAC KBP datasets (restricted to non-NIL mentions) for the of the YAGO+KB aliasentity mapping.

Local and pairwise scores
Our baseline system is similar in design and accuracy to Plato (Lazic et al., 2015). Given the referent phrase m i and textual context features b i , it computes the probability of a candidate entity as p i (c) ∝ p(c|m i )p(b i |c). The system resolves mentions independently and does not have an explicit coherence model; however, it does capture some coherence information indirectly as referent phrases are included as string context features. We experiment with several versions of the mention prior p(c|m i ) as described in the previous section.
Scores for single-link model: In the single-link model, we simply set the local score for mention i  and candidate c to s i (c) = ln p i (c) 1−p i (c) , so that likely candidates get positive scores. We set the pairwise score between two candidates heuristically to s ij (y i , y j ) = ln o(y i , y j ) + 2.3, where o(y i , y j ) is the number of outlinks from the Wikipedia page of y i to the page of y j . We consider up to three candidates for each mention for CONLL, and ten for TAC; if the baseline probability of the top candidate exceeds 0.9, we only consider the top candidate. Including more candidates did not make a difference in performance, as additional candidates had low baseline scores and were almost never chosen in practice. Scores for attention model: Local features φ s i (x, y i ) for the attention model are derived from p i (c). As the attention models have no probabilistic interpretation, we inject as features log p i (c) and log(1 − p i (c)). We set log 0 = 0 by convention, and handle the case where log is undefined by introducing two additional binary indicator features for p i (c) = 0 and p i (c) = 1.
Edge features φ p ij are set based on three sources of information: (1) Table 3: CoNLL test-b evaluation for recent competitive systems and our models, using different alias-entity maps. "KB+HP*" means we train and score entities using KB+HP, but output entities only in HP.
between y i and y j , (2) number of hyperlinks between Wikipedia pages of y i and y j (in either direction), and (3) number of mentions of y i on the Wikipedia page of y j and vice versa, after annotating Wikipedia with our baseline resolver. We cap each count to five and encode it using five binary indicator features, where the j th feature is set to 1 if the count is j and 0 otherwise. Additionally, for each count c we add a feature log (1 + c). We also added a binary feature which is one if y i = y j . We train the scores for the attention model on the 946 CoNLL train documents for CoNLL, and on the TAC 2009 evaluation and TAC 2010 training documents for TAC.

Results
CoNLL: Table 3 compares our models to recent competitive systems on CoNLL test-b in terms of mention-averaged (micro) accuracy. We also note the alias-entity map used in each system, as the corresponding gold recall is an upper bound on accuracy, and alias ambiguity determines the difficulty of the task. Therefore performance is not strictly comparable between maps.
Our baseline is slightly better than Lazic et al. (2015), but degrades after adding YAGO aliases which increase ambiguity. The attention model provides a substantial gain over the baseline, and outperforms Chisholm and Hachey (2015) by 2.3% in absolute accuracy.
The extremely low ambiguity (Tab. 1) of the HP alias mapping, coupled with guaranteed gold recall, makes the task too easy to be considered a realistic benchmark. Although we match Pershina et al. (2015) using KB+HP, for completeness, we provide the performance of our system with candidate entities restricted to those in HP (KB+HP*), but this is not equivalent to using only HP during training and inference. With KB+HP*, we outperform Pershina et al. (2015), and are competitive with recent unpublished work by Yamada et al. (2016), which uses entity and word embeddings. Including embeddings as features in our system may lead to further gains.
TAC KBP: Table 4 shows our results for the TAC KBP 2010 evaluation datasets, where we used the KB+YAGO entityalias map for all our experiments. To compute NIL clusters required for B 3 + F 1 , we simply rely on the fact that our KB is larger than the TAC reference KB, similarly to previous work. We assign a unique NIL label to all mentions of an entity that is in our KB but not in TAC. For mentions that cannot be linked to our KB, we simply use the mention string as the NIL identifier. Once again, our attention models improve the performance over the baseline system in nearly all experiments, with multi-focus attention outperforming single-link. Compared to prior work, we achieve competitive performance on TAC 2010 and the best results to date on TAC 2011 and TAC 2012. Table 5 shows two examples from the TAC 2011 dataset in which our multi-focus attention model improves over the baseline, along with the focus mentions in the document.

Effect of K and β on attention
We set the size of the multi-focus attention beam K based on accuracy on CoNLL test-a (for CoNLL) and training accuracy (for TAC). Fig.  3 shows the effect of K on the performance on CoNLL test-a dataset. Performance peaks for K = 6, with a sharp decrease after K = 10. This validates our central premise: all-pairs label coupling may hurt accuracy.
In   experiments we cross-validated over a wide range of β values, including β = ∞ which corresponds to taking the exact sum of K largest values. We found that the optimal value in most cases was large: β = 10, 100, or even ∞. This suggests that a hard attention model, where exactly K mentions are picked is adequate in the current settings.

Conclusion
We have described an attention-based approach to collective entity resolution, motivated by the observation that a non-salient entity in a long document may only have relations to a small subset of other entities. We explored two approaches to attention: a multi-focus attention model with tractable inference decomposed over mentions, and a single-focus model with global inference implemented using belief propagation. Our empirical results show that the methods results in significant performance gains across several benchmarks. Experiments in varying the size of the attention beam K in the star-shaped model suggest that multi-focus attention is beneficial. It is of course possible to extend the global single-link model to the multi-focus case, by modifying the model factors and resulting messages. However, the simplicity of the star-shaped model, its empirical effectiveness, and ease of learning parameters make it an attractive approach for easily incorporating attention into existing resolution models. The model can also readily be applied to other structured prediction problems in language processing, such as selecting antecedents in coreference resolution.
Deep learning has recently been used in mutliple NLP applications, including parsing (Chen and Manning, 2014) and translation (Bahdanau et al., 2014). Learning the local and pairwise scores in our model using a deep architecture rather than a linear model would likely lead to performance improvements. The star-shaped model is particularly amenable to this architecture, as it can be implemented via a feed-forward sequence of operations (including sorting, which can be implemented with soft-max gates).
Finally, one may consider a more elaborate model in which attention depends on the current state of the system; for example, the state can summarize the mention context. The dynamics of the underlying state can be modeled by recurrent neural networks or LSTMs (Bahdanau et al., 2014).
In conclusion, we have shown that attention is an effective mechanism for improving entity resolution models, and that it can be implemented via a simple inference mechanism, where model parameters can be easily learned.

Proof of Proposition 3.1
Begin with the optimization problem in Eq. (6). Introduce the following Lagrange multipliers: λ for the i u i = K constraint, and α i ≥ 0 for the u i ≤ 1 constraint. We can ignore the u i ≥ 0 constraint, as it will turn out to be satisfied. Denote Sentence with mention Entity Attn. focus mentions Caroline has dropped her name base: Caroline (given name) Democratic Party from consideration for the seat attn: Caroline Kennedy New York that Hillary has left vacant.
Robert Kennedy Chris Johnson had just 13 tackles last base: Chris Johnson (running back) Oakland Raiders season, and the Raiders currently have attn: Chris Johnson (cornerback) Oakland Raiders have 11 defensive backs on their roster.
Oakland Raiders Table 5: Examples of gains by our algorithm, showing the resolved mention, the entities it resolves to in the baseline and the attention models, and the mentions in the document that are attended to (here K = 3). In the first example, the baseline labels the mention "Caroline" as the given name, whereas the attention model attends to mentions that identify it as the diplomat Caroline Kennedy. In the second example, both models resolve "Chris Johnson" to football players, but the attention model finds the correct one by attending to three mentions of his former team, the Oakland Raiders.
Maximizing L with respect to u i yields: From this we can obtain the convex dual g(λ, α), and after minimizing over λ we arrive at: Next, we maximize the above with respect to α ≥ 0. Introduce Lagrange multipliers γ i for the constraint α i ≥ 0 and the corresponding Lagrangian L(α, γ). We propose a solution for α, γ and show that it satisfies the KKT conditions. MinimizingL wrt α we can characterize the optimal γ as: Set α i as follows: It can now be confirmed that the α, γ from Equations 16 and 15 satisfy the KKT conditions. Plugging the α value into g(α) yields the solution in the proposition. Differentiability follows from Nesterov (2005) and the gradient is u i in Eq. (13).