## Abstract

A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for Horn formulas and read-once formulas, where revision operators are restricted to deletions of variables or clauses, and for parity formulas, where revision operators include both deletions and additions of variables. We also show that the query complexity of the read-once revision algorithm is near-optimal.

Original language | English |
---|---|

Pages (from-to) | 139-176 |

Number of pages | 38 |

Journal | Artificial Intelligence |

Volume | 156 |

Issue number | 2 |

DOIs | |

State | Published - Jul 2004 |

### Bibliographical note

Funding Information:Keywords: Theory revision; Knowledge revision; Horn formulas; Query learning; Computational learning theory; Boolean function learning * Corresponding author. E-mail addresses: [email protected] (J. Goldsmith), [email protected] (R.H. Sloan), [email protected] (B. Szörényi), [email protected] (G. Turán). 1 Partially supported by NSF grant CCR-0100040. 2 Partially supported by NSF grants CCR-9800070 and CCR-0100336. 3 Partially supported by NSF grants CCR-0100336 and CCR-9800070.

### Funding

Keywords: Theory revision; Knowledge revision; Horn formulas; Query learning; Computational learning theory; Boolean function learning * Corresponding author. E-mail addresses: [email protected] (J. Goldsmith), [email protected] (R.H. Sloan), [email protected] (B. Szörényi), [email protected] (G. Turán). 1 Partially supported by NSF grant CCR-0100040. 2 Partially supported by NSF grants CCR-9800070 and CCR-0100336. 3 Partially supported by NSF grants CCR-0100336 and CCR-9800070.

Funders | Funder number |
---|---|

National Science Foundation (NSF) | CCR-0100040, CCR-0100336, CCR-9800070 |

Directorate for Computer and Information Science and Engineering | 0100336, 9800070, 0100040 |

## Keywords

- Boolean function learning
- Computational learning theory
- Horn formulas
- Knowledge revision
- Query learning
- Theory revision

## ASJC Scopus subject areas

- Language and Linguistics
- Linguistics and Language
- Artificial Intelligence