A Combined Analytic and Inductive Approach to Learning in Knowledge-Based Systems

Michael Pazzani
Department of Information and Computer Science,
University of California, Irvine
Irvine, CA 92717
Office Phone: (949) 824-5888
Fax Phone: (949) 824-4056
Electronic Mail: pazzani@ICS.UCI.EDU

Combining expert knowledge and inductive learning for knowledge-base maintenance

We are investigating the use of novel machine learning techniques to facilitate the acquisition of knowledge for knowledge-based systems and the management of large knowledge bases. We have developed a machine learning system that maintains a close tie between a knowledge base of expert rules and a database of examples. For example, if the knowledge base is changed, the examples in the database affected by the change will be identified, and more importantly, if the database changes (e.g., by the addition of examples), the system will can make changes to the knowledge base to make it consistent with the examples. This system is called the First-Order Combined Learner FOCL.

Objective

Use machine learning methods to find patterns in data that are not correctly classified by expert knowledge

Input

Examples belonging to a set of categories

Rules that classify examples into categories

Output

Rules that classify examples into categories

Performance Goal

At least as accurate as running inductive program on examples

At least as accurate as original rules

Calendar Management Example

Collaboration with Tom Mitchell , CMU. The Calendar Manager schedules the time, duration, location of meetings. It Learns to suggest defaults of users given information on the purpose of meeting, the people attending, and the person scheduling meeting. It is regularly used by several people at CMU.

Unique Aspects of UCI work: FOCL

Learns first-order rules from examples

More expressive than propositional logic used in decision trees, neural nets, etc.

Ability to learn from relational & object oriented databases

Some Calendar Rules Without First Order Rules:

location-WeH5309 :- attendees = office-hours & 
                    sponsor = mitchell
location-WeH5307 :- attendees = office-hours & 
                    sponsor = mason

Some Calendar Rules With First Order Rules

location(Meeting, Room) :- attendees(Meeting, office-hours) & 
                           sponsor(Meeting, S) &
                           office(S, Room).

This first-order rule captures the same information as the two propositional rules: Faculty typically have office hours in their offices.

Use of existing rules to bias learning

The theory graphed below is a simple theory of how faculty schedule their meeting locations. A person who schedules the meeting schedule it in his office, classes are held in the classroom in which they are assigned, and seminars are held in seminar rooms. The theory isn't perfect, but it helps a FOCL learn to make more accurate predictions. For example, one rule is changed by training on two faculty schedules to indicate that faculty schedule meetings in their office if no more than two others attend.

(event-location_learned_rule ?0 ?1) :- 
        (event-type ?0 ?2), (eql ?2 meeting), (scheduled-by ?0 ?3),
        (office ?3 ?1), (number-of-attendees ?0 ?4), (<= ?4 2)

Comparison of Learning Methods

This graph shows the average accuracy of FOCL trying to predicting the location at which a meeting will be held under three conditions:

Empirical (No Relations). FOCL learns rules like a propositional learner. It doesn't use additional relations containing information on classroom or office locations
Empirical (Relations) FOCL uses relations containing information on classroom or office locations to learn first-order rules.
Empirical+ Analytic (Relations) FOCL uses relations containing information on classroom or office locations to learn first-order rules. In addition, FOCL is given an approximate theory that is about 85% accurate.

FOCL is more accurate when given useful background relations, and even more accurate when also given an approximate domain theory.

Existing Applications of FOCL

Application              Rules   Data        Source        
Chess end games             10   1000 	  investigator
Payment of student loans    20   1000 	  honors project
Foreign trade negotiations  30    100 	  company (EBR)
Aircraft Identification     35    100 	  company (Hughes)
Telephone network           80   1000 	  company (NYNEX)
Calendar management          7    500 	  CMU
Translation              (3000)  7200 	  company (NTT)

Work In Progress

I assume you are familiar with a Hot List that contains pointers to your favorite Web pages. We are working on an an extension to Mosaic that contains a Cold List with pointers to Web pages you've visited but didn't like. Here's why:

Links on your cold list will be displayed in gray to warn you not to go there.
We are building a learning program to analyze your Hot List and Cold List and to suggest new Web Pages that you'd be interested in.

Publications

Machine learning papers from UCI

Project Leader: Michael Pazzani
Department of Information and Computer Science,
University of California, Irvine
Irvine, CA 92717-3425
pazzani@ics.uci.edu