×

On universal algorithms for classifying and predicting stationary processes. (English) Zbl 1479.60080

Summary: This is a survey of results on universal algorithms for classification and prediction of stationary processes. The classification problems include discovering the order of a k-step Markov chain, determining memory words in finitarily Markovian processes and estimating the entropy of an unknown process. The prediction problems cover both discrete and real valued processes in a variety of situations. Both the forward and the backward prediction problems are discussed with the emphasis being on pointwise results. This survey is just a teaser. The purpose is merely to call attention to results on classification and prediction. We will refer the interested reader to the sources. Throughout the paper we will give illuminating examples.

MSC:

60G25 Prediction theory (aspects of stochastic processes)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Algoet, P. (1992). Universal schemes for prediction, gambling and portfolio selection. Annals of Probability. 20 901-941. Correction: ibid. vol. 23, pp. 474-478, 1995. · Zbl 0758.90006
[2] Algoet,P. (1994) The strong low of large numbers for sequential decisions under uncertainity. IEEE Transactions on Information Theory 40 609-634. · Zbl 0827.62077
[3] Algoet, P (1999) Universal schemes for learning the best nonlinear predictor given the infinite past and side information. IEEE Transactions on Information Theory, 45 1165-1185. · Zbl 0959.62078
[4] Bailey, D.H. (1976) Sequential Schemes for Classifying and Predicting Ergodic Processes. Ph. D. thesis, Stanford University.
[5] Berger, A. (1951) On uniformly consistent tests. Ann. Math. Statistics 22 289-293. · Zbl 0042.38003
[6] Berti, P. Crimaldi,I. Pratelli, L. and Rigo,P. (2009) Rate of convergence of predictive distributions for dependent data Bernoulli 15 1351-1367. · Zbl 1375.60063
[7] Biau, G., Bleakley, K. Györfi, L., and Ottucsák, Gy. (2010) Nonparametric sequential prediction of time series, Journal of Nonparametric Statistics, 22 297-317. · Zbl 1189.62152
[8] Breiman, L. (1957) The individual ergodic theorem of information theory, Annals of Mathematical Statistics, 28, 809-811, · Zbl 0078.31801
[9] Breiman, L. (1960) The individual ergodic theorem of information theory: correction, Annals of Mathematical Statistics, 31, 809-810. · Zbl 0092.34001
[10] Bühlmann, P. and Wyner, A.J. (1999) Variable- length Markov chains. Annals of Statistics 27 480-513. · Zbl 0983.62048
[11] Bunea, F. and Nobel, A. (2008) Sequential procedures for aggregating arbitrary estimators of a conditional mean IEEE Transactions on Information Theory 54 1725-1735. · Zbl 1329.62359
[12] Cover T. (1975). Open Problems in Information Theory. 1975 IEEE-USSR Joint Workshop on Information Theory 35-36.
[13] Csiszár, I. and Shields, P. (2000) The consistency of the BIC Markov order estimator. Annals of Statistics. 28 1601-1619. · Zbl 1105.62311
[14] Csiszár, I. (2002) Large-scale typicality of Markov sample paths and consistency of MDL order estimators. IEEE Transactions on Information Theory 48 1616-1628. · Zbl 1060.62092
[15] Csiszár, I. and Talata, Zs. (2006) Context tree estimation for not necessarily finite memory processes via BIC and MDL. IEEE Transactions on Information Theory 52 1007-1016. · Zbl 1284.94027
[16] Cerqueti, R., Falbo, P., and Pelizzari, C. (2017) Relevant states and memory in Markov chain bootstrapping and simulation. European Journal of Operational Research 256 163-177. · Zbl 1394.90553
[17] Dembo, A. and Peres, Y. (1994) A topological criterion for hypothesis testing. Annals of Stat. 22 106-117. · Zbl 0818.62010
[18] Felber, T. Jones, D., Kohler, M., and Walk, H. (2013) Weakly universally consistent static forecasting of stationary and ergodic time series via local averaging and least squares estimates. Journal of Statistical Planning and Inference 143 1689-1707. · Zbl 1279.62198
[19] Finesso, L. (1990) Consistent Estimation of the Order for Markov and Hidden Markov Chains PhD thesis, University of Maryland.
[20] Finesso, L. (1992) Estimation of the order of a finite Markov chain. Recent advances in mathematical theory of systems, control, networks and signal processing, I (Kobe, 1991), 643-645, Mita, Tokyo.
[21] Furstenberg, H. (1960) Stationary Processes and Prediction Theory Princeton University Press. · Zbl 0178.53002
[22] Gallo, S. and Leonardi F. (2015) Nonparametric statistical inference for the context tree of a stationary ergodic process Electronic Journal of Statistics. 9 2076-2098. · Zbl 1327.62457
[23] Gutman, Y. and Hochman, M. (2008) On processes which cannot be distinguished by finite observation. Israel J. Math. 164 265-284. · Zbl 1149.37005
[24] Györfi, L., Kohler, M., Krzyzak, A. and Walk, H. (2002) A Distribution Free Theory of Nonparametric Regression Springer-Verlag, New York · Zbl 1021.62024
[25] Györfi, L. Lugosi, G. (2002) Strategies for sequential prediction of stationary time series. In M. Drop, P. L’Ecuyer, and F. Szidarovszky, editors, Examination of Stochastic Theory, Methods and Applications, 225-248. Kluwer Academic Publishers.
[26] Györfi, L. Lugosi, G. and Morvai, G. (1999) A simple randomized algorithm for sequential prediction of ergodic time series. IEEE Transactions on Information Theory 45 2642-2650. · Zbl 0951.62080
[27] Györfi, L., Morvai, G. and Yakowitz, S. (1998) Limits to consistent on-line forecasting for ergodic time series. IEEE Transactions on Information Theory, 44 886-892. · Zbl 0899.62122
[28] Györfi, L. and Ottucsák, Gy. (2007) Sequential prediction of unbounded stationary time series. IEEE Transactions on Information Theory 53 1866-1872. · Zbl 1314.62215
[29] Györfi, L., Ottucsák, Gy. and Walk H., (2012) Machine Learning for Financial Engineering Imperial College Press, London. · Zbl 1238.91006
[30] Györfi, L. and Sancetta, S. (2014) An open problem on strongly consistent learning of the best prediction for Gaussian processes. In Topics in Nonparametric Statistics 115-136. Springer, New York, NY. · Zbl 1337.60052
[31] Handel, R. (2011) On the minimal penalty for Markov order estimation. Probability Theory and Related Fields 150 709-738. · Zbl 1235.62120
[32] Heller, A. (1965) On Stochastic Processes Derived from Markov Chains. Annals of Math. Stat. 36 1286-1291. · Zbl 0139.34603
[33] Hida, T. and Hitsuda, M. (1993) Gaussian Processes. Providence, RI:AMS Translation of Mathematical Monographs, 10 · Zbl 0793.60002
[34] Hoeffding, W. and Wolfowitz, J. (1958) Distinguishability of sets of distributions. Ann. Math. Statist. 29 700-718. · Zbl 0135.19404
[35] Jones, D. Kohler,M. and Walk, H. (2012) Weakly Universally Consistent Forecasting of Stationary and Ergodic Time Series. IEEE Transactions on Information Theory 58 1191-1202. · Zbl 1365.62356
[36] Kalikow, S. (1990) Random Markov processes and uniform martingales. Israel Journal of Mathematics, 71 33-54. · Zbl 0711.60041
[37] Kalikow, S., Katznelson, Y. and Weiss, B. (1992) Finitarily deterministic generators for zero entropy systems. Israel Journal of Mathematics 79 33-45. · Zbl 0768.60074
[38] Kalocinski, D. and Steifer, T. (2019) An Almost Perfectly Predictable Process with No Optimal Predictor In: 2019 IEEE International Symposium on Information Theory (ISIT) NEW YORK: IEEE, 2504-2508.
[39] Kalocinski, D. and Steifer, T. (2019) On unstable and unoptimal prediction Mathematical Logic Quarterly 65 218-227. · Zbl 1521.03124
[40] Keane, M. (1972) Strongly mixing g-measures. Invent. Math. 16 309-324. · Zbl 0241.28014
[41] Keane, M. and Smorodinsky, M. (1979) Bernoulli schemes of the same entropy are finitarily isomorphic. Ann. of Math. 109 397-406. · Zbl 0405.28017
[42] Khaleghi A., Ryabko, D., Mary, J. and Preux P. (2016) Consistent Algorithms for Clustering Time Series Journal of Machine Learning Research 3 1-32. · Zbl 1360.68683
[43] Khudanpur, S. and Narayan, P. (2002) Order Estimation for a Special Class of Hidden Markov Sources and Binary Renewal Processses. IEEE Transactions on Information Theory 48 1704-1713. · Zbl 1061.94022
[44] Kieffer, J. (1993) Strongly consistent code-based identification and order estimation for constrained finite-state model classes. IEEE Transactions on Information Theory 39 893-902. · Zbl 0784.94005
[45] Kolmogorov, A.N. (1959) Entropy per unit time as a metric invariant of automorphisms. (Russian), Dokl. Akad. Nauk SSSR 124 754-755. · Zbl 0086.10101
[46] Kontoyiannis, I., Algoet, P., Suhov, Yu. M. and Wyner, A.J. (1998) Nonparametric entropy estimation for stationary processes and random fields, with application to English text. IEEE Transactions on Information Theory 44 1319-1327. · Zbl 1026.94516
[47] Kraft, Ch. (1955) Some conditions for consistency and uniform consistency of statistical procedures. Univ. California Publ. Statist. 2, pp. 125-141. · Zbl 0066.12202
[48] Löcherbach, E. and Orlandi, E.(2011) Neighborhood radius estimation for variable-neighborhood random fields. Stochastic Process. Appl. 121 2151-2185. · Zbl 1398.62058
[49] Maker, Ph.T. (1940). The ergodic theorem for a sequence of functions, Duke Math. J., 6, 27-30. · Zbl 0027.07705
[50] Merhav, N. and Feder, M. (1998) Universal Prediction IEEE Transactions on Information Theory 44 2124-2147. · Zbl 0933.94008
[51] Merhav, N., Gutman, M. and Ziv, J. (1989) On the estimation of the order of a Markov chain and universal data compression. IEEE Transactions on Information Theory 35 1014-1019. · Zbl 0683.94004
[52] Molnár-Sáska, G. and Morvai, G. (2010) Intermittent Estimation for Gaussian Processes. IEEE Transactions on Information Theory 56 2778-2782. · Zbl 1366.62169
[53] Morvai, G. (1994) Estimation of Conditional Distribution for Stationary Time Series. PhD Thesis, Technical University of Budapest.
[54] Morvai, G. (2003) Guessing the output of a stationary binary time series. In: Foundations of Statistical Inference, (Eds. Y. Haitovsky, H.R.Lerche, Y. Ritov) Physika-Verlag 207-215. · Zbl 05280104
[55] Morvai, G., Yakowitz, S., and Algoet, M. (1997) Weakly convergent nonparametric forecasting of stationary time series. IEEE Transactions on Information Theory 43 483-498. · Zbl 0871.62082
[56] Morvai, G., Yakowitz, S. and Györfi, L. (1996) Nonparametric inferences for ergodic, stationary time series. Annals of Statistics., 24 370-379. · Zbl 0855.62076
[57] Morvai, G. and Weiss, B. (2003) Forecasting for stationary binary time series. Acta Applicandae Mathematicae, 79 25-34. · Zbl 1030.62076
[58] Morvai, G. and Weiss, B. (2004) Intermittent estimation of stationary time series. Test 13 525-542. · Zbl 1082.62073
[59] Morvai, G. and Weiss, B. (2005) Prediction for discrete time series. Probability Theory and Related Fields 132 1-12. · Zbl 1061.62148
[60] Morvai, G. and Weiss, B. (2005) Limitations on intermittent forecasting. Statistics and Probability Letters 72 285-290. · Zbl 1066.62090
[61] Morvai, G. and Weiss, B. (2005) On classifying processes. Bernoulli 11 523-532. · Zbl 1073.62077
[62] Morvai, G. and Weiss, B. (2005) Inferring the conditional mean. Theory of Stochastic Processes 11 No. 1-2, 112-120. · Zbl 1164.62382
[63] Morvai, G. and Weiss, B. (2005) Order estimation of Markov chains. IEEE Transactions on Information Theory 51 1496-1497. · Zbl 1309.62144
[64] Morvai, G. and Weiss, B. (2005) Forward estimation for ergodic time series. Ann. I.H.Poincaré Probabilités et Statistiqoes 41 859-870. · Zbl 1070.62073
[65] Morvai, G. and Weiss, B. (2007) On estimating the memory for finitarily Markovian processes. Ann. I.H.Poincaré-PR 43 15-30. · Zbl 1106.62094
[66] Morvai, G. and Weiss, B. (2007) On sequential estimation and prediction for discrete time series. Stochastics and Dynamics 7 417-437. · Zbl 1255.62228
[67] Morvai, G. and Weiss, B. (2008) Estimating the Lengths of Memory Words. IEEE Transactions on Information Theory 54 3804-3807. · Zbl 1329.60095
[68] Morvai, G. and Weiss, B. (2008) On universal estimates for binary renewal processes. Ann. Appl. Probab. 18 1970-1992. · Zbl 1158.62053
[69] Morvai, G. and Weiss, B. (2009) Estimating the residual waiting time for binary stationary time series. ITW 2009. IEEE Information Theory Workshop on Networking and Information Theory 10-12 June 2009 67-70.
[70] Morvai, G. and Weiss, B. (2011) Nonparametric Sequential Prediction for Stationary Processes. Annals of Probability 39, 1137-1160. · Zbl 1301.60052
[71] Morvai, G. and Weiss, B. (2011) Testing stationary processes for independence. Ann. I.H.Poincaré-PR 47 1219-1225. · Zbl 1271.62196
[72] Morvai, G. and Weiss, B. (2012) A note on prediction for discrete time series. Kybernetika 48 809-823,. · Zbl 1318.62277
[73] Morvai, G. and Weiss, B. (2013) Universal Tests for Memory Words. IEEE Transactions on Information Theory 59 6873-6879. · Zbl 1365.60032
[74] Morvai, G. and Weiss, B. (2014) Inferring the Residual Waiting Time for Binary Stationary Time Series. Kybernetika 50 869-882. · Zbl 1308.62067
[75] Morvai, G. and Weiss, B. (2016) A versatile scheme for predicting renewal times. Kybernetika 52 348-358. · Zbl 1389.62062
[76] Morvai, G. and Weiss, B. (2019) A note on discriminating Poisson processes from other point processes with stationary inter arrival times. Kybernetika 55, 802-808. · Zbl 1463.60070
[77] Morvai, G. and Weiss, B. (2020) Estimating the conditional expectations for continuous time stationary processes. Kybernetika 56, 410-431. · Zbl 1474.60098
[78] Morvai, G. and Weiss, B. (2020) Universal rates for estimating the residual waiting time in an intermittent way. Kybernetika 56, 601-616. · Zbl 1474.60203
[79] A. Nobel, “Limits to classification and regression estimation from ergodic processes,” Annals of Statistics, vol. 27 pp. 262-273. · Zbl 0933.62033
[80] Nobel, A.B. (2003) On optimal sequential prediction for general processes. IEEE Transactions on Information Theory 49 83-98. · Zbl 1063.94516
[81] Nobel, A. (2006) Hypothesis testing for families of ergodic processes. Bernoulli 12 251-269. · Zbl 1099.62097
[82] Ornstein, D.S. (1978) Guessing the next output of a stationary process. Israel Journal of Mathematics 30 292-296. · Zbl 0386.60032
[83] Ornstein, D.S. (1974) Ergodic Theory, Randomness, and Dynamical Systems. Yale University Press. · Zbl 0296.28016
[84] Ornstein, D.S. and Weiss, B. (1990) How sampling reveals a process. The Annals of Probability 18 905-930. · Zbl 0709.60036
[85] Ornstein, D.S. and Weiss, B. (1993) Entropy and data compression schemes. IEEE Transactions on Information Theory 39 78-83. · Zbl 0764.94003
[86] Ornstein, D.S. and Weiss, B. (2007) Entropy is the only finitely observable invariant. J. Mod. Dyn. 1 93-105. · Zbl 1109.37005
[87] Peres, Y. and Shields, P. (2005) Two new Markov order estimators. arXiv:math/0506080v1 [math.ST]
[88] Ren, J., Bai, X., Lu, Y.Y., Tang,K., Wang, Y, Reiner, G., and Sun, F. (2018) Alignment-Free Sequence Analysis and Applications Annual Review of Biomedical Data Science 1 93-114.
[89] Ryabko, B. (1988) Prediction of random sequences and universal coding. Problems of Inform. Trans. 24 87-96. · Zbl 0666.94009
[90] Ryabko, B. (2009) Compression-Based Methods for Nonparametric Prediction and Estimation of Some Characteristics of Time Series. IEEE Transactions on Information Theory 55 4309-4315. · Zbl 1367.62095
[91] Ryabko, B. and Astola, J. (2006) Universal codes as a basis for time series testing. Stat. Methodol. 3 375-397. · Zbl 1248.60038
[92] Ryabko, D. (2006) Pattern recognition for conditionally independent data. Journal of Machine Learning Research 7 645-664. · Zbl 1222.68355
[93] Ryabko, D. (2009) An impossibility result for process discrimination. 2009 IEEE International Symposium on Information Theory, VOLS 1- 4 1-4 1734-1738.
[94] Ryabko, D. (2010) Discrimination Between B-Processes is Impossible. Journal of Theoretical Probability 23 565-575. · Zbl 1190.62095
[95] Ryabko, D. (2019) Asymptotic nonparametric statistical analysis of stationary time series, Springer International Publishing. · Zbl 1503.62005
[96] Ryabko, D. (2019) On asymptotic and finite-time optimality of Bayesian predictors. J. Mach. Learn. Res. 20 1-24. · Zbl 1446.62249
[97] Scarpellini, B. (1979) Predicting the future of functions on flows, Math. Systems Theory, 12, 281-296. · Zbl 0429.60036
[98] Scarpellini, B. (1979) Entropy and nonlinear prediction, Probability Theory and Related Fields, 50, (2), 165-178. · Zbl 0419.60033
[99] Scarpellini, B. (1981) Conditional expectations of stationary processes. Z. Wahrsch. Verw. Gebiete 56 no. 4, 427-441. · Zbl 0468.60042
[100] Schäfer, D. (2002) Strongly Consistent Online Forecasting of Centered Gaussian Processes. IEEE Transactions on Information Theory 48 791-799. · Zbl 1072.60501
[101] Shannon,C.E. (1948) A mathematical theory of communication. Bell System Tech. J. 27 379-423, 623-656. · Zbl 1154.94303
[102] Takahashi, H. (2011) Computational Limits to Nonparametric Estimation for Ergodic Processes IEEE Transactions on Information Theory 57 6995-6999. · Zbl 1365.62122
[103] Takahashi, H. (2011) Computational Limits to Nonparametric Estimation for Ergodic Processes IEEE Transactions on Information Theory 57 6995-6999. · Zbl 1365.62122
[104] Weiss,B. (2005) Some remarks on filtering and prediction of stationary processes. Israel J. of Math. 149 345-360. · Zbl 1085.60024
[105] Weiss,B. (2005) Some remarks on filtering and prediction of stationary processes. Israel J. of Math. 149 345-360. · Zbl 1085.60024
[106] Weiss, B. (2000) Single Orbit Dynamics, American Mathematical Society. · Zbl 1083.37500
[107] Weiss, B. (2000) Single Orbit Dynamics, American Mathematical Society. · Zbl 1083.37500
[108] Ziv, J. and Lempel, A. (1977) A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 23 337-343. · Zbl 0379.94010
[109] Ziv, J. and Lempel, A. (1977) A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 23 337-343. · Zbl 0379.94010
[110] Ziv, J. (1978) Coding theorems for individual sequences. IEEE Transactions on Information Theory 24 405-412. · Zbl 0416.94006
[111] Ziv, J. (1978) Coding theorems for individual sequences. IEEE Transactions on Information Theory 24 405-412. · Zbl 0416.94006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.