Knowledge representation and reasoning
A.A. 2025/2026
Learning objectives
L'obiettivo del corso è di fornire agli studenti una comprensione approfondita delle basi teoriche e degli algoritmi per rappresentare la conoscenza e il ragionamento automatico, concentrandosi sull'uso della logica come mezzo per la codifica della conoscenza e sulle tecniche di inferenza di tipo simbolico. Verranno trattati concetti chiave dell'intelligenza artificiale simbolica come tecniche di formal explainability, l'integrazione di inferenza logica con approcci di IA basati sul Machine Learning come tecniche di ragionamento neuro-simbolico. Verranno inoltre esplorate applicazioni pratiche delle tecniche viste durante il corso.
Expected learning outcomes
Lo studente sarà in grado di utilizzare i principali linguaggi di rappresentazione della conoscenza e di codificare diversi task di ragionamento utilizzando tali linguaggi. Saprà modellare scenari reali tramite i linguaggi appresi e di identificare i giusti compromessi tra espressività e complessità computazionale dei vari linguaggi. Lo studente acquisirà una comprensione approfondita degli algoritmi di ragionamento deduttivo e sarà in grado di utilizzare sistemi reali per la rappresentazione della conoscenza e il ragionamento. Inoltre, saprà integrare la logica deduttiva con sistemi di IA induttivi (di ML) attraverso approcci di ragionamento neuro-simbolico.
Periodo: Primo quadrimestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Course syllabus and organization
Edizione unica
Responsabile
Periodo
Primo quadrimestre
Programma
- Rappresentare i dati e ragionare sui dati usando la logica. Che cos'è la rappresentazione della conoscenza e il ragionamento? Introduzione alla logica proposizionale come linguaggio semplice di rappresentazione della conoscenza. I modelli come strumento per dare significato alla nostra rappresentazione. Differenza tra "verità" e "dimostrabilità". Come possiamo usare la logica per fare inferenza e derivare nuova conoscenza da quella esistente. Perché la logica proposizionale non è adeguata.
- Nozioni base di logica. Sintassi e semantica della logica proposizionale e della risoluzione. Sintassi e semantica della logica del primo ordine (FO) come linguaggio più expressivo per ragionare sui dati.
- Limiti computazionali della logica del primo ordine. Discussione sull'indecidibilità del ragionamento nella logica del primo ordine. Necessità di formalismi specializzati che possono essere implementati in pratica e che permettono di fare ragionamento su grandi quantità di dati. Il più semplice framework di rappresentazione della conoscenza e ragionamento: i database come conoscenza e le query congiuntive come obiettivo dell'inferenza.
- Complessità dell'inferenza di query congiuntive su database, e limiti dei database semplici come meccanismo di rappresentazione della conoscenza. Introduzione alle basi di conoscenza, un formalismo per codificare conoscenza tramite regole di inferenza per ragionare su grandi quantità di dati.
- Tre modi diversi per fornire semantica alle regole di inferenza: basata su modelli, basata su punto fisso, e basata su prove di derivazione. Equivalenza delle tre le semantiche.
- Implementare il ragionamento con regole di inferenza nella pratica. Gli algoritmi naïve e semi-naïve per il ragionamento basato su punto fisso. Complessità degli algoritmi e complessità intrinseca del ragionamento con regole di inferenza.
- Limiti di espressività delle regole di inferenza. Le basi di conoscenza con regole di inferenza non possono esprimere concetti non monotoni. Introduzione alla sintassi e semantica delle regole di inferenza semi-positive: un formalismo più espressivo. Adattamento delle procedure basate su punto fisso per il ragionamento.
- Estensione delle regole semi-positive con una nozione più flessibile di negazione. Regole di inferenza con negazione stratificata. Equivalenza tra semantica basata su modelli e semantica basata su punto fisso su qualsiasi stratificazione. Le regole stratificate preservano l'efficienza del ragionamento su grandi quantità di dati.
- Oltre la negazione stratificata. Cenno all'indecidibilità del ragionamento con regole di inferenza non stratificate e problematiche concettuali della negazione non stratificata. Introduzione a una nozione di modello più adeguata a scopi pratici: i modelli stabili. L'uso più comune delle regole di inferenza sotto modelli stabili: l'operatore di scelta e il paradigma "guess and verify".
- Ragionamento probabilistico tramite regole di inferenza. Database probabilistici e la semantica dei mondi possibili per le regole di inferenza. Come possiamo calcolare effettivamente l'inferenza probabilistica in pratica?
- Provenance smiring come framework unificante per il ragionamento (probabilistico) su regole di inferenza. Il framework dei semiring e le sue connessioni con il ragionamento su regole di inferenza. Introduzione ai principali semiring: which-provenance, why-provenance e provenance polynomials.
- Combinare regole di inferenza con il Machine Learning. Usare il framework dei semiring come strumento per interfacciare regole di inferenza con modelli di deep learning: panoramica del linguaggio di inferenza Scallop.
- Nozioni base di logica. Sintassi e semantica della logica proposizionale e della risoluzione. Sintassi e semantica della logica del primo ordine (FO) come linguaggio più expressivo per ragionare sui dati.
- Limiti computazionali della logica del primo ordine. Discussione sull'indecidibilità del ragionamento nella logica del primo ordine. Necessità di formalismi specializzati che possono essere implementati in pratica e che permettono di fare ragionamento su grandi quantità di dati. Il più semplice framework di rappresentazione della conoscenza e ragionamento: i database come conoscenza e le query congiuntive come obiettivo dell'inferenza.
- Complessità dell'inferenza di query congiuntive su database, e limiti dei database semplici come meccanismo di rappresentazione della conoscenza. Introduzione alle basi di conoscenza, un formalismo per codificare conoscenza tramite regole di inferenza per ragionare su grandi quantità di dati.
- Tre modi diversi per fornire semantica alle regole di inferenza: basata su modelli, basata su punto fisso, e basata su prove di derivazione. Equivalenza delle tre le semantiche.
- Implementare il ragionamento con regole di inferenza nella pratica. Gli algoritmi naïve e semi-naïve per il ragionamento basato su punto fisso. Complessità degli algoritmi e complessità intrinseca del ragionamento con regole di inferenza.
- Limiti di espressività delle regole di inferenza. Le basi di conoscenza con regole di inferenza non possono esprimere concetti non monotoni. Introduzione alla sintassi e semantica delle regole di inferenza semi-positive: un formalismo più espressivo. Adattamento delle procedure basate su punto fisso per il ragionamento.
- Estensione delle regole semi-positive con una nozione più flessibile di negazione. Regole di inferenza con negazione stratificata. Equivalenza tra semantica basata su modelli e semantica basata su punto fisso su qualsiasi stratificazione. Le regole stratificate preservano l'efficienza del ragionamento su grandi quantità di dati.
- Oltre la negazione stratificata. Cenno all'indecidibilità del ragionamento con regole di inferenza non stratificate e problematiche concettuali della negazione non stratificata. Introduzione a una nozione di modello più adeguata a scopi pratici: i modelli stabili. L'uso più comune delle regole di inferenza sotto modelli stabili: l'operatore di scelta e il paradigma "guess and verify".
- Ragionamento probabilistico tramite regole di inferenza. Database probabilistici e la semantica dei mondi possibili per le regole di inferenza. Come possiamo calcolare effettivamente l'inferenza probabilistica in pratica?
- Provenance smiring come framework unificante per il ragionamento (probabilistico) su regole di inferenza. Il framework dei semiring e le sue connessioni con il ragionamento su regole di inferenza. Introduzione ai principali semiring: which-provenance, why-provenance e provenance polynomials.
- Combinare regole di inferenza con il Machine Learning. Usare il framework dei semiring come strumento per interfacciare regole di inferenza con modelli di deep learning: panoramica del linguaggio di inferenza Scallop.
Prerequisiti
Anche se non strettamente necessario, gli studenti dovrebbero possedere nozioni di base di teoria degli insiemi, di logica, e algoritmi.
Metodi didattici
Il docente utilizzerà principalmente lezioni frontali tramite lavagna per l'esposizione dei concetti teorici, al fine di consentire agli studenti di seguire i concetti espoti al giusto ritmo. Saranno anche discusse diverse esercitazioni al fine di permettere gli studenti di consolidare i concetti acquisiti. Le esercitazioni verranno svolte utilizzando strumenti di knowledge representation and reasoning dello stato dell'arte, quali Clingo/DLV e Scallop.
Materiale di riferimento
- Appunti del corso
- Libri:
- "Logic in Computer Science: Modelling and Reasoning about Systems". Michael Huth and Mark Ryan -- basi di logica proposizionale e logica del primo ordine.
- "Foundations of Databases". Serge Abiteboul, Richard Hull, Victor Vianu -- basi di dati e query congiuntive, e regole di inferenza (con negazione stratificata).
- "Knowledge Representation, Reasoning, and the Design of Intelligent Agents". Michael Gelfond and Yulia Kahl -- modelli stabili e operatore choice, ma menziona anche database e query congiuntive.
- Libri:
- "Logic in Computer Science: Modelling and Reasoning about Systems". Michael Huth and Mark Ryan -- basi di logica proposizionale e logica del primo ordine.
- "Foundations of Databases". Serge Abiteboul, Richard Hull, Victor Vianu -- basi di dati e query congiuntive, e regole di inferenza (con negazione stratificata).
- "Knowledge Representation, Reasoning, and the Design of Intelligent Agents". Michael Gelfond and Yulia Kahl -- modelli stabili e operatore choice, ma menziona anche database e query congiuntive.
Modalità di verifica dell’apprendimento e criteri di valutazione
Gli studenti saranno valutati tramite un esame scritto con domande aperte sugli argomenti del corso. L'obiettivo principale dell'esame è verificare che gli studenti siano in grado di codificare conoscenze espresse in linguaggio naturale utilizzando i formalismi logici presentati durante il corso, che siano capaci di ricostruire le dimostrazioni dei principali risultati teorici trattati e che comprendano i diversi processi di ragionamento richiesti dai formalismi logici. Gli studenti che superano con successo l'esame scritto principale potranno essere sottoposti a un esame orale, a discrezione del docente.
Professor(s)