Efficient Data Representations that Preserve Information
(invited lecture for ALT 2003)
Author: Naftali Tishby
Affiliation: Institute of Computer Science and
Center for Neural Computation, The Hebrew University,
A fundamental issue in computational learning theory, as well as in
biological information processing, is the best possible relationship
between model representation complexity and its prediction accuracy.
Clearly, we expect more complex models that require longer data
representation to be more accurate. Can one provide a quantitative, yet
general, formulation of this trade-off?
In this talk I will discuss this question from Shannon's Information Theory
perspective. I will argue that this trade-off can be traced back to the
basic duality between source and channel coding and is also related to the
notion of "coding with side information". I will review some of the
theoretical achievability results for such relevant data representations and
discuss our algorithms for extracting them. I will then demonstrate the
application of these ideas for the analysis of natural language corpora
and speculate on possibly-universal aspects of human language that they
Based on joint works with Ran Bacharach, Gal Chechik, Amir Globerson,
Amir Navot, and Noam Slonim.
©Copyright 2003 SPRINGER