|
Classification with Finite Memory Revisited
Jacob Ziv,
Professor of Electrical Engineering, Technion--Israel Institute of Technology:
President, Israeli Academy of Sciences and Humanities
Thursday October 3, 2002 4:00 pm, Princeton University, Friend 101:
A device called a classifier observes an unknown probability law P on
L-vectors from an alphabet of size A. Its task is to decide whether
P is identical with some given probability law Q. If the classifier
has an unlimited memory, this is a simple matter because one can feed
the classifier with enough training data for P.
It has been shown (Wyner-Ziv,1996) that if N, the size of the memory
(e.g. the length of the training sequence), is smaller than some
critical value, reliable classification is not always possible.
(The critical value is exponential in L).
In this seminar we describe an efficient universal classifier that
yields a vanishing classification error for any unknown stationary
source that satisfies a strong mixing condition, provided that N is
bigger than the critical value.
|
 |
