Fighting about frequency and randomly generating fitness landscapes

A couple of months ago, I was in Cambridge for the Evolution Evolving conference. It was a lot of fun, and it was nice to catch up with some familiar faces and meet some new ones. My favourite talk was Karen Kovaka‘s “Fighting about frequency”. It was an extremely well-delivered talk on the philosophy of science. And it engaged with a topic that has been very important to discussions of my own recent work. Although in my case it is on a much smaller scale than the general phenomenon that Kovaka was concerned with,

Let me first set up my own teacup, before discussing the more general storm.

Recently, I’ve had a number of chances to present my work on computational complexity as an ultimate constraint on evolution. And some questions have repeated again and again after several of the presentations. I want to address one of these persistent questions in this post.

How common are hard fitness landscapes?

This question has come up during review, presentations, and emails (most recently from Jianzhi Zhang’s reading group). I’ve spent some time addressing it in the paper. But it is not a question with a clear answer. So unsurprisingly, my comments have not been clear. Hence, I want to use this post to add some clarity.

Let’s look at the general storm that Kovaka has identified: debates over frequency. Or debates over how typical certain effects are.

Whenever two or more interesting mechanisms or phenomena that are at odds with each other arise in biology, a debate emerges: how frequent is X? Are most cases Y, with X as just an edge case? Do most systems follow Y? Does X matter more? And other similar questions are asked.

Scientists then aggregate themselves into communities that bifurcate around the answers.

You can see this happening to some extent in polls run by Jeremy Fox on controversial ideas in ecology, and by Andrew Hendrey on controversial ideas in evolution. And Kovaka argues that the majority of fights in biology.

Sometimes it feels like these questions could be resolved empirically. But from Kovaka’s study, this is seldom the case. Heated frequency debates are not resolved empirically. In fact, they usually just peter out and fade. In some sense, it can feel in hindsight that these controversites don’t matter.

Let’s look at this in the context of my work on computational complexity.

I introduce the notion of easy landscapes, where the computation is not the limiting constraint, and populations can quickly find local fitness peaks. These describe how biologists have mostly thought about static fitness landscapes. As a contrast, I also define hard landscapes where computational is a limiting constraint and thus populations cannot find a local fitness peak in polynomial time. Within a hard landscape, you can easily resolve the frequency debate: no local peak can be found in polynomial time from most starting points, following any evolutionary dynamic (or any polynomial time algorithm more generally).

To establish this, I carry over several techniques from computer science. Most relevant to this case: worst case analysis.

A big difficulty arises in introducing radically different tools from theoretical computer science into biology. They require a thorough defence that I was hoping to delay until after I could attribute some success to the tools. But a careful reviewer 2 noticed this sleight-of-hand and asked me to mount the defence right away. A defence of worst-case analysis. I’ve know since at least 2014 that I’d have to provide compelling arguments. So before the paper was published, I already mounted a partial defence in the text, and more carefully in appendix D.3.

I’d encourage you to read these if you’re interested, dear reader. But I’ll try to discuss the same content in a slightly different way here.

I don’t reason about randomly generated fitness landscapes or the corresponding probability distributions over fitness landscapes. As such, I show the existence of hard fitness landscapes but I cannot reason about the likelihood of such instances. This is not a bug — it’s a feature. I don’t think it makes sense to talk about random fitness landscapes.

As reviewer 2 noted (and as I incorporated into the final text), this is a cultural difference between theoretical computer science and statistical physics. Since statistical physics provides the currently dominant toolset in evolutionary biology, I have an uphill struggle. But I think that cstheory is in the right here.

Fitness landscapes are huge objects. Hyper-astronomical objects. And although we’ve made some measurements of tiny landscapes or local snapshots of more realistic landscapes, it is conceptually impossible to measure a full fitness landscape exhaustively. They are simply too big.

If we can’t measure even one particular object. How is it reasonable to define a distribution that generates these objects? How would we ever test the reasonableness of this generating distribution?

More importantly, fitness landscapes are particular. A zebra is on a particular fitness landscape that exists due to various physical and biological laws. There isn’t some process that has generated random landscapes and some species ended up on some and some on others.

But these are ontological arguments. Let’s make a pragmatic one.

When people discuss classical fitness landscape results. They often talk about logical properties like the degree of epistasis and size of the landscape — but they seldom explicitly discuss (or change) the sampling distribution. They speak as if the assumed generating distribution is not an assumption, but just ignorance. An ignorance that doesn’t bias the conclusion.

But this isn’t the case for such high dimensional objects. In these cases, randomness gives structure. And that structure is highly dependent on the sampling distribution.

In the case of easy vs hard landscapes, I expect hardness results to be extremely sensitive to sampling distributions. I believe this since similar results exist for similar models, although I haven’t proved them yet for the NK-model. In particular, I expect that for samples from uniform distributions (even when properly defined to avoid the simple span arguments we can make against current distributions), hard landscapes will be rare. But if we sample from the inverse Kolmogorov distribution (i.e. landscapes with short descriptions are more likely than landscapes with long descriptions — like Occam’s razor) then my asymptotic hardness results will cary over: hard landscapes will be common.

Yet both the uniform distribution and Occam’s razor can be defended as reasonable choices of distribution. During a recent conversation, Colin Twomey even made a compeling argument for the direct opposite of Occam’s razor: that ‘typical’ fitness landscapes are the incompressible ones. So what should we make of this sensitivity of the model? We can’t use this to answer how frequent fitness landscapes are, but maybe that wasn’t the right question.

In the more general context, Kovaka gives us a way forward. She points out that the talk of ‘frequency’ is actually not important in general biological fights over frequency. This wording is just a frame and if taking literally, it seldom contributes to actual advancement of the field. What matters instead, is that in the process of arguing about how typical or rare particular phenomena or mechanisms are, biologists learn the logical limits and boundaries of these phenomena much better. It is these logical characterizations and interconnections that form the lasting contribution of frequency debates. It is these logical characterizations that showcase the causal patterns and regularities of phenomena. It is these logical characterizations that explain how a particular pattern will be established in future cases. In the end, it ends up that we do not actually want to know the frequency but instead the particular conditions for a pattern.

So what does this mean in the context of fitness landscapes? It means that we should do the next step that cstheory points us to: parametrized complexity. Figure out what logical features of (the descriptions of) fitness landscapes can guarantee easy ones and which can’t.

I am currently working on this. And I hope it ends up with more helpful questions than “how common are hard landscapes?”

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

8 Responses to Fighting about frequency and randomly generating fitness landscapes

  1. Boris Borcic says:

    Hello Artem,

    > “computational complexity as an ultimate constraint on evolution”

    Given how *simple* a group the Monster notoriously is, “complexity” above, sets M safely away from belonging among “ultimate constraints on evolution”;) To further dispel the idea M should if possible be displayed in the act of dividing the complexity of some computation by its own mighty order.

    Sorry, this is like private poetry, but your prose wakes musings of decades back

  2. mimblewabe says:

    Let me try to reframe your point to see if I understand: landscapes can be so intractable that some questions about them are not worth studying (yet? ever?).

    Assuming that is what you’re saying, it’s rational to focus on just the parts of the theory where you can make progress. At the same time, if the theory is ever to be useful in practice, you need to be able to recognize landscapes of particular biological systems you want to study. It’s hard to see how statistics could be avoided here, you need to be able to infer landscapes from measurements. Unless, of course, you fix some arbitrary landscape a priori—but if landscapes are so huge, how do you know you picked the right one? Again, you need to be able to talk about families of landscapes and compare them.

    So is it the case that your work is purely theoretical? Or are there practical applications that somehow avoid landscape inference?

    • I don’t think that I am arguing against measuring landscapes (except in so far as saying that a complete measurement without any inference is impossible due to the exponential size of a landscape). But I am arguing against distributions of landscapes (in either theoretical or experimental work). In experimental work, I am arguing against assuming particular distributions a priori and then estimating the parameters of said distributions of landscapes.

      One can measure particular landscapes without trying to fit them to some distribution that generates landscapes. Of course, this is non-trivial and requires us to limit ourselves to a reasonable a priori hypothesis class. Such a hypothesis would have a logical characterization which I think is more useful than assuming a particular (convenient for analysis) generating distribution.

      How should we pick our hypothesis class? That is an interesting question. We certainly want it to be expressable enough to capture interesting features and questions about landscapes. But we don’t want it to be so expressive that it becomes unlearnable.

      • mimblewabe says:

        Sorry, haven’t noticed your answer.

        In my dictionary, measurement comes with a statistical model and a distribution of likely values (since no measurement is ever exact). I understand that landscape distributions might be intractable but then what does measurement even mean in this context?

        The last paragraph is intriguing, sounds like something a machine learning researcher might say. I wonder: have you written anything about connections between landscapes and ML?

      • Boris Borcic says:

        > (measurement without any inference is impossible due to the exponential size of a landscape)

        (wouldn’t “hyperbolic” be more insightful than “exponential”?)

        I mean, I’ve a sense that “hyperbolic” would better harmonize with a situation where is undecided whether the landscape is time-varying. A situation I find interesting to contemplate.

  3. Pingback: Friday links: regression to the mean vs. the purple-snouted crompus, profs vs. meetings, and more | Dynamic Ecology

  4. Pingback: The gene-interaction networks of easy fitness landscapes | Theory, Evolution, and Games Group

  5. Pingback: Generating random power-law graphs | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: