Matters Horn and other features in the computational learning theory landscape: The notion of membership

Abstract

Current knowledge representation research has sought to provide schemes for encoding knowledge about how a given system behaves, with the goal being accuracy and utility. Ideally, the goal of encoding knowledge is not the task of encoding, but the product of the encoding task. If such encodings are required for a variety of systems, then question of automating the process of encoding arises.

This thesis considers this automation process to be a question of whether it is possible to automatically learn the encoding based on the behavior of the system to be described. A variety of representation languages ${\cal L}$ are considered, as are a variety of means for the learner to acquire a variety of types of data about the system in question. The learning process is abstracted as a learning problem in which the goal is to collect efficiently sufficient information to identify some hidden concept C represented using the language ${\cal L}$. The source of information about C is its relationship to some class of examples ${\cal X}$ that is assumed to be reasonably available even though C itself is not. In addition to conjecturing guesses as to the identity of C, the learner is permitted ask how C relates to individuals $x \in {\cal X}$. The goal of inquiry about this automation process is either to produce a learning algorithm that efficiently automates the encoding of any representation that uses some useful representation language ${\cal L}$ or to show that no such learning algorithm is possible. The centerpiece of this thesis is that there do exist learning algorithms for two natural representation languages: propositional Horn sentences and the C scLASSIC description logic.