Maths, machine learning, brute force and elegance

Back when I was at the International Maths Olympiad Training Camp in Mumbai in 1999, the biggest insult one could hurl at a peer was to describe the latter’s solution to a problem as being a “brute force solution”. Brute force solutions, which were often ungainly, laboured and unintuitive were supposed to be the last resort, to be used only if one were thoroughly unable to implement an “elegant solution” to the problem.

Mathematicians love and value elegance. While they might be comfortable with esoteric formulae and the Greek alphabet, they are always on the lookout for solutions that are, at least to the trained eye, intuitive to perceive and understand. Among other things, it is the belief that it is much easier to get an intuitive understanding for an elegant solution.

When all the parts of the solution seem to fit so well into each other, with no loose ends, it is far easier to accept the solution as being correct (even if you don’t understand it fully). Brute force solutions, on the other hand, inevitably leave loose ends and appreciating them can be a fairly massive task, even to trained mathematicians.

In the conventional view, though, non-mathematicians don’t have much fondness for elegance. A solution is a solution, and a problem solved is a problem solved.

With the coming of big data and increased computational power, however, the tables are getting turned. In this case, the more mathematical people, who are more likely to appreciate “machine learning” algorithms recommend “leaving it to the system” – to unleash the brute force of computational power at the problem so that the “best model” can be found, and later implemented.

And in this case, it is the “half-blood mathematicians” like me, who are aware of complex algorithms but are unsure of letting the system take over stuff end-to-end, who bat for elegance – to look at data, massage it, analyse it and then find that one simple method or transformation that can throw immense light on the problem, effectively solving it!

The world moves in strange ways.

Bayesian recognition in baby similarity

When people come to see small babies, it’s almost like they’re obliged to offer their opinions on who the child looks like. Most of the time it’s an immediate ancestor – either a parent or grandparent. Sometimes it could be a cousin or aunt or uncle as well. Thankfully it’s uncommon to compare babies’ looks to those who they don’t share genes with.

So as people have come up and offered their opinions on who our daughter looks like (I’m top seed, I must mention), I’ve been trying to analyse how they come up with their predictions. And as I observe the connections between people making the observations, and who they mention, I realise that this too follows some kind of Bayesian Recognition.

Basically different people who come to see the baby have different amounts of information on how each of the baby’s ancestors looked like. A recent friend of mine, for example, will only know how my wife and I look. An older friend might have some idea of how my parents looked. A relative might have a better judgment of how one of my parents looked than how I looked.

So based on their experiences in recognising different people in and around the baby’s immediate ancestry, they effectively start with a prior distribution of who the baby looks like. And then when they see the baby, they update their priors, and then mention the person with the highest posterior probability of matching the baby’s face and features.

Given that posterior probability is a function of prior probability, there is no surprise that different people will disagree on who the baby looks like. After all, each of their private knowledge of the baby’s ancestry’s idiosyncratic faces, and thus their priors, will be different!

Unrelated, but staying on Bayesian reasoning, I recently read this fairly stud piece in Aeon on why stereotyping is not necessarily a bad thing. The article argues that in the absence of further information, stereotypes help us form a good first prior, and that stereotypes only become a problem if we fail to update our priors with any additional information we get.

Half life of pain

Last evening, the obstetrician came over to check on the wife, following the afternoon’s Caesarean section operation. Upon being asked how she was, the wife replied that she’s feeling good, except that she was still in a lot of pain. “In how many days can I expect this pain to subside?”, she asked.

The doctor replied that it was a really hard question to answer, since there was no definite time frame. “All I can tell you is that the pain will go down gradually, so it’s hard to say whether it lasts 5 days or 10 days. Think of this – if you hurt your foot and there’s a blood clot, isn’t the recovery gradual? It’s the same in this case”.

While she was saying this, I was reminded of exponential decay, and started wondering whether post-operative pain (irrespective of the kind of surgery) follows exponential decay, decreasing by a certain percentage each day; and when someone says pain “disappears” after a certain number of days, it means that pain goes below a particular  threshold in that time period – and this particular threshold can vary from person to person.

So in that sense, rather than simply telling my wife that the pain will “decrease gradually”, the obstetrician could have been more helpful by saying “the pain will decrease gradually, and will reduce to half in about N days”, and then based on the value of N, my wife could determine, based on her threshold, when her pain would “go”.

Nevertheless, the doctor’s logic (that pain never “disappears discretely”) had me impressed, and I’ve mentioned before on this blog about how I get really impressed with doctors who are logically aware.

Oh, and I must mention that the same obstetrician who operated on my wife yesterday impressed me with her logical reasoning a week ago. My then unborn daughter wasn’t moving too well that day, because of which we were in hospital. My wife was given steroidal injections, and the baby started moving an hour later.

So when we mentioned to the obstetrician that “after you gave the steroids the baby started moving”, she curtly replied “the baby moving has nothing to do with the steroidal injections. The baby moves because the baby moves. It is just a coincidence that it happened after I gave the steroids”.

Bayes and serial correlation in disagreements

People who have been in a long-term relationship are likely to recognise that fights between a couple are not Markovian – in that the likelihood of fighting today is not independent of the likelihood of having fought yesterday.

In fact, if you had fought in a particular time period, it increases the likelihood that you’ll fight in the next time period. As a consequence, what you are likely to find is that there are times when you go days, or weeks, or even months, together in a perennial state of disagreement, while you’ll also have long periods of peace and bliss.

While this serial correlation can be disconcerting at times, and make you wonder whether you are in a relationship with the right person, it is not hard to understand why this happens. Once again, our old friend Reverend Thomas Bayes comes to the rescue here.

This is an extremely simplified model, but will serve the purpose of this post. Each half of a couple beliefs that the other (better?) half can exist in one of two states – “nice” and “jerk”. In fact, it’s unlikely anyone will completely exist in one of these states – they’re likely to exist in a superposition of these states.

So let’s say that the probability of your partner being a jerk is P(J), which makes the probability of him/her being “nice” at P(N) = 1- P(J). Now when he/she does or says something (let’s call this event E), you implicitly do a Bayesian updation of these probabilities.

For every word/action of your partner, you can estimate the probabilities in the two cases of your partner being jerk, and nice. After every action E by the partner, you update your priors about them with the new information.

So the new probability of him being a jerk (given event E) will be given by
P(J|E) = \frac{P(J).P(E|J)}{P(J).P(E|J) + P(N).P(E|N)} (the standard Bayesian  formula).

Now notice that the new probability of the partner being a jerk is dependent upon the prior probability. So when P(J) is already high, it is highly likely that whatever action the partner does will not move the needle significantly. And the longer P(J) stays high, the higher the probability that you’ll lapse into a fight again. Hence the prolonged periods of fighting, and serial correlation.

This equation also explains why attempts to resolve a fight quickly can backfire. When you are fighting, the normal reaction to resolve it is by committing actions that indicate that you are actually nice. The problem is that the equation above has both P(E|N) and P(E|J) in it.

So, in order to resolve a fight, you should not only commit actions that you would do when you are perceived nice, but also actions that you would NOT do if you are a jerk. In other words, the easiest way to pull P(J) down in the above equation is to commit E with high P(E|N) and low P(E|J).

What complicates things is that if you use one such weapon too many times, the partner will will begin to see through you, and up her P(E|J) for this event. So you need to keep coming up with new tricks to defuse fights.

In short, that serial correlation exists in relationship fights is a given, and there is little you can do to prevent it. So if you go through a long period of continuous disagreement with your partner, keep in mind that such things are par for the course, and don’t do something drastic like breaking up.

Horses, Zebras and Bayesian reasoning

David Henderson at Econlog quotes a doctor on a rather interesting and important point, regarding Bayesian priors. He writes:

 Later, when I went to see his partner, my regular doctor, to discuss something else, I mentioned that incident. He smiled and said that one of the most important lessons he learned from one of his teachers in medical school was:

When you hear hooves, think horses, not zebras.

This was after he had some symptoms that are correlated with heart attack and panicked and called his doctor, got treated for gas trouble and was absolutely fine after that.

Our problem is that when we have symptoms that are correlated with something bad, we immediately assume that it’s the bad thing that has happened, and panic. In that process we don’t consider alternate reasonings, and then do a Bayesian analysis.

Let me illustrate with a personal example. Back when I was a schoolboy, and I wouldn’t return home from school at the right time, my mother would panic. This was the time before cellphones, remember, and she would just assume that “the worst” had happened and that I was in trouble somewhere. Calls would go to my father’s office, and he would ask her to wait, though to my credit I was never so late that they had to take any further action.

Now, coming home late from school can happen due to a variety of reasons. Let us eliminate reasons such as wanting to play basketball for a while before returning – since such activities were “usual” and been budgeted for. So let’s assume that there are two possible reasons I’m late – the first is that I had gotten into trouble – I had either been knocked down on my way home or gotten kidnapped. The second is that the BTS (Bangalore Transport Service, as it was then called) schedule had gone completely awry, thanks to which I had missed my usual set of buses, and was thus delayed. Note that me not turning up at home until a certain point of time was a symptom of both of these.

Having noticed such a symptom, my mother would automatically come to the “worst case” conclusion (that I had been knocked down or kidnapped), and panic.   But then I’m not sure that was the more rational reaction. What she should have done was to do a Bayesian analysis and use that to guide her panic.

Let A be the event that I’d been knocked over or kidnapped, and B be the event that the bus schedule had gone awry. Let L(t) be the event that I haven’t gotten home till time t, and that such an event has been “observed”. The question is that, with L(t) having been observed, what are the odds of A and B having happened? Bayes Theorem gives us an answer. The equation is rather simple:

P(A | L(t) ) =  P(A).P(L(t)|A) / (P(A).P(L(t)|A) + P(B).P(L(t)|B) )

P(B|L(t)) is just one minus the above quantity (we assume that there is nothing else that can cause L(t)) .

So now let us give values. I’m too lazy to find the data now, but let’s say we find from the national crime data that the odds of a fifteen-year-old boy being in an accident or kidnapped on a given day is one in a million. And if that happens, then L(t) obviously gets observed. So we have

P(A) = \frac{1}{1000000}
P(L(t) | A) = 1

The BTS was notorious back in the day for its delayed and messed up schedules. So let us assume that P(B) is \frac{1}{100}. Now, P(L(t)|B) is tricky, and the reason the (t) qualifier has been added to L. The larger t is, the smaller the value of L(t)|B. If there is a bus schedule breakdown, there is probably a 50% probability that I’m not home an hour after “usual”. But there is only a 10% probability that I’m not home two hours after “usual” because a bus breakdown happened. So

P(L(1)|B) = 0.5
P(L(2)|B) = 0.1

Now let’s plug in and based on how delayed I was, find the odds that I was knocked down/kidnapped. If I were late by an hour,
P(A|L(1)) = \frac{ \frac{1}{1000000} \ 1 }{ \frac{1}{1000000}  \ 1 + \frac{1}{100} \ 0.5}
or P(A|L(1)) = 0.00019996. In other words, if I didn’t get home an hour later than usual, the odds that I had been knocked down or kidnapped was just one in five thousand!

What if I didn’t come home two hours after my normal time? Again we can plug into the formula, and here we find that P(A|L(2)) = 0.000999 or one in a thousand! So notice that the later I am, the higher the odds that I’m in trouble. Yet, the numbers (admittedly based on the handwaving assumptions above) are small enough for us to not worry!

Bayesian reasoning has its implications elsewhere, too. There is the medical case, as Henderson’s blogpost illustrates. Then we can use this to determine whether a wrong act was due to stupidity or due to malice. And so forth.

But what Henderson’s doctor told him is truly an immortal line:

When you hear hooves, think horses, not zebras.

Deranging groups

Ok so this is a mathematical problem. I plan to give three group assignments to my IIMB class. Let’s assume that there are 60 kids and for each assignment I want them to form groups of four members each. For the first assignment I’ve let them form the groups themselves.

For the second assignment, though, I want to create a “derangement” of these groups – in the sense that I want to form a different set of 15 groups of 4 members each such that no pair of students who are in the same group for assignment 1 will be in the same group for assignment 2. And I’m looking for an algorithm to thus “derange” my students. And whether it is possible at all to derange students thus.

My inclination is that this might have a solution in graph theory – in terms of graph colouring or something? Take the students from the first group and join every pair of students that are in the same group with an edge. Then colour the nodes of the graph. Pick nodes of the same colour (these are students that haven’t been in groups together) and randomly assign them to new groups. Repeat for all colours.

Question is how many colours we need to colour the graph. If it’s planar, we’ll need only 4 colours! And considering that the first assignment has 4 students per group, the maximum degree of a node is 3. If the maximum degree of an edge is 3, does that say anything about the planarity of the graph? If I derange the students once for assignment 2, can I do it again for assignment 3 (now each node has a degree of 6!) ? How do I think about this mathematically? Can you help?

Factorising 2015

Sometimes when I come across a new number I factorise it, just for kicks. So when the year ticked over that’s what I tried doing.

It is intuitive that 2015 is divisible by 5, so I quickly decomposed it into 5 times 403. And then my intuitive reaction was “403 looks prime. So 2015 is such an uninteresting number”.

But then doing the rigorous analysis (dividing 403 by all primes <= 20 (= sqrt (403)), I figured that it goes by 13, and can be decomposed into 13 and 31, which makes it quite interesting!

So 2015 is a product of 5, 13 and 31, which makes it interesting, in that it is a product of relatively small primes!

The year began well here in Bangalore. It started drizzling soon after the clocks ticked over 12, and this morning has also been what people might describe as “gloomy” but what I find to be absolutely romantic weather!

Wish you all a happy and prosperous 2015!