A Game Theory Approach to Feature Selection for Text Classi cation

Abstract

This paper presents an initial study on how game theory can be applied to select positive and negative features for a text classi cation task. The proposed approach builds upon previous work where the players are the positive and negative categories, while the strategies are the choices of selecting a given feature as positive or negative. We explore how the payo matrix can be described in a more general way and analyze how the choice of a given payo matrix in uences the e ectiveness of a text classi cation engine.

Introduction

The automatic classi cation of textual documents [ 4 ] is a process that requires the choice of a set of representative features in order to tell whether a document belong to a particular topic or not. For text classi cation, a straightforward and easy solution is to use the entire set of words present in all the documents of the dataset. However, there are situations where the choice of a subset of words, rather than the entire vocabulary, leads to signi cant performance improvement [ 2, 3 ]. This choice is based on the output of functions usually called feature selection metrics; these functions can can be roughly divided in two sets: one-sided and two-sided metrics. One-sided metrics select the features most indicative of membership for one class only (positive features), while two-sided metrics consider the features most indicative of either membership or non-membership (positive or negative features) for a class. `Positive' and `negative' have two meanings in the context of text classi cation: i) a feature can be positive or negative depending on whether it is indicative or not for a class; ii) a class can be positive or negative. The second meaning is usually related to a binary classi cation problem where, given a set of classes, the positive class is the one we are interested in and the negative class is the union of all the remaining classes. Positive features are intuitively the rst choice to describe the documents of a class, but also negative features are important to improve the quality of classi cation [ 2 ]. In fact, \a judicious combination [of positive and negative features] shows great potential and practical merits" for (probabilistic) text classi ers [ 6 ].

Following this idea, Azam and Yao [ 1 ] propose a game theory framework for selecting features that are representative for both positive and negative classes. According to their approach, the choice of including or discarding a positive/negative feature can be modeled as a two-player game. Players are the positive and negative categories, which indipendently choose whether to keep or discard a given feature. As in any game, the payo of each player depends on the combined choices of the two categories, which thus try to maximize their payo for each feature eventually reaching the Nash equilibrium. In this paper, we discuss a generalization of the game theory framework proposed by [ 1 ] and show an interpretation, inspired by language models, that has an additional parameter that can be optimized to achieve a better classi cation performance. 2

Mathematical Background

In this section, we present the mathematical notation and the basic de nition of game theory to describe the problem of feature selection. Given a set of classes C = fc1; : : : ; ci; : : : ; cng and a set of documents D = fd1; : : : ; dj ; : : : ; dmg, we indicate the positive class i with c+ = ci and the corresponding negative class with c = C n ci. If documents are described by a vocabulary of words V = fw1; : : : ; wk; : : : ; wvg, then the probability of word wk given the positive (or negative) category is P (wkjc+) (or P (wkjc )).

In game theory, a game G is a triple G = fP; S; F g, where P is the set of players, S a set of strategies, and F a set of payo functions. In the context of feature selection, we have two `players' P = fc+; c g, two 'strategies' S = fs1 : keep; s2 : discardg, where s1 means the choice of keeping the feature and s2 to discard it, and two sets of payo functions F = fuc+ ; uc g one for each player. The payo set for the two players can be de ned as: uc+ = uc = u(s1+; s1 ); u(s1+; s2 ); u(s2+; s1 ); u(s2+; s2 ) u(s1 ; s1+); u(s1 ; s2+); u(s2 ; s1+); u(s2 ; s2+) where, for example, u(s1 ; s2+) is the payo of the `negative' player that plays the action `keep the feature' while the `positive' player played the action `discard the feature'. The payo table used to play the game is shown in Table 1.

The typical approach in non-cooperative game theory is to analyze the payo function in order to nd strategies that form a Nash equlibrium, that is a combination of choices where no player can improve its payo by changing its strategy unilaterally. For instance, given Table 1, the combined strategy (s1+; s1 ) (both players keeping the feature) is a Nash equilibrium only if player c+ will have a smaller payo with the combined strategy (s2; s1) and player c will have a smaller payo with the combined strategy (s1; s2). Even if it is not guaranteed that each payo matrix has a Nash equilibrium with only deterministic choices (called pure strategies), in this initial contribution we will not discuss the case of a Nash equilibrium with probabilistic choices (called mixed strategies).

In [ 1 ], the utility of players in the payo matrix is computed in two ways according to the particular situation: i) when the action is `keep the feature' + s1 2112 PP((wwjjjjcc+))s+1+PP((wwjjjjcc+)) , s2

P (wjjc+); P (wjjc )

s2

P (wjjc+); P (wjjc ) 12 P (wjjc+) + P (wjjc ) , 12 P (wjjc ) + P (wjjc+) or `discard the feature' for both players, the utility is the average between the probability of nding (or not nding) the word wj in the positive and negative class and it is equal for both players; ii) when only one player decides to `keep the feature' (or `discard the feature') the utility for that player is just the probability of the word given the class. In Table 2, we show the utilities for each pair of strategies in for the game of feature selection. 3

Our proposal

Starting from the utilities de ned in Table 2, we propose a more general interpretation for computing the payo matrix based on the idea of language models to interpolate the probability of the word in the class and in the collection with a parameter [ 5 ] that, in our case, can be optimized for each pair of actions of the two players.

For example, if we use to weight the action of one player and (1 ) the action of the other player we can de ne the utility of `keeping the feature' for the positive category and `discard the feature' for the negative category as: u(s1+; s2 ) = u(s2 ; s1+) = 1+2 P (wj jc+) + (1 2 1+ P (wj jc ) + (1 1+2 )P (wj jc ) 2 1+ )P (wj jc+) where 1+2 and 2 1+ are two di erent parameters for the two actions that, in [ 1 ], are equal to one 1+2 = 2 1+ = 1. Similarly, when the actions are concordant, for example both players keep the feature, we have: u(s1+; s1 ) = u(s1 ; s1+) = 1+1 P (wj jc+) + (1 1 1+ P (wj jc+) + (1 1+1 )P (wj jc ) 1 1+ )P (wj jc ) In order to reproduce the approach presented in [ 1 ], the parameters should be equal to 21 , 1+1 = 1 1+ = 12 . In Table 3, we show the payo matrix with the interpolated probabilities for all the possible actions. (1) (2) (3) (4) c

s1 + s1 1+1 P (wjjc+) + (1

1 1+ P (wjjc ) + (1 s2 2+1 P (wjjc+) + (1 1 2+ P (wjjc ) + (1

Preliminary Analysis and Future Work

In our initial analysis, we used the toy example shown in [ 1 ] to understand how di erent values of the parameters can shift the Nash equilibrium from one strategy to another. This can be easily demonstrated for some of the words in that experiment, but it is less clear whether this is possible in situations where the same feature has almost the same probability of appearing in both classes. However, the analysis of this simple example may lead to super cial conclusions since the numbers used in that experiment do not re ect values of the probabilities computed for a real text collections (where the magnitude of the values of probabilities is very rarely above 10 1). For this reason, our study will focus on the next steps: { use standard text collections (i.e. Reuters 21578, 20 Newsgroups, Reuters RCV1) to study whether it is possible to shift Nash equilibrium by changing the values of the paramters lambda; { nd optimal lambdas by means of k-fold cross-validation approaches and test whether this values of the parameters can improve text classi cation performances signi cantly; { study whether a Nash equilibrium with mixed strategies is possible (and e ective in terms of classi cation performance) on real datasets.

References

1. Nouman Azam and JingTao Yao . Proc. of Rough Sets, Fuzzy Sets, Data Mining and Granular Computing: RSFDGrC 2011 , chapter Incorporating Game Theory in Feature Selection for Text Categorization , pages 215 { 222 . Springer, 2011 .

2. George Forman . An extensive empirical study of feature selection metrics for text classi cation . J. of Mach. Learn. Res. , 3 : 1289 { 1305 , 2003 .

3. Vipin Kumar and Sonajharia Minz . Feature Selection: A Literature Review . Smart CR , 4 ( 3 ): 211 { 229 , 2014 .

4. Fabrizio Sebastiani . Machine Learning in Automated Text Categorization. ACM Comput. Surv. , 34 ( 1 ):1{ 47 , March 2002 .

5. ChengXiang Zhai . Statistical Language Models for Information Retrieval A Critical Review . Found. Trends Inf. Retr. , 2 ( 3 ): 137 { 213 , March 2008 .

6. Zhaohui Zheng , Xiaoyun Wu , and Rohini Srihari . Feature Selection for Text Categorization on Imbalanced Data . SIGKDD Explor . Newsl., 6 ( 1 ): 80 { 89 , June 2004 .