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

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.


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


Examples belonging to a set of categories

Rules that classify examples into categories


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:

    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:


    Machine learning papers from UCI
    Project Leader: Michael Pazzani
    Department of Information and Computer Science,
    University of California, Irvine
    Irvine, CA 92717-3425