The Last-Step Minimax Algorithm
作者： Eiji Takimoto , Manfred K. Warmuth
关键词:
摘要: We consider on-line density estimation with a parameterized from an exponential family. In each trial t the learner predicts parameter θt. Then it receives instance xt chosen by adversary and incurs loss - ln p(xt|θt) which is negative log-likelihood of w.r.t. predicted learner. The performance measured regret defined as total minus best off-line. develop algorithm called Last-step Minimax Algorithm that minimax optimal assuming current last one. For one-dimensional families, we give explicit form prediction show its O(ln T), where T number trials. particular, for Bernoulli slightly better than standard Krichevsky-Trofimov probability estimator.
springer.com
core.ac.uk
elsevier.com
sci-hub.st 参考文章(11)
Katy S. Azoury, M. K. Warmuth, Relative loss bounds for on-line density estimation with the exponential family of distributions uncertainty in artificial intelligence. ,vol. 43, pp. 31- 40 ,(1999) , 10.1023/A:1010896012157
Shun-ichi Amari, Differential-geometrical methods in statistics ,(1985)
Jürgen Forster, On Relative Loss Bounds in Generalized Linear Regression fundamentals of computation theory. pp. 269- 280 ,(1999) , 10.1007/3-540-48321-7_22
Manfred K. Warmuth, Eiji Takimoto, The Minimax Strategy for Gaussian Density Estimation. pp conference on learning theory. pp. 100- 106 ,(2000)
Kenji Yamanishi, Extended Stochastic Complexity and Minimax Relative Loss Analysis algorithmic learning theory. pp. 26- 38 ,(1999) , 10.1007/3-540-46769-6_3
Yoav Freund, Predicting a binary sequence almost as well as the optimal biased coin Proceedings of the ninth annual conference on Computational learning theory - COLT '96. pp. 89- 98 ,(1996) , 10.1145/238061.238072
J.J. Rissanen, Fisher information and stochastic complexity IEEE Transactions on Information Theory. ,vol. 42, pp. 40- 47 ,(1996) , 10.1109/18.481776
K. Yamanishi, A decision-theoretic extension of stochastic complexity and its applications to learning IEEE Transactions on Information Theory. ,vol. 44, pp. 1424- 1439 ,(1998) , 10.1109/18.681319
Qun Xie, A.R. Barron, Asymptotic minimax regret for data compression, gambling and prediction international symposium on information theory. ,vol. 46, pp. 431- 445 ,(1997) , 10.1109/18.825803
Jun-ichi Takeuchi, Andrew R Barron, None, Asymptotically minimax regret by Bayes mixtures Proceedings. 1998 IEEE International Symposium on Information Theory (Cat. No.98CH36252). pp. 318- ,(1998) , 10.1109/ISIT.1998.708923