Insegnamento a.a. 2023-2024

20877 - INFORMATION THEORY

Department of Computing Sciences

Course taught in English
AI (8 credits - II sem. - OB  |  INF/01)
Course Director:
LUCA TREVISAN



Conoscenze pregresse consigliate

Mathematical maturity and the basics of combinatorics and of discrete probability

Mission e Programma sintetico

MISSION

The mission of the course is to make students: (i) understand the mathematical foundations of data compression and of error detection and error correction when storing and transmitting data; (ii) have familiarity with the concept of entropy and mutual information, and their applications to high-dimensional probability, data analysis, predictions and the foundations of machine learning; (iii) be prepared to use entropy regularization and the maximum entropy principle in machine learning, to use KL divergence to study the similarity of distributions, and to understand the connection between data compression and predictions.

PROGRAMMA SINTETICO

The main topics of the course are:

- probability and combinatorics review

- notions of entropy and mutual information

- entropy and data compression

- applications to predictions

- channel capacity and error-correcting codes

- continuous analogs of discrete channels

- applications to statistics

- the maximum entropy principle

- applications to finance: portfolio theory


Risultati di Apprendimento Attesi (RAA)

CONOSCENZA E COMPRENSIONE

Al termine dell'insegnamento, lo studente sarà in grado di...

- understand how entropy models optimal data compression and how data compression is related to modeling and predictions

- understand how to model the errors introduced by a noisy channel and how the capacity of a channel limits the rate of information transmission

- describe and analyze the main families of algebraic error-correcting codes

- connect information theory concepts to applications in statistics, finance, and machine learning

CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE

Al termine dell'insegnamento, lo studente sarà in grado di...

- define probabilistic models and compute information-theoretic quantities related to such models

- choose the error-correcting scheme most appropriate to a particular applications

- apply information-theoretic techniques to compute tail bounds of discrete probabilistic models

- apply information-theoretic techniques to machine learning applications

- use entropy and KL divergence in applications, perform calculations and estimate asymptotic bounds

- apply information-theoretic techniques to financial models


Modalità didattiche

  • Lezioni frontali
  • Esercitazioni (esercizi, banche dati, software etc.)
  • Lavori/Assignment individuali

DETTAGLI

Students will practice their modeling and calculation skills with in-class exercises. Those will take place a few times during the semester during class. Students will aply the theoretical knowledge from previous lectures to solve the exercises individually or in small groups. The correct solution will then be presented by the instructor. The goal of this activity is for students to practice the applications of the theoretical knowledge imparted in class and to self-evaluate their progress in the class.

 

Students will also be given take-home individual assignments, which will similarly be questions that test the ability of the students to apply the theoretical knowledge of the course. These assignments will be graded. The goal of this activity is for students to practice their problem-solving abilities on more challenging questions than the ones given as in-class exercises, and it will provide an ongoing assessment of the progress of each student in their understanding of the subject. 


Metodi di valutazione dell'apprendimento

  Accertamento in itinere Prove parziali Prova generale
  • Prova individuale scritta (tradizionale/online)
  x x
  • Assignment individuale (relazione, esercizio, dimostrazione, progetto etc.)
x    

STUDENTI FREQUENTANTI E NON FREQUENTANTI

Students will be given individual take-home assignments to test their progress during the course, there will be a written midterm and a written general exam. The final grade will be determined by assignments (5%), midterm (40%) and general (55%)


Materiali didattici


STUDENTI FREQUENTANTI E NON FREQUENTANTI

Cover and Thomas, "Elements of Information Theory", 2nd edition, Wiley

Modificato il 06/02/2024 09:46