Message passing is to calculate a marginal probability given a structure of information model (a graph).
[Factor graph]: A factor graph is a bi-partile graph. One type of nodes is random variable (unknown we would like to know). The other type of nodes is factor, which represents the interaction between random variables, or evidences. The global probability must be able to be represented by the multiplication of local factors, i.e.,
p[x1,x2,...,xn] = f1[xv1]f2[xv2]...fm[xvm], where each xv is a list of x (partial set of xn).
The interpretation of the world (the guessing of the random variables) depends on the factors. So if we accumulate the factors,
p = f1*f2*...*fn,
we can calculate the marginal probability by probability propagation.
[Baysian Network]:
The joint probability of a network can be represented as multiplication of local conditional probability. The basic concept is built on sufficient statistics (also conditional independence.)
[e.g.] Three random variables,
x->y->z, p(z x, y) = p(z y). Given y, knowing x has no use. That means, knowing y is sufficient to predict z. (Look wiki for sufficient statistics).
The upshot is that we can factorize the distribution.
If we know p(x,y,z), we can calculate all the marginal distributions such as p(x), p(y), p(xz). If we want to calculate p[z,x=x'], we can start with
p[z,x= x'] = sum_{y}p[x=x',y,z]/sum_{z,y}p[x=x',y,z].
p[z,y,x=x'] = p[z,y,x=x']p[y,x'] = p[z,y]p[y,x']p[x'].
A Baysian network can therefore factorize into localized factors, f1, f2, ...fn.
A Baysian network is a special case of a factor graph.
A random markov field is also a special case of a factor graph.
[Probability Propagation]
To calculate the marginal probability of a factor graph, an algorithm of probability propagation can be adopted.
z-->
y-->f-->x: the edge from a factor node to a variable node.
2007年11月20日 星期二
2007年11月6日 星期二
coding
[Symbol]
x[n] = the nth transmitted symbol.
y[n] = the nth received symbol.
n[n] = the nth received noise.
y[n] = x[n] + n[n].
T: a time interval.
N: number of symbols in an interval (or orthogonal function for better definition).
W: bandwidth.
W = N/2T, by Nuquist sampling theorem.
N0 : noise spectral density.
n[n] = Normal(0, N0/2). From conservation of energy, total energy = N0*W = E[n[n]^2] * N/T. So the variance is linear proportion to noise spectral density. n[n] is the amplitude in time domain, whereas N0 is the amplitude^2 in the spectrum domain.
R : bit rate.
Eb = x[n]^2/R. Power per source bit. Eb is the symbol power spectral density. Eb*W = E[x[n]]*N/T.
SNR: Eb/N0 is dimensionless, reported in decibels.
x[n] = the nth transmitted symbol.
y[n] = the nth received symbol.
n[n] = the nth received noise.
y[n] = x[n] + n[n].
T: a time interval.
N: number of symbols in an interval (or orthogonal function for better definition).
W: bandwidth.
W = N/2T, by Nuquist sampling theorem.
N0 : noise spectral density.
n[n] = Normal(0, N0/2). From conservation of energy, total energy = N0*W = E[n[n]^2] * N/T. So the variance is linear proportion to noise spectral density. n[n] is the amplitude in time domain, whereas N0 is the amplitude^2 in the spectrum domain.
R : bit rate.
Eb = x[n]^2/R. Power per source bit. Eb is the symbol power spectral density. Eb*W = E[x[n]]*N/T.
SNR: Eb/N0 is dimensionless, reported in decibels.
訂閱:
文章 (Atom)