# Machines that learn better

##### May 18, 2010 by Larry Hardesty

(PhysOrg.com) -- In the last 20 years or so, many of the key advances in artificial-intelligence research have come courtesy of machine learning, in which computers learn how to make predictions by looking for patterns in large collections of training data. A new approach called probabilistic programming makes it much easier to build machine-learning systems, but it’s useful for a relatively narrow set of problems. Now, MIT researchers have discovered how to extend the approach to a much larger class of problems, with implications for subjects as diverse as cognitive science, financial analysis and epidemiology.

Historically, building a machine-learning system capable of learning a new task would take a graduate student somewhere between a few weeks and several months, says Daniel Roy, a PhD student in the Department of Electrical Engineering and who along with Cameron Freer, an instructor in pure mathematics, led the new research. A handful of new, experimental, probabilistic programming languages — one of which, Church, was developed at MIT — promise to cut that time down to a matter of hours.

At the heart of each of these new languages is a so-called inference algorithm, which instructs a machine-learning system how to draw conclusions from the data it’s presented. The generality of the inference algorithm is what confers the languages’ power: The same algorithm has to be able to guide a system that’s learning how to recognize objects in digital images, or filter spam, or recommend DVDs based on past rentals, or whatever else an artificial-intelligence program may be called upon to do.

The inference algorithms currently used in probabilistic programming are great at handling discrete data but struggle with continuous data. For an idea of what that distinction means, consider three people of different heights. Their rank ordering, from tallest to shortest, is discrete: Each of them must be first, second, or third on the list. But their absolute heights are continuous. If the tallest person is 5 feet 10 inches tall, and the shortest is 5 feet 8 inches, you can’t conclude that the third person is 5 feet 9 inches: He or she could be 5 feet 8.5 inches, or 5 feet 9.6302 inches or an infinite number of other possibilities.

Designers of probabilistic programming languages are thus avidly interested in whether it’s possible to design a general-purpose inference algorithm that can handle continuous data. Unfortunately, the answer appears to be no: In a yet-unpublished paper, Freer, Roy, and Nate Ackerman of the University of California, Berkeley, mathematically demonstrate that there are certain types of statistical problems involving continuous data that no general-purpose algorithm could solve.

But there’s good news as well: Last week, at the International Conference on Artificial Intelligence and Statistics, Roy presented a paper in which he and Freer not only demonstrate that there are large classes of problems involving continuous data that are susceptible to a general solution but also describe an inference algorithm that can handle them. A probabilistic that implemented the algorithm would enable the rapid development of a much larger variety of machine-learning systems. It would, for instance, enable systems to better employ an analytic tool called the Pólya tree, which has been used to model stock prices, disease outbreaks, medical diagnoses, census data, and weather systems, among other things.

“The field of probabilistic programming is fairly new, and people have started coming up with probabilistic programs, but Dan and Cameron are really filling the theoretical gaps,” says Zoubin Ghahramani, professor of information engineering at the University of Cambridge. The hope, Ghahramani says, “is that their theoretical underpinnings will make the effort to come up with probabilistic programming languages much more solidly grounded.”

Chung-chieh Shan, a computer scientist at Rutgers who specializes in models of linguistic behavior, says that the MIT researchers’ work could be especially useful for artificial-intelligence systems whose future behavior is dependent on their past behavior. For instance, a system designed to understand spoken language might have to determine words’ parts of speech. If, in some context, it notices that a word tends to be used in an uncommon way — for instance, “man” is frequently used as a verb instead of a noun — then, going forward, it should have greater confidence in assigning that word its unusual interpretation.

Often, Shan explains, treating problems as having such “serial dependency” makes them easier to describe. But it also makes their solutions harder to calculate, because it requires keeping track of an ever-growing catalogue of past behaviors and revising future behaviors accordingly. Freer and Roy’s algorithm, he says, provides a way to convert problems that have serial dependency into problems that don’t, which makes them easier to solve. “A lot of models would call for this kind of picture,” Shan says. Roy and Freer’s work “is narrowing this gap between the intuitive description and the efficient implementation.”

While Freer and Roy’s algorithm is guaranteed to provide an answer to a range of previously intractable problems, Shan says, “there’s a difference between coming up with the right algorithm and implementing it so that it runs fast enough on an actual computer.” Roy and Freer agree, however, which is why they haven’t yet incorporated their algorithm into Church. “It’s fairly clear that within the set of models that our algorithm can handle, there are some that could be arbitrarily slow,” Roy says. “So now we have to study additional structure. We know that it’s possible. But when is it efficient?”

Explore further: Researcher finds hidden efficiencies in computer architecture

## Related Stories

#### A Grand Unified Theory of Artificial Intelligence

Mar 30, 2010

In the 1950s and '60s, artificial-intelligence researchers saw themselves as trying to uncover the rules of thought. But those rules turned out to be way more complicated than anyone had imagined. Since then, ...

#### Solving big problems with new quantum algorithm

Nov 09, 2009

(PhysOrg.com) -- In a recently published paper, Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves large problems much faster ...

#### A new way to help computers recognize patterns

Jan 25, 2006

Researchers at Ohio State University have found a way to boost the development of pattern recognition software by taking a different approach from that used by most experts in the field. This work may impact research in areas ...

#### Seeing things: Researchers teach computers to recognize objects

Oct 13, 2009

(PhysOrg.com) -- If computers could recognize objects, they could automatically search through hours of video footage for a particular two-minute scene. A tourist strolling down a street in a strange city ...

#### P vs. NP -- The most notorious problem in theoretical computer science remains open

Oct 29, 2009

In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wander ...

#### Yale Professor wins Godel Prize for showing how computer algorithms solve problems

Aug 13, 2008

Daniel A. Spielman, professor of applied mathematics and computer science at Yale, has been awarded the prestigious Gödel Prize for developing a technique, known as Smoothed Analysis, that helps predict the ...

## Recommended for you

#### UT Dallas professor to develop framework to protect computers' cores

9 hours ago

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

12 hours ago

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

15 hours ago

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

#### Researcher seeks to lessen failures in computerized visual recognition programs

Apr 17, 2014

Computer programs that use facial or image recognition systems—be it security cameras or applications that search databases for everything from photographs of wanted criminals to images of bears – are like any other technological ...

##### droid001
1 / 5 (1) May 18, 2010
"algorithm ...recommend DVDs based on past rentals"
This algorithm never recommend something completely different, but interesting.
Because he does not understand the purpose and meaning of "interesting".
##### JayK
1 / 5 (1) May 18, 2010
@droid001: Do you have the faintest clue what you're talking about?
##### JayK
3 / 5 (2) May 18, 2010
Rarely is the questions asked, is our machines learning?
##### droid001
3 / 5 (2) May 18, 2010
"...is a so-called inference algorithm, which instructs a machine-learning system how to draw conclusions from the data it’s presented"
I do not see any machine-learning system here, only probabilistic analysis of data.
##### JayK
1 / 5 (1) May 18, 2010
I do not see any machine-learning system here, only probabilistic analysis of data.

You didn't read the article, did you?
"But it also makes their solutions harder to calculate, because it requires keeping track of an ever-growing catalogue of past behaviors and revising future behaviors accordingly. Freer and Roy’s algorithm, he says, provides a way to convert problems that have serial dependency into problems that don’t, which makes them easier to solve."
If you really don't understand what the journalist is trying to explain, then just admit it and move on.

## More news stories

#### Five features an Amazon phone might offer (Update)

A report this week in The Wall Street Journal that Amazon is planning to release a smartphone has prompted industry analysts and technology blogs to muse about what the device might offer.

#### All-in-One Media Keyboard offers navigation from the couch

(Phys.org) —Microsoft this week announced its All-in-One Media Keyboard. This is a peripheral that is targeted for users who want a comfortable, useful keyboard to use whether sitting on the living room ...

#### Going nuts? Turkey looks to pistachios to heat new eco-city

Pistachios are already a key ingredient in Turkish baklava, but the country may now have found a new way to exploit the nuts known as "green gold"—by using their shells to heat a new eco-city.

#### LinkedIn membership hits 300 million

The career-focused social network LinkedIn announced Friday it has 300 million members, with more than half the total outside the United States.

#### Android gains in US, basic phones almost extinct

The Google Android platform grabbed the majority of mobile phones in the US market in early 2014, as consumers all but abandoned non-smartphone handsets, a survey showed Friday.

#### New, more versatile version of Geckskin: Gecko-like adhesives now useful for real world surfaces

(Phys.org) —The ability to stick objects to a wide range of surfaces such as drywall, wood, metal and glass with a single adhesive has been the elusive goal of many research teams across the world, but ...

#### Impact glass stores biodata for millions of years

(Phys.org) —Bits of plant life encapsulated in molten glass by asteroid and comet impacts millions of years ago give geologists information about climate and life forms on the ancient Earth. Scientists ...

#### Astronomers discover first self-lensing binary star system

(Phys.org) —A pair of astronomers at the University of Washington has discovered the first known instance of a self-lensing binary-star system. In their paper published in the journal Science, Ethan Kruse ...

#### 'Dressed' laser aimed at clouds may be key to inducing rain, lightning

The adage "Everyone complains about the weather but nobody does anything about it," may one day be obsolete if researchers at the University of Central Florida's College of Optics & Photonics and the University ...

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...