## 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 language | English |
---|---|

Pages (from-to) | 1919-1938 |

Number of pages | 20 |

Journal | Journal of Machine Learning Research |

Volume | 6 |

State | Published - Dec 2005 |

## Keywords

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

## ASJC Scopus subject areas

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