下载文档原格式
干货非常详细的有向图模型与无向图模型原理总结本文是小编结合了多个图模型的经典文章所作的一个总结，对于一谈到图模型和马尔科夫知识就产生厌恶的同学，本文会带你循序渐进的去理解图模型的算法原理。
目录1. 为什么要用有向图模型和无向图模型2. 有向图模型的条件独立概率表示方法3. 无向图模型的条件独立概率表示方法4. 有向图模型举例——贝叶斯网络5. 有向图模型举例——隐马尔科夫模型6. 无向图模型举例——马尔科夫随机场7. 小结概率建模在机器学习领域有着广泛的应用，如贝叶斯分类、隐马尔可夫模型和条件随机场。
在实际的人工智能项目中，我们常常面对高维空间的特征，若以概率的角度去构建机器学习模型，你首先需要做的就是分析高维特征空间的联合概率举例来说，对于K维随机向量，其联合概率为高维空间的分布，一般难以建模。
假设每个随机变量为离散值并有m 个取值，下面开始介绍如何估计随机向量X的联合概率P(X)。
1）最直接的方法是分析随机变量中所有可能的组合，每个随机变量有m个取值，K维随机向量X共有的可能取值，若要通过该方法正确的构建模型，则需要大量的训练数据。
若每一个可能的随机向量X 的联合分布用一个参数表示，那么构建该模型需要参数，当m=2，K=100时，模型参数的大小约为，这大大超出了目前计算机的存储能力。
这里需要提醒的一点是随机向量X共有的可能取值，而模型参数个数是的原因是所有可能取值的概率和等于1，即自由度降低了1。
2）我们对模型结构进行独立性假设，假设随机变量是相互独立的，那么随机向量X的联合概率为：独立性假设相比于第一种方法大大的减少了模型参数个数，如m=2，K=100时，模型参数个数是100，第一种方法的模型参数约为。
3）针对前两种估计联合概率方法的缺点，我们对模型结构进行了条件独立性假设，如果在给定的条件下相互独立，则联合概率有：上式是条件独立性的一个例子，独立性假设大大的减少了模型参数量，举个例子来说：假设有四个二值变量，用第一种方法计算联合概率，那么模型需要个参数。
图的基本概念图是一种直观的离散模型，由于其在众多领域中的广泛应用，越来越引起人们的兴趣，其应用领域包括计算机科学、化学、运筹学、电子工程、语言学和经济学。
我们这一讲学习三种图模型，即无向图、有向图和加权图，看看它们可以表示哪些事物，然后研究两个问题，即欧拉回路问题和汉密尔顿回路问题。
1. 无向图无向图是由有限个点和这些顶点之间的若干连线所组成的。
例如，下面的无向图由3个顶点和5条边组成。
我们把这个图用集合语言描述如下：({v 1, v 2, v 3}, {{v 1, v 1}, {v 1, v 2}, {v 1, v 3},{v 2, v 3},{v 2, v 3}})多重集（multi-set ）：集合中同一个元素可出现多次。
定义1.1 设V 是非空的有限集合，E 是V 上的无序对所组成的有限多重集，则称二元组(V ,E)为无向图（undirected graph ），其中V 称为顶点集，其中的元素称为顶点（vertex ）或者结点（node ），E 称为边集，其中的无序对称为无向边（undirected edge ），简称边。
边{v 1, v 2}通常简记为v 1v 2，并称该边连接顶点v 1和v 2，其中的顶点称为这条边的端点（ends 或end-points ）。
只有一个端点的边称为环（loop ）。
具有相同端点的两条边统称为平行边或者多重边。
不含环和平行边的无向图称为简单无向图。
作为数学模型，其中顶点表示一些不同的对象，边表示两个对象之间的某种联系。
例1.2 Bacon 数查找任意演员的Bacon 数的网址： 。
例1.3 并行计算的循环模型例1.4 并行计算的超立方体模型（hypercube ）2. 有向图定义2.1 若V 是非空的有限集， E 是V 上的有序对组成的有限多重集，则称(V , E)为有向图。
有向边(a,b)通常简记为ab ，其中顶点a 和b 分别称为该有向边的始起点和终点。
图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。
注意：元素可以重复出现的集合称作多重集合。
某元素重复出现的次数称作该元素的重复度。
例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。
从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。
1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。
通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。
与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。
通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。
⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。
（2）顶点数称作图的阶，n个顶点的图称作n阶图。
（3）⼀条边也没有的图称作零图，n阶零图记作N n。
1阶零图N1称作平凡图。
平凡图只有⼀个顶点，没有边。
（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。
（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。
（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。
（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。
概率图模型之有向图与无向图概率图模型之有向图与无向图2010-11-22 16:38:34| 分类：技术仓库 | 标签： |字号大中小订阅转自/blog/cns!2D7821B3AF3C6073!155.entry概率图模型之有向图与无向图图模型用图结构描述随机变量之间的依赖关系，结点表示随机变量，边表示随机变量之间的依赖关系，可以是有向图和无向图。
一无向图模型无向图模型又叫马尔可夫网络、马尔可夫随机场，是关于一组有马尔可夫性质随机变量X的全联合概率分布模型。
1 无向图模型的表示给定包含n个随机变量的问题域，则定义在问题域U上的无向图模型包括拓扑结构和参数两部分:拓扑结构S:节点表示随机变量，两节点之间的连线表示它们之间具有直接的相互影响。
参数Θ:无向图模型参数是对节点之间相互影响的定量描述。
它是拓扑结构S中每个极大完全子图所对应的势函数的集合。
其中，极大完全子图(clique)是指不包含于其它完全子图的完全子图（完全子图中任何两节点是直接相连的），势函数则反映了极大完全子图的每种可能状态的能量。
2 无向图模型的联合概率分解利用无向图模型可将图的联合概率分解为一系列因子式。
给定无向图模型拓扑结构S和参数Θ之后，问题域U上的联合概率密度函数可写为:其中N为无向图中极大完全子图的数目。
3 例子：二有向图模型1 一个简单的例子2 一般情况考虑任意联合分布，通过连续使用乘法规则利用局部马尔可夫性简化简化：在给定其所有父亲节点的情况下，随机变量X与其非后继条件独立。
其中pai是Xi的父节点集合。
三有向图模型与无向图模型的对比：1 共同之处将复杂的联合分布分解为多个因子的乘积2 不同之处有向图模型因子是概率分布、无需全局归一无向图模型因子是势函数，需要全局归一3 优缺点无向图模型中势函数设计不受概率分布约束，设计灵活，但全局归一代价高有向图模型无需全局归一、训练相对高效。
