Exercise 2.9

1. Consider a learning problem where each instance is described by a conjunction of n boolean attributes a ₁ . . . a _n. Thus, a typical instance would be
   
   

   ( a ₁ = T ) && ( a ₂ = F ) && . . . && ( a _n = T )

   Now consider a hypothesis space H in which each hypothesis is a disjunction of constraints over these attributes. For example, a typical hypothesis would be
   
   

   ( a ₁ = T ) || ( a ₅ = F ) || ( a ₇ = T )

   Propose an algorithm that accepts a sequence of training examples and outputs a consistent hypothesis if one exists. Your algorithm should run in time that is polynomial in n and in the number or training examples.

I just don't get it yet...

Note: I was very right about not getting it. This answer is all ookie. Maybe some day I'll put the correct answer here... but would you care? Well, if you do, then write me already.

OK, someone did write asking for the answer. I have to dig up my notebook for the course and see what I can see. Reading the question now, I'm surprised I ever understood what it meant. :^)