1 Introduction
With 144.8 billion emails sent every day around the world,Footnote 1 emails represent an essential mode of digital communication. The market share of emails is tremendous, and largely untapped. Not only are traditional applications of keyword extraction important for emails, but also emails present a unique scenario in their own right. According to Wasserman, up to 28% of workers’ time is spent checking emails,Footnote 2 and most work emails are not important.Footnote 3 It is therefore paramount that we be able to somehow sort this enormous pile of emails into a workable collection so that the more important ones are dealt with immediately, whereas others are relegated to future inspection (Laclavík and Maynard Reference Laclavík and Maynard2009).
While all existing email clients include some form of free text search to help users identify relevant threads of conversation, keyword extraction from emails can help us spot salient phrases from emails, thereby automatically tagging/categorizing them into appropriate folders (or ‘labels’), and in effect, giving us a faceted search functionality complementary to the vanilla text search on emails.
In this paper, we address the task of automatic keywordFootnote 4 extraction from emails, as a way to automatically annotate email content with salient words or phrases that can help us decide on the importance or relevance of an email or thread. The availability of keywords could facilitate the access to email on mobile devices, and they could be used as a preprocessing step for smart email applications that aim to classify or prioritize emails. Keywords could help visualize emails in the form of ‘keyword clouds’ with larger keywords indicating more salience (Chuang, Manning and Heer Reference Chuang, Manning and Heer2012), and the clouds can be interactive so that when a user clicks or taps on a certain keyword, all emails pertaining to that keyword get retrieved. Different colors indicate different ‘keyword topics’, so that all keywords under a certain topic get grouped together in one area of the cloud.
Furthermore, keywords form their own social networks (Grineva, Grinev and Lizorkin Reference Grineva, Grinev and Lizorkin2009), and important meta-information about documents can be mined by looking into networks of keywords. Keyword networks also serve as a powerful visualization tool by themselves, so that users who are interested in relationship (or association strength) between two keywords or keyword cliques may benefit from looking at such visualizations.
Keyword extraction is an important problem in natural language processing, where the goal is to identify the most important words and phrases in a document. The keywords can either serve as a short summary of the document, giving users an overview of its contents; or they can indicate the topics that are being discussed.
While it may be argued that keywords are often an impoverished representation of the underlying topic space, and that there are alternative models that capture such spaces (Blei, Ng and Jordan Reference Blei, Ng and Jordan2003; Dredze et al. Reference Dredze, Wallach, Puller and Pereira2008; Liu et al. Reference Liu, Huang, Zheng and Sun2010), it is important to consider that probabilistic topic models need to be trained on large corpora, and they often suffer from scalability issues. Keyword extraction, on the other hand, can be performed in both supervised and unsupervised fashion, and most keyword extraction methods do not need large training corpora.
Keyword extraction has traditionally been the domain of librarians and book indexers, but more recently the problem has seen a number of novel applications. For instance, keywords have been used to thematically group web sites (Tonella et al. Reference Tonella, Ricca, Pianta and Girardi2003), where authors reverse-engineered a graph of webpages by clustering them, and using keywords to label the clusters. Keywords were used as anchor phrases to link to Wikipedia articles in Mihalcea and Csomai (Reference Mihalcea and Csomai2007), and as summary topics to visualize how topics change over time in online Korean news articles (Lee and Kim Reference Lee and Kim2008). Keywords have been used to target advertisements on webpages (Yih, Goodman and Carvalho Reference Yih, Goodman and Carvalho2006), and as indicators of academic paper content and user interest in a content-based paper recommendation system (Ferrara, Pudota and Tasso Reference Ferrara, Pudota, Tasso, Agosti, Esposito, Meghini and Orio2011).
With such a large number of applications, it is surprising that keyword extraction from emails has not received much attention from the research community. In this paper, we introduce a new dataset, consisting of single and thread emails manually annotated with keywords, and describe a number of features that can be used for unsupervised or supervised email keyword extraction. Through several evaluations, we show that we can achieve results that significantly improve over several baselines, and also improve over state-of-the-art systems participating in the SemEval 2010 keyphrase extraction task (Kim et al. Reference Kim, Medelyan, Kan and Baldwin2010).
2 Background and related work
Keyword extraction usually proceeds in three steps: candidate extraction, ranking/classification, and postprocessing. In the candidate extraction step, potentially important phrases are identified and extracted from the documents. In the ranking/classification step, these candidate terms are either ranked according to some ranking function derived from the document structure, or they are classified as to whether they represent key terms or not. In the postprocessing step, top k terms from the ranked list (or terms that are classified as keywords) are semantically normalized to yield a set of phrases so that each denotes a single concept.
In practice, there are some good heuristics for candidate extraction. Hulth (Reference Hulth2003) noted that base noun phrases often constitute a predominant form of keyphrase. She further leveraged previous studies in observing that specific patterns of part-of-speech tags are beneficial for keyword extraction. Csomai and Mihalcea (Reference Csomai and Mihalcea2007) experimented with stopword-filtered n-grams and named entities as potential keywords.
The second step – ranking/classification – is trickier, because it is not immediately obvious what ranking function or phrase features to use. In a study by Hasan and Ng (Reference Hasan and Ng2010), tfidf was shown to be a surprisingly robust candidate. While conceptually simple, it beats other more complex ranking strategies. Other important features for keyword classification include tfidf (Nguyen and Kan Reference Nguyen and Kan2007; Jiang, Hu and Li Reference Jiang, Hu and Li2009; Li et al. Reference Li, Zhou, Juan and Han2010), first occurrence position of the phrase (Hulth Reference Hulth2003), capitalization (Li et al. Reference Li, Zhou, Juan and Han2010), phrase length (in words) and is-in-title (Jiang et al. Reference Jiang, Hu and Li2009).
Two salient groups of ranking functions deal with the phraseness and informativeness of a candidate phrase (Tomokiyo and Hurst Reference Tomokiyo and Hurst2003). Informativeness denotes how much information content a stand-alone phrase carries with it, and is usually determined by the number of occurrences of that phrase in a background corpus (Tomokiyo and Hurst Reference Tomokiyo and Hurst2003). Phraseness, on the other hand, is a measure of how cohesive or tightly-linked a phrase is; in other words, whether the constituent words of a phrase come together more often than by chance. Phraseness is estimated based on the co-occurrence frequency of words in a foreground corpus. A final ranking of phrases is produced by some linear combination of phraseness and informativeness scores. Tomokiyo and Hurst (Reference Tomokiyo and Hurst2003) proposed the use of language models in estimating phraseness and informativeness, whereas Csomai and Mihalcea (Reference Csomai and Mihalcea2007) used chi-squared test. A different formulation is that of keyphraseness, proposed by Mihalcea and Csomai (Reference Mihalcea and Csomai2007), where the probability of a word or a phrase to be linked to a Wikipedia article, calculated across the entire Wikipedia, is used as an indication of how likely that word or phrase is to be selected as a keyword.
Note that the above-mentioned phrase ranking strategies are mostly ad hoc, and they emerged as a way to heuristically assess the purported importance or relevance of a phrase. There is, however, a completely different class of ranking algorithms that look into this problem from a more cognitively appealing standpoint. These algorithms look into the structure of word co-occurrence networks, where nodes are word types and edges are word collocations. Mihalcea and Tarau (Reference Mihalcea, Tarau, Lin and Wu2004) introduced TextRank and observed that in these networks, important words can be thought of as being endorsed by other words, and this leads to an interesting phenomenon. Words that are most important, viz. keywords, emerge as the most central words in the resulting network, with high degree and PageRank (Page et al. Reference Page, Brin, Motwani and Winograd1998). A stream of studies ensued after the seminal work of TextRank (see Hasan and Ng (Reference Hasan and Ng2010) for a detailed comparison). While most looked into variants of PageRank, Litvak and Last (Reference Litvak and Last2008) experimented with the HITS algorithm (Kleinberg Reference Kleinberg1999), while Boudin (Reference Boudin2013) investigated other indices like degree, betweenness and closeness.
The final important step in keyphrase extraction is postfiltering. Extracted phrases are disambiguated and normalized for morpho-syntactic variations and lexical synonymy (Csomai and Mihalcea Reference Csomai and Mihalcea2007). Adjacent words are also sometimes collapsed into phrases, for a more readable output.
Benchmark datasets for keyword extraction include ICSI – a collection of meeting transcripts divided into 201 segments (Liu et al. Reference Liu, Pennell, Liu and Liu2009), NUS – a set of 211 academic papers (Nguyen and Kan Reference Nguyen and Kan2007), INSPEC – 2,000 titles and abstracts from journal papers (Hulth Reference Hulth2003), and SemEval – 184 academic papers from SemEval 2010 Keyphrase Extraction Task (Kim et al. Reference Kim, Medelyan, Kan and Baldwin2010). Given the preponderance of keyword-annotated datasets in the academic domain, most research in keyword extraction has focused on academic papers.
There are only three previous studies that we are aware of that considered keyword extraction from emails. Turney (Reference Turney2000) reports a study that pioneered email keyword extraction, but his dataset has not been released. Goodman and Carvalho (Reference Goodman and Carvalho2005) worked with emails, but since their goal was to extract implicit search queries from emails, and not keywords, their dataset is not useful to us. Dredze et al. (Reference Dredze, Wallach, Puller and Pereira2008) extracted summary keywords from emails using latent concept models, and evaluated the extracted keywords in two novel tasks – automated foldering (predicting which folder an email should go to), and recipient prediction. While Dredze et al.’s study did look into (unsupervised) email keyword extraction, they performed an extrinsic evaluation of their approach rather than intrinsically evaluating on a gold standard dataset.
Also relevant is the work by Laclavík and Maynard (Reference Laclavík and Maynard2009), who discuss general strategies for email classification, storage and integration with other information management systems. They further point out that email communication in a modern organization is mostly action-oriented, and that knowledge workers of all kinds interact with their emails on a daily basis. This stands in sharp contrast with keyword extraction in the academic domain,Footnote 5 where papers are meant for other researchers who are reasonably familiar with the domain – and therefore use formal and scientific vocabulary. Furthermore, academic communication via papers is single-way (author to audience), and dissemination-oriented. Also, unlike academic papers, emails mostly discuss topics at hand, including urgent ones. Hence, emails stand to benefit from their own keyword extraction system. In fact, Laclavík and Maynard briefly hinted at email keyword extraction as a way to combat the email information overload (cf. Section 5).
3 Keyword extraction pipeline
Our keyword extraction systems proceed in five stages:
-
(1) Email processing
-
(2) Candidate extraction
-
(3) Preprocessing
-
(4) Ranking/Classification
-
(5) Postprocessing
As a first step, we sentence-segment each email manually, followed by tokenization based on whitespace. We ignore email metadata such as filename, ID, date, from and to, subject and signature fields. This was done to ensure that our systems are only focusing on the email text. We also remove numbers and words consisting of one or two characters.
In the candidate extraction stage, we generate candidate phrases from a document. We experimented with four types of phrase candidates, and found noun phrases and named entities to be the best (Section 4.2).
In the preprocessing stage, we clean up the phrase candidates by removing punctuation, folding to lowercase, and removing numbers and leading and trailing stopwords. We also implemented a preprocessing heuristic, which is a syntactic filter that only considers nouns and adjectives while constructing the word co-occurrence network. This is based on the observation that most keywords consist of nouns and adjectives (along with function words), and therefore a part-of-speech filter at this stage can help eliminate some of the potential noise.
In the fourth and most important stage, we extract keywords from emails using two approaches – unsupervised and supervised. In the unsupervised (ranking) approach, we (a) rank words using several linguistic and centrality-based features, and then collapse the top-ranked adjacent words to form keyphrases; (b) rank candidate phrases (noun phrases and named entities) using several phrase features – both linguistic and centrality-based, and then extract the top-ranked phrases as keyphrases. In the supervised (classification) approach, we classify candidate phrases as keyphrase vs. non-keyphrase using phrase features, and return the ones classified as keyphrase. Both approaches are evaluated on our own dataset consisting of 319 keyword-annotated emails.
In the fifth stage, we implement a postprocessing heuristic (for word ranking) that constructs longer key phrases starting with the selected keywords, by collapsing adjacent words from the top k ranking into phrases.Footnote 6 The problem with this collapsing strategy is that the final number of phrases cannot be predicted from the number of input keywords k, and there is no control over the number of collapsed phrases. Other variants of this collapsing strategy that alleviate this problem are possible, but they are found to introduce new complications, e.g., very long keywords or several keywords that are semantically redundant. We therefore use the basic collapsing heuristic described before.
4 Features for keyword extraction
We extract two broad classes of features for keyword extraction from emails: word features and phrase features. These features are either used by themselves, in an unsupervised fashion, or together in a supervised setting.
In the following, we describe each feature, along with a short note on its potential utility in keyword extraction. Note that word and centrality features are extracted after removing stopwords.
4.1 Word features
Word features are used to rank word types (i.e., unique words) based on their frequency, positional and surface properties.
-
• Tf: Raw frequency of a word type in a document.Footnote 7 It is an important indicator of the word’s saliency.
-
• Tf.idf: Raw frequency of a word type multiplied by its idf (inverse document frequency) computed on the British National Corpus (Clear Reference Clear, Landow and Delany1993).
-
• First position: Position of the first occurrence of a word in a document. Position is measured by number of word tokens since the beginning of the document. Words appearing towards the beginning of a document often contain introductory information, thereby being important from the perspective of keyword extraction.
-
• Last position: Position of the last occurrence of a word in a document. Position, as before, is measured by number of word tokens since the beginning of the document. Words appearing near the end of a document may contain summary information, thereby becoming important.
-
• Normalized first position: First position feature, normalized by the number of words in the document.
-
• Normalized last position: Last position feature, normalized by the number of words in the document.
-
• Word length: Number of characters in a word. Longer words sometimes contain richer information owing to word-compounding, morphology, etc.
-
• Is capitalized?: Whether the word is capitalized. This is a binary feature. Word capitalization is often a strong cue for detecting named entities.
-
• Is in subject?: Whether the word appears in the subject line of an email/thread. This is another binary feature. Words appearing in an email’s subject line often contain important information, much like the words in the title line of a general document (Jiang et al. Reference Jiang, Hu and Li2009).
We also implement word centrality features, which are features defined on word co-occurrence networks (Mihalcea and Tarau Reference Mihalcea, Tarau, Lin and Wu2004). For each email, a word co-occurrence network is constructed by adding all the word types (i.e., unique words) as nodes, and by drawing an edge between the words that occur next to each other. Centrality measures on such co-occurrence networks can yield a powerful set of features for keyword extraction. In this work, we focus on the following centrality features:
-
• Degree: Number of edges incident to a node. Since word types implicitly endorse each other via collocation edges, the more edges that are incident to a word, the more important the word becomes.
-
• PageRank: Stationary probability of a random walk visiting a particular word in the word co-occurrence network. When used with teleportation, such a random walk ends up assigning higher probabilities to more important words in the network (Mihalcea and Tarau Reference Mihalcea, Tarau, Lin and Wu2004).
-
• Coreness: Measure of how ‘deep’ a word is in the co-occurrence network. The ‘deeper’ a word, the more its importance. This feature is inspired by the core-periphery structure of small-world networks, and computed using the so-called k-cores decomposition (Seidman Reference Seidman1983; Batagelj and Zaveršnik Reference Batagelj and Zaveršnik2003).
-
• Neighborhood size (order one): Number of immediate neighbors to a node. It is a version of node degree that disregards self-loops, which can arise in word co-occurrence networks due to constructions such as ‘again, again and again’. The more neighbors a node have, the higher its importance.
4.2 Phrase features
In addition to features reflecting the importance of individual words, we also calculate phrase features, which are used to rank/classify entire phrases. More precisely, these features are used to classify (document, phrase) pairs, as explained in the next section.
Following Csomai and Mihalcea (Reference Csomai and Mihalcea2007), we extract four types of candidate keywords: stopword-filtered n-grams (n = 1, 2, 3, 4), stopword-filtered base noun phrases, named entities extracted using the Stanford Named Entity Recognizer (NER) (Finkel, Grenager and Manning Reference Finkel, Grenager and Manning2005), and named entities extracted using an unsupervised heuristic (sequences of capitalized words that never appear without capitalization). We use the CRFTagger (Phan Reference Phan2006) for part-of-speech tagging, and Mark Greenwood’s NP chunker for base noun phrase identification.Footnote 8 The following features are used to rank these candidate keywords:
-
• Phrase Tf: Raw frequency of a phrase in a document.
-
• Phrase Idf: Inverse document frequency of a phrase, computed as the average of idfs of its constituent words. The word idfs were computed on the British National Corpus.
-
• Phrase Tf.idf: Raw frequency of a phrase multiplied by its idf.
-
• Within-document frequency: Number of sentences a phrase appeared in (for a particular document). The more sentences a phrase appears in, the higher its importance.
-
• Mean length of containing sentences: Mean length of the sentences a phrase appeared in (for a particular document) – in word tokens, word types and (non-space) characters. These three features encode the importance of the containing sentences. Longer sentences should carry more information.
-
• Phrase length: Length of a phrase calculated as the number of constituent word tokens and non-space characters. These two features encode the fact that longer phrases usually carry more information.
-
• Length of the containing document: Length of the document a phrase appears in – in word tokens, word types and non-space characters. These three features encode the weight of the containing document.
-
• Mean length of constituent words: Average length of constituent words in non-space characters.
-
• First and last containing sentences: Index of the first and the last sentence a phrase appears in (for a particular document). These two features encode positional information of a phrase.
-
• Diameter: Difference between the indexes of the first and last containing sentences.
-
• Wikipedia keyphraseness: Ratio of the number of Wikipedia documents where a phrase appeared as a keyword, and the number of Wikipedia documents where the phrase appeared (Mihalcea and Csomai Reference Mihalcea and Csomai2007). This ratio, when computed for phrases with reasonable document counts, provides an estimate of their importance as well as cohesiveness.
-
• POS pattern probability: Probability of a part-of-speech pattern emerging as a candidate keyword from among all base noun phrase patterns. This feature is inspired by a similar feature used in Csomai and Mihalcea (Reference Csomai, Mihalcea, McKeown, Moore, Teufel, Allan and Furui2008). We included a second probability – probability of obtaining a candidate keyword pattern from among unique base noun phrase patterns. These two probabilities incorporate syntax information in our model.
-
• Is in subject?: Whether the phrase appears in the subject line of an email/thread. This is a binary feature.
-
• Overlap with subject: If the phrase appears in the subject line, then this feature is the length of the phrase in words, divided by the length of the subject line in words; otherwise, zero.
-
• Are all words capitalized?: This binary feature is a strong cue for detecting named entities.
-
• Mean degree, PageRank, coreness and neighborhood size: Mean degree, PageRank, coreness and neighborhood size (order one) of the constituent words of a phrase in the word co-occurrence network. Note that stopwords are not included in the word network. These four features indicate the importance of a phrase in terms of centrality. Higher values denote greater importance.
-
• Phrase degree, PageRank, coreness and neighborhood size: Degree, PageRank, coreness and neighborhood size (order one) of a phrase in the phrase co-occurrence network. Phrase co-occurrence networks are similar to word co-occurrence networks, except that nodes are candidate phrases instead of words, and edges are defined between candidate phrases that appear in the same sentence. Higher values indicate greater importance.
Note that among the above features, coreness and neighborhood size are novel features in our study, and to the best of our knowledge, they have never been used in keyword extraction. Further, their behavior is different from tfidf. We illustrate an example in Table 1 (ECS080; corporate single email), which shows that both the ranking as well as the value ranges are different for phrase tfidf, phrase mean coreness and phrase mean neighborhood size. For example, the word ‘afternoon’ has a mean neighborhood size of four (i.e., it is connected to four other phrases) and a mean coreness of six, but a low tfidf of 2.41 (‘afternoon’ appears in several of the emails). Yet another example is the word ‘chris.’ It has a low mean neighborhood size of one and low mean coreness of zero, but the tfidf is much higher (4.54), showing once again that these features are not redundant in their behavior.
Keyphrase ranking obtained with three features
5 Evaluation
5.1 Dataset
To our knowledge, there is no dataset available for keyword extraction from emails. To evaluate our methods, we compiled our own dataset consisting of 212 single emails and 107 email threads (of 4–8 emails each) drawn from the Enron collection (Klimt and Yang Reference Klimt and Yang2004).Footnote 9
First, each email and thread within this dataset was manually classified as either ‘private’ or ‘corporate’. The corporate emails discuss issues related to work and office, whereas the personal emails deal with issues related to home, family and friends. Examples of corporate and personal emails are shown in Table 2.
Example of a corporate email and a personal email, along with keyword annotations
Next, all the emails and threads in the dataset are annotated for keywords by four independent human judges. The annotators were asked to assign 5–20 keywords to each email/thread, ranked in their order of importance. We requested annotators to select keywords that are up to five words in length. While the definition of a ‘keyword’ can vary depending on the annotator, we provided some guidelines and recommendations for increased consistency, e.g., we recommended the selection of noun phrases, named entities or any other phrases that best capture the essence of a given email/thread.
Example keywords assigned by the annotators are shown in Table 2. Table 3 shows the keyword statistics of different categories of emails. Overall, threads have more keywords than single emails, and corporate emails have more keywords than personal emails.
Keyword annotation statistics
We compute inter-annotator agreement by considering one annotator as the ground truth, and the (set union of) remaining annotators as the ‘system’. Further, we consider three forms of agreement:
-
• Exact match : when two phrases match exactly (up to lowercasing and spaces).
-
• BOWmatch : when two phrases’ bags of words (BOW) match exactly after lowercasing (except stopwords).
-
• Relaxed match : when two phrases either match exactly up to lowercasing, or can be made identical by adding a single word to the beginning or end of the shorter phrase (Chuang et al. Reference Chuang, Manning and Heer2012).
Micro-averaged precision, recall, F-score, and Jaccard similarity under these three settings are shown in Table 4. Note that the best agreement under exact match is only 33.63% F-score, which is not very high, thus indicating the difficulty of the keyword extraction task (cf. Hasan and Ng (Reference Hasan and Ng2014)).Footnote 10 However, if we consider the BOW match, the best agreement is much higher (51.63% F-score). The same holds true for the relaxed match. This shows that annotators – although clearly divergent in their opinion, do in fact tend to select very similar words to construct their keyphrases. Results on pairwise agreement (Table 5) present the same evidence.
Inter-annotator agreement
Pairwise inter-annotator agreement
5.2 Evaluation settings and metrics
Our experimental results are primarily based on a combined gold standard, obtained from the set union of the keywords assigned by the four annotators, with an average of 19.35 keywords per email. Note that we also considered the alternative of creating a gold standard by using the set intersection of the four annotations. This results in zero keywords per email, reflecting the diversity of opinions on the annotations for this task. Instead, we adopt as our intersection gold standard the union of pairwise intersections between the annotations, yielding 5.70 keywords per email (on average). This gold standard results in an artificially small dataset that does not accurately reflect the performance of a keyword extraction system. Nonetheless, for the sake of completeness, we also report the results obtained on this intersection set (Section 6.3).
All the keyword extraction experiments are evaluated using micro-averaged precision, recall, F-score, and Jaccard similarity. We used F-score as our primary yardstick for comparing different systems. The evaluations are performed at phrase-level, where we count a candidate phrase appearing in the gold standard as an exact match (up to lowercasing and spaces).
6 Results and discussion
We perform two sets of experiments, one consisting of unsupervised methods that rely on the individual use of the features described in Section 4, and a second set consisting of a supervised framework that combines all the features using machine learning.
6.1 Unsupervised methods
For unsupervised keyword extraction, we first apply the preprocessing heuristic to select only nouns and adjectives, then rank candidate words according to different features (one feature at a time), followed by a selection of the top 50% of the words from the resulting ranked list, and finally use the postprocessing heuristic to collapse adjacent words into key phrases. For the binary features (such as Is in subject? and Is the word/Are the words capitalized?), we take all words/phrases with value 1 instead of top 50%.
Table 6 shows the performance values obtained for the word and phrase features, and Table 7 shows the values for binary features. Note that mean neighborhood size yields the best F-score, followed by phrase tfidf and phase tf. Among word features, word tfidf performs the best, followed by word PageRank. The superiority of tfidf in both cases is in line with the findings by Hasan and Ng (Reference Hasan and Ng2010). For binary features (Table 6), we see that one of them gives the highest precision among all systems (47.11%). However, their recall is very low (2–16%), thereby yielding a relatively low F-score (esp. for Is in subject?).
Performance of unsupervised keyword extraction. Best values in different columns are boldfaced
Performance of binary features in unsupervised keyword extraction. Best values in different columns are boldfaced
6.2 Supervised methods
For supervised keyword extraction, we apply the same steps as in the unsupervised methods, but perform the ranking of the candidates using a machine learning algorithm applied in leave-one-out cross-validation fashion using all the phrase features. The supervised system includes a few features that cannot be used for keyphrase ranking, but could be potentially useful for the selection of keywords (e.g., document-specific features such as document length).
The supervised framework is formulated as a binary classification task, where each (document, candidate keyword) pair is classified as relevant or not. Using a small development dataset of 30 emails, we tried nine different classification algorithms, including KNN, Naive Bayes, SVM SMO, J48 decision tree, PART rule learner, OneR, Logistic Regression, AdaBoost and LogicBoost. We found that Naive Bayes and KNN performed best, and therefore used these classifiers in our experiments on the entire evaluation dataset. For all the classification experiments, we use Weka (Hall et al. Reference Hall, Frank, Holmes, Pfahringer, Reutemann and Witten2009). The performance values are micro-averaged.
The results of the leave-one-out cross-validation on the entire dataset of 319 emails are shown in Table 8. Interestingly, the results are comparable to the inter-annotator agreement rates reported in Tables 4 and 5, which is an indication of how accurate our best systems are as compared to human performance.
Performance of supervised keyword extraction. Best values in different columns are boldfaced. Performance values are micro-averaged in leave-one-out cross-validation
For an additional analysis, we also determine and report the most discriminative features (by Information Gain), as shown in Table 9. Note that Phrase Tf.idf and Mean neighborhood size appear among the most discriminative features, which is not surprising since these two features are also among the best in the unsupervised approach (Table 6). Note further that Phrase Tf appears to be more discriminative than Phrase Tf.idf, and that the index of the first containing sentence and length of the containing document are also among most discriminative features.
Most discriminative keyword extraction features by Information Gain on the email dataset
6.3 Additional evaluations
To further analyze the results of our supervised methods, we perform three additional evaluations.
First, we evaluate the effect of in-domain training, where for each of the four categories of emails in our dataset – personal single, personal thread, corporate single, and corporate thread – we restrict the training set to other documents in the same category. Table 10 shows the overall results obtained in this evaluation. Although the in-domain constraint results in a net decrease of the training set size, performance values improved because emails are more similar within a category than across categories. The F-score improvement with respect to the open-domain results from Table 8 are relatively small: 0.67 percentage point for KNN and 1.37 percentage point for Naive Bayes. Acknowledging that the size of the data used to train these in-domain systems is smaller than that used to train the open-domain data, the lesson learned from this experiment is that if domain-specific data is available, the same performance can be obtained with a fraction of the data.
Results of in-domain training. Best values in different columns are boldfaced. Performance values are micro-averaged in leave-one-out cross-validation
Second, we evaluate our supervised methods against a gold standard dataset formed by using the intersection of the pairwise annotations produced by the human judges. As noted in Section 5, taking the intersection results in a very small dataset, which is not ideal for measuring the performance of an automatic system. We nonetheless report these results in Table 11, to show the ability of our system to identify these keywords that were agreed upon by both annotators.
Performance of supervised keyword extraction under intersection gold standard. Best values in different columns are boldfaced. Performance values are micro-averaged in leave-one-out cross-validation
Finally, to understand the performance of our keyword extraction methods on different types of emails (e.g., single emails versus threads; personal emails versus corporate emails), we perform separate evaluations of our supervised methods on each of the four different subsets of our dataset. Table 12 shows these comparative results. As seen in the table, personal emails are significantly more difficult to process than corporate emails. The highest F-scores are obtained with the KNN classifier on single emails, which may be due to the fact that there is less variance in the topics covered by the emails in this data (as opposed to threads, where there may be topic shifts).
Performance of supervised keyword extraction on subsets of our dataset: single emails; threads; personal emails; corporate emails
6.4 Comparison with existing systems
To place our results in perspective, using our email dataset we evaluate five previously introduced systems for keyword extraction. We chose two state-of-the-art unsupervised keyword extraction systems – SingleRank and ExpandRank (Wan and Xiao Reference Wan and Xiao2008; Hasan and Ng Reference Hasan and Ng2010), two top-performing systems in SemEval 2010 keyphrase extraction task (Kim et al. Reference Kim, Medelyan, Kan and Baldwin2010) – KX_FBK (Pianta and Tonelli Reference Pianta and Tonelli2010) and SZTERGAK (Berend and Farkas Reference Berend and Farkas2010; Berend Reference Berend2011) and KEA (Witten et al. Reference Witten, Paynter, Frank, Gutwin and Nevill-Manning1999) – a well-known supervised keyword extractor.Footnote 11 Table 13 shows the results obtained by these five systems, in comparison with our two best unsupervised methods, and our two supervised settings. Our Naive Bayes system gives the best precision, which is very encouraging in a subjective task like keyword extraction. Overall, our systems are found to be better than the state-of-the-art, with our KNN system leading to the best F-score (38.99%), which is 12.76% better than the best state-of-the-art system (SZTERGAK) on this dataset. This improvement is significant (p < 0.00001) using a two-sample test for equality of proportions with continuity correction. Also, our unsupervised systems performed better than state-of-the-art systems, with best F-score of 30.82%.
Comparison with existing systems. Best values in different columns are boldfaced. Performance values are micro-averaged. Systems marked with O are ours, U are unsupervised, and S are supervised. KX_FBK and SZTERGAK are two of the top performers in SemEval 2010 keyphrase extraction task
6.5 Post-hoc evaluation of keyphrases
As a final evaluation, we set up two experiments that allow us to measure the quality of the keywords extracted by our system in an extrinsic way.
First, we perform a post-hoc evaluation, where the keywords produced by our system are manually annotated by a human judge for appropriateness. We set this evaluation as follows: For a given email (single or thread), first the human judge carefully reads the email text to make sure she is familiar with its content; next, the judge is presented with a set of keywords, and her task is to determine which of the keywords reflect important content of the email text.
We take a random sample of 40 single emails (20 personal, 20 corporate), and 20 thread emails (10 personal, 10 corporate), and generate keyphrases using our best system (KNN). The human judge then classifies these keyphrases as appropriate or not, as described above. Table 14 shows the fraction of keywords found to be correct for each email type. The results suggest that in such a post-hoc evaluation, a significantly larger fraction (78–86%) of the keywords produced by our system are found to be acceptable by a human judge. This is in line with previous work on keyword extraction (Csomai and Mihalcea Reference Csomai, Mihalcea, McKeown, Moore, Teufel, Allan and Furui2008), which showed that there can be large gaps between the ad-hoc and post-hoc evaluations of keywords, as humans often have a difficult time generating a comprehensive list of keywords for a given text, yet they do agree with the appropriateness of a larger set of keywords when presented to them.
Keyphrase appropriateness in a post-hoc evaluation
The second experiment consists of an application-based evaluation, where we simulate a potential classification task that a user has to accomplish when presented with a set of emails (e.g., the daily incoming email). Specifically, a human judge is given the task to classify each email in a set as being either ‘personal’ or ‘corporate.’ We compare the scenario where the classification is performed by only reading the extracted keywords, versus reading the entire text and measure both the correctness of the classification (against our own existing gold standard annotations) as well as the time it takes to perform the task in each scenario.Footnote 12
We perform ten rounds of simulation, where in each round we select ten random emails and their corresponding keyphrases. The presentation order of the email texts or email keyphrases is randomized to remove any sequence effect. The classification accuracy of this simulation process – averaged over the ten rounds – is shown in Table 15 (standard deviations in parentheses). Note that just by reading the keyphrases, the human judge was able to correctly classify the emails 85% of the time, whereas reading the full text leads to 90% – which is only 5% improvement. Note further that the time taken to classify the emails just by reading the keyphrases is 6.53 seconds on average, whereas reading the full text takes at least ten seconds. This shows that keyword extraction can be very helpful in real life by substantially reducing the time taken to triage emails, at comparable accuracy levels.
Email classification results. Standard deviations in parentheses
7 Conclusion
Keyword extraction from emails is largely an open problem, with potentially important benefits given the growing number of emails that we have to handle in our daily communication. In this paper, we described and evaluated methods for unsupervised and supervised keyword extraction from emails. We defined two types of features – word features and phrase features – which we then evaluated on a novel dataset consisting of emails manually annotated with keywords. To the best of our knowledge, our work is the first attempt to extract keywords from emails after the seminal study by Turney (Reference Turney2000). Our unsupervised experiments highlighted the role played by the different features for keyword extraction from emails. We also combined all the features using a supervised framework, and obtained results that improved significantly over the use of individual features. The results obtained with our best system represent a significant improvement over state-of-the-art in general-purpose keyword extraction, which is an encouraging result given the informal nature of emails and their difference from academic abstracts. Moreover, two extrinsic evaluations have further demonstrated the quality of the keywords extracted with our system.
The manually annotated email dataset introduced in this paper is publicly available from http://lit.eecs.umich.edu.
