On the Effect of Learned Clauses on Stochastic Local Search
Ontology highlight
ABSTRACT:
SUBMITTER: Pulina L
PROVIDER: S-EPMC7326537 | biostudies-literature | 2020 Jun
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Conflict-driven clause learning (CDCL) is a remarkably successful paradigm for solving the satisfiability problem of propositional logic. Instead of a simple depth-first backtracking approach, this kind of solver learns the reason behind occurring conflicts in the form of additional clauses. However, despite the enormous success of CDCL solvers, there is still only a limited understanding of what influences the performance of these solvers in what way. Considering different measures, this paper demonstrates, quite surprisingly, that clause learning (without being able to get rid of some clauses) can not only help the solver but can oftentimes deteriorate the solution process dramatically. By conducting extensive empirical analysis, we furthermore find that the runtime distributions of CDCL solvers are multimodal. This multimodality can be seen as a reason for the deterioration phenomenon described above. Simultaneously, it also gives an indication of why clause learning in combination with clause deletion is virtually the de facto standard of SAT solving, in spite of this phenomenon. As a final contribution, we show that Weibull mixture distributions can accurately describe the multimodal distributions. Thus, adding new clauses to a base instance has an inherent effect of making runtimes long-tailed. This insight provides an explanation as to why the technique of forgetting clauses is useful in CDCL solvers apart from the optimization of unit propagation speed.
| S-EPMC9417043 | biostudies-literature
Project description:Many applications requiring both spectral and spatial information at high resolution benefit from spectral imaging. Although different technical methods have been developed and commercially available, computational spectral cameras represent a compact, lightweight, and inexpensive solution. However, the tradeoff between spatial and spectral resolutions, dominated by the limited data volume and environmental noise, limits the potential of these cameras. In this study, we developed a deeply learned broadband encoding stochastic hyperspectral camera. In particular, using advanced artificial intelligence in filter design and spectrum reconstruction, we achieved 7000-11,000 times faster signal processing and ~10 times improvement regarding noise tolerance. These improvements enabled us to precisely and dynamically reconstruct the spectra of the entire field of view, previously unreachable with compact computational spectral cameras.
| S-EPMC8149860 | biostudies-literature
Project description:Migration is a dynamic process in which a cell searches the environment and translates acquired information into somal advancement. In particular, interneuron migration during development is accomplished by two distinct processes: the extension of neurites tipped with growth cones; and nucleus translocation, termed nucleokinesis. The primary purpose of our study is to investigate neurite branching and nucleokinesis using high-resolution time-lapse confocal microscopy and computational modeling. We demonstrate that nucleokinesis is accurately modeled by a spring-dashpot system and that neurite branching is independent of the nucleokinesis event, and displays the dynamics of a stochastic birth-death process. This is in contrast to traditional biological descriptions, which suggest a closer relationship between the two migratory mechanisms. Our models are validated on independent data sets acquired using two different imaging protocols, and are shown to be robust to alterations in guidance cues and cellular migratory mechanisms, through treatment with brain-derived neurotrophic factor, neurotrophin-4, and blebbistatin. We postulate that the stochastic branch dynamics exhibited by interneurons undergoing guidance-directed migration permit efficient exploration of the environment.
| S-EPMC2718142 | biostudies-literature
Project description:BackgroundDesign of drug combination cocktails to maximize sensitivity for individual patients presents a challenge in terms of minimizing the number of experiments to attain the desired objective. The enormous number of possible drug combinations constrains exhaustive experimentation approaches, and personal variations in genetic diseases restrict the use of prior knowledge in optimization.ResultsWe present a stochastic search algorithm that consisted of a parallel experimentation phase followed by a combination of focused and diversified sequential search. We evaluated our approach on seven synthetic examples; four of them were evaluated twice with different parameters, and two biological examples of bacterial and lung cancer cell inhibition response to combination drugs. The performance of our approach as compared to recently proposed adaptive reference update approach was superior for all the examples considered, achieving an average of 45% reduction in the number of experimental iterations.ConclusionsAs the results illustrate, the proposed diverse stochastic search algorithm can produce optimized combinations in relatively smaller number of iterative steps. This approach can be combined with available knowledge on the genetic makeup of the patient to design optimal selection of drug cocktails.
| S-EPMC3971504 | biostudies-literature
Project description:Phylogenetic reconstruction is vital to analyzing the evolutionary relationship of genes within and across populations of different species. Nowadays, with next generation sequencing technologies producing sets comprising thousands of sequences, robust identification of the tree topology, which is optimal according to standard criteria such as maximum parsimony, maximum likelihood or posterior probability, with phylogenetic inference methods is a computationally very demanding task. Here, we describe a stochastic search method for a maximum parsimony tree, implemented in a software package we named PTree. Our method is based on a new pattern-based technique that enables us to infer intermediate sequences efficiently where the incorporation of these sequences in the current tree topology yields a phylogenetic tree with a lower cost. Evaluation across multiple datasets showed that our method is comparable to the algorithms implemented in PAUP* or TNT, which are widely used by the bioinformatics community, in terms of topological accuracy and runtime. We show that our method can process large-scale datasets of 1,000-8,000 sequences. We believe that our novel pattern-based method enriches the current set of tools and methods for phylogenetic tree inference. The software is available under: http://algbio.cs.uni-duesseldorf.de/webapps/wa-download/.
| S-EPMC3698465 | biostudies-literature
Project description:In any visual search task in the lab or in the world, observers will make errors. Those errors can be categorized as "deterministic": If you miss this target in this display once, you will definitely miss it again. Alternatively, errors can be "stochastic", occurring randomly with some probability from trial to trial. Researchers and practitioners have sought to reduce errors in visual search, but different types of errors might require different techniques for mitigation. To empirically categorize errors in a simple search task, our observers searched for the letter "T" among "L" distractors, with each display presented twice. When the letters were clearly visible (white letters on a gray background), the errors were almost completely stochastic (Exp 1). An error made on the first appearance of a display did not predict that an error would be made on the second appearance. When the visibility of the letters was manipulated (letters of different gray levels on a noisy background), the errors became a mix of stochastic and deterministic. Unsurprisingly, lower contrast targets produced more deterministic errors. (Exp 2). Using the stimuli of Exp 2, we tested whether errors could be reduced using cues that guided attention around the display but knew nothing about the content of that display (Exp3a, b). This had no effect, but cueing all item locations did succeed in reducing deterministic errors (Exp3c).
| S-EPMC10951178 | biostudies-literature
Project description:The spread of case-control genome-wide association studies (GWASs) has stimulated the development of new variable selection methods and predictive models. We introduce a novel Bayesian model search algorithm, Binary Outcome Stochastic Search (BOSS), which addresses the model selection problem when the number of predictors far exceeds the number of binary responses.Our method is based on a latent variable model that links the observed outcomes to the underlying genetic variables. A Markov Chain Monte Carlo approach is used for model search and to evaluate the posterior probability of each predictor.BOSS is compared with three established methods (stepwise regression, logistic lasso, and elastic net) in a simulated benchmark. Two real case studies are also investigated: a GWAS on the genetic bases of longevity, and the type 2 diabetes study from the Wellcome Trust Case Control Consortium. Simulations show that BOSS achieves higher precisions than the reference methods while preserving good recall rates. In both experimental studies, BOSS successfully detects genetic polymorphisms previously reported to be associated with the analyzed phenotypes.BOSS outperforms the other methods in terms of F-measure on simulated data. In the two real studies, BOSS successfully detects biologically relevant features, some of which are missed by univariate analysis and the three reference techniques.The proposed algorithm is an advance in the methodology for model selection with a large number of features. Our simulated and experimental results showed that BOSS proves effective in detecting relevant markers while providing a parsimonious model.
| S-EPMC3392850 | biostudies-literature
Project description:Decisions typically comprise several elements. For example, attention must be directed towards specific objects, their identities recognized, and a choice made among alternatives. Pairs of competing accumulators and drift-diffusion processes provide good models of evidence integration in two-alternative perceptual choices, but more complex tasks requiring the coordination of attention and decision making involve multistage processing and multiple brain areas. Here we consider a task in which a target is located among distractors and its identity reported by lever release. The data comprise reaction times, accuracies, and single unit recordings from two monkeys' lateral interparietal area (LIP) neurons. LIP firing rates distinguish between targets and distractors, exhibit stimulus set size effects, and show response-hemifield congruence effects. These data motivate our model, which uses coupled sets of leaky competing accumulators to represent processes hypothesized to occur in feature-selective areas and limb motor and pre-motor areas, together with the visual selection process occurring in LIP. Model simulations capture the electrophysiological and behavioral data, and fitted parameters suggest that different connection weights between LIP and the other cortical areas may account for the observed behavioral differences between the animals.
| S-EPMC4545888 | biostudies-literature
Project description:MotivationRapid methods for protein structure search enable biological discoveries based on flexibly defined structural similarity, unleashing the power of the ever greater number of solved protein structures. Projection methods show promise for the development of fast structural database search solutions. Projection methods map a structure to a point in a high-dimensional space and compare two structures by measuring distance between their projected points. These methods offer a tremendous increase in speed over residue-level structural alignment methods. However, current projection methods are not practical, partly because they are unable to identify local similarities.ResultsWe propose a new projection-based approach that can rapidly detect global as well as local structural similarities. Local structural search is enabled by a topology-inspired writhe decomposition protocol that produces a small number of fragments while ensuring that similar structures are cut in a similar manner. In benchmark tests, we show that our method, writher, improves accuracy over existing projection methods in terms of recognizing scop domains out of multi-domain proteins, while maintaining accuracy comparable with existing projection methods in a standard single-domain benchmark test.AvailabilityThe source code is available at the following website: http://compbio.berkeley.edu/proj/writher/.
| S-EPMC2859133 | biostudies-literature
Project description:This article analyzes the conditions for local adaptation in a metapopulation with infinitely many islands under a model of hard selection, where population size depends on local fitness. Each island belongs to one of two distinct ecological niches or habitats. Fitness is influenced by an additive trait which is under habitat-dependent directional selection. Our analysis is based on the diffusion approximation and accounts for both genetic drift and demographic stochasticity. By neglecting linkage disequilibria, it yields the joint distribution of allele frequencies and population size on each island. We find that under hard selection, the conditions for local adaptation in a rare habitat are more restrictive for more polygenic traits: even moderate migration load per locus at very many loci is sufficient for population sizes to decline. This further reduces the efficacy of selection at individual loci due to increased drift and because smaller populations are more prone to swamping due to migration, causing a positive feedback between increasing maladaptation and declining population sizes. Our analysis also highlights the importance of demographic stochasticity, which exacerbates the decline in numbers of maladapted populations, leading to population collapse in the rare habitat at significantly lower migration than predicted by deterministic arguments.
| S-EPMC8251656 | biostudies-literature