K ey G ames: A Game Theoretic Approach to Automatic Keyphrase Extraction (2020)

Abstract: In this paper, we introduce two advancements in the automatic keyphrase extraction (AKE) space - KeyGames and pke+. KeyGames is an unsupervised AKE framework that employs the concept of evolutionary game theory and consistent labelling problem to ensure consistent classification of candidates into keyphrase and non-keyphrase. Pke+ is a python based pipeline built on top of the existing pke library to standardize various AKE steps, namely candidate extraction and evaluation, to ensure truly systematic and comparable performance analysis of AKE models. In the experiments section, we compare the performance of KeyGames across three publicly available datasets (Inspec 2001, SemEval 2010, DUC 2001) against the results quoted by the existing state-of-the-art models as well as their performance when reproduced using pke+. The results show that KeyGames outperforms most of the state-of-the-art systems while generalizing better on input documents with different domains and length. Further, pke+’s pre-processing brings out improvement in several other system’s quoted performance as well.

## introduction automatic keyphrase extraction (ake) is a task of identifying important words and phrases that best describe a given text document. ake makes searching and indexing large digital collections of text feasible and finds use in a variety of natural language processing (nlp) and information retrieval (ir) tasks ( @xcite , @xcite , @xcite ). owing to its widespread use, keyphrase extraction has emerged as a fundamental nlp task, improvements in which could lead to improvements in higher-level applications that build upon it @xcite . due to this importance, many approaches to keyphrase extraction have been proposed in the literature, majorly along two research lines: supervised and unsupervised @xcite . however, the field faces two specific problems. firstly, with state-of-the-art performance on keyphrase extraction being much lower than on the many core nlp tasks, there is still a fair amount of improvement possible in this space @xcite . secondly, there is no effective way to compare and analyze various past ake systems since most of them use different experimental setups. different works have used different pre-processing and evaluation to demonstrate their performance. these discrepancies in the past studies make assessing the progress of the ake space very challenging. to deal with the first issue, we recognised the need to approach this challenging problem from a fresh perspective. we thus propose a game-theoretic framework for ake -keygames. players, strategies, and payoffs form an integral part of any game. in keygames, the candidate keyphrases act as players having two strategies each: being a keyphrase and being a non-keyphrase. each phrase plays a game with all the other phrases before deciding upon its strategy. next, the definition of keyphrases is paraphrased, such that it paves the way for us to develop heuristics which are then formulated into mathematical payoffs. as per our definition, a candidate keyphrase becomes a keyphrase if it satisfies the following two conditions: (a) it should be related to the main themes of the document (b) it should be related to other important phrases in the document. to capture (a) in our payoffs, we use semantic relatedness between the phrases and the theme of the document (we call this confidence -higher this metric, more confident the candidate is of becoming a keyphrase). later, we also bias a candidate's confidence based on its positional information and frequency of occurrence. to capture (b), we use semantic relatedness between the different phrases. the construction of these payoffs is discussed in detail in section 5.4. once we have the payoffs in place, we apply evolutionary game algorithm to score and rank keyphrases. inspired by @xcite , our reasons for exploring game theory were two fold; firstly, game theory and nlp have a intuitionistic parallel wherein both have entities interacting with each other thereby influencing each other's behaviour. second and more important was the ability of game-theoretic frameworks to perform consistent labelling of entities under contextual constraints. we discuss this property in detail in section 3 and further demonstrate consistent labelling in action when we incorporate a preliminary constraint in keygames's payoffs to tackle overgeneration foot_0 in extracted keyphrases (keygames+, section 5.4). through this effort, we reduce the overgeneration error by ˜10% points across datasets. to deal with the second issue, we built pke+ foot_1 as an extension to pke library foot_2 @xcite , pke is a python based tool kit containing implementation of various existing state-of-the-art ake systems. under pke+, we have provided a pipeline with standardized modules for candidate extraction and evaluation. all of pke's implemented systems can be plugged-in to this pipeline to extract keyphrases under similar experimental setup, allowing for a fair comparision (we have implemented keygames simply as another system under pke's setting). to the best of our knowledge, using a game-theoretic approach for ake has not been proposed before and our work is first such attempt. in fact, the application of game theory to nlp is still in its infancy. we believe that our work would spur additional research in this regard. ## game theory game theory is a branch of applied mathematics that provides predictive power in interactive decisionmaking situations @xcite . a typical game consists of a finite set of players, @xmath0, p 2 , .., p n ), a set of pure strategies for each player i, @xmath1, ..., n ) and a utility or payoff function u i : 1 ⇥ .. n ! r which associates a combination of strategies played by various players to the payoffs they receive. each player aims to settle on a strategy which maximizes its payoff. the concept of payoff, in general, refers to the satisfaction that a player derives from the outcome of a game while interacting with other players. furthermore, in a two player game, payoffs of a player i when it plays the game with player j can be represented in the payoff matrix a ij , wherein values in each cell of the matrix indicates the payoff player i gets when opting the strategy corresponding to the row represented by that cell, in the event when the j th player chooses the strategy corresponding to the column represented by that cell. nash equilibria are those strategy profiles which are best response to the strategy of the co-player and no player has the incentive to unilaterally deviate from his strategy, because there is no way to do better. in evolutionary game theory (egt), instead of choosing a strategy with certainty as in classical game theory, players choose strategies with certain probability. we thus use the concept of mixed strategy space for each player in egt. mixed strategy space is defined as a probability distribution over the pure strategies a player is allowed to play. it is represented as a vector x @xmath2, ..., x m i ) where m is the number of pure strategies and each component x h i denotes the probability that player i chooses its h th pure strategy. note that: an important aspect we observe within the framework of egt is the inductive learning process wherein the players play the game repeatedly till equilibrium is achieved and keep on updating their beliefs on the state of the game and choose their strategy accordingly @xcite . the steps below are followed to model this learning process: step 1: the expected payoff of every pure strategy each player i can obtain (u 1 i ) in a single two player game is obtained using the equation: step 2: the expected payoff obtained by each player i in a single game (u 2 i ) is calculated using: step 3: discrete time version of the replicator dynamic equation @xcite is used to update the mixed strategy space of a player i after the end of each iteration as follows: ## motivation an important factor that motivated us to pursue game theoretic models was their ability to solve consistent labelling problem wherein labelling of objects is done while satisfying certain constraints as per the context of the problem @xcite . we observed that ake can be modeled as a consistent labelling problem as well wherein a candidate keyphrase is to be labelled either a keyphrase or a non-keyphrase abiding to certain constraints majorly based on the definition of a keyphrase. this distinguishes our approach from the existing ake algorithms. a game-theoretic algorithm allows us not only to exploit the contextual information from an input document like various previous works do but also lets us design constraints and heuristics and ensures that classification of candidates into keys and non-keys remains consistent with these heuristics. in fact, it has been shown that, in some cases, using only contextual information without the imposition of constraints can lead to inconsistencies in the assignment of labels to related linguistic entities @xcite . a clear example of such a case is seen while extracting keyphrases from short texts where we have fewer candidates than the number of keyphrases to be extracted. any other scoring algorithm would classify all the candidates as keys. keygames, however, will classify only those candidates into keys that remain consistent with the definition of a keyphrase and will classify the rest as non-keys. a consistent labelling problem can be defined as tuple hx, l, ci where @xmath3, x 2 ...x n } is a set of n objects, @xmath4, l 2 . . . l m } is a set of m labels and c is a real-valued, n 2 ⇤ m 2 matrix of compatibility coefficients also called compatibility model, @xmath5, µ) | , µ 2 l}. c ij ( , µ) is the measure of strength of compatibility of two hypothesis "x i is labeled " and "x j is labeled µ". c is used to impose constraints on labelling so that each label assignment is consistent. the problem is to find a label for each object such that the resulting set of object-label pairs is consistent with the constraints of the compatibility model @xcite @xcite observed that a consistent labelling problem is equivalent to a polymatrix game. they demonstrated that the objects are equivalent to players in game theory, the labels are strategies each player can opt for, the compatibility model is the payoff matrix designed for the game and a consistent labelling solution is the nash equilibrium. in our model, the candidate keyphrases serve as the objects (players), "keyphrase" and "non-keyphrase" serve as the only two labels (strategies) and finally, the mathematical signals formulated using definition of keyphrases serve as the compatibility model (payoff matrix). these signals simply imply that two candidates, one of which adheres to the definition of a keyphrase and another one which doesn't, cannot be assigned the same labels. clearly, the first one is to be labelled a keyphrase while the second one is to be labelled a non-keyphrase. ## related work existing studies present keyphrase extraction in two steps. firstly, a list of candidate keyphrases is generated using heuristic rules such as extracting important noun phrases or extracting phrases that match specific pos (part-of-speech) tags @xcite . in the next step, ranking mechanisms are often used to select the keyphrases from among the candidates. both supervised and unsupervised methods are used here. detailed surveys on these are available @xcite . here, we focus on unsupervised approaches due to their many benefits (no training data, domain independence). in unsupervised approaches, many techniques have been explored including, graph-based ranking, clustering and statistical methods. many statistical based approaches like tfidf, kpminer(el-beltagy and rafea, 2009) have been proposed. yake @xcite recently used a combination of statistical metrics to capture context information and the spread of the terms in the document. in graph-based approaches, a document is represented as a graph and word-word interactions are scored using graph centrality measures such as pagerank @xcite and its variants. first introduced as textrank @xcite , words are here represented by nodes and two words are connected by an edge if they co-occur in given window size. nodes are then ranked using pagerank. @xcite extended textrank to singlerank by incorporating weights to edges, using number of co-occurences between words as weights. another graph based model, positionrank @xcite demonstrated the importance of capturing the positions and frequency of a word in a biased pagerank algorithm, preferring words that appeared earlier and more frequently in the text. there have also been attempts at extracting keyphrases that cover all the main topics of the document. this has been done either by using a clustering based approach @xcite to cluster words into specific topics or by using latent dirichlet allocation(lda) model @xcite to obtain the topic distribution @xcite . the lda based methods require training data, making the systems corpus dependent. clustering based approaches were first used in a graph by @xcite . in their proposed system, topicrank, candidates are clustered depending on the percentage of shared words using hierarchical clustering. a graph is constructed where each node represents a cluster and edges are weighted based on the phrases' offset position in the text. this work was extended to multipartiterank @xcite by encoding topical and positional information within a multipartite graph structure. with recent advances in deep learning, word embeddings are increasingly being used to study word associations in nlp. @xcite first proposed usage of word embedding vectors for keyphrase extraction when they used the semantic information supplied by pretrained word embeddings to formulate a weighted scheme which is then used on a weighted page rank algorithm. later using a similar approach, @xcite proposed a corpus dependent method making use of their domain specific trained fasttext embeddings @xcite for extracting keyphrases from scientific articles. recently in a departure from graph-based approaches, @xcite proposed embedrank where they use sentence embeddings (sent2vec) to represent both the candidate phrases and the document in the same high-dimensional vector space. their system then ranks the candidate phrases using cosine similarity (semantic relatedness) between the embedding of the candidate phrase and the document embedding. keygames combines many of the approaches discussed above. here we develop payoffs by capturing word-word and topic-word interactions using fasttext embeddings and later bias these interactions using frequency and positional information of a candidate. ## conclusion and future work in this paper, we discussed our work on a novel, unsupervised game-theoretic approach to automatic keyphrase extraction after modeling the task as a consistent labelling problem. we paraphrased the definition of a keyphrase, conceptualized logics to model the same, and ultimately designed keyphrase games by quantifying these logics into mathematical payoffs. for carrying out experiments, we used pke to construct a new pipeline pke+, standardizing candidate extraction, and evaluation steps across different systems. our proposed method consistently outperforms most of the existing systems on three datasets with different domains and lengths, indicating the potential of game theory as an alternative. in the future, we plan on working with infection and immunization dynamics (inimdyn) @xcite , which approximately simulates replicator dynamics in linear time, thereby reducing time-complexity of keygames. we plan to experiment with different heuristics in our payoffs as well. we would also like to explore other methods like document embedding to extract the theme of the document.