Theory Revision and Related Problems in Learning Theory

Theory revision is the correcting of a given, roughly correct rule, also known as a concept or theory. This problem arises frequently in machine learning, for instance, when the initial output of an expert system is not correct, and when the machine learning problem is too large or too complex to solve from scratch, and an approximately correct rule is needed to jump-start the learning process. There has been considerable ad hoc building of theory revision systems, but the theory is poorly understood. This research investigates fundamental mathematical possibilities and limitations of efficient theory revision. It is hoped that as a result of this research, theory revision in computational learning theory will emerge as a general framework for the study of learning situations where a large amount of initial information is available or necessary. In particular, the PIs investigate the following areas: extensions of their previous work on propositional logic theory revision with queries, relations to certificate complexity and attribute-efficient learning, revision problems for predicate logic representations, and both the learning and revising of categorial grammars.