Knowledge representation and reasoning
A.A. 2026/2027
Obiettivi formativi
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.
Risultati apprendimento attesi
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 può essere seguito come corso singolo.
Programma e organizzazione didattica
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ù espressivo.
- 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 alla negazione e potere espressivo.
- Introduzione alle basi di conoscenza, un formalismo per codificare conoscenza tramite regole di inferenza per ragionare su grandi quantità di dati.
- Implementare il ragionamento con regole di inferenza nella pratica. Gli algoritmi naïve e semi-naïve per il ragionamento. Complessità degli algoritmi e complessità intrinseca del ragionamento con regole di inferenza.
- Rendere più efficiente l'inferenza su basi di conoscenza: la tecnica del magic-set rewriting.
- 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. Le regole stratificate preservano l'efficienza del ragionamento su grandi quantità di dati.
- Confronto del potere espressivo dei formalismi di basi di conoscenza e i formalismi precedenti.
- Cenni su ragionamento probabilistico tramite regole di inferenza, approcci neurosimbolicili.
- 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ù espressivo.
- 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 alla negazione e potere espressivo.
- Introduzione alle basi di conoscenza, un formalismo per codificare conoscenza tramite regole di inferenza per ragionare su grandi quantità di dati.
- Implementare il ragionamento con regole di inferenza nella pratica. Gli algoritmi naïve e semi-naïve per il ragionamento. Complessità degli algoritmi e complessità intrinseca del ragionamento con regole di inferenza.
- Rendere più efficiente l'inferenza su basi di conoscenza: la tecnica del magic-set rewriting.
- 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. Le regole stratificate preservano l'efficienza del ragionamento su grandi quantità di dati.
- Confronto del potere espressivo dei formalismi di basi di conoscenza e i formalismi precedenti.
- Cenni su ragionamento probabilistico tramite regole di inferenza, approcci neurosimbolicili.
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 agli 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 (non obbligatori, ma a integrazione degli Appunti del corso):
- Brachman, R. J., & Levesque, H. J. (2004). Knowledge Representation and Reasoning. Morgan Kaufmann. ISBN: 978-1-55860-932-7, DOI: https://doi.org/10.1016/B978-1-55860-932-7.X5083-3.
- Genesereth, M. R., & Kao, E. (2017). Introduction to Logic (3nd ed.). Stanford University. ISBN: 978-3-031-01801-5, DOI: https://doi.org/10.1007/978-3-031-01801-5.
- Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of Databases. Addison-Wesley. ISBN: 0-201-53771-0.
- Greco, S., & Molinaro, C. (2016). Datalog and Logic Databases. Springer. ISBN: 978-3-031-01854-1, DOI: https://doi.org/10.1007/978-3-031-01854-1.
- Libri (non obbligatori, ma a integrazione degli Appunti del corso):
- Brachman, R. J., & Levesque, H. J. (2004). Knowledge Representation and Reasoning. Morgan Kaufmann. ISBN: 978-1-55860-932-7, DOI: https://doi.org/10.1016/B978-1-55860-932-7.X5083-3.
- Genesereth, M. R., & Kao, E. (2017). Introduction to Logic (3nd ed.). Stanford University. ISBN: 978-3-031-01801-5, DOI: https://doi.org/10.1007/978-3-031-01801-5.
- Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of Databases. Addison-Wesley. ISBN: 0-201-53771-0.
- Greco, S., & Molinaro, C. (2016). Datalog and Logic Databases. Springer. ISBN: 978-3-031-01854-1, DOI: https://doi.org/10.1007/978-3-031-01854-1.
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.
INFO-01/A - Informatica - CFU: 6
Lezioni: 48 ore
Docente:
Calautti Marco
Turni:
Turno
Docente:
Calautti MarcoDocente/i