B003725 - Artificial Intelligence. Fall 2023

Instructor

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

email: .

Office Hours

Monday, 10:45-12:45.

Description

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

Learning objectives

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 based on a short discussion during office hours. It would often take several iterations by email so please do not ask the project by email. You have some freedom in choosing the area and the modality of your project but not in choosing the exact problem. 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. Your should be ready to answer practical and theoretical questions about your project during the oral exam.

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

Schedule and reading materials

Relevant sections of the textbook(s) are listed on the right side. You are expected to study these sections thoroughly and be able to discuss their contents during the exam. The listed additional materials (usually papers) are to be studied only when marked as "required" (unless they are relevant to your project work, then you need to study them thoroughly).

Date	Topics	Readings/Handouts
2023-09-18	What is AI? Agents, environments, rationality. Goal-driven agents: problem formulation. Search graphs.	RN20 1, 2.1-2.4, 3.1-3.2 Optional additional readings: (McCarthy 2007); (Gershman et al. 2015);
2023-09-20	Search trees. General best-first algorithm. Blind search algorithms: DFS, BFS, Uniform Cost. Analysis.	RN20 3.1-3.3 Optional additional readings: (Felner, 2011);
2023-09-25	Iterative Deepening. Bidirectional search. Heuristics. Algorithm A* and conditions for optimality. Dominance and empirical evaluation of heuristics. Pattern databases.	RN20 3.4, 3.5.1-3.5.3, 3.6.1, 3.6.2. Optional: RN20 3.5.4-3.5.6 Required additional readings: (Korf, 1985); (Korf & Felner 2002); Optional additional readings: (Felner, 2011); (Hansson et al. 1992);
2023-09-27	More on designing heuristics. Beam search. Local search: Hill climbing, local beam search, simulated annealing.	RN20 3.6, 4.1 Optional additional readings: (Kirkpatrick et al. 1983);
2023-10-2	Constraint satisfaction problems. Inference for CSPs (constraint propagation): Arc consistency, AC-3 and its analysis.	RN20 6.1, 6.2
2023-10-4	Path-consistency and k-consistency. Backtracking search. Heuristics for variable and value ordering.	RN20 6.3 Required additional readings: (van Beek, 2006); Optional additional readings: (Wallace, 1993);
2023-10-09	Inference during backtracking: maintaining arc consistency and forward checking. Solving tree problems. Cutset conditioning. Dual problems and cluster trees. Construction of junction trees for triangulated graphs.	RN20 6.5, 6.4, 7.1 Required additional readings: (Dechter, 2006);
2023-10-11	Cliques in triangulated graphs. Triangulation via variable elimination. Recup of the junction tree solver.	Required additional readings: (Dechter, 2006);
2023-10-11	Constraint modeling with Minizinc and CPMpy.	Required additional readings: (Marriott et al, 2014); Optional additional readings: (Guns 2019); Online resources: Minizinc website; CPMpy website; Source code;
2023-10-16	No class today
2023-10-18	Introduction to logic. Formulae. Knowledge bases. Syntax and semantics of propositional and first order logic. Entailment. Decidability of propositional logic.	RN20 7.3, 7.4, 8.1, 8.2
2023-10-23	Valid and satisfiable formulae. Logical equivalence. Conjunctive normal form. Reduction of entailment and CSP to SAT. DPLL algorithm. Randomized k-SAT and phase transition. WalkSAT.	RN20 7.5, 7.6 Optional additional readings: (Hoos & Stützle, 2005);
2023-10-25	Theorem proving. Inference rules and theorem proving as search. Soundness and completeness. Resolution. Ground resolution theorem. Definite and Horn clauses. Forward and backward chaining.	RN20 7.5
2023-10-30	Limitations of logic under uncertainty. Probabilities, distributions, beliefs. Patterns of probabilistic reasoning. Updating beliefs from evidence using Bayes' rule. Conditional independence. Introduction to graphical models.	RN20 12.1-12-5; B12 1., 3.1
2023-11-01	No class today
2023-11-06	Markov networks. Compatibility functions. Examples. I-maps and D-maps. Hammersley-Clifford theorem. Limitations of undirected networks. Directed graphical models. Examples.	RN20 13.2, B12 4.1, 4.2.
2023-11-08	Conditional independence entailment. D-separation and conditional independence in directed networks. Conditional probability tables. Examples.	RN20 13.2 (except 13.2.3); B12 3.1, 4.2, 4.5, 6.1 Optional: B12 23
2023-11-13	Junction trees for probabilistic inference. Initialization, message passing, inserting evidence. Construction of junction trees for probabilistic inference: moralization. Introduction to hidden Markov models for part-of-speech tagging.	RN20 13.3.4, 14.1, 14.3, 23.1.6; B12 6, 23.2, 23.5.1 Required additional readings: (Jensen, 1997) - pw to unzip ai23; Optional additional readings: (Huang & Darwiche, 1996);
2023-11-15	The Hugin system for probabilistic reasoning	Online resources: Hugin expert website;
2023-11-15	Markov blankets. Max propagation vs. sum propagation. The Viterbi algorithm for the decoding problem in HMMs. Parameter learning in graphical models. Maximum likelihood estimation.	RN20 14.2.3, 20.1, 20.2.1; B12 23.2. Optional additional readings: (Aji & McEliece, 2000);
2023-11-20	No class today
2023-11-22	Frequentist and bayesian parameter learning. The problem with incomplete data. Beta distribution. Laplace smoothing.	RN20 20.1, 20.2, (optional 20.3); D17 9. Required additional readings: (Heckerman, 1999);
2023-11-27	Dirichlet priors. Structure learning for Bayesian networks. Naive Bayes and its discrimination surface. Supervised learning	RN20 20.2.5, 20.2.7, 20.2.2 Required additional readings: (Heckerman, 1999); (McCallum & Nigam 1998);
2023-11-29	Supervised learning. Empirical risk minimization. Loss functions. Hyperplanes and the perceptron algorithm. Block-Novikoff theorem. Voted perceptron. Dual form of the perceptron algorithm.	RN20 19.1, 19.2, 19.4.2 Required additional readings: (Cristianini & Shawe-Taylor, 2000) - pw to unzip ai19; (Freund & Schapire 1999); Optional additional readings: (Jordan & Mitchell, 2015);
2023-12-04	Decision trees for classification. Greedy top-down algorithm. Impurity measures. Hyperparameters. Bias-variance tradeoff. Bagging. Random forests.	RN20 19.3, 19.4, 19.8.1, 19.8.2 Required additional readings: (Mitchell 1997) - pw to unzip ai19; (Breiman 2001);
2023-12-06	Adaboost and its analysis. Learning decision stumps.	RN20 19.8 Required additional readings: (Freund et al. 1999); Optional additional readings: (Freund & Schapire 1997);
2023-12-13	Introduction to Scikit-Learn.	Required additional readings: (Pedregosa et al. 2011); Online resources: Scikit-learn website; Weka website; Jupyter notebooks;

Note

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