Using Learning in PIA

Adrien DI MASCIO


Table of Contents

Brief description of the different elements used in the learning procedure
Why decision trees ?
Definitions
The learning procedure
Technical details
The ID3 algorithm

Brief description of the different elements used in the learning procedure

Why decision trees ?

We decided to use decision trees rather than neural networks or Case-base learning. Neural networks, according to the article's authors, offer similar performances but the way it processes is not human-understandable, thus disabling the interactivity potential. Case-base learning offers good result too, and it is easily understandable, but we wanted to use rules to describe user's preferences because we think it's a natural way for a person to express what he or she wants. For example, one may say : IF it is a "Weekly Synthesis Meeting" THEN contact every one. As we keep the learnt rules in a very simple format, it's easy for the user to merge his own rules in the base and then it is possible for him to interact with the system during the learning period.

Definitions

Meetings

A meeting, in our procedure, consists of a set of six features whose values are used to build rules. These values are :

  • Category : this describes the meeting type. For example, categories could be "Personal", "WSM", "Business", "Holiday Week-end", ...

  • Duration : the meeting's duration.

  • Location : the meeting's location.

  • Day : the day of the Week for this meeting.

  • Hour : the start hour of the meeting.

  • Attendees : the persons to contact and to make the appointment with.

Rules

Rules can be defined in two different ways depending on which context it is used in. The first format is the one used in the database. It is stored in xml, in a very simple way. The following example will be self-explainable :

	    
	  <prefrule test-relevance='3/5' training-relevance='8/10'>
	   <if>
	    <meetingattr name='category'>Personal</meetingattr>
	    <meetingattr name='duration'>60</meetingattr>
	   </if>
	   <then>
	    <meetingattr name='day' type='sure'>monday</meetingattr>
	   </then>
	  </prefrule>
	    
	  
This rule means that IF the meeting's category is Personal, and if the meeting's duration is 60 minutes, THEN the meeting's day will be monday. The relevance's attributes are here to evaluate the rule's performance. For example, here, in our training sample, this rule could be applied in 10 cases, and gave the expected result in 8 of these cases.

The second way of storing rules is the way used during the execution itself of the learning procedure. Rules are then objects which own two dictionnaries - a conditions one, and a consequences one - and other variables which hold the relevance informations. The two dictionnaries are built in the same way : keys are features and values are the associated values. Note that sometimes, in particular during a negociation process, consequences'value in the dicionnary are tuples which hold the value associated to the feature and a string which represent the type : positive, negative, ...

The learning procedure

The learning procedure we decided to use is largely inspired from the CAP one. CAP (Calendar Apprentice) is a calendar manager which learns its users' preferences. The way CAP proceed is described in the article: Experience with a Learning Personal Assistant. After having read several articles, this method appeared as a good way to proceed to learn users' preferences.

  1. Update the performance statistics for each current rule, to include performance on all new training example meetings.

  2. Extract all meetings from the user's calendar. Then cut out this set in two sub-sets which we will call Training examples and Test examples.

  3. Then, for each feature F in [duration,location,day,hour,category,attendees] :

    • Make a decision tree for F from the Training examples, using the ID3 algorithm.

    • Extract all the rules from this decision tree.

    • Compute rules' performance and optimize rules, i.e. remove all rules' conditions which do not decrease the rules' performance over both Training examples and Test examples.

  4. Sort each new rule into the previous rules in the base.

Technical details

The ID3 algorithm

As described above, we use the ID3 algorithm to build our decision trees. Here is the pseudo-code :

	  
	  MAKE_DECISION_TREE(Sample, Remaining_features)
	    IF Stop_condition(Sample)
	      THEN
	        Return a Leaf Node labelled with the feature and its corresponding value
            --------
            IF Remaining_features is an empty list
	      THEN
                Return a Leaf Node labelled with "Undecidable" value for this feature
	    --------
	    
	    F = choose_best_feature(Sample,remaining_features)
	    N = new Node testing F
	    remove F from the Remaining_features list

            FOR each distinct value V of F in Sample
   	      DO
	        sub_sample = all Examples in Sample whose value of F is V
	        B = MAKE_DECISION_TREE(sub_sample, Remaining_features)
	        Let B be a new sub-branch of N
              DONE
           
            RETURN N
	  
	

This is a generic ID3 algorithm. Some parts, in particular choose_best_feature() and stop_condition(), might be very dependant of the context in which you would like to use this algorithm. In our code, we used a ID3 class which is abstract, and created a MeetingID3 class which implements the choose_best_feature() method and overrides the __init__ method in order to let the tree_type - used in the ID3 algorithm - be a "MeetingDecionTree" and not just a "DecisionTree". Now, to use the different learning modules in your own context, you should write a class which inherits from the ID3 one and write the choose_best_feature() method which appears to be the most appropriate in your case.

In fact, you'll find, in all these modules, a set of class definitions which are sufficiently large to be used in a lot of contexts. The "only" things you'll have to code are the methods which requires specific processing, for example the methods which define how to load / update the rules base (which depend on the way you want to store them).