Many problems in science and engineering can be formulated as determining the values of a set of unknown variables, given a noisy set of observations and uncertain knowledge about how all the variables and observations are related. For example, how would you determine a transmitted message, based on a noisy received signal? How would you determine the pattern of blood flow in a patient's heart, based on a corrupted MRI image? How would you identify a small number of face images that summarize a diverse set of face images? How would you identify a small number of sentences that accurately reflect the content of a document? How would you learn a codebook useful for quantizing speech signals? How would you identify a small number of cities that are most easily accessible from all other cities by commercial airline? How would you identify segments of DNA that reflect the expression properties of genes? In this tutorial, I will review message-passing algorithms that have recently gained a lot of interest in the engineering, computer science and computational biology communities. These algorithms work by exchanging messages between variables and observations -- these messages try to pin down probable solutions while taking into account uncertainties. As an example, I will describe how this approach can be used to derive an algorithm that my colleagues and I recently introduced, called `affinity propagation'. This algorithm solves the problem of summarizing a set of observations by a subset of exemplars, which can then be used for decision-making or coding. I'll discuss aspects of message-passing and affinity propagation in particular that could impact efficient implementation in multi-core architectures, FPGA hardware and VLSI hardware.

Sponsored by IEEE Canada and the Sections of Central Canada
by the