The Metaphor of the Hills

Imagine that one day you’re standing on a very foggy field of grassy hills. It’s so foggy you can’t see even an inch in front of your nose, and what’s worse, you have no GPS or 4G reception. You decide to try to climb up one of those hills; maybe if you’re higher up you’ll be able to see something, or at least get some GPS signal.

Now, you can’t really see anything, so to start out you have to sort of fumble in the fog. You take a tentative step forward, and that doesn’t change anything. You take another, and you actually get to ground that’s a bit lower than where you were, so you take a step back. You try going left, and there the ground’s higher. On you go, fumbling around, trying to find somewhere with some at least minimal GPS reception.

Eventually you reach the top of one hill. There’s some GPS reception there; it’s not great, it’s in fact pretty crappy, but at least it’s there, unlike down where you started out. Except… what if there’s a higher hill somewhere nearby? You only found the one hill, and the only way to find another would be going back down again, and in this fog, there are no guarantees that you’ll even find your way back up the same hill you just climbed; you might even get lost and end up at a shorter hill, and that’d be pretty awful.

So, in sum, you’re faced with two choices: you can either continue exploring the landscape, or you can try to exploit what you have found. Maybe Google Maps will load in less than an hour, who knows?

You might be thinking now that this is a metaphor for something, and of course you’d be right. I mean, what would be the point of me even mentioning imaginary hill fields? How did you even get there in the first place? And where’d the fog come from? And what earthly carrier are you even using that can’t give you reception in the middle of an open field? Also there’s the title of the post which should be a dead giveaway. So, yeah, metaphor.

In this little story, your actions could be well described as an optimisation process: you were trying to optimise for something (height), so you followed a set of behaviours that you believed would get you to a better situation than you’d been in. Now, this was an admittedly poor algorithm to follow, but given how little you could see in this fog, I think it’s understandable that you couldn’t really do anything better. And the fact that the fog didn’t let you see where you were going meant that you didn’t really have a sense of direction, you couldn’t look for the highest hill around and just go there. Your optimisation was strictly local. And you know what other optimisation process behaves just like that?

Evolution does.

How exactly? Think about how it works: new individuals suffer random mutations, and in the long term these mutations either make this individual fitter (i.e. producing more/healthier offspring more efficiently) or less fit1. So if you think of evolutionary “fitness” as the height in our metaphor, and the fumbling steps as random genetic mutations, then what evolution really does is just explore this “fitness landscape” randomly and trying to find (if I may anthropomorphise it) higher ground.

And this also sheds light on the suboptimality of the blind idiot god’s methods. Evolution just can’t do globally optimal in general. If evolution settled on a particular feature for a species, this may be just because it never walked in the right direction. And the fact that the highest hill can be very, very far from the second highest hill means that this random walk may very well never reach a global highest point no matter what.

Not to mention that the fitness landscape is actually not as much like a field of grassy hills as it is like a desert with ever-shifting dunes: as a species’ environment changes, maybe because of climate or migration or a natural disaster, genes that used to code for locally optimal structures may become very useless. Vestigial structures like the appendix, wisdom teeth and the inside corner of the eye are examples of things that have long since lost their “original function” but remain there as a fossil of a time when our desert looked much different.

And this is yet another important insight: you can never start over. You can never return to your starting point in this night desert; it may not even be there anymore, with the constant shifts in the dunes. Everything you build is built on top of what’s already there; everywhere you go, you can only go from where you currently are.

There are other phenomena you can more-or-less approximate or think of as this landscape. For example, society as a whole, or any specific aspect of it. When something changes in society – a new government system is tried, or even just a new president, or some new technology is invented -, things can get better or worse. People have new ideas, stuff happens, and it’s more-or-less random how good or bad a thing is. But as it changes, society can’t really go back to where it was, and if it so happens that we’re at or near the top of some hill so that most changes make stuff worse, there might be no increasingly bettering path to a more desirable world.

And using this metaphor, we can characterise a Revolution (like the far left sometimes talks about) in an interesting way: a leap of faith in a random direction, going farther than a single step, and forbidding you to just take it back and return where you came from. And the thing is, this is not a wholly bad idea! If you know your hill isn’t high enough, and it could be higher, the best you can do may just be trying to go somewhere else and try your luck.

…but of course, this does not work most of the time. You’re at a local optimum, and with all this damn fog you really can have no clue about how much better – or worse! – things can get. And yes, it is a pretty thick fog: everyone thought communism was going to be great before it was actually tried, so even when you think your leap is more-or-less guided, you can still land somewhere crappy and end up on top of a pretty crappy hill.

So that’s not really enough to justify the leap, is it? Let’s make this metaphor a bit more complex: suppose that in addition to blocking your GPS signal, this mysterious fog is very unevenly varied in temperature in a way that’s not necessarily correlated with height, so that as you walk the place can get warmer or colder. Now you’re optimising for two things: height, and temperature. And yeah, maybe you’re at a pretty high hill, but if it’s so cold you’re freezing your toes off, the leap I mentioned might just look quite desirable. It’s no surprise that Revolutions are usually caused by people with fairly bad lives: sure, it may be quite a nice high hill, but you don’t have a coat or a blanket and it’s cold and surely there must be a better place.

This foggy hill that changes temperature is what we call a multi-objective landscape. When you were trying to just find the highest hill, life was simple, and every step you took always had an obvious change associated with it. But if the temperature changes, too, sometimes there may be no global optimum, nowhere the temperature is perfect and the height is maximal. Maybe every change you make, every step you take, is a trade-off between height and temperature. Want to go higher? Alright, but it’ll get you colder. Want to get warmer? Fantastic, but you’re sacrificing your GPS signal.

When it’s possible to take a step that brings us closer to the optimum of one goal without bringing us farther from any other goal’s optimum, that step is called a Pareto improvement. A path in our optimisation landscape that has the property that every positive change in one goal is met with a negative change in at least one other goal is called a Pareto frontier or Pareto optimal, when it’s no longer possible to make any Pareto improvements.

It’s clear that most optimisation problems are in fact multi-objective, in real life. Sometimes you can make choices that only affect one thing you care about in any significant way, but sometimes you can’t, and a significant challenge of building a coherent Utility Function is exactly balancing the many things we care about and figuring how just how to compare them and add them together. Is it even possible? Well, clearly, we make choices all the time, but it’s no less hard.

Every problem is a field of hills. As humans, with a human imagination, sometimes our hills have less fog than this. Sometimes the problem is simple enough that it has only one hill, visible from miles away. But most of the time, it doesn’t; most of the time, there’s fog; most of the time, even if you have found a very good solution, you have not found the very best possible solution. And sometimes you just can’t, and need to make do with what you have found.2

1This is in fact incorrect. Genes are successful inasmuch as their presence causes their own frequency in the population to grow over time. While it’s true that this is usually attained by making sure the individual’s lineage does better than its competitors’ relatively speaking, that may not always be the case. For example, think about a hypothetical dominant mutation that causes a species’ genome to become thenceforth incapable of further mutations. A moment’s thought shows that this gene will very rapidly take over the population and the first time some environmental shift causes that species’ conditions to alter it will go extinct due to an inability to adapt to its new selective pressures; the species would have literally evolved to extinction. Less contrived examples exist in nature.

2I apologise for the mess that this post is. I haven’t really written in a while and kinda just wrote it as it came, and didn’t review it. Still, I hope it was useful!

Advertisements
This entry was posted in Computer Science, Intuitive Mathematics, Mathematics, Philosophy, Rationality and tagged , , . Bookmark the permalink.

2 Responses to The Metaphor of the Hills

  1. Will says:

    I think you are confused about some things. The hill climbing algorithm you are describing is gradient ascent, and it’s very easy for it to get stuck in a local optimum. Genetic algorithms with large enough populations are much LESS likely to get stuck in local optima (it still happens). They are very slow optimization methods, but what you lose in speed you gain in the probability you find the max.

    Consider, instead of climbing the hill, randomly populate people across the landscape. Now take the N highest members and “breed them” by doing weighted averages of their locations. Throw out the rest of the population. Keep doing this and you’re much more likely to find the highest hill than if you had started randomly in the landscape and simply taken steps upward.

  2. pedromvilar says:

    Er… You seem to have missed the point of the post, which is quite simply to present the notion of an “optimisation process” to someone who isn’t familiar with it.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s