Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation
Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation
复制标题
DOI：
10.1007/978-3-031-06901-7_21
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
R. Ghuge;Anupam Gupta;V. Nagarajan
中科院分区：
文献类型：
--
作者：
R. Ghuge;Anupam Gupta;V. Nagarajan
序贯测试问题涉及到一个复杂的系统，它有几个组件，每个组件都以某种独立的概率“工作”。每个组件的结果可以通过执行测试来确定，这会产生一些成本。整个系统的状态是由其组件的结果的函数给出的。目标是通过以最小的预期成本执行测试来评估此功能。虽然在这个主题上已经有了大量的工作，但可证明的近似界主要限于简单的函数，如“n中取k”和半空间。我们认为更一般的“得分分类”功能，我们提供了第一个常数因子近似算法（改善了以前的对数近似比）。此外，我们的策略是非自适应的;它只涉及以先验的固定顺序执行测试。我们还考虑了相关的半空间求值问题，其中我们想要在半空间上求值一些函数（例如，半空间的交集）。我们表明，我们的方法提供了一个近似算法这个问题。我们的算法还扩展到“批量”测试的设置，其中多个测试可以同时执行，同时产生额外的设置成本。最后，我们进行了计算实验，证明了我们的分数分类算法的实际性能。我们观察到，在大多数情况下，我们的算法的成本是在一个因素的1.5的信息理论下限的最优value.Funding：这项工作得到了支持的计算和通信基础司[赠款CCF-2006778和CCF-2006953]和土木，机械和制造业创新司[格兰特CMMI-1940766]。
Sequential testing problems involve a complex system with several components, each of which is “working” with some independent probability. The outcome of each component can be determined by performing a test, which incurs some cost. The overall system status is given by a functionfof the outcomes of its components. The goal is to evaluate this functionfby performing tests at the minimum expected cost. Although there has been extensive prior work on this topic, provable approximation bounds are mainly limited to simple functions, like “k-out-of-n” and half-spaces. We consider significantly more general “score classification” functions, and we provide the first constant-factor approximation algorithm (improving over a previous logarithmic approximation ratio). Moreover, our policy is nonadaptive; it just involves performing tests in an a priori fixed order. We also consider the related half-space evaluation problem, where we want to evaluate some function ondhalf-spaces (e.g., the intersection of half-spaces). We show that our approach provides an-approximation algorithm for this problem. Our algorithms also extend to the setting of “batched” tests, where multiple tests can be performed simultaneously while incurring an extra setup cost. Finally, we perform computational experiments that demonstrate the practical performance of our algorithm for score classification. We observe that, for most instances, the cost of our algorithm is within a factor of 1.5 of an information-theoretic lower bound on the optimal value.Funding:This work was supported by the Division of Computing and Communication Foundations [Grants CCF-2006778 and CCF-2006953] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-1940766].