UMass Machine Learning and Friends Lunch | Main / Dynamic Programming Lifts Of Graphs And Counting Problems

Abstract: Recent advances in the study of approximate inference algorithms in the machine learning community have led to provable lower bounds on the partition function for certain families of graphical models. I'll explain how simple dynamic programming algorithms combined with "lifts" of graphs have led to these new lower bounds and how lifts of graphs can lead to better algorithms for approximate inference. I'll conclude by discussing a number of interesting conjectures related to classic counting problems in computer science.

Bio: Nicholas Ruozzi graduated from Yale University in 2011 with a Ph.D. in computer science. He was a postdoctoral researcher at Ecole Polytechnique Federale de Lausanne (EPFL) from 2011-2013. He is currently a postdoc and adjunct assistant professor at Columbia University. He is primarily interested in graphical models, approximate inference, and optimization.