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).
Tuesday, 10:4512:45
Until further notice, it will be on Skype. Please with your Skype ID on the day before and I will reply with a tentative meeting time.
This course introduces some basic concepts in AI and covers four main topics:
B003368 (Algorithms and Data Structures)
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 (Searching, Constraints, Logic programming, Graphical Models, Learning). The topic will be decided discussing with the student during office hours. 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.
For videos please go to the MoodleWebEx connector (UniFI credentials required).
Date  Topics  Readings/Handouts 

20200921  Administrivia. Introduction to Artificial Intelligence. Intelligence and rationality. Basic notions of theoretical computer science: decidability and NPcompleteness. 

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

20200928  Formulation of a search problem. Search graphs and search trees. General structure of the search procedure. Main algorithms: DFS, BFS, Uniform Cost (completeness, optimality, time and space analysis). Introduction to iterative Deepening. 

20201001  More blind search: details on Iterative Deepening, Bidirectional Search. Comparisons. Heuristics. Greedy best first search. Admissibility and consistency. A*. Optimality of A*. 

20201005  Designing heuristics. Dominance. Linear conflicts. Pattern databases. Performance measures, effective branching factor. Local search. Hill climbing. Beam search. 

20201008  Python practice on blind and heuristic search (code is on Moodle). 

20201008  More on local search. Simulated annealing. 

20201012  No class today 

20201015  Constraint satisfaction problems. Examples. Inference for CSPs (constraint propagation). Node and arc consistency. AC3 and its analysis. Limitations of arcconsistency. Path and kconsistency. Introduction to backtracking search. 

20201019  Backtracking search. Variable and value ordering. Maintaining arc consistency. Forward checking. Solving tree problems. Cutset conditioning. Dual problems and their networks. Junction trees. 

20201022  Triangulation of graphs. Minconflicts. Introduction to logical agents. 

20201022  Constraint modeling with Minizinc. 

20201026  Knowledge bases. Formulae, syntax, semantics. Entailment and logical inference. Propositional theorem proving. Inference rules. Resolution. 

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

20201102  Beliefs, probabilities, and probabilistic reasoning. Updating beliefs from evidence using Bayes' rule. Conditional independence. Examples. 

20201105  Directed graphical models (Bayesian networks). Semantics. Examples. Conditional independence entailment. Dseparation and conditional independence in directed networks. 

20201109  Limitations of Dseparation. Markov networks. Inference in directed networks. Junction trees for probabilistic inference. 

20201112  Frequentist and bayesian parameter learning. Priors and posteriors. Beta distribution. 

20201116  No class today 

20201119  More Bayesian conjugates: Dirichlet distribution. Hyperparameters and pseudocounts. Parameter learning for directed models in the complete data case. Structure learning. Naive Bayes classifier. 

20201123  Laplace smoothing for Naive Bayes. Multinomial Naive Bayes. Some performance measures for binary classification: Accuracy, Precision, Recall, Breakeven point. General formulation of the supervised learning problem. Naive Bayes as a linear classifier. 

20201126  Hyperplanes and the perceptron algorithm. BlockNovikoff theorem. Voted perceptron. Dual form of the perceptron algorithm, 

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

20201203  Pruning and rulepruning for decision trees. Sketch of the random forest algorithm. 

20201203  Introduction to ScikitLearn. 

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.