Application of Message Passing and Sinkhorn Balancing Algorithms for Probabilistic Graphical Models

Probabilistic Graphical Models (PGMs) allow us to map real world scenarios to adeclarative representation and use it as a basis for predictive analysis. It is a framework thatallows us to express complex probability distributions in a simple way. PGMs can be applied to avariety of scenarios wherein a model is built to reflect the conditional dependencies betweenrandom variables and then used to simulate the interactions between them to draw conclusions.The framework further provides many algorithms to analyze these models and extractinformation.One of the applications of PGMs is in solving mathematical puzzles such as Sudoku.Sudoku is a popular number puzzle that involves filling in empty cells in an ‘N x N’ grid in sucha way that numbers 1 to N appear only once in each row, column and ‘N 1/2 x N 1/2 ’ sub-grid. Wecan model this problem as a PGM and represent it in the form of a bipartite graph. The mainconcepts we employ to obtain an algorithm to solve Sudoku puzzles are factor graphs andmessage passing algorithms. In this project we attempt to modify the sum-product messagepassing algorithm to solve the puzzle. Additionally, we implement a solution using Sinkhornbalancing to overcome the impact of loopy propagation and compare its performance with theformer