Automatic Keyphrase Extraction: A Survey of the State of the Art

As noted before, a set of phrases and words is typically extracted as candidate keyphrases using heuristic rules. These rules are designed to avoid spurious instances and keep the number of candidates to a minimum. Typical heuristics include (1) using a stop word list to remove stop words [33], (2) allowing words with certain part-of-speech tags (e.g., nouns, adjectives, verbs) to be candidate keywords [38, 53, 30], (3) allowing n-grams that appear in Wikipedia article titles to be candidates [13], and (4) extracting n-grams [56, 20, 37] or noun phrases [1, 57] that satisfy pre-defined lexico-syntactic pattern(s) [41].

Many of these heuristics have proven effective with their high recall in extracting gold keyphrases from various sources. However, for a long document, the resulting list of candidates can be long. Consequently, different pruning heuristics have been designed to prune candidates that are unlikely to be keyphrases [17, 29, 10, 59, 40].

Research on supervised approaches to keyphrase extraction has focused on two issues: task reformulation and feature design.

Existing unsupervised approaches to keyphrase extraction can be categorized into four groups.

Designing evaluation metrics for keyphrase extraction is by no means an easy task. To score the output of a keyphrase extraction system, the typical approach, which is also adopted by the SemEval-2010 shared task on keyphrase extraction, is (1) to create a mapping between the keyphrases in the gold standard and those in the system output using exact match, and then (2) score the output using evaluation metrics such as precision (P), recall (R), and F-score (F).

Conceivably, exact match is an overly strict condition, considering a predicted keyphrase incorrect even if it is a variant of a gold keyphrase. For instance, given the gold keyphrase “neural network”, exact match will consider a predicted phrase incorrect even if it is an expanded version of the gold keyphrase (“artificial neural network”) or one of its morphological (“neural networks”) or lexical (“neural net”) variants. While morphological variations can be handled using a stemmer [10], other variations may not be handled easily and reliably.

Human evaluation has been suggested as a possibility [36], but it is time-consuming and expensive. For this reason, researchers have experimented with two types of automatic evaluation metrics. The first type of metrics addresses the problem with exact match. These metrics reward a partial match between a predicted keyphrase and a gold keyphrase (i.e., overlapping $n$-grams) and are commonly used in machine translation (MT) and summarization evaluations. They include Bleu, Meteor, Nist, and Rouge. Nevertheless, experiments show that these MT metrics only offer a partial solution to problem with exact match: they can only detect a subset of the near-misses [24].

The second type of metrics focuses on how a system ranks its predictions. Given that two systems $A$ and $B$ have the same number of correct predictions, binary preference measure (Bpref) and mean reciprocal rank (MRR) [32] will award more credit to $A$ than to $B$ if the ranks of the correct predictions in $A$’s output are higher than those in $B$’s output. R-precision ($R_p$) is an IR metric that focuses on ranking: given a document with $n$ gold keyphrases, it computes the precision of a system over its $n$ highest-ranked candidates [60]. The motivation behind the design of $R_p$ is simple: a system will achieve a perfect $R_p$ value if it ranks all the keyphrases above the non-keyphrases.

Table 2 lists the best scores on some popular evaluation datasets and the corresponding systems. For example, the best F-scores on the Inspec test set, the DUC-2001 dataset, and the SemEval-2010 test set are 45.7, 31.7, and 27.5, respectively.³³A more detailed analysis of the results of the SemEval-2010 shared task and the approaches adopted by the participating systems can be found in Kim et al. (2013).

Two points deserve mention. First, F-scores decrease as document length increases. These results are consistent with the observation we made in Section 2 that it is more difficult to extract keyphrases correctly from longer documents. Second, recent unsupervised approaches have rivaled their supervised counterparts in performance [38, 10, 33]. For example, KP-Miner [11], an unsupervised system, ranked third in the SemEval-2010 shared task with an F-score of 25.2, which is comparable to the best supervised system scoring 27.5.

Although a few researchers have presented a sample of their systems’ output and the corresponding gold keyphrases to show the differences between them [56, 42, 37], a systematic analysis of the major types of errors made by state-of-the-art keyphrase extraction systems is missing.

To fill this gap, we ran four keyphrase extraction systems on four commonly-used datasets of varying sources, including Inspec abstracts [20], DUC-2001 news articles [43], scientific papers [27], and meeting transcripts [30]. Specifically, we randomly selected 25 documents from each of these four datasets and manually analyzed the output of the four systems, including tf*idf, the most frequently used baseline, as well as three state-of-the-art keyphrase extractors, of which two are unsupervised [53, 33] and one is supervised [37].

Our analysis reveals that the errors fall into four major types, each of which contributes significantly to the overall errors made by the four systems, despite the fact that the contribution of each of these error types varies from system to system. Moreover, we do not observe any significant difference between the types of errors made by the four systems other than the fact that the supervised system has the expected tendency to predict keyphrases seen in the training data. Below we describe these four major types of errors.

Overgeneration errors are a major type of precision error, contributing to 28–37% of the overall error. Overgeneration errors occur when a system correctly predicts a candidate as a keyphrase because it contains a word that appears frequently in the associated document, but at the same time erroneously outputs other candidates as keyphrases because they contain the same word. Recall that for many systems, 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 on athlete Ben Johnson in Figure 1, where the keyphrases are boldfaced. As we can see, the word Olympic(s) has a significant presence in the document. Consequently, many systems not only correctly predict Olympics as a keyphrase, but also erroneously predict Olympic movement as a keyphrase, yielding overgeneration errors.

Infrequency errors are a major type of recall error contributing to 24–27% of the overall error. Infrequency errors occur when a system fails to identify a keyphrase owing to its infrequent presence in the associated document [31]. 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 Ben Johnson example, many keyphrase extractors fail to identify 100-meter dash and gold medal as keyphrases, resulting in infrequency errors.

Redundancy errors are a type of precision error contributing to 8–12% of the overall error. 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 a system’s failure 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, Olympics and Olympic games refer to the same concept, so a system that predicts both of them as keyphrases commits a redundancy error.

Evaluation errors are a type of recall error contributing to 7–10% of the overall error. An evaluation error occurs when a system outputs a candidate that is semantically equivalent to a gold keyphrase, but is considered erroneous by a scoring program because of its failure to recognize that the predicted phrase and the corresponding gold keyphrase are semantically equivalent. In other words, an evaluation error is not an error made by a keyphrase extractor, but an error due to the naivety of a scoring program. In our example, while Olympics and Olympic games refer to the same concept, only the former is annotated as keyphrase. Hence, an evaluation error occurs if a system predicts Olympic games but not Olympics as a keyphrase and the scoring program fails to identify them as semantically equivalent.

We recommend that background knowledge be extracted from external lexical databases (e.g., YAGO2 [47], Freebase [4], BabelNet [39]) to address the four types of errors discussed above.

First, we discuss how redundancy errors could be addressed by using the background knowledge extracted from external databases. Note that if we can identify semantically equivalent candidates, then we can reduce redundancy errors. The question, then, is: can background knowledge be used to help us identify semantically equivalent candidates? To answer this question, note that Freebase, for instance, has over 40 million topics (i.e., real-world entities such as people, places, and things) from over 70 domains (e.g., music, business, education). Hence, before a system outputs a set of candidates as keyphrases, it can use Freebase to determine whether any of them is mapped to the same Freebase topic. Referring back to our running example, both Olympics and Olympic games are mapped to a Freebase topic called Olympic games. Based on this information, a keyphrase extractor can determine that the two candidates are aliases and should output only one of them, thus preventing a redundancy error.

Next, we discuss how infrequency errors could be addressed using background knowledge. A natural way to handle this problem would be to make an infrequent keyphrase frequent. To accomplish this, we suggest exploiting an influential idea in the keyphrase extraction literature: the importance of a candidate is defined in terms of how related it is to other candidates in the text (see Section 3.3.1). In other words, if we could relate an infrequent keyphrase to other candidates in the text, we could boost its importance.

We believe that this could be accomplished using background knowledge. The idea is to boost the importance of infrequent keyphrases using their frequent counterparts. Consider again our running example. All four systems have managed to identify Ben Johnson as a keyphrase due to its significant presence. Hence, we can boost the importance of 100-meter dash and gold medal if we can relate them to Ben Johnson.

To do so, note that Freebase maps a candidate to one or more pre-defined topics, each of which is associated with one or more types. Types are similar to entity classes. For instance, the candidate Ben Johnson is mapped to a Freebase topic with the same name, which is associated with Freebase types such as Person, Athlete, and Olympic athlete. Types are defined for a specific domain in Freebase. For instance, Person, Athlete, and Olympic athlete are defined in the People, Sports, and Olympics domains, respectively. Next, consider the two infrequent candidates, 100-meter dash and gold medal. 100-meter dash is mapped to the topic Sprint of type Sports in the Sports domain, whereas gold medal is mapped to a topic with the same name of type Olympic medal in the Olympics domain. Consequently, we can relate 100-meter dash to Ben Johnson via the Sports domain (i.e., they belong to different types under the same domain). Additionally, gold medal can be related to Ben Johnson via the Olympics domain.

As discussed before, the relationship between two candidates is traditionally established using co-occurrence information. However, using co-occurrence windows has its shortcomings. First, an ad-hoc window size cannot capture related candidates that are not inside the window. So it is difficult to predict 100-meter dash and gold medal as keyphrases: they are more than 10 tokens away from frequent words such as Johnson and Olympics. Second, the candidates inside a window are all assumed to be related to each other, but it is apparently an overly simplistic assumption. There have been a few attempts to design Wikipedia-based relatedness measures, with promising initial results [13, 33, 37].⁴⁴Note that it may be difficult to employ our recommendations to address infrequency errors in informal text with uncorrelated topics because the keyphrases it contains may not be related to each other (see Section 2).

Overgeneration errors could similarly be addressed using background knowledge. Recall that Olympic movement is not a keyphrase in our example although it includes an important word (i.e., Olympic). Freebase maps Olympic movement to a topic with the same name, which is associated with a type called Musical Recording in the Music domain. However, it does not map Olympic movement to any topic in the Olympics domain. The absence of such a mapping in the Olympics domain could be used by a keyphrase extractor as a supporting evidence against predicting Olympic movement as a keyphrase.

Finally, as mentioned before, evaluation errors should not be considered errors made by a system. Nevertheless, they reveal a problem with the way keyphrase extractors are currently evaluated. To address this problem, one possibility is to conduct human evaluations. Cheaper alternatives include having human annotators identify semantically equivalent keyphrases during manual labeling, and designing scoring programs that can automatically identify such semantic equivalences.