2013/09/11 by Ferdinando Cicalese, Cicalese, Ferdinando, Eduardo Sany Laber +5 · 2 citations
Computer Science · #68Q25 #68Q32 #68T05 #68W25 #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #F.2 #F.2.2 #FOS: Computer and information sciences #I.2 #I.2.6 #Machine Learning (cs.LG) #Machine Learning and Algorithms #Neural Networks and Applications #Rough Sets and Fuzzy Logic #acm:68Q25 #acm:68Q32 #acm:68T05 #acm:68W25 #cs.AI #cs.DS #cs.LG #msc:68Q25 #msc:68Q32 #msc:68T05 #msc:68W25
paper · pdf · doi:10.48550/arxiv.1309.2796
A preliminary version of this paper was accepted for presentation at ICML 2014
openalex publication_date 2013/09/11 · arxiv created 2014/07/26 · arxiv updated 2014/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, the process of reading the value of a variable might involve some cost, computational or even a fee to be paid for the experiment required for obtaining the value. This cost should be taken into account when deciding the next variable to read. 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 approxima- tion simultaneously for the expected and worst cost spent. This is best possible under the assumption that P ≠ NP.