Mapping Entity Sets in News Archives Across Time

Named entities are first class citizens in news and typically attract a lot of focus in any news article analysis. Therefore, automatic approaches toward effective named entity detection, disambiguation, linking and understanding have gathered much attention and have been studied since long ago. This is also true for the case of archival news article collections, albeit ancient documents typically add additional challenges for those tasks. The way in which history is studied and taught is also often entity centric and event centric.

One of common objectives of studying the history is to compare it with the present for drawing informative, novel or interesting conclusions. Accordingly, in such across-time scenarios an entity-to-entity comparison is an intuitive approach alongside event-to-event comparison. Imagine a journalist who aims to undertake a study of a certain period in the past in order to gain insights concerning similarity between the present political scene and the one in that period. In this case, an entity-centric comparison could provide him or her with a novel outlook on the present political elites and lead to drawing new conclusions and discussions with regard to wider political scene. Opinions on the continuity, change or analogy could be then formed or supported. Across-time entity-centered contrast may be also useful for scholars (e.g., historians or social scientists) studying different views of the past. For example, automatic comparison of household appliances in 1970s–1980s with those used in 2000s–2010s could facilitate work for scientists interested in the history and evolution of technology used at home.

In general, the determination of corresponding entity pairs is beneficial for in-depth understanding of the relation between the past and present and leads to the improved comprehension of our history and heritage. Furthermore, it can also support generation of forecasts according to the intuition that future events may resemble past ones based on the correspondence and similarity of their actors, i.e., entities. This kind of across-time comparison could be also seen as a special type of data integration problem, as it essentially consists of combining data that reside in different sources (entities in distant periods) and providing users with a unified view of them (generated mappings). We note, however, that comparing entire entity sets manually is not easy since people tend to possess limited knowledge about things from the past and lack historical perspective, necessary for comparisons involving longer time gaps. Another reason is possibly large size of entity sets, which can be also diverse and complex, demanding much cognitive effort. The objective of this work is then to propose automatic approaches for comparison of entity sets across time.

A natural method of set comparison is to find pairs of corresponding and representative entities of the both sets. Actually, example-based learning is an effective strategy that humans tend to adopt. Good examples help to grasp difficult concepts or complex entity categories in more effective way than high-level feature descriptions. Therefore, in our scenario, given two input collections of entities from different times (e.g., present politicians and ones from 1970s–1980s), we would aim to automatically generate a diversified set of corresponding entity pairs (e.g., US Presidents: Donald Trump and Ronald Reagan, Russian Presidents: Vladimir Putin and Mikhail Gorbachev or others less obvious examples in the case of politicians comparison). Given the generated entity mappings, a journalist, scientist or other professional could then be better equipped to further match events or entire periods in which those entities played key roles (e.g., matching political scenes of different times) in order to formulate or support various theories and analogies.

The problem of automatically generating comparable entity pairs is difficult due to the following challenges: (1) it is non-trivial to design approaches for representing across-time entity correspondence, especially, in cases when the entity sets come from time periods separated by long time gaps. The development of such correspondences needs to take into consideration differences in general contexts of the different, studied time periods. Collecting training data for establishing such connections is also challenging. (2) Effective comparison should involve typical entity representatives as these are usually associated with better representativeness of features and are less likely to cause misunderstanding. To give an example from biology, for an effective comparison of mammals with another animal class, one would prefer typical mammals like lions over atypical ones like platypuses (which lay eggs instead of giving birth). (3) Lastly, the input entity sets can be quite large and diverse (e.g., celebrities). Hence, the typical-example selection strategy would need to take into account any detected latent subgroups. Based on this, rather than proposing a single entity pair as an output, a set of pairs (each for every latent subgroup) would be preferred. An effective method then needs to output an optimal subset of all possible pairs, which would be composed of both typical and temporally comparable entities.

To approach the above-mentioned challenges, we introduce a novel technique for generating typical across-time comparables. First of all, we base the measurement of entity typicality on the findings from psychology and cognitive sciences [6, 14, 39]. In particular, an entity is considered typical in a diverse set if it is representative within a significant subset of that set. We next formulate the measurement of across-time entity comparability by first aligning vector spaces derived from the compared periods and then finding corresponding terms. For this, we adopt the distributed vector representation [27] to represent the context vectors of entities and we learn linear and orthogonal transformations between two vector spaces of input collections for establishing across-time entity correspondence. Lastly, inspired by the popular affinity propagation (AP) algorithm [11], we propose a concise joint integer linear programming framework (J-ILP) which detects typical entities (subsequently called exemplars) and outputs comparable pairs from the detected exemplars.

We perform experiments on the New York Times (NYT) Annotated Corpus [34], which has been frequently used to evaluate different researches that focus on temporal information processing or extraction in document archives [3]. The experiments demonstrate that the proposed method outperforms the baselines by 58.7% percent on average.

This paper is an extended version of our previous work [5]. We improve the previous work by (1) conducting extensive experiments on additional time periods of NYT dataset with new detailed analysis; (2) introducing additional novel metrics (typicality, comparability and product) for providing more evidence to demonstrate the effectiveness of proposed methods. Finally, (3) we discuss the key factors which can affect the model performance in detail.

Formally, given two sets of entities denoted by \(D_{A}\) and \(D_{B}\), where \(D_{A}\) and \(D_{B}\) come from different time periods \(T_{A}\) and \(T_{B}\), respectively (\(T_{A}\cap T_{B} = \varnothing\) and, typically \(T_{A}\) represents some period in the past while \(T_{B}\) represents more present time period), the task is to discover m comparable entity pairs P = [\(p_{1}\), \(p_{2}\), \(\ldots\), \(p_{m}\)] to form a concise subset conveying the most important comparisons, where \(p_{i}\) = \((e_{i}^{A}, e_{i}^{B})\). \(e_{i}^{A}\) and \(e_{i}^{B}\) are entities from \(D_{A}\) and \(D_{B}\), respectively (see Fig. 1 for an illustration of our research problem). The pairs should have good quality, i.e., each entity should be representative in its set, and entities within the same pair should be temporally comparable. Moreover, the set of selected entities should cover as many subgroups as possible to avoid redundancy.

Learning from examples is an effective strategy extensively adopted in cognition and education [14]. Good examples should be, however, typical. In this work, we apply the strategy of using typical examples for discovering comparable entity pairs. We denote the typicality of an entity e with regard to a set of entities S as \({\mathrm{Typ}}(e, S)\). The entities to be selected for comparison should be typical in their sets; namely, \({\mathrm{Typ}}(e_{i}^{A}, D_{A})\) and \({\mathrm{Typ}}(e_{i}^{B}, D_{B})\) should be as high as possible when \(p_{i}\) = \((e_{i}^{A}, e_{i}^{B})\) is a selected entity pair.

As suggested by the previous research in typicality analysis [14], an entity e in a set of entities S is typical, if it is likely to appear in S. We denote the likelihood of an entity e given a set of entities S by L(e|S) (to be defined soon). However, it is not appropriate to simply use L(e|S) as an estimator of typicality \({\mathrm{Typ}}(e, S)\) considering the characteristics of our task. First of all, the collections of entities for comparison can be very complex, and thus, they may cover many different kinds of entities. For example, if we want to compare US scientists across time, each of entity collections will include multiple kinds of entities such as mathematicians, physicists, chemists and so on. It is then very difficult for a single entity to represent all of them. In addition, different entity kinds vary in their significance. For instance, “physicists” are far more common than “entomologists”. Naturally, entities typical in a salient entity subset should be more important than those belonging to small subsets.

Given a set S including k mutually exclusive latent subgroups [\(S^{1}, S^{2}, \ldots ,S^{k}\)], let \(e_{i}^{t}\) denote the ith entity in the tth subgroup of S. We state two criteria required for \(e_{i}^{t}\) to be typical in the entire set S:

Criterion 1\(e_{i}^{t}\) should be representative in \(S^{t}\).

Criterion 2 The significance of \(S^{t}\) in S should be high.

The typicality of \(e_{i}^{t}\) with respect to S is then defined as follows:where \(L(e_{i}^{t}|S^{t})\) measures the representativeness of \(e_{i}^{t}\) with regard to the subgroup \(S^{t}\). In addition, \(\frac{\left| S^{t} \right| }{\left| S\right| }\) indicates the relative size of \(S^{t}\) regarded as an estimator of significance. \(e_{i}^{t}\) is more typical when the number of entities in its subgroup is large.

The likelihood L(e|S) of an entity e given a set of entities S is the posterior probability of e given S, which can be computed using probability density estimation methods. Many model estimation techniques have been proposed including parametric and nonparametric density estimations. We use kernel estimation [2] as it does not require any distribution assumption and can estimate unknown data distributions effectively. Kernel estimation is a generalization of sampling [14]. Moreover, we choose the commonly used Gaussian kernels. An illustration of the Gaussian kernel estimator is given in Fig. 2.

We set the bandwidth of the Gaussian kernel estimator \(h = \frac{1.06s}{\root 5 \of {n}}\) as suggested in [36], where n is the size of the data and s is the standard deviation of the data set. Formally, given a set of entities \(S = (e_{1}, e_{2}, \ldots , e_{n})\), the underlying likelihood function is approximated as:where \(d(e,e_{i})\) is the cosine distance between e and \(e_{i}\) and \(G_{h}(e,e_{i})\) is a Gaussian kernel.

In this section, we describe the method for measuring temporal comparability between an entity \(e_{A}\) in set \(D_{A}\) and an entity \(e_{B}\) in the other set \(D_{B}\). Intuitively, if \(e_{A}\) and \(e_{B}\) are comparable to each other, then \(e_{A}\) and \(e_{B}\) contain comparable aspects. For instance, (iPod, Walkman) could be regarded as comparable based on the observation that Walkman played the role of a popular portable music player 30 years ago same as iPod does nowadays. The key difficulty comes from the fact that there is low overlap between terms’ contexts across time (e.g., the set of top co-occurring words with iPod in documents published in 2010s has typically little overlap with the set of top co-occurring words with walkman that are extracted from documents in 1980s). It is impossible to directly compare entities in two different semantic vector spaces, as the features in both spaces have no direct correspondence between each other (as can be seen in Fig. 3).Thus, our task is then to build the connection between semantic spaces of \(D_{A}\) and \(D_{B}\).

Let transformation matrix W map the words from \(D_{A}\) into \(D_{B}\), and transformation matrix Q map the words in \(D_{B}\) back into \(D_{A}\). Let a and b be normalized word vectors from the news document collections \(D_{A}\) and \(D_{B}\), respectively. The correspondence between words a and b can be evaluated as the similarity between vectors b and Wa, i.e., \({\mathrm{Corr}}(a,b) = b^{\mathrm{T}}Wa\). However, we could also form this correspondence as \({\mathrm{Corr}}'(a,b) = a^{{\mathrm{T}}}Qb\).

This observation has also been reported in [37, 42] for the purpose of bilingual text translation. Note that orthogonal transformation preserves vector norms, so given normalized vectors a and b, \({\mathrm{Corr}}(a,b) = b^{\mathrm{T}}Wa \ = |b||Wa|\cos (b, Wa) = \cos (b, Wa) = {\mathrm{Sim}}_{\mathrm{cosine}}(a,b)\).

However, the following challenge is that the training term pairs for learning the mapping W are difficult to obtain. We adopt here a trick proposed by [44] for preparing enough training data. Namely, we use so-called common frequent terms (CFTs) as the training term pairs. CFT is very frequent terms in both compared document collections (see Table 1 for some examples of used CFTs in this work). Such frequent terms tend to change their meanings only to a small extent across time. The phenomenon that words which are intensively used in everyday life evolve more slowly has been reported in several languages including English, Spanish, Russian and Greek [13, 23, 29].¹

Given L pairs composed of normalized vectors of CFTs trained in both document collections [(\(a_{1}\),\(b_{1}\)), (\(a_{2}\),\(b_{2}\)), \(\ldots\), (\(a_{L}\),\(b_{L}\))], we should learn the transformation W by maximizing the accumulated cosine similarity of CFT pairs (we utilize the top 5% (18k words) of common frequent terms to train the transformation matrix),To infer the orthogonal transformation W from pairs of CFTs \(\{a_{i}, b_{i}\}_{i = 1}^{L}\), we state the following theorem.

The obtained orthogonal transformation \(W^{*}\) allows for learning correspondence on the level of terms. Based on it, we measure the temporal comparability between an entity \(e_{A}\) in set \(D_{A}\) and an entity \(e_{B}\) in the other set \(D_{B}\) as follows:

In this section, we describe our method for discovering comparable entity pairs. Given two sets of entities \(D_{A}\) and \(D_{B}\) the output is m comparable entity pairs [\(p_{1}\), \(p_{2}\), \(\ldots\), \(p_{m}\)], where each pair contains an entity from \(D_{A}\) and an entity from \(D_{B}\). Inspired by AP algorithm [11], we formulate our task as a process of identifying a subset of typical comparable entity pairs. It has been empirically found that using AP for solving objectives such as in our case (see Eq. 6) suffers considerably from convergence issues [43]. Thus, we propose a concise integer linear programming (ILP) formulation for discovering comparable entities, and we use the branch-and-bound method to obtain the optimal solution.

The prior here is that the ratio of typical candidate entities over trivial candidate entities is very low given the output length limit, and the input entity sets can be very diverse. We thus call an entity as exemplar if it represents a latent subgroup and is voted by other entities. Intuitively, if the selected exemplars concisely represent the entire entity set, their typicality and diversity will naturally arise. We then formulate the task as a process of selecting a subset of \(k_{A}\) and \(k_{B}\) exemplars for each set, respectively, and choosing m entity pairs based on the identified exemplars. Each non-exemplar entity is assigned to an exemplar entity based on a measure of similarity, and each exemplar e represents a subgroup comprised of all non-exemplar entities that are assigned to e. On the one hand, we wish to maximize the overall typicality of selected exemplars w.r.t. their representing subgroups. On the other hand, we expect to maximize the overall comparability of the top m entity pairs, where each pair consists of two exemplars from different sets.

We next introduce some notations used in our method. Let \(e_{i}^{A}\) denote the ith entity in \(D_{A}\). \(M_{A} = [m_{ij}]^{A}\) is a \(n_{A}\times n_{A}\) binary square matrix such that \(n_{A}\) is the number of entities within \(D_{A}\). \(m_{ii}^{A}\) indicates whether entity \(e_{i}^{A}\) is selected as an exemplar or not, and \(m_{ij:i\ne j}^{A}\) represents whether entity \(e_{i}^{A}\) votes for entity \(e_{j}^{A}\) as its exemplar. Similar to \(M_{A}\), the \(n_{B}\times n_{B}\) binary square matrix \(M_{B}\) indicates how entities belonging to \(D_{B}\) choose their exemplars, where \(n_{B}\) is the number of entities within \(D_{B}\). \(m_{ii}^{B}\) indicates whether entity \(e_{i}^{B}\) is selected as an exemplar or not, and \(m_{ij:i\ne j}^{B}\) represents whether entity \(e_{i}^{B}\) votes for entity \(e_{j}^{B}\) as its exemplar. Different from \(M_{A}\) and \(M_{B}\), \(M_{T} = [m_{ij}]^{\mathrm{T}}\) is a \(n_{A}\times n_{B}\) binary matrix whose entry \(m_{ij}^{\mathrm{T}}\) denotes whether entities \(e_{i}^{A}\) and \(e_{j}^{B}\) are paired together as the final result. Figure 5 shows an example of the exemplar identification task and the corresponding matrices \(M_{A}\), \(M_{B}\) and \(M_{T}\). Then, the following ILP problem is designed for the task of selecting \(k_{A}\) and \(k_{B}\) exemplars for each set, respectively, and for selecting m comparable entity pairs:We now explain the meaning of the above formulas. First, Eq. (12) forces that \(k_{A}\) and \(k_{B}\) exemplars are identified for both sets \(D_{A}\) and \(D_{B}\), respectively, and Eq. (15) guarantees that m entity pairs are selected as the final result. The restriction given by Eq. (13) means each entity must choose only one exemplar. Equation (14) enforces that if one entity \(e_{j}^{X}\) is voted by at least one other entity, then it must be an exemplar (i.e., \(m_{jj}^{X} = 1\)). The constraint given by (16) and (17) jointly guarantees that if an entity is selected in any comparable entity pair (i.e., \(m_{ij}^{\mathrm{T}} = 1\)), then it must be an exemplar in its own subgroup (i.e., \(m_{ii}^{A} = 1\) and \(m_{jj}^{B} = 1\)). Restricted by Eqs. (18) and (19), each selected exemplar in the result is only allowed to appear once to avoid redundancy. \({T}'( M_{X} )\) represents the overall typicality of selected exemplars in both sets \(D_{A}\) and \(D_{B}\), and \(G(e_{i}^{X})\) denotes the representing subgroup for entity \(e_{i}^{X}\) (if \(e_{i}^{X}\) is not chosen as an exemplar, its representing subgroup will be null). \({C}'( M_{T} )\) denotes the overall comparability of generated entity pairs. In view of the fact that there are \((k_{A} + k_{B})\) values (each value is in [0,1]) in the typicality component \({T}'( M_{A} ) + {T}'( M_{B} )\), and m numbers (each number is in [0,1]) in the comparability part \({C}'( M_{T} )\), we add the coefficients m and \((k_{A} + k_{B})\) in the objective function to avoid suffering from skewness problem. Finally, the parameter \(\lambda\)² is used to balance the weight of the two parts. Our proposed ILP formulation guarantees to achieve the optimal solution by using branch-and-bound method.

Comparable Entity Mining The task of comparable entity mining has attracted much attention in the NLP and Web mining communities [15‐19, 22]. Approaches to this task include hand-crafted extraction rules [8], supervised machine-learning methods [26, 35] and weakly supervised methods [17, 22]. Jindal et al. [18, 19] were the first to propose a two-step system in finding comparable entities which first tackles a classification problem (i.e., whether a sentence is comparative) and then a labeling problem (i.e., which part of the sentence is the desideratum). Later work refined that system by using a bootstrapping algorithm [22], or extended the idea of mining comparables to different types of corpora including query logs [16, 17] and comparative questions [22]. In addition, comparable entity mining is strongly related to the problem of automatic structured information extraction, comparative summarization and named entity recognition. Some work lies in the intersection of these tasks [10, 24].

Temporal Analog Detection and Embeddings Alignment A part of our system approaches the task of identifying temporally corresponding terms across different times. The related work to this subtask includes computing term similarity across time [1, 20, 21, 38]. In this study, we represent terms using the distributed vector representation [27]. Thus, the problem of connecting news articles’ context across different time periods can be approached by aligning pre-trained word embeddings in different time periods. Mikolov et al. proposed a linear transformation aligning bilingual word vectors for automatic text translation such as translation from Spanish to English [28]. Faruqui et al. obtained bilingual word vectors using CCA [9]. More recently, Xing et al. argued that the linear matrix adopted by Mikolov et al. should be orthogonal [42]. Similar suggestion has been given by Samuel et al. [37]. Besides linear models, nonlinear models such as “deep CCA” have also been introduced for the task of mapping multilingual word embeddings [25]. In this study, we adopt the orthogonal transformation for computing across-time entity correspondence due to its high accuracy and efficiency.

To the best of our knowledge, we are the first to focus on the task of automatically generating across-time comparable entity pairs given two entity sets, and on using the notion of typicality analysis from cognitive science and psychology.

We discuss here several relevant aspects to the task of mapping entity sets in news archives across time.

Entity comparison has been studied in the past (e.g., [33]). For an input entity pair, the task was to find their differences and similarities. Other work focused on finding a comparable entity for a given input entity [15, 17]. In this paper, we propose a novel entity-oriented comparison style over time in which entire subsets of entities from different time periods are matched to generate sets of comparable entity pairs. We introduce an approach that conducts such across-time comparison based on finding typical exemplars. Picking exemplars is an effective strategy used by humans for obtaining contrastive knowledge or for understanding unknown entity groups by their comparison to familiar groups (e.g., entities from the past compared to ones from present). We adopt a concise ILP model for maximizing the overall representativeness and comparability of the selected entity pairs. The experimental results demonstrate the effectiveness of our model compared to several competitive baselines.

In future, we will test our model on more heterogeneous and larger datasets where contexts of entities may be more difficult to be compared.