IIT CS583 概率图模型 笔记

一课一章程

标题需要分层整理

公式手写不截图

笔记结构

Chapter 1 - IntroductionChapter 2 - FoundationsChapter 3 - The Bayesian Network RepresentationChapter 4 - Undirected Graphical ModelsChapter 5 - Local Probabilistic ModelsChapter 6 - Template-Based RepresentationsChapter 7 - Gaussian Network ModelsChapter 8 - The Exponential FamilyChapter 9 - Variable EliminationChapter 10 - Clique TreesChapter 11 - Inference as OptimizationChapter 12 - Particle-Based Approximate InferenceChapter 13 - MAP InferenceChapter 15 - Inference in Temporal ModelsChapter 16 - Learning Graphical Models: OverviewChapter 17 - Parameter EstimationChapter 18 - Structure Learning in Bayesian NetworksChapter 20 - Learning Undirected ModelsChapter 21 - CausalityChapter 22 - Utilities and DecisionsChapter 23 - Structured Decision Problems

https://github.com/CS583pgm/F2021

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

syllabus

part1 -syllabus

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

陈述性表示（declarative representation）

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（X）实际上是的缩写

合取span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\" P（X=x，Y=y）\

随机变量

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

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

条件概率P（X|Y)

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

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

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

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

MARGINAL INDEPENDENCE

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

conditional probabilitiy

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

随机变量的独立性

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

概率查询

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

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

边缘最大后验概率查询

查询分布

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"P(a=x

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

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

概率密度函数（probability density function）

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"P(Y|X=x)=\\lim_{\\xi \\to 0}P(Y|x-\\xi=X

条件概率分布密度

均匀分布（uniform distribution）

高斯分布 

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

if X~span class=\"equation-text\" data-index=\"0\" data-equation=\

Uniform and Gaussion Distribution

连续空间

Expectation

Variance

期望、方差

概率基础

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

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

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

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

子图和团

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

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

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

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

图基础

教材阅读&lecture

part2 -foundations

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

Why is  BAD? Computational | Cognitive | Statistical  challenge

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

COMPACTNESS（紧凑型） 

font color=\"#c41230\

至少需要表示span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"P(i)\

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

span class=\"equation-text\" data-index=\"0\" data-equation=\

如果假设 span class=\"equation-text\" data-index=\"0\" data-equation=\

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

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

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

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

贝叶斯网 -DAG

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

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

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

解释消除--有新证据出现的时候，就消除了旧证据单独对结果的一些影响概率，例如:span class=\"equation-text\" data-index=\"0\" data-equation=\"P(i^{1}|g^{3})=0.079\" contenteditable=\"false\

BAYESIAN NETWORK STRUCTURE

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

推理模式--数据结构

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

由例子图中可得到

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

条件独立假设

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

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

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

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

最小I-map

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

I-MAP TO FACTORIZATION

FACTORIZATION To I-map

从分布到图

因果迹 Z-Y\"

证据迹span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"X-Z

共同原因 span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"XY\"

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

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

共同作用Z-Y\

不观察 Z ， span class=\"equation-text\" data-index=\"0\" data-equation=\

观察Z，只有满足span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

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

X<-Z->Y

X->Z<-Y

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

XYZ典型的四种双边迹

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

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

有效迹的概念

全局马尔可夫独立性

可靠性和完备性

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

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

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

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)的

D分离举例

D分离

相同骨架和相同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 

I 等价

图的独立性

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

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

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

贝叶斯网的链式法则：span class=\"equation-text\" data-index=\"0\" data-equation=\

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

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

I-map

按变量序列 span class=\"equation-text\" data-index=\"0\" data-equation=\

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

找不到就继续用原先的U

从U小到大，寻找

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

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

先画出来全连接的无向图

假设最深的入度是d

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

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

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

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

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

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

finding I -quivalent 算法

   I-MAP

  P-MAP

 and no edge can be remove  is minimal I-map

图 G  分布 P

summary

part3 -Bayesian network

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

Z又称之为配分函数

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

有些分布无法用贝叶斯网络表示；比如：span class=\"equation-text\" data-index=\"0\" data-equation=\

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

无向图

Structure

参数本身也是无向的

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

ϕ(Aspan class=\"mpunct\

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

Parameters

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

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

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

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

因子分解：假设每个span class=\"equation-text\" data-index=\"0\" data-equation=\

简化马尔可夫网

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

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

Markov Blanket （马尔可夫毯）

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

Independencies

markov

Graphs   markov network 

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

因子图

    能量函数

对数线性模型 

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

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

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

特征表示

Undirected graph

Factor graph

features

THREE DIFFERENT PARAMETERIZATIONS

度量马尔可夫随机场 MRF

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

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

过参数化

最早的马尔可夫网之一

ISING MODELS(伊辛模型）

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

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

CRFs

Add edges between X and all  

find minimal I-map

FROM DISTRIBUTIONS TO GRAPHS

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

BNS to MNS 

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

MNS to BNS

弦图

lecture&教材阅读

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

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

问题

part4 -Undirected Graphical Models

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

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

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

忽略了结构

CPDs的缺点

例子

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

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

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

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

 Deterministic CPDs

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

树CPD

tree CPD 对应的规则值；比如沿着span class=\"equation-text\" data-index=\"0\" data-equation=\

规则CPD

特定上下文CPD

The noisy-or model

Logistic CPD

应对连续变量的情况

Linear Gaussian CPD

Causal independence

CPDS类型

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

这张图没懂什么意思

问题

part5 -CPDs

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

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

markov Assumption.  

区别

Temporal models

DYNAMIC BAYESIAN NETWORKS

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

当给定t时刻状态的时候，O(t) 观测值与整个状态序列条件独立span class=\"equation-text\" data-index=\"0\" data-equation=\

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

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

例子：

典型的是隐马尔可夫

认为 有两个独立的假设

STATE OBSERVATION MODELS

 例子：追踪移动物体

KALMAN FILTERS

Temporal models

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

不同课程，会组合

LDA

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

Relation models

model类型

具体卡尔曼滤波器是什么

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

问题：

part6-Template -Based representations

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

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

 需要的操作次数 大于 

Key idea

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

乘法次数是

加法次数是

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

操作次数

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

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

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

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

是new factor after+  ，举例: span class=\"equation-text\" contenteditable=\"false\" data-index=\"1\" data-equation=\

span class=\"equation-text\" data-index=\"0\" data-equation=\"\\Psi\" contenteditable=\"false\

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

有证据的习题

无向图的习题

变量消元顺序习题举例

示例，消除T 

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

用图来表示变量消元

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

过程：

举例:

最少的邻居 num-neighbors

举例：

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

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

最终顺序

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

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

寻找最好的消元顺序

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

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

无关节点 in BNS

lecture&教材阅读

part7-VARIABLE ELIMINATION

对于给定的概率图模型，因子集为  ，变量集合为X。聚类图是定义在概率图模型之上的一个无向图，每一个节点i是变量集的子集聚类图必须满足组保持的性质，即每一个因子φ必须与一个节点 关联，使得因子φ中的随机变量为聚类图中节点中的随机变量的子集，即span class=\"equation-text\" data-index=\"3\" data-equation=\"Scope[φ]⊆ C_i\" contenteditable=\"false\

聚类图

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

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

执行交叉性质： 对于聚类图而言，如果对于任意的变量span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

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

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 (上一次传播过来的内容*本节点内的内容）



belief

part8 -junction tree algorithm

取样

变分推理

近似推理的两种方式

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

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

逻辑：

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

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

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

样本数量应该 =ln(2/\\delta)}{2e^{2}}\" contenteditable=\"false\"    其中  绝对误差    确保 的概率都在对应的误差内

=\\frac{3ln(2/\\delta)}{P(y)e^{2}}\" contenteditable=\"false\"  其中 e 相对误差    确保 的概率都在对应的误差内

方法：

前向采样（forward sampling） no evidence

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

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

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

Likelihood weighting  with evidence

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

Gibbs sampling

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

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

tips：

采样的分类

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

part9-sampling 

也就是先消元Z 求和

再寻找Y 求最大 

需要针对 Z 求和



边缘MAP  span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

P(A)P(B|A) 

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

sum-product algorithm or  max -product algorithm

part10-MAP INFERENCE

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

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

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

learning的动机

Assume the domain is governed by P*

n samples from P* 

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

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

独立同分布IID   Independent and identically distributed 

Parameters for a given structure 

Parameters and the structure of the network

learning

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

learning的原理

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

密度估计

具体的预测任务

知识发现

一般分类

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



熵：

相对熵可以将公式转化为

寻找最小的KLD 本质是寻找最大的span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"E_{p^{*}}[log(\\widetilde{P})]\

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

密度估计

分类，本质是求MAP

条件似然

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

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

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

寻找结构的挑战在于

知识发现

学习目标

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

目标函数（Quantifies our preferences over candidates）

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

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

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

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

学习优化

part11-Learning overview

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

overview

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

置信区间？

log likelihood 

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

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

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

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

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

贝叶斯网络的MLE

ML from BNs

maximum likelihood estimation

先验概率

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

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

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

关于 independence

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

如果假设关于span class=\"equation-text\" data-index=\"0\" data-equation=\"\\theta\" contenteditable=\"false\

也叫做拉普拉斯平滑

FACTORIZATION

mean= a/(a+b)

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

根据   ===>

BETA DISTRIBUTION

dirichlet distribution

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

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

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

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

k2 prior

实际上是假定了一个数字D，每个节点的超参数使用span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

BDE prior

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

忽略它

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

imputing

梯度优化

 =span class=\"equation-text\" data-index=\"1\" data-equation=\

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

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

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

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

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

往复、直到 收敛

是个迭代的过程

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

MISSING DATA

Bayesian estimation

Bayesian network

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

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

LOG-LINEAR MODELS ：span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

各自除以\\frac{1}{M} l(w:D)=\\sum_{i}w_{i}E_{D}[f_{i}(d_{i})]-lnZ\"

The log-likelihood is

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

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

由于f1只涉及A  所以 span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

本质上

实例：

最大化 来估计参数

  zero-mean Laplace distribution  L2 

 zero-mean diagonal Gaussian with equal variances L1      

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

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

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

L1 和L2 的区别？

Gradinet ascent 

MARKOV NETWORKS

part12-parameter ESTIMATION

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

需要真实分布的I等价

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

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

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

目标和难点：

Find minimal I-MAP 

Find all I-equivalent structures 

 + 

MI(mutual information) span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

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

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

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

数据很难真的独立  INDEPENDENCE TESTS

Constraint-based structure learning

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

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

 增加父节点会使得分属更高  因为 =I_p(X;Y)\"

最高分的图是完全图 

一种方式是限制图的深度

MAXIMUM LIKELIHOOD 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

likelihood score 自然满足

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

分数可以被分解

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

非常容易达到plateau

A tree-structured network 

如何寻找一个好的结构

BAYESIAN SCORE

SCORE-BASED APPROACHES

THREE APPROACHES

BAYESIAN NETWORKS

Assume H* is a P-Map for P* 

继续 用 mutual information for independence test

CONSTRAINT-BASED

SCORE-BASED

MARKOV NETWORK

part13-STRUCTURE LEARNING

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

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

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

假设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的最优策略。假设我们想知道某个策略和最优策略之间的差异，我们就可以用相对熵来衡量这两者之间的差异。即，相对熵 = 某个策略的交叉熵 - 信息熵（根据系统真实分布计算而得的信息熵，为最优策略)。

相对熵

交叉熵和相对熵的区别

闭式解也叫 解析解 analytical solution

闭式解（closed-form）

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

寻找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

无关节点

生成团树

团树传播计算

已知样本 D0 I0 S0 G2 L1

新的第一是求 ：P(D0| I0，S0，G2，L1）span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

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

= span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

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

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

Gibbs实例

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

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

参数估计 missingData EM算法

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

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

考试时候可能常用痛点

笔记正文

583 概率图模型