Scienze matematiche per l’intelligenza artificiale

STEFANO LEONARDI
LORENZO MARCONI

Obiettivi Generali

Fornire allo studente le nozioni formali fondamentali di due aspetti basilari della preparazione di uno scienziato dell'intelligenza artificiale, la logica matematica e i metodi probabilistici in informatica. A questi due aspetti sono dedicate le due sezioni del corso. La prima parte del corso ha l’obiettivo di introdurre la logica matematica come potente strumento per modellare e ragionare formalmente su diversi aspetti dell’intelligenza artificiale, in particolare la gestione dei dati, la rappresentazione della conoscenza, l'interrogazione e la revisione di dati e conoscenza. La seconda parte del corso intende illustrare alcuni aspetti fondamentali dei metodi
probabilistici in Informatica quali il progetto e l'analisi degli algoritmi probabilistici, i metodi di campionamento e di allocazione probabilistica, i processi stocastici e alcune loro applicazioni all'analisi dei dati e dell’apprendimento automatico.


Obiettivi specifici

Conoscenza e comprensione
Rispetto alla prima parte del corso, lo studente impara le nozioni fondamentali della logica matematica, i principi secondo i quali si giudica la validità degli argomenti, si analizzano le relazioni tra argomenti e si valutano i rapporti inferenziali, come la deduzione, l’induzione e l’abduzione, tra essi. Rispetto alla seconda parte del corso, lo studente impara le nozioni basilari della progettazione degli algoritmi probabilistici e della loro analisi ed acquisisce le basi per applicare tali nozioni al progetto di algoritmi fondamentali in Intelligenza Artificiale, inclusi algoritmi di ricerca e ordinamento, algoritmi su reti e grafi, algoritmi di classificazione, clustering e apprendimento automatico.

Applicare conoscenza e comprensione
Lo studente acquisisce una comprensione profonda del ruolo della logica in vari aspetti dell'intelligenza artificiale e si appropria di conoscenze di base per formalizzare un problema in logica, analizzare teorie logiche e ragionare sulle relative inferenze, costruire teorie logiche per la modellazione di basi di conoscenza di media complessità, specificare in logica interrogazioni di basi di dati e di conoscenza e tradurre in programmi logici la specifica di semplici computazioni.
Lo studente acquisisce una comprensione profonda del ruolo del ruolo della probabilità nel progetto di algoritmi e nell'analisi dei dati e si appropria di conoscenze di base per svolgere analisi di algoritmi probabilistici, definire algoritmi probabilistici per problemi di media complessità, applicare metodi fondamentali quali il metodo di Monte Carlo, le catene di Markov, la programmazione dinamica ed i modelli bayesiani a diversi contesti, come le sequenze, i grafi, le reti, l’apprendimento automatico, la classificazione ed il clustering.

Capacità critiche e di giudizio
Lo studente è in grado di valutare la validità di affermazioni e di argomentazioni, la coerenza di un insieme di assiomi in una base di conoscenza, l’adeguatezza della formulazione di una computazione che estrae dati da una base di dati e di conoscenza, la correttezza di un programma logico rispetto alla specifica di determinate proprietà. Lo studente è in grado di analizzare algoritmi probabilistici, di valutare l’efficacia di metodi probabilistici e di ottimizzazione dinamica a problemi algoritmici e di Intelligenza Artificiale e di giudicare la qualità dell’applicazione di algoritmi di apprendimento automatico, di classificazione e di clustering.

Capacità comunicative
Le attività pratiche e le esercitazioni del corso consentono allo studente di acquisire strumenti cruciali per comunicare e condividere la valutazione critica di strumenti e linguaggi logici e il loro ruolo nell'intelligenza artificiale e dei metodi algoritmici e il loro ruolo in diversi importanti contesti dell'Intelligenza Artificiale.

Capacità di apprendimento
Oltre alle classiche capacità di apprendimento fornite dallo studio teorico delle tematiche di base trattate nel corso, le modalità di svolgimento del corso stesso, in particolare le attività progettuali, stimolano lo studente all'approfondimento autonomo di alcuni argomenti, al lavoro di gruppo e all'applicazione concreta delle nozioni e delle tecniche apprese durante il corso.

Fornire allo studente le nozioni formali fondamentali di due aspetti basilari della preparazione di uno scienziato dell'intelligenza artificiale, la logica matematica e i metodi probabilistici in informatica. A questi due aspetti sono dedicate le due sezioni del corso. La prima parte del corso ha l’obiettivo di introdurre la logica matematica come potente strumento per modellare e ragionare formalmente su diversi aspetti dell’intelligenza artificiale, in particolare la gestione dei dati, la rappresentazione della conoscenza, l'interrogazione e la revisione di dati e conoscenza. La seconda parte del corso intende illustrare alcuni aspetti fondamentali dei metodi

probabilistici in Informatica quali il progetto e l'analisi degli algoritmi probabilistici, i metodi di campionamento e di allocazione probabilistica, i processi stocastici e alcune loro applicazioni all'analisi dei dati e dell’apprendimento automatico.


Obiettivi specifici

Conoscenza e comprensione
Rispetto alla prima parte del corso, lo studente impara le nozioni fondamentali della logica matematica, i principi secondo i quali si giudica la validità degli argomenti, si analizzano le relazioni tra argomenti e si valutano i rapporti inferenziali, come la deduzione, l’induzione e l’abduzione, tra essi. Rispetto alla seconda parte del corso, lo studente impara le nozioni basilari della progettazione degli algoritmi probabilistici e della loro analisi ed acquisisce le basi per applicare tali nozioni al progetto di algoritmi fondamentali in Intelligenza Artificiale, inclusi algoritmi di ricerca e ordinamento, algoritmi su reti e grafi, algoritmi di classificazione, clustering e apprendimento automatico.

Applicare conoscenza e comprensione
Lo studente acquisisce una comprensione profonda del ruolo della logica in vari aspetti dell'intelligenza artificiale e si appropria di conoscenze di base per formalizzare un problema in logica, analizzare teorie logiche e ragionare sulle relative inferenze, costruire teorie logiche per la modellazione di basi di conoscenza di media complessità, specificare in logica interrogazioni di basi di dati e di conoscenza e tradurre in programmi logici la specifica di semplici computazioni.
Lo studente acquisisce una comprensione profonda del ruolo del ruolo della probabilità nel progetto di algoritmi e nell'analisi dei dati e si appropria di conoscenze di base per svolgere analisi di algoritmi probabilistici, definire algoritmi probabilistici per problemi di media complessità, applicare metodi fondamentali quali il metodo di Monte Carlo, le catene di Markov, la programmazione dinamica ed i modelli bayesiani a diversi contesti, come le sequenze, i grafi, le reti, l’apprendimento automatico, la classificazione ed il clustering.

Capacità critiche e di giudizio
Lo studente è in grado di valutare la validità di affermazioni e di argomentazioni, la coerenza di un insieme di assiomi in una base di conoscenza, l’adeguatezza della formulazione di una computazione che estrae dati da una base di dati e di conoscenza, la correttezza di un programma logico rispetto alla specifica di determinate proprietà. Lo studente è in grado di analizzare algoritmi probabilistici, di valutare l’efficacia di metodi probabilistici e di ottimizzazione dinamica a problemi algoritmici e di Intelligenza Artificiale e di giudicare la qualità dell’applicazione di algoritmi di apprendimento automatico, di classificazione e di clustering.

Capacità comunicative
Le attività pratiche e le esercitazioni del corso consentono allo studente di acquisire strumenti cruciali per comunicare e condividere la valutazione critica di strumenti e linguaggi logici e il loro ruolo nell'intelligenza artificiale e dei metodi algoritmici e il loro ruolo in diversi importanti contesti dell'Intelligenza Artificiale.

Capacità di apprendimento
Oltre alle classiche capacità di apprendimento fornite dallo studio teorico delle tematiche di base trattate nel corso, le modalità di svolgimento del corso stesso, in particolare le attività progettuali, stimolano lo studente all'approfondimento autonomo di alcuni argomenti, al lavoro di gruppo e all'applicazione concreta delle nozioni e delle tecniche apprese durante il corso.

Un corso di base in algoritmi e programmazione, ed un corso di base di probabilità.

1 Lecture Overview of Algorithm Analysis Kleinberg and Tardos, Ch. 2.1 - 2.4

2 Lecture Stable Matching Kleinberg and Tardos, Ch. 1.1, 1.2

3 Lecture Network Flow: Ford and Fulkerson, Capacity Scaling, Shortest Augmenting Paths Kleinberg and Tardos, Ch. 7.1, 7.2, 7.3

4 Lecture Perfect Matching, Circulations, Improved algorithm for bipartite matching (Ascending Price Matching, Hopcroft-Karp) Kleinberg and Tardos, Ch. 1.1, 7.5, 7.7

5 Lecture Greedy Algorithms

6 Lecture Dynamic Programming Kleinberg and Tardos, Ch. 4.1, 4.4, 6.1, 6.2, 6.4, 6.4, 6.8 slides

7 Lecture Basics of complexity and NP-completeness

8 Lecture 8 Basics of approximation algorithms Reference [4], Chapters 1 and 3 slides

9 Lecture Basics of approximation algorithms Reference [4], Chapters 2.1, 8.1, 8.2 slides

10 Lecture Linear Programming based approximation algorithms Reference [4], Chapters 12

11 Lecture Basics of Randomized Algorithms Reference [5], Chapter 5

12 Lecture Introduction to Game Theory and Equilibria Computation Lecture Notes

13 Lecture Computing Equilibria in Zero-Sum Games and Efficiency of Equilibria Lecture Notes

14 Lecture Selfish Routing and Price of Anarchy See Lecture Notes of Lecture 14 and Exercises, Section 2

II Sezione:

Riferimenti:

[1] Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitznmacher, E. Upfal, Cambridge University Press,

[2] Algorithms, S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Mc. Graw Hill.

Lezioni ed Esercitazioni

In person

Modalità d'esame
I Sezione.
Lo studente può scegliere di svolgere l'esame per la sezione "Logica e Informatica" tra due modalità:
Nel primo caso lo studente o il gruppo di due studenti (non di più) sceglie di affrontare un argomento da essi stessi proposto (eventualmente anche in sinergia con un progetto relativo alla sezione del corso su metodi probabilistici) oppure selezionato tra quelli proposti dal docente, e comunica la scelta al docente.

Nel secondo caso l'esame consiste di una prova d'esame tradizionale (scritta ed eventualmente orale) vertente sul programma d'esame. Anche in questo caso lo studente deve mandare un messaggio al docente, che indicherà la data dell'esame.

II Sezione.

Lo studente può scegliere di svolgere l'esame per la sezione "Metodi Probabilistici" tra due modalità:
1. Svolgere un assignment in un gruppo formato da due studenti da consegnare alcuni giorni prima della prima sessione di esame in cui l'assignment verrò discusso con il docente.
2. Svolgere un esame scritto e una discussione orale.

II Sezione.
i) Risolvere il problema della determinazione del numero atteso di passi computazionali necessari per risolvere un problema informatico.
ii) Determinare il numero di campioni necessari per stimare una grandezza con una data precisione nel metodo Monte Carlo.
iii) Determinare lo stato stazionario di una catena di Markov