Humans learn to very quickly identify complex objects and variations of them. We generally recognize an “A” no matter what the font, texture or background, for example, or the face of a coworker even if she puts on a hat or changes her hairstyle. We also can identify an object when just a portion is visible, such as the corner of a bed or the hinge of a door. But how? Are there simple techniques that humans use across diverse tasks? And can such techniques be computationally replicated to improve computer vision, machine learning or robotic performance?
Researchers at Georgia Tech discovered that humans can categorize data using less than 1 percent of the original information, and validated an algorithm to explain human learning -- a method that also can be used for machine learning, data analysis and computer vision.
“How do we make sense of so much data around us, of so many different types, so quickly and robustly?” said Santosh Vempala, Distinguished Professor of Computer Science at the Georgia Institute of Technology and one of four researchers on the project. “At a fundamental level, how do humans begin to do that? It’s a computational problem.”
Researchers Rosa Arriaga, Maya Cakmak, David Rutter, and Vempala at Georgia Tech’s College of Computing studied human performance in “random projection” tests to understand how well humans learn an object. They presented test subjects with original, abstract images and then asked whether they could correctly identify that same image when randomly shown just a small portion of it.
“We hypothesized that random projection could be one way humans learn,” Arriaga explains, a senior research scientist and developmental psychologist. “The short story is, the prediction was right. Just 0.15 percent of the total data is enough for humans.”
Next, researchers tested a computational algorithm to allow machines (very simple neural networks) to complete the same tests. Machines performed as well as humans, which provides a new understanding of how humans learn. “We found evidence that, in fact, the human and the neural network behave very similarly,” Arriaga said.
The researchers wanted to come up with a mathematical definition of what typical and atypical stimuli look like and, from that, predict which data would hardest for the human and the machine to learn. Humans and machines performed equally, demonstrating that indeed one can predict which data will be hardest to learn over time.
Results were recently published in the journal Neural Computation (MIT press). It is believed to be the first study of “random projection,” the core component of the researchers’ theory, with human subjects.
To test their theory, researchers created three families of abstract images — some originally as large as 500 x 500 pixels — and extracted very small, random samples from them, ranging in size from 6 to 20 pixels square. Humans and simple neural networks were shown the whole image for 10 seconds, then randomly shown 16 smaller sketches and asked to identify the original image. Using abstract images ensured that neither humans nor machines had any prior knowledge of what the objects were.
“We were surprised by how close the performance was between extremely simple neural networks and humans,” Vempala said. “The design of neural networks was inspired by how we think humans learn, but it’s a weak inspiration. To find that it matches human performance is quite a surprise.”
“This fascinating paper introduces a localized random projection that compresses images while still making it possible for humans and machines to distinguish broad categories,” said Sanjoy Dasgupta, professor of computer science and engineering at the University of California San Diego and an expert on machine learning and random projection. “It is a creative combination of insights from geometry, neural computation, and machine learning.”
Although researchers cannot definitively claim that the human brain actually engages in random projection, the results support the notion that random projection is a plausible explanation, the authors conclude. In addition, it suggests a very useful technique for machine learning: large data is a formidable challenge today, and random projection is one way to make data manageable without losing essential content, at least for basic tasks such as categorization and decision making.
The algorithmic theory of learning based on random projection already has been cited more than 300 times and has become a commonly used technique in machine learning to handle large data of diverse types.
The complete research paper, “Visual Categorization with Random Projection,” can be found here and in the October edition of Neural Computation.
This work is partially funded by the National Science Foundation (CCF-0915903 and CCF-1217793). Any conclusions expressed are those of the principal investigator and may not necessarily represent the official views of the funding organizations.