LE/EECS 4401 3.0 Artificial Intelligence
GS/EECS 5326 3.0 Topics in Artificial Intelligence
Winter 2020
Department of Electrical
Engineering & Computer Science,
York University
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 11: Solutions to assignment 2 are here (login using your EECS account credentials).
- Mar 22: Assignment 2 is out; it is due April 6 at 23:59;
you must upload your assignment paper using WebSubmit
here
(login using your EECS account credentials) by the deadline.
- Mar 19: There will be no change in the course's evaluation scheme due to the shift to online instruction. The final exam will be a take-home exam and will be held on April 13 as originally scheduled. More information about the exam will be posted later. The project presentations will be done using Zoom video conference during the week of March 30.
- Mar 16: The course is proceeding online from now on. See the course announcements on Moodle for information on how to attend the online classes and office hours. Lecture recordings are also available there. Lecture notes will continue to be posted here.
- Mar 11: Information of the course project is available
here; the project proposal is due on
March 17;
you must upload your proposal using WebSubmit
here
(login using your EECS account credentials) by the deadline.
- Mar 2: Solutions to assignment 1 are here.
-
Feb 25: The midterm test will be held during class on March 5.
It will cover everything we have seen up to Week 4 inclusively, i.e. FOL syntax and semantics, expressing knowledge and reasoning in FOL, description logics (including the tableau proof procedure), and defaults reasoning formalisms.
-
Feb 13: The deadline for submitting Assignment 1
has been extended to February 21 at 23:59;
you must upload your assignment paper using WebSubmit
here
(login using your EECS account credentials) by the deadline.
- Feb 10: As announced in class, the lecture on Feb 11 is cancelled; a makeup lecture will be scheduled later.
- Jan 29: Assignment 1 is out; it is due Feb 21 at 23:59 (extended!)..
Instructor
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 416-736-2100 ext. 70146
Email: lesperan@eecs.yorku.ca
Lectures
Tuesday and Thursday from 11:30 to 13:00 to in ACW 205.
Instructor Office Hours
Tuesdays from 17:00 to 18:00 and Thursdays 13:30
to 14:30.
Textbook
Russell, S.J. and Norvig, P.,
Artificial Intelligence: A Modern Approach, 3rd edition
Prentice Hall, 2010.
Authors' web site,
Publisher's web site.
(The new 4th edition won't be released until April, so we have to use the
3rd edition.)
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
Assignments (2 @ 10% (each) | 20% |
Midterm Test |
20% |
Project Proposal |
5% |
Project Presentation |
10% |
Project Report |
20% |
Final Exam | 25% |
Total | 100% |
Tentative Schedule
- Week 1 (Jan 6) Introduction. Review of FOL.
- Week 2 (Jan 13) Expressing Knowledge in FOL. Reasoning in
FOL. Supervised learning of classes and rules.
- Week 3 (Jan 20) Description Logic and Ontologies.
- Week 4 (Jan 27) Default Reasoning and ASP.
- Week 5 (Feb 3) Reasoning about Actions and Planning.
- Week 6 (Feb 10) Planning. Golog.
- (Feb 17) Reading Week -- No Classes. Assignement 1 due.
- Week 7 (Feb 24) Planning as Heuristic Search.
- Week 8 (Mar 2) Reasoning under Uncertainty and Bayes Nets. Learning Probabilistic Models. Midterm Test.
- Week 9 (Mar 9) Probabilistic Reasoning over Time. Project Proposals Due.
- Week 10 (Mar 16) Markov Decision Processes.
- Week 11 (Mar 23) Reinforcement Learning. Assignement 2 due.
- Week 12 (Mar 30) 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 6): 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 13): 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).
- Week 3 (Jan 20): 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);
De Giacomo's
presentation Description Logics for Conceptual Data Modeling in UML, slides 1-26 and 32;
Horrocks and Sattler's
slides on tableaux for ALC concept satisfiability and
Horrocks and Sattler's
slides on tableaux for ALC knowledge bases, slides 2 and 3
(Baader and Sattler's
paper Overview of Tableau Algorighms for Description Logics, further explains this material);
De Giacomo's
presentation Towards Systems for Ontology-based Data Access and Integration using Relational Technology (Oct 5, 2010 U of Toronto) slides 4-6, 13, 29, 30, and 36-38.
Additional Optional Readings:
Baader and Sattler's paper Overview of Tableau Algorighms for Description Logics;
Calvanese et al's paper Conceptual Modeling for Data Integration;
Calvanese et al's Ontologies and Databases: The DL-Lite Approach;
Lutz's slides on Reasoning in Description Logics: Expressive Power vs.
Computational Complexity,from his tutorial at KR 2010.
- Week 4 (Jan 27): 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);
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 5 (Feb 3): 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 6 (Feb 10), Week 7 (Feb 24), and Week 8 (March 2): 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 1 and
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 9 (March 9): 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 10 (March 16): Sequential Decision Making Under Uncertainty
Required Readings:
Russell & Norvig, Chapter 17, Sec. 1 to 4 inclusively.
Lecture transparencies from Russell & Norvig, Chapter 17.
- Week 11 (March 23): Reinforcement Learning, Suoervised Learning
Required Readings:
Russell & Norvig, Chapter 21 and Chapter 18, Sections 1 to 3
(the rest of the chapter is optiional).
Lecture transparencies on Russell & Norvig, Chapter 21, from Prof. Picard, we went over slides 23 to 38.
Lecture transparencies from Russell & Norvig, Chapter 18, Sections 1-3.
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:
Ronald J. Brachman and Hector J. Levesque,
Knowledge Representation and Reasoning,
Elsevier/Morgan Kaufmann 2004, ISBN 1-55860-932-6
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
About Prolog