March 5th, 2007
Affinity propagation for faster computing
Canadian computer scientists have developed a new algorithm named 'affinity propagation' which can considerably speed up IT systems. One of the researchers said that 'affinity propagation works by considering all possible interpretations of the data at once.' This new algorithm is based on pairing up pieces of data instead of putting them through a process of elimination. As an example, the system was used for handwriting recognition by looking at thousands of images of hand-written numbers taken from postal codes. It took only five minutes to find pictures that accurately accounted for the various styles of handwriting while the standard computing approach would take about five million years(!!!). This 'affinity propagation' could be used in a wide range of applications, such as medical imaging, drug discovery, genetics, telecommunications or airline or automobile traffic planning.
This algorithm has been developed at the University of Toronto by Brendan Frey, a professor in the department of Electrical and Computer Engineering and Delbert Dueck, a member of his research group about Probabilistic and Statistical Inference.
Before going further, below you can see how affinity propagation was used for air travel: "(B) Affinity propagation was applied to similarities derived from air-travel efficiency (measured by estimated travel time) between the 456 busiest commercial airports in Canada and the United States. (C) Seven exemplars identified by affinity propagation are color-coded, and the assignments of other cities to these exemplars is shown. Cities located quite near to exemplar cities may be members of other more distant exemplars due to the lack of direct flights between them (e.g., Atlantic City is 100 km from Philadelphia, but is closer in flight time to Atlanta). (D) The inset shows that the Canada-USA border roughly divides the Toronto and Philadelphia clusters, due to a larger availability of domestic flights compared to international flights. However, this is not the case on the west coast as shown in (E), because extraordinarily frequent airline service between Vancouver and Seattle connects Canadian cities in the northwest to Seattle." (Credit for images and caption: Brendan Frey and Delbert Dueck)
The University of Toronto news release gives other details about the use of affinity propagation.
To illustrate its potential, researchers showed the system thousands of images of hand-written numbers taken from postal codes. It took only five minutes to find a small collection of pictures that accurately account for the various styles of handwriting. The standard computing approach, which is currently used in many areas all around the world, would take about five million years to account for the writing styles as accurately.
How could they guess that such a computation would take five million years? I really would like to know.
Anyway, this research work has been published by Science under the name "Clustering by Passing Messages Between Data Points" (Volume 315, Number 5814, Pages 972-976, February 16, 2007). Here is an excerpt from the abstract.
We devised a method called "affinity propagation," which takes as input measures of similarity between pairs of data points. Real-valued messages are exchanged between data points until a high-quality set of exemplars and corresponding clusters gradually emerges. We used affinity propagation to cluster images of faces, detect genes in microarray data, identify representative sentences in this manuscript, and identify cities that are efficiently accessed by airline travel. Affinity propagation found clusters with much lower error than other methods, and it did so in less than one-hundredth the amount of time.
And here is a link to the full paper (PDF format, 23 pages, 1.27 MB) from which the above illustration has been extracted and which contains additional information to the technical paper.
Finally, if you need more information or try the algorithm yourself, here is a link to the Affinity Propagation Clustering home page.
Sources: University of Toronto news release, February 15, 2007; and various websites
You'll find related stories by following the links below.
