Asymptotic minimax regret for data compression, gambling, and prediction
Asymptotic minimax regret for data compression, gambling, and prediction
复制标题
数据压缩、赌博和预测的渐近最小最大遗憾
DOI：
10.1109/18.825803
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
A. Barron
中科院分区：
文献类型：
--
作者：
Qun Xie;A. Barron
对于数据压缩，赌博和单个序列X/sub 1/，/spl middot // spl middot // spl middot/，x/sub n/spl middot的预测问题。给定概率质量函数的目标家族p（x/sub 1/，/spl middot // spl middot // spl middot/，x/sub n/|/spl theta/），我们如何选择概率质量质量函数q （x/sub 1/，/spl middot // spl middot // spl middot/，x/sub n/），以使其大约最大程度地减少最大遗憾/下方dissplayskip10ptminus6pt max（log1/q（x/sub 1/，/sub 1/，/spl） middot // Spl middot // Spl middot/，X/sub n/） - log1/p（x/sub 1/，/spl middot // spl middot // spl middot // spl middot/，x/sub n/|/spl theta // spl circ/）），以便它在minimax遗憾的渐近学中实现了最佳常数c，即形式（d/2）log（n/2/spl pi/）+c+o（1） ），参数维度在哪里？是否可以轻松实施这些渐近学的策略Q？最坏情况序列问题的解决方案与相应期望版本的解决方案有何关系/spl middot // spl middot/，x/sub n/） - log1/p（x/sub 1/，/spl middot // spl middot // spl middot // spl middot/，x/sub sub n/|/spl theta/） ）？在离散的无内存情况下，具有给定大小M的给定字母，带有dirichlet（1/2，/spl middot // spl middot // spl middot // spl middot/，1/2）的贝叶斯程序是渐近的最大值。它的简单修饰显示为渐近的最小值。最佳常数是c/sub m/= log（/spl gamma/（1/2）/sup m //（/spl gamma/（m/2）），它与平方根积分的对数一致此外，对于最坏情况的渐近策略，对于预期版本而言，我们的最佳策略也是最佳的。在此设置中，从大小为k的字母中的侧面信息显示为k（m-1）/2logn/2/spl pi/k+kc/sub m/+o（1）。
For problems of data compression, gambling, and prediction of individual sequences x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/ the following questions arise. Given a target family of probability mass functions p(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/|/spl theta/), how do we choose a probability mass function q(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/) so that it approximately minimizes the maximum regret/belowdisplayskip10ptminus6pt max (log1/q(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/)-log1/p(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/|/spl theta//spl circ/)) and so that it achieves the best constant C in the asymptotics of the minimax regret, which is of the form (d/2)log(n/2/spl pi/)+C+o(1), where d is the parameter dimension? Are there easily implementable strategies q that achieve those asymptotics? And how does the solution to the worst case sequence problem relate to the solution to the corresponding expectation version min/sub q/ max/sub 0/ E/sub 0/(log1/q(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/)-log1/p(x/sub 1/, /spl middot//spl middot//spl middot/, x/sub n/|/spl theta/))? In the discrete memoryless case, with a given alphabet of size m, the Bayes procedure with the Dirichlet(1/2, /spl middot//spl middot//spl middot/, 1/2) prior is asymptotically maximin. Simple modifications of it are shown to be asymptotically minimax. The best constant is C/sub m/=log(/spl Gamma/(1/2)/sup m//(/spl Gamma/(m/2)) which agrees with the logarithm of the integral of the square root of the determinant of the Fisher information. Moreover, our asymptotically optimal strategies for the worst case problem are also asymptotically optimal for the expectation version. Analogous conclusions are given for the case of prediction, gambling, and compression when, for each observation, one has access to side information from an alphabet of size k. In this setting the minimax regret is shown to be k(m-1)/2logn/2/spl pi/k+kC/sub m/+o(1).