Patent Document ID: 5481650
Application ID: 08320102

Base Claim:
1. 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 comprises the steps of: creating an antecedent description grammar containing a plurality of rules defining permissible ways to generate said logic clauses from said known relations; loading said training data and said grammar into said computer; in said computer: generating a logic clause for said hypothesis in accordance with said grammar, 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 comprises the steps of: formulating an initial logic clause in accordance with said grammar; 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, each refinement being derived by applying the rules of said grammar in a nonlooping linear sequence; calculating an information gain for each said refinement with respect to the clause being refined; and choosing the refinement with the highest information gain.

---

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