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:4512: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 

20190923  Administrivia. Introduction to Artificial Intelligence. Intelligence and rationality. Some basic theoretical computer science notions. 

20190926  No class today 

20190930  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. 

20191003  Formulation of a search problem. Search graphs and search trees. General structure of the treesearch procedure. 

20191007  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. 

20191010  Heuristics. Greedy best first search. Admissibility and consistency. A*. Optimality of A*. Performance measures. Designing heuristics. Pattern databases. 

20191014  Python practice on blind and heuristic search. 

20191014  Performance measures. Local search. Hill climbing. Beam seach. 

20191017  No class today 

20191021  Simulated annealing. Introduction to constraint programming. Constraint satisfaction problems. Examples. Inference for CSPs (constraint propagation). Node and arc consistency. AC3 and its analysis. 

20191024  Limitations of arcconsistency. Path and kconsistency. Backtracking search. Variable and value ordering. 

20191028  Maintaining arc consistency. Forward checking. Directed arc consistency. Solving tree problems. Cutset conditioning. Dual problems and their networks. 

20191031  Constraint modeling with Minizinc and Numberjack. 

20191104  Junction trees for constraint programs. Logicbased agents. Knowledge bases. Formulae, syntax, semantics. Entailment and logical inference. 

20191107  Propositional logic and propositional theorem proving. Resolution. Conjunctive normal form. 

20191111  Proofs by resolution. Ground resolution theorem. Definite clauses. Forward and backward chaining. SAT and the DPLL procedure. Random SAT problems. 

20191114  Beliefs, probabilities, and probabilistic reasoning. Examples. 

20191118  Patterns of probabilistic reasoning. Updating beliefs from evidence using Bayes' rule. Conditional independence. Examples. 

20191121  Directed graphical models (Bayesian networks). Semantics. Examples. Conditional independence entailment. 

20191125  Dseparation and conditional independence in directed networks. Examples. Introduction to probabilistic inference. 

20191128  Junction trees for probabilistic inference. Maximum likelihood parameter learning (complete and iid data). 

20191202  Bayesian parameter learning. Priors and posteriors. Beta distribution. Bayesian conjugacy. Hyperparameters and pseudocounts. Dirichlet distribution. Structure learning. 

20191205  No class today 

20191209  Supervised learning and the Naive Bayes classifier. Laplace smoothing. Estimating the true error using a test set or crossvalidation. Naive Bayes as a linear classifier. Hyperplanes and the perceptron algorithm. BlockNovikoff theorem. Voted perceptron. 

20191212  Decision trees. Top down induction algorithm. Handling continuous attributes. Pruning. Splitting criteria (Gini, entropy, why classification error does not work). 

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