Consider a user searching for a list of civilians killed by the New York Police Department, who issues that query to a search engine. She lands on a web page where she finds the sentence: łOn Feb. 4, 1999, four NYPD officers in the Bronx fired 41 shots at a 22-year-old immigrant from Guinea named Amadou Diallo. ž 1 .
Can she use the information she now has ś a query and an example sentence with an instance of her goal identified ś to find other mentions of killings? Knowledge bases such as Wikipedia rarely contain articles about non-popular entities such as łAmadou Diallo", so we cannot adopt entity retrieval based approaches that search through knowledge base articles on entities organized by entity categories [21]. Document co-occurrence based retrieval models would find a large number of unrelated entities co-occurring with New York Police Department in different contexts and thus result in low precision [2]. Corpus-based set expansion methods can be useful, but they require more than one seed to infer the context and type of the desired entity class and do not take a query as input [20].
An information extraction approach to this problem is to construct a weak supervised training dataset and estimate a statistical NLP model (e.g., feature-rich logistic regression, CNN, CRF) [11]. Such a dataset is usually constructed by automatically labeling sentences with relevant instances from a knowledge base or a historical list. In the case of our example, the absence of a manually curated historical database of NYPD police killing would make this process infeasible.
Active Learning (AL) based approaches could be used to gather informative sentences using a human-in-the-loop setting [7]. However, we have just one training sentence and a statistical model estimated using that would produce ineffective queries for users. We need to retrieve at least a handful of sentences containing target entity instances to support an AL approach [6]. If we can retrieve such sentences and annotate them, the model would have some positive instances and might then be capable of learning actively. We focus on sentences because a sentence offers more context for interpreting entity relevance [7]. Moreover, retrieval of these sentences is also useful for other downstream applications like summarization, entity comprehension and retrieving entities in context [13,18,24].
In this work, we take an IR approach, retrieving sentences containing entities from a user desired list. Our contributions are: (1) we show that distant supervision with an entity annotated in the input training sentence can be effective if a query expansion technique is used; (2) we describe a semantic relevance model for query expansion and show that it is able to exploit entity co-occurrence; and, (3) we perform experimental evaluation with TREC List QA datasets and show that on average the top 20 sentences found by our approach contain nearly half of the target entities.
Related work comes from Corpus-based Set Expansion (CSE) , List Completion (LC), and Entity Ranking (ER). Each task is similar to ours but uses more seeds, external resources or lacks an example sentence for context.
Seed Selection for Active Learning. Active learning (AL) is a setting where a classifier determines which unlabeled data would contribute most to its learning process, and asks a human judge to label those data points [19]. Dligach and Palmer addressed the problem of seed selection for AL [6]. They considered a scenario where rare class examples constitute 5% of the data. They stated that 10 randomly selected seeds for AL would have 60% chances of selecting none of the rare class examples. They proposed Language Model (LM) based sampling for selecting seed words for the Word Sense Disambiguation task. Our work focuses on sentences selection for Information Extraction and hypothesizes that a semantic retrieval based approach is more suitable.
List QA. List questions are a special class of questions, where a system has to come up with a set of entities in response to a question [4,22]. Systems built for solving this task often leverage some form of well-trained entity recognizer to collect the most promising answer passages [12,16]. When the target type of a question is known in advance (e.g., who suggests person), identifying passages with that type of entity helps narrow down the set of candidate results. However, these approaches do not generalize to arbitrary types.
Set Expansion and List Completion. In the List or Set Completion task a small set of seed entities is given, with the aim of retrieving a complete set of target entities. Our work does not assume the existence of a knowledge-base, which makes it differ dramatically from set expansion.
Entity Ranking Systems. Our proposed task is also closely related to the entity ranking task in INEX 2009 [5] and TREC 2010 [1]. Approaches taken by participants in these tasks included the use of co-occurrence models, NER based type filtering, and context modeling [8]. Co-occurrence modeling was further applied based on context. The relation between a pair of entities was measured by their co-occurrence in documents (context-independent) and by computing similarity of the term vectors extracted from those documents (context-dependent) [3]. Some solutions augmented entity representation with entity synonyms and used search engines with that representation. Most of the participants of this task adopted external resources and were heavily dependent on Wikipedia for performing entity type filtering [8]. We study retrieving sentences with target entities by focusing only on textual content around entities.
We are given a collection of sentences, S = {S 1 , . . . , S n } drawn from a collection of documents, D q , identified by a list query, q. We also have a training sentence S q with a set of entities E q from S q identified. In our experiments, S q ∈ S, but that is not required. E q will normally have one entity in it, but we allow the possibility that a sentence lists more than one name of the target type. Broadly speaking, our objective is to define a function F (S i , S q ) that can score any sentence S i ∈ S based on the likelihood it contains a previously unseen entity of the same type characterized by E q . Here, the type of E q is implicitly indicated by the contextual information presented in the training sentence.
This task requires a relevant sentence to contain relevant as well as novel entities. Our evaluation set consists of a set of target entities, E t belonging to the same type as E q . Our scoring function F (•) scores each S i ∈ S to produce a ranked list of sentences. We define E k as the union of E q and the subset of E t that has been seen in sentences at ranks 1 to k, with E 0 = E q . We count a sentence at rank k as relevant only if E k E k -1 ś that is, if a new target entity occurs. Relevance thus incorporates novelty in this evaluation. Our goal is to show as many distinct entities as possible in the top k retrieved sentences, because more relevant entities with their context would give us more useful training data for AL.
We consider both topical and functional similarities to rank candidate sentences. To capture topical similarity, we use a sentence embedding-based approach to rank candidate sentences from S by the likelihood that their content matches the training sentence, S q . For the embedding-based retrieval step, we compute the similarity of the sentence embedding of S q to embeddings of all sentences from S. We find that despite the expansion implicit in embeddings, there is value in further expansion of S q using explicit query expansion methods. Furthermore, we achieve functional similarity by looking at the NER tag of the entities in a candidate sentence, which we refer to as type refinement approach.
In order to induce a semantic representation of our short sentences, we lean on the the distributed representation of words learned by the skip-gram model of word2vec [15]. The sentence embedding of any sentence S i is computed as the average of word embedding vectors for each token t ∈ S i . Wieting et al. [23] showed that a simple averaging over the embedding of the words in a sentence provides an effective representation for that sentence in two supervised NLP tasks: sentence similarity and sentence entailment. We do not have sentence similarity labels to train a model, and so we adopt this simple method of averaging.
We compute the similarity score for S i given query S q using cosine similarity as shown in Equation 1, with V being a function that returns the SE vector for its argument.
Score S E (S q , S i ) = cos[V (S q ), V (S i )] = δ (S i , S q )
(1)
To create a broader and more generalized representation of the training sentence S q , we build on the well-known IR technique of query expansion (QE). For expanding S q in this problem we select a set of k < n sentences from D q , Q e = {S 1 , S 2 , ..., S k } ⊂ S and combine Q e with S q to create an improved representation, S + q . We hypothesize that we can obtain a better representation of user intent with query expansion using the entity set E q from S q . As a result we construct
Thus we enrich our query representation by drawing in context of the query entity set E q . This approach is referred to as distant supervision and it is widely adopted by the NLP community [11]. However, distant supervision is generally applied when there is much more than one example. As it is difficult to learn a statistical model using distant supervision with a single training example, we construct a query model using the distantly supervised data. We take two different approaches to query model construction.
taining Q e , we compute the expanded representation S + q of S q using the following equation:
Informally, S + q is the weighted average of the embeddings of the sentences in Q e . The weight α i of sentence S i ∈ Q e is calculated as Score S E (S q , S i ).
Query Expansion with Terms (TQE).. We compute an embedding based query language model for expanding the sentence query S q . Given a set of expansion sentences Q e , we compute the expanded query model θ q using:
For a sentence S i , P(t |S i ) can be estimated as 1 l en(S i ) , and δ (S i , S q ) can be estimated as the cosine similarity of the embedding of S i and S q . After obtaining P(t |θ q ), we normalize the distribution, and finally compute the expanded representation S + q of S q using:
Our unit of retrieval is a sentence, and we want that sentence to contain novel entities of the target entity type. We use a standard NER tool to find the broad entity type from the query (e.g., person) and discard any candidate sentences that does not contain at least one unseen instance of the same broad entity type. As an example, assume that our target entity type is presidents of United States, and the broad entity type is person. Now, if a sentence at position k in the ranked list does not contain at least one new person instance, we assume that this sentence will thus not have any new president instance and we discard it to refine the ranked list. This approach has a chance to hurt some queries when the NER tagger is wrong (e.g., the type of the target entity łChicagož is movie, but the broad entity type identified by the NER tagger is location), but it improves overall performance in this study. They excluded list questions that seek common entities like countries, cities, etc. An example question from the refined dataset is list all the graduates of DePaw University. For each list question the dataset provides sentences from the top 1000 documents retrieved against the question. The document ranking is provided by TREC track organizers using BM25 ranking algorithm. For reproducibility purposes, we use the same sentence dataset, even though using a more modern retrieval algorithm may result in better overall results.
The dataset is particularly suitable for us considering the motivating example we provided in introduction -a user queries a search engine at first with her list information need. We call that set D q and draw our candidate set of sentences, S, from there, resulting in a sentence corpus containing an average of 25,229 sentences per query. If we randomly choose one sentence from the corpus, there is 0.7% probability of seeing a sentence that contains a target entity. Thus, only a small subset of these sentences are entity bearing ones. We found this small subset by matching all the sentences against the answer keys of the list question provided by TREC. Thus, for the list question asking about the graduates of DePaw University, we formed a large sentence corpus in which only a handful of sentences contain names of the graduates. We judged and selected our query sentence S q from those (120 sentences for 120 list queries) and evaluated the effectiveness of our approaches in retrieving the remaining sentences.
All sentences in the dataset are annotated with the Stanford Named Entity Recognizer [9]. Each sentence term receives a label from the set {OTHER, ORGANIZATION, NUMBER, DOLLAR, LO-CATION, TIME, MISC, PERSON, ORDINAL, DURATION, PERCENT, MONEY}. Among the 120 query sentences 10, 17, 1, 51, 5 and 36 contain instances of LOCATION, ORGANIZATION, NUMBER, PER-SON, MISC, and OTHER entities, respectively. We note that 34% of the entities identified are of OTHER type, which suggests that this dataset is challenging and perhaps interesting to the NER community as well. Moreover, the task gets harder with the novelty requirement, as a sentence would not be relevant in the ranked list if it does not contain a new entity of the target entity class.
Training Word Embeddings. We train word embeddings using the Stanford-NLP lemmatized form of the AQUAINT text corpus. Using the word2vec tool by Mikolov et al. [15], we derived 200-dimensional skipgram embeddings with a context window of 5, no negative samples, and the recommended sampling threshold of 10 -5 . The raw text of the AQUAINT corpus is 1.6 GB and it contains 517M words. These skipgram models were recommended as the most robust by Levy et al. [14]. For reproducibility, we release our word embeddings alongside our data.
The upper portion of Table 1 shows a comparison of our baselines for the proposed task: SE, BM25 and Conditional Random Field (CRF) model. We found that semantic search works better than keyword based search, and classic information extraction approach, CRF fails with one training sentence and a tagged entity. SE brings 90% of the entities in the top 1000 sentence, whereas BM25 finds 82% (not reported in table). High entity recall in the top 1000 sentences is necessary for our type-refinement approach. As a neural sentence retrieval baseline, we tried to train a siamese recurrent neural network [17] on Stanford SNLI sentence similarity corpus and applied it on our dataset for scoring candidate sentences. It performed poorly because of domain adaptation issues. We do not report those results for that reason.
The middle portion of the table shows the performance of sentence based query expansion explained in Section 4.2. Using the weight setW = {α 0 , . . . , α n } in Equation 2, we put uniform weights on the ranked query entity-bearing sentences to compute a weighted query representation. We also used the semantic similarity scores between query sentence and expansion sentences to obtain W . Both 1 focuses on term based QE (TQE) approaches explained in Section 4.2.2. We used the cosine similarity score from SE as document priors for computing term weights for TQE. The first term based method set uniform weights to all top k retrieved terms and it performs significantly worse compared to the weighted version. It shows that our term weight estimation is effective. Overall, the term and sentence based methods perform comparably in terms of precision and recall. The term based method achieves significant increase in MAP at cutoff 1000.
Interestingly, when we consider P(t |S) = 1 and δ (S, S q ) = 1 we obtain results very close to the weighted version (Section 4.2.2). That indicates that term count in expansion sentences is the most important component of the expanded query. To understand why this happens note that for each of the expansion sentences the query entity terms are common, so they get a high probability in the final query model. After looking at the top-ranked search results we found that a majority of the sentences contain the query entity itself. It seems that the model is thus considering query entitybearing sentences from across D q and selecting the sentences with novel co-occurring entities at the top ranks.
We proposed retrieval approaches using a single training sentence to retrieve more training data. In general, this approach can be taken for any task that suffers from data sparsity. Our approach could retrieve almost half of the target entities by considering only 20 sentences. If these sentences are annotated by a user, it might then be possible to build a model capable of doing active learning. In future work, we expect to combine IR and statistical models for active learning. A limitation of our model is its struggles to retrieve non-co-occurring entities in the top ranks. We aim to improve this model to further increase recall, perhaps by de-emphasizing the original selected target.
From https://www.huffingtonpost.com/2014/07/18/killed-by-the-nypd-black-men_ n_5600045.html