Biased learning system

Claim 3

The method of claim 1 in which the information gain of the refined logic clause C i+1 with respect to the initial logic clause or refined logic clause being refined C i is defined as ##EQU3## where i is an integer greater than 0, T 1 + and T i - are the number of positive and negative examples respectively covered by C i and T i ++ is the number of positive examples covered by C i that are also covered by C i+1 .

Claim 4

In a method of using a computer to form a hypothesis for a target concept from (i) known relations and (ii) training data containing both positive and negative examples, said hypothesis including one or more logic clauses, which method includes the steps of: loading said known relations and said training data into said computer; in said computer: generating a logic clause for said hypothesis from said known relations, said logic clause being true for at least one of said positive examples but false for substantially all of said negative examples; removing from said training data the positive examples for which said logic clause is true; adding said logic clause to said hypothesis; and repeating said generating, removing and adding steps until substantially all said positive examples are removed; wherein said generating step includes the steps of: generating an initial logic clause; if said initial logic clause is true for negative examples, refining said initial logic clause; and if said refined clause is true for negative examples, repeating said refining step until said clause is no longer true for substantially all said negative examples; and wherein said refining step comprises the steps of: deriving a plurality of refinements of the clause being refined, calculating an information gain for each said refinement with respect to the clause being refined; and choosing the refinement with the highest information gain; the improvement comprising: creating an antecedent description grammar containing a plurality of rules defining permissible ways to generate said logic clauses from said known relations; loading said grammar into said computer; in each said generating step, generating said logic clauses in accordance with said grammar; and in each said refining step; deriving each refinement by applying the rules of said grammar in a nonlooping linear sequence.

Claim 5

In a method of using a computer to form a hypothesis for a target concept from (i) known relations and (ii) training data containing both positive and negative examples, said hypothesis including one or more logic clauses, which method includes the steps of: loading said known relations and said training data into said computer; in said computer: generating a logic clause for said hypothesis from said known relations, said logic clause being true for at least one of said positive examples but false for substantially all of said negative examples; removing from said training data the positive examples for which said logic clause is true; adding said logic clause to said hypothesis; and repeating said generating, removing and adding steps until substantially all said positive examples are removed; wherein said generating step includes the steps of: generating an initial logic clause; if said initial logic clause is true for negative examples, refining said initial logic clause; and if said refined clause is true for negative examples, repeating said refining step until said clause is no longer true for substantially all said negative examples; and wherein said refining step comprises the steps of: deriving a plurality of refinements of the clause being refined, calculating an information gain for each said refinement with respect to the clause being refined; and choosing the refinement with the highest information gain; the improvement comprising: creating an antecedent description grammar containing a plurality of rules defining permissible ways to generate said logic clauses from said known relations; loading said grammar into said computer; in each said generating step, generating said logic clauses in accordance with said grammar; and in each said refining step; deriving each refinement by applying the rules of said grammar in a nonlooping linear sequence.

Claim 6

The method of claim 1 wherein said antecedent description grammar is based on one or more of the following types of background knowledge about said target concept: background knowledge for avoiding vacuous predicates in said logic clauses, background knowledge about differences in types of variables, background knowledge in the form of useful programming constructs relevant to said target concept and background knowledge in the form of logic clauses that approximate said target concept.