Michael Jordan的图模型导论

需积分: 5 108 浏览量更新于2024-06-21 收藏 6.72MB PDF 举报

"乔丹的《概率图模型导论》PDF文件" 乔丹的《概率图模型导论》是一份详尽的课程资料，由加州大学伯克利分校的Michael I. Jordan教授编纂。该资源是手动整理并拼接成的一个PDF文件，涵盖了概率图模型的基础理论和应用。作为一门课程的讲义，它旨在引导读者进入这个领域，特别是对那些初学者来说，是一份非常有价值的参考资料。在第1章中，虽然原文尚未完成，但作者建议读者可以参考其网站上名为“图形模型”的文章（www.s.berkeley.edu/~jordan/publications.html）来替代。这篇文章概述了基本的概率图模型框架和推理算法，并通过几个实际生活中的例子来说明这些模型的应用。概率图模型是一种在统计学中广泛使用的工具，特别是在生物信息学、信息检索、语音处理、图像处理和通信软件等领域。当需要处理涉及数千甚至数百万随机变量的大型模型时，这些图形模型提供了一种通用的方法。它们通过图形化的方式表示变量间的条件依赖关系，使得理解和推断复杂概率分布变得更加直观和高效。图形模型的核心概念包括贝叶斯网络和马尔科夫随机场。贝叶斯网络是一种有向图模型，其中节点代表随机变量，边表示变量之间的条件概率关系。而马尔科夫随机场是无向图模型，强调了变量的局部条件独立性。这两种模型都支持各种推断算法，如变量消元法、信念传播（如贝叶斯网络中的消息传递）和最大似然估计等。在乔丹的讲义中，读者可以期待深入学习如何构建、分析和利用这些模型解决实际问题。此外，这份资料可能还会涵盖一些高级主题，如结构学习（自动发现模型结构）、参数估计（确定模型参数）、近似推理（用于处理大规模模型的计算策略）以及在不同领域的具体应用示例。对于想要深入理解概率图模型及其在现实世界应用的学者或从业者，《概率图模型导论》是一份不可多得的学习资源。它将帮助读者掌握这个强大工具的理论基础，同时提供实践经验，以便在未来的工作中能够有效地运用这些知识。

which are formed into a tree. The sum-product algorithm running on this tree yields not only a

single marginal, but all marginal s, where by “marginal” we now mean the marginal probability of

all variables in each clique. The computational complexity of the algor ithm is determined by the

size of the largest clique, which is lower bounded by the treewidth of the graph.

In summary, exact inference al gor i thms such as the elimation algorithm, the sum-product algo-

rithm, and the junction tr ee algorithm compute marginal probabilities by systematically exploiting

the graphical structure; in essence exploiting the conditional i ndependencies encoded in the pattern

of edges in the graph. In the best case, the treewidth of the graph is small, and an elimination

order that achieves the treewidth can be found easily. Many classical graphical models, including

hidden Mar kov models, trees, and the state-space models associated with Kalman ﬁltering, are of

this kind. In general, however, the treewidth can b e overly large, and in such cases exact algorithms

are not viable.

To see how to proceed in the case of more complex models, note that large treewidth heuristically

implies that the intermediate terms that are computed by the exact algorithms are sums of many

terms. This provides hope that there might be concentration phenomena that can be exploited by

approximate inference methods. These concentrations (if they exist) are necessarily dependent on

the speciﬁc numerical values of the potentials. In the next two sections, we overview some of the

algorithms that aim to exploit both the numerical and the graph-theoretic properties of graphical

models.

3.2 Sampling algorithms

Sampling algorithms such as importance sampling and Markov chain Monte Carlo (MCMC) provide

a general methodology for probabil i stic inference (Liu, 2001, Robert and Casella, 2004). The

graphical model setting provides an opportunity for graph-theoretic structure to be exploited in

the design, analysis and implementation of sampling algorithms.

Note in particular that the class of MCMC algorithms known as Gibbs sampling requires the

computation of the pr obab i li ty of individual variables conditioned on all of the remaining variables.

The Markov properties of graphical models are useful here; conditioning on the so-called Markov

blanket of a given node renders the node independent of all other variables. In directed graphical

models, the Mar kov blanket is the set of parents, children and co-parents of a given node (“co-

parents” are nodes which have a child in common with the node). In the undirected case, the Markov

blanket is simply th e set of neighbors of a given node. Using these deﬁnitions, Gibbs samplers can

be set up automatically from the graphical model speciﬁcation, a fact that is exploited in the BUGS

software for Gibbs sampling in graphical models (Gilks et al., 1994). The Markov blanket is also

useful in the design of Metropolis-based algorithms—factors that do not appear in the Markov

blanket of a set of variables being considered in a proposed update can be neglected.

Finally, a variety of hybrid algorithms can be deﬁned in which exact i nference algorithms are

used locally within an overall sampling framework (Jensen et al ., 1995, Murphy, 2002).

3.3 Variational algorithms

The basic idea of variational inference is to characterize a probability distribution as the solution

to an optimization prob lem, to perturb this optimization problem, and to solve the perturbed

problem. While these methods are applicable in p ri n cipl e to general probabilistic inference, thus

far their main domain of application has been to graphical models.

In their earliest application to general statistical inference, variational methods were formulated

in terms of the minimization of a Kullback-Leibler (KL) divergence, and the space over which the

optimization was performed was a set of “simpliﬁed” probability distributions, generally obtained

by removing edges from a graphical model (see Titterington, 2004, thi s volume). A more general

perspective has emerged, however, which relaxes the constraint that the optimization is performed

over a set of probability distribu tion s, and no longer focuses on the KL divergence as the sole

optimization fun ctional of interest. This approach can yield signiﬁcantly tighter approximations.

We brieﬂy overview the key ideas here; for a detailed presentation see Wainwright and Jordan

(2003).

case they are the marginal pr ob abi l i ties that were our focus in Sec. 3.1. Eq. (10) is a general

expression of the in f erence problem that any algorithm (such as the junction tree algorithm) aims

to solve.

Approximate inference algorithms can now be obtained by perturbing the optimization problem

in Eq. (10) in various ways. One approach i s to restrict the optimization to a class of simpliﬁed

or “tractable” distributions—this is kn own as the mean ﬁeld approach (Jordan et al., 1999). Thus

we consider a subset M

T ract

⊆ M corr esponding to distributions that are tractable vis-a-vis an

algorithm such as the junction tree algorithm, and restrict the optimization to this set:

sup

µ∈M

T ract



hµ, θi − A

∗

(µ)



. (13)

The optimizing values of µ are the mean ﬁeld approximations to the expected suﬃcient statistics.

Moreover, b ecause we have restricted the optimization to an inner approximation to the set M, we

obtain a lower bound on the cumulant generating function.

Another class of variational inference algorithms can be obtained by considering ou ter approx-

imations to the set M. In particular, the parameters µ must satisfy a number of consistency

relations if they are to be expected suﬃcient statistics of some probability distribution. The Bethe

approximation involves retaining only those consistency relations that arise from local neighbor-

hood relationships in the graphical model, dropp i ng all other constraints (Yedidia et al., 2001).

E.g., for a linked pair of n odes (s, t), the marginal µ

, x

) must equal µ

) if we sum over x

and also the marginal µ

, x

) must also equal µ

) if we sum over x

for a link (s, u). Let

us refer to the set containing such vectors µ as M

Local

, where M ⊆ M

Local

. Carrying out the

optimization over this set, we h ave the Bethe variational problem:

sup

µ∈M

Local



hµ, θi − A

∗

Bethe

(µ)



. (14)

Note that A

∗

has been replaced by A

∗

Bethe

in this expression. Indeed, by assumption it is infeasible to

compute the conjugate function A

∗

on M, and moreover it can be shown that A

∗

is inﬁnite ou tside

of M, so an app r oximation to A

∗

is needed. The quantity A

∗

Bethe

is known as the Bethe entropy,

and it is a sum of entropy terms associated with the edges of the graph; a natural counterpart to

Local

One can attempt to solve Eq. (14) by adding Lagrange multipliers to reﬂect the constraints

deﬁning M

Local

and diﬀerentiating to obtain a set of ﬁxed point equations. Surprisingly, these

equations end up being equivalent to the “sum-product” algorithm for trees in Eq. (6). The

messages m

) are simply exponentiated Lagrange multipliers. Thus the Bethe approximation

is equivalent to applying the local message-passing scheme developed for trees to graphs that have

loops (Yedidia et al., 2001). The algorithm has been surprisingly successful in practice, and in

particular has been the algorithm of choice in the applications to error-control codes discussed in

Section 5.

The area of variational inference has been quite active in recent years. Algorithms known as

“cluster variation methods” have been proposed that extend the Bethe approximation to high-order

clusters of variables (Yedidia et al., 2001). Other papers on higher-order variational methods in-

clude Leisink and Kappen (2002) and Mi nka (2002). Wainwright and Jordan (2004) have presented

algorithms based on semideﬁnite relaxations of the variational problem. Theoretical analysis of vari-

ational inference i s still in its infancy; see Tatikonda and Jordan (2002) for in i tial steps towards an

analysis of convergence.

Given that variational inference methods involve treating inference p r obl ems as optimization

problems, empirical Bayes procedures are par ti cul arl y easy to formulate within the variational

framework, and many of the applications of variational methods to date have been empirical

Bayesian. The f r amework does not require one to stop short of full Bayesian inference, how-

ever. See, e.g., Attias (2000) and Ghahramani and Beal (2001) for recent papers devoted to full

Bayesian applications of variational inference.

4. Bioinformatics

The ﬁ eld of bioinformatics is a fertile ground for the app li cation of graphical models. Many of

the classical probabilistic models in the ﬁ eld can be viewed as instances of graphical models, and

剩余564页未读，继续阅读

冬虫夏草1993

粉丝: 49
资源: 2

Michael Jordan的图模型导论

an introduction to graphical models

introduction to graphical model

introduction to graphical modelling

AN INTRODUCTION TO GRAPHICAL model

Introduction to Graphical Model

an introduction to probabilistic graphical models by Michael Jordan

An Introduction to Probabilistic Graphical Models

An introduction to probabilistic graphical models

Introduction to Graphical Models

Introduction to Probabilistic Graphical Models

最新资源