[RN20]
Paolo Frasconi, DINFO, via di S. Marta 3, 50139 Firenze
email: .
Tuesday Monday 10:45-12:45.
The course will introduce problems and basic algorithmic techiques in the following areas:
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.
B003368 (Algorithms and Data Structures)
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.
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 |
|---|---|---|
| 2024-09-17 | Administrivia. Main topics in current AI and what will be covered in this course. |
|
| 2024-09-19 | Search problems. States, actions, costs. Search graph. Search tree. General best-first algorithm. Blind search algorithms: DFS, BFS, Uniform Cost. Iterative deepening. Bidirectional search. Analysis. |
|
| 2024-09-24 | Heuristics. Algorithm A* and conditions for optimality. Dominance and empirical evaluation of heuristics. Pattern databases. |
|
| 2024-09-26 | Beam search. Searching and optimizing goal states. Metaheuristics for local search: Hill climbing, local beam search, simulated annealing. |
|
| 2024-10-01 | Evolutionary algorithms. Constraint satisfaction problems. Inference for CSPs (constraint propagation): Arc consistency, AC-3 and its analysis. |
|
| 2024-10-03 | Backtracking search. Heuristics for variable and value ordering. Inference during backtracking: maintaining arc consistency and forward checking. |
|
| 2024-10-08 | Cutset conditioning. Dual problems and cluster trees. Junction trees and triangulated graphs. Cliques in triangulated graphs. Triangulation via variable elimination. |
|
| 2024-10-10 | Constraint modeling with Minizinc and CPMpy. |
|
| 2024-10-10 | Introduction to logic. Formulae. Syntax, semantics, interpretations |
|
| 2024-10-15 | Ontological and epistemological committments of a logic. Semantics. Interpretation functions. Entailment. Semantics of propositional logic. Propositional formulae. Valid and satisfiable formulae. Logical equivalence. Deduction theorem. Decidability of propositional logic. |
|
| 2024-10-17 | Theorem proving. Inference rules and theorem proving as search. Soundness and completeness. Conjunctive normal form. Resolution. Ground resolution theorem. Reduction of entailment to SAT. Introduction to SAT solving. |
|
| 2024-10-22 | Proof of the ground resolution theorem. Reduction of entailment and CSP to SAT. The DPLL algorithm. WalkSAT. |
|
| 2024-10-24 | Randomized k-SAT and phase transition. # Definite and Horn clauses. # Forward and backward chaining. Limitations of logic under uncertainty. Probabilities, distributions, beliefs. Marginalization and chain rule. |
|
| 2024-10-29 | Probability distributions over several variables. Parameterization of discrete distributions. Independence and conditional independence. Directed probabilistic graphical models. Factorization of joint distributions according to a directed graph. Conditional probability tables. |
|
| 2024-10-31 | Conditional independence entailment. D-separation and conditional independence in directed networks. I-maps and D-maps. Limitations of Bayesian networks. Undirected graphical models. U-separation. |
|
| 2024-11-05 | Markov networks. Compatibility functions. Markov blankets. Hammersley-Clifford theorem. Markov chains. Language models. Hidden Markov models. |
|
| 2024-11-07 | Algorithmic problems for graphical models. Sampling from a Bayesian network. Junction trees for probabilistic inference. Initialization, message passing, inserting evidence. Construction of junction trees for probabilistic inference: moralization. Max propagation vs. sum propagation. |
|
| 2023-11-12 | No class today. Also: office hours moved to Friday Nov 15, 14:15-16:15 |
|
| 2024-11-14 | Parameter learning in graphical models. Problem setup and assumptions. Maximum likelihood estimation. Frequentist and bayesian parameter learning. Beta distribution. |
|
| 2024-11-19 | Bayesian conjugacy. Laplace smoothing. Dirichlet priors. Structure learning for Bayesian networks. Naive Bayes. |
|
| 2024-11-21 | Supervised learning. Examples. Empirical risk minimization. Train and test error. NB as a supervised learning algorithm. Discrimination surface of Naive Bayes. Hyperplanes and the perceptron algorithm. Block-Novikoff theorem. |
|
| 2024-11-26 | Voted perceptron. Dual form of the perceptron algorithm. Decision trees for classification. Greedy top-down algorithm. Impurity measures. Hyperparameters. |
|
| 2024-12-03 | The decision tree hypothesis space. Decision trees with continuous attributes. Bias-variance tradeoff. Bagging. Random forests. |
|
| 2024-12-10 | Bias-variance tradeoff. Bagging. Random forests. Adaboost and its analysis. Learning decision stumps. |
|
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.