Machine Learning Reimagines the Building Blocks of Computing

Algorithms — the chunks of code that allow programs to sort, filter and combine data, among other things — are the standard tools of modern computing. Like tiny gears inside a watch, algorithms execute well-defined tasks within more complicated programs.

They’re ubiquitous, and in part because of this, they’ve been painstakingly optimized over time. When a programmer needs to sort a list, for example, they’ll reach for a standard “sort” algorithm that’s been used for decades.

Now researchers are taking a fresh look at traditional algorithms, using the branch of artificial intelligence known as machine learning. Their approach, called algorithms with predictions, takes advantage of the insights machine learning tools can provide into the data that traditional algorithms handle. These tools have, in a real way, rejuvenated research into basic algorithms.

Machine learning and traditional algorithms are “two substantially different ways of computing, and algorithms with predictions is a way to bridge the two,” said Piotr Indyk, a computer scientist at the Massachusetts Institute of Technology. “It’s a way to combine these two quite different threads.”

The recent explosion of interest in this approach began in 2018 with a paper by Tim Kraska, a computer scientist at MIT, and a team of Google researchers. In it, the authors suggested that machine learning could improve a well-studied traditional algorithm called a Bloom filter, which solves a straightforward but daunting problem.

Imagine you run your company’s IT department and you need to check if your employees are going to websites that pose a security risk. Naively, you might think you’ll need to check every site they visit against a blacklist of known sites. If the list is huge (as is likely the case for undesirable sites on the internet), the problem becomes unwieldy — you can’t check every site against a huge list in the tiny amount of time before a webpage loads.

The Bloom filter provides a solution, allowing you to quickly and accurately check whether any particular site’s address, or URL, is on the blacklist. It does this by essentially compressing the huge list into a smaller list that offers some specific guarantees.

Bloom filters never produce false negatives — if they say the site is bad, it’s bad. However, they can produce false positives, so perhaps your employees won’t be able to visit some sites they should have access to. That’s because they trade some accuracy for an enormous amount of data compression — a trick called “lossy compression.” The more that Bloom filters compress the original data, the less accurate they are, but the more space they save.

To a simple Bloom filter, every website is equally suspicious until it’s confirmed to not be on the list. But not all websites are created equal: Some are more likely than others to wind up on a blacklist, simply because of details like their domain or the words in their URL. People understand this intuitively, which is why you likely read URLs to make sure they’re safe before you click on them.

Kraska’s team developed an algorithm that can also apply this kind of logic. They called it a “learned Bloom filter,” and it combines a small Bloom filter with a recurrent neural network (RNN) — a machine learning model that learns what malicious URLs look like after being exposed to hundreds of thousands of safe and unsafe websites.

When the learned Bloom filter checks a website, the RNN acts first and uses its training to determine if the site is on the blacklist. If the RNN says it’s on the list, the learned Bloom filter rejects it.