We study the problem of evaluating a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. Reading the value of a variable is done at the expense of some cost, and the goal is to design a strategy (decision tree) for evaluating the function incurring as little cost as possible in the worst case or in expectation (according to a prior distribution on the possible variables assignments). Except for particular cases of the problem, in general, only the minimization of one of these two measures is addressed in the literature. However, there are instances of the problem for which the minimization of one measure leads to a strategy with a high cost with respect to the other measure (even exponentially bigger than the optimal). We provide a new construction which can guarantee a trade-off between the two criteria. More precisely, given a decision tree guaranteeing expected cost @math and a decision tree guaranteeing worst cost @math our method can guarantee for any chosen trade-off value @math to produce a decision tree whose worst cost is @math and whose expected cost is @math These bounds are improved for the relevant case of uniform testing costs. Motivated by applications, we also study a variant of the problem where the cost of reading a variable depends on the variable's value. We provide an @math approximation algorithm for the minimization of the worst cost measure, which is best possible under the assumption @math .
Note that the questions we are studying here are different and possibly more fundamental than those studied in @cite_11 : is it possible, even allowing exponential construction time, to build a decision tree whose expected cost is very close to the best possible expected cost achievable and whose worst testing cost is very close to the best possible worst case achievable? How close can we get or better what is the best trade off we can simultaneously guarantee?
@cite_11
2128028322
In several applications of automatic diagnosis and active learning a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the corresponding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables' assignments). Our algorithm builds a strategy (decision tree) which attains a logarithmic approximation simultaneously for the expected and worst cost spent. This is best possible since, under standard complexity assumption, no algorithm can guarantee o(log n) approximation.