Efficient Specialization of Relational Concepts

Abstract

This research note presents an algorithm for a common induction problem, the specialization of overly general concepts. A concept is too general when it matches a negative example. The particular case addressed here assumes that concepts are represented as conjunctions of predicates, that specialization is performed by conjoining predicates to the overly general concept, and that the resulting specializations are to be as general as possible. It is shown that the problem is simple if the concept representation language is propositional, but NP-complete if the language is first-order (i.e., relational). Nonetheless, there exists an algorithm, based on manipulator of bit vectors, that provides good average-case performance. Keywords: Machine learning; Artificial intelligence; Version spaces; Concept induction.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA222366

Entities

People

  • Kurt VanLehn

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Autonomy
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Science
  • Computers
  • Concept Formation
  • Coverings
  • Illinois
  • Information Science
  • Language
  • Learning
  • Machine Learning
  • Military Research
  • New York
  • Procurement
  • Psychology
  • Specialization
  • United States

Readers

  • Artificial Intelligence
  • Operations Research

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • Space