Keith A. Pray - Professional and Academic Site · · ·
Professional
 · · · ·
 · · · · · · · · ·
Teaching
 · ·

Project 9: Analytical Learning

Intro ] [ 11.1-slide ] [ 11.1 ]

Code ] [ Report ] [ Up: Machine Learning ]

Exercise 11.1

Consider the problem of learning the target concept "pairs of people who live in the same house," denoted by the predicate HouseMates ( x, y ). Below is a positive example of the concept.

```
HouseMates ( Joe, Sue )

Person ( Joe )		Person ( Sue )
Sex ( Joes, Male )		Sex ( Sue, Female )
HairColor ( Joe, Black )	HairColor ( Sue, Brown )
Height ( Joe, Short )	Height ( Sue, Short )
Nationality ( Joe, US )	Nationality ( Sue, US )
Mother ( Joe, Mary )	Mother ( Sue, Mary )
Age ( Joe, 8 )		Age ( Sue, 6 )
```
The following domain theory is helpful for acquiring the HouseMates concept:
```
HouseMates ( x, y )	<- InSameFamily ( x, y )
HouseMates ( x, y )	<- FraternityBrothers ( x, y )
InSameFamily ( x, y )	<- Married ( x, y )
InSameFamily ( x, y )	<- Youngster ( x ) ^
Youngster ( y ) ^ SameMother ( x, y )
SameMother ( x, y )	<- Mother ( x, z ) ^ Mother ( y, z )
Youngster ( x )		<- Age ( x, a ) ^ LessThan ( a, 10 )
```
Apply the `Prolog-EBG` algorithm to the task of generalizing from the above instance, using the above domain theory. In particular,

1. Show a hand trace-trace of the `Prolog-EBG` algorithm applied to this problem; that is, show the explanation generated for the training instance, show the result of regressing the target concept through this explanation, and show the resulting Horn clause rule. -- Enough spaces so the pretty tree prints on the same page --
```

Joe  = J		HouseMates ( J, S )
Sue  = S			^
Mary = M			|
InSameFamily ( J, S )
^
________________|________________________
^			^		^
|			|		|
SameMother ( J, S )	Youngster ( J )		|
^			^		|
________|________________	|    Youngster ( S )
^			^	|		^
|			|	|	________|
Mother ( J, M )		Mother ( S, M )	|	^	^
________________________|	|	|
^	^			|	|
|	|		Age ( S, 6 )	|
|	|				|
Age ( J, 8 )	LessThan ( 8, 10 ) LessThan ( 6, 10 )
```

```			HouseMates ( x, y )
^
|
InSameFamily ( x, y )
^
________________|________________________
^			^		^
|			|		|
SameMother ( x, y )	Youngster ( x )		|
^			^		|
________|________________	|    Youngster ( y )
^			^	|		^
|			|	|	________|
Mother ( x, z )		Mother ( y, z )	|	^	^
________________________|	|	|
^	^			|	|
|	|		Age ( ya, 6 )	|
|	|				|
Age ( x, xa )	LessThan ( xa, 10 ) LessThan ( ya, 10 )
```

```HouseMates ( x, y ) <-	SameMother ( x, y ) ^
( Age ( x, xa ) ^ LessThan ( xa, 10 ) ) ^
( Age ( y, ya ) ^ LessThan ( ya, 10 ) )
```

2. Suppose that the target concept is "people who live with Joe" instead of "pairs of people who live together." Write down this target concept in terms of the above formalism. Assuming the same training instance and domain theory as before, what Horn clause rule will `Prolog-EBG` produce for this new target concept?
```LivesWithJoe ( y ) <-	SameMother ( Joe, y ) ^
( Age ( y, ya ) ^ LessThan ( ya, 10 ) )
```

by: Keith A. Pray  