Density estimation using game theory

Density estimation using game theory1 Ignacio Garc´ıa-Jurado Department of Statistics and OR, Faculty of Mathematics, Universidad de Santiago de Compostela, 15782 Santiago de Compostela, Spain. Luciano M´endez-Naya Department of Econometrics, Faculty of Economics, Universidad de Santiago de Compostela, 15782 Santiago de Compostela, Spain. C´esar S´anchez-Sellero Department of Statistics and OR, Faculty of Mathematics, Universidad de Santiago de Compostela, 15782 Santiago de Compostela, Spain. Abstract: In this note we show that the mathematical tools of cooperative game theory allow a successful approach to the statistical problem of estimating a density function. Specifically, any random sample of an absolutely continuous random variable determines a transferable utility game, the Shapley value of which proves to be an estimator of the density function of binned kernel and WARPing types, with good computational and statistical properties. Key Words: Cooperative Games, Density Estimation, Shapley Value. Mailing Author: Ignacio Garc´ıa-Jurado (ig[email protected]). Running Title: Density Estimation. 1Authors acknowledge the financial support of Spanish Ministry for Science and Technology and FEDER through projects BFM2002-03213 and BEC2002-04102-C02-02 and of Xunta de Galicia through projects PGIDT00PXI20104PR and PGIDT03PXIC20701PN. They also thank the comments of two anonymous referees. 1 1 Introduction The relationship between game theory and statistics is generally seen as very one-sided: whereas the influence of probability theory and bayesian statistics on game theory is evident, the only well-known contribution of game theory to statistical thought is the minimax principle. Noncooperative games had a certain influence on statistical theory (Blackwell and Girshick (1953); Schwarz (1994)), but cooperative game theory has been applied to statistics very rarely (Land and Gefeller’s (1997) and (2000) treatment of an epidemiological problem as a cost allocation game is one of those applications). This is to some extent surprising if one bears in mind that fairness, one of the central themes of cooperative game theory, is clearly desirable in statistics in the sense that a good statistical estimator should in some sense provide an estimate that is fair, given the available data. The aim of this note is to provide a new illustration of the connection between cooperative game theory and statistics. We show that the mathematical tools of cooperative game theory allow a successful approach to the statistical problem of estimating a density function. Specifically, we show that any random sample of an absolutely continuous random variable can be used to construct a TU (transferable utility) game, the Shapley value of which (Shapley (1953)) is an estimator of the density function of binned kernel type (Hall and Wand (1996)) and WARPing type (H¨ardle (1991)). Density estimation is an important problem in statistics that has generated a large literature in the last decades. Its purpose is to provide an accurate estimation of the density function of a random variable on the basis of a random sample. Nowadays, density estimation is a basic tool for exploratory data analysis and for other important fields within statistics. For a complete introduction to density estimation, Silverman (1986) can be consulted. In section 2 below we describe the density estimation problem, model it as a cooperative game whose Shapley value is the required density estimator, and obtain a more convenient expression for this estimator. In section 3 we provide an axiomatic characterization of the Shapley density estimator. Finally, in section 4 we make some comments on the statistical and computational properties of the Shapley density estimator. 2 2 Density estimation as a game-theoretical problem In a density estimation problem we have a random sample X1, ..., Xmof m independent and identically distributed observations of an absolutely continuous random variable with density function f.fis unknown and the problem is to estimate fusing the random sample. A variety of nonparametric density estimators have been proposed and studied since the publication of the pioneer works by Parzen (1962) and Rosenblatt (1956) on the so-called kernel methods. For a survey on density estimation see Silverman (1986). A kernel estimator is any real function ˆ fof the form ˆ f(x) = 1 mh m X j=1 Kx−Xj h where Kis a density function symmetric around zero and his the so-called bandwidth or smoothing parameter. Note that, defined in this way, ˆ fis a density function (a non-negative real function which integrates to one). The necessity of the smoothing parameter comes from the fact that every observation Xiin the sample not only shows that there is a positive density on the real number Xibut also that there is a positive density on a neighborhood of the real number Xi(note that the original variable is continuous and we have a finite sample to estimate its density). The selection of his an important, though difficult, issue. There is a large number of papers on the selection of the bandwidth parameter for given classes of estimators. For a survey on this topic see Cao et al (1994). Very often, the statistical literature has treated this problem as a different one. One issue is to identify families of density estimators with good statistical and computational properties. Another different issue, which is usually analyzed in a second stage, is to find a good selector of the smoothing parameter for a given family of density estimators. In this paper we focus on the first of these issues and obtain a density estimator based on the Shapley value. Our main target is to illustrate a connection between cooperative game theory and statistics by showing that this new estimator is a competitive one from a statistical point of view. Moreover, we provide an axiomatic characterization for it. Axiomatic characterizations might be useful for statisticians, who 3 have sometimes several procedures to solve a problem and no clear reasons to choose one among those procedures. To model the density estimation problem in game-theoretical terms, we proceed essentially as follows: we consider the real line Ras an infinite set of players of a cooperative game with characteristic function vsuch that for any coalition A(i.e. any subset Aof R), v(A) is determined by X1, .., Xmand A itself; we then define our estimator ˆ fof fas the payoff vector allocated by an appropriate game-theoretical solution concept. The precise nature of ˆ f evidently depends on both the solution concept used and the way in which v(A) is determined by X1, .., Xmand A. In this paper we adopt a simple approach to the latter question, taking v(A) proportional to the cardinality of {X1, .., Xm}∩A0, where A0is a set containing A. To avoid game-theoretical complications, and in the interests of computational efficiency (see section 4), we actually group the points of Rin a countable number of “indivisible coalitions“ Jithat act as the effective players. As noted above, we start by dividing Rin intervals of the same length δ, i.e. R=∪i∈Z[δi, δ(i+ 1)). We denote [δi, δ(i+ 1)) by Ji(for all i∈Z). Now, for every S⊂Z, define ¯v(S) = 1 mδ m X j=1 I∪i∈S¯ Ji(Xj) where, for all i∈Z,¯ Jiis the set ∪{Jr| |r−i| ≤ k},kbeing a non-negative integer, and IAdenotes the indicator function of A, for any set A⊂R (IA(x) = 1 if x∈A,IA(x) = 0 if x∈R\A). About ¯vnote that: 1. ¯v(Z) = 1 δ. In fact, we want to allocate 1 δto the intervals of {Ji|i∈Z} because in this way we can define ˆ f(x) as the share of 1 δthat Jiobtains (x∈Ji) and, then, R+∞ −∞ ˆ f(x)dx = 1. 2. For every S⊂Z, ¯v(S) is 1 mδ times the number of observations belonging to an interval k-close to an interval in {Ji|i∈S}. This can be interpreted as the maximum density that can be allocated to S. Observe that kplays here the role of the smoothing parameter. Now we can make a TU-game (N, v) out of the density estimation problem characterized by the sample X1, ..., Xm: 4 •N={i∈Z|¯v(i)>0}(note that N, which is a finite set, can also be written as N={i∈Z|¯v(S∪ {i})−¯v(S)>0 for some S⊂Z}). •vis the restriction of ¯vto {S|S⊂N}. About this game we can make the following comments: 1. If k= 0 the game is additive. If k≥1 the game is subadditive and, moreover, v(N)<Pi∈Nv(i). As kincreases, the Jiintervals share their observations with more neighboring intervals, producing a smoothing effect in the game. 2. It is easy to see that vis a concave game. 3. vcan be seen as a cost game. Since v(S) can be interpreted as the maximum density that should be allocated to S, a fair allocation x must belong to the core of v, i.e. X i∈S xi≤v(S) for all S⊂N. Since vis a concave game, its Shapley value φ(v) lies in its core (see Shapley (1971)). Thus, a promising estimator of the density function is that based on φ(v). Formally, the Shapley estimator we propose is given by: ˆ fS(x) = φi(v) if x∈Ji,i∈N 0 if x∈Ji,i6∈ N. Since the number of players in the game may be large, calculation of ˆ f directly from its definition and that of the Shapley value can be very onerous. The following theorem provides a more convenient expression. Theorem 1 Let (N, v)be the TU-game associated with the density estimation problem characterized by the sample X1, ..., Xm. Then, for any i∈N, φi(v) = 1 mδ X r∈Nk(i) n(r) 2k+ 1 where n(r)denotes the number of observations belonging to the interval Jr and Nk(i)is the set {r∈N| |r−i| ≤ k}. 5 Proof. From the definition of the Shapley value, φi(v) = 1 n!X π∈Π(N) 1 mδ X r∈Pk(i,π) n(r) where Π(N) is the set of permutations of N,nis the cardinality of the set Nand Pk(i, π) = {r∈Nk(i)|π(i)≤π(s) for all s∈Nk(r)}. Now, taking into account that, for each r∈Nk(i), the cardinality of the set {π∈Π(N)|π(i)≤π(s) for all s∈Nk(r)} is n!/(2k+ 1), then X π∈Π(N)X r∈Pk(i,π) n(r) = X r∈Nk(i) n! 2k+ 1n(r) and the theorem follows.2 3 An axiomatic characterization of the Shapley estimator Taking into account the properties of the Shapley value, it is possible to provide axiomatic characterizations of the Shapley estimator. We present one in this section which follows the ideas in Myerson (1977). Assume that δ > 0 is fixed. A δ-estimator is a map which assigns to every random sample X=X1, . . . , Xma density function2ˆ fXwhich satisfies ˆ fX(x) = ˆ fX(y) for all x, y ∈Jiand all i∈Z. For simplicity, we denote by ˆ fX(i) the evaluation of ˆ fXin any x∈Ji. Observe that, since ˆ fXis a density function, it holds that ˆ fX(x)≥0 for all x∈Rand that Pi∈Zˆ fX(i) = 1/δ. Note also that the Shapley estimator is, in fact, a family of δ-estimators (one for each k∈N; remember that kdenotes the smoothing parameter). 2For notational convenience, in this section we denote by ˆ fXthe density estimation for a given sample X. 6 Let us see some interesting properties for the δ-estimators. Let X= X1, . . . , Xmbe a random sample and suppose that the smoothing parameter k is fixed. We say that i, j ∈Zare directly connected if there exists an element of the sample Xlsuch that Xl∈¯ Ji∩¯ Jj. We say that C⊂Zis a connected set if, for every i, j ∈Cthere exists a finite sequence {i1, . . . , ir} ⊂ Csuch that i1=i,ir=jand is, is+1 are directly connected for every s∈ {1, . . . , r −1}. We say that Cis a connected component of Zif Cis a maximal connected subset of Z. The first property that we consider is component efficiency, which states that the density that the δ-estimator assigns to the intervals in a connected component is the one corresponding to the observations belonging to those intervals. CE (Component Efficiency). A δ-estimator is said to satisfy component efficiency for kif, for every random sample Xand every connected component C, X i∈C ˆ fX(i) = mC m 1 δ where mCis the number of observations lying in ∪i∈CJi. Note that if a δ-estimator satisfies CE for k, then it allocates density equal to zero to the intervals in whose neighborhoods there are no observations of the sample, more precisely to those Jisuch that Pr∈Nk(i)n(r) = 0. The second property that we introduce is the fairness property. Informally, this property states that, when estimating a density function, the increment of the density due to a particular observation is the same for all intervals in the neighborhood of this observation. F (Fairness). A δ-estimator is said to satisfy fairness for kif, for every random sample X, every i, j ∈Zdirectly connected and every Xl∈¯ Ji∩¯ Jj, it holds that ˆ fX(i)−ˆ fX\Xl(i) = ˆ fX(j)−ˆ fX\Xl(j), where X\Xlis the sample identical to Xexcept for the fact that Xlhas been shifted far from the observations of X(more precisely, it has been shifted to an interval Jrsuch that ¯ Jr∩¯ Js=∅for all Jscontaining some observation of X). A statistical argument to further explain these properties is the following. As it was remarked, every sample observation Xishows that there is a 7 positive density not only on the real number Xibut also on a neighborhood of it (given by the smoothing parameter). Having this in mind, CE can be interpreted as that the positive density given by the sample is allocated to the right intervals. F means that the density corresponding to an observation Xiis allocated equally to all those intervals to which it must be allocated. These two properties are, in our opinion, quite natural and appealing. Moreover, they characterize the family of the Shapley estimators, as the following theorem shows. Theorem 2 Take δ > 0. For every value of the smoothing parameter k, the corresponding Shapley estimator is the unique δ-estimator satisfying CE and F. Proof. Clearly, the Shapley estimator satisfies CE and F. In order to prove uniqueness, assume that there exist two different δ-estimators satisfying CE and F (let us call them estimators 1 and 2). Since they are different, there must exist a sample Xof size msuch that ˆ f1 X6=ˆ f2 Xand such that it has a maximal number of connected components among those samples of size mfor which the two estimators provide different estimations. For this X, take a connected component Cand i, j ∈Csuch that iand jare directly connected. Since both estimators satisfy F, ˆ fr X(i)−ˆ fr X(j) = ˆ fr X\Xl(i)−ˆ fr X\Xl(j) (1) for all r∈ {1,2}and all Xl∈¯ Ji∩¯ Jj. Note now that ˆ f1 X\Xl(i)−ˆ f1 X\Xl(j) = ˆ f2 X\Xl(i)−ˆ f2 X\Xl(j) (2) because, if Xlis the unique observation in ∪k∈CJk, then all the elements in equation (2) are zeros and, otherwise, X\Xlhas, at least, one connected component more than Xand then (2) follows from maximality of X. Hence, in view of (1) and (2), it holds that ˆ f1 X(i)−ˆ f2 X(i) = ˆ f1 X(j)−ˆ f2 X(j). It is clear that repeating this argument a finite number of times, one concludes that ˆ f1 X(i)−ˆ f2 X(i) is constant for all i∈C. Since both estimators satisfy CE that constant must be zero. This clearly implies that ˆ f1 X=ˆ f2 X, which is a contradiction. 2 8 4 Properties of the Shapley estimator In the sequel, the statistical and computational properties of this estimator will be studied in comparison with a kernel estimator. The Shapley estimator results to be within well-known families of density estimators: it is a binned kernel density estimator and it is a WARPing-type density estimator. Binned kernel density estimators use some set of binning functions wδ i(x) (where Pi∈Zwδ i(x) = 1 for all x∈Rand δ > 0) to distribute the weight of each sample point Xjamong the intervals Ji(the bins); concentrate the accumulated weight of each bin at its center, gi; and then apply a kernel estimator to the resulting weighted “sample“ {(gi, Ni)}, where Ni=Pm j=1 wδ i(Xj): ˆ fB(x) = 1 mh X i∈Z NiK(x−gi h). The Shapley estimator is a binned kernel estimator with wδ i(x) = IJi(x), Ni=n(i), K=1 2I[−1,1) and h=δ(k+1 2). WARPing (Weighted Averaging of Rounded Points) estimators use a discrete function w(r, i) (r, i ∈Z;Pi∈Zw(r, i) = 1 ∀r∈Z) to distribute the total weight of the sample points in each bin among the neighboring bins: ˆ fW(x) = 1 mδ X r∈Z w(r, i)n(r)∀x∈Ji. If δis small enough, smoothing is mainly effected by the function w(r, i), which is often defined in terms of a smoothing parameter. The Shapley estimator is a WARPing estimator with w(r, i) = 1 (2k+1) if r∈Nk(i), w(r, i) = 0 otherwise. Scott (1985) showed that one particular type of WARPing estimator, the averaged shifted histogram, is similar to the histogram in computational efficiency and to kernel estimators in statistical efficiency. By computational efficiency we simply mean little computational costs, whereas statistical efficiency refers to the accuracy of the estimation. Results on the efficiency of binned kernel estimators have been obtained by Hall and Wand (1996). The objective of binning is to reduce computational costs. Computationally, the most efficient estimator is the histogram, which uses bins without 9