## Monday, 17 August 2009

### The Psychology of Grit

This is in response to Aida's post, but since it became fairly long i decided to promote it from a comment to a post. That should particularly please anyone reading this on google reader. You know who you are.

I find this all very interesting. I think that Aida's intuitions are quite correct. I think that for different problems it's certainly going to be the case that different commitment levels are optimal. How can we decide what level of commitment to use for a particular problem?

In fact algorithms for exploring state space do exist and do have to quantify 'grit'. For instance, if we want to seek the lowest potential minimum of a state space, or for the more poetically inclined, the lowest valley of a mountain range, we could choose an algorithm that bounces around wildly (low grit) or one that calmly proceeds to the bottom of it's current minimum (high grit). Which is more efficient at quickly finding the lowest valley actually depends on the specifics of the mountain range - if there's lots of local minima a calm algorithm might get trapped, but if there's an large obvious valley then a wild algorithm will bounce around and waste too much time.

This problem is one that computer scientists have put a fair amount of effort into studying. Take the case where you have to interview candidates for a job. In this thought experiment we're going to assume that you have to accept or reject the candidate at the end of the interview - there's no phoning back later. Under these conditions what is the most effective way to get the best person?

It turns out that the best method (and i think that this is provably the most efficient method) is to interview the first 33% of the candidates, remember the best one, then offer the job to the next candidate who is better than that. The fascinating thing is that it's been speculated that humans use a similar algorithm when picking a mate. When we're young we tend to date various different people. This is the equivalent of the interviewing the first 33% of candidates. In later years, when we decide to settle down, there is some evidence that people pick the next person who is 'better' than the best person that they dated when they were young. It shouldn't be that surprising though, as evolution has had a whole lot of time to optimise these algorithms (aside: i wonder what the most efficient algorithm is for optimising an algorithm).

I think that we can now rephrase Aida's question. What do the potential landscapes look like for various different decisions that we have to make in life? If we know this then we can use the collected knowledge of computer science to pick the most efficient algorithm to make our choices.

As noted above, for any activity that existed in the pleistocene era (when humanity was evolving) you probably can't do much better than your natural reactions. For other, more modern problems, we can probably greatly improve on our natural instincts.

Taking it one step further - can we quantifiably create a potential map of the outcomes of a decision*? I think that it should be possible to create some sort of restricted map of something useful - my first instinct is to try with the job market because salary is a nice indicator of depth of valley. I'm just not sure how to quantify distance between jobs i.e. where grit would come in. Maybe job adverts describing essential and useful skills could provide a route to which jobs you can jump between?

Any thoughts?

*(i guess this is now straying pretty close to game theory, although it may be a slightly different approach to that taken by game theorists, certainly when they solve the simplest of their scenarios - the only ones i'm familiar with)

"i wonder what the most efficient algorithm is for optimising an algorithm"

ReplyDeleteYou could apply the Darwinian optimiser: kill the least successful algorithms. That's the basis of comp sci "genetic algorithms".

It's true that genetic algorithms would allow us to explore the state space of other algorithms (as would some other options), but I was wondering about the provably most efficient algorithm. I suspect that we simply don't know, but i thought i'd throw it out there.

ReplyDeleteProving that there was no more efficient algorithm would be along the lines of a general solution to the halting problem. In other words, it's impossible.

ReplyDeleteI'm not sure I agree.Or at least it depends what you're referring to.

ReplyDeleteIf you mean that, under any circumstances, it's impossible to show that you have the most efficient possible algorithm for a particular task - then i disagree. As you i'm sure you know, the halting problem is only a problem over all possible program input pairs. It doesn't mean that every problem ever is undecidable. In a simple instance you can know whether a program is going to halt. So it becomes a question of whether 'the most efficient algorithm to search through possible algorithms' is a simple problem.

If you have good reason (effectively a mathematical proof or knowledge of one - I would almost be surprised if this didn't exist) to think that finding a solution to the problem of 'the most efficient algorithm to search through possible algorithms' is going to involve a general solution to the halting problem then I agree that would mean it was never possible to know.

An answer along the lines of 'it can never be known whether you have the most efficient algorithm for searching for an algorithm because to do so would involve solving the halting problem' is exactly the sort I was hoping for when i posed the question. I'd just like a semi-formal proof of why that was the case.

I do agree when you rephrase the problem like this, assuming you're referring to this specific instance, my intuition says that it won't be possible to know.

@Marc

ReplyDeleteAn answer along the lines of 'it can never be known whether you have the most efficient algorithm for searching for an algorithm because to do so would involve solving the halting problem' is exactly the sort I was hoping for when i posed the question. I'd just like a semi-formal proof of why that was the case.

I do agree when you rephrase the problem like this, assuming you're referring to this specific instance, my intuition says that it won't be possible to know.

Your intuition serves you well. To the best of my knowledge and belief (as a mere computer scientist), there is no generalised way of reasoning about all algorithms. A (semi-)formal proof of that would be along the lines of proving a negative.