Browsing by Author "Barcelo, Pablo"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Screening of COVID-19 cases through a Bayesian network symptoms model and psychophysical olfactory test
    (CELL PRESS, 2021) Eyheramendy, Susana; Saa, Pedro A.; Undurraga, Eduardo A.; Valencia, Carlos; Lopez, Carolina; Mendez, Luis; Pizarro Berdichevsky, Javier; Finkelstein Kulka, Andres; Solari, Sandra; Salas, Nicolas; Bahamondes, Pedro; Ugarte, Martin; Barcelo, Pablo; Arenas, Marcelo; Agosin, Eduardo
    The sudden loss of smell is among the earliest and most prevalent symptoms of COVID-19 when measured with a clinical psychophysical test. Research has shown the potential impact of frequent screening for olfactory dysfunction, but existing tests are expensive and time consuming. We developed a low-cost ($0.50/test) rapid psychophysical olfactory test (KOR) for frequent testing and a model-based COVID-19 screening framework using a Bayes Network symptoms model. We trained and validated the model on two samples: suspected COVID-19 cases in five healthcare centers (n = 926; 33% prevalence, 309 RT-PCR confirmed) and healthy miners (n = 1,365; 1.1% prevalence, 15 RT-PCR confirmed). The model predicted COVID-19 status with 76% and 96% accuracy in the healthcare and miners samples, respectively (healthcare: AUC = 0.79 [0.75-0.82], sensitivity: 59%, specificity: 87%; miners: AUC = 0.71 [0.63-0.79], sensitivity: 40%, specificity: 97%, at 0.50 infection probability threshold). Our results highlight the potential for low-cost, frequent, accessible, routine COVID-19 testing to support society's reopening.
  • No Thumbnail Available
    Item
    The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
    (ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE, 2021) Arenas, Marcelo; Barcelo, Pablo; Bertossi, Leopoldo; Monet, Mikael
    Scores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP - score, a version of the Shapley value that can help explain the result of a learned model on a specific entity by assigning a score to every feature. While in general computing Shapley values is a computationally intractable problem, it has recently been claimed that the SHAP-score can be computed in polynomial time over the class of decision trees. In this paper, we provide a proof of a stronger result over Boolean models: the SHAP -score can be computed in polynomial time over deterministic and decomposable Boolean circuits. Such circuits, also known as tractable Boolean circuits, generalize a wide range of Boolean circuits and binary decision diagrams classes, including binary decision trees, Ordered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). We also establish the computational limits of the notion of SHAP-score by observing that, under a mild condition, computing it over a class of Boolean models is always polynomially as hard as the model counting problem for that class. This implies that both determinism and decomposability are essential properties for the circuits that we consider, as removing one or the other renders the problem of computing the SHAP-score intractable (namely, #P-hard).