Bayesian search: A simple rule to find stuff you’ve lost
- Everyone has misplaced something from time to time, be it a phone, wallet, or set of keys.
- When something extraordinarily valuable, like a nuclear submarine, is lost, a mathematical search technique is often used to find it.
- The tenets of the technique are simple enough to understand and deploy in our everyday lives.
When you lose your phone, wallet, or keys, you may resort to a few tricks to relocate them. Maybe you’ll retrace your steps. Maybe you’ll look in each of the locations that you typically put them. Or perhaps you’ll try to remember every unusual place you’ve been lately. Each of these choices makes logical sense.
When an entity with vast resources loses something extraordinarily valuable, like a nuclear submarine, they call in the big guns of Bayesian search theory to help. Fortunately for the rest of us, the basic concepts are simple enough to distill for finding those everyday items. Even if your missing item is worth merely hundreds of dollars, this mathematical process can streamline the logic of your search, saving you time and money.
Dude, where’s my car?
The probability that a lost item is found in one place versus another is an intuitive concept that can be turned into a mathematical object. A simple map, divided into a grid, with each section assigned a probability of containing an item, is a form of probability density function. Let’s say that you left your car in a parking lot with 100 spots, and now you have forgotten where you parked. The most basic parking lot probability density function shows one box for each space, each with a probability of 1/100 (or 0.01).
Let’s further assume that you’re not disabled, and there are ten spaces for disabled people. Now the probability density function looks more like 0.011 in 90 of the spaces and 0.001 in each disabled space. (We are further assuming a 10% chance that you made a mistake parking.)
Let’s bring in some more data. The ten parking spots furthest from the store are empty. The chances of your car being there are zero. Now your density function looks like 80 squares with a probability of ~0.0125. If you tend to drive around and around the lot to find the space closest to the door, then the spaces nearer the store have somewhat higher probability, and the spots further out have somewhat lower probability.
The point is that each time you acquire more information, the probability density function changes. So, in this way, you can narrow down and speed up your search, beginning with the spots with the highest probability of containing your car, and working your way down the probability list, checking the lowest probability spots as a last resort.
Did the dog eat my homework?
The first map is good, but a second map is even better. This second map contains, for each search area, the chance that you would actually find the item if it were in that spot.
To demonstrate, let’s construct a slightly different metaphor. If your homework has disappeared, it would be easier or harder to find in various places you might look. If the homework is on an empty desk, you’re sure to see it there. If you left it on a cluttered desk, covered with piles of paper, your chances are lower. If it could have blown out the window, the chance it might still be in the yard is much smaller because of the wind. If the dog ate it, your probability of finding it goes to zero.
Now, take these two probability distribution maps and multiply them together. Any search area that is both likely to contain the item and has a high likelihood of you finding it if it’s there will be represented by a relatively large number. These are good places to begin your search. Areas where either the item is easy to spot but unlikely to be, or likely to be but hard to spot, have a smaller number. These are a lower search priority. Areas where it isn’t likely to be and you can’t easily spot it — the dog comes to mind — are relegated to the very last resort.
Finding a fugitive
As you search the areas with the greatest combined likelihood, you should re-evaluate your assumptions and update your probability map as you go along.
Let’s introduce a third metaphor. Now you’re searching for an escaped convict. Your pack of tracking hounds can smell where he has been recently. Near the prison is a road leading to a bus stop. The probability that he would run up the road to catch a bus is relatively high, and your chances of spotting him if he is near the open road (as opposed to, say, the woods) are high as well. The glass-walled stop where buses only appear sporadically has a similarly high combined probability.
If you are searching the road and the hounds pick up no scent, then the probability that he is at some location further up the road is greatly diminished. The bus stop is now a lower probability location, too. On the other hand, if the dogs do smell something, the bus stop probability has increased.
If this all sounds relatively straightforward, that’s because it is. The trick to the method is to use intelligent reasoning in your probability distributions, including how you modify them as you go. The probability density function of where the object might be located particularly requires serious thought. The best way to form such a function is not to guess, or presume random chance, but to develop a series of hypotheses about why it disappeared and map out where it is most likely to be as a result. Across the search area, assign a probability to each square for each hypothesis, and then multiply those probabilities together.
Bayesian search is common sense + math
In the case of a missing ship, several probability fields could be constructed by starting with a hypothesis and following its probable conclusions. The first hypothesis might be that the most probable location is centered near where the last radio contact was made, and the probability decreases the further you get from that location. Another hypothesis might be that if a hurricane passed through the area, the path of the eyewall of the storm is the most likely place for the ship to have sunk. If a piece of debris is found floating in one area, then the probability the shipwreck lies nearby goes up, and the probability it is far away goes down. If there is a strong current flowing through the area with the debris, then the upstream path of that current acquires a higher probability, extending back as far as it has flowed since the ship was lost. The areas downstream drop in probability.
Bayesian search is a distillation of smart common sense, formalized and made more rigorous with relatively simple mathematical concepts. If you’re looking for a billion-dollar lost treasure, you might sit down at a computer to map out many probability distributions and mathematically combine them. If you’re on an hour-long search for your wallet, a quick and dirty mental implementation of the Bayesian search method can save you time and increase your chances of success.
