The Stochastic Score Classification Problem
The Stochastic Score Classification Problem
复制标题
随机分数分类问题
DOI：
10.4230/lipics.esa.2018.36
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Devorah Kletenik
中科院分区：
文献类型：
--
作者：
Dimitrios Gkenosis;Nathaniel Grammel;L. Hellerstein;Devorah Kletenik
考虑以下随机分数分类问题。医生正在评估病人患某种疾病的风险，并可以对病人进行n次测试。每个测试都有一个二元结果，阳性或阴性。阳性结果是风险的指示，患者的评分是阳性测试结果的总数。测试结果准确。医生需要根据评分将患者分类为B风险类别之一（例如，低、中、高风险）。这些类别中的每一个都对应于一个连续的分数范围。测试i为正的概率为p_i，执行成本为c_i。为了降低成本，医生将按顺序执行所有测试，并在可能确定患者的风险类别时停止测试，而不是执行所有测试。问题是确定医生应该进行测试的顺序，以便最大限度地减少预期的测试成本。我们提供近似算法的自适应和非自适应版本的这个问题，并提出了一些开放的问题。
Consider the following Stochastic Score Classification Problem. A doctor is assessing a patient's risk of developing a certain disease, and can perform n tests on the patient. Each test has a binary outcome, positive or negative. A positive result is an indication of risk, and a patient's score is the total number of positive test results. Test results are accurate. The doctor needs to classify the patient into one of B risk classes, depending on the score (e.g., LOW, MEDIUM, and HIGH risk). Each of these classes corresponds to a contiguous range of scores. Test i has probability p_i of being positive, and it costs c_i to perform. To reduce costs, instead of performing all tests, the doctor will perform them sequentially and stop testing when it is possible to determine the patient's risk category. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We provide approximation algorithms for adaptive and non-adaptive versions of this problem, and pose a number of open questions.