# Finding patterns in corrupted data

October 26, 2016CAMBRIDGE, Mass -- Data analysis -- and particularly big-data analysis -- is often a matter of fitting data to some sort of mathematical model. The most familiar example of this might be linear regression, which finds a line that approximates a distribution of data points. But fitting data to probability distributions, such as the familiar bell curve, is just as common.

If, however, a data set has just a few corrupted entries -- say, outlandishly improbable measurements -- standard data-fitting techniques can break down. This problem becomes much more acute with high-dimensional data, or data with many variables, which is ubiquitous in the digital age.

Since the early 1960s, it's been known that there are algorithms for weeding corruptions out of high-dimensional data, but none of the algorithms proposed in the past 50 years are practical when the variable count gets above, say, 12.

That's about to change. Earlier this month, at the IEEE Symposium on Foundations of Computer Science, a team of researchers from MIT's Computer Science and Artificial Intelligence Laboratory, the University of Southern California, and the University of California at San Diego presented a new set of algorithms that can efficiently fit probability distributions to high-dimensional data.

Remarkably, at the same conference, researchers from Georgia Tech presented a very similar algorithm.

The pioneering work on "robust statistics," or statistical methods that can tolerate corrupted data, was done by statisticians, but both new papers come from groups of computer scientists. That probably reflects a shift of attention within the field, toward the computational efficiency of model-fitting techniques.

"From the vantage point of theoretical computer science, it's much more apparent how rare it is for a problem to be efficiently solvable," says Ankur Moitra, the Rockwell International Career Development Assistant Professor of Mathematics at MIT and one of the leaders of the MIT-USC-UCSD project. "If you start off with some hypothetical thing -- 'Man, I wish I could do this. If I could, it would be robust' -- you're going to have a bad time, because it will be inefficient. You should start off with the things that you know that you can efficiently do, and figure out how to piece them together to get robustness."

**Resisting corruption**

To understand the principle behind robust statistics, Moitra explains, consider the normal distribution -- the bell curve, or in mathematical parlance, the one-dimensional Gaussian distribution. The one-dimensional Gaussian is completely described by two parameters: the mean, or average, value of the data, and the variance, which is a measure of how quickly the data spreads out around the mean.

If the data in a data set -- say, people's heights in a given population -- is well-described by a Gaussian distribution, then the mean is just the arithmetic average. But suppose you have a data set consisting of height measurements of 100 women, and while most of them cluster around 64 inches -- some a little higher, some a little lower -- one of them, for some reason, is 1,000 inches. Taking the arithmetic average will peg a woman's mean height at 6 feet 4 inches, not 5 feet 4 inches.

One way to avoid such a nonsensical result is to estimate the mean, not by taking the numerical average of the data, but by finding its median value. This would involve listing all the 100 measurements in order, from smallest to highest, and taking the 50th or 51st. An algorithm that uses the median to estimate the mean is thus more robust, meaning it's less responsive to corrupted data, than one that uses the average.

The median is just an approximation of the mean, however, and the accuracy of the approximation decreases rapidly with more variables. Big-data analysis might require examining thousands or even millions of variables; in such cases, approximating the mean with the median would often yield unusable results.

**Identifying outliers**

One way to weed corrupted data out of a high-dimensional data set is to take 2-D cross sections of the graph of the data and see whether they look like Gaussian distributions. If they don't, you may have located a cluster of spurious data points, such as that 80-foot-tall woman, which can simply be excised.

The problem is that, with all previously known algorithms that adopted this approach, the number of cross sections required to find corrupted data was an exponential function of the number of dimensions. By contrast, Moitra and his coauthors -- Gautam Kamath and Jerry Li, both MIT graduate students in electrical engineering and computer science; Ilias Diakonikolas and Alistair Stewart of USC; and Daniel Kane of USCD -- found an algorithm whose running time increases with the number of data dimensions at a much more reasonable rate (or, polynomially, in computer science jargon).

Their algorithm relies on two insights. The first is what metric to use when measuring how far away a data set is from a range of distributions with approximately the same shape. That allows them to tell when they've winnowed out enough corrupted data to permit a good fit.

The other is how to identify the regions of data in which to begin taking cross sections. For that, the researchers rely on something called the kurtosis of a distribution, which measures the size of its tails, or the rate at which the concentration of data decreases far from the mean. Again, there are multiple ways to infer kurtosis from data samples, and selecting the right one is central to the algorithm's efficiency.

The researchers' approach works with Gaussian distributions, certain combinations of Gaussian distributions, another common distribution called the product distribution, and certain combinations of product distributions. Although they believe that their approach can be extended to other types of distributions, in ongoing work, their chief focus is on applying their techniques to real-world data.

-end-

**ADDITIONAL BACKGROUND**

ARCHIVE: Dueling algorithms

Massachusetts Institute of Technology

**Related Algorithm Articles:**

New algorithm to help process biological images

Skoltech researchers have presented a new biological image processing method that accurately picks out specific biological objects in complex images.

Skoltech researchers have presented a new biological image processing method that accurately picks out specific biological objects in complex images.

Skoltech scientists break Google's quantum algorithm

In the near term, Google has devised new quantum enhanced algorithms that operate in the presence of realistic noise.

In the near term, Google has devised new quantum enhanced algorithms that operate in the presence of realistic noise.

The most human algorithm

A team from the research group SEES:lab of the Department of Chemical Engineering of the Universitat Rovira I Virgili and ICREA has made a breakthrough with the development of a new algorithm that makes more accurate predictions and generates mathematical models that also make it possible to understand these predictions.

A team from the research group SEES:lab of the Department of Chemical Engineering of the Universitat Rovira I Virgili and ICREA has made a breakthrough with the development of a new algorithm that makes more accurate predictions and generates mathematical models that also make it possible to understand these predictions.

Algorithm turns cancer gene discovery on its head

Prediction method could help personalize cancer treatments and reveal new drug targets.

Prediction method could help personalize cancer treatments and reveal new drug targets.

New algorithm predicts gestational diabetes

Timely prediction may help prevent the condition using nutritional and lifestyle changes.

Timely prediction may help prevent the condition using nutritional and lifestyle changes.

New algorithm could mean more efficient, accurate equipment for Army

Researchers working on an Army-funded project have developed an algorithm to simulate how electromagnetic waves interact with materials in devices to create equipment more efficiently and accurately.

Researchers working on an Army-funded project have developed an algorithm to simulate how electromagnetic waves interact with materials in devices to create equipment more efficiently and accurately.

Universal algorithm set to boost microscopes

EPFL scientists have developed an algorithm that can determine whether a super-resolution microscope is operating at maximum resolution based on a single image.

EPFL scientists have developed an algorithm that can determine whether a super-resolution microscope is operating at maximum resolution based on a single image.

Algorithm designed to map universe, solve mysteries

Cornell University researchers have developed an algorithm designed to visualize models of the universe in order to solve some of physics' greatest mysteries.

Cornell University researchers have developed an algorithm designed to visualize models of the universe in order to solve some of physics' greatest mysteries.

Algorithm tells robots where nearby humans are headed

A new tool for predicting a person's movement trajectory may help humans and robots work together in close proximity.

A new tool for predicting a person's movement trajectory may help humans and robots work together in close proximity.

Algorithm to transform investment banking with higher returns

A University of Bath researcher has created an algorithm which aims to remove the elements of chance, bias or emotion from investment banking decisions, a development which has the potential to reduce errors in financial decision making and improve financial returns in global markets.

A University of Bath researcher has created an algorithm which aims to remove the elements of chance, bias or emotion from investment banking decisions, a development which has the potential to reduce errors in financial decision making and improve financial returns in global markets.

## Trending Science News

**Current Coronavirus (COVID-19) News**

## Top Science Podcasts

We have hand picked the**top science podcasts of 2020**.

**Now Playing: TED Radio Hour**

**Climate Mindset**

In the past few months, human beings have come together to fight a global threat. This hour, TED speakers explore how our response can be the catalyst to fight another global crisis: climate change. Guests include political strategist Tom Rivett-Carnac, diplomat Christiana Figueres, climate justice activist Xiye Bastida, and writer, illustrator, and artist Oliver Jeffers.

**Now Playing: Science for the People**

**#562 Superbug to Bedside**

By now we're all good and scared about antibiotic resistance, one of the many things coming to get us all. But there's good news, sort of. News antibiotics are coming out! How do they get tested? What does that kind of a trial look like and how does it happen? Host Bethany Brookeshire talks with Matt McCarthy, author of "Superbugs: The Race to Stop an Epidemic", about the ins and outs of testing a new antibiotic in the hospital.

**Now Playing: Radiolab**

**Speedy Beet**

There are few musical moments more well-worn than the first four notes of Beethoven's Fifth Symphony. But in this short, we find out that Beethoven might have made a last-ditch effort to keep his music from ever feeling familiar, to keep pushing his listeners to a kind of psychological limit. Big thanks to our Brooklyn Philharmonic musicians: Deborah Buck and Suzy Perelman on violin, Arash Amini on cello, and Ah Ling Neu on viola. And check out The First Four Notes, Matthew Guerrieri's book on Beethoven's Fifth. Support Radiolab today at Radiolab.org/donate.