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 )
    

     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 )
    

---

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.

   
   	Joe  = J
   	Sue  = S
   	Mary = M
   			HouseMates ( J, S )
   				^
   				|
   		       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 ) ) 
         

---