New Horn revision algorithms

Judy Goldsmith, Robert H. Sloan

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the measured resource) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give efficient revision algorithms in the model of learning with equivalence and membership queries. The algorithms work in a general revision model where both deletion and addition revision operators are allowed. In this model one of the main open problems is the efficient revision of Horn formulas. Two revision algorithms are presented for special cases of this problem: for depth-1 acyclic Horn formulas, and for definite Horn formulas with unique heads.

Original languageEnglish
Pages (from-to)1919-1938
Number of pages20
JournalJournal of Machine Learning Research
Volume6
StatePublished - Dec 2005

Keywords

  • Computational learning theory
  • Exact learning
  • Horn formulas
  • Query learning
  • Theory revision

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'New Horn revision algorithms'. Together they form a unique fingerprint.

Cite this