Time+Place: Sunday 11/06/2006 16:30 Room 337-8 Taub Bld.
Title: How to learn the most out of an individual sequence?
Speaker: Jacob Ziv - in memory of Shimon Even http://en.wikipedia.org/wiki/Jacob_Ziv
Affiliation: Technion IIT
Host: Reuven Bar-Yehuda


In memory of Shimon Even:
See also: http://en.wikipedia.org/wiki/Shimon_Even

16:00-16:30 Reception
16:30-16:40 In memory of Shimon Even
16:40-17:00 Conferment of the Shimon Even Prize for a Ph.D. student,
followed by a presentation by the recipient
17:00-17:10 Break
17:10-18:00 Prof. Jacob Ziv on
"How to learn the most out of an individual sequence?"

What is the information that is hidden in an individual
finite-alphabet sequence? 

We first consider the case where consecutive blocks of N letters of a
semi-infinite finite-alphabet individual sequence X are being
compressed into binary sequences by some one-to-one mapping. It is
assumed that no a-priori information about the sequence is available
at the encoder, which must therefore adopt a universal data
compression algorithm. We discuss the best possible compression that
may be achieved by ANY universal data compression algorithm for finite
N-blocks and demonstrate that context tree coding essentially achieves

Next, we discuss a device called "classifier", which observes an
individual training sequence X. The classifier's task is to examine
individual test sequences of length N and decide whether the test
N-sequence has the same features as those that are captured by the
training sequence X or is sufficiently different according to some
appropriate criterion. Here again, it is demonstrated that a
particular universal context classifier with a computational time
complexity and storage-space complexity that is linear in N is
essentially optimal. This may contribute a theoretical "individual
sequence" justification for the Probabilistic Suffix Tree (PST)
approach in learning theory and in computational biology

Directions to the Technion:
Car entry at the gate: Just say you are attending the "Computer Science
Memorial Day"