Minimal models for explaining unbounded increase in fitness

On a prior version of my paper on computational complexity as an ultimate constraint, Hemachander Subramanian made a good comment and question:

Nice analysis Artem! If we think of the fitness as a function of genes, interactions between two genes, and interactions between three genes and so on, your analysis using epistasis takes into account only the interactions (second order and more). The presence or absence of the genes themselves (first order) can change the landscape itself, though. Evolution might be able to play the game of standing still as the landscape around it changes until a species is “stabilized” by finding itself in a peak. The question is would traversing these time-dependent landscapes for optima is still uncomputable?

And although I responded to his comment in the bioRxiv Disqus thread, it seems that comments are version locked and so you cannot see Hema’s comment anymore on the newest version. As such, I wanted to share my response on the blog and expand a bit on it.

Mostly this will be an incomplete argument for why biologists should care about worst-case analysis. I’ll have to expand on it more in the future.

Read more of this post


Techne and Programming as Analytic Philosophy

This week, as I was assembling furniture — my closest approach to a traditional craft — I was listening to Peter Adamson interviewing his twin brother Glenn Adamson about craft and material intelligence. Given that this interview was on the history of philosophy (without any gaps) podcast, at some point, the brothers steered the conversation to Plato. In particular, to Plato’s high regard for craft or — in its Greek form — techne.

For Peter, Plato “treats techne, or craft, as a paradigm for knowledge. And a lot of the time in the Socratic dialogues, you get the impression that what Socrates is suggesting is that we need to find a craft or tekne for virtue or ethics — like living in the world — that is more or less like the tekne that say the carpenter has.” Through this, the Adamson twins proposed a view of craft and philosophy as two sides of the same coin.

Except, unlike the carpenter and her apprentice, Plato has Socrates trying to force his interlocutors to formulate their knowledge in propositional terms and not just live it. It is on this point that I differ from Peter Adamson.

The good person practices the craft of ethics: of shaping their own life and particular circumstances into the good life. Their wood is their own existence and their chair is the good life. The philosopher, however, aims to make the implicit (or semi-implicit) knowledge of the good person into explicit terms. To uncover and specify the underlying rules and regularities. And the modern philosopher applies these same principles to other domains, not just ethics. Thus, if I had to give an incomplete definition for this post: philosophy is the art of turning implicit knowledge into propositional form. Analytic philosophy aims for that propositional form to be formal.

But this is also what programmers do.

In this post, I want to convince you that it is fruitful to think of programming as analytic philosophy. In the process, we’ll have to discuss craft and the history of its decline. Of why people (wrongly) think that a professor is ‘better’ than a carpenter.
Read more of this post

Hobbes on knowledge & computer simulations of evolution

Earlier this week, I was at the Second Joint Congress on Evolutionary Biology (Evol2018). It was overwhelming, but very educational.

Many of the talks were about very specific evolutionary mechanisms in very specific model organisms. This diversity of questions and approaches to answers reminded me of the importance of bouquets of heuristic models in biology. But what made this particularly overwhelming for me as a non-biologist was the lack of unifying formal framework to make sense of what was happening. Without the encyclopedic knowledge of a good naturalist, I had a very difficult time linking topics to each other. I was experiencing the pluralistic nature of biology. This was stressed by Laura Nuño De La Rosa‘s slide that contrasts the pluralism of biology with the theory reduction of physics:

That’s right, to highlight the pluralism, there were great talks from philosophers of biology along side all the experimental and theoretical biology at Evol2018.

As I’ve discussed before, I think that theoretical computer science can provide the unifying formal framework that biology needs. In particular, the cstheory approach to reductions is the more robust (compared to physics) notion of ‘theory reduction’ that a pluralistic discipline like evolutionary biology could benefit from. However, I still don’t have any idea of how such a formal framework would look in practice. Hence, throughout Evol2018 I needed refuge from the overwhelming overstimulation of organisms and mechanisms that were foreign to me.

One of the places I sought refuge was in talks on computational studies. There, I heard speakers emphasize several times that they weren’t “just simulating evolution” but that their programs were evolution (or evolving) in a computer. Not only were they looking at evolution in a computer, but this model organism gave them an advantage over other systems because of its transparency: they could track every lineage, every offspring, every mutation, and every random event. Plus, computation is cheaper and easier than culturing E.coli, brewing yeast, or raising fruit flies. And just like those model organisms, computational models could test evolutionary hypotheses and generate new ones.

This defensive emphasis surprised me. It suggested that these researchers have often been questioned on the usefulness of their simulations for the study of evolution.

In this post, I want to reflect on some reasons for such questioning.

Read more of this post

Labyrinth: Fitness landscapes as mazes, not mountains

Tonight, I am passing through Toulouse on my way to Montpellier for the 2nd Joint Congress on Evolutionary Biology. If you are also attending then find me on 21 August at poster P-0861 on level 2 to learn about computational complexity as an ultimate constraint on evolution.

During the flight over, I was thinking about fitness landscapes. Unsurprising — I know. A particular point that I try to make about fitness landscapes in my work is that we should imagine them as mazes, not as mountain ranges. Recently, Raoul Wadham reminded me that I haven’t written about the maze metaphor on the blog. So now is a good time to write on labyrinths.

On page 356 of The roles of mutation, inbreeding, crossbreeding, and selection in evolution, Sewall Wright tells us that evolution proceeds on a fitness landscape. We are to imagine these landscapes as mountain ranges, and natural selection as a walk uphill. What follows — signed by Dr. Jorge Lednem Beagle, former navigator of the fitness maze — throws unexpected light on this perspective. The first two pages of the record are missing.

Read more of this post

Darwin as an early algorithmic biologist

In his autobiography, Darwin remarked on mathematics as an extra sense that helped mathematicians see truths that were inaccessible to him. He wrote:

Darwin Turing HeadbandDuring the three years which I spent at Cambridge… I attempted mathematics… but got on very slowly. The work was repugnant to me, chiefly from my not being able to see any meaning in the early steps in algebra. This impatience was very foolish, and in after years I have deeply regretted that I did not proceed far enough at least to understand something of the great leading principles of mathematics, for [people] thus endowed seem to have an extra sense. But I do not believe that I should ever have succeeded beyond a very low grade. … in my last year I worked with some earnestness for my final degree of B.A., and brushed up … a little Algebra and Euclid, which later gave me much pleasure, as it did at school.

Today, this remark has become a banner to rally mathematicians interested in biology. We use it to convince ourselves that by knowing mathematics, we have something to contribute to biology. In fact, the early mathematical biologist were able to personify the practical power of this extra sense in Gregor Mendel. From R.A. Fisher onward — including today — mathematicians have presented Mendel as one of their own. It is standard to attributed Mendel’s salvation of natural selection to his combinatorial insight into the laws of inheritance — to his alternative to Darwin’s non-mathematical blending inheritance.

But I don’t think we need wait for the rediscovery of Mendel to see fundamental mathematical insights shaping evolution. I think that Darwin did have mathematical vision, but just lacked the algorithmic lenses to focus it. In this post I want to give examples of how some of Darwin’s classic ideas can be read as anticipating important aspects of algorithmic biology. In particular, seeing the importance of asymptotic analysis and the role of algorithms in nature.
Read more of this post

Proximal vs ultimate constraints on evolution

For a mathematician — like John D. Cook, for example — objectives and constraints are duals of each other. But sometimes the objectives are easier to see than the constraints. This is certainly the case for evolution. Here, most students would point you to fitness as the objective to be maximized. And at least at a heuristic level — under a sufficiently nuanced definition of fitness — biologists would agree. So let’s take the objective as known.

This leaves us with the harder to see constraints.

Ever since the microscope, biologists have been expert at studying the hard to see. So, of course — as an editor at Proceedings of the Royal Society: B reminded me — they have looked at constraints on evolution. In particular, departures from an expected evolutionary equilibrium is where biologists see constraints on evolution. An evolutionary constraint is anything that prevents a population from being at a fitness peak.

Winding path in a hard semi-smooth landscape

In this post, I want to follow a bit of a winding path. First, I’ll appeal to Mayr’s ultimate-proximate distinction as a motivation for why biologists care about evolutionary constraints. Second, I’ll introduce the constraints on evolution that have been already studied, and argue that these are mostly proximal constraints. Third, I’ll introduce the notion of ultimate constraints and interpret my work on the computational complexity of evolutionary equilibria as an ultimate constraint. Finally, I’ll point at a particularly important consequence of the computational constraint of evolution: the possibility of open-ended evolution.

In a way, this post can be read as an overview of the change in focus between Kaznatcheev (2013) and (2018).
Read more of this post

Heuristic models as inspiration-for and falsifiers-of abstractions

Last month, I blogged about abstraction and lamented that abstract models are lacking in biology. Here, I want to return to this.

What isn’t lacking in biology — and what I also work on — is simulation and heuristic models. These can seem abstract in the colloquial sense but are not very abstract for a computer scientist. They are usually more idealizations than abstractions. And even if all I care about is abstract models — which I can reasonably be accused of at times — then heuristic models should still be important to me. Heuristics help abstractions in two ways: portfolios of heuristic models can inspire abstractions, and single heuristic models can falsify abstractions.

In this post, I want to briefly discuss these two uses for heuristic models. In the process, I will try to make it a bit more clear as to what I mean by a heuristic model. I will do this with metaphors. So I’ll produce a heuristic model of heuristic models. And I’ll use spatial structure and the evolution of cooperation as a case study.

Read more of this post

Algorithmic lens as Alan Turing’s wider impact

Today is Alan Turing’s birthday. He would have turned 106.

It has been too long since I last wrote about him on TheEGG. Today, I want to provide an overview of some of his most important work based on my and other’s answers on this old cstheory question. This will build slightly on a post I wrote two years ago for the Heidelberg Laureate Forum, but it will share a lot of text in common.

Turing is far from obscure. Every computer scientist and programmer has heard his name. The Nobel prize of Computer Science is named after him. He has even joined the ranks of mathematicians with feature-length films. Although a film that misrepresents much history. But even outside of film, I feel that our perceptions and representations of Turing are shaped too heavily by the current boundaries and constraints of computer science. Or at least how computer science is popularly (mis)understood.

Also, it is just easier to film the building a giant machine than about proving theorems and revolutionizing how we think about the world.

As the great breadth of his work shows, Turing would not recognize the disciplinary boundaries that confine computer science to technology. Like Abel Molina, he would see many motivations for computer science, from Science and Technology to Mathematics and Philosophy to Society. Turing viewed the whole world through the algorithmic lens. A wide ambition that is sometimes lacking in modern computer science.

In this post, I want to highlight some of the aspects of the world that Turing looked at.
Read more of this post

Double-entry bookkeeping and Galileo: abstraction vs idealization

Two weeks ago, I wrote a post on how abstract is not the opposite of empirical. In that post, I distinguished between the colloquial meaning of abstract and the ‘true’ meaning used by computer scientists. For me, abstraction is defined by multiple realizability. An abstract object can have many implementations. The concrete objects that implement an abstraction might differ from each other in various — potentially drastic — ways but if the implementations are ‘correct’ then the ways in which they differ are irrelevant to the conclusions drawn from the abstraction.

I contrasted this comp sci view with a colloquial sense that I attributed to David Basanta. I said this colloquial sense was just that an abstract model is ‘less detailed’.

In hindsight, I think this colloquial sense was a straw-man and doesn’t do justice to David’s view. It isn’t ignoring any detail that makes something colloquially abstract. Rather, it is ignoring ‘the right sort of’ detail in the ‘right sort of way’. It is about making an idealization meant to arrive at some essence of a (class of) object(s) or a process. And this idealization view of abstraction has a long pedigree.

In this post, I want to provide a semi-historical discussion of the the difference between (comp sci) abstraction vs idealization. I will focus on double-entry bookkeeping as a motivation. Now, this might not seem relevant to science, but for Galileo it was relevant. He expressed his views on (proto-)scientific abstraction by analogy to bookkeeping. And in expressing his view, he covered both abstraction and idealization. In the process, he introduced both good ideas and bad ones. They remain with us today.

Read more of this post

Abstract is not the opposite of empirical: case of the game assay

Last week, Jacob Scott was at a meeting to celebrate the establishment of the Center for Evolutionary Therapy at Moffitt, and he presented our work on measuring the effective games that non-small cell lung cancer plays (see this preprint for the latest draft). From the audience, David Basanta summarized it in a tweet as “trying to make our game theory models less abstract”. But I actually saw our work as doing the opposite (and so quickly disagreed).

However, I could understand the way David was using ‘abstract’. I think I’ve often used it in this colloquial sense as well. And in that sense it is often the opposite of empirical, which is seen as colloquially ‘concrete’. Given my arrogance, I — of course — assume that my current conception of ‘abstract’ is the correct one, and the colloquial sense is wrong. To test myself: in this post, I will attempt to define both what ‘abstract’ means and how it is used colloquially. As a case study, I will use the game assay that David and I disagreed about.

This is a particularly useful exercise for me because it lets me make better sense of how two very different-seeming aspects of my work — the theoretical versus the empirical — are both abstractions. It also lets me think about when simple models are abstract and when they’re ‘just’ toys.

Read more of this post