One strategy for winning a coevolutionary struggle is to evolve rapidly. Most of the literature on host-pathogen coevolution focuses on this phenomenon, and looks for consequent evidence of coevolutionary arms races. An alternative strategy, less often considered in the literature, is to deter rapid evolutionary change by the opponent. To study how this can be done, we construct an evolutionary game between a controller that must process information, and an adversary that can tamper with this information processing. In this game, a species can foil its antagonist by processing information in a way that is hard for the antagonist to manipulate. We show that the structure of the information processing system induces a fitness landscape on which the adversary population evolves. Complex processing logic can carve long, deep fitness valleys that slow adaptive evolution in the adversary population. We suggest that this type of defensive complexity on the part of the vertebrate adaptive immune system may be an important element of coevolutionary dynamics between pathogens and their vertebrate hosts. Furthermore, we cite evidence that the immune control logic is phylogenetically conserved in mammalian lineages. Thus our model of defensive complexity suggests a new hypothesis for the lower rates of evolution for immune control logic compared to other immune structures.
Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement at the fact that the mechanism of natural selection has produced the whole of Life as we see it around us. From a computational perspective, it is natural to marvel at evolution's solution to the problems of robotics, vision and theorem proving! What, then, is the complexity of evolution, viewed as an algorithm? One answer to this question is 10^{12}, roughly the number of sequential steps or generations from the earliest single celled creatures to today's Homo Sapiens. To put this into perspective, the processor of a modern cell phone can perform 10^{12} steps in less than an hour. Another answer is 10^30, the degree of parallelism, roughly the maximum number of organisms living on the Earth at any time. Perhaps the answer should be the product of the two numbers, roughly 10^42, to reflect the total work done by evolution, viewed as a parallel algorithm.
Here we argue, interpreting our recently published paper, that none of the above answers is really correct. Viewing evolution as an algorithm poses an additional challenge: recombination. Even if evolution succeeds in producing a particularly good solution (a highly fit individual), its offspring would only inherit half its genes, and therefore appear unlikely to be a good solution. This is the core of the problem of explaining the role of sex in evolution, known as the queen of problems in evolutionary biology.
The starting point is the diffusion-equation-based approach of theoretical population geneticists, who analyze the changing allele frequencies (over the generations) in the gene pool, consisting of the aggregate of the genetic variants (or alleles) over all genes (or loci) and over all individuals in a species. Taking this viewpoint to its logical conclusion, rather than acting on individuals or species or genes, evolution acts on this gene pool, or genetic soup, by making it more potent, in the sense that it increases the expected fitness of genotype drawn randomly from this soup. Moreover, for much genetic variation, this soup may be assumed to be in the regime of weak selection, a regime where the probability of occurrence of a certain genotype involving various alleles at different loci is simply the product of the probabilities of each of its alleles. In this regime, we show that evolution in the regime of weak selection can be formulated as a game, where the recombining loci are the players, the alleles in those loci are possible moves or actions of each player, and the expected payoff of each player-locus is precisely the organism's expected fitness across the genotypes that are present in the population. Moreover, the dynamics specified by the diffusion equations of theoretical population geneticists is closely approximated by the dynamics of multiplicative weight updates (MWUA).
The algorithmic connection to MWUA brings with it new insights for evolutionary biology, specifically, into the question of how genetic diversity is maintained in the presence of natural selection. For this it is useful to consider a dual view of MWUA, which expresses what each gene is optimizing as it plays the game. Remarkably this turns out to be a particular convex combination of the entropy of its distribution over alleles and cumulative expected fitness. This sheds new light on the maintenance of diversity in evolution.
All of this suggests that the complexity of evolution should indeed be viewed as 10^12, but for a subtle reason. It is the number of steps of multiplicative weight updates carried out on allele frequencies in the genetic soup. A closer examination of this reveals further that the accurate tracking of allele frequencies over the generations requires the simulation of a quadratic dynamical system (two parents for each offspring). Moreover the simulation of even simple quadratic dynamical systems is known to be PSPACE-hard. This suggests that the tracking of allele frequencies might require large population sizes for each species, putting into perspective the number 10^30. Finally, it is worth noting that in this view there is a primacy to recombination or sex, which serve to provide robustness to the mechanism of evolution, as well as the framework within which MWUA operates.
In this age of big data and natural language processing, to what extent can we leverage new technologies and new tools to make progress in organizing disparate biomedical data sources? Imagine a system in which one could bring together sequencing data with phenotypes, gene expression data, and clinical information all under the same conceptual heading where applicable. Bio-ontologies seek to carry this out by organizing the relations between concepts and attaching the data to their corresponding concept. However, to accomplish this, we need considerable time and human input. Instead of resorting to human input alone, we describe a novel approach to obtaining the foundation for bio-ontologies: obtaining propositions (links between concepts) from biomedical text so as to fill the ontology. The heart of our approach is applying logic rules from Aristotelian logic and natural logic to biomedical information to derive propositions so that we can have material to organize knowledge bases (ontologies) for biomedical research. We demonstrate this approach by constructing a proof-of-principle bio-ontology for COVID-19 and related diseases.
In the spirit of RL-Classifier reductions [1], we present a method to reduce a specific class of POMDPs to a time-sensitive family of classifiers. POMDPs are in general intractable to solve exactly, so this reduction allows us to solve the full POMDP by using algorithms like Q-learning, which are known to have polynomial convergence time. A great advantage of this approach is that we can exploit classifiers to discretize and approximate the otherwise continuous belief state. The family of classifiers we introduce are so-called anytime classifiers, which guarantee increasing accuracy (decreasing error rate) when given more training data. In real-time reinforcement learning, speed is important, so it is necessary to determine the optimal time to stop training the anytime classifier. This is called the optimal stopping time. We present an algorithm to learn the optimal stopping time for a given anytime classifier and show its connections to neural mechanisms of sensory decision-making. The type of POMDP which can be reduced to an anytime classifier has states which correspond directly to actions augmented by two more actions: continuing and stopping training of the state classifier. The parallels to optimal stopping problems are clear, and we use an extension of Tsitsiklis & Van Roy’s work [2] to derive a learning algorithm for stopping time similar to Q learning. Because all classifiers which are based on calculating the posterior probability using Bayesian models are anytime classifiers (which we show using the Laplace Method), solving this class of POMDP can also be viewed as Bayesian Inference with a stopping rule, with the posterior distribution being parametrized by stopping time.
One strategy for winning a coevolutionary struggle is to evolve rapidly. Most of the literature on host-pathogen coevolution focuses on this phenomenon, and looks for consequent evidence of coevolutionary arms races. An alternative strategy, less often considered in the literature, is to deter rapid evolutionary change by the opponent. To study how this can be done, we construct an evolutionary game between a controller that must process information, and an adversary that can tamper with this information processing. In this game, a species can foil its antagonist by processing information in a way that is hard for the antagonist to manipulate. We show that the structure of the information processing system induces a fitness landscape on which the adversary population evolves, and that complex processing logic is required to make that landscape rugged. Drawing on the rich literature concerning rates of evolution on rugged landscapes, we show how a species can slow adaptive evolution in the adversary population. We suggest that this type of defensive complexity on the part of the vertebrate adaptive immune system may be an important element of coevolutionary dynamics between pathogens and their vertebrate hosts.
We propose a new view of active learning algorithms as optimization. We show that many online active learning algorithms can be viewed as stochastic gradient descent on non-convex objective functions. Variations of some of these algorithms and objective functions have been previously proposed without noting this connection. We also point out a connection between the standard min-margin offline active learning algorithm and non-convex losses. Finally, we discuss and show empirically how viewing active learning as non-convex loss minimization helps explain two previously observed phenomena: certain active learning algorithms achieve better generalization error than passive learning algorithms on certain data sets (Schohn and Cohn, 2000; Bordes et al., 2005) and on other data sets many active learning algorithms are prone to local minima (Sch¨ utze et al., 2006). 1 Background We address the active learning problem in this paper. We assume data points X 2 R d and labels Y 2 fi1;1g are drawn from some fixed unknown distribution p(x;y). We wish to choose the classifier f 2 F that minimizes the expected loss EX;Y [l(Y;f;X)] where l is a loss function. In general, the size of F may be uncountable. In standard passive supervised learning we approximately minimize this expected loss by minimizing instead the loss on a set or stream of i.i.d. labeled training examples (xi;yi) » p(x;y). In active learning, we also have access to i.i.d. xi, but we selectively query the labels yi for the examples. In
