There are three steps to fruit fly’s search algorithm, which has been maximized for speed and low-power efficiency over millennia of neural evolution. In the first step, Navlakha explained, the smell is picked up by 50 odor-receptor neurons in the fly’s nose. Each neuron fires at a slightly different rate, so the odor is said to have 50 dimensions.
Then, instead of reducing those 50 dimensions down to five or 10 representative vectors, it explodes up to 2,000 dimensions. But the way that it expands is the brilliant part. Rather than simply multiplying each of the original 50 signals by 40, Navlakha said, the fly brain uses a technique called sparse, binary, random projection.
Here’s how it works. The 2,000 dimensions are encoded in 2,000 Kenyon cells, a type of neuron in the fly’s brain. Each of the Kenyon cells gets its firing rate by adding up the values of six randomly selected neurons from the original 50 odor receptors. Using this random sampling method, the fly can dive deeper into the odor data without overburdening its circuitry.
Navlakha uses the analogy of trying to identify family relationships within a group of 100 people.
“What computer scientists will do with those 100 people is stuff them into a crowded room. This is the low-dimensional space,” said Navlakha. “What the fly is doing is taking those 100 people and spreading them out on a football field. Then you can imagine that it would be very easy to delineate and find this group structure, as opposed to everyone being on top of each other in a room.”
RELATED: Some Butterflies Have Been Fooling Others for 2 Million Years
Once the odor data is spread out in the fly’s brain across 2,000 cells, a single neuron called APL does the sorting. It inhibits or shuts off all but the highest-firing Kenyon cells (the top five percent) and uses a “winner-take-all” method to tag the odor with a single descriptive hash.
The fly’s circuitry itself wasn’t a new discovery; the neurobiology was already relatively well understood. The new part was taking the fly’s three-step neural algorithm and translating it into computer code. Navlakha and his colleagues wanted to test the fly’s random expansion algorithm against more conventional similarity-search algorithms on large datasets.
The team ran the two algorithms against a standard database of 10,000 images with the goal of identifying a cluster of nearest matches. The results of each algorithm would be compared to the results of a slower, one-by-one, linear search that was sure to find the most similar images.
The fruit fly algorithm was the clear winner, effectively doubling the accuracy the conventional computer science method in both an image-similarity search and a text-based document search. The next step, Navlakha said, will be to analyze mammalian neural circuitry for further refinements and upgrades to nature’s evolutionary algorithm.
“It’s a really exciting time to study not only the brain, but all of biology. There are so many strategies of computation and flexibility and adaptation that we can learn,” said Navlakha. “This idea of using a random projection is such a fundamental principle in computer science. To see that evolution has figured out that it’s a good way to solve this problem... it keeps me up at night thinking about all this stuff.”
WATCH: What Makes Flies the Greatest Fliers?