A New Strategy for Predicting, Coding, and Gambling on Decaying Large Alphabets

• Activity Number: 36
• Type: Contributed
• Date/Time: Sunday, August 4, 2013 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Xiao Yang*+ and Andrew Barron
• Companies: Yale and Yale University
• Keywords: large alphabet ; prediction ; minimax regret ; Bayes

Abstract

When we are facing prediction, compression or gambling problem on a large number of choices, traditional methods are deemed incapable in the sense that the per symbol regret does not diminish to zero. However, in many situations we are not to predict or compress on the whole probability simplex. Instead, practically useful conditions put on the probability space or the data could avoid the old difficulty and lead to reasonable solutions of this problem. The result is also interpretable compared to the finite alphabet analogue. In this work, we propose a Bayes strategy based on a lower-dimensional Dirichlet prior for predicting on decaying alphabets, that is, alphabet with size m large but only a small number L of symbols occupying most of the probability. Upper bounds on the expected regret measured by the Kullback-leibler loss and pointwise regret are given. Moreover, examples of prediction and compression of two pieces of literature works are provided. In addition, the minimax regret for large alphabet prediction with a fixed number of symbols appearing in also included.