Discovering Substructure in Examples

Abstract

This thesis describes a method for discovering substructure concepts in examples. The method involves a computationally constrained best-first search guided by four heuristics: cognitive savings, compactness, connectivity and coverage. Each heuristic is described in detail along with its role in evaluating an individual substructure concept. The SUBDUE computer program that implements the method contains a substructure discovery module, a substructure specialization module and an incremental substructure background knowledge module for applying previously discovered substructures in a hierarchy that is used to determine which substructures are present in the input examples. The system has performed well on a number of examples from different domains and has discovered many interesting substructure concepts such as an aromatic ring and a macro-operator for stacking blocks. The method and implementation of the SUBDUE system are described, and an analysis of experimental results is presented.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1988
Accession Number
ADA197778

Entities

People

  • Lawrence B. Holder Jr

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Autonomy
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Artificial Intelligence
  • Atoms
  • Automata Theory
  • Chemistry
  • Cognition
  • Cognitive Science
  • Computational Science
  • Computer Languages
  • Computer Programs
  • Computer Science
  • Computer Vision
  • Computers
  • Identification
  • Machine Learning
  • Organic Chemistry
  • Psychological Theory
  • Psychology

Readers

  • Neural Network Machine Learning.
  • Systems Analysis and Design