Classification with Finite Memory
Presenter: Jacob Ziv, Professor, School of Electrical Engineering, The Technion, Israel
Host: Hosted by Alon Orlitsky - contact Alon Orlitsky through Lori Unruh at lunruh@soe.ucsd.edu.
Date: Wednesday, August 14, 2002 (*rescheduled from 08/12/02)
Time: 2:00 p.m., Reception to follow
Location: 4307, EBU I , UC San Diego campus, La Jolla [Directions] [Parking Information]
Abstract: A device called a classifier observes an unknown probability law P on l-vectors from and alphabet 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.
We show 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.)
At the same time, we describe an efficient universal classifier that yields a vanishing classification error for any stationary source that satisfy a mixing condition, provided that N is bugger than the critical value.
Bio: Jacob Ziv received the B.Sc., Dip. Eng., and M.Sc. degrees, all in Electrical Engineering, from the Technion - Israel Institute of Technology, Haifa, Israel, in 1954, 1955, 1957, respectively, and the Sc.D. degree from the Massachusetts Institute of Technology, Cambridge, USA, in 1962.
From 1955-59, and again from 1962-68, he was at the Scientific Department, Israel Ministry of Defense, as a Senior Research Engineer, and as Head of Communications Division, respectively. >From 1961-62, while studying for his doctorate at MIT, he joined the Applied Science Division of Melpar, Inc., as a Senior Research Engineer in communication theory. From 1968-70 he was a Member of the Technical Staff of Bell Laboratories, Inc. He joined Technion full time in 1970 where he is now the Herman Gross Professor of Electrical Engineering and a Technion Distinguished Professor. He was Dean of the Faculty of Electrical Engineering from 1974-76 and Vice President of Academic Affairs from 1978-82.
Jacob Ziv was also the Chairman of the Israeli Universities Planning and Grants Committee from 1985-91. He is a Member of the Israel National Academy of Sciences and Humanities and is currently serving as its President. His research interests include data-compression, information theory, and statistical communication.