An Augmented EBL and its Application to the Utility Problem

Abstract

EBL can learn justified generalizations from only one example when the domain theory is perfect. However, it does not work when the domain theory is imperfect. Imperfectness of the domain theory can be classified into four levels, i.e. incomplete, intractable, inconsistent and non-operational ones. It is necessary to unify EBL and SBL to solve these problems. In this paper, we propose a framework of an augmented EBL to handle plural examples simultaneously. We formalize it on logic program, and introduce a concept of least EBG to extract similarities from plural examples. We discuss on an approach to solve utility problem with the augmented EBL. Utility problem is a problem to learn more efficient description under complete, tractable, consistent but nonoperational domain theories. We define operationality criteria with maximizing usage degree and minimizing backtracking number, and show they increase partial monotonically by generalization. Since this partial monotinicity is not preferable to search operational generalizations, least EBGs are more operational than usual EBGs. We design a simple incremental learner based on least EBGs, and show its usefulness in recursive domain theories. We also discuss on other imperfect theory problems.