Hill Climbing in real life

Fifteen years back, I enrolled for a course on Artificial Intelligence as part of my B.Tech. programme at IIT Madras. It was well before stuff like “machine learning” and “data science” became big, and the course was mostly devoted to heuristics. Incidentally, that term, we had to pick between this course and one on Artificial Neural Networks (I guess nowadays that one is more popular given the hype about Deep Learning?), which meant that I didn’t learn about neural networks until last year or so.

A little googling tells me that Deepak Khemani, who taught us AI in 2002, has put up his lectures online, as part of the NPTEL programme. The first one is here:

In fact, the whole course is available here.

Anyways, one of the classes of problems we dealt with in the course was “search”. Basically, how does a computer “search” for the solution to a problem within a large “search space”?

One of the simplest heuristic is what has come to be known as “hill climbing” (too lazy to look through all of Khemani’s lectures and find where he’s spoken about this). I love computer science because a lot of computer scientists like to describe ideas in terms of intuitive metaphors. Hill climbing is definitely one such!

Let me explain it from the point of view of my weekend vacation in Edinburgh. One of my friends who had lived there a long time back recommended that I hike up this volcanic hill in the city called “Arthur’s Peak“.

On Saturday evening, I left my wife and daughter and wife’s parents (who I had travelled with) in our AirBnB and walked across town (some 3-4 km) to reach Holyrood Palace, from where Arthur’s Seat became visible. This is what I saw: 

Basically, what you see is the side of a hill, and if you see closely, there are people walking up the sides. So what you guess is that you need to make your way to the bottom of the hill and then just climb.

But then you make your way to the base of the hill and see several paths leading up. Which one do you take? You take the path that seems steepest, believing that’s the one that will take you to the top quickest. And so you take a step along that path. And then see which direction to go to climb up steepest. Take another step. Rinse. Repeat. Until you reach a point where you can no longer find a way up. Hopefully that’s the peak.

Most of the time, you are likely to end up on the top of a smaller rock. In any case, this is the hill climbing algorithm.

So back to my story. I reached the base of the hill and set off on the steepest marked path.

I puffed and panted, but I kept going. It was rather windy that day, and it was threatening to rain. I held my folded umbrella and camera tight, and went on. I got beautiful views of Edinburgh city, and captured some of them on camera. And after a while, I got tired, and decided to call my wife using Facetime.

In any case, it appeared that I had a long way to go, given the rocks that went upwards just to my left (I was using a modified version of hill climbing in that I used only marked paths. As I was to rediscover the following day, I have a fear of heights). And I told that to my wife. And then suddenly the climb got easier. And before I knew it I was descending. And soon enough I was at the bottom all over again!

And then I saw the peak. Basically what I had been climbing all along was not the main hill at all! It was a “side hill”, which I later learnt is called the “Salisbury Crags”. I got down to the middle of the two hills, and stared at the valley there. I realised that was a “saddle point”, and hungry and tired and not wanting to get soaked in rain, I made my way out, hailed a cab and went home.

I wasn’t done yet. Determined to climb the “real peak”, I returned the next morning. Again I walked all the way to the base of the hill, and started my climb at the saddle point. It was a tough climb – while there were rough steps in some places, in others there was none. I kept climbing a few steps at a time, taking short breaks.

One such break happened to be too long, though, and gave me enough time to look down and feel scared. For a long time now I’ve had a massive fear of heights. Panic hit. I was afraid of going too close to the edge and falling off the hill. I decided to play it safe and turn back.

I came down and walked across the valley you see in the last picture above. Energised, I had another go. From what was possibly a relatively easier direction. But I was too tired. And I had to get back to the apartment and check out that morning. So I gave up once again.

I still have unfinished business in Edinburgh!

 

Ladder Theory and Local Optima

According to the Ladder Theory, women have two “ladders”. One is the “good ladder” where they rank and place men they want to fuck. The rest of the men get placed on the “friends ladder”. Men on the other hand have only one ladder (though I beg to disagree).

The question is what your strategy should be if you end up on top of the “wrong” (friends) ladder. On the one hand, you get your “dove“‘s attention and mostly get treated well there. On the other hand, that’s not where you intended to end up.

Far too many people at the top of the friends ladder remain there because they are not bold enough to take a leap. They think it is possible to remain there (so that they “preserve the friendship”) and at the same time make their way into the dove’s good ladder.

Aside 1: The reason they want to hold on to their friendship (though that’s not the reason they got close to the dove) can be explained by “loss aversion” – having got the friendship, they are loathe to let go of it. This leads them to pursuing a risk-free strategy, which is unlikely to give them a big upside.

Aside 2: A popular heuristic in artificial intelligence is Hill Climbing , in which you constantly take the path of maximum gradient. It can occasionally take you to the global maximum, but more often than not leaves you at a “local maximum”. Improvements on hill climbing (such as Simulated Annealing) all involve occasionally taking a step down in search of higher optimum.

Behavioural economics and computer science aside, the best way to analyse the situation when you’re on top of the friends ladder is using finance. Financial theory tells you that it is impossible to get a large risk-free upside (for if you could, enough people would buy that security that the upside won’t be significant any more).

People on top of the friends ladder who want to preserve their friendships while “going for it” are delusional – they want the risk-free returns of the friendship at the same time as the possibility of the grand upside of getting to the right ladder. They should understand that such trades are impossible.

They should also understand that they might be putting too high a price on the friendship thanks to “loss aversion”, and that the only way to escape the current “local optimum” is by risking a downward move. They should remember that the reason they got close to their dove was NOT that they end up on the friends ladder, and should make the leap (stretching the metaphor). They might end up between two stools (or ladders in this case), but that might be a risk well worth taking!

PS: this post is not a result of my efforts alone. My Wife, who is a Marriage Broker Auntie, contributed more than her share of fundaes to this, but since she’s too lazy to write, I’m doing the honours.