The DOI matches its Crossref record; 67 of the 67 references it cites were found in a registry or an index.
Universal prediction
Abstract
This paper consists of an overview on universal prediction from an information-theoretic perspective. Special attention is given to the notion of probability assignment under the self-information loss function, which is directly related to the theory of universal data compression. Both the probabilistic setting and the deterministic setting of the universal prediction problem are described with emphasis on the analogy and the differences between results in the two settings.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Estimating the Dimension of a Model
Schwarz, G. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344136 · Cited by 47,033
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Probability, Random Variables, and Stochastic Processes.
Abrahams, J., & Papoulis, A. (1984) · Journal of the American Statistical Association · doi:10.2307/2288754 · Cited by 16,226
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
Extrapolation, Interpolation, and Smoothing of Stationary Time Series: With Engineering Applications
Wiener, N. (1949) · The MIT Press eBooks · doi:10.7551/mitpress/2946.001.0001 · Cited by 4,826
Compression of individual sequences via variable-rate coding
Ziv, J., & Lempel, A. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055934 · Cited by 3,432
On the Complexity of Finite Sequences
Lempel, A., & Ziv, J. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055501 · Cited by 2,717
Prediction and Entropy of Printed English
Shannon, C. E. (1951) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1951.tb01366.x · Cited by 2,686
Asymptotically efficient adaptive allocation rules
Lai, T. L., & Robbins, H. (1985) · Advances in Applied Mathematics · doi:10.1016/0196-8858(85)90002-8 · Cited by 2,406
An invariant form for the prior probability in estimation problems
Jeffreys, H. (1946) · Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences · doi:10.1098/rspa.1946.0056 · Cited by 2,323
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
A New Interpretation of Information Rate
Kelly, J. L. (1956) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1956.tb03809.x · Cited by 1,586
Reference Posterior Distributions for Bayesian Inference
Bernardo, J. M. (1979) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1979.tb01066.x · Cited by 1,095
Dawid, A. P. (1984) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2981683 · Cited by 1,085
Randolph, P. H. (1970) · Technometrics · doi:10.1080/00401706.1970.10488715 · Cited by 986
The context-tree weighting method: basic properties
Willems, F. M. J., Shtarkov, Y. M., & Tjalkens, T. J. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382012 · Cited by 919
Universal coding, information, prediction, and estimation
Rissanen, J. (1984) · IEEE Transactions on Information Theory · doi:10.1109/tit.1984.1056936 · Cited by 898
Fisher information and stochastic complexity
Rissanen, J. J. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.481776 · Cited by 814
An analog of the minimax theorem for vector payoffs
Blackwell, D. (1956) · Pacific Journal of Mathematics · doi:10.2140/pjm.1956.6.1 · Cited by 740
Entropy and Information Theory
Gray, R. M. (1990) · Springer eBooks · doi:10.1007/978-1-4757-3982-4 · Cited by 660
Cover, T. M. (1991) · Mathematical Finance · doi:10.1111/j.1467-9965.1991.tb00002.x · Cited by 587
Vovk, V. G. (1990) · Conference on Learning Theory · doi:10.5555/92571.92672 · Cited by 551
The performance of universal encoding
Krichevsky, R., & Trofimov, V. (1981) · IEEE Transactions on Information Theory · doi:10.1109/tit.1981.1056331 · Cited by 535
Generalized Kraft Inequality and Arithmetic Coding
Rissanen, J. J. (1976) · IBM Journal of Research and Development · doi:10.1147/rd.203.0198 · Cited by 510
Rissanen, J., & Langdon, G. (1981) · IEEE Transactions on Information Theory · doi:10.1109/tit.1981.1056282 · Cited by 454
Information-theoretic asymptotics of Bayes methods
Clarke, B. S., & Barron, A. R. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.54897 · Cited by 431
Game theory, on-line prediction and boosting
Freund, Y., & Schapire, R. E. (1996) · Proceedings of the ninth annual conference on Computational learning theory - COLT '96 · doi:10.1145/238061.238163 · Cited by 383
Universal prediction of individual sequences
Feder, M., Merhav, N., & Gutman, M. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.144706 · Cited by 373
Self-citationDavisson, L. (1973) · IEEE Transactions on Information Theory · doi:10.1109/tit.1973.1055092 · Cited by 365
Universal portfolios with side information
Cover, T. M., & Ordentlich, E. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.485708 · Cited by 347
Vovk, V. G. (1990) · Colt Proceedings 1990 · doi:10.1016/b978-1-55860-146-8.50032-1 · Cited by 328
Jeffreys' prior is asymptotically least favorable under entropy risk
Clarke, B. S., & Barron, A. R. (1994) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(94)90153-8 · Cited by 292
Asymptotically Subminimax Solutions of Compound Statistical Decision Problems
Robbins, H. E. (1951) · University of California Press eBooks · doi:10.1525/9780520411586-011 · Cited by 264
Asymptotically Subminimax Solutions of Compound Statistical Decision Problems
Robbins, H. (1985) · Herbert Robbins Selected Papers · doi:10.1007/978-1-4612-5110-1_1 · Cited by 228
A universal finite memory source
Weinberger, M. J., Rissanen, J. J., & Feder, M. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382011 · Cited by 228
Self-citationA convergent gambling estimate of the entropy of English
Cover, T., & King, R. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055912 · Cited by 220
Complexity of strings in the class of Markov sources
Rissanen, J. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057210 · Cited by 192
On-Line Algorithms in Machine Learning
Blum, A. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0029575 · Cited by 162
Sequential prediction of individual sequences under general loss functions
Haussler, D., Kivinen, J., & Warmuth, M. K. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.705569 · Cited by 161
Cesa‐Bianchi, N., Freund, Y., Helmbold, D. P., Haussler, D. H., Schapire, R. E., & Warmuth, M. K. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167198 · Cited by 143
Mutual information, metric entropy and cumulative relative entropy risk
Haussler, D. H., & Opper, M. (1997) · The Annals of Statistics · doi:10.1214/aos/1030741081 · Cited by 137
Prequential Probability: Principles and Properties
Dawid, A. P., & Vovk, V. (1999) · Bernoulli · doi:10.2307/3318616 · Cited by 135
Universal Schemes for Prediction, Gambling and Portfolio Selection
Algoet, P. (1992) · The Annals of Probability · doi:10.1214/aop/1176989811 · Cited by 114
Universal schemes for sequential decision from individual data sequences
Merhav, N., & Feder, M. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243445 · Cited by 102
Self-citationA strong version of the redundancy-capacity theorem of universal coding
Merhav, N., & Feder, M. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382017 · Cited by 101
Self-citationPlotnik, E., Weinberger, M. J., & Ziv, J. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.108250 · Cited by 98
A source matching approach to finding minimax codes
Davisson, L., & Leon‐Garcia, A. (1980) · IEEE Transactions on Information Theory · doi:10.1109/tit.1980.1056167 · Cited by 97
Learning probabilistic prediction functions
Santis, A. D., Markowsky, G., & Wegman, M. N. (1988) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21929 · Cited by 95
Average redundancy rate of the Lempel-Ziv code
Louchard, G., & Szpankowski, W. (1997) · IEEE Transactions on Information Theory · doi:10.1109/18.567640 · Cited by 92
Optimal sequential probability assignment for individual sequences
Weinberger, M. J., Merhav, N., & Feder, M. (1994) · IEEE Transactions on Information Theory · doi:10.1109/18.312161 · Cited by 91
Self-citationControlled Random WalksPreprint
Blackwell, D. (2010) · RePEc: Research Papers in Economics · Cited by 89
A game of prediction with expert advice
Vovk, V. (1995) · Annual Conference on Computational Learning Theory (COLT) · doi:10.1145/225298.225304 · Cited by 88
A note on the Ziv - Lempel model for compressing individual sequences (Corresp.)
Langdon, G. G. (1983) · IEEE Transactions on Information Theory · doi:10.1109/tit.1983.1056645 · Cited by 85
The strong law of large numbers for sequential decisions under uncertainty
Algoet, P. (1994) · IEEE Transactions on Information Theory · doi:10.1109/18.335876 · Cited by 74
Asymptotic Solutions of the Compound Decision Problem for Two Completely Specified Distributions
Hannan, J. F., & Robbins, H. E. (1955) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177728591 · Cited by 73
The prediction error of stationary Gaussian time series of unknown covariance
Davisson, L. (1965) · IEEE Transactions on Information Theory · doi:10.1109/tit.1965.1053829 · Cited by 73
On loss functions which minimize to conditional expected values and posterior probabilities
Miller, J. W. V., Goodman, R. M., & Smyth, P. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243457 · Cited by 68
Optimal prefetching via data compression
Vitter, J. S., & Krishnan, P. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185360 · Cited by 67
Minimax noiseless universal coding for Markov sources
Davisson, L. (1983) · IEEE Transactions on Information Theory · doi:10.1109/tit.1983.1056652 · Cited by 65
Gambling using a finite state machine
Feder, M. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.133269 · Cited by 65
Self-citationPredicting Nearly As Well As the Best Pruning of a Decision Tree
Helmbold, D. P., & Schapire, R. E. (1997) · Machine Learning · doi:10.1023/a:1007396710653 · Cited by 65
Dawid, A. P. (1992) · Lecture notes-monograph series · doi:10.1214/lnms/1215458842 · Cited by 61
On-line learning of linear functions
Littlestone, N., Long, P. M., & Warmuth, M. K. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103467 · Cited by 44
Coding of sources with unknown statistics--I: Probability of encoding error
Ziv, J. (1972) · IEEE Transactions on Information Theory · doi:10.1109/tit.1972.1054830 · Cited by 38
Worst Case Prediction over Sequences under Log Loss
Opper, M., & Haussler, D. H. (1999) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4612-1524-0_6 · Cited by 29
Cited by
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
Reliable communication under channel uncertainty
Lapidoth, A., & Narayan, P. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720535 · Cited by 519
Optimal, reliable estimation of quantum states
Blume-Kohout, R. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/4/043034 · Cited by 393
Privacy against statistical inference
du Pin Calmon, F., & Fawaz, N. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483382 · Cited by 327
Verdu, S. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720531 · Cited by 316
Metadata
- Authors
- Merhav, N., & Feder, M.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1998
- Volume
- 44
- Issue
- 6
- Pages
- 2124-2147
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2294584261
- Cited by
- 438
- References
- 67
- FWCI
- 10.94
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.