"Minimizing the Average Query Complexity of Learning Monotone Boolean Functions"
INFORMS Journal of Computing,
Vol. 14, No. 2, pp. 142-172, 2002.
Vetle I. Torvik and
Evangelos Triantaphyllou
Abstract:
This paper addresses the problem of completely reconstructing
deterministic monotone boolean functions via membership queries.
The minimum average query complexity is guaranteed via recursion,
where partially ordered sets (posets) make up the overlapping
subproblems. The optimality conditions for all the 4,688 posets
generated for the problem with up to 5 variables are summarized
in the form of an evaluative criterion. The evaluative criterion
extends the computational feasibility up to problems involving
about 20 variables. A framework for unbiased average case
comparison of monotone boolean function inference algorithms is
developed using unequal probability sampling. Empirical results
show that an implementation of the subroutine considered as a
standard in the literature performs more than twice as many
queries than the evaluative criterion on the average for 8
variables, and the gap increases with the number of variables.
It should also be noted that the first algorithm ever designed
for this problem performed consistently within 2% of the
evaluative criterion, and consequently prevails, by far, as the
most efficient of the many pre-existing algorithms.
Key Words:
Computational learning, Monotone boolean functions, Membership
queries, Average case complexity, Recursion, Partially ordered
sets (posets), Isomorphism, Greedy algorithm, Unequal probability
sampling, Unbiased estimators.
(Size = 600 KB)
