Document Open Access Logo

The Stochastic Score Classification Problem

Authors Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.36.pdf
  • Filesize: 487 kB
  • 14 pages

Document Identifiers

Author Details

Dimitrios Gkenosis
  • Department of Informatics and Telecommunications, University of Athens, Athens, Greece
Nathaniel Grammel
  • Department of Computer Science, University of Maryland, College Park, Maryland, USA
Lisa Hellerstein
  • Department of Computer Science and Engineering, NYU Tandon School of Engineering, Brooklyn, NY, USA
Devorah Kletenik
  • Department of Computer and Information Science, Brooklyn College, CUNY, Brooklyn, New York, USA

Funding

The authors were partially supported by NSF Award IIS-1217968.
  • Kletenik, Devorah: Partially supported by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City University of New York

Cite As Get BibTex

Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, and Devorah Kletenik. The Stochastic Score Classification Problem. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.36

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • approximation algorithms
  • symmetric Boolean functions
  • stochastic probing
  • sequential testing
  • adaptivity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jayadev Acharya, Ashkan Jafarpour, and Alon Orlitsky. Expected query complexity of symmetric Boolean functions. In IEEE 49th Annual Allerton Conference on Communication, Control, and Computing, pages 26-29, 2011. Google Scholar
  2. Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik, and Tonguç Ünlüyurt. Evaluation of monotone dnf formulas. Algorithmica, 77(3):661-685, 2017. Google Scholar
  3. Eric Bach, Jérémie Dusart, Lisa Hellerstein, and Devorah Kletenik. Submodular goal value of boolean functions. Discrete Applied Mathematics, 238:1-13, 2018. URL: http://dx.doi.org/10.1016/j.dam.2017.10.022.
  4. Yosi Ben-Dov. Optimal testing procedure for special structures of coherent systems. Management Science, 1981. Google Scholar
  5. Endre Boros and Tonguç. Ünlüyurt. Diagnosing double regular systems. Annals of Mathematics and Artificial Intelligence, 26(1-4):171-191, September 1999. URL: http://dx.doi.org/10.1023/A:1018958928835.
  6. Ming-Feng Chang, Weiping Shi, and Kent Fuchs, W.Ȯptimal diagnosis procedures for k-out-of-n structures. IEEE Transactions on Computers, 39(4):559-564, April 1990. Google Scholar
  7. Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, and Ananda Theertha Suresh. On the query computation and verification of functions. In IEEE International Symposium on Information Theory (ISIT), pages 2711-2715, 2012. Google Scholar
  8. Amol Deshpande, Lisa Hellerstein, and Devorah Kletenik. Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack. ACM Trans. Algorithms, 12(3):42:1-42:28, April 2016. URL: http://dx.doi.org/10.1145/2876506.
  9. Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, and Devorah Kletenik. The stochastic score classification problem. CoRR, 2018. URL: http://arxiv.org/abs/1806.10660.
  10. Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486, 2011. Google Scholar
  11. Daniel Golovin and Andreas Krause. Adaptive submodularity: A new approach to active learning and stochastic optimization (version 5). CoRR, abs/1003.3967, 2017. URL: http://arxiv.org/abs/1003.3967.
  12. Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, and Patrick Lin. Scenario submodular cover. In Proceedings of the 14th International Workshop on Approximation and Online Algorithms, pages 116-128. Springer, 2016. Google Scholar
  13. Russell Greiner, Ryan Hayward, Magdalena Jankowska, and Michael Molloy. Finding optimal satisficing strategies for and-or trees. Artificial Intelligence, 170(1):19-58, 2006. Google Scholar
  14. Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In International Conference on Integer Programming and Combinatorial Optimization, pages 205-216. Springer, 2013. Google Scholar
  15. Jongbin Jung, Connor Concannon, Ravi Shroff, Sharad Goel, and Daniel G Goldstein. Simple rules for complex decisions. arXiv preprint arXiv:1702.04690, 2017. Google Scholar
  16. Prabhanjan Kambadur, Viswanath Nagarajan, and Fatemeh Navidi. Adaptive submodular ranking. In International Conference on Integer Programming and Combinatorial Optimization, pages 317-329. Springer, 2017. Google Scholar
  17. Hemant Kowshik and PR Kumar. Optimal computation of symmetric boolean functions in collocated networks. IEEE Journal on Selected Areas in Communications, 31(4):639-654, 2013. Google Scholar
  18. Feng Nan and Venkatesh Saligrama. Comments on the proof of adaptive stochastic set cover based on adaptive submodularity and its implications for the group identification problem in "group-based active query selection for rapid diagnosis in time-critical situations". IEEE Trans. Information Theory, 63(11):7612-7614, 2017. URL: http://dx.doi.org/10.1109/TIT.2017.2749505.
  19. Salam Salloum. Optimal testing algorithms for symmetric coherent systems. PhD thesis, University of Southern California, 1979. Google Scholar
  20. Salam Salloum and Melvin Breuer. An optimum testing algorithm for some symmetric coherent systems. Journal of Mathematical Analysis and Applications, 101(1):170 - 194, 1984. URL: http://dx.doi.org/10.1016/0022-247X(84)90064-7.
  21. Salam Salloum and Melvin A. Breuer. Fast optimal diagnosis procedures for k-out-of-n:g systems. IEEE Transactions on Reliability, 46(2):283-290, Jun 1997. URL: http://dx.doi.org/10.1109/24.589958.
  22. Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2523-2532. SIAM, 2018. Google Scholar
  23. Truyen Tran, Wei Luo, Dinh Phung, Jonathan Morris, Kristen Rickard, and Svetha Venkatesh. Preterm birth prediction: Deriving stable and interpretable rules from high dimensional data. In Conference on Machine Learning in Healthcare, LA, USA, 2016. Google Scholar
  24. Tonguç Ünlüyurt. Sequential testing of complex systems: a review. Discrete Applied Mathematics, 142(1-3):189-205, 2004. Google Scholar
  25. Berk Ustun and Cynthia Rudin. Supersparse linear integer models for optimized medical scoring systems. Machine Learning, 102(3):349-391, 2016. Google Scholar
  26. Berk Ustun and Cynthia Rudin. Optimized risk scores. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1125-1134. ACM, 2017. Google Scholar
  27. Jiaming Zeng, Berk Ustun, and Cynthia Rudin. Interpretable classification models for recidivism prediction. Journal of the Royal Statistical Society: Series A (Statistics in Society), 180(3):689-722, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact