Princeton-Rutgers Seminar Series in Communications and Information Theory

Chris Rose and Sergio Verdú, Co-Chairs

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


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.