My PhD thesis investigates exact methods for inference and parameter estimation in graphical models. One widely used method is the Junction-Tree algorithm, which converts a graphical model into a tree of cliques. However the complexity of this algorithm grows exponentially with the size of the maximal clique used. An alternative method is that of the graph cuts, which reduces the inference problem to computing the minimum-cut (or maximum-flow) of the graph. The graph cuts method has a polynomial running time (in the number of nodes), but is limited to graphs with a particular constraint on edge potentials (submodularity constraint). Furthermore, the graph cuts framework is primarily suited for inference, rather than parameter estimation. My thesis presents an exact method that like the Junction-Tree algorithm can be used for both inference and parameter estimation, while retaining the polynomial runtime of the graph cuts method.

In 1960's physicists presented a polynomial-time algorithm for computing the log-partition function of a planar Ising model, which is a crucial step for inference. This model corresponds to a planar graphical model with binary labels and only edge potentials. Recently this method was introduced to the Machine Learning community by Globerson and Jaakkola in 2007 (CiteSeerX), however very few have followed up on that work, perhaps due to the complexity of the algorithm.

My work simplifies earlier algorithms including that of Globerson and Jaakkola, by eliminating the need to construct the expanded dual graph. We show a precise complementary connection between graph cuts and perfect matchings on the expanded dual and establish the role of planarity. We describe how the algorithm can be used in popular parameter estimation frameworks: Maximum-Margin and Maximum-Likelihood; and apply it to a number of real-world problems: image denoising, image segmentation and territory prediction in the game of Go. Finally, we present a number of extensions: prefactoring of the Kasteleyn matrix to speed up training, application to moderately non-planar graphs, application to multi-labeled graphs, close connection to graph cuts and a possibility for a hybrid approach.

Publications

Nicol N. Schraudolph and Dmitry Kamenetsky. Efficient exact inference in planar Ising models, In Advances in Neural Information Processing Systems 21, Cambridge, MA, to appear 2009, MIT Press. [pdf] [poster]

Nicol N. Schraudolph and Dmitry Kamenetsky. Efficient exact inference in planar Ising models, Technical Report 0810.4401, arXiv, October 2008. [pdf] [web]

Yannick Pencolé, Dmitry Kamenetsky and Anika Schumann. Towards Low-cost Diagnosis of Component-based Systems, 6th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes (SAFEPROCESS-06), Beijing (P.R. China) August 29-September 1, 2006. [pdf]

Workshops

Dmitry Kamenetsky, Nicol N. Schraudolph, Simon Günter, S.V.N. Vishwanathan. Modelling Go positions with planar CRFs, NIPS Workshop: Statistical Models of Networks, 2007 [poster]

Dmitry Kamenetsky, Nicol N. Schraudolph, Simon Günter, S.V.N. Vishwanathan. Modelling Go positions with planar CRFs, NIPS Workshop: Machine Learning and Games, 2007 [extended abstract] [talk 3.5Mb]

Theses

Dmitry Kamenetsky. A Comparison of Neural Network Architectures in Reinforcement Learning in the Game of Othello, Honours Thesis, University of Tasmania, 2005. [pdf]

Other

Presentation given at PhD monitoring at the Australian National University in May 2008 [talk 5.8Mb]

Dmitry Kamenetsky and Choon Hui Teo. Solving Minesweeper using Graphical Models, Project report for graphical models course, 2007 [pdf]

Presentation given at the Games Seminar at the University of Alberta in December 2007 [talk 4.3Mb]

Presentation given at PhD monitoring at the Australian National University in September 2007 [talk]

Presentation given at PhD monitoring at the Australian National University in March 2007 [talk 2.5Mb]

Presentation given at PhD monitoring at the Australian National University in September 2006 [talk]

An article on Symmetry Groups that I wrote for the undegraduate journal Nexus at the University of Tasmania in 2004 [pdf]