"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

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.

Download this paper as a PDF file. (Size = 600 KB)

Visit Dr. Triantaphyllou's homepage.