Predicting a binary sequence almost as well as the optimal biased coin
Predicting a binary sequence almost as well as the optimal biased coin
复制标题
预测二进制序列几乎与最优偏置硬币一样好
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Y. Freund
中科院分区：
文献类型：
--
作者：
Y. Freund
We apply the exponential weight algorithm, introduced and Littlestone and Warmuth [26]and by Vovk [35]to the problem of predicting a binary sequence almost as well as the best biased coin. We first show that for the case of the logarithmic loss, the derived algorithm is equivalent to the Bayes algorithm with Jeffreys prior, that was studied by Xie and Barron [38]under probabilistic assumptions. We derive a uniform bound on the regret which holds for any sequence. We also show that if the empirical distribution of the sequence is bounded away from 0 and from 1, then, as the length of the sequence increases to infinity, the difference between this bound and a corresponding bound on the average case regret of the same algorithm (which is asymptotically optimal in that case) is only 1/2. We show that this gap of 1/2 is necessary by calculating the regret of the min–max optimal algorithm for this problem and showing that the asymptotic upper bound is tight. We also study the application of this algorithm to the square loss and show that the algorithm that is derived in this case is different from the Bayes algorithm and is better than it for prediction in the worstcase.
