Models of Intervention: Helping Agents and Human Users Avoid Undesirable Outcomes.

When working in an unfamiliar online environment, it can be helpful to have an observer that can intervene and guide a user toward a desirable outcome while avoiding undesirable outcomes or frustration. The Intervention Problem is deciding when to intervene in order to help a user. The Intervention Problem is similar to, but distinct from, Plan Recognition because the observer must not only recognize the intended goals of a user but also when to intervene to help the user when necessary. We formalize a family of Intervention Problems and show that how these problems can be solved using a combination of Plan Recognition methods and classification algorithms to decide whether to intervene. For our benchmarks, the classification algorithms dominate three recent Plan Recognition approaches. We then generalize these results to Human-Aware Intervention, where the observer must decide in real time whether to intervene human users solving a cognitively engaging puzzle. Using a revised feature set more appropriate to human behavior, we produce a learned model to recognize when a human user is about to trigger an undesirable outcome. We perform a human-subject study to evaluate the Human-Aware Intervention. We find that the revised model also dominates existing Plan Recognition algorithms in predicting Human-Aware Intervention.

A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling between Local Optima.

Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of 2k reachable offspring, where k is the number of recombining components. This article introduces a new GPX2 operator, which finds more recombining components than GPX or Iterative Partial Transcription (IPT). We also show that GPX2 has O(n) runtime complexity, while also introducing new enhancements to reduce the execution time of GPX2. Finally, we experimentally demonstrate the efficiency of GPX2 when it is used to improve solutions found by the multitrial Lin-Kernighan-Helsgaum (LKH) algorithm. Significant improvements in performance are documented on large (n>5000) and very large (n=100,000) instances of the Traveling Salesman Problem.

Bio-ModelChecker: Using Bounded Constraint Satisfaction to Seamlessly Integrate Observed Behavior With Prior Knowledge of Biological Networks.

The in silico study and reverse engineering of regulatory networks has gained in recognition as an insightful tool for the qualitative study of biological mechanisms that underlie a broad range of complex illness. In the creation of reliable network models, the integration of prior mechanistic knowledge with experimentally observed behavior is hampered by the disparate nature and widespread sparsity of such measurements. The former challenges conventional regression-based parameter fitting while the latter leads to large sets of highly variable network models that are equally compliant with the data. In this paper, we propose a bounded Constraint Satisfaction (CS) based model checking framework for parameter set identification that readily accommodates partial records and the exponential complexity of this problem. We introduce specific criteria to describe the biological plausibility of competing multi-valued regulatory networks that satisfy all the constraints and formulate model identification as a multi-objective optimization problem. Optimization is directed at maximizing structural parsimony of the regulatory network by mitigating excessive control action selectivity while also favoring increased state transition efficiency and robustness of the network's dynamic response. The framework's scalability, computational time and validity is demonstrated on several well-established and well-studied biological networks.

Computation of Robust Minimal Intervention Sets in Multi-Valued Biological Regulatory Networks.

Enabled by rapid advances in computational sciences, in silico logical modeling of complex and large biological networks is more and more feasible making it an increasingly popular approach among biologists. Automated high-throughput, drug target identification is one of the primary goals of this in silico network biology. Targets identified in this way are then used to mine a library of drug chemical compounds in order to identify appropriate therapies. While identification of drug targets is exhaustively feasible on small networks, it remains computationally difficult on moderate and larger models. Moreover, there are several important constraints such as off-target effects, efficacy and safety that should be integrated into the identification of targets if the intention is translation to the clinical space. Here we introduce numerical constraints whereby efficacy is represented by efficiency in response and robustness of outcome. This paper introduces an algorithm that relies on a Constraint Satisfaction (CS) technique to efficiently compute the Minimal Intervention Sets (MIS) within a set of often complex clinical safety constraints with the aim of identifying the smallest least invasive set of targets pharmacologically accessible for therapy that most efficiently and reliably achieve the desired outcome.

High-fidelity discrete modeling of the HPA axis: a study of regulatory plasticity in biology.

BACKGROUND: The hypothalamic-pituitary-adrenal (HPA) axis is a central regulator of stress response and its dysfunction has been associated with a broad range of complex illnesses including Gulf War Illness (GWI) and Chronic Fatigue Syndrome (CFS). Though classical mathematical approaches have been used to model HPA function in isolation, its broad regulatory interactions with immune and central nervous function are such that the biological fidelity of simulations is undermined by the limited availability of reliable parameter estimates. METHOD: Here we introduce and apply a generalized discrete formalism to recover multiple stable regulatory programs of the HPA axis using little more than connectivity between physiological components. This simple discrete model captures cyclic attractors such as the circadian rhythm by applying generic constraints to a minimal parameter set; this is distinct from Ordinary Differential Equation (ODE) models, which require broad and precise parameter sets. Parameter tuning is accomplished by decomposition of the overall regulatory network into isolated sub-networks that support cyclic attractors. Network behavior is simulated using a novel asynchronous updating scheme that enforces priority with memory within and between physiological compartments. RESULTS: Consistent with much more complex conventional models of the HPA axis, this parsimonious framework supports two cyclic attractors, governed by higher and lower levels of cortisol respectively. Importantly, results suggest that stress may remodel the stability landscape of this system, favoring migration from one stable circadian cycle to the other. Access to each regime is dependent on HPA axis tone, captured here by the tunable parameters of the multi-valued logic. Likewise, an idealized glucocorticoid receptor blocker alters the regulatory topology such that maintenance of persistently low cortisol levels is rendered unstable, favoring a return to normal circadian oscillation in both cortisol and glucocorticoid receptor expression. CONCLUSION: These results emphasize the significance of regulatory connectivity alone and how regulatory plasticity may be explored using simple discrete logic and minimal data compared to conventional methods.

TSPmap, a tool making use of traveling salesperson problem solvers in the efficient and accurate construction of high-density genetic linkage maps.

BACKGROUND: Recent advances in nucleic acid sequencing technologies have led to a dramatic increase in the number of markers available to generate genetic linkage maps. This increased marker density can be used to improve genome assemblies as well as add much needed resolution for loci controlling variation in ecologically and agriculturally important traits. However, traditional genetic map construction methods from these large marker datasets can be computationally prohibitive and highly error prone. RESULTS: We present TSPmap, a method which implements both approximate and exact Traveling Salesperson Problem solvers to generate linkage maps. We demonstrate that for datasets with large numbers of genomic markers (e.g. 10,000) and in multiple population types generated from inbred parents, TSPmap can rapidly produce high quality linkage maps with low sensitivity to missing and erroneous genotyping data compared to two other benchmark methods, JoinMap and MSTmap. TSPmap is open source and freely available as an R package. CONCLUSIONS: With the advancement of low cost sequencing technologies, the number of markers used in the generation of genetic maps is expected to continue to rise. TSPmap will be a useful tool to handle such large datasets into the future, quickly producing high quality maps using a large number of genomic markers.

Efficient retrieval of landscape Hessian: forced optimal covariance adaptive learning.

Knowledge of the Hessian matrix at the landscape optimum of a controlled physical observable offers valuable information about the system robustness to control noise. The Hessian can also assist in physical landscape characterization, which is of particular interest in quantum system control experiments. The recently developed landscape theoretical analysis motivated the compilation of an automated method to learn the Hessian matrix about the global optimum without derivative measurements from noisy data. The current study introduces the forced optimal covariance adaptive learning (FOCAL) technique for this purpose. FOCAL relies on the covariance matrix adaptation evolution strategy (CMA-ES) that exploits covariance information amongst the control variables by means of principal component analysis. The FOCAL technique is designed to operate with experimental optimization, generally involving continuous high-dimensional search landscapes (≳30) with large Hessian condition numbers (≳10^{4}). This paper introduces the theoretical foundations of the inverse relationship between the covariance learned by the evolution strategy and the actual Hessian matrix of the landscape. FOCAL is presented and demonstrated to retrieve the Hessian matrix with high fidelity on both model landscapes and quantum control experiments, which are observed to possess nonseparable, nonquadratic search landscapes. The recovered Hessian forms were corroborated by physical knowledge of the systems. The implications of FOCAL extend beyond the investigated studies to potentially cover other physically motivated multivariate landscapes.

Calibration of liquid crystal ultrafast pulse shaper with common-path spectral interferometry and application to coherent control with a covariance matrix adaptation evolutionary strategy.

An ultrafast pulse shaper for coherent control applications is described, complete with a simple, reliable calibration technique and an advanced learning control algorithm. The calibration technique makes use of a common-path interferometer, producing less noisy measurements than a conventional Mach-Zehnder interferometer. A covariance matrix adaptation evolutionary strategy (ES) is demonstrated to perform better than a traditional ES for high-dimensional search landscapes.

Properties of gray and binary representations.

Representations are formalized as encodings that map the search space to the vertex set of a graph. We define the notion of bit equivalent encodings and show that for such encodings the corresponding Walsh coefficients are also conserved. We focus on Gray codes as particular types of encoding and present a review of properties related to the use of Gray codes. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new convergence proofs for a special class of unimodal functions; the proofs show that a steepest ascent bit climber using any reflected Gray code representation reaches the global optimum in a number of steps that is linear with respect to the encoding size. There are in fact many different Gray codes. Shifting is defined as a mechanism for dynamically switching from one Gray code representation to another in order to escape local optima. Theoretical results that substantially improve our understanding of the Gray codes and the shifting mechanism are presented. New proofs also shed light on the number of unique Gray code neighborhoods accessible via shifting and on how neighborhood structure changes during shifting. We show that shifting can improve the performance of both a local search algorithm as well as one of the best genetic algorithms currently available.