Classification with finite memory
Aaron D. Wyner, J. Ziv · IEEE Transactions on Information Theory · 1996
Consider the following situation. A device called a classifier observes a probability law P on l-vectors from an alphabet of size A. Its task is to observe a second probability law Q and decide whether P/spl equiv/Q or P and Q are sufficiently different according to some appropriate criterion. If the classifier has available an unlimited memory (so that it can remember P(z) exactly for all z), this is a simple matter. In fact for most differentness criteria, a finite memory of 2/sup (log/ /sup A)l+o(l)/ bits will suffice (for large l), i.e., store a finite approximation of P(z) for all A/sup l/z's. In a sense made precise in this paper, it is shown that a memory of only about 2/sup Rl/ bits is required, where the quantity R