LE/EECS 4401 3.0 Artificial Intelligence
GS/EECS 5326 3.0 Topics in Artificial Intelligence
Winter 2021

For additional information, see the course page on eClass!

Course Description

This is a second course in artificial intelligence that covers selected topics in this area such as: reasoning about action and planning, uncertain and fuzzy reasoning, knowledge representation, automated reasoning, non-monotonic reasoning and answer set programming, ontologies and description logic, local search methods, Markov decision processes, autonomous agents and multi-agent systems, machine learning, reasoning about beliefs and goals, and expert systems.

This Year's Theme: Knowledge-Based Systems and their Relationship to Machine Learning.

Knowledge-based systems that use symbolic representations of knowledge and automated reasoning are well established and their performance is often quite good. However it can be very costly to have experts input the knowlege that they use. Recently, given the availability of labelled training data, there has been a lot of work on using maching learning techniques to build AI applications, which often achieve with very good performance However, this has lead to concerns about the safety of such systems and their inability to explain their behavior. Given this, there is much interest in understanding how to relate and combine knowledge-based systems techniques and maching learning methods. The course will cover a broad range of current symbolic knowledge representation and reasoning techniques, including probabilistic methods, and also look at associated mchine learning techniques.

What's New:

• Apr 19: Assignment 2 solutions are available here (enter your EECS ID and password to access).
• Mar 25: Assignment 2 is out. It is due on April 16 at 23:59 (extended!).
• Feb 28: Assignment 1 solutions are available here (enter your EECS ID and password to access).
Feb 23: The midterm test will be held on eClass during the lecture time on March 2. The test is open book and lasts 90 minutes. It covers everything we have seen up to February 23 inclusively, i.e. FOL syntax and semantics, expressing knowledge and reasoning in FOL, description logics (including the tableau proof procedure), and defaults reasoning (except for the material on answer set programming).
• Feb 23: Information of the course project is available here; the project proposal is due on March 9 (submit it on eClass).
• Feb 4: Assignment 1 is out. It is due on Feb 22 at 10am.
• Jan 7: Online lectures start on January 12; see below for the Zoom Meeting info.

Instructor

Prof. Yves Lespérance
Office: LAS 3052A
Email: lesperan@eecs.yorku.ca

Lectures

Tuesday and Thursday from 10:00 to 11:30.

Instructor Office Hours

Tuesdays and Thursdays from 15:00 to 16:00.

Textbooks (Optional)

Russell, S.J. and Norvig, P., Artificial Intelligence: A Modern Approach, 4th edition Prentice Hall, 2020. ISBN 978-0134610993.
Authors' web site, Publisher's web site.
(If you already have the 3rd edition, you can use that instead of the 4th.)

Ronald J. Brachman and Hector J. Levesque, Knowledge Representation and Reasoning, Elsevier/Morgan Kaufmann 2004. ISBN 1-55860-932-6.
Publisher's web site

Prerequisites

General prerequisites; LE/EECS3401 3.00 Introduction to Artificial Intelligence and Logic Programming. You should know first-order logic. You must know either Prolog or Java, preferably both.

Evaluation

Tentative Schedule

• Week 1 (Jan 11) Introduction to AI and Knowledge Representation. Review of FOL.
• Week 2 (Jan 18) Expressing Knowledge in FOL. Reasoning in FOL. Supervised learning of classes and rules.
• Week 3 (Jan 25) Description Logic and Ontologies.
• Week 4 (Feb 1) Default Reasoning and ASP.
• Week 5 (Feb 8) Supervised Learning.
• (Feb 15) Reading Week -- No Classes. Assignement 1 due.
• Week 6 (Feb 22) Reasoning about Actions and Planning.
• Week 7 (Mar 1) Planning. Golog. Planning as Heuristic Search. Midterm Test.
• Week 8 (Mar 8) Reasoning under Uncertainty and Bayes Nets. Learning Probabilistic Models. Project Proposals Due.
• Week 9 (Mar 15) Probabilistic Reasoning over Time.
• Week 10 (Mar 22) Markov Decision Processes. Assignment 2 due.
• Week 11 (Mar 29) Reinforcement Learning.
• Week 12 (Apr 5) Project Presentations.

Academic Honesty

It is important that you look at the departmental guidelines on academic honesty. You must cite all sources that you use in answering assignment and test questions, and in your project report. You may not collaborate with others in course assignments, tests, and project unless indicated, and all collaborators must be listed.

Readings and Lecture Transparencies

• Week 1 (Jan 11): Introduction to Knowledge Representation and Reasoning. Review of FOL.
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning Chapters 1 and 2. The slides for the entire book are here (enter your EECS ID and password to access).
• Week 2 (Jan 18): Expressing Knowledge in FOL. Reasoning in FOL.
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning Chapters 3 and 4; also please read Chapter 5 slides 80, 85, 89, and 90 (see Week 1 for a link to the book slides).
  The additional examples discussed in class are here.
• Weeks 3 & 4 (Jan 25 & Feb 1): Description Logics.
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning Chapter 9, slides 139-149 (see Week 1 for a link to the book slides).
  Turhan's Introduction to Description Logics slides, Tableau Proof Examples discussed on 09/02/202.
  Optional Readings: Baader and Sattler's paper Overview of Tableau Algorithms for Description Logics, Turhan's paper Introduction to Description Logics -- A Guided Tour, Kroetzsch et al's paper A Description Logic Primer.
• Week 5 & 6 (Feb 8 & 22): Defaults.
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning Chapter 11, slides 179-195 (see Week 1 for a link to the book slides);
  my additional examples slides;
  Levesque's slides on Answer Set Programming;
  here is information on the clingo Amswer Set Programming Tool from Potsdam Universiy (you can run simple examples in your browser by following the link in the Getting Started page).
• Week 7 (Mar 1) Learning from Examples
  Required Readings: Russell & Norvig 3rd edition Chapter 18 Sec. 1, 2, 3, 6, and 7 (the rest of the chapter is optional).
  Lecture transparencies from Russell & Norvig Chapter 18 Sec 1 to 3, Lecture transparencies from Russell & Norvig Chapter 18 Sec 6 and 7.
• Week 8 (Mar 8): Reasoning about Action.
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning, Chapter 14 (see Week 1 for a link to the book slides).
• Week 9 (March 15): Planning.
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning, Chapter 15 (see Week 1 for a link to the book slides).
  Lecture notes by Hector Geffner on Planning as Heuristic Search part 2 (from a short course at Sapienza University of Rome; July 2010; see Chapter 2 of the Bonet and Geffner book in the References below for more details; it is available as an eBook at York Libraries).
• Week 10 (March 22): Reasoning under Uncertainty
  Required Readings: Brachman and Levesque Knowledge Representation and Reasoning, Chapter 12 (see Week 1 for a link to the book slides).
• Week 11 (March 29): Sequential Decision Making Under Uncertainty & Reinforcement Learning
  Required Readings: Russell & Norvig, Chapter 17, Sec. 1 to 4 inclusively.
  Lecture transparencies from Russell & Norvig, Chapter 17.

References

Other good AI textbooks:

Poole, D. and Mackworth, A. Artificial Intelligence, Foundations of Computational Agents, 2nd edition, Cambridge University Press, 2017.

On First-Order Logic:

Enderton, H.B., A Mathematical Introduction to Logic. Academic Press, New York, 1972.

Tourlakis, G., Mathematical Logic. Wiley, 2008.

On knowledge representation:

Baral, C. Knowledge representation, reasoning, and declarative problem solving. Cambridge University Press, Cambridge/New York, 2003.

Genesereth, M.R. and Nilsson, N.J. Logical foundations of artificial intelligence. Morgan Kaufmann, Los Altos, CA, 1987.

Van Harmelen, F., Lifschiltz, V., and Porter, B. Handbook of Knowledge Representation. Elsevier, Amsterdam, 2008.

On description logic:

Baader, F., Calvanese, D., McGuiness, D., Nardi, D., Patel-Schneider, P. The Description Logic Handbook, 2nd Edition. Cambridge Univ. Press, Cambridge UK, 2007.

Lutz, C. Reasoning in Description Logics: Expressive Power vs. Computational Complexity, slides from Tutorial at KR 2010.

On reasoning about action:

Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001. York Library eCopy, Book home page.

On AI Planning:

Geffner, H. and Bonet, B. A Concise Introduction to Models and Methods for Automated Planning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2013.

Haslum, P., Lipovetzky, N., Magazzeni, D., and Muise, C. An Introduction to the Planning Domain Definition Language. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2019.

Hoffmann, J. Everything you always wanted to know about planning - (but were afraid to ask). In Bach, J. and Edelkamp, S., editors, KI 2011: Advances in Artificial Intelligence, 34th Annual German Conference on AI, Berlin, Germany, October 4-7, 2011. Proceedings, volume 7006 of Lecture Notes in Computer Science, pages 1–13. Springer, 2011.

Ghallab, M. Nau, D, and Traverso, M. Automated Planning: Theory & Practice, Morgan Kaufmann, 2004.

On Machine Learning:

Murphy, K.P. Machine Learning: A Probabilistic Perspective. Adaptive computation and machine learning. MIT Press, 2012.

Mitchell, T.M. Machine Learning. McGraw-Hill, 1997.

Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. Adaptive computation and machine learning. MIT Press, 2016.

On Reinforcement Learning:

Sutton, R. S. and Barto, A. G. Reinforcement Learning - An Introduction, 2nd Edition. Adaptive computation and machine learning. MIT Press, 2018.

On Prolog:

Clocksin, W.F. and Mellish, C.S., Programming in Prolog, (5th edition), Springer Verlag, New York, 2004.

Bratko, I. Prolog Programming for Artificial Intelligence 4th Edition, Pearson Education Canada, 2012.

Sterling, L.S. and Shapiro, E.Y. The Art of Prolog, Second Edition, MIT Press, 1994.

Running SWI-Prolog in the Prism Lab

• To run Prolog execute the command pl. To exit enter <CTRL>-D at the prompt.
• Documentation is available on the web.

Getting Prolog

• SWI-Prolog -- Windows, Linux, and Mac OS X versions of Prolog. Free software licensed under the Lesser GNU Public License. Look under downloads and IDE tools.

About Prolog

• A starting point is the Carnegie Mellon School of Computer Science Prolog repository.