Stanford University
Thursday, July 6, 2006
|
Lecture Home |
Kailath Lecture 2006 Abstract |
|
2006 Program |
On Universal Modelling: How to Learn the Most from an Individual SequenceJacob ZivHerman Gross Professor of Electrical EngineeringTechnion -- Israel Institute of Technology Traditionally, the analysis of information processing systems is based on modeling the mechanism that generates the observed data, e.g. as a realization of some ergodic process. Based on such assumptions, a processor (a data compression algorithm, or a classifier for example) is then optimally designed. In practice, such a-priori information is often not available and the processor design must be based on the observed data only, under some complexity constraints on the processor. This raises the question of what we can do when only a single data record is available, and in particular the question: What is the information carried by an individual sequence? We first consider the case where consecutive blocks of N letters of a semi-infinite finite-alphabet individual sequence are being compressed into binary sequences by some one-to-one mapping. It is assumed that no a-priori information about the sequence is available at the encoder, which must therefore adopt a universal data compression algorithm. We discuss the best possible compression that may be achieved by ANY universal data compression algorithm for finite N-blocks and demonstrate that this can be achieved by context tree coding. Next, we discuss a device called a "classifier", which observes an individual training sequence, X; its task is to examine individual test sequences of length N and to decide whether the test N-sequence has the same features as those that can be captured by the training sequence X, or is significantly different, according to some appropriate criterion. Here again, it is demonstrated that a particular universal context classifier with computational time and storage-space complexity linear in N is essentially optimal.
These results may contribute a theoretical "individual
sequence" justification for the Probabilistic Suffix Tree (PST) approach
in learning theory and in computational biology.
|
