A Polynomial Approach to the Constructive Induction of Structural Knowledge
Machine LearningPublished 1 February 1994Open access
Jörg-Uwe Kietz, Katharina Morik
Citations113
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
KLUSTER builds the most specific generalization and a most general discrimination in polynomial time and embeds these concept learning problems into the overall task of learning a hierarchy of concepts.
Abstract
S.193-217
Keywords
Computer Science
Machine LearningKnowledge Acquisition Via Incremental Conceptual Clustering
1,754 Citations1987Douglas Fisher
COBWEB is a conceptual clustering system that organizes data so as to maximize inference ability, and is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
Cognitive ScienceAn overview of the KL-ONE Knowledge Representation System
1,620 Citations1985R. J. Brachman, James G. Schmolze
The kernel ideas of KL-ONE are presented, emphasizing its ability to form complex structured descriptions, and notions of taxonomy and classification that are central to it are highlighted.
Machine LearningLearning Logical Definitions from Relations
1,425 Citations1990J. R. Quinlan
FOIL is a system that learns Horn clauses from data expressed as relations, but extends them to a first-order formalism, which has been applied successfully to several tasks taken from the machine learning literature.
The MIT Press eBooksAlgorithmic Program Debugging
1,094 Citations1983Ehud Shapiro
An algorithm that can fix a bug that has been identified, and integrate it with the diagnosis algorithms to form an interactive debugging system that can debug programs that are too complex for the Model Inference System to synthesize.
Machine LearningKnowledge acquisition via incremental conceptual clustering
1,081 Citations1987Douglas Fisher
COBWEB is a conceptual clustering system that organizes data so as to maximize inference ability, and is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
Artificial IntelligenceA theory and methodology of inductive learning
1,006 Citations1983Ryszard S. Michalski
The presented theory views inductive learning as a heuristic search through a space of symbolic descriptions, generated by an application of various inference rules to the initial observational statements.
Cognitive ScienceAn Overview of the KL‐ONE Knowledge Representation System*
977 Citations1985Ronald J. Brachman, James G. Schmolze
New Generation ComputingInductive logic programming
932 Citations1991Stephen Muggleton
A discussion of the feasibility of extending the RLGG framework to allow for the invention of new predicates and the possible relationship between Algorithmic Complexity theory and Probably-Approximately-Correct Learning is discussed.
Surveys in computer scienceLogic Programming and Databases
746 Citations1990Stefano Ceri, Georg Gottlob +1 more
Efficient Induction of Logic Programs
657 Citations1990Stephen Muggleton, Cheng Feng
The concept of h-easy rlgg clauses is introduced and it is proved that the length of a certain class of \determinate" r lgg is bounded by a polynomial function of certain features of the background knowledge.
ACM SIGMOD RecordCLASSIC: a structural data model for objects
504 Citations1989Alexander Borgida, Ronald J. Brachman +2 more
Elsevier eBooksMachine Invention of First-order Predicates by Inverting Resolution
441 Citations1988Stephen Muggleton, Wray Buntine
A mechanism for automatically inventing and generalising first-order Horn clause predicates is presented, based on inverting the mechanism of resolution, which has its roots in the Duce system for induction of propositional Horn clauses.
Lecture notes in computer scienceReasoning and Revision in Hybrid Representation Systems
401 Citations1990Bernhard Nebel
The universal term-forming formalism is a hybrid representation formalism that combines terminological cycles, representation and management of knowledge, and reasoning in the formalism.
Machine LearningExperiments with Incremental Concept Formation: UNIMEM
289 Citations1987Michael Lebowitz
UNIMEM is a robust program that can be run on many domains with real-world problem characteristics such as uncertainty, incompleteness, and large numbers of examples, including the automatic creation of non-disjoint concept hierarchies that are evaluated over time.
International Journal of Man-Machine StudiesWhat's in a concept: structural foundations for semantic networks
236 Citations1977Ronald J. Brachman
This paper examines the fundamentals of network notation, in order to understand why the “formalism” has not been the panacea it was once hoped to be and emphasizes the importance of considering an “epistemological foundation” on which to consistently build representations for complex concepts.
Computational Complexity of Machine Learning
229 Citations1990Michael Kearns
A centerpiece of the thesis is a series of results demonstrating the computational difficulty of learning a number of well-studied concept classes by reducing some apparently hard number-theoretic problems from cryptography to the learning problems.
Elsevier eBooksAN ESSENTIAL HYBRID REASONING SYSTEM: KNOWLEDGE AND SYMBOL LEVEL ACCOUNTS OF KRYPTON
222 Citations1989Ronald J. Brachman, Victoria Pigman Gilbert +1 more
This work gives here both a formal Knowledge Level view of the user interface to KRYPTON and the technical Symbol Level details of the integration of the two disparate components, thus providing an essential picture of the abstract function that KryPTON computes and the implementation technology needed to make it work.
CLASSIC: a structural data model for objects
216 Citations1989Alexander Borgida, Ronald J. Brachman +2 more
The kind of language of descriptions and queries presented here provides a new arena for the search for languages that are more expressive than conventional DBMS languages, but for which query processing is still tractable.
Machine LearningExperiments with incremental concept formation: UNIMEM
185 Citations1987Michael Lebowitz
UNIMEM is a robust program that can be run on many domains with real-world problem characteristics such as uncertainty, incompleteness, and large numbers of examples, including the automatic creation of non-disjoint concept hierarchies that are evaluated over time.
Conceptual Clustering: Inventing Goal-Oriented Classifications of Structured Objects
181 Citations1986Robert E. Stepp, Ryszard S. Michalski
Artificial IntelligenceGeneralized subsumption and its applications to induction and redundancy
172 Citations1988Wray Buntine
A theoretical framework and algorithms are presented that provide a basis for the study of induction of definite (Horn) clauses hinge on a natural extension of θ-subsumption that forms a strong model of generalization.
Machine LearningLearning Conjunctive Concepts in Structural Domains
154 Citations1989David Haussler
This class of concepts is formally defined, and it is shown that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, the learning algorithm is allowed to make subset queries.
Computing least common subsumers in description logics
150 Citations1992William W. Cohen, Alex Borgida +1 more
This paper introduces a new operation for description logics: computing the "least common subsumer" of a pair of descriptions, which computes the largest set of commonalities between two descriptions.
International Joint Conference on Artificial IntelligenceThe restricted language architecture of a hybrid representation system
144 Citations1985Marc Vilain
This paper describes KL-TWO, a hybrid reasoner based on the restricted representation facility RUP, and discusses KL- TWO, its subcomponents, and the techniques used to interface them.
Fraunhofer-Publica (Fraunhofer-Gesellschaft)Knowledge Acquisition and Machine Learning: Theory, Methods, and Applications
113 Citations1993Katharina Morik, Stefan Wrobel +2 more
Machine LearningLearning conjunctive concepts in structural domains
95 Citations1989David Haussler
This class of concepts is formally defined, and it is shown that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, the learning algorithm is allowed to make subset queries.
Lecture notes in computer scienceSome lower bounds for the computational complexity of inductive logic programming
51 Citations1993Jörg-Uwe Kietz
It is shown that a learning algorithm for i2-determinate Hornclauses (with variable i) could be used to decide the PSPACE-complete problem of Finite State Automata Intersection, and that a Learning Algorithm for 12-nondeterminates HornclAuses could be use to decision the NP-complete Problem of Boolean Clause Satisfiability (SAT).
The discovery of the equator or concept driven learning
42 Citations1983Werner Emde, Christopher Habel +1 more
This paper presents a model-driven method for machine learning of inference rules, which involves both: ' learning by induction' and 'learning by being told'.
Controlling the Complexity of Learning in Logic through Syntactic and Task-Oriented Models
37 Citations1991Jörg-Uwe Kietz, Stefan Wrobel
The BACK System Revisited
32 Citations1989Christof Peltason, Albrecht Schmiedel +2 more
The redesign and the implemention of the Berlin advanced computational knowledge representation system (in Prolog) are described and the overall knowledge base language is sketched, syntax and semantics are given, and the usage is illustrated by examples.
Learnability of description logics
29 Citations1992William W. Cohen, Haym Hirsh
A simple description logic is defined, some results on its expressive power are summarized, and its learnability is analyzed; it is shown that the full logic cannot be tractably learned; however, syntactic restrictions that enable tractable learning exist.
Elsevier eBooksINCREMENTAL CONCEPT FORMATION WITH COMPOSITE OBJECTS
26 Citations1989Kevin Thompson, Pat Langley
This chapter discusses incremental concept formation involving composite objects in a system called LABYRINTH, which borrows from COBWEB the basic principle of probabilistic concepts organized in a disjoint hierarchy, but it extends the representation language for instances and concepts.
Informatik-FachberichteHigher-order Concepts in a Tractable Knowledge Representation
17 Citations1987Stefan Wrobel
It is shown that metapredicates have the necessary properties to qualify for inclusion in a knowledge representation: they can be given a precise semantics, and allow a natural set of Inferences to be provided effectively.
Elsevier eBooksKBG: A Knowledge Based Generalizer
13 Citations1990Gilles Bisson
This paper presents a new generalization mechanism, inspired by the structural matching algorithm, which consists in using the domain theory in order to perform the saturation of the examples given by an expert.
Elsevier eBooksA BOOTSTRAPPING APPROACH TO CONCEPTUAL CLUSTERING
12 Citations1989Katharina Morik, Joerg-Uwe Kietz
This chapter reviews a bootstrapping approach to conceptual clustering based on an inference engine with facts and rules represented in a restricted first order predicate logic.
Lecture notes in computer scienceThe central role of explanations in disciple
11 Citations2005Yves Kodratoff, Gheorghe Tecuci
The central mechanism in DICIPLE is the one of explanations which is used in all the learning modes of DISCIPLE.
OpenGrey (Institut de l'Information Scientifique et Technique)Incremental and reversible acquisition of taxonomies
10 Citations1988Kietz, J.U., Berlin Technische Univ. (Germany). Fachbereich 20 - Informatik +1 more
OpenGrey (Institut de l'Information Scientifique et Technique)A Comparative Study Of Structural Most Specific Generalizations Used In Machine Learning
1 Citations1992Kietz, J.U. (Gesellschaft fuer Mathematik und Datenverarbeitung m.b.H. Bonn (GMD), St. Augustin (Germany). Inst. fuer Angewandte Informationstechnik), Gesellschaft fuer Mathematik und Datenverarbeitung m.b.H. Bonn (GMD), St. Augustin (Germany)