We consider on-line density estimation with a parameterized density from an exponential family. In each trial t the learner predicts a parameter θ{sub}t. Then it receives an instance x{sub}t chosen by the adversary and incurs loss - ln p(x{sub}t|θ{sub}t which is the negative log-likelihood of x{sub}t w.r.t the predicted density of the learner. The performance of the learner is measured by the regret defined as the total loss of the learner minus the total loss of the best parameter chosen off-line. We develop an algorithm called the Last-step Minimax Algorithm that predicts with the minimax optimal parameter assuming that the current trial is the last one. For one-dimensional exponential families, we give an explicit form of the prediction of the Last-step Minimax Algorithm and show that its regret is O(ln T), where T is the number of trials. In particular, for Bernoulli density estimation the Last-step Minimax Algorithm is slightly better than the standard Krichevsky-Trofimov probability estimator.
展开▼
机译：我们考虑与指数族的参数化密度的线密度估计。在每个试验中，学习者预测参数θ{sub} t。然后它接收由对手和发生的损失所选择的实例x {sub} t - ln p（x {sub} t |θ{sub} t，这是x {sub} t的负对数似然学习者。学习者的性能是通过定义的遗憾来衡量，因为学习者的总损失减去了离线所选择的最佳参数的总损失。我们开发了一种称为最后一步Minimax算法的算法，该算法预测最小值假设当前试验是最后一个级别的最佳参数。对于一维指数族，我们提供了一种明确的形式，预测最后一步最小的算法，并显示其后悔是O（ln t），其中t是t试验数量。特别是，对于伯努利密度估计，最后一步的最小算法略好于标准的Krichevsky-Trofimov概率估计器。
展开▼
