### 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

**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.