Applications of Markov random fields part2(Machine Learning)
- Interacting Jump Processes Preserve Semi-Global Markov Random Fields on Path Space(arXiv)
Author : Ankan Ganguly, Kavita Ramanan
Abstract : Consider a system of interacting particles indexed by the nodes of a graph whose vertices are equipped with marks representing parameters of the model such as the environment or initial data. Each particle takes values in a countable state space and evolves according to a (possibly non-Markovian) continuous-time pure jump process whose jump intensities depend only on its own state (or history) and marks as well as the states (or histories) and marks of particles and edges in its neighborhood in the graph. Under mild conditions on the jump intensities, it is shown that the trajectories of the interacting particle system exhibit a certain local or semi-global Markov random field property whenever the initial condition satisfies the same property. Our results complement recent works that establish the preservation of a local second-order Markov random field property for interacting diffusions. Our proof methodology in the context of jump processes is different, and works directly on infinite graphs, thereby bypassing any limiting arguments. Our results apply to models arising in diverse fields including statistical physics, neuroscience, epidemiology and opinion dynamics, and have direct applications to the study of marginal distributions of interacting particle systems on Cayley trees
2.On polynomial-time solvability of combinatorial Markov random fields (arXiv)
Author : Shaoning Han, Andrés Gómez, Jong-Shi Pang
Abstract : he problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled as a mixed-integer program. This motivates us to study a general class of convex submodular optimization problems with indicator variables, which we show to be polynomially solvable in this paper. The key insight is that, possibly after a suitable reformulation, indicator constraints preserve submodularity. Fast computations of the associated Lovász extensions are also discussed under certain smoothness conditions, and can be implemented using only linear-algebraic operations in the case of quadratic objectives
