Università degli Studi di Pavia

Facoltà di Ingegneria

Artificial Intelligence

A.A. 2021-2022

First Semester

Fri: 11:00 a.m. - 1:00 p.m., Room A2

Fri: 2:00 p.m. - 4:00 p.m., Room A1

Lectures & Suggested Readings:

Reports of errors in the resources below are always welcome

1. 2021.10.01 (theory)

   Introduction [pdf]

   Alan Turing (Wikipedia)
   Computer chess (Wikipedia)

   Shannon, C., "Programming a Computer for Playing Chess", Philosophical Magazine, 41 (314), 1950 [pdf]

   BBC2 Horizon, "Out of Control", 2012 [video, on Dailymotion]

   D. Silver, et al., "Mastering the game of Go with deep neural networks and tree search", Nature, 529, 2016 [link]

   "AlphaGo - The Movie | Full Documentary", YouTube, 2020 [video]

2. 2021.10.01 (theory)

   Symbolic reasoning [pdf]
   Language, schemas and reasoning

   Syllogism (ancient logic) (Wikipedia)

3. 2021.10.08 (theory)

   Propositional logic [pdf]
   Boolean algebras, formal propositional language and its semantics, satisfiability, entailment

   Rules of inference, justified by entailment (Wikipedia)

4. 2021.10.15 (theory)

   Entailment and algorithms [pdf]
   Turing machine, decision problems, computational complexity, entailment as a satisfiability problem (i.e. refutation)

5. 2021.10.22 (theory)

   Automated Symbolic Calculus [pdf]
   Semantic tableaux, propositional resolution, soundess and completeness, computational complexity

   Tree Proof Generator [link]: online solver through semantic tableaux

6. 2021.10.29 (theory)

   First-order logic [pdf]
   First-order semantic structures, formal language, variables and quantifiers, satisfaction, entailment

7. 2021.11.05 (theory)

   Semi-decidability of First-Order logic [pdf]
   Prenex normal form, skolemization, Herbrand's theorem

   Prenex normal form (Wikipedia)

   First-Order resolution [pdf]
   Clausal form, unification, resolution method for first-order logic

8. 2021.11.12 (theory)

   SLD resolution [pdf]
   Horn clauses, SLD resolution, logic programming

   Depth-first search (Wikipedia)
   Breadth-first search (Wikipedia)

   Minimal Models [pdf]
   Horn clauses, Herbrand model, implicit database

9. 2021.11.19 (theory)

   Plausible reasoning [pdf]
   Negation as failure, closed world assumption, deductive, inductive and abductive reasoning

   Probabilitistic reasoning: representation and inference [pdf]
   Foundations of probability, probability space, random variables, Bayes' theorem, probabilistic inference

   Countable set (Wikipedia)
   Sigma algebra (Wikipedia - see simple set-based examples)
   Probability space (Wikipedia)
   Random variable (Wikipedia)

   "The Banach-Tarski Paradox" (semi-serious but also very informative), YouTube, 2015 [video]

10. 2021.11.26 (theory)

    Graphical models [pdf]
    Graphical models and factorization, d-separation, inference, computational methods

    Examples with "Bayes" (free software) available on AISpace
    [download] (see Belief and Decision Networks)

11. 2021.12.03 (theory)

    Supervised learning [pdf]
    Learning proababilities from observations: maximum likelihood estimator, maximum a posteriori probability, conjugate prior distribution

    Binomial distribution (Wikipedia)
    Beta distribution (Wikipedia)
    Conjugate prior (Wikipedia)

    Beta distribution interactive plot [link]

12. 2020.12.03 (theory)

    Numerical supervised learning [pdf]
    Learning with models that cannot be optimized analytically, logistic regression, gradient descent, stochastic gradient descent, mini-batch gradient descent

    Logistic regression (Wikipedia)

13. 2021.12.17 (theory)

    Unsupervised learning [pdf]
    Learning from incomplete observations: k-means, hidden random variables, EM algorithm, observability model

    k-means (a.k.a. LBG) algorithm - online demo [link]

    Voronoi tesselation with Lloyd relaxation - online demo [link]

    Expected Maximization in python (Colab Notebook) [link]

    Andrew Ng, "The EM algorithm", CS229 Lecture notes, Stanford [pdf]

14. 2022.01.14 (theory)

    Causal Models [pdf]
    Causal Graphical Models, potential outcomes, do-calculus, adjustment set

    Judea Pearl, An Introduction to Causal Inference, Int J Biostat. 2010 Jan 6; 6(2): 7 [link]

    Pearl, J., Glymour, M., Jewell, Causal Inference in Statistics: A Primer [link]
    (at this time, an online version of the book is freely available at the above link)

15. 2022.01.21 (theory)

    Reinforcement learning [pdf]
    Multi-armed bandits and methods, Thompson sampling, Markov Decision Processes, value function, optimal policy, iterative learning algorithms

    Shannon Entropy (Wikipedia)
    Kullback-Leibler divergence (Wikipedia)

    Reinforcement Learning Simulator: a demo for the maze example implemented in Java [link]

    ConvnetJS: Deep Q Learning Demo [link]

    Sutton, R.S., Barto, A.G., Reinforcement Learning: An Introduction, 2nd Edition (draft) [link]
    (at this time, the draft is freely available at the above link)

Instructor

1. Marco Piastra

2. Contact: marco.piastra@unipv.it

Kiro

1. Course info

Exams

1. See Faculty website

Further resources:

(There are no required textbooks for this course. The following books are recommended as optional readings)

1. Mordechai Ben-Ari, Mathematical Logic for Computer Science (3rd Edition). Springer, 2012

2. Kevin P. Murphy, Machine Learning: A Probabilistic Perspective, MIT Press, 2012.

Links

1. Artificial Intelligence Reading Group

1. Artificial Intelligence, A.A. 2020-2021 and before