Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory

By Peter D. Grünwald, A. P. Dawid. 2004

584 citations recorded by the source corpus.

We describe and develop a close relationship between two problems that have customarily been regarded as distinct: that of maximizing entropy, and that of minimizing worst-case expected loss. Using a formulation grounded in the equilibrium theory of zero-sum games between Decision Maker and Nature, these two problems are shown to be dual to each other, the solution to each providing that to the other. Although Topsoe described this connection for the Shannon entropy over 20 years ago, it does not appear to be widely known even in that important special case. We here generalize this theory to apply to arbitrary decision problems and loss functions. We indicate how an appropriate generalized definition of entropy can be associated with such a problem, and we show that, subject to certain regularity conditions, the above-mentioned duality continues to apply in this extended context. This simultaneously provides a possible rationale for maximizing entropy and a tool for finding robust Bayes acts. We also describe the essential identity between the problem of maximizing entropy and that of minimizing a related discrepancy or divergence between distributions. This leads to an extension, to arbitrary discrepancies, of a well-known minimax theorem for the case of Kullback-Leibler divergence (the redundancy-capacity theorem of information theory). For the important case of families of distributions having certain mean values specified, we develop simple sufficient conditions and methods for identifying the desired solutions. We use this theory to introduce a new concept of generalized exponential family linked to the specific decision problem under consideration, and we demonstrate that this shares many of the properties of standard exponential families. Finally, we show that the existence of an equilibrium in our game can be rephrased in terms of a Pythagorean property of the related divergence, thus generalizing previously announced results for Kullback-Leibler and Bregman divergences.

Subfields: Management Science and Operations Research, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistical and Nonlinear Physics

Citations in the corpus

Maximum Likelihood Estimation in Log-Linear Models: Theory and Algorithms (2011, methodology): “5 in Haberman (1974) (see Appendix B) and Corollary 3 in Eriksson et al.”
Clustering with Bregman Divergences (2005, background): “Note that F(·) is a function and it is possible to extend the notion of Bregman divergences to the space of functions (Csiszár, 1995; Grünwald and Dawid, 2004).”
Bregman Divergences and Surrogates for Learning (2009, methodology): “A3 makes it easy to recover losses like the log loss or the Brier score [ 8 ], respectively ,from � Q and � B in (22) and (23).”
Strictly Proper Scoring Rules, Prediction, and Estimation (2007, methodology): “Dawid (1998, 2006), Grünwald and Dawid (2004), and Buja et al. (2005) have given further examples of proper scoring rules, entropy, and divergence functions and have elaborated on the connections to the Bregman divergence.”
A survey of Bayesian predictive methods for model assessment, selection and comparison (2012, methodology): “For more information on information measures and discrepancies or divergences as loss functions, see Robert (1996); Bernardo (2005a,b); Gneiting (2011); Grünwald and Dawid (2004).”
Robust Learning under Uncertain Test Distributions: Relating Covariate Shift to Model Misspecification (2014, methodology): “We tie the two problems of density ratio estimation and learning a predictor together through the robust Bayes framework (Grünwald & Dawid, 2004).”
A tutorial introduction to the minimum description length principle (2004, background): “The literature has also established connections between MDL and Jaynes’ [2003] Maximum Entropy Principle [Feder 1986; Li and Vitányi 1997; Grünwald 1998; Grünwald 2000; Grünwald and Dawid 2004] and Vapnik’s [1998] structural risk minimization principle [Grünwald 1998], but there is no space her”
Low Impact Artificial Intelligences (2017, background): “ wish to avoid, we are on much rmer grounds when dening the positive relationship to information theory are involved and not worth expounding in detail here. For extended discussions, see [GR07] and [GD04]. 9 aim we are looking for. This suggests other ways of producing higher impact: by specically ”
Modeling Interaction via the Principle of Maximum Causal Entropy (2010, background): “The maximum causal entropy distribution minimizes the worst case prediction log-loss, inf Theorem 3 follows naturally from Gr¨unwald & Dawid (2003) and extends their “robust Bayes” results to the interactive setting as one justiﬁcation for the maximum causal entropy approach.”
An introduction to domain adaptation and transfer learning (2018, methodology): “Worst-case settings are often formalized as minimax optimization problems [21,88].”
Information Divergence Geometry and the Application to Statistical Machine Learning (2009, background): “Γ -minimax solution, and also [20] for a more general discussion from a game theoretic point of view.”
A Brief Introduction to Machine Learning for Engineers (2017, background): “This leads to the definition of generalized entropy [42] Hl(px) = min x̂ Ex∼px [l(x, x̂)], (A.”