Subscribe to our free daily newsletters
. 24/7 Space News .




Subscribe to our free daily newsletters



TECH SPACE
Method enables machine learning from unwieldy data sets
by Staff Writers
Boston MA (SPX) Dec 20, 2016


Researchers from MIT's Computer Science and Artificial Intelligence Laboratory and its Laboratory for Information and Decision Systems have designed a new algorithm that makes it much more practical to select diverse subsets from a much larger dataset. Image courtesy Christine Daniloff and MIT.

When data sets get too big, sometimes the only way to do anything useful with them is to extract much smaller subsets and analyze those instead.

Those subsets have to preserve certain properties of the full sets, however, and one property that's useful in a wide range of applications is diversity. If, for instance, you're using your data to train a machine-learning system, you want to make sure that the subset you select represents the full range of cases that the system will have to confront.

Last week at the Conference on Neural Information Processing Systems, researchers from MIT's Computer Science and Artificial Intelligence Laboratory and its Laboratory for Information and Decision Systems presented a new algorithm that makes the selection of diverse subsets much more practical.

Whereas the running times of earlier subset-selection algorithms depended on the number of data points in the complete data set, the running time of the new algorithm depends on the number of data points in the subset. That means that if the goal is to winnow a data set with 1 million points down to one with 1,000, the new algorithm is 1 billion times faster than its predecessors.

"We want to pick sets that are diverse," says Stefanie Jegelka, the X-Window Consortium Career Development Assistant Professor in MIT's Department of Electrical Engineering and Computer Science and senior author on the new paper.

"Why is this useful? One example is recommendation. If you recommend books or movies to someone, you maybe want to have a diverse set of items, rather than 10 little variations on the same thing. Or if you search for, say, the word 'Washington.'

"There's many different meanings that this word can have, and you maybe want to show a few different ones. Or if you have a large data set and you want to explore - say, a large collection of images or health records - and you want a brief synopsis of your data, you want something that is diverse, that captures all the directions of variation of the data.

"The other application where we actually use this thing is in large-scale learning. You have a large data set again, and you want to pick a small part of it from which you can learn very well."

Joining Jegelka on the paper are first author Chengtao Li, a graduate student in electrical engineering and computer science; and Suvrit Sra, a principal research scientist at MIT's Laboratory for Information and Decision Systems.

Thinking small
Traditionally, if you want to extract a diverse subset from a large data set, the first step is to create a similarity matrix - a huge table that maps every point in the data set against every other point. The intersection of the row representing one data item and the column representing another contains the points' similarity score on some standard measure.

There are several standard methods to extract diverse subsets, but they all involve operations performed on the matrix as a whole. With a data set with a million data points - and a million-by-million similarity matrix - this is prohibitively time consuming.

The MIT researchers' algorithm begins, instead, with a small subset of the data, chosen at random. Then it picks one point inside the subset and one point outside it and randomly selects one of three simple operations: swapping the points, adding the point outside the subset to the subset, or deleting the point inside the subset.

The probability with which the algorithm selects one of those operations depends on both the size of the full data set and the size of the subset, so it changes slightly with every addition or deletion. But the algorithm doesn't necessarily perform the operation it selects.

Again, the decision to perform the operation or not is probabilistic, but here the probability depends on the improvement in diversity that the operation affords. For additions and deletions, the decision also depends on the size of the subset relative to that of the original data set. That is, as the subset grows, it becomes harder to add new points unless they improve diversity dramatically.

This process repeats until the diversity of the subset reflects that of the full set. Since the diversity of the full set is never calculated, however, the question is how many repetitions are enough. The researchers' chief results are a way to answer that question and a proof that the answer will be reasonable.

Research paper: Fast mixing Markov chains for strongly Rayleigh measures, DPPs, and constrained sampling


Comment on this article using your Disqus, Facebook, Google or Twitter login.


Thanks for being here;
We need your help. The SpaceDaily news network continues to grow but revenues have never been harder to maintain.

With the rise of Ad Blockers, and Facebook - our traditional revenue sources via quality network advertising continues to decline. And unlike so many other news sites, we don't have a paywall - with those annoying usernames and passwords.

Our news coverage takes time and effort to publish 365 days a year.

If you find our news sites informative and useful then please consider becoming a regular supporter or for now make a one off contribution.

SpaceDaily Contributor
$5 Billed Once


credit card or paypal
SpaceDaily Monthly Supporter
$5 Billed Monthly


paypal only

.


Related Links
Massachusetts Institute of Technology
Space Technology News - Applications and Research






Share this article via these popular social media networks
del.icio.usdel.icio.us DiggDigg RedditReddit GoogleGoogle

Previous Report
TECH SPACE
New technology of ultrahigh density optical storage researched at Kazan University
Kazan, Russia (SPX) Dec 02, 2016
According to current estimates, dozens of zettabytes of information will need to be placed somewhere by 2020. New physical principles must be found, the ones that facilitate the use of single atoms or molecules as basic memory cells. This can be done with the help of lasers. However, the existing methods of optical storage are limited to the diffraction limit (~500 nm), so the respective recordi ... read more


TECH SPACE
Spacewalk for Thomas Pesquet at ISS

NASA's Exo-Brake 'Parachute' to Enable Safe Return for Small Spacecraft

Trump sits down with tech execs, including critics

Trump sits down with tech execs, including critics

TECH SPACE
United Launch Alliance launches EchoStar XIX satellite

NASA Engineers Test Combustion Chamber to Advance 3-D Printed Rocket Engine Design

Ultra-Cold Storage - Liquid Hydrogen may be Fuel of the Future

Technical glitch postpones NASA satellite launch

TECH SPACE
All eyes on Trump over Mars

Opportunity performs several drives to ancient gully

Full go-ahead for building ExoMars 2020

Skimming an alien atmosphere

TECH SPACE
Chinese missile giant seeks 20% of a satellite market

China-made satellites in high demand

Space exploration plans unveiled

China launches 4th data relay satellite

TECH SPACE
OneWeb announces key funding form SoftBank Group and other investors

Space as a Driver for Socio-Economic Sustainable Development

SoftBank delivers first $1 bn of Trump pledge, to space firm

Telecom satellite system to encircle globe

TECH SPACE
Uncovering the secrets of water and ice as materials

The hidden side of sulfur

Chemical trickery corrals 'hyperactive' metal-oxide cluster

High Resolution Imaging of Hypervelocity Impacts

TECH SPACE
Astronomers discover dark past of planet-eating 'Death Star'

Microlensing Study Suggests Most Common Outer Planets Likely Neptune-mass

Are planets like those in 'Star Wars

Exciting new creatures discovered on ocean floor

TECH SPACE
Juno Captures Jupiter 'Pearl'

Juno Mission Prepares for December 11 Jupiter Flyby

Research Offers Clues About the Timing of Jupiter's Formation

New Perspective on How Pluto's "Icy Heart" Came to Be




Memory Foam Mattress Review
Newsletters :: SpaceDaily :: SpaceWar :: TerraDaily :: Energy Daily
XML Feeds :: Space News :: Earth News :: War News :: Solar Energy News






The content herein, unless otherwise known to be public domain, are Copyright 1995-2017 - Space Media Network. All websites are published in Australia and are solely subject to Australian law and governed by Fair Use principals for news reporting and research purposes. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA news reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. All articles labeled "by Staff Writers" include reports supplied to Space Media Network by industry news wires, PR agencies, corporate press officers and the like. Such articles are individually curated and edited by Space Media Network staff on the basis of the report's information value to our industry and professional readership. Advertising does not imply endorsement, agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. Privacy Statement