On Limited Memory Universal Classification of Individual Sequences
J. Ziv · 2006
We discuss a device called "classifier" (or discriminator) that observes an individual "training" sequence of length of m letters, Xm1. The classifier's task is to examine individual test sequences of length N and decide whether the test N-sequence has the same features as those that are captured by the training sequence, or is sufficiently different, according to some appropriate criterion. No a-priori information about the test sequences is available to the classifier, aside from the training sequence. A universal classifier d(N,ZN1isin AN) for N-vectors is a mapping from ANonto {0,1}. Upon observing ZN1, the classifier declares ZN1to be "similar" to the training sequence Xm1, iff d(N,ZN1) = 1. A trivial way to proceed is to compare the test sequence XN1with each of the distinct N-vectors that appear in the training sequence Xm1. However, this procedure calls for a storage-space complexity that may grow exponentially with N. It is demonstrated that a particular universal context-tree classifier with a computational and storage complexity that is linear in N is essentially optimal. Another task for an N-sequence classifier is to decide whether two N-sequences YN1and ZN1, or more, are similar to each other in the sense that each of the N-sequences is similar (as defined above) to the same unknown training sequence which is not available, (e.g "do these N-sequences sequences have a "common ancestor" - a frequent topic in computational biology). It is demonstrated that such an hypothesis may be essentially optimally tested based on the same context-tree classifier. This contributes a theoretical "individual sequence" justification for the probabilistic suffix tree approach in computational biology