|
Abstract : |
Question We want to predict the value of a hidden monotone Boolean function f: f maps vectors of n bits onto Boolean values, and if f(x) = 1 for a vector x, then flipping any bit of x from 0 to 1 keeps f(x) = 1. We would like to predict how the hidden function f will label a random bit vector x. For information about f, our algorithm can get a small number (polynomial in n) random bit vectors and the label f gives them. The question is this: What should we do to maximize our probability of agreeing with f(x) (no matter what f is---the probability is over the random choice of x), and what guarantee can we make about this probability? Guaranteeing 1=2 is easy---flip a coin---but how much better can we do? Motivation This question arises in learning settings where we want to predict a hidden function---whether a consumer will like granola bars, for example. We are given some history about the problems. One shopper who regularly buys Cheerios and raisins but not oatmeal liked granola bars; another who buys Cheerios but not not raisins or oatmeal did not. Should we offer granola bars to a shopper who buys only raisins? To make the problem tractable, we make assumptions about consistency, monotonicity, and uniformity: The function will always label a bit vector the same way (consistency); each 1 bit can only help, and no 0 bit can help (monotonicity); examples are uniformly distributed among the bit vectors (unifor-mity). Removing these makes the problem much more difficult (consistency) or even impossible (monotonicity and uniformity). (Impossible here prohibits guarantees of more than 1=2 + 1=poly(n), where poly(n) can be any polynomial in n.) Results The following table summarizes the history of the problem and our results. The algorithms represent known guarantees; the hardness results represent upper bounds on the most any algorithm can guarantee. (The hardness results are actually stronger: They hold even if the algorithm is allowed to choose the labeled bit vectors.) author algorithm hardness result, |
