IIT CS583 概率图模型笔记思维笔记模板_ProcessOn思维导图、流程图

part1 -syllabus

syllabus

Chapter 1 - Introduction
Chapter 2 - Foundations
Chapter 3 - The Bayesian Network Representation
Chapter 4 - Undirected Graphical Models
Chapter 5 - Local Probabilistic Models
Chapter 6 - Template-Based Representations
Chapter 7 - Gaussian Network Models
Chapter 8 - The Exponential Family
Chapter 9 - Variable Elimination
Chapter 10 - Clique Trees
Chapter 11 - Inference as Optimization
Chapter 12 - Particle-Based Approximate Inference
Chapter 13 - MAP Inference
Chapter 15 - Inference in Temporal Models
Chapter 16 - Learning Graphical Models: Overview
Chapter 17 - Parameter Estimation
Chapter 18 - Structure Learning in Bayesian Networks
Chapter 20 - Learning Undirected Models
Chapter 21 - Causality
Chapter 22 - Utilities and Decisions
Chapter 23 - Structured Decision Problems

https://github.com/CS583pgm/F2021

推荐教材 -概率图模型原理和技术 Daphne koller

part2 -foundations

教材阅读&lecture

陈述性表示（declarative representation）

知识和推理分离，可以设计通用的算法，而不考虑所用知识所在的领域

概率基础

Ω定义为空间，S定义为可测试事件集合，a∈S，比如骰子，6是一个结果 S={1,3,5}表示事件【奇数】

概率分布：

P(a)>=0 for all a∈S

P(AUB)=P(A) U P(B)

p(Ω)=1

概率学派解释

频率派：解释为事件发生的频率，无限次重复试验的结果比值。

条件概率 P（B | A）已知A发生的前提下B发生的概率 P（A ∩ B）=P(A)*P(B|A)

summation rule

链式法则：P(first)P(second|first)P(third|first,second)…P(last|all_previous) ，举例：

贝叶斯规则：

随机变量

伯努利分布 val(X) ={true,false} 的多项式分布

P（X）实际上是的缩写

合取实际缩写成P(x,y)

边缘概率分布，是一个值，一列或者一行的和

联合概率分布，是一个矩阵式内容，表达所有可能的结果

条件概率P（X|Y)

相互独立 P（ a|b）=p（a）

条件独立P（a|b∩c）=P（a|c）或者 P（a∩b | c）=P（a|c）P（b|c）

举例：已知成绩c的前提下，a和b学校都录取的概率=已知c的前提下a录取的概率 × 已知c的前提下b录取的概率

MARGINAL INDEPENDENCE

P(a|b)=P(a) or P(b)=0

P(a,b)=P(a)P(b)

P(X=t）=0.6 ； P(Y=t）=0.3 ；P（x=t,y=t）=0.18 边缘独立

conditional probabilitiy

P（Grade） =（a,b,c）

P(Grade|industious)=(a|i,b|i,c|i) (a|¬i,b|¬i,c|¬i)

P(Grade|industrious= industrious) = (a|i,b|i,c|i)

P(Grade=a | industrious=industrious)=(a|i)

随机变量的独立性

条件独立泛化到变量集，就是 P满足(X=x⊥Y=y | Z=z) ，如果Z是空，本质也就是P满足（X⊥Y），称之为边缘独立

查询分布

概率查询

P（Y|E=e），已知证据e的前提下，查询Y的边缘概率

MAP查询（最大后验概率）（也称为MPE 最可能解释）

边缘最大后验概率查询

连续空间

概率密度函数（probability density function）

我们一直所说的概率密度函数就是只我们想要求面积时候的那个图形的表达式

神解释：考虑一个密度分布不均匀的小球，总质量为1，概率密度就相当于这个小球某处的密度，值是可以大于1的，但是这个密度乘以体积所得的质量（也就是概率）是恒小于等于1的。然后至于概率密度越大的点，说明单位体积落在该点的质量越大（也就是发生这个点附近事件的概率越大）

条件概率分布密度

均匀分布（uniform distribution）

x~Unif[a,b]

高斯分布

联合密度函数，条件密度函数

Uniform and Gaussion Distribution

if X~，then E[X]=，Var[X]=

期望、方差

Expectation

Variance

图基础

节点和边：边分为有向边和无向边，有向边的图既为有向图，无向边的图既为无向图

有向边：Xi->Xj∈ε,则称Xj在图中是Xi的子节点，Xi是Xj的父节点

无向边: Xi - Xj ,则称他们是邻节点

节点X的度（degree)是其参与的边个数

节点X的入度（indegree）是所有有向边Y->X的个数

图的度是图中节点的最大度

子图和团

路径和迹：路径是符合 Xi->Xj 或者 Xi-Xj ,迹不需要一定符合 Xi->Xj ；every paths is trails ，every trails is not paths

连通图：图中任意两节点之间都有迹

圈（cycle）：存在一条路径Xi.....Xk 最终Xi=Xk；环（loop）存在一条迹Xi.....Xk 最终Xi=Xk

有向无圈图 DAG 是构成贝叶斯网络的基本表达

包含有向边和无向边的有圈图，称之为PDAG，部分有向无圈图

part3 -Bayesian network

教材阅读&lecture

背景：表示联合概率分布所需的参数量大，是专家系统进行表达的主要障碍

Why is BAD? Computational | Cognitive | Statistical challenge

COMPACTNESS（紧凑型）

Reduce the number of parameters through independence 通过独立性减少参数

条件参数化方法--如何计算需要多少个参数

P(x1,x2...xn,y1,y2,...ym) 每个有参数都是binary，需要个参数

P(y1,y2..ym|x1,x2...xn)每个有参数都是binary，需要

至少需要表示,,这三个参数，所以【联合分布表示为4个结果的多项式，需要3个参数】

向如下这种三值多项式，其实需要每行需要2个参数表示，所以总计需要4个参数

3.1.3.1的例子实际上用独立性对表达式进行了替换

=* 直接表达I，S，G的联合概率分布2*2*3 需要12个数，所以需要11个参数

如果假设，即已知一个学生是高智商的前提下，那么再多知道他的SAT成绩，对于得知他哪儿课成绩，是没影响的，那么,只需要2+2+3=7个参数即可

朴素贝叶斯：在给定的事例的条件下，所有特征独立

核心是将参数与变量的关系变成线性关系，而非联合分布的指数关系

贝叶斯网 -DAG

两种理解贝叶斯网的方式：数据结构和条件独立假设

推理模式--数据结构

逐步获得图中各种因素而【顺流而下】对影响的查询，称之为因果推理（causal reasoning）护着预测（prediction） Causal reasoning

逐步获得证据，不断调整【原因】的概率的查询，称之为证据推理(evidential reasoning）或者解释（explanation） Evidential reasoning

Intercausal reasoning（比书种多出的一种，从中间查的定义）

解释消除--有新证据出现的时候，就消除了旧证据单独对结果的一些影响概率，例如:,而获得一门课难度后,就销售了成绩低事件的影响

BAYESIAN NETWORK STRUCTURE

HUGIN LITE（software）贝叶斯网络工具

条件独立假设

由例子图中可得到

但是无法得到，并不是因果关系，已知父节点就独立的，当获得了L的信息后，也会影响G的概率，既：

一旦明确了一个节点的父节点的值，那么父节点再向上的祖先的直接or间接的影响都被包含在父节点里了已经

定义：在给定父节点条件下，每个节点与其非后代节点条件独立

从分布到图

用图G来展现分布P的结构

通过构建P的图G 并检测G 的D分离，就可以获得P的独立性

最小I-map

图K是I的一个一个I-map，从K中移除任何一条边都使得它不再是I-map，那么图K就是I的 minimal I-map

I-MAP TO FACTORIZATION

是通过I-map的独立性断言，对分布P进行化简

FACTORIZATION To I-map

If P factorizes over G, then G is an I-Map for P.

图的独立性

D分离

XYZ典型的四种双边迹

因果迹

证据迹

共同原因

共同作用 ,也称之为V结构

Z不作为观察点的时候，XY条件独立

Z作为观察点点时候，XY不条件独立

都需要考虑观察 Z 和不观察Z两种情况（逻辑拆分）

不观察 Z ，只有满足，才能说明X与Y相互独立

观察Z，只有满足，才能说明X与Y关于Z相互独立

X->Z->Y （Y->Z->X同理）

X<-Z->Y

若不观测Z，则P(X,Y)=∑zP(X,Y,Z)=∑zP(X|Z)P(Y|Z)P(Z)。X与Y并不是独立事件

X->Z<-Y

若不观测Z，则P(X,Y)=∑zP(X,Y,Z)=P(X)P(Y)∑zP(Z)=P(X)P(Y)。X与Y相互独立

若观测Z，则P(X,Y|Z)=P(X,Y,Z)/P(Z)=P(X)P(Y)P(Z|X,Y)/P(Z)。X与Y关于Z不独立

有效迹的概念

对于贝叶斯网络中的一条迹（路径）和观测变量Z，当的取值能够相互影响时，称路径是有效的

当不是有效迹时，那么显然相互独立

全局马尔可夫独立性

可靠性和完备性

D分离算法

判断XY之间所有迹，是不是都是有效迹，但是低效

step1：从叶到根遍历，Z和Z中有后代的节点

step2：广度优先，从X到Y沿迹遍历，遇到阻塞就停止，最终能找到一条X到Y的迹，就说明存在有效迹

D分离举例

判断x,y是否关于z D分离：

X和Y关于Z有向分离，等于X和Y关于Z条件独立

X到Y的Tail不是Active，等于X和Y关于Z条件独立

D分离定义：给定Z，只要在贝叶斯网中，X到Y的Trail不是Active，就说明X和Y关于Z是有向分离(d-separation)的

I 等价

如果I(k1)=I(k2),就说这两个图结构K1和K2是I等价

相同骨架和相同V结构能推导两个G是I等价（充分不必要条件）

相同骨架和相同非正则结构集合 <==>两个G是I等价（充要条件）

非正则结构

X->Z<-Y 中，X和Y之间没有有向边，那么它是一个非正则结构（immorality）

I(G1)=I(G2)=I(G3)

A given distribution can be represented with one of I-equivalent structures and it might be impossible to identify a unique structure

X ->Y and X <- Y are I-equivalent. Then, we cannot readily argue whether X causes Y or Y causes X.(数据并没有告诉我们因果关系）

I-map

是在P中成立的形如的独立断言集合

一个概率分布 P 包含有一堆条件独立关系，把这个条件独立关系的集合称为 I(P)；一张 Graph G 也包含了一堆条件独立关系，把这堆条件独立关系的集合称为 I(G)。如果 I(G) 包含于 I(P)，那么就把这张 Graph G 叫做这个概率分布的 I-map (Independence-map)。

I-map到因子分解，通过已知的I(P) 里的断言，来化简联合规律分布的因子

贝叶斯网的链式法则：

每一个P的 I-map k，每一个属于K的断言，在P里肯定都是真，但是P内可能包含K以外的断言

P-Map (perfectmap）: I(G)=I(P) ，G是一个P分布的 Pmap

finding minimal I-map (building Bayesian network）算法

按变量序列 , 将，作为的初始U

从U小到大，寻找

如果找到就用新的U 替代原来的U

找不到就继续用原先的U

用U的每个节点指向生成一条边

finding I -quivalent 算法

先画出来全连接的无向图

假设最深的入度是d

逐个 x-y 对儿，进行查找原图中的

每查找一次，如果找不到任何独立，就保留边

如果找到独立，就删除边，并且把作为一组记录进一个{集合}

剩下的无向图中，找出左右v结构

在这些v结构中，找XZY中的XZY是否在↑{集合A}里，如果在，说明这不是非正则结构，如果不在则可以定向X->Z<-Y

给其他边定向（遵循不能有cycle的原则）

summary

图 G 分布 P

I-MAP

P-MAP

and no edge can be remove is minimal I-map

part4 -Undirected Graphical Models

lecture&教材阅读

马尔科夫网（markov network）：举例，比如希望表示A和B两人意见一致的可能性，本质是A和B与一个因子（facor）联系起来，而没有方向性（既这个因子）

实数域R：实数域是实数所在的有理集合，具有连续性、完备性、有序性等性质

；实际上因子是functions from D to R

联合概率分布P(a,b,c,d)=/Z ; Z=

Z又称之为配分函数

分布P的独立性性质直接分布P在图上的分离性性质对应

有些分布无法用贝叶斯网络表示；比如： , ; 保证没有循环是很难的；

Graphs markov network

markov

Structure

无向图

Parameters

参数本身也是无向的

没有足够的参数表达每两两之间的因子，所以实际上会用因子的乘积表达其他因子

；就是吉布斯分布（Gibbs distribution）

和不一定一致，因为其他因子的影响可能更强

边缘概率更大

ϕ (A, B)

因子中，概率更大

Independencies

团位势(clique potential) :参数化马尔科夫网的因子，团(clique)就是一个无向图的完全子图，既然是完全图，当然每对顶点之间都必须要有边相连。

如果包含X Y 的一个因子，实际上引入了一个交互影响，所以图中XY之间有一条边

团指的：{A,B}{B,C}

最大团（maximum clique）：最大团就是就是结点数最多的极大团

极大团（maximal clique）: 如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团

因子分解：假设每个都是H的完备子图，则称具有的分布在马尔可夫网上H因子分解

简化马尔可夫网

马尔可夫网在计算机视觉中称之为马尔卡夫随机场（MRF）

X⊥Y|Z if X and Y are separated in H given Z (当无向图中，给定Z的时候，X和Y就没有通路了，就认为是独立的）

Markov Blanket （马尔可夫毯）

X ⊥ X \ MB(X) | MB(X), where MB stands for Markov Blanket. Markov Blanket of a variable X in a Markov network H is its neighbors.

MB 是 x 的所有邻居，也就是当给定你的所有邻居节点的时候，你和其他非邻居节点独立（例子中，A⊥ DE|BC)

因子图

因子图包含两类节点：变量节点和因子节点，以及变量节点和因子节点之间的边

对数线性模型

能量函数

特征表示

特征f(D) 是 val（D) 到R的一个函数

指示特征函数，输出 1or 0

可以将马尔可夫网表示成一个对数线性模型

THREE DIFFERENT PARAMETERIZATIONS

Undirected graph

Factor graph

features

度量马尔可夫随机场 MRF

过参数化

标准马尔可夫表示提供了太多空间，很难解释共享团中的具体影响，因此分布可以用无穷多种参数表示

标准参数化，标准能量函数

ISING MODELS(伊辛模型）

最早的马尔可夫网之一

CRFs

统一有向和无向图--条件随机场是一个在变量子集上存在有向依赖的马尔可夫网

判别式模型 discriminative model 计算条件概率，而生成式模型 generative model 计算联合概率分布，所以CRF是判别模型

FROM DISTRIBUTIONS TO GRAPHS

find minimal I-map

Add edges between X and Y, if P does not entail X ⊥ Y | X\ {X, Y}

Add edges between X and all

BNS to MNS

x y 之间有边的或者 xy 是同一节点的父节点 ----M[G]（道德图）需要在xy之间补无向边

贝叶斯网络G，B是G的任意一个分布，则M[G]是的I-map(也就是说M[G}表达的独立性可能少于)

进一步：M[G]也是的 minimal I-map

如果贝叶斯网络图G本身是正则的，则M [G] 是的 P-map

MNS to BNS

实际上是根据MNS的每个节点，按顺序判断独立性，生成BNS的 minimal I-map ( 和BNS的自身根据独立性生成minial I-map一样）

弦图

问题

整体的结构是什么，为什么要做这些？

度量MRFS 为什么可以drop 1/z？

part5 -CPDs

lecture&教材阅读

CPDs or CPTs 都是叫做条件概率表格

CPD is a function that maps (x, Pa(x)) to a conditional distribution P(x|Pa(x))

CPDs的缺点

只能处理离散域的，连续值的处理不了

随着父节点的增多，表格会很庞大

忽略了结构

CPDS类型

Deterministic CPDs

例子

图模型的好处是，结构明确，可以不用查表算数值，就推导出已经成立的独立性

C是AB的确定性函数，那么D⊥E|AB，如果C不是确定性函数是不能推导这个独立性的

因为C是Xor ，所以已知 C和 B 就能推导A ，那么D⊥E | BC

因为C是 or 函数，所以都不需要知道B，仅当知道A=T的前提下 DE就独立了

特定上下文CPD

例子：如果学生不申请（apply=F)的时候，雇主就不会获得letter和SAT的信息，也就是Apply=F的时候，其他所有分布应该相同，或者雇主一旦拿到SAT，根本不考虑letter ，所以)

树CPD

规则CPD

tree CPD 对应的规则值；比如沿着最后得到的的概率就可以获得规则4

Causal independence

The noisy-or model

每一项Zi都不发生 y才不发生才是y0 ,所以 y0的概率是每一项都不发生概率的积，y1 是 1-这个积

Logistic CPD

Linear Gaussian CPD

应对连续变量的情况

总结：CPD本质是表达Y和给定条件的关系，也就变成了一个函数

问题

这张图没懂什么意思

part6-Template -Based representations

lecture&教材阅读

有一些场景是随着输入的变化，条件概率之间会变化，甚至结构会变化

本质是构建一个模板，当接收到输入参数的时候，能根据模板进行自动生成结构、同时参数可以共享

model类型

Temporal models

markov Assumption.

区别

Temporal models

DYNAMIC BAYESIAN NETWORKS

Definition: A dynamic Bayesian network (DBN) is a pair <B0,B→>, where B0 is a Bayesian network over X(0), representing the initial distribution over states, and B→ is a 2-time-slice Bayesian network for the process.

STATE OBSERVATION MODELS

认为有两个独立的假设

状态本身随着马尔可夫方式方式 . --- 也称之为转移模型(transition model)

当给定t时刻状态的时候，O(t) 观测值与整个状态序列条件独立-- 也称之为观测模型（observation model )

例子：

开车中，你实际的位置是真实的状态，google地图通过很多传感器或者参考物观察你的位置，实际会有误差

你的血糖值是真实的状态，但是血糖仪通过扎手指等获得的是观察值，因为各种因素也会有误差

典型的是隐马尔可夫

KALMAN FILTERS

例子：追踪移动物体

plate models（对象关系领域的有向概率模型）

模版的概念，隐形假设认为plate 是相同的CPD，也就所有P(G(S)|I(S))对所有实例的学生都相同

不同课程，会组合

LDA

Relation models

问题：

具体卡尔曼滤波器是什么

隐马尔可夫和卡尔曼滤波需要细致看

part7-VARIABLE ELIMINATION

lecture&教材阅读

推理的复杂性--变量消元是精确推理的一部分

近似推理和精确推理最差的情况下都是NP-难问题，都是需要指数级时间的

Key idea

需要的操作次数大于

变量消元法，就是按指定因子顺序求和，然后normalize

操作次数

假设n个随机变量，m个因子，最大的情况是消去所有变量

乘法次数是

加法次数是

变量消元的基础思路（阅读）

变量消元的本质是动态规划，把中间重复计算的结果进行存储，避免重复计算

不同的顺序，节省不同的重复结算，会带来不同的操作总数

变量消元顺序习题举例

没消元前的总步骤数应该是 ISDGL 乘法步骤 2*2*2*3*2=48（要考虑有多少个表达式相乘？），加法步骤 48-1=47 （乘法步骤是所有变量都需要互相相乘计算，加法步骤是相乘的结果都需要相加）

顺序中的ops 次数有疑惑。。。

是new factor after+ ，举例:

是new factor after * , 举例:

有证据的习题

无向图的习题

用图来表示变量消元

要消除变量X，找出所有X的邻居节点，使得所有邻居节点之间两两相连，然后删除X节点

示例，消除T

寻找最好的消元顺序

最少的邻居 num-neighbors

举例:

过程：

step1：任意选1个节点比如B

step2：寻找剩余未编号的节点集合中和已编号节点邻居最多的节点，如果有多个相同随意选1个，比如图中 SRD 都和B邻居，且只有B1个邻居，假定选S

step3：剩余集合中有LDR都有1个邻居，假定选D

step4：剩余集合中有R有BD两个邻居，L有S1个邻居，所以选R

step5：剩余集合中有L有SR两个邻居，T和X只有1个邻居，A没邻居，所以选L

step6：T有LR两个邻居，所以选T

step7：XA都有1个邻居，顺序无所谓了

最后又大到小消元：AXTLRDB

消除它引入最少的边 min-fill

举例：

{A,T,L,R,S,B,D,X} 消除的话，需要补边的数量是{0,2,2,8,1,2,0,0}

step1:选所有节点中需要补边数做小的节点开始，有多个的话任意选1个，比如A=0

step2:图变成：图中TDX消除缺边都是0，假设选X

最终顺序

在最少邻居和消除引入最少边之间权衡

无关节点 in BNS

独立所以无关：A-->B-->C-->D-->H 的图下，求 P(B|C=T)，D节点是无关节点，因为给定

查询P(Y|E)，Z是Y和E的祖先(注意是祖先，不仅仅是父节点)集合，W-Z-Y-E都是不相关的

part8 -junction tree algorithm

聚类图

对于给定的概率图模型，因子集为，变量集合为X。聚类图是定义在概率图模型之上的一个无向图，每一个节点i是变量集的子集聚类图必须满足组保持的性质，即每一个因子φ必须与一个节点关联，使得因子φ中的随机变量为聚类图中节点中的随机变量的子集，即,同时，对于聚类图中的节点,和节点之间的每一条边定义一个割集，即

团树：通过变量消元法得到聚类图应该为一个团树，团树应满足

树状图：在变量消元的过程中，每一个中间的因子被使用了一次，聚类图中的每一个节点传递一个消息给另外一个节点，因此整个的变量消元过程产生的聚类图为一个树状图

族保持性质：概率图模型中的每一个因子必须出现在某一个消元步骤，所以可以满足族保持的性质

执行交叉性质：对于聚类图而言，如果对于任意的变量
，如果X也出现在两个节点之间唯一路径之间的唯一路径上的每一个节点，则该改聚类图满足执行交叉的性质
举例：

生成团树的过程：

step0: 生成道德图（ xy 是同一节点的父节点 ----M[G]（道德图）需要在xy之间补无向边）

step1:按照消元顺序找到，消除每个变量时涉及的因子合集（实际上是生成了最大团）

step2: 从第一个消除的起点开始，寻找和变量合集交集最大的因子合集当做节点，开始进行连接

step3：如果有多个相同的最大连接，就会产生图中的ADE 和 ABD、DEF的关系，都是有2个交叉

结束的标记：

connect two disconnected components by a maximal size

根据这个图，结束的标志，应该是团树中包含了图中的所有节点的时候

variable elimination on junction tree

团树传播算法（https://www.cnblogs.com/long5683/p/13366178.html）

message (上一次传播过来的内容*本节点内的内容）

所以，意思是B是和下一个节点相关的内容，所以把A合并了，把B相关的概率信息传下去

belief

part9-sampling

近似推理的两种方式

取样

变分推理

采样的分类

采样，顾名思义就是从特定的概率分布中抽取相应样本点的过程。采样在机器学习中有着非常重要的应用：它可以将复杂的分布简化为离散的样本点；可以用重采样对样本集进行调整以更好地适应后期的模型学习；可以用于随机模拟已进行复杂模型的近似求解或推理。另外，采样在数据可视化方面也有很多应用，可以帮助人们快速、直观地了解数据的结构和特性。
对于一些简单的分布，如均匀分布、高斯分布等，很多编程语言里都有直接的采样函数。然而，即使是这些简单分布，其采样过程也并不是显而易见的，仍需要精心设计。对于比较复杂的分布，往往并没有直接的采样函数可供调用，这时就需要其他更加复杂的采样方法。因此，对采样方法的深入理解是很必要的。
另一方面，采样得到的样本集也可以看作是一种非参数模型，即用较少量的样本点（经验分布）来近似总体分布，并刻画总体分布中的不确定性。从这个角度来说，采样其实也是一种信息降维，可以起到简化问题的作用。例如，在训练机器学习模型时，一般想要优化的是模型在总体分布上的期望损失（期望风险），但总体分布可能包含无穷多个样本点，要在训练时全部用上几乎是不可能的，采集和存储样本的代价也非常大。因此，一般采用总体分布的一个样本集来作为总体分布的近似，称之为训练集，训练模型的时候是最小化模型在训练集上损失函数（经验风险）。同理，在评估模型时，也是看模型在另外一个样本集（测试集）上的效果。这种信息降维的特性，使得采样在数据可视化方面也有很多应用，它可以帮助人们快速、直观地了解总体分布中数据的结构和特性

前向采样（forward sampling） no evidence

逻辑：

假定知道结构，知道每个节点的概率，不知道全局概率，用采样的方法近似的估计联合概率分布

方法：

For each variable Vi that is ready Sample a value vi for Vi using P(Vi | Pa(Vi))

ready的标准是没有父节点或者父节点被sample过

最后得到结果表，就可以合并求每个节点的边缘概率

样本数量应该其中绝对误差确保的概率都在对应的误差内

其中 e 相对误差确保的概率都在对应的误差内

接受-拒绝采样（Acceptance-Rejection sampling） with evidence

和前向采样的区别是，先拿到了证据，然后前向采样，当法某个实例的某个节点的采样结果和证据不同，那这个实例被拒绝（丢弃）

Likelihood weighting with evidence

每个抽样的实例拥有一个 weight

Gibbs sampling

MCMC是马尔可夫蒙特卡罗方法，是一种针对高维变量的采样方法

tips：

无论是拒绝抽样还是重要性采样，都是属于独立采样，即样本与样本之间是独立无关的

接受-拒绝采样效率会很低，因为可能大量的样本都是无效的

马尔科夫链的蒙特卡罗方法

part10-MAP INFERENCE

边缘MAP

需要针对 Z 求和

也就是先消元Z 求和

再寻找Y 求最大

sum-product algorithm or max -product algorithm

MAP 指的 MAP(A,B)

P(A)P(B|A)

消元B 过程中，不求和，取B里T和F 最大的

继续消元A ，A=F 大，所有 MAP=(A=F,B=?)

根据图中，A=F的时候B=F大，所以MAP=（A=F,B=F）

当有两个选项概率一样的时候，可以任意取某一个比如 P(A)=<0.5,0.5> MAP =TorF 都正确

part11-Learning overview

learning的动机

learning之前都是假定已知模型的结构和参数，现实中一般让专家搭建这个结构

一般也通过一些典型的查询结果，来检查模型是否返回一般可能的解答

收集数据比获取专家知识更容易

learning的原理

假定领域存在潜在分布P*，由某个有向or 无向模型诱导组成，在给定的分布P中采样M个样本，从中学习模型族

Assume the domain is governed by P*

A network model M*=(K*, q*)

n samples from P*

独立同分布IID Independent and identically distributed

多次掷硬币，每次之间假设是没关系的

多个病人来看病，每个病人之间假设是没关系的

learning

Parameters for a given structure

Parameters and the structure of the network

学习目标

实际情况往往缺乏数据，所以一般选择构造较为近似的模型，近似的模型往往某些方面会做的比较差，所以要明确主要的目标

一般分类

密度估计

具体的预测任务

知识发现

密度估计

用网络进行某个推理任务求 P(...|....)

用相对熵评估近似模型的损失程度

熵：

相对熵可以将公式转化为

寻找最小的KLD 本质是寻找最大的

,它也称之为期望的对数似然

具体的预测任务

分类，本质是求MAP

条件似然

知识发现

找出真实的结构，而不是诱导一个相似的结构以达到近似的预测结果

寻找结构的挑战在于

结构可能不好辨别，因为结构本身可能有多个I等价

证明边是有关联或者方向都很难，因为需要大量的数据

学习优化

有一个候选模型空间(a hypothesis space)(A set of candidate models)

目标函数（Quantifies our preferences over candidates）

学习可以描述为在候选模型空间中寻找得分最高的模型

overfitting ：捕捉了太多的细节，并没有捕捉到规律

偏差：变量之间更独立，更多的数据也是独立，所以需要增加一些函数的参数，欠拟合

方差：变量之间关系更复杂，需要更多的数据找规律，欠拟合

part12-parameter ESTIMATION

overview

假定结构已知、通过样本估算结构的参数

Bayesian network

maximum likelihood estimation

log likelihood

投硬币的例子，假设正反面由参数Θ决定, 投掷5次后，3次正面 2次反面

log likelihood 为 log(L(Θ:D))=3log(Θ)+2log((1-Θ)

对↑ 求导并且令导数为0 ，求出 Θ=3/(3+2)=0.6 ,MLE=0.3

置信区间？

ML from BNs

贝叶斯网络的MLE

The key is that the parameters for each variable can be optimized independently

====>

用联合概率分布的结果数据，可以推导结构是否合理

x1,x2,x3 假设认为是 x1->x2->x3

计算 P(x1=F) *P(x2=F|x1=F)*P(x3=F|x2=F)

计算P(x1=F,x2=T,x3=F)

两者相差很大，说明结构不是这样的

计算中任何一项得到0都是问题，会使得整个结构为0 ，影响学习过程，一般要做特殊处理

Bayesian estimation

先验概率

关于 independence

频率派的逻辑是 Θ是已知且固定的，所以每次投掷获得样本都是独立的符合 plate model，概率固定，每次独立

贝叶斯派的逻辑是，假定我们不知道参数Θ，而是随着不断的获得样本，不断获得一点关于Θ 的信息，那么样本之间就不独立了

本质是期望P(Θ) 的分布在真实值 Θ 周围有一个尖峰

FACTORIZATION

P(D)是已知（已经获得的样本的数据），所以

如果假设关于的先验分布是在[0,1]上的均匀分布，

也叫做拉普拉斯平滑

BETA DISTRIBUTION

mean= a/(a+b)

mode=(a-1)/(a+b-2)

根据 ===>

dirichlet distribution

贝叶斯估计在贝叶斯网络中

本质上更多的先验概率，是降低了预测的方差 ,先验通常也被理解为 belief

在贝叶斯网络中的贝叶斯估计步骤：

step1：先对每个节点获得一个先验概率，直接MLE

step2:假定一个分布假设都是<1,1>

step3:计算每个节点的后验概率，然后按贝叶斯网公式算在整体

先验[1,1]

先验[1000,1000]

k2 prior

贝叶斯网络中的所有节点的先验都是认为是1 ，

BDE prior

实际上是假定了一个数字D，每个节点的超参数使用

MISSING DATA

忽略它

imputing

用其它已有的值替预估填充它

梯度优化

EM 最大期望法（只涵盖这个583）

=/ for each X

https://zhuanlan.zhihu.com/p/78311644

是个迭代的过程

先通过现有的数据，估算了一个

根据估算了缺失数据是什么的可能性

将根据估算估算出来的数据，合并回样本，然后重新估算

重新用新的估算缺失的数据的可能

往复、直到收敛

MARKOV NETWORKS

domain(X)={T,F},Parameters and

when Dataset D has a T and b F instances --> maximum likelihood estimates

因为有Z，所以无法分别对每个节点参数优化

LOG-LINEAR MODELS ：

The log-likelihood is

各自除以

lnZ 是凸函数， -lnZ是凹函数，似然函数=线性函数+凹函数=凹函数 ===>所以不存在局部最优解==>有全局最优解，但不一定唯一 ==>凹函数极大值点就是梯度为0 的点

==> (省略了推导过程）

实例：

由于f1只涉及A 所以

本质上

Gradinet ascent

最大化来估计参数

L1 和L2 的区别？

zero-mean Laplace distribution L2

zero-mean diagonal Gaussian with equal variances L1

l2 比l1 对更大的参数的惩罚粒度更大

L2永远无法使得参数变为0 ，而L1可以

因为L1可以使得一些参数变为0 所以可以使得某两个节点之间失去边的关联，所以理论上可以改变表示

part13-STRUCTURE LEARNING

task : Our task is to learn the structure (and the parameters)

目标和难点：

需要真实分布的I等价

但是由于有噪声的存在，任何两个节点可能都不是独立的，我们如何区分它是不是由于噪声引起的？

添加一条非必须的边（binary），会使得要估计的翻倍，同时也会使得数据更加碎片化，预估结果的方差加大

所以如果数据有限，相比找到更真实的G，更稀疏的G可能更好

BAYESIAN NETWORKS

THREE APPROACHES

Constraint-based structure learning

Find minimal I-MAP

Find all I-equivalent structures

数据很难真的独立 INDEPENDENCE TESTS

+

本质是判断P(x,y)?=P(x)P(y)

MI(mutual information)

当MI和都为0 ，那么x和y独立，但是实际上很难归于到0，往往是设置一个阈值区间

区间大的话，就更多独立，所以图比较稀疏

区间小的话，就更少独立，bian

SCORE-BASED APPROACHES

MAXIMUM LIKELIHOOD SCORE

使用MLE 同时需要参数和 G 都最大的情况

分数= M* MI的和 - M* 熵

增加父节点会使得分属更高因为

最高分的图是完全图

x->y, y->z, z->x

一种方式是限制图的深度

BAYESIAN SCORE

这块已经看不懂了

The mutual information grows linearly in M whereas the model complexity grows logarithmically 、 The larger the M the more emphasis on fit to the data

如何寻找一个好的结构

I等价的结构，分数应该相同，比如 X->Y, Y->X

likelihood score 自然满足

bayesian score 在使用BDe先验方式的时候满足

分数可以被分解

因为分数可以被分解，所以加减边只影响一个变量的分数，颠倒一个边，只影响两个变量的分数

A tree-structured network

非常容易达到plateau

MARKOV NETWORK

CONSTRAINT-BASED

Assume H* is a P-Map for P*

继续用 mutual information for independence test

SCORE-BASED

题外话

频率派和贝叶斯派的核心区别

频率派认为事物本质是固定的，也就是参数是固定的，不断变化的是被测量的数据，测试越多数据，约接近事物的本质（参数既定，数据变量）

贝叶斯派认为事物的本质是变化的，已知的数据才是固定的，越来越多的数据，来不断调整事物的概率（参数是变量，数据是固定的）

交叉熵和相对熵的区别

信息量

一个事件发生的概率越低，则这个事件包含的信息量越大

假设P(x1)=0.9 P(y1)=0.4 ==> I(x1)=-log(0.9)=0.15 I(y1)=-log(0.4)=1.32 y1的信息量更大

熵

熵是一种对不确定性的方法，对于存在不确定性的系统，熵越大表示该系统的不确定性越大，熵为0表示没有任何不确定性

交叉熵

等于评估两个分布之间的信息熵，越低越好

相对熵

KL散度是两个概率分布P和Q差别的非对称性的度量。简单来说，相对熵用来衡量两个取值为正的函数或概率分布之间的差异

相对熵和交叉熵区别在于，交叉熵中P、Q是有真实分布和预测分布的说法的，相对熵没有，且交叉熵代表的是由Q到P的最优策略。
假设我们想知道某个策略和最优策略之间的差异，我们就可以用相对熵来衡量这两者之间的差异。即，相对熵 = 某个策略的交叉熵 - 信息熵（根据系统真实分布计算而得的信息熵，为最优策略)。

闭式解（closed-form）

闭式解也叫解析解 analytical solution

试着程序化的内容

判断独立性（有向和无向）

寻找minimal i-map

寻找I-等价

变量消元

cpds表示

模板表示

MRF和CRF的计算

计算消元成本

寻找消元顺序

samling 程序化

不明白

寻找最好消元顺序的原理是什么

BNS中无关节点的，part2 的原因是什么？

变量消元，节省op 次数的细节

如何看待，团树中，解决share computation的问题？

生成团树的过程中，为什么没有最后的AE ？connect two disconnected components by a maximal size？不懂

junction tree 和join tree。。是一件事

CRF应该细看，弄明白了

变分推理具体指的是什么？

具体为什么精确推理是np-hard

Likelihood weighting 的 W是什么来着？

MCMC、gabbis 采样的原理

这咋推导的来着。。。

凸函数和凹函数

梯度上升到底是为了应对什么？

考试时候可能常用痛点

贝叶斯网寻找无关节点

P(A|B) A和B的所有祖先节点都无关

变量消元顺序 after* 是 participate里有元素的总和，after+ 是

里消除变量后的元素

EM算法，核心算count的时候需要算联合概率

计算全概率分布数值作业1

minimal I-map

I 等价

条件参数算个数

贝叶斯网写公式算参数个数

贝叶斯网独立性判断

马尔科夫网画图算概率

马尔科夫网独立性判断

对数线性模型、特征表示算概率

CRF计算

MRF计算

BNS to MNS

MNS to BNS

CPDs 特定上下文、 Deterministic 指定节点类型

CPDs norsiy or ，logistics CPDs

model STATE OBSERVATION MODELS 和卡尔滤波器的公式会不会考

plate model

变量消元 BN &MN

图消元 min fill & min neighbors

无关节点

生成团树

团树传播计算

抽样: 前向抽样、likelihood 抽样、拒绝抽样、Gibbs抽样

Gibbs实例

P(D)P(I)P(G|D,I)P(S|I)P(L|G)

已知样本 D0 I0 S0 G2 L1

新的第一是求：P(D0| I0，S0，G2，L1）

消除和要求的内容没关系的

=

得出的数字是 P(D|e)=<数字，1-数字> 然后判断本行的采样

注意每行已经得出的样本后，接下来的变量采样就用这行已经得出的替代

参数估计原理、beta分布实验、k2先验、BDE 先验

参数估计 missingData EM算法

马尔科夫参数估计求、Gradinet ascent ，L1 L2 差别

结构学习：X2 和 Mi的计算实例

IIT CS583 概率图模型 笔记

IIT CS583 概率图模型笔记