Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost

Ferdinando Cicalese, Eduardo Laber, Aline Medeiros Saettler
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):414-422, 2014.

Abstract

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). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP.

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-cicalese14, title = {Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost}, author = {Ferdinando Cicalese and Eduardo Laber and Aline Medeiros Saettler}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {414--422}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/cicalese14.pdf}, url = {http://proceedings.mlr.press/v32/cicalese14.html}, abstract = {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). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP.} }
Endnote
%0 Conference Paper %T Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost %A Ferdinando Cicalese %A Eduardo Laber %A Aline Medeiros Saettler %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-cicalese14 %I PMLR %J Proceedings of Machine Learning Research %P 414--422 %U http://proceedings.mlr.press %V 32 %N 1 %W PMLR %X 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). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP.
RIS
TY - CPAPER TI - Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost AU - Ferdinando Cicalese AU - Eduardo Laber AU - Aline Medeiros Saettler BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-cicalese14 PB - PMLR SP - 414 DP - PMLR EP - 422 L1 - http://proceedings.mlr.press/v32/cicalese14.pdf UR - http://proceedings.mlr.press/v32/cicalese14.html AB - 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). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP. ER -
APA
Cicalese, F., Laber, E. & Saettler, A.M.. (2014). Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(1):414-422

Related Material