91251 - Languages and Algorithms for Artificial Intelligence

Learning outcomes

At the end of the course, the student has an understanding of the main linguistic and algorithmic techniques used in the context of AI, including the main aspects related to functional, logic and constraint programming, with their theoretical foundations and practical applications. The student has an understanding of the basic principles of distributed models and algorithms, consensus problems, and large-scale algorithms for the analysis of big data.

Course contents

Module 1

Introduction to mathematical logic. Unification. Resolution.
Introduction to logic programming. Prolog languages.
Constraint logic programming and concurrent constraint programming. Constraint programming. The language MiniZinc.

Module 2

Programming and learning paradigm, and the languages for inference. Introduction to the language Scheme/Racket and its probabilistic extensions Church/Gamble. Generative models as probabilistic programs. Bayesian programming in Church/Gamble. Learning as conditional inference. Inference algorithms (rejection sampling and Metropolis Hastings). Operational semantics and inference by evaluation. Time permitting, an overview of differentiable programming.

Module 3

Rudiments of Computability and Complexity Theory. Undecidability, polynomial time computability, and NP-completeness. Between the feasible and the unfeasible. A Formal Learning Model: PAC Learning. Learning via Uniform Convergence. The Bias-Complexity Tradeoff.
The VC-Dimension.

Readings/Bibliography

Module 1

Dirk van Dalen. Logic and structure. 4th edition, Springer.

K. Doets. From Logic to Logic Programming. The Mit

Press.Russell, Norvig. Artificial Intelligence: A Modern Approach (any edition). Pearson.

Module 2

N. D. Goodman, J. B. Tenenbaum, and The ProbMods Contributors (2016). Probabilistic Models of Cognition (1st ed.). (available at http://v1.probmods.org/index.html)

Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, Frank Wood, An introduction to probabilistic programming (available at https://arxiv.org/abs/1809.10756).

Module 3

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

Michael Kearns, Umesh. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.

Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

Teaching methods

Theoretical and practical class lectures.

Assessment methods

Written and/or oral examinations at the end of each module.
Possible project work.

Teaching tools

Lectures. Practical exercises.

Office hours

See the website of Ugo Dal Lago

See the website of Maurizio Gabbrielli

See the website of Francesco Gavazzo