Title: Classification with Finite Memory Revisited
Speaker: Jacob Ziv, Professor of Electrical Engineering, Technion--Israel Institute of Technology: President, Israeli Academy of Sciences and Humanities
Date: Thursday October 3, 2002 4:00 pm
Location: Princeton University, Friend 101
Abstract:
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.
Seminar Sponsored by DIMACS Special Focus on Computational Information Theory and Coding.