Methods for Artificial Intelligence
Insegnamento: Methods for Artificial Intelligence
Titolo insegnamento in inglese: Methods for Artificial Intelligence
Lingua: inglese
Anno di corso: 1
Semestre: 2
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Silvia Rossi
Obiettivi Formativi
L’obiettivo di questo corso è di fornire agli studenti una conoscenza completa e approfondita dei principi e delle tecniche dell'intelligenza artificiale introducendo i problemi classici dell'IA, nonché i modelli e gli algoritmi utilizzati per affrontare questi problemi. Il programma del corso è diviso in tre parti. Nella prima saranno presentati algoritmi per la risoluzione di problemi di ricerca informata nello spazio degli stati, ricerca online ed in presenza di avversario, e problemi di soddisfacimento di vincoli. Nella seconda parte sarà analizzato il ragionamento e processo decisionale in caso di incertezza, discusso come rappresentare la conoscenza, inclusa la conoscenza incompleta e incerta del mondo reale; come ragionare logicamente con quella conoscenza usando le probabilità; come utilizzare questi modelli e metodi di ragionamento per decidere cosa fare. Nella terza parte saranno introdotte le problematiche relative a modelli distribuiti di decisione. In particolare saranno presentati approcci di teoria dei giochi per la modellazione di processi di decisione nel caso di interazioni non cooperative e le possibili applicazioni di tali tecniche a problematiche concrete.
Programma
Introduzione al Corso • Cenni Storici Problem Solving • Tipologia di problemi: Problemi a Stato singolo, Problemi a stato multiplo, Problemi dipendenti da situazioni, Imprevedibili a priori, Problemi di tipo esplorazione. • Strutture di rappresentazione e formalizzazione del problema per le prime tre tipologie. • Strategie di ricerca non informata per le prime due tipologie di ricerca: o Ricerca in ampiezza e a costo uniforme; o Ricerca in profondità, e con iterazione della profondità; o Proprietà e confronto delle strategie di ricerca. • Strategie di ricerca e euristiche per le prime due tipologie di ricerca: o Greedy best-first, A* ed euristiche ammissibili; o Euristiche consistenti; o Iterative Deepening A*; o Algoritmi di ricerca locale: Hill-climbing search, Local beam search, Simulated Annealing and Genetic. • Giochi a più agenti: giochi a somma zero visti come problemi da risolvere; o Funzioni di utilità e strategia minimax; o Alpha beta pruning. • Soluzione di problemi con vincoli: CSP o CSP come problema di ricerca; o Backtracking per CSP, ordinamento di variabili e valori; o Propagazione dei vincoli: Forward Checking e AC3; o Struttura del problema; o Ricerca locale. Ragionamento e rappresentazione con conoscenza incerta • Rappresentazione dell’incertezza: o Introduzione a decision theory, nozioni base di probabilità, eventi atomici, probabilita’ incondizionata, Joint probabilità distribution, probabilita’ condizionale; o Indipendenza e indipendenza condizionata, teorema di Bayes; • Reti bayesiane: o Introduzione e tabelle delle probabilità condizionate; o Rappresentazione delle relazioni e delle probabilità condizionate; o Inferenze esatte: enumerazione, eliminazione di variabili. • Ragionamento in condizioni di incertezza: o Azioni e utilità attesa, decision networks e rappresentazione di un problema di decisione, valore dell’informazione; o Problemi con decisioni in sequenza, utilità degli stati e equazione di Bellman, policy, soluzione con iterazione del valore, soluzione con iterazione della policy. Sistemi multi-agente e game theory • Introduzione ai sistemi multi-agente; • Introduzione al game theory: o Giochi in forma normale e soluzioni o Strategie pure e miste; equilibri di Nash, Pareto ottimalita', social welfare; o Giochi a somma zero e rappresentazione estesa; o Calcolo di equilibi e dominanze; o Soluzioni di giochi a somma zero, minmax e alfabeta. o Giochi ripetuti. • Computational social choice: o Meccanismi di votazione: funzioni di scelta sociale e social welfare; o Proprieta' e teorema di Arrow; o Muller-Satterthwaite theorem; o Funzioni di ranking e PageRank; o Votazioni Strategiche e mechanism design (strategie dominanti e Bayes Nash); • Allocating scarce resources: o Meccanismi d'asta, aste per item individuali (asta Inglese, asta Olandese, asta Giapponese, Vickrey); o Strategie dominanti ed equilibri nei meccanismi d'asta; • Reaching agreements: o Negoziazione, domini; o Negoziazione in domini task oriented; o Approcci game teoretici, protocolli con offerte alternate; o Approcci euristici, protocollo di concessione monotona, strategia di Zeuthen; o Negoziazione multi-issue.
Modalità didattiche
Lezioni frontali ed esercitazioni.
Materiale didattico
Si consulti il sito web del docente.
Modalità di esame
L'esame si articola in prova scritta ed orale.
In caso di prova scritta i quesiti sono a risposta libera ed esercizi numerici.