Vedant Misra

Osama bin Laden and Bayesian Search

A technique from operations research called Bayesian search was famously applied to finding vessels lost at sea by John Craven, the US Navy’s Chief Scientist for Special Projects. Given that the recent targeted killing of Osama bin Laden was the work of Navy Seals, it’s possible that directed belief networks were at some point used in the search.

To understand why Bayesian inference is useful in search, consider what you might do if you lost your ring after tripping on the curb.  Suppose your ring landed either in some nearby bushes or on the sidewalk.  Also, suppose that when you tripped, your arm stretched towards the bushes, so you think it’s more likely your ring is there than on the sidewalk.  Still, you’re likely to search the sidewalk first, because it’s easy.  That is, the probability of finding the ring given that it’s on the sidewalk is much higher than the probability of finding it if it’s in the bushes, even if it’s more likely to be in the bushes than on the sidewalk.  You’re considering not only where your target is likely to be, but also  how likely it is to find the target in each location.

Let’s look at how this intuition might have been used to find Osama bin Laden.

First, let’s formulate scenarios about bin Laden’s status.  Suppose that experts’ opinions indicate that, with the probabilities shown, he’s either

  • Able, and actively running Al-Qaeda: 20%
  • Able, but in hiding, and passively involved with Al-Qaeda: 30%
  • Receiving dialysis treatment in a hospital: 30%
  • Alive, but doing something else: 10%
  • Dead: 10%

To decide where to search, we want to determine where he’s likely to be in each of these scenarios.  We’ll define a discrete search space by saying that we expect bin Laden to be in each of these places with the probabilities shown:
* Karachi: 10% * Islamabad: 10% * Lahore: 10% * Elsewhere in Pakistan: 50% * Outside of Pakistan: 20%

Next we want to define conditional probabilities that he is in each of these locations given each of the above scenarios. For example, If he’s dead, finding him in, say, Islamabad, will be near impossible. In other words,

because his body may have already been buried or destroyed.  Consider what actually turned out to be the case — he was (effectively) in Islamabad, and was able, but in hiding.  Bayes’ theorem tells us that

Where L is a “Location”, and S is a “Scenario.”  The probability of finding bin Laden in Islamabad, given that he’s able but in hiding, might then be:

If we compute this probability for each location for each scenario, we have a set of probabilities that we can use to define a search path that starts at the point of highest probability and moves to lower probability areas.  If we had three locations, and three “likelihood classes” of finding bin Laden in each of them, we’d have a histogram like this one:

3D bar chart

This shows us probabilities in discrete space. One axis is "Locations," the other is "Likelihood of finding".

Information we gather during the search might be used to revise probabilities during the search.  For instance, we might receive new intel while searching Lahore that decreases the probability that bin Laden is dead, which forces us to recompute all conditional probabilities in which we depended on P(dead).