Generalized Zurek's bound on the cost of an individual classical or quantum computation.

We consider the minimal thermodynamic cost of an individual computation, where a single input x is mapped to a single output y. In prior work, Zurek proposed that this cost was given by K(x|y), the conditional Kolmogorov complexity of x given y (up to an additive constant that does not depend on x or y). However, this result was derived from an informal argument, applied only to deterministic computations, and had an arbitrary dependence on the choice of protocol (via the additive constant). Here we use stochastic thermodynamics to derive a generalized version of Zurek's bound from a rigorous Hamiltonian formulation. Our bound applies to all quantum and classical processes, whether noisy or deterministic, and it explicitly captures the dependence on the protocol. We show that K(x|y) is a minimal cost of mapping x to y that must be paid using some combination of heat, noise, and protocol complexity, implying a trade-off between these three resources. Our result is a kind of "algorithmic fluctuation theorem" with implications for the relationship between the second law and the Physical Church-Turing thesis.

Thermodynamic Bound on the Asymmetry of Cross-Correlations.

The principle of microscopic reversibility says that, in equilibrium, two-time cross-correlations are symmetric under the exchange of observables. Thus, the asymmetry of cross-correlations is a fundamental, measurable, and often-used statistical signature of deviation from equilibrium. Here we find a simple and universal inequality that bounds the magnitude of asymmetry by the cycle affinity, i.e., the strength of thermodynamic driving. Our result applies to a large class of systems and all state observables, and it suggests a fundamental thermodynamic cost for various nonequilibrium functions quantified by the asymmetry. It also provides a powerful tool to infer affinity from measured cross-correlations, in a different and complementary way to the thermodynamic uncertainty relations. As an application, we prove a thermodynamic bound on the coherence of noisy oscillations, which was previously conjectured by Barato and Seifert [Phys. Rev. E 95, 062409 (2017)PRESCM2470-004510.1103/PhysRevE.95.062409]. We also derive a thermodynamic bound on directed information flow in a biochemical signal transduction model.

Computational capacity of LRC, memristive, and hybrid reservoirs.

Reservoir computing is a machine learning paradigm that uses a high-dimensional dynamical system, or reservoir, to approximate and predict time series data. The scale, speed, and power usage of reservoir computers could be enhanced by constructing reservoirs out of electronic circuits, and several experimental studies have demonstrated promise in this direction. However, designing quality reservoirs requires a precise understanding of how such circuits process and store information. We analyze the feasibility and optimal design of electronic reservoirs that include both linear elements (resistors, inductors, and capacitors) and nonlinear memory elements called memristors. We provide analytic results regarding the feasibility of these reservoirs and give a systematic characterization of their computational properties by examining the types of input-output relationships that they can approximate. This allows us to design reservoirs with optimal properties. By introducing measures of the total linear and nonlinear computational capacities of the reservoir, we are able to design electronic circuits whose total computational capacity scales extensively with the system size. Our electronic reservoirs can match or exceed the performance of conventional "echo state network" reservoirs in a form that may be directly implemented in hardware.

A Novel Approach to the Partial Information Decomposition.

We consider the "partial information decomposition" (PID) problem, which aims to decompose the information that a set of source random variables provide about a target random variable into separate redundant, synergistic, union, and unique components. In the first part of this paper, we propose a general framework for constructing a multivariate PID. Our framework is defined in terms of a formal analogy with intersection and union from set theory, along with an ordering relation which specifies when one information source is more informative than another. Our definitions are algebraically and axiomatically motivated, and can be generalized to domains beyond Shannon information theory (such as algorithmic information theory and quantum information theory). In the second part of this paper, we use our general framework to define a PID in terms of the well-known Blackwell order, which has a fundamental operational interpretation. We demonstrate our approach on numerous examples and show that it overcomes many drawbacks associated with previous proposals.

Dependence of integrated, instantaneous, and fluctuating entropy production on the initial state in quantum and classical processes.

We consider the additional entropy production (EP) incurred by a fixed quantum or classical process on some initial state ρ, above the minimum EP incurred by the same process on any initial state. We show that this additional EP, which we term the "mismatch cost of ρ," has a universal information-theoretic form: it is given by the contraction of the relative entropy between ρ and the least-dissipative initial state φ over time. We derive versions of this result for integrated EP incurred over the course of a process, for trajectory-level fluctuating EP, and for instantaneous EP rate. We also show that mismatch cost for fluctuating EP obeys an integral fluctuation theorem. Our results demonstrate a fundamental relationship between thermodynamic irreversibility (generation of EP) and logical irreversibility (inability to know the initial state corresponding to a given final state). We use this relationship to derive quantitative bounds on the thermodynamics of quantum error correction and to propose a thermodynamically operationalized measure of the logical irreversibility of a quantum channel. Our results hold for both finite- and infinite-dimensional systems, and generalize beyond EP to many other thermodynamic costs, including nonadiabatic EP, free-energy loss, and entropy gain.

Entropy production given constraints on the energy functions.

We consider the problem of driving a finite-state classical system from some initial distribution p to some final distribution p^{'} with vanishing entropy production (EP), under the constraint that the driving protocols can only use some limited set of energy functions E. Assuming no other constraints on the driving protocol, we derive a simple condition that guarantees that such a transformation can be carried out, which is stated in terms of the smallest probabilities in {p,p^{'}} and a graph-theoretic property defined in terms of E. Our results imply that a surprisingly small amount of control over the energy function is sufficient (in particular, any transformation p→p^{'} can be carried out as soon as one can control some one-dimensional parameter of the energy function, e.g., the energy of a single state). We also derive a lower bound on the EP under more general constraints on the transition rates, which is formulated in terms of a convex optimization problem.

Decomposing information into copying versus transformation.

In many real-world systems, information can be transmitted in two qualitatively different ways: by copying or by transformation. Copying occurs when messages are transmitted without modification, e.g. when an offspring receives an unaltered copy of a gene from its parent. Transformation occurs when messages are modified systematically during transmission, e.g. when mutational biases occur during genetic replication. Standard information-theoretic measures do not distinguish these two modes of information transfer, although they may reflect different mechanisms and have different functional consequences. Starting from a few simple axioms, we derive a decomposition of mutual information into the information transmitted by copying versus the information transmitted by transformation. We begin with a decomposition that applies when the source and destination of the channel have the same set of messages and a notion of message identity exists. We then generalize our decomposition to other kinds of channels, which can involve different source and destination sets and broader notions of similarity. In addition, we show that copy information can be interpreted as the minimal work needed by a physical copying process, which is relevant for understanding the physics of replication. We use the proposed decomposition to explore a model of amino acid substitution rates. Our results apply to any system in which the fidelity of copying, rather than simple predictability, is of critical relevance.

Dynamics of beneficial epidemics.

Pathogens can spread epidemically through populations. Beneficial contagions, such as viruses that enhance host survival or technological innovations that improve quality of life, also have the potential to spread epidemically. How do the dynamics of beneficial biological and social epidemics differ from those of detrimental epidemics? We investigate this question using a breadth-first modeling approach involving three distinct theoretical models. First, in the context of population genetics, we show that a horizontally-transmissible element that increases fitness, such as viral DNA, spreads superexponentially through a population, more quickly than a beneficial mutation. Second, in the context of behavioral epidemiology, we show that infections that cause increased connectivity lead to superexponential fixation in the population. Third, in the context of dynamic social networks, we find that preferences for increased global infection accelerate spread and produce superexponential fixation, but preferences for local assortativity halt epidemics by disconnecting the infected from the susceptible. We conclude that the dynamics of beneficial biological and social epidemics are characterized by the rapid spread of beneficial elements, which is facilitated in biological systems by horizontal transmission and in social systems by active spreading behavior of infected individuals.

Publisher Correction: A space-time tradeoff for implementing a function with master equation dynamics.

The original version of the Supplementary Information associated with this Article contained an error throughout in which all inline references to Theorems, Definitions and Lemmas given in the main Article were incorrectly given as '??'. The HTML has been updated to include a corrected version of the Supplementary Information.

A space-time tradeoff for implementing a function with master equation dynamics.

Master equations are commonly used to model the dynamics of physical systems, including systems that implement single-valued functions like a computer's update step. However, many such functions cannot be implemented by any master equation, even approximately, which raises the question of how they can occur in the real world. Here we show how any function over some "visible" states can be implemented with master equation dynamics-if the dynamics exploits additional, "hidden" states at intermediate times. We also show that any master equation implementing a function can be decomposed into a sequence of "hidden" timesteps, demarcated by changes in what state-to-state transitions have nonzero probability. In many real-world situations there is a cost both for more hidden states and for more hidden timesteps. Accordingly, we derive a "space-time" tradeoff between the number of hidden states and the number of hidden timesteps needed to implement any given function.

A spectrum of routing strategies for brain networks.

Communication of signals among nodes in a complex network poses fundamental problems of efficiency and cost. Routing of messages along shortest paths requires global information about the topology, while spreading by diffusion, which operates according to local topological features, is informationally "cheap" but inefficient. We introduce a stochastic model for network communication that combines local and global information about the network topology to generate biased random walks on the network. The model generates a continuous spectrum of dynamics that converge onto shortest-path and random-walk (diffusion) communication processes at the limiting extremes. We implement the model on two cohorts of human connectome networks and investigate the effects of varying the global information bias on the network's communication cost. We identify routing strategies that approach a (highly efficient) shortest-path communication process with a relatively small global information bias on the system's dynamics. Moreover, we show that the cost of routing messages from and to hub nodes varies as a function of the global information bias driving the system's dynamics. Finally, we implement the model to identify individual subject differences from a communication dynamics point of view. The present framework departs from the classical shortest paths vs. diffusion dichotomy, unifying both models under a single family of dynamical processes that differ by the extent to which global information about the network topology influences the routing patterns of neural signals traversing the network.

Semantic information, autonomous agency and non-equilibrium statistical physics.

Shannon information theory provides various measures of so-called syntactic information, which reflect the amount of statistical correlation between systems. By contrast, the concept of 'semantic information' refers to those correlations which carry significance or 'meaning' for a given system. Semantic information plays an important role in many fields, including biology, cognitive science and philosophy, and there has been a long-standing interest in formulating a broadly applicable and formal theory of semantic information. In this paper, we introduce such a theory. We define semantic information as the syntactic information that a physical system has about its environment which is causally necessary for the system to maintain its own existence. 'Causal necessity' is defined in terms of counter-factual interventions which scramble correlations between the system and its environment, while 'maintaining existence' is defined in terms of the system's ability to keep itself in a low entropy state. We also use recent results in non-equilibrium statistical physics to analyse semantic information from a thermodynamic point of view. Our framework is grounded in the intrinsic dynamics of a system coupled to an environment, and is applicable to any physical system, living or otherwise. It leads to formal definitions of several concepts that have been intuitively understood to be related to semantic information, including 'value of information', 'semantic content' and 'agency'.

The Minor fall, the Major lift: inferring emotional valence of musical chords through lyrics.

We investigate the association between musical chords and lyrics by analysing a large dataset of user-contributed guitar tablatures. Motivated by the idea that the emotional content of chords is reflected in the words used in corresponding lyrics, we analyse associations between lyrics and chord categories. We also examine the usage patterns of chords and lyrics in different musical genres, historical eras and geographical regions. Our overall results confirm a previously known association between Major chords and positive valence. We also report a wide variation in this association across regions, genres and eras. Our results suggest possible existence of different emotional associations for other types of chords.

Extraction of pharmacokinetic evidence of drug-drug interactions from the literature.

Drug-drug interaction (DDI) is a major cause of morbidity and mortality and a subject of intense scientific interest. Biomedical literature mining can aid DDI research by extracting evidence for large numbers of potential interactions from published literature and clinical databases. Though DDI is investigated in domains ranging in scale from intracellular biochemistry to human populations, literature mining has not been used to extract specific types of experimental evidence, which are reported differently for distinct experimental goals. We focus on pharmacokinetic evidence for DDI, essential for identifying causal mechanisms of putative interactions and as input for further pharmacological and pharmacoepidemiology investigations. We used manually curated corpora of PubMed abstracts and annotated sentences to evaluate the efficacy of literature mining on two tasks: first, identifying PubMed abstracts containing pharmacokinetic evidence of DDIs; second, extracting sentences containing such evidence from abstracts. We implemented a text mining pipeline and evaluated it using several linear classifiers and a variety of feature transforms. The most important textual features in the abstract and sentence classification tasks were analyzed. We also investigated the performance benefits of using features derived from PubMed metadata fields, various publicly available named entity recognizers, and pharmacokinetic dictionaries. Several classifiers performed very well in distinguishing relevant and irrelevant abstracts (reaching F1≈0.93, MCC≈0.74, iAUC≈0.99) and sentences (F1≈0.76, MCC≈0.65, iAUC≈0.83). We found that word bigram features were important for achieving optimal classifier performance and that features derived from Medical Subject Headings (MeSH) terms significantly improved abstract classification. We also found that some drug-related named entity recognition tools and dictionaries led to slight but significant improvements, especially in classification of evidence sentences. Based on our thorough analysis of classifiers and feature transforms and the high classification performance achieved, we demonstrate that literature mining can aid DDI discovery by supporting automatic extraction of specific types of experimental evidence.

Modularity and the spread of perturbations in complex dynamical systems.

We propose a method to decompose dynamical systems based on the idea that modules constrain the spread of perturbations. We find partitions of system variables that maximize "perturbation modularity," defined as the autocovariance of coarse-grained perturbed trajectories. The measure effectively separates the fast intramodular from the slow intermodular dynamics of perturbation spreading (in this respect, it is a generalization of the "Markov stability" method of network community detection). Our approach captures variation of modular organization across different system states, time scales, and in response to different kinds of perturbations: aspects of modularity which are all relevant to real-world dynamical systems. It offers a principled alternative to detecting communities in networks of statistical dependencies between system variables (e.g., "relevance networks" or "functional networks"). Using coupled logistic maps, we demonstrate that the method uncovers hierarchical modular organization planted in a system's coupling matrix. Additionally, in homogeneously coupled map lattices, it identifies the presence of self-organized modularity that depends on the initial state, dynamical parameters, and type of perturbations. Our approach offers a powerful tool for exploring the modular organization of complex dynamical systems.

Multi-scale integration and predictability in resting state brain activity.

The human brain displays heterogeneous organization in both structure and function. Here we develop a method to characterize brain regions and networks in terms of information-theoretic measures. We look at how these measures scale when larger spatial regions as well as larger connectome sub-networks are considered. This framework is applied to human brain fMRI recordings of resting-state activity and DSI-inferred structural connectivity. We find that strong functional coupling across large spatial distances distinguishes functional hubs from unimodal low-level areas, and that this long-range functional coupling correlates with structural long-range efficiency on the connectome. We also find a set of connectome regions that are both internally integrated and coupled to the rest of the brain, and which resemble previously reported resting-state networks. Finally, we argue that information-theoretic measures are useful for characterizing the functional organization of the brain at multiple scales.

Neural correlates of apparent motion perception of impoverished facial stimuli: a comparison of ERP and ERSP activity.

Our brains readily decode human movements, as shown by neural responses to face and body motion. N170 event-related potentials (ERPs) are earlier and larger to mouth opening movements relative to closing in both line-drawn and natural faces, and gaze aversions relative to direct gaze in natural faces (Puce and Perrett, 2003; Puce et al., 2000). Here we extended this work by recording both ERP and oscillatory EEG activity (event-related spectral perturbations, ERSPs) to line-drawn faces depicting eye and mouth movements (Eyes: Direct vs Away; Mouth: Closed vs Open) and non-face motion controls. Neural activity was measured in 2 occipito-temporal clusters of 9 electrodes, one in each hemisphere. Mouth opening generated larger N170s than mouth closing, replicating earlier work. Eye motion elicited robust N170s that did not differ between gaze conditions. Control condition differences were seen, and generated the largest N170. ERSP difference plots across conditions in the occipito-temporal electrode clusters (Eyes: Direct vs Away; Mouth: Closed vs Open) showed statistically significant differences in beta and gamma bands for gaze direction changes and mouth opening at similar post-stimulus times and frequencies. In contrast, control stimuli showed activity in the gamma band with a completely different time profile and hemispheric distribution to facial stimuli. ERSP plots were generated in two 9 electrode clusters centered on central sites, C3 and C4. In the left cluster for all stimulus conditions, broadband beta suppression persisted from about 250ms post-motion onset. In the right cluster, beta suppression was seen for control conditions only. Statistically significant differences between conditions were confined between 4 and 15Hz, unlike the occipito-temporal sites where differences occurred at much higher frequencies (high beta/gamma). Our data indicate that N170 amplitude is sensitive to the amount of movement in the visual field, independent of stimulus type. In contrast, occipito-temporal beta and gamma activity differentiates between facial and non-facial motion. Context and stimulus configuration likely plays a role in shaping neural responses, based on comparisons of the current data to previously reported studies. Broadband suppression of central beta activity, and significant low frequency differences were likely stimulus driven and not contingent on behavioral responses.

Classification of protein-protein interaction full-text documents using text and citation network features.

We participated (as Team 9) in the Article Classification Task of the Biocreative II.5 Challenge: binary classification of full-text documents relevant for protein-protein interaction. We used two distinct classifiers for the online and offline challenges: 1) the lightweight Variable Trigonometric Threshold (VTT) linear classifier we successfully introduced in BioCreative 2 for binary classification of abstracts and 2) a novel Naive Bayes classifier using features from the citation network of the relevant literature. We supplemented the supplied training data with full-text documents from the MIPS database. The lightweight VTT classifier was very competitive in this new full-text scenario: it was a top-performing submission in this task, taking into account the rank product of the Area Under the interpolated precision and recall Curve, Accuracy, Balanced F-Score, and Matthew's Correlation Coefficient performance measures. The novel citation network classifier for the biomedical text mining domain, while not a top performing classifier in the challenge, performed above the central tendency of all submissions, and therefore indicates a promising new avenue to investigate further in bibliome informatics.