Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Exact learning when irrelevant variable abound

Autor
Guijarro, D.; Lavin, V.; Raghavan, V.
Tipus d'activitat
Document cientificotècnic
Data
1998-11
Codi
R98-59
Repositori
http://hdl.handle.net/2117/84907 Obrir en finestra nova
Resum
We prove the following results. Any Boolean function of O(log n) relevant variables can be exactly learned with a set of non-adaptive membership queries alone and a minimum sized decision tree representation of the function constructed, in polynomial time. In contrast, such a function cannot be exactly learned with equivalence queries alone using general decision trees and other representation classes as hypotheses. Our results imply others which may be of independent interest. We show...
Citació
Guijarro Guillem, David; Lanvín, Víctor; Raghavan, Vijay. "Exact learning when irrelevant variables abound". 1998.
Paraules clau
Boolean functions, Irrelevant variables

Participants

  • Guijarro Guillem, David  (autor)
  • Lavin, V  (autor)
  • Raghavan, V  (autor)

Arxius