SAT-Based Encodings for Optimal Decision Trees with Explicit Paths
Ontology highlight
ABSTRACT:
SUBMITTER: Pulina L
PROVIDER: S-EPMC7326558 | biostudies-literature | 2020 Jun
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:The 'Ending the HIV Epidemic (EHE)' national plan aims to reduce annual HIV incidence in the United States from 38,000 in 2015 to 9300 by 2025 and 3300 by 2030. Diagnosis and treatment are two most effective interventions, and thus, identifying corresponding optimal combinations of testing and retention-in-care rates would help inform implementation of relevant programs. Considering the dynamic and stochastic complexity of the disease and the time dynamics of decision-making, solving for optimal combinations using commonly used methods of parametric optimization or exhaustive evaluation of pre-selected options are infeasible. Reinforcement learning (RL), an artificial intelligence method, is ideal; however, training RL algorithms and ensuring convergence to optimality are computationally challenging for large-scale stochastic problems. We evaluate its feasibility in the context of the EHE goal. We trained an RL algorithm to identify a 'sequence' of combinations of HIV-testing and retention-in-care rates at 5-year intervals over 2015-2070 that optimally leads towards HIV elimination. We defined optimality as a sequence that maximizes quality-adjusted-life-years lived and minimizes HIV-testing and care-and-treatment costs. We show that solving for testing and retention-in-care rates through appropriate reformulation using proxy decision-metrics overcomes the computational challenges of RL. We used a stochastic agent-based simulation to train the RL algorithm. As there is variability in support-programs needed to address barriers to care-access, we evaluated the sensitivity of optimal decisions to three cost-functions. The model suggests to scale-up retention-in-care programs to achieve and maintain high annual retention-rates while initiating with a high testing-frequency but relaxing it over a 10-year period as incidence decreases. Results were mainly robust to the uncertainty in costs. However, testing and retention-in-care alone did not achieve the 2030 EHE targets, suggesting the need for additional interventions. The results from the model demonstrated convergence. RL is suitable for evaluating phased public health decisions for infectious disease control.
| S-EPMC8613448 | biostudies-literature
Project description:Each sphere of knowledge and information could be depicted as a complex mesh of correlated items. By properly exploiting these connections, innovative and more efficient navigation strategies could be defined, possibly leading to a faster learning process and an enduring retention of information. In this work we investigate how the topological structure embedding the items to be learned can affect the efficiency of the learning dynamics. To this end we introduce a general class of algorithms that simulate the exploration of knowledge/information networks standing on well-established findings on educational scheduling, namely the spacing and lag effects. While constructing their learning schedules, individuals move along connections, periodically revisiting some concepts, and sometimes jumping on very distant ones. In order to investigate the effect of networked information structures on the proposed learning dynamics we focused both on synthetic and real-world graphs such as subsections of Wikipedia and word-association graphs. We highlight the existence of optimal topological structures for the simulated learning dynamics whose efficiency is affected by the balance between hubs and the least connected items. Interestingly, the real-world graphs we considered lead naturally to almost optimal learning performances.
| S-EPMC4450758 | biostudies-literature
Project description:For decades now, normative theories of perceptual decisions, and their implementation as drift diffusion models, have driven and significantly improved our understanding of human and animal behaviour and the underlying neural processes. While similar processes seem to govern value-based decisions, we still lack the theoretical understanding of why this ought to be the case. Here, we show that, similar to perceptual decisions, drift diffusion models implement the optimal strategy for value-based decisions. Such optimal decisions require the models' decision boundaries to collapse over time, and to depend on the a priori knowledge about reward contingencies. Diffusion models only implement the optimal strategy under specific task assumptions, and cease to be optimal once we start relaxing these assumptions, by, for example, using non-linear utility functions. Our findings thus provide the much-needed theory for value-based decisions, explain the apparent similarity to perceptual decisions, and predict conditions under which this similarity should break down.
| S-EPMC4992126 | biostudies-literature
Project description:The objective consensus methodology has recently been applied in consensus finding in several studies on medical decision-making among clinical experts or guidelines. The main advantages of this method are an automated analysis and comparison of treatment algorithms of the participating centers which can be performed anonymously.Based on the experience from completed consensus analyses, the main steps for the successful implementation of the objective consensus methodology were identified and discussed among the main investigators.The following steps for the successful collection and conversion of decision trees were identified and defined in detail: problem definition, population selection, draft input collection, tree conversion, criteria adaptation, problem re-evaluation, results distribution and refinement, tree finalisation, and analysis.This manuscript provides information on the main steps for successful collection of decision trees and summarizes important aspects at each point of the analysis.
| S-EPMC5559810 | biostudies-other
Project description:ImportanceComputed tomographic (CT) scanning is the standard for the rapid diagnosis of intracranial injury, but it is costly and exposes patients to ionizing radiation. The Pediatric Emergency Care Applied Research Network (PECARN) rules for identifying children with minor head trauma who are at very low risk of clinically important traumatic brain injury (ciTBI) are widely used to triage CT imaging.ObjectiveTo examine whether optimal classification trees (OCTs), which are novel machine-learning classifiers, improve on PECARN rules' predictive accuracy.Design, setting, and participantsA secondary analysis of prospective, publicly available data on emergency department visits for head trauma used by the PECARN group to develop their tool was conducted to derive OCT-based prediction rules for ciTBI in a development cohort and compare their predictive performance vs the PECARN rules in a validation cohort among children who were younger than 2 years and 2 years or older. Data on 42 412 children with head trauma and without severely altered mental status who were examined between June 1, 2004, and September 30, 2006, were gathered from 25 emergency departments in North America participating in PECARN. Data analysis was conducted from September 15, 2016, to December 18, 2018.Main outcomes and measuresThe outcome was ciTBI, with predictive performance measured by estimating the sensitivity, specificity, positive predictive value, negative predictive value, positive likelihood ratio, and negative likelihood ratio for the OCT and the PECARN rules. The OCT and PECARN rules' performance was compared by estimating ratios for each measure.ResultsOf the 42 412 children (15 996 [37.7%] girls) included in the analysis, 10 718 were younger than 2 years (25.3%; mean [SD] age, 11.6 [0.6] months) and 31 694 were 2 years or older (74.7%; age, 9.1 [4.9] years). Compared with PECARN rules, OCTs misclassified 0 vs 1 child with ciTBI in the younger and 10 vs 9 children with ciTBI in the older cohort, and correctly identified more children with very low risk of ciTBI in the younger (7605 vs 5701) and older (20 594 vs 18 134) cohorts. In the validation cohorts, compared with the PECARN rules, the OCTs had statistically significantly better specificity (in the younger cohort: 69.3%; 95% CI, 67.4%-71.2% vs 52.8%; 95% CI, 50.8%-54.9%; in the older cohort: 65.6%; 95% CI, 64.5%-66.8% vs 57.6%; 95% CI, 56.4%-58.8%), positive predictive value (odds ratios, 1.54; 95% CI, 1.36-1.74 and 1.23; 95% CI, 1.17-1.30, in younger and older children, respectively), and positive likelihood ratio (risk ratios, 1.54; 95% CI, 1.36-1.74 and 1.23; 95% CI, 1.17-1.30, in younger and older children, respectively). There were no statistically significant differences in the sensitivity, negative predictive value, and negative likelihood ratio between the 2 sets of rules.Conclusions and relevanceIf implemented, OCTs may help reduce the number of unnecessary CT scans, without missing more patients with ciTBI than the PECARN rules.
| S-EPMC6515573 | biostudies-literature
Project description:Phylogeographic methods reconstruct the origin and spread of taxa by inferring locations for internal nodes of the phylogenetic tree from sampling locations of genetic sequences. This is commonly applied to study pathogen outbreaks and spread. To evaluate such reconstructions, the inferred spread paths from root to leaf nodes should be compared to other methods or references. Usually, ancestral state reconstructions are evaluated by node-wise comparisons, therefore requiring the same tree topology, which is usually unknown. Here, we present a method for comparing phylogeographies across different trees inferred from the same taxa. We compare paths of locations by calculating discrete Fréchet distances. By correcting the distances by the number of paths going through a node, we define the Fréchet tree distance as a distance measure between phylogeographies. As an application, we compare phylogeographic spread patterns on trees inferred with different methods from hemagglutinin sequences of H5N1 influenza viruses, finding that both tree inference and ancestral reconstruction cause variation in phylogeographic spread that is not directly reflected by topological differences. The method is suitable for comparing phylogeographies inferred with different tree or phylogeographic inference methods to each other or to a known ground truth, thus enabling a quality assessment of such techniques.
| S-EPMC6242967 | biostudies-literature
Project description:Confidence judgments are a central example of metacognition-knowledge about one's own cognitive processes. According to this metacognitive view, confidence reports are generated by a second-order monitoring process based on the quality of internal representations about beliefs. Although neural correlates of decision confidence have been recently identified in humans and other animals, it is not well understood whether there are brain areas specifically important for confidence monitoring. To address this issue, we designed a postdecision temporal wagering task in which rats expressed choice confidence by the amount of time they were willing to wait for reward. We found that orbitofrontal cortex inactivation disrupts waiting-based confidence reports without affecting decision accuracy. Furthermore, we show that a normative model can quantitatively account for waiting times based on the computation of decision confidence. These results establish an anatomical locus for a metacognitive report, confidence judgment, distinct from the processes required for perceptual decisions.
| S-EPMC4364549 | biostudies-literature
Project description:In many fragmented habitats, the detectability of a population in a habitat patch closely depends on the local abundance of individuals. However, metapopulation studies rarely connect abundance and detectability. We propose a framework for using abundance-based estimates of detectability in the analysis of a spatially-explicit stochastic patch occupancy model (SPOM). We illustrate our approach with the example of Tenebrio opacus, a beetle inhabiting hollows in old trees, and have based it on a 6-year monitoring programme of adult beetles in an area harbouring a high density of old oaks. We validated our abundance-based methodology by showing that the estimates of detectability were positively and significantly correlated with those obtained from presence/absence data (Pearson r?=?0.54, p?<?2E-16) in our study system. We further showed that the height of the hollow on the tree and the area of its entrance hole, the living status and girth of the host tree, and the time of survey significantly affected the detectability of beetle populations. Median detectability was 51% for one survey. The SPOM analysis revealed a high but heterogeneous extinction risk among trees, suggesting a metapopulation dynamics between the "classic" and "mainland-island" paradigms. However, it also indicated unexplained beetle colonization of trees in our study, despite the fact that we included limited detectability in our estimation procedure. This may have been due to the cryptic larval stage of T. opacus and may thus invalidate the use of a classic SPOM in our study system.
| S-EPMC6208700 | biostudies-literature
Project description:Group-living animals are often faced with choosing between one or more alternative resource sites. A central question in such collective decision making includes determining which individuals induce the decision and when. This experimental and theoretical study of shelter selection by cockroach groups demonstrates that choices can emerge through nonlinear interaction dynamics between equal individuals without perfect knowledge or leadership. We identify a simple mechanism whereby a decision is taken on the move with limited information and signaling and without comparison of available opportunities. This mechanism leads to optimal mean benefit for group individuals. Our model points to a generic self-organized collective decision-making process independent of animal species.
| S-EPMC1458659 | biostudies-literature
Project description:Substances that do not degrade over time have proven to be harmful to the environment and are dangerous to living organisms. Being able to predict the biodegradability of substances without costly experiments is useful. Recently, the quantitative structure-activity relationship (QSAR) models have proposed effective solutions to this problem. However, the molecular descriptor datasets usually suffer from the problems of unbalanced class distribution, which adversely affects the efficiency and generalization of the derived models. Accordingly, this study aims at validating the performances of balanced random trees (RTs) and boosted C5.0 decision trees (DTs) to construct QSAR models to classify the ready biodegradation of substances and their abilities to deal with unbalanced data. The balanced RTs model algorithm builds individual trees using balanced bootstrap samples, while the boosted C5.0 DT is modeled using cost-sensitive learning. We employed the two-dimensional molecular descriptor dataset, which is publicly available through the University of California, Irvine (UCI) machine learning repository. The molecular descriptors were ranked according to their contributions to the balanced RTs classification process. The performance of the proposed models was compared with previously reported results. Based on the statistical measures, the experimental results showed that the proposed models outperform the classification results of the support vector machine (SVM), K-nearest neighbors (KNN), and discrimination analysis (DA). Classification measures were analyzed in terms of accuracy, sensitivity, specificity, precision, false positive rate, false negative rate, F1 score, receiver operating characteristic (ROC) curve, and area under the ROC curve (AUROC).
| S-EPMC7763457 | biostudies-literature