SFU                       Computing Science                       05-2
________________________________________________________________________
CMPT 419-3 D1"    Special Topics in Artificial Intelligence
 Instructor: O. Schulte                     SFU Burnaby

________________________________________________________________________

OBJECTIVE/DESCRIPTION:

Logic and Learning.  Research in AI has shown that if-then rules can
represent much of our everyday knowledge.  For example:  "if Bob is the
father of Alice and Alice is the mother of Luke, then Bob is the
grandfather of Luke", or "customers who have bought Dune also have bought
StarWars".  It turns out that writing rules like these is a powerful way to
program, which has given rise to the field of Logic Programming, and also a
strong formalism for writing queries for databases, which has led to
Deductive Databases.  Before we can use rules to express our knowledge, we
must somehow get that knowledge in the first place.  If we want to use
machines to extract the knowledge from data, the challenge is combine
Machine Learning with logical rules.  The field that addresses this
challenge is called Inductive Logic Programming.  Most of this course will
present the basics of Inductive Logic Programming.  Inductive Logic
Programming has been applied to many domains from learning gene sequences
to chess endgame positions; we will look at some of the major applications.
Relational Models are the fundamental modelling tool for modern database
systems.  Relational models are close to formal logic, and researchers in
data mining who look for associations among entities in a database have
used the formalism of logical rules to express these associations.  A
famous example is the rule "customers who buy diapers are also likely to
buy beer".  We will look at rule learning techniques tailored for mining
databases.  The first goal of the course is to present the two major
systems for learning logical rules, Quinlan's FOIL and Muggleton's PROGOL.
Rather than attempt an exhaustive survey of the field, I will introduce
enough material about logic programming and cover enough of the theory
behind these programs so that students can apply these systems on their own
to new datasets.  A well-known alternative to logical rules are Bayes Nets
or graphical models which capture probabilistic and causal relationships in
the data.  An exciting new development is a combination of Bayes Nets with
relational models known as Probabilistic Relational Models.  If we have
enough time we will look at how Probabilistic Relational Models work and
what some of their applications are.

TOPICS:

   o Logical Rules and Logic Programming
   o Deductive Databases
   o Inductive Logic Programming (ILP)
   o The FOIL and PROGOL ILP systems
   o Some Applications of ILP
   o Datamining, Association Rules, Relational Decision Trees
   o time permitting:  Probabilistic Relational Models.

GRADING:

Tentative Grading Scheme:  - 40% Final Exam - 40% Final Project - 20%
Assignments Students must receive a passing mark on the exam to receive a
grade higher than D in this course.  The final grading scheme will be
announced during the first week of classes.

TEXTBOOKS:

   o Inductive Logic Programming, Lavrac and Dzeroski, Ellis Horwood, 1994
   o Relational Data Mining, Lavrac and Dzeroski (eds.), Springer, Berlin,
     2001

RECOMMENDED:

   o Machine Learning (1997).  Chapters 10, 11, 12., Tom Mitchell, McGraw
     Hill, 1997

REFERENCES:

   o The Foundations of Inductive Logic Programming, Shan-Hwei
     Nienhuys-Cheng und Ronald de Wolf, Springer, Berlin, 1997

PREREQUISITES/COREQUISITES:

CMPT 310 or permission of the instructor.  Logic Programming background
desirable.

Distributed:  February 16, 2005

.......................................................................

Academic Honesty plays a key role in our efforts to maintain a high
standard of academic excellence and integrity.  Students are advised that
ALL acts of intellectual dishonesty are subject to disciplinary action by
the School; serious infractions are dealt with in accordance with the Code
of Academic Honesty (T10.02)
(http://www.sfu.ca/policies/teaching/t10-02.htm).  Students are encouraged
to read the School's policy information
(http://www.cs.sfu.ca/undergrad/Policies/).