On parallel attribute-efficient learning

✍ Scribed by Peter Damaschke

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 209 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00047-3

✦ Synopsis

This paper continues our earlier work on (non)adaptive attribute-efficient learning. We consider exact learning of Boolean functions of n variables by membership queries, assuming that at most r variables are relevant. The learner works in consecutive rounds, such that the set of simultaneous queries in every round may depend on all information gained so far. For deterministic learning of specific monotone functions we prove that any strategy that uses an optimal query number needs YðrÞ rounds in the worst case. Furthermore, we make some progress regarding the constant factors in nearly query-optimal strategies. For example, we propose a strategy using roughly 2 rþ1 þ 2Z log 2 n queries in 3r rounds. In contrast to the limitations of deterministic strategies, there is a randomized strategy that learns monotone functions by 2 O ðrÞ þ Oðr log nÞ expected queries in Oðlog rÞ expected rounds. Actually, this result holds in more general function classes. The second part of the paper addresses the computational complexity of parallel learning of arbitrary Boolean functions with r relevant variables. We obtain several strategies which use a constant number of rounds, Oð2 r polyðr log nÞÞ queries, and only 2 OðrÞ n polyðlog nÞ computations.