Undirected Graphical Model Structure

Jump to navigation Jump to search

An Undirected Graphical Model Structure is a graphical probability model instance that is an undirected graph (and with a potential function).




  • http://en.wikipedia.org/wiki/Random_element#Random_field
    • … Several kinds of random fields exist, among them the Markov random field (MRF), Gibbs random field (GRF), conditional random field (CRF), and Gaussian random field. An MRF exhibits the Markovian property : [math]\displaystyle{ P(X_i=x_i|X_j=x_j, i\neq j) =P(X_i=x_i|\partial_i), \, }[/math] where [math]\displaystyle{ \partial_i }[/math] is a set of neighbours of the random variable Xi. In other words, the probability that a random variable assumes a value depends on the other random variables only through the ones that are its immediate neighbours. The probability of a random variable in an MRF is given by : [math]\displaystyle{ P(X_i=x_i|\partial_i) = \frac{P(\omega)}{\sum_{\omega'}P(\omega')}, }[/math] where Ω' is the same realization of Ω, except for random variable Xi. It is difficult to calculate with this equation, without recourse to the relation between MRFs and GRFs proposed by Julian Besag in 1974.





  • (Awate, 2006) ⇒ Suyash P. Awate. (2006). “Adaptive Nonparametric Markov Models and Information-Theoretic Methods for Image Restoration and Segmentation." PhD Dissertation.
    • Markov random fields (MRFs) are stochastic models that characterize the local spatial interactions in data. The last 40 years have seen significant advances in the mathematical analysis of MRFs as well as numerous application areas for MRFs ranging from physics, pattern recognition, machine learning, artificial intelligence, image processing, and computer vision. This has firmly established MRFs as powerful statistical tools for data analysis. This dissertation proposes an adaptive MRF image model and builds processes images relying on this model. This section gives a brief review of theory behind MRFs and some relevant MRF-based algorithms.

      The first concept of the MRF theory came from the physicist Ernst Ising in the 1920s. Ising was trying to devise a mathematical model to explain the experimental results concerning properties of ferromagnetic materials. This dealt with local interactions between a collection of dipoles associated with such materials. He published the model in his doctoral thesis, which later became popular as the Ising model. The name Markov, however, is dedicated in the memory of the mathematician Andrei Markov who pioneered the work on Markov chains, i.e., ordered sequences of RVs where the conditional PDF of an RV given all previous RVs is exactly the same as the conditional PDF of the RV given only its pr{e}ceeding RV. In other words, the next RV, given the present RV, is conditionally independent of all other previous RVs. This notion of conditional independence concerning chains of RVs generalizes to grids of RVs or random fields. Such random fields are called MRFs.

      A random field [47,161] is a family of RVs [math]\displaystyle{ \bf{X} = \lbrace {X_t} \rbrace_{t \in \mathcal{T} } }[/math], for some index set [math]\displaystyle{ \mathcal{T} }[/math]. For each index [math]\displaystyle{ t }[/math], the RV [math]\displaystyle{ X_t }[/math] is defined on some sample-space [math]\displaystyle{ \Omega }[/math]. If we let [math]\displaystyle{ \mathcal{T} }[/math] be a set of points defined on a discrete Cartesian grid and fix [math]\displaystyle{ \Omega = \omega }[/math], we have a realization or an instance of the random field, [math]\displaystyle{ {\bf X} (\omega) = {\bf x} }[/math], called the digital image. In this case, [math]\displaystyle{ \mathcal{T} }[/math] is the set of grid points in the image. For vector-valued images [math]\displaystyle{ X_t }[/math] becomes a vector RV.





  • (Li, 1995) ⇒ Stan Z. Li. (1995). “Markov Random Field Modeling in Computer Vision.” Springer-Verlag. ISBN:4431701451