WikiRank: Improving Keyphrase Extraction Based on Background Knowledge

Abstract: Keyphrase is an efficient representation of the main idea of documents. While background knowledge can provide valuable information about documents, they are rarely incorporated in keyphrase extraction methods. In this paper, we propose WikiRank, an unsupervised method for keyphrase extraction based on the background knowledge from Wikipedia. Firstly, we construct a semantic graph for the document. Then we transform the keyphrase extraction problem into an optimization problem on the graph. Finally, we get the optimal keyphrase set to be the output. Our method obtains improvements over other state-of-art models by more than 2% in F1-score.

As the amount of published material rapidly increases, the problem of managing information becomes more difficult. Keyphrase, as a concise representation of the main idea of the text, facilitates the management, categorization, and retrieval of information. Automatic keyphrase extraction concerns “the automatic selection of important and topical phrases from the body of a document”. Its goal is to extract a set of phrases that are related to the main topics discussed in a given document BIBREF0 .
Existing methods of keyphrase extraction could be divided into two categories: supervised and unsupervised. While supervised approaches require human labeling, at the same time needs various kinds of training data to get better generalization performance, more and more researchers focus on unsupervised methods.
Traditional methods of unsupervised keyphrase extraction mostly focus on getting information of document from word frequency and document structure BIBREF0 , however, after years of attempting, the performance seems very hard to be improved any more. Based on this observation, it is reasonable to suspect that the document itself possibly cannot provide enough information for keyphrase extraction task.
To get good coverage of the main topics of the document, Topical PageRank BIBREF1 started to adopt topical information in automatic keyphrase extraction. The main idea of Topical PageRank is to extract the top topics of the document using LDA, then sum over the scores of a candidate phrase under each topic to be the final score. The main problems with Topical PageRank are: First, The topics are too general. Second, since they are using LDA, they only classify the words to several topics, but don't know what the topics exactly are. However, the topical information we need for keyphrase extraction should be precise. As shown in Figure , the difference between a correct keyphrase sheep disease and an incorrect keyphrase incurable disease could be small, which is hard to be captured by rough topical categorization approach.
To overcome the limitations of aforementioned approaches, we propose WikiRank, an unsupervised automatic keyphrase extraction approach that links semantic meaning to text
The key contribution of this paper could be summarized as follows:
Figure shows part of an example document. In this figure, the gold keyphrases are marked with bold, and the keyphrases extracted by the TextRank system are marked with parentheses. We are going to illustrate the errors exist in most of present keyphrase extraction systems using this example. Overgeneration errors occur when a system correctly predicts a candidate as a keyphrase because it contains a word that frequently appears in the associated document, but at the same time erroneously outputs other candidates as keyphrases because they contain the same word BIBREF0 . It is not easy to reject a non-keyphrase containing a word with a high term frequency: many unsupervised systems score a candidate by summing the score of each of its component words, and many supervised systems use unigrams as features to represent a candidate. To be more concrete, consider the news article in Figure . The word Cattle has a significant presence in the document. Consequently, the system not only correctly predict British cattle as a keyphrase, but also erroneously predict cattle industry, cattle feed, and cattle brain as keyphrases, yielding overgeneration errors.
Redundancy errors occur when a system correctly identifies a candidate as a keyphrase, but at the same time outputs a semantically equivalent candidate (e.g., its alias) as a keyphrase. This type of error can be attributed to the failure of a system to determine that two candidates are semantically equivalent. Nevertheless, some researchers may argue that a system should not be penalized for redundancy errors because the extracted candidates are in fact keyphrases. In our example, bovine spongiform encephalopathy and bse refer to the same concept. If a system predicts both of them as keyphrases, it commits a redundancy error.
Infrequency errors occur when a system fails to identify a keyphrase owing to its infrequent presence in the associated document. Handling infrequency errors is a challenge because state-of-the-art keyphrase extractors rarely predict candidates that appear only once or twice in a document. In the Mad cow disease example, the keyphrase extractor fails to identify export and scrapie as keyphrases, resulting in infrequency errors.
The WikiRank algorithm includes three steps: (1) Construct the semantic graph including concepts and candidate keyphrases; (2)(optional) Prune the graph with heuristic to filter out candidates which are likely to be erroneously produced; (3) Generate the best set of keyphrases as output.
This is one of the crucial steps in our paper that connects the plain text with human knowledge, facilitating the understanding of semantics. In this step, we adopt TAGME BIBREF2 to obtain the underlying concepts in documents.
TAGME is a powerful topic annotator. It identifies meaningful sequences of words in a short text and link them to a pertinent Wikipedia page, as shown in Figure . These links add a new topical dimension to the text that enable us to relate, classify or cluster short texts.
This step is to filter out unnecessary word tokens from the input document and generate a list of potential keywords using heuristics. As reported in BIBREF3 , most manually assigned keyphrases turn out to be noun groups. We follow BIBREF4 and select candidates lexical unit with the following Penn Treebank tags: NN, NNS, NNP, NNPS, and JJ, which are obtained using the Stanford POS tagger BIBREF5 , and then extract the noun groups whose pattern is zero or more adjectives followed by one or more nouns. The pattern can be represented using regular expressions as follows INLINEFORM0 
where JJ indicates adjectives and various forms of nouns are represented using NN, NNS and NNP .
We build a semantic graph INLINEFORM0 in which the set of vertices INLINEFORM1 is the union of the concept set INLINEFORM2 and the candidate keyphrase set INLINEFORM3 —i.e., INLINEFORM4 . In the graph, each unique concept INLINEFORM5 or candidate keyphrase INLINEFORM6 for document INLINEFORM7 corresponds to a node. The node corresponds to a concept INLINEFORM8 and the node corresponds to a candidate keyphrase INLINEFORM9 are connected by an edge INLINEFORM10 , if the candidate keyphrase INLINEFORM11 contains concept INLINEFORM12 according to the annotation of TAGME. Part of the semantic graph of the sample document is shown in Figure . Concepts corresponding to are shown in Table .
According to BIBREF1 , good keyphrases should be relevant to the major topics of the given document, at the same time should also have good coverage of the major topics of the document. Since we represent the topical information with concepts annotated with TAGME, the goal of our approach is to find the set INLINEFORM0 consisting of INLINEFORM1 keyphrases, to cover concepts (1) as important as possible (2) as much as possible.
Let INLINEFORM0 denote the weight of concept INLINEFORM1 . We compute INLINEFORM2 as the frequency INLINEFORM3 exists in the whole document INLINEFORM4 . To quantify how good the coverage of a keyphrase set INLINEFORM5 is, we compute the overall score of the concepts that INLINEFORM6 contains.
Consider a subgraph of INLINEFORM0 , INLINEFORM1 , which captures all the concepts connected to INLINEFORM2 . In INLINEFORM3 , the set of vertices INLINEFORM4 is the union of the candidate keyphrase set INLINEFORM5 , and the set INLINEFORM6 of concepts that nodes in INLINEFORM7 connect to. The set of edges INLINEFORM8 of INLINEFORM9 is constructed with the edges connect nodes in INLINEFORM10 with nodes in INLINEFORM11 .
We set up the score of a concept INLINEFORM0 in the subgraph INLINEFORM1 as following: DISPLAYFORM0 
where INLINEFORM0 is the weight of INLINEFORM1 as we defined before, and INLINEFORM2 is the degree of INLINEFORM3 in the subgraph INLINEFORM4 . Essentially, INLINEFORM5 is equal to the frequency that concept INLINEFORM6 is annotated in the keyphrase set INLINEFORM7 .
The optimization problem is defined as: The goal of the optimization problem is to find the candidate keyphrase set INLINEFORM0 , such that the sum of the scores of the concepts annotated from the phrases in INLINEFORM1 is maximized.
We propose an algorithm to solve the optimization problem, as shown in Algorithm . In each iteration, we compute the score INLINEFORM0 for all candidate keyphrases INLINEFORM1 and include the INLINEFORM2 with highest score into INLINEFORM3 , in which INLINEFORM4 evaluates the score of concepts added to the new set INLINEFORM5 by adding INLINEFORM6 into INLINEFORM7 .
In practice, computing score for all the candidate keyphrases is not always necessary, because some of the candidates are very unlikely to be gold keyphrase that we can remove them from our graph before applying the algorithm to reduce the complexity.
In this section, we introduce three heuristic pruning steps that significantly reduces the complexity of the optimization problem without reducing much of the accuracy.
Step 1. Remove the candidate keyphrase INLINEFORM0 from original graph INLINEFORM1 , if it is not connected to any concept.
The intuition behind this heuristic is straightforward. Since our objective function is constructed over concepts, if a candidate keyphrase INLINEFORM0 doesn't contain any concept, adding it to INLINEFORM1 doesn't bring any improvement to the objective function, so INLINEFORM2 is irrelevant to our optimization process. Pruning INLINEFORM3 would be a wise decision.
Step 2. Remove the candidate keyphrase INLINEFORM0 from original graph INLINEFORM1 , if it is only connected to one concept that only exists once in the document
If a candidate keyphrase contains fewer concepts, or the concepts connects to it barely exist in the document, we think this candidate keyphrase contributes less valuable information to the document. In practice, there are numerous INLINEFORM0 pairs in graph INLINEFORM1 that is isolated from the center of the graph. We believe they are irrelevant to the major topic of the document.
Step 3. For a concept INLINEFORM0 connecting to more than INLINEFORM1 candidate keyphrases, remove any candidate keyphrase INLINEFORM2 which (1)Does not connect to any other concept. AND (2)The ranking is lower than INLINEFORM3 th among all candidate keyphrases connect to INLINEFORM4 .(In practice, INLINEFORM5 is usually 3 or 4.)
According to equation EQREF10 , if there are already INLINEFORM0 instances of concept INLINEFORM1 in the INLINEFORM2 , adding the INLINEFORM3 th instance of INLINEFORM4 will only contribute INLINEFORM5 to INLINEFORM6 . At the same time, among all the candidate keyphrases connected to concept INLINEFORM7 , our optimization process always chooses the ones that connect to other concepts as well over the ones that do not connect to any other concept. Combining these two logic, a candidate satisfying the constrains of Step 3 is not likely to be picked in the best keyphrase set INLINEFORM8 , so we can prune it before the optimalization process.
The DUC-2001 dataset BIBREF6 , which is a collection of 308 news articles, is annotated by BIBREF7 .
The Inspec dataset is a collection of 2,000 abstracts from journal papers including the paper title. This is a relatively popular dataset for automatic keyphrase extraction, as it was first used by BIBREF3 and later by Mihalcea and BIBREF8 and BIBREF9 .
The NUS Keyphrase Corpus BIBREF10 includes 211 scientific conference papers with lengths between 4 to 12 pages. Each paper has one or more sets of keyphrases assigned by its authors and other annotators. The number of candidate keyphrases that can be extracted is potentially large, making this corpus the most challenging of the four.
Finally, the ICSI Meeting Corpus (Janin et al., 2003), which is annotated by Liu et al. (2009a), includes 161 meeting transcriptions. Unlike the other three datasets, the gold standard keys for the ICSI corpus are mostly unigrams.
For comparing with our system, we reimplemented SingleRank and Topical PageRank. Table shows the result of our reimplementation of SingleRank and Topical PageRank, as well as the result of our system. Note that we predict the same number of phrase ( INLINEFORM0 ) for each document while testing all three methods.
The result shows our result has guaranteed improvement over SingleRank and Topical PageRank on all four corpora.
We proposed an unsupervised graph-based keyphrase extraction method WikiRank. This method connects the text with concepts in Wikipedia, thus incorporate the background information into the semantic graph and finally construct a set of keyphrase that has optimal coverage of the concepts of the document. Experiment results show the method outperforms two related keyphrase extraction methods.
We suggest that future work could incorporate more other semantic approaches to investigate keyphrase extraction task. Introducing the results of dependency parsing or semantic parsing (e.g., OntoUSP) in intermediate steps could be helpful.

Figure and table captions:
Figure 1: Part of the Sample Document 2 Bold: Gold Keyphrase In parentheses: Keyphrase generated by TextRank algorithm Underlined: Keyphrase annotated to Wikipedia Entity by TagMe
Figure 2: Part of the Semantic Graph of the Sample Document Circle: Concept Rectangle: Candidate Keyphrase
Table 1: Part of the Concepts Annotated from the Sample Document
Table 2: The Result of our System as well as the Reimplementation of SingleRank and Topical PageRank on four Corpora

Questions about this paper:
what was their model's f1 score?

Answers:
F1 score their system achieved is 27.53, 27.01, 4.30 and 9.10 on DUC, Inspec, ICSI and NUS dataset respectively.