[Ml-stat-talks] Caetano talk, mon, 12/20, 2:30, CS room 402

Robert Schapire schapire at CS.Princeton.EDU
Wed Dec 15 20:58:45 EST 2010

Tiberio Caetano will give a talk this Monday, December 20, at 2:30pm in 
room 402 of the CS building.  See abstract below.

Let me know if you would like to meet with him, or join us for lunch.



Faster Algorithms for Max-Product Message-Passing

Tiberio Caetano
NICTA - Australian National University


Maximum A Posteriori inference in graphical models is often solved via 
message-passing algorithms, such as the junction-tree algorithm, loopy 
belief-propagation, or factor-graph inference.  All such algorithms rely 
on two components: a procedure to pass a single message and a protocol 
that determines the order in which different messages should be passed.  
This presentation describes a novel algorithm for solving the first 
problem: passing a single message.  The algorithm is exact, just as the 
standard algorithm used for this task, however it is substantially 
faster in practice when the state space of the random variables is 
large.  Although it has the same worst-case complexity, it has a much 
better expected-case complexity since it exploits the structure of the 
clique potentials in the graphical model.  Since the algorithm only 
affects the message-passing step, it can be used with any protocol.  The 
assumptions it requires are also very often met in practice.  We 
illustrate the practical advantages of the improved algorithm in a 
number of tasks, such as text and image denoising, optical flow 
inference, stereo disparity estimation, and graph matching.

- Joint work with Julian McAuley

Bio: Tiberio Caetano studied Electrical Engineering, Physics and 
Computer Science at the Federal University of Rio Grande do Sul (UFRGS), 
Brazil, where he obtained the PhD degree with highest distinction in 
2004.  The research part of the PhD program was undertaken at the 
Computing Science Department at the University of Alberta, Canada.  He 
held a postdoctoral research position at the Alberta Ingenuity Centre 
for Machine Learning and is currently a senior researcher and research 
group manager with the Statistical Machine Learning Group at NICTA.  He 
is also an affiliate faculty member at the Research School of 
Information Sciences and Engineering, Australian National University.  
His research interests include machine learning and computer vision.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20101215/70ff0d46/attachment.htm>

More information about the Ml-stat-talks mailing list