|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
|| Affiliation: || Technion IIT
|| Host: || Reuven Bar-Yehuda
In memory of Shimon Even: http://www.wisdom.weizmann.ac.il/~oded/s_even.html See also: http://en.wikipedia.org/wiki/Shimon_Even Program: 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?" Abstract: 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 it. 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: http://www.cs.technion.ac.il/GeneralInformation/Directions/index.html Car entry at the gate: Just say you are attending the "Computer Science Memorial Day"