B003725 - Artificial Intelligence - Fall 2017

Learning Objectives

You will learn about the basic concepts and the main research areas of AI. Broad topics that are covered include: searching, constraint programming, logic, probabilistic reasoning, and machine learning.

Prerequisites

B003368 (Algorithms and Data Structures)

Suggested readings

Textbooks:

[RN10] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. 3rd edition. Pearson, 2010.

[B12] D. Barber. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012.

Other texts:

[HTF09] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Data Mining, Inference, and Prediction. 2nd edition. Springer, 2009.

[STC00] John Shawe-Taylor and Nello Cristianini. Support Vector Machines and other kernel-based learning methods, Cambridge University Press, 2000

[PM10] David L. Poole, Alan K. Mackworth. Artificial Intelligence: Foundations of Computational Agents. Cambridge University Press, 2010.

[D03] Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003.

[F94] P. Flach. Simply Logical. Intelligent Resoning by Esample. Wiley 1994.

[GN87] M. Genesereth, N. J. Nilsson. Logical Foundations of Artificial Intelligence. Morgan Kaufmann Publishers, 1987. Alibris

Assessment

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 (Learning, Searching, Constraints, Logic programming). The oral exam covers the rest of the course.

Schedule and reading materials

Date Topics Readings/Handouts
2017-09-25 Administrivia. Introduction to Artificial Intelligence. Intelligence and rationality. Some basic theoretical computer science notions.
  • RN10 1
2017-09-28 Agents, percepts and actions. The agent function. Rational agents. Environment types. Examples. Structure of agents. Reflex agents.
  • RN10 2.1-2.4
2017-10-02 Problem-solving agents. Examples. Search graphs and search trees. Performance measures. Blind search (depth and breadth first).
  • RN10 3.1, 3.2, 3.3
2017-10-05 Analysis of BFS. Depth-limited search and iterative deepening. Uniform cost search. Optimality. Bidirectional search.
  • RN10 3.4
2017-10-09 Heuristics. Greedy best first search. Admissibility and consistency. A*. Optimality of A*. Performance measures. Designing heuristics. Pattern databases.
  • RN10 3.5, 3.6
2017-10-12 Python practice on blind and heuristic search.
2017-10-16 Local search. Hill climbing. Beam seach. Simulated annealing. Introduction to constraint programming. Constraint satisfaction problems. Examples.
  • RN10 4.1.1, 4.1.2, 4.1.3, 6.1.
2017-10-19 Inference for CSPs (constraint propagation). Node and arc consistency. AC-3 and its analysis. Path consistency. Introduction to search for CSPs.
  • RN10 6.1, 6.2
2017-10-23 Backtracking search. Variable and value ordering. Maintaining arc consistency.
  • RN10 6.3.1, 6.3.2
2017-10-30 Min-conflict. Forward checking. Directed arc consistency. Solving tree problems. Cutset conditioning. Dual problems and their networks. Junction trees.
  • RN10 6.3.2, 6.4, 6.5
2017-11-02 Constraint modeling with Minizinc and Numberjack.
2017-11-06 Logic-based agents. Knowledge bases. Entailment and logical inference. Model checking. Propositional logic. Syntax and semantics. Decidability. Satisfiability. Deduction theorem. Propositional theorem proving.
  • RN10 7.1-7.4, 7.5.1
2017-11-09 Resolution. Proofs by resolution. Conjunctive normal form. Ground resolution theorem. Definite clauses and Horn clauses.
  • RN10 7.5.2, 7.5.3
2017-11-13 Forward and backward chaining. SAT and the DPLL procedure. Random SAT problems. WalkSAT.
  • RN10 7.5.4, 7.6
2017-11-16 Beliefs, probabilities, and probabilistic reasoning. Conditional independence. Examples.
  • RN10 ch. 13, B12 ch. 1
2017-11-20 Homework: Solve problem in RN10 13.6. Directed graphical models (Bayesian networks). Semantics of directed networks. Conditional independence entailment. Examples.
  • RN10 14.1, 14.2, B12 3.1, 3.2
2017-11-23 D-separation and conditional independence in Bayesian networks. Conditional probability tables.
  • RN10 14.2, 14.3, B12 3.3
2017-11-23 Brief introduction to Hugin
2017-11-27 Inference. Junction trees for probabilistic inference. Algebra of probability tables. Absorption. Local and global consistency. Propagation in junction trees. Introduction to parameter learning in directed graphs. Maximum likelihood estimation for complete data.
  • RN10 14.4.4, 20.1, 20.2.1
2017-11-30 Machine learning and supervised learning. The Naive Bayes classifier. Training error, true error, using a test set to estimate the true error.
  • RN10 18.1, 18.2, 20.2.2
2017-12-04 Laplace smoothing for Naive Bayes. Multinomial model for text categorization. k-fold cross-validation. Decision trees. Top-down induction algorithm.
  • RN10 18.3
2017-12-07 Splitting criteria for decision trees. Why classification error does not work as measure of impurity. Gini index. Entropy criterion. Combatting overfitting with pre- and post-pruning. Handling continuous attributes. Rule pruning. Random forests.
  • RN10 18.3, 18.4.1
2017-12-14 Perceptron. Block-Novikoff theorem.
  • RN10 18.6.3, 18.7.2
2017-12-14 Introduction to Scikit-Learn.
2017-12-12 Optional Seminar: Intel AI Academy Seminar on Machine Learning and Deep Learning Fundamentals. Room 111 Santa Marta, 14:30

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.