Symbolic Revision of Theories with M-of-N Rules

Abstract

This paper presents a major revision of the Either propositional theory refinement system. Two issues are discussed. First, we show how run time efficiency can be greatly improved by changing from a exhaustive scheme for computing repairs to an iterative greedy method. Second, we show how to extend Either to refine M-of-N rules. The resulting algorithm, Neither (New Either), is more than an order of magnitude faster and produces significantly more accurate results with theories that fit the M-of-N format. To demonstrate the advantages of Neither, we present preliminary experimental results comparing it to Either and various other systems on refining the DNA promoter domain theory. 1 Introduction Recently, a number of machine learning systems have been developed that use examples to revise an approximate (incomplete and/or incorrect) domain theory [ Ginsberg, 1990; Ourston and Mooney, 1990; Towell and Shavlik, 1991; Danyluk, 1991; Whitehall et al., 1991; Matwin and Plante, 1991 ] . ...