Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

Fast Learning of k-Term DNF Formulas with Queries

1995; Elsevier BV; Volume: 51; Issue: 3 Linguagem: Inglês

10.1006/jcss.1995.1075

ISSN

1090-2724

Autores

Avrim Blum, Steven Rudich,

Tópico(s)

Imbalanced Data Classification Techniques

Resumo

This paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term DNF formulas in time n · 2O(k), where n is the number of input variables. This improves upon previous O(nk) bounds and allows one to learn DNF formulas of O(log n) terms in polynomial time. We present the algorithm in its most natural form as a randomized algorithm and then show how recent derandomization techniques can be used to make it deterministic. The algorithm is an exact learning algorithm, but one where the equivalence query hypotheses and the final output are general (not necessarily k-term) DNF formulas. For the special case of two-term DNF formulas, we give a simpler version of our algorithm that uses at most 4n + 2 total membership and equivalence queries.

Referência(s)