B003725 - Artificial Intelligence - Fall 2021

Contacts

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

email: .

Office Hours

Wednesday, 10:45-12:45.

Until further notice, it will be via telco. Please on the day before and I will reply with a tentative meeting time.

Learning Objectives

The course will introduce problems and basic algorithmic techiques in the following areas:

• Classic/symbolic AI: agents, searching, constraints, logic
• Probabilistic AI: probabilistic reasoning and graphical models
• Machine learning: Fundamentals of supervised learning algorithms

You will be able to design and apply simple searching agents, solvers for constraint satisfaction problems, understand and apply simple probabilistic models and solve basic data-driven classification problems. The course will serve as a foundation for further study in AI as well as in engineering areas where AI is becoming predominant.

Prerequisites

B003368 (Algorithms and Data Structures)

Suggested readings

Textbook

Other texts

Assessment

There is a final project and a final oral exam.

The final project will be assigned by the teacher based on a short discussion with the student during office hours. The project typically consists the 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 practical and theoretical 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

For videos please go to the Moodle-WebEx connector (UniFI credentials required).

Date	Topics	Readings/Handouts
2021-09-22	Administrivia. Introduction to Artificial Intelligence. Agents, environments, percepts, actions. Rational agents.	RN21 1, 2.1-2.4 Gershman, S. J., Horvitz, E. J., and Tenenbaum, J. B. (2015). Computational rationality, A converging paradigm for intelligence in brains, minds, and machines. Science, 349(6245), 273-278. J. McCarthy (2007) What is Artificial Intelligence?
2021-09-23	Formulation of a search problem. Search graphs and search trees. General structure of the search procedure. General best-first algorithm. Completeness and optimality.	RN21 3.1-3.3
2021-09-29	Blind search: DFS, BFS, Uniform Cost, Iterative Deepening, Bidirectional. Comparisons. Heuristics. Greedy best first search. Admissibility and consistency. A*. Optimality of A*. Designing heuristics. Dominance.	RN21 3.4.5-3.4.7, 3.5 A. Felner (2011). Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm, in Proc. 4th Int. Symp. on Combinatorial Search (SoCS-2011), pp. 47--51. "R.E. Korf Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence, 27(1):97--109, 1985."
2021-09-30	Linear conflicts. Pattern databases. Performance measures, effective branching factor. Local search. Hill climbing. Beam search. Simulated annealing	RN21 3.6, 4.1 Hansson, O., Mayer, A., & Yung, M. (1992). Criticizing solutions to relaxed models yields powerful admissible heuristics. Information Sciences, 63(3), 207-227. (This paper introduces the linear conflicts heuristic for the 15-puzzle) Korf, R. E., & Felner, A. (2002). Disjoint pattern database heuristics. Artificial Intelligence, 134(1-2), 9-22. Kirkpatrick, Scott, C. Daniel Gelatt, and Mario P. Vecchi. Optimization by simulated annealing. Science 220.4598 (1983): 671-680.
2021-10-06	Constraint satisfaction problems. Examples. Backtracking search. Inference for CSPs (constraint propagation). Arc consistency, AC-3 and its analysis.	RN21 6.1, 6.2, 6.3 Wallace, R. J. (1993). Why AC-3 is almost always better than AC-4 for establishing arc consistency in CSPs. In IJCAI (Vol. 93, pp. 239–245).
2021-10-07	Path-consistency and k-consistency. Heuristics for variable and value ordering. Maintaining arc consistency vs. forward checking. Complexity. Tree problems. Cutset conditioning. Introduction to clustering.	RN21 6.2-6.5 P. van Beek. Backtracking Search Algorithms. In F. Rossi, P. van Beek and T. Walsh (Eds.) Handbook of Constraint Programming, 2006.
2021-10-13	Triangulation of graphs. Construction of junction trees for constraint satisfaction. Constraint modeling with Minizinc.	RN21 6.4, 7.1 R. Dechter. Tractable Structures for Constraint satisfaction problems. In F. Rossi, P. van Beek and T. Walsh (Eds.) Handbook of Constraint Programming, 2006. Minizinc website Marriott, K., Stuckey, P. J., Koninck, L. D., & Samulowitz, H. (2014). A minizinc tutorial.
2021-10-14	Introduction to logic. Formulae, syntax, semantics. Syntax and semantics of propositional and first order logic. Entailment.	RN21 7.1-7.3, 7.4.1, 7.4.2, 8.1, 8.1.1, 8.1.2
2021-10-20	Procedures for logical inference. Soundness and completeness. Decidability of propositional logic. Deduction theorem and refutation. Logical equivalences. Conjunctive normal form. SAT and the DPLL procedure. WalkSAT. Random SAT problems.	RN21 7.4, 7.6
2021-10-21	Theorem proving. Resolution. Ground resolution theorem. Definite and Horn clauses. Forward and backward chaining.	RN21 7.5
2021-10-28	Beliefs, probabilities, and probabilistic reasoning. Updating beliefs from evidence using Bayes' rule. Conditional independence.	RN21 ch. 12.1-12-5, B12 ch. 1
2021-11-04	Directed graphical models (Bayesian networks). Semantics. Examples. Conditional independence entailment. D-separation and conditional independence in directed networks.	RN21 14.1, 14.2, B12 3.3 Hugin expert website
2021-11-10	D-separation (cont.). Limitations of D-separation. Markov networks. Inference in directed networks. Junction trees for probabilistic inference.	RN21 14.4.4., B12 6. F. Jensen. Introduction to Bayesian Networks (1997), Ch. 4
2021-11-18	Hugin propagation. Frequentist parameter learning and Laplace smoothing. Supervised learning. Naive Bayes as a graphical model. The supervised learning problem.	RN21 20.1, 20.2.1, 20.2.2, 19.2 Heckerman, D. (1999). A Tutorial on Learning With Bayesian Networks. In Learning in Graphical Models, M. Jordan, ed., MIT Press, Cambridge, MA. Revised Feb 2020. McCallum, A. & Nigam, K., (1998). A comparison of event models for naive Bayes text classification. In AAAI-98 workshop on learning for text categorization (Vol. 752, pp. 41-48).
2021-11-25	Hyperplanes and the perceptron algorithm. Block-Novikoff theorem. Voted perceptron. Dual form of the perceptron algorithm,	RN21 18.1, 18.2, 18.6.3, 18.7.2; D17 4. Cristianini, N., and Shawe-Taylor, J. An introduction to support vector machines and other kernel-based learning methods. Cambridge university press, 2000. Ch. 2 Freund, Y., & Schapire, R. E. (1999). Large margin classification using the perceptron algorithm. Machine Learning, 37(3), 277–296.
2021-12-02	Multi-layered perceptron. Expressiveness. Response functions. Losses. Stochastic gradient descent. Gradient computation for linear networks.	RN21 19.6, 21.1, 21.2
2021-12-09	Backpropagation and stochastic gradient descent for multilayered networks. Introduction to Adaboost.	RN21 21.1, 21.4, 19.8.4 Freund, Y., Schapire, R., & Abe, N. (1999). A short introduction to boosting. Journal-Japanese Society For Artificial Intelligence, 14(771–780), 1612.
2021-12-16	Analysis of AdaBoost. Decision trees. Greedy top-down construction of decision trees. Random forests.	RN21 19.3, 19.8 Freund, Y., & Schapire, R. E. (1997). A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), 119–139. Mitchell, T. (1997). Machine Learning. McGraw-Hill. Chapter 3: Decision Trees (on Moodle).

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.