RHB+: A Type-Oriented ILP System Learning from Positive Data

1 Introduction

Inductive Logic Programming (ILP) [Muggleton, 1991] is a promising approach to knowledge-level learning from real-world examples such as the wide variety of facts contained in on-line newspapers or large-scale databases. Major extensions related to types (or sorts) are, however, required for ILP systems to handle real-world relations. First, types should be always attached to hypotheses in order to make comprehensible rules with appropri­ ate generality. Second, background knowledge, even if it includes thousands of hierarchically structured types, must not deteriorate system performance. These ex­ tensions have to be achieved within the restriction that only positive examples are available because negatives are not usually found in real-world data. Actually, type hierarchy has played a key role in several natural lan­ ~uage processing systems, such as [Ikehara et a!., 19~3], lHastings and Lytinen, 1994] . Knowledge representatiOn languages [Ai:t-Kaci and Nasr, 1986], [Ai:t-Kaci et a!., 1994], [Borgida and Patel-Schneider, 1994], [Sowa, 1991] also incorporate types and they achieve efficient inheri­ tance according to the type hierarchy used.

The following example illustrates that type informa­ tion is essential to learning in the situation in which a human could learn rules of appropriate generality from a small number of examples by using type hierarchy.

Example 1 (Sample data of "speak")

Suppose that a person knows the following relations :

• Positive example : { speak(Jack,English), speak(Jun,Japanese)}
• Background knowledge : { grew_in(Jack,UK), grew_in( Jun,Japan), official_lang( UK,English) , official_lang( Japan, Japanese) }.

Existing ILP systems may produce the clause :

This clause is, however, over-general because it says that everything that grew up in a country, even a dog or cat, speaks that language. Types effectively solve this problem. In this case, we expect the following relations with types to be produced:

where Var:T denotes that every variable Var appearing in a clause is the type T. In other words, this clause rep­ resents "A human speaks a particular language if s/he grew up in a country whose official language is that lan­ guage" .

To learn this relation, we have to give the following additional background knowledge to the learner:

Japanese <language, Japan <country}

Note that A <B denotes A is a sub-type of B.

Adding is_a relations to background knowledge seems to lead us to our goal but conventional ILP systems vir­ tually fail to produce hypotheses with appropriate types even though background knowledge incorporates types and is_a relations. This is mainly because it is not realis­ tic to handle a large number of fragments of a large-scale type hierarchy as ordinary background knowledge. The types have a tree or lattice structure and giving right types means to follow the links of the structure based on the generalization and specialization operations.

In this paper, we present the design and implementa­ tion of the type-oriented ILP system RH B+ to solve the problems. In Section 2, the algorithms and implemen­ tation methods of RH B+ , especially the novel mecha­ nisms for learning relations with types, are described. Experimental results are shown in Section 3. Section 4 describes related work and Section 5 concludes this pa­ per.

2 RHB+

In this section, we describe the novel relational learner RH B+ which generates typed Prolog programs from just positive examples on the basis of background knowledge which might include a large-scale type hierarchy.

2.1 Hypothesis Language

The hypothesis language of RH B+ is the Horn clause [Lloyd, 1987] based on the restricted form of '1/J-terms used in LOGIN [Alt-Kaci and Nasr, 1986] or LIFE [Alt-Kaci et al., 1994] 1 . For convenience, we call this restricted form T-terms. Informally, T-terms are Prolog terms whose variables are replaced with variable Var of type T, which is denoted as Var:T. Moreover, a function is allowed to have labels or keywords for read­ ability. The definition of T-terrps is as follows.

Definition 1 ( T-terms)

1. An individual constant is a term.
2. If T is a type and X is a variable, X :T is a term.
3. If t 1 , ... , tn are terms, l 1 , ... , ln are labels, and f is a function symbol of arity n, then f(l 1 * t 1 , ... , ln * tn) is a term.

Labels are symbols used as keywords to indicate the content of arguments in terms. For example, speak( name *Jack, lang *French) is a literal based on T-terms whose labels are "name" and "lang". While T-terms have labels, they are compatible to usual Pro­ Jog terms. A usual logic term can be regarded as a T­ term whose labels are argument position numbers in the terms. For example,

got( Jack, good_grade)

1 wildJife, an implementation of LIFE, IS available at http:/ /www.isg.sfu.ca/life

is regarded as

and sometimes the former is used for the concise repre­ sentation of a T-term when the labels are numbers.

As an abbreviation, X:T is denoted as T if X is bound to no other variable or constant. X:T is denoted as X if T is the universal type (i.e., the root of a type hierarchy) or if X:T appeared before in a clause.

For example,

can be abbreviated as

where human and good_grade are types.

2.2 Lgg with types

In the definition of the least general generalization {lgg) [Plotkin, 1969], the definition of the term lgg should be extended to T-term lgg. Other definitions of lgg are equivalent to the originals. Note that lub(s , t) is the function which returns the least upper bound of s and t according to a type hierarchy if t and s are types, other­ wise it returns a new variable X.

Definition 2 ( T-term lgg)

1. lgg(t,t) = t .
2. lgg(f(lt * St, .. ,ln * Sn),j(lt * t1, .. , ln * tn) f(lt * lgg(st,tt), ... ,ln * lgg(sn , tn)).
3. lgg(s , t) = u for term s and t of different symbols or with different function names, where the tuple ( s, t, u) is in the history H.
4. 4· lgg(s, t) = u for term s and t of different symbols or with different/unction names, whereu = lub(s,t) and (s,t,u) is not in H . Then add (s,t,u) into H.

RH B+ employs this lgg to make candidates for the heads of hypothesis clauses from pairs of positive exam­ ples.

For example,

2.3 RH B+ Algorithms

Given positive examples are non-negative literals based on T-terms. The hypothesis language is Horn clauses based on T-terms. The background knowledge are non­ negative literals. 2 RH B+ employs a combination of bottom-up and top-down approaches, following the re­ sult described in [Zelle et al., 1994] . That is, first make the head in a bottom-up manner then construct the body in a top-down manner.

The outer loop of RH B+ finds covers of the given positive examples P in a greedy manner. It constructs clauses one by one by calling inner _loop( P, Po, B K) which returns a hypothesis clause, where Po is origi­ nal positive examples and BK is background knowledge. Covered examples are removed from Pin each cycle; Po remains unchanged.

2 Horn clauses that produce finite numbers of atoms can be included.

Algorithm 1 inner _loop(P, P0 , BK)

1. Given positive examples P ,P0 , background knowl­ edge BK.
2. Decide types of variables in a head by computing typed lggs of N pairs of elements in P, and select the most general head as Head.
3. If StopCond(P0 , BK, Head) is satisfied, return Head.
4. Let Body be empty.
5. Create a set of all possible literals L using variables in Head and Body.
6. Let BEAM be top K literals lk of L with respect to positive weighted informativity, PWI(P,BK,(Head :-Body,lk)).
7. Do later steps, assuming that lk is added to Body for each literallk in BEAM.
8. Dynamically restrict types in Body by calling restrict(P,BK,(Head :- Body)}.
9. If StopCond{P0 ,BK,(Head :- Body)} is satisfied, return (Head:- Body).
10. Goto 5.

We will now see how types are utilized in each compo­ nent of the RH B+ algorithm in the following sections.

2.4 Dynamic type restriction by positive examples

The special feature of RH B+ is the dynamic type re­ striction by positive examples during clause construc­ tion. restrict(P,BK,(Head :-Body)) in Algorithm 1 does this part, where P represents positives, BK is back­ ground knowledge, and (Head:-Body) is a hypothetical clause. The restriction uses positive examples currently covered in order to determine appropriate types. In­ formally, for each variable X; appearing in the clause, RHB+ computes the lub of all types bound to X; when covered positive examples are unified with the current head in turn. Formally, the dynamic type restriction by positive examples is defined as follows.

Algorithm 2 (Dynamic type restriction by positive ex­ amples)

1. Given a hypothesis clause Hypo= (Head :-Body) and positives P.
2. Collect all the types in Hypo and put them into a list TypeSet.
3. Let P be examples in P covered by Hypo.
4. For all elements p; of P , unify Head and p;, then prove Body. Make a list TypeSet; of bound types in the proved Head and Body so that the position of each type in TypeSet; correctly corresponds to the position of the original type in TypeSet .
5. For all Xk in TypeSet , compute lub rk of all bound types of Xk in TypeSet;.
6. For all k, bind Tk to xk.

Type restriction binds a type to each newly introduced variable in the body. Without a type restriction, newly introduced variables would always have no types, and RHB+ might produce over-general clauses. Note that the result of the type restriction operation by unifica­ tion dynamically affects the types of all variables related to the unified variable. This operation is directly im­ plemented by using the type unification mechanism of LIFE.

It would rather not aggressively add type to narrow the current cover but it is interesting that the dynamic type restriction significantly contributes to narrowing the current cover and helping the learner to find good hypotheses.

Example 2

When we have positive examples and background knowl­ edge as given in Example 1 and additional data about cat Socks.

• Additional positive example : { speak( Socks, cat-lang) }
• Additional background knowledge : {grew_in(Socks,Japan), Socks <cat} .

Suppose that speak( age':'!t,anything) is the current head. Adding official_lang/2 , one of the candidates for additional literal, restricts the types in the head as fol­ lows. The current clause before the type restriction is:

The second argument of official_lang matches an offi­ cial language. This cause that covered positives are only examples relating to humans because the positive related to Socks is no longer covered. Therefore, the type agent is restricted to humans and we obtain:

After that, the data unrelated to humaris will not af­ fect the clause construction. This illustrates how the typing contributes to restricting types in forming typed clauses.

2.5 Use of types in computing lnformativity

Type information is also used to compute informativity PWI(P,BK,(Head :-Body)).

where IPI denotes the number of positive examples cov­ ered by T. In effect, this is weighted informativity em­ ploying the Laplace estimate [Cestnik, 1990]. Q(T) is the empirical content and defined as follows.

Definition 3 (Empirical content) Q(T) is a set of atoms with the predicate name of Head in the least Her­ brand model M(T) of theroy T. Q(T) is called the em­ pirical content. This notation is borrowed from the model complexity measure (Conklin and Witten, 1994}.

Type information is very useful for computing Q(T) . Let H s be a set of instances of Head generated by prov­ ing Body using backtracking. We introduce the notation lrl which expresses the number of constants that type T represents. When Tis a constant, lrl is defined as 1. In­ tuitively, lrl is the number of leaves under T in the type hierarchy.

where Types(h) returns the set of types in h.

Example 3

Positive examples and background knowledge are as given in Example 1. T is the background knowledge and the following clause:

speak(human, Y: language) :- official_lang(X,Y).

In this case, the set of instances H s is {speak( human, Japanese),speak(human, English)}. Caution is needed in that human is the type representing two constants: Jack and Jun.

Type information drastically reduces the time to cal­ culate informativity because it cuts the effort of gen­ erating huge numbers of combinations of constants for computing the empirical content. In this case, PW I(T) is calculated as follows:

2.6 Use of types in the stopping condition

This section describes how the stopping condition StopCond(P0 ,BK,(Head :-Body)) works. When given only positive examples, usual informativity can not be applied. When T is the current hypothesis and back­ ground knowledge, we use the Model Covering Ratio {MCR):

The stopping condition is "MCR(T) ::; a" for a pre­ defined constant a ( 0 ::; a ::; 1). Note that I Po I here de­ notes the original positive examples covered by T. This is because IQ(T)I may include a lot of examples removed from P in earlier steps . Type information plays a key role in computing the stopping condition because it per­ mits the efficient calculation of IQ(T)I as described in the previous section.

3 Experiments and Results

In order to confirm that RH B+ can efficiently handle a type hierarchy, two kinds of experiments were con­ ducted with one part of 3000 is_a relations. We selected more appropriate representation of is_ a relations for each learner: PROGOL incorporated is_a literals, which rep­ resent direct links in a type hierarchy, in background knowledge and FOIL used type literals.

The first experiment determined the effect of type hi­ erarchy size. We tested FoiL, PROGOL 3 and RH B+ on artificial data while changing hierarchy size.

The second experiment measured the performance of those three learners with real data extracted from news­ paper articles. We used a SparcStation 20 with 96 Mbyes of memory for the experiments.

3.1 Type Hierarchy

Figure 1 shows the structure of our type hierar­ chy [Ikehara et al., 1993]. The hierarchy is a sort of con­ cept thesaurus represented as a tree structure in which each node is called a category (i .e., a type). An edge in this structure represents an is_a relation among the categories. For example, "Agents" and "Person" (see Figure 1) are both categories. The edge between these two categories indicates that any instance of "Person" is also an instance of "Agents". The current version of type hierarchy is 12 levels deep and contains about 3000 category nodes. Such level of detail was found necessary to perform semantical analysis that enabled real world text understanding [Ikehara et al., 1993].

3 PROGOL4.2 with set(posonly) option.

In order to estimate the effect of type hierarchy size on learning speed, we randomly generated positive ex­ amples that satisfied the following answer clause:

speak(A: person,B: language):- grew_in(A, C: country), officiaUang(C, B).

Figure 2 shows that FOIL exponentially slows as the type hierarchy size increases. On the other hand, the learning speed of RH s+ and PROGOL were not affected so much by the number of is_a relations. MCRs of the results from the artificial data should not be taken seriously.

3.3 Experiment by Real Data

We extracted articles relating to accidents from a one­ year newspaper corpus written in Japanese. 4 Forty two articles are related to accidents that resulted in some numbers of death and injury. We parsed the sentences with the commercial-quality parser of our machine trans­ lation system [Ikehara et al., 1993], and performed se­ mantic analysis to extract the case frames in the sen­ tences. Twenty five articles were well parsed and seman­ tically analyzed. Case frames were converted into literals and we created two kinds of positive examples from those literals. One was death_toll which represents the number of deaths in each article and the other was injury which represents the number of injuries in an article. In pre­ possessing, literals unrelated to positive examples were removed. The result was that three literals for each ar­ ticle were selected as background knowledge. The data set consisted of 25 positive examples. The background knowledge contained 78 literals with 26 kinds of predi­ cates and 124 types and constants.

Tables 1 and 2 show the learning results of FOIL, PRO­ GOL and RH s+. IHypol shows the number of clauses in hypotheses Hypo. T is the union of the hypotheses and background knowledge. IFIIIQ(T)I shows the MCR, the ratio between covered positives and the empirical con­ tent ofT, that is, the size of the set of all instances of the head provable from T . Handling type information seriously degraded the learning speed of FOIL. PROGOL was relatively fast; however it's results were over-general in both experiments. RH s+ recorded both good per­ formance and appropriate generality of the outputs.

4 We used the Mainichi Newspapers articles of 1992 under appropriate permission.

Because of space limits, only the learning results from data "death toll" are shown here as follows.

· FOIL result death_toll(A,B) :- dead(A,B,C,D). death_toll(A,B) :- confirmed(A,C,B), anything(B). death_toll(A,B) :- null(B), is_article_l(A) . · PROGOL result death_toll(al,''). death_toll(A,B) :- dead(A,B,C,D). death_toll(A,B) :- confirmed(A,C,B) .

·RHB+ result death_toll(article=>_A:any, dead=>_B:number) dead( article=>_!, agent=>_B, sub_agent=>any, cause=>any). death_toll(article =>al,dead=>''). death_toll(article =>_A:a4, dead=>_B:four) confirmed(article=>_A, by=>accident, obj=>_B). death_toll(article=>a23, dead=>'driver').

4 Related Work

Some previous learners, such as FOIL [Quinlan, 1990], GOLEM [Muggleton, 1990] and PROGOL [Muggleton, 1995] use type or sort declarations for curtailing the search space. Their learning results, however, do not have type information linked to those declarations. Sim­ ply including types and is_a relations in background knowledge is not a solution to obtaining typed clauses. The reason is that the possibility of a long is_a or type chain creates excessive overhead; the learner must search for all is_a literals or type literals. For example, when the type hierarchy is twelve levels deep, a chain of up to twelve is_a literals should be checked. When is_a represents direct links in a type hierarchy, one possible chain might be:

When is_a includes indirect links in a type hierarchy, atoms to be checked are:

is_a(X, male), is_a(X, human), ... , is_a(X, agent), ... . When type literals represent types in a type hierarchy, atoms to be checked are:

In those cases, top-down learners spend too much time trying to construct those chains while bottom-up learn­ ers try to remove the some of is_a or type atoms and find good hypotheses.

Special treatment to types was presented in [Yamazaki et al., 1995]. It requires both positive and negative ex­ amples to efficiently decide one_isa atoms.

According to an input-output declaration, FOIDL [Mooney and Califf, 1995] generates implicit negatives by output queries for input arguments of positive ex­ amples in a normal ILP setting. RH s+ utilizes type information to compute the number of covered examples including implicit negatives.

5 Conclusions and remarks

RH s+, which learns typed Prolog programs, was pre­ sented. Its performance is not affected by the number of types or type hierarchies size for the sake of direct manipulation of types and utilization of type informa­ tion in computing informativity heuristics and stopping conditions. It also achieved appropriate generalization levels of hypotheses. At this point, a full LIFE compiler is not available but the current interpretive version of RH s+ showed good performance. The execution speed will markedly improved when a LIFE compiler becomes available.

Acknowledgments

We thank the anonymous referees for their constructive comments. It helped us improve performance of FOIL and PROGOL in the experiments.