Communications of the ACM
Sizing Samples
MIT researchers have shown that graphs shaped like stars and chains establish, respectively, the worst- and best-case scenarios for computers doing pattern recognition.
Credit: Christine Daniloff / MIT
Numerous scientific fields employ computers to deduce patterns in data, and Massachusetts Institute of Technology researchers led by graduate student Vincent Tan have taken an initial step to determine how much data is enough to support reliable pattern inference by envisioning data sets as graphs.
In the researchers' work, the nodes of the graph represent data and the edges stand for correlations between them, and from this point of view a computer tasked with pattern recognition is provided a bunch of nodes and asked to construe the weights of the edges between them. The researchers have demonstrated that graphs configured like chains and stars establish, respectively, the best- and worst-case scenarios for computers charged with pattern recognition.
Tan says that for tree-structured graphs with shapes other than stars or chains, the "strength of the connectivity between the variables matters." Carnegie Mellon University professor John Lafferty notes that a tree-structured approximation of data is more computationally efficient.
From MIT News
View Full Article
Abstracts Copyright © 2010 Information Inc., Bethesda, Maryland, USA 
No entries found