[RN20]
Paolo Frasconi, DINFO, via di S. Marta 3, 50139 Firenze
email: .
Wednesday, 14:45-16: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 |
|---|---|---|
| 2022-09-19 | Administrivia and covered topics. Agents and environments. Goal-driven agents: problem formulation |
|
| 2022-09-20 | Formulation of a search problem. Search graphs and search trees. General best-first algorithm. |
|
| 2022-10-03 | Analysis of blind search: DFS, BFS, Uniform Cost, Iterative Deepening, Bidirectional. Heuristics. Algorithm A* and conditions for optimality. Dominance and empirical evaluation of heuristics. |
|
| 2022-09-30 | More heuristics and some strategies for improving heuristic search. Local search: Hill climbing, local beam search, simulated annealing. |
|
| 2022-10-10 | Constraint satisfaction problems. Inference for CSPs (constraint propagation): Arc consistency, AC-3 and its analysis. Path-consistency and k-consistency. |
|
| 2022-10-11 | Backtracking search Heuristics for variable and value ordering. Maintaining arc consistency vs. forward checking. Tree problems. Cutset conditioning. |
|
| 2022-10-17 | Dual problems and cluster trees. Construction of junction trees for chordal graphs. Triangulation. Min-conflict solver. Introduction to logic. Formulae. Knowledge bases. |
|
| 2022-10-18 | Syntax and semantics of propositional and first order logic. Entailment |
|
| 2022-10-24 | Constraint modeling with Minizinc. |
|
| 2022-10-24 | Procedures for logical inference. Soundness and completeness. Decidability of propositional logic. |
|
| 2022-10-25 | Conjunctive normal form. Deduction theorem and refutation. Logical equivalences. Inference rules and theorem proving as search. Resolution. # Ground resolution theorem. # Definite and Horn # clauses. Forward and backward chaining. |
|
| 2022-11-07 | Ground resolution theorem. Definite and Horn clauses. Forward and backward chaining. SAT and the DPLL procedure. WalkSAT. |
|
| 2022-11-08 | Random SAT problems. Universal and existential instantiation in first-order logic. Propositionalization. Decidability of first-order logic. Limitations of logic under uncertainty. |
|
| 2022-11-14 | Beliefs, probabilities, and probabilistic reasoning. Updating beliefs from evidence using Bayes' rule. Conditional independence. Directed graphical models (Bayesian networks). |
|
| 2022-11-15 | Semantics of directed graphical models. Examples. Conditional independence entailment. D-separation and conditional independence in directed networks. |
|
| 2022-11-21 | Recap of d-separation. Reparameterization with noisy OR. Markov networks: semantics and u-separation. Markov blankets. Junction trees for probabilistic inference. Initialization. |
|
| 2022-11-21 | The Hugin system for probabilistic reasoning |
|
| 2022-11-22 | Sum and max propagation in junction trees. General ideas for belief propagation in polytrees. Factor graphs. Parameter learning. Recap on maximum likelihood and frequentist parameter estimation. |
|
| 2022-11-28 | Frequentist and bayesian parameter learning. Beta and Dirichlet distribution. Laplace smoothing. |
|
| 2022-11-29 | Structure learning for Bayesian networks. Major machine learning paradigms. Supervised learning. |
|
| 2022-12-03 | Discrimination surface of Naive Bayes. Hyperplanes and the perceptron algorithm. Block-Novikoff theorem. Voted perceptron. Dual form of the perceptron algorithm and very brief introduction to kernels. Multiclass with one-vs-rest and one-vs-all. |
|
| 2022-12-06 | Decision trees for classification. Greedy top-down algorithm. Impurity measures. Bias tradeoff variance. |
|
| 2022-12-12 | Bagging and random forest. Adaboost and its analysis. |
|
| 2022-12-13 | Introduction to Scikit-Learn. |
|
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.