Biased learning system

Claim 1

In a computer system, an improved apparatus for inducing a hypothesis which is employed to automatically classify items of data from a set of the data items in which each item has been labelled with the item's classification, the apparatus being of the type comprising: means for learning the hypothesis from the set of the data items, means for biasing the means for learning to narrow a hypothesis space within which the means for learning operates, and the improvement comprising in the means for biasing: a) entities which are mappable to hypotheses to determine whether a given hypothesis is consistent with a given entity and thereby narrow the hypothesis space; b) means for generating the entities, with, i) each entity being generated by a sequence of transformations which follow rules of grammar, beginning from an initial entity and ii) each transformation being such that a later entity produced by a transformation from an earlier entity restricts the hypothesis space to a greater degree than the earlier entity does; and c) input means for receiving an antecedent description grammar, designed by a user, which defines the rules of grammar which must be followed in transforming the entities.

Claim 3

A method for narrowing a hypothesis space in computer apparatus for inducing a hypothesis which is employed to automatically classify items of data from a set of the data items in which each item has been labelled with the item's classification, the method comprising the steps of: a) receiving an antecedent description grammar which was designed by a user, and which defines rules which transformations of entities must follow; b) employing the antecedent description grammar to generate entities which are mappable to hypotheses to determine whether a given hypothesis is consistent with a given entity, i) the antecedent description grammar defining a set of transformations and ii) each entity being generated by a sequence of the transformations beginning from an initial entity, and iii) each transformation being such that a later entity produced by a transformation from an earlier entity restricts the hypothesis space to a greater degree than does the earlier entity; and b) employing the entities to narrow the hypothesis space.

Claim 4

A method for narrowing a hypothesis space in computer apparatus for inducing a hypothesis which is employed to automatically classify items of data from a set of the data items in which each item has been labelled with the item's classification, the method comprising the steps of: a) receiving an antecedent description grammar which was designed by a user, and which defines rules which transformations of entities must follow; b) employing the antecedent description grammar to generate entities which are mappable to hypotheses to determine whether a given hypothesis is consistent with a given entity, i) the antecedent description grammar defining a set of transformations and ii) each entity being generated by a sequence of the transformations beginning from an initial entity, and iii) each transformation being such that a later entity produced by a transformation from an earlier entity restricts the hypothesis space to a greater degree than does the earlier entity; and b) employing the entities to narrow the hypothesis space.

Claim 5

A method of using a computer to derive a collection of one or more clauses which describe a set of training examples, comprising the following steps: a) accepting from a user i) a grammar which specifies operations permitted in deriving Horn clauses, ii) the set of training examples, in which some are defined as positive, and some as negative; b) repeatedly performing the following steps until all positive training examples are covered by a Horn clause: i) generating a Horn clause, using steps permitted by the grammar; ii) using a Horn theorem-prover, A) inquiring whether the Horn clause covers negative examples and, if so, modifying the Horn clause so that it covers no negative examples; and B) inquiring whether the Horn clause, as modified if required in paragraph (A), covers positive examples and, if so, adding the Horn clause to the collection.

Claim 6

A method of using a computer to derive a collection of one or more clauses which describe a set of training examples, comprising the following steps: a) accepting from a user i) a grammar which specifies operations permitted in deriving Horn clauses, ii) the set of training examples, in which some are defined as positive, and some as negative; b) repeatedly performing the following steps until all positive training examples are covered by a Horn clause: i) generating a Horn clause, using steps permitted by the grammar; ii) using a Horn theorem-prover, A) inquiring whether the Horn clause covers negative examples and, if so, modifying the Horn clause so that it covers no negative examples; and B) inquiring whether the Horn clause, as modified if required in paragraph (A), covers positive examples and, if so, adding the Horn clause to the collection.