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 = {Cicalese, Ferdinando and Laber, Eduardo and Saettler, Aline Medeiros}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {414--422}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, 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 = {https://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 %P 414--422 %U https://proceedings.mlr.press/v32/cicalese14.html %V 32 %N 1 %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 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-cicalese14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 414 EP - 422 L1 - http://proceedings.mlr.press/v32/cicalese14.pdf UR - https://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 Proceedings of Machine Learning Research 32(1):414-422 Available from https://proceedings.mlr.press/v32/cicalese14.html.

Related Material