Markov Random Field - Understanding the Definition

AI Thread Summary
Markov random fields (MRFs) are defined on a finite connected graph G=(V,E), where a random element X takes values in S^V. The conditional distribution of X for a subset W of vertices depends only on the values of X at the boundary of W. The discussion clarifies that the domain of X is V, with each vertex representing an element of a set of random variables, rather than states. The distinction between a vector of random variables and a set is emphasized, as well as the importance of the selection process in defining the domain. Understanding these concepts is crucial for interpreting articles that utilize MRFs.
Palindrom
Messages
263
Reaction score
0
First encounter with the term, I'd like some help understanding it. I know there are several approaches, but this one is important to me because I'm trying to understand an article that uses it throughout its text.

Definition: Let G=(V,E) be a finite (connected) graph and let S be a finite set. A random element X taking values in S^V is said to be a Markov random field if for each W\subset V, the conditional distribution of X(W) given X(V\W) depends on X(V\W) only through its values on \partial W.

It goes on to write this mathematically, which I will write down here if you ask me to. My problem is with the phrase "A random element X taking values in...".
I just want to know from where to where X is. Obviously X takes values in S^V, so this is the range of X. What is its domain?
 
Physics news on Phys.org
Obviously X's domain is W. E.g. X(w) = 1 if w = Head, X(w) = 0 if w = Tail. Then W = {Head, Tail).
 
I don't have W, I have only V and S.

Did you mean V? So X:V\rightarrow S^V?

I don't see the sense of that - V doesn't represent states, it is the vertices's set of the graph.

Could you explain?
 
You are right, W is a subset of V; so the domain is V.
 
I can't see why. Needless to say I believe you, but I don't understand it.

You're telling me that X:V\rightarrow S^V? I can't see why, V represents locations, not outcomes in some experiment. I mean, are we assigning to each atom a configuration of the whole system?

Besides, what is the probability measure on V?
 
Last edited:
I should have differentiated between a vector X of random variables and a set X of random variables. From your definition, X is a set of random variables. Each vertex v of V represents an element of X.

In the 2-D Isling model, (V,E) looks like:
?
?
?
?
where each ? is a vertex v with two possible values (+,-) and 4 neighbors (North, East, South, West), unless it is sitting on the boundary.

Had X been defined as a vector, the domain of X would have been the sample space \Omega which underlies the joint probability P(X = x).

But for a subset U of V, X(U) denotes the image of "those vertices that are included in U." (When X is a set, there is an implicit selection process w/r/t which vertices to include in the set.)

Although the v's in V have the joint domain \Omega, the domain of the set X is defined as V. This emphasizes the selection process. At least that's how I understand it.

A more complete notation would be to write \bold X(V(\Omega_V)) = SV. Although with some misuse of notation one might write \Omega_V for V. This would fold the selection process into the sample space.

A free e-book can be found at: http://www.ams.org/online_bks/conm1/
 
Last edited:
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top