B003725 - Artificial Intelligence - Fall 2019

Bachelor degree in Computer Engineering, University of Florence


Contacts

Paolo Frasconi, DINFO, via di S. Marta 3, 50139 Firenze

email: (please do not use my address @unifi.it, it was forcibly moved to gmail by the central administration and it has all sorts of problems: messages may be replied with delay or not replied at all)

Office Hours

Tuesday, 10:45-12:45

Please do not email me about office hours, just check the School of Engineering Website for (unlikely) changes


Learning Objectives

You will learn about the basic concepts and the main research areas of AI. Broad topics that are covered include: searching, constraint programming, logic, probabilistic reasoning, and machine learning.

Prerequisites

B003368 (Algorithms and Data Structures)

Suggested readings

Textbooks

[RN10]
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. 3rd edition. Pearson, 2010.
[B12]
D. Barber. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012.

Other texts

[HTF09]
T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Data Mining, Inference, and Prediction. 2nd edition. Springer, 2009.
[PM17]
David L. Poole, Alan K. Mackworth. Artificial Intelligence: Foundations of Computational Agents. 2nd edition. Cambridge University Press, 2017.
[D03]
Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003.
[J97]
F. Jensen. Introduction to Bayesian Networks, 1997

Assessment

There is a final project and a final oral exam.

The final project will be assigned by the teacher on one of the main topics of the course (Learning, Searching, Constraints, Logic programming, Graphical Models). The topic will be decided discussing with the student. The project typically consists of modeling or application of AI techniques to simple real problems, or it could involve the implementation and the verification of algorithmic techniques described in the course. Students should be ready to answer questions about their project during the oral exam.

The oral exam covers the rest of the course. During the exam, students should prove they can master both theoretically and practically the methods and the algorithmic techniques described in the course.

Schedule and reading materials

Date Topics Readings/Handouts
2019-09-23 Administrivia. Introduction to Artificial Intelligence. Intelligence and rationality. Some basic theoretical computer science notions.
  • RN10 1
2019-09-26 No class today
2019-09-30 Agents, percepts and actions. The agent function. Rational agents. Environment types (discrete, static, deterministic, etc.). Examples. Structure of agents. Reflex agents. Using a model. Goal based agents. Examples of search problems.
  • RN10 2.1-2.4, 3.1
2019-10-03 Formulation of a search problem. Search graphs and search trees. General structure of the tree-search procedure.
  • RN10 3.1, 3.2, 3.3
2019-10-07 Blind search. DFS, BFS, Uniform Cost Search, Iterative Deepening, Bidirectional Search. Proof of optimality for UCS. Analysis in terms of completeness, optimality, running time, and space.
  • RN10 3.3, 3.4
2019-10-10 Heuristics. Greedy best first search. Admissibility and consistency. A*. Optimality of A*. Performance measures. Designing heuristics. Pattern databases.
  • RN10 3.5, 3.6
2019-10-14 Python practice on blind and heuristic search.
2019-10-14 Performance measures. Local search. Hill climbing. Beam seach.
  • 4.1.1, 4.1.3
2019-10-17 No class today
2019-10-21 Simulated annealing. Introduction to constraint programming. Constraint satisfaction problems. Examples. Inference for CSPs (constraint propagation). Node and arc consistency. AC-3 and its analysis.
  • RN10 4.1.2, 6.1, 6.2.
2019-10-24 Limitations of arc-consistency. Path and k-consistency. Backtracking search. Variable and value ordering.
  • RN10 6.2, 6.3
2019-10-28 Maintaining arc consistency. Forward checking. Directed arc consistency. Solving tree problems. Cutset conditioning. Dual problems and their networks.
  • RN10 6.5
2019-10-31 Constraint modeling with Minizinc and Numberjack.
2019-11-04 Junction trees for constraint programs. Logic-based agents. Knowledge bases. Formulae, syntax, semantics. Entailment and logical inference.
  • RN10 6.5, 7.1-7.3
2019-11-07 Propositional logic and propositional theorem proving. Resolution. Conjunctive normal form.
  • RN10 7.4, 7.5.1
2019-11-11 Proofs by resolution. Ground resolution theorem. Definite clauses. Forward and backward chaining. SAT and the DPLL procedure. Random SAT problems.
  • RN10 7.5.2, 7.5.3, 7.5.4, 7.6
2019-11-14 Beliefs, probabilities, and probabilistic reasoning. Examples.
  • RN10 ch. 13.1-13-3, B12 ch. 1
2019-11-18 Patterns of probabilistic reasoning. Updating beliefs from evidence using Bayes' rule. Conditional independence. Examples.
  • RN10 13.4-13.6, B12 chapter 1
2019-11-21 Directed graphical models (Bayesian networks). Semantics. Examples. Conditional independence entailment.
  • RN10 14.1, 14.2, B12 3.1, 3.2, 3.3
2019-11-25 D-separation and conditional independence in directed networks. Examples. Introduction to probabilistic inference.
  • RN10 14.2, 14.3, 14.4.1, B12 3.3, 4.5
2019-11-28 Junction trees for probabilistic inference. Maximum likelihood parameter learning (complete and iid data).
  • RN10 14.4.4., 20.2.1. B12 6.
2019-12-02 Bayesian parameter learning. Priors and posteriors. Beta distribution. Bayesian conjugacy. Hyperparameters and pseudo-counts. Dirichlet distribution. Structure learning.
  • RN10 20.2.4, 20.2.5; B12 9.4, 9.5
2019-12-05 No class today
2019-12-09 Supervised learning and the Naive Bayes classifier. Laplace smoothing. Estimating the true error using a test set or cross-validation. Naive Bayes as a linear classifier. Hyperplanes and the perceptron algorithm. Block-Novikoff theorem. Voted perceptron.
  • RN10 18.1, 18.2, 18.6.3, 18.7.2, 20.2.2
2019-12-12 Decision trees. Top down induction algorithm. Handling continuous attributes. Pruning. Splitting criteria (Gini, entropy, why classification error does not work).
  • RN10 18.3

Note

Full text of linked papers is normally accessible when connecting from a UNIFI IP address. Use the proxy proxy-auth.unifi.it:8888 (with your credentals) if you are connecting from outside the campus network.