Loading...
Loading...

Go to the content (press return)

Exact learning when irrelevant variable abound

Author
Guijarro, D.; Lavin, V.; Raghavan, V.
Type of activity
Report
Date
1998-11
Code
R98-59
Repository
http://hdl.handle.net/2117/84907 Open in new window
Abstract
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...
Citation
Guijarro Guillem, David; Lanvín, Víctor; Raghavan, Vijay. "Exact learning when irrelevant variables abound". 1998.
Keywords
Boolean functions, Irrelevant variables

Participants

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

Attachments