1. Intro duction
Probabilityisawell-understo od method of representing uncertain knowledge and reasoning
to uncertain conclusions. It is applicable to low-level tasks such as p erception, and to high-
level tasks such as planning. In the Bayesian framework, learning the probabilistic models
needed for such tasks from empirical data is also considered a problem of probabilistic in-
ference, in a larger space that encompasses various possible models and their parameter
values. To tackle the complex problems that arise in articial intelligence, exible meth-
ods for formulating mo dels are needed. Techniques that have been found useful include
the sp ecication of dep endencies using \b elief networks", approximation of functions using
\neural networks", the introduction of unobservable \latentvariables", and the hierarchical
formulation of models using \hyperparameters".
Such exible mo dels come with a price however. The probability distributions they give rise
to can b e very complex, with probabilities varying greatly over a high-dimensional space.
There maybenoway to usefully characterize such distributions analytically. Often, however,
a sample of p oints drawn from such a distribution can provide a satisfactory picture of it.
In particular, from such a sample we can obtain
Monte Carlo
estimates for the expectations
of various functions of the variables. Suppose
X
=
f
X
1
;
...
;X
n
g
is the set of random
variables that characterize the situation b eing mo deled, taking on values usually written as
x
1
;
...
;x
n
, or some typographical variation thereon. These variables might, for example,
represent parameters of the model, hidden features of the ob jects mo deled, or features of
ob jects that may b e observed in the future. The expectation of a function
a
(
X
1
;
...
;X
n
)
| it's average value with respect to the distribution over
X
| can b e approximated by
h
a
i
=
X
~
x
1
X
~
x
n
a
(~
x
1
;
...
;
~
x
n
)
P
(
X
1
=~
x
1
;
...
;X
n
=~
x
n
) (1.1)
1
N
N
1
X
t
=0
a
(
x
(
t
)
1
;
...
;x
(
t
)
n
) (1.2)
where
x
(
t
)
1
;
...
;x
(
t
)
n
are the values for the
t
-th point in a sample of size
N
. (As ab ove, I will
often distinguish variables in summations using tildes.) Problems of prediction and decision
can generally be formulated in terms of nding such expectations.
Generating samples from the complex distributions encountered in articial intelligence
applications is often not easy,however. Typically, most of the probability is concentrated
in regions whose volume is a tiny fraction of the total. To generate points drawn from
the distribution with reasonable eciency, the sampling procedure must search for these
relevant regions. It must do so, moreover, in a fashion that does not bias the results.
Sampling metho ds based on
Markov chains
incorporate the required search aspect in a
framework where it can be proved that the correct distribution is generated, at least in
the limit as the length of the chain grows. Writing
X
(
t
)
=
f
X
(
t
)
1
;
...
;X
(
t
)
n
g
for the set of
variables at step
t
, the chain is dened by giving an initial distribution for
X
(0)
and the
transition probabilities for
X
(
t
)
given the value for
X
(
t
1)
. These probabilities are chosen
so that the distribution of
X
(
t
)
converges to that for
X
as
t
increases, and so that the
Markovchain can feasibly b e simulated by sampling from the initial distribution and then,
in succession, from the conditional transition distributions. For a suciently long chain,
equation (1.2) can then b e used to estimate exp ectations.
1
评论2