CS6800 11F: Presentation Topics

This list is not meant to be exclusive or exhaustive. If there are papers in a field of your interest that use Information Theory and that you would interested in presenting, I would strongly encourage you to present those papers. Think of the list below as just a starting point.

1. Gambling/Investments

   One can characterize the optimal method for gambling via Information Theory, and extensions of this work can be applied to "optimal portfolios" in the stock market.

   Possible presentation topics can be found in

   • Cover and Thomas, Chapter 6;
   • Cover and Thomas, Chapter 16.

2. Kolmogorov Complexity

   Kolmogorov Complexity is a fascinating topic, worthy of a course in and of itself. (I may teach such a course some day.) Kolmogorov Complexity measure the complexity of a "string" not by the entropy of the source that produced it but rather by the size of the smallest program which could reproduce it. Kolmogorov Complexity has many applications, and there are deep connections to Information Theory.

   Possible presentation topics can be found in

   • Cover and Thomas, Chapter 14;
   • Li and Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications.
     (This is a text that should be available at the library; I also have a copy in my office.)

3. Signal Processing, Computer Vision, etc.

   Information Theory has been widely applied to these areas. Below are but a few classic papers.

   • Viola and Wells, Alignment by Maximization of Mutual Information;
   • Hyvarinen, Independent Component Analysis by Minimization of Mutual Information

4. Biology

   Information Theory has often been applied to biological problems; entire conferences have been devoted to these approaches. Here are a few pointers:

   • Pacific Symposium on BioComputing, Information-theoretic Approaches to Biology;
   • Biological Information Theory;
   • Molecular Information Theory;
   • Yockey, Information Theory and Molecular Biology.
     (This text should be available at the library.)

5. Similarity Measures and Computational Linguistics

   Similarity measures are often needed to solve problems in Computational Linguistics, and Information Theory has been widely applied to both topics.

   • Lin, An Information-Theoretic Definition of Similarity;
   • Benedetto, Caglioti, and Loretto, Language Trees and Zipping;
   • Li, Chen, Li, Ma, and Vitanyi, The Similarity Metric
     (This would require a primer on Kolmogorov Complexity or should be scheduled after such a primer by someone else.)

6. Machine Learning

   Information Theory is at the heart of nearly all algorithms for learning Decision Trees, one of the most used and useful machine learning methods. Information Theory has also been used to prove lower bounds on the number of samples necessary to learn in the presence of noise.

   • Inferring decision trees. Below are two tutorials; they contain many other references.
     • Building Classification Models: ID3 and C4.5
     • Induction of Decision Trees

   • Gentile and Helmbold, Improved lower bounds for learning from noisy examples: an information-theoretic approach
     (Presenting this paper would probably require a background in PAC learning.)

7. Network Information Flow and Network Coding

   A flurry of recent papers has appplied Information Theory and coding to study the problem of information flow in computer networks.

   • The Network Coding Homepage