Universal sequential learning and decision from individual data sequences

ABSTRACT

Sequential learning and decision algorithms are investigated, with various application areas, under a family of additive loss functions for individual data sequences. Simple universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n-1logn, where n is the sample size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSM's), is studied. It is shown that Markovian machines with sufficiently long memory exist that are asymptotically nearly as good as any given FSM (deterministic or randomized) for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric schemes is discussed with special attention to the recursive least squares (RLS) algorithm.

REFERENCES

• A92: P. H. A!goet, "Universal Schemes for Prediction, Gambling, and Portfolio Selection,'' Ann. Probab., April 1992.
• AC88: P. H. A!goet and T. M. Cover, "Asymptotic Optimality and Asymptotic Equipartition Properties of Log-Optimum Investment,'' Ann. Probab., 16, No. 2, pp. 876- 898, 1988.
• B56: D. Blackwell, "An Analog to the Minimax Theorem for Vector Payoffs," Pac. J. Math., vol. 6, pp. 1-8, 1956.
• C74: T. M. Cover, "Universal Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin," Technical Report 12, Dept. of Statistics, Stanford University, 1974.
• C91: T. M. Cover, "Universal Portfolios," mATH.fINANCE,VOL,L,NO.1 PP. 1-29, January 1991.
• CS77: T. M. Cover and A. Shenhar, "Compound Bayes Predictors for Sequences with Apparent Markov Structure," IEEE 7~ans. Syst. Man. Cybern., Vol. SMC-7, pp. 421- 424, May-June 1977.
• CT91: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• CK81: I. Csisz~ and J. Kamer, Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, 1981.
• D83: L. D. Davisson, "Minimax Noiseless Universal Coding for Markov Sources," IEEE Trans. Inform. Theory, IT-29, No. 2, pp. 211-215, 1983.
• F91: M. Feder, "Gambling Using a Finite-State Machine," IEEE Trans. Inform. Theory, Voi. IT-37, No. 5, pp. 1459-1465, Sept. 1991.
• FMG92: M. Feder, N. Merhav, and M. Gutman, "Universal Prediction of Individual Sequences," to appear in IEEE Trans. Inform. Theory, July 1992. Also, summarized in Proc. 17th Convention of Electrical & Electronics Engineers in Israel, pp. 223-226, May 1991.
• G62: A. Gill, Introduction to the Theory of Finite-State Machines. McGraw Hill, 1962.
• G68: D. C. Gilliland, "Sequential Compound Estimation," Ann. Math. Statist., Vol. 39, No. 6, pp. 1890-1904, 1968.
• G72: D. C. Gilliland, "Asymptotic Risk Stability Resulting from Play Against the Past in a Sequence of Decision Problems," IEEE 7?ans. Inform. Theory, Vol. IT-18, No. 5, pp. 614-617, Sept. 1972.
• GH69: D. C. Gi!liland, and J. F. Hannan, "On an Extended Compound Decision Problem," Ann. Math. Statist., Vol. 40, No. 5, pp. 1536-1541, 1969.
• GH78: D. C. Gilliland and M. K. Helmers, "On the Continuity of the Bayes Response," IEEE I?ans. Inform. Theory, Vol. IT-24, No. 4, pp. 506-508, July 1978.
• GP77: G. C. Goodwin and R. L. Payne, Dynamic System Identification: Experiment Design and Data Analysis. Mathematics in Science and Engineering, Vol. 136. Academic Press, 1977.
• G84: R. M. Gray, "Vector Quantization," IEEE ASSP Magazine, Vol. 1, No. 2, pp. 4-29, 1984.
• G88: R. M. Gray, Probability, Random Processes, and Ergodic Properties. Springer-Verlag, 1988.
• H57: J. F. Hannan, "Approximation to Bayes Risk in Repeated Plays," in Contributions to the Theory of Games, Vol. III, Annals of Mathematics Studies, No. 39, pp. 97-139, Princeton 1957.
• HR57: J. F. Hannan and H. Robbins, "Asymptotic Solutions of the Compound Decision Problem for Two Completely Specified Distributions,'' Ann. Math. Statist., Vol. 26, pp. 37-51, 1957.
• H86: S Haykin, Adaptive filter theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• H72: M. E. Hellman, "The Effects of Randomization on Finite-Memory Decision Schemes," IEEE Trans. Inform. Theory, IT-18, No. 4, pp. 499-502, 1972.
• HC70: M. E. Heilman and T. M. Cover, "Learning with Finite Memory," Ann. Math. Statist., Vol. 41, No. 3, pp. 765-782, 1970.
• HC71: M. E. Hellman and T. M. Cover, "On Memory Saved by Randomization," Ann. Math. Statist., Vol. 42, No. 3, pp. 1075- 1078, 1971.
• JN84: N. S. Jayant and P. Noll, Digital Coding of Wave forms. Englewood Cliffs, N.J. Prentice-Hall, 1984.
• J67: M. V. Johns, Jr., "Two-action Compound Decision Problems," Proc. Fifth Berkeley Symp. Math. Statist. Prob., Vol. 1, pp. 463-478, University of California Press, 1967.
• KT81: R. E. Krichevsky and V. K. Trofimov, "The Performance of Universal Encoding,'' IEEE Trans. Inform. Theory, IT-27, No. 2, pp. 199-207, March 1981.
• L84: G. G. Langdon, Jr., "An Introduction to Arithmetic Coding," IBM J. Res. Develop., Vol. 28, No. 2, pp. 135-149, 1984.
• LR86: F T Leighton , R L Rivest, Estimating a probability using finite memory, IEEE Transactions on Information Theory, v.32 n.6, p.733-742, Nov. 1986 [doi>10.1109/TIT.1986.1057250]
• LBG80: Y, Linde, A. Buzo, and R. M. Gray, "An Algorithm for Vector Quantizer Design," IEEE Trans. Commun., COM-28, No. 1, pp. 84-95, 1980.
• M75: J. Makhoui, "Linear Prediction: A Tutorial Review," Proc. IEEE, Vol. 63, No. 4, 1975,
• MF92: N. Merhav and M. Feder, "Universal Schemes for Sequential Decision from Individual Data Sequences," submitted to IEEE Trans. Inform. Theory, 1992.
• N79: Y. Nogami, "The k-Extended Set- Compound Estimation Problem in a Nonregular Family of Distributions over (0,0+1)," Ann. Inst. Statist. Math., Vol. 31A, pp. 169-176, 1979.
• PWZ92: E. Plotnik, M. J. Weinberger, and J. Ziv, "Upper Bounds on the Probability of Sequences Emitted by Finite-State Soumes and on the Redundancy of the Lempe!-Ziv Algorithm," IEEE Trans. Inform. Theory, Vol. IT-38, No. 1, pp. 66-72, January 1992.
• R84: J. Rissanen, "Universal Coding, Information, Prediction, and Estimation," IEEE Trans. Inform. Theory, Vol. IT-30, No. 4, pp. 629-636, July 1984.
• R86: J. Rissanen, "Stochastic Complexity and Modeling," Ann. Statist., Vol. 14, No. 3, pp. 1080-1100, 1986.
• R51: H. Robbins, "Asymptotically Subminimax Solutions of Compound Statistical Decision Problems," Proc. 2nd Berkeley Syrup. Math. Statist. Prob., pp. 131-148, 1951.
• S63: E. Samuel, "Asymptotic Solutions of the Sequential Compound Decision Problem," Ann. Math. Statist., pp. 1079-1095, 1963.
• S64: E. Samuel, "Convergence of the Losses of Certain Decision Rules for the Sequential Compound Decision Problem," Ann. Math. Statist., pp. 1606-1621, 1964.
• S74: B. O. Shubert "Finite-Memory Classification of Bernoulli Sequences Using Reference Samples," IEEE Trans. Inform. Theory, IT-20, No. 3, pp. 384-387, 1974.
• S65: D. D. Swain, "Bounds and Rates of Convergence for the Extended Compound Estimation Problem in the Sequence Case," Tech. Report no. 81, Department of Statistics, Stanford University, 1965.
• V66: J. Van Ryzin, "The Sequential Compound Decision Problem with mxn Finite Loss Matrix," Ann. Math. Statist., Vol. 37, pp. 954-975, 1966.
• V80: S. B. Vardeman, "Admissible Solutions of k-Extended Finite State Set and Sequence Compound Decision Problems," J. Multivariate Anal., Vol. 10, pp. 426441, 1980.
• ZL78: J. Ziv and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Trans. Inform. Theory, IT- 24, No. 5, pp. 530-536, Sept. 1978.
• Z90: J. Ziv, Compression, tests for randomness and estimating the statistical model of an individual sequence, Sequences: combinatorics, compression, security, and transmission, Springer-Verlag New York, Inc., New York, NY, 1990

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing

General Terms:
Theory, Verification