概率图模型-原理与技术 第二章 基础知识 习题与编程
概率图模型-原理与技术 总目录
- http://blog.csdn/icefire_tyh/article/details/54026071#t3
2.4 令P是 (Ω,S) 上的一个分布, α∈S 是满足 P(α)>0 的一个事件,条件概率 P(β|α) 表示对 β∈S 中每一个事件赋值。证明其满足定义2.1。
P(β|α)=P(β∩α)P(α)
由于P是
(Ω,S)
上的一个分布,所以
1.
由于β∩α∈S
,所以
P(β∩α)≥0
,且
P(α)>0
,所以
P(β|α)≥0
。
2.
P(Ω|α)=P(Ω∩α)P(α)=P(α)P(α)=1
3.假设
γ∩β=∅
,则
(γ∩α)∩(β∩α)=∅
所以
P(γ∪β|α)=P((γ∪β)∩α)P(α)=P((γ∩α)∩(β∩α))P(α)=P(γ∩α)+P(β∩α)P(α)=P(γ|α)+P(β|α)
2.7 证明2.1.4.3节讨论的条件独立性。
a.证明弱联合性和收缩性对任意概率分布有效。
b.证明相交性对任意正概率分布成立。
c.当P不是正分布时,为相交性提供一个反例。
a.
弱联合
(X⊥Y,W|Z)⇒(X⊥Y|Z,W)
当P(W)=0,W与任何随机变量独立。即
(X⊥Y,W|Z)⇒(X⊥Y|Z)⇒(X⊥Y|Z,W)
当P(W)>0,根据分解性
(X⊥Y,W|Z)⇒(X⊥W|Z)
即
P(X|Z)=P(X|Z,W)
由
(X⊥Y,W|Z)⇒P(X,Y,W|Z)=P(X|Z)P(Y,W|Z)
等式两边同时除以P(W|Z)
P(X,Y|Z,W)=P(X|Z)P(Y,W|Z,W)=P(X|Z,W)P(Y|Z,W)⇒(X⊥Y|Z,W)
收缩性
(X⊥W|Z,Y)∧(X⊥Y|Z)⇒(X⊥Y,W|Z)
(X⊥Y|Z)⇒P(X|Z)=P(X|Z,Y)
(X⊥W|Z,Y)⇒P(X,W|Z,Y)=P(X|Z,Y)P(W|Z,Y)=P(X|Z)P(W|Z,Y)
所以
P(X,Y,W|Z)=P(X,W|Z,Y)P(Y|Z)=P(X|Z)P(W|Z,Y)P(Y|Z)=P(X|Z)P(Y,W|Z)
b.
相交性
:对任意正分布,且互不相交的随机变量集合X,Y,Z,W,有
(X⊥Y|Z,W)∧(X⊥W|Z,Y)⇒(X⊥Y,W|Z)
由于是正分布,即不存在X,Y,Z,W取值使得概率或条件概率为0。
(X⊥Y|Z,W)⇒P(X|Z,W)=P(X|Z,Y,W)
(X⊥Y|Z,W)⇒P(X|Z,Y)=P(W|Z,Y,W)
所以
P(X|Z,Y)=P(X|Z,W)
两边同乘
P(Y|Z)P(W|Z)
,得
P(X,Y|Z)P(W|Z)=P(X,W|Z)P(Y|Z)
两边对Y累加得
P(X|Z)P(W|Z)=P(X,W|Z)⇒(X⊥W|Z)
由
(X⊥Y|Z,W)⇒P(X,Y|Z,W)=P(X|Z,W)P(Y|Z,W)=P(X|Z)P(Y|Z,W)
两边同乘
P(W|Z)
得
P(X,Y,W|Z)=P(X|Z)P(Y,W|Z)⇒(X⊥Y,W|Z)
c.暂无
2.12 证明期望的如下性质:令X是满足 P(X≥0)=1 的一个随机变量那么对任意 t≥0 ,有 P(X≥t)≤Ep[X]t 。
假设X是连续型变量
Ep[X]=∫∞0xf(x)dx=∫t0xf(x)dx+∫∞txf(x)dx≥∫t0xf(x)dx+t∫∞tf(x)dx
其中
t∫∞tf(x)dx=tP(X≥t)
所以
tP(X≥t)≤Ep[X]
,又因为t>0,所以有
P(X≥t)≤Ep[X]t
。
离散型变量同理。
2.15 加入对于任何 0≤a≤1 和任意x,y,有 f(ax+(1−a)y)≥af(x)+(1−a)f(y) ,那么这个函数f是凹函数。假如相反的条件成立,那么函数就是凸函数。证明连续可微的函数是一个凹函数,当且仅当对所有x, f′′(x)≤0 。
由
f′′(x)≤0
可以推出
f′(x)
在定义域上递减。做一个一般性限定,假设
x≤y
固定
y
,设
k′(x)=af′(ax+(1−a)y)−af′(x)(x≤y)
由于
x≤y,0≤a≤1
,
ax+(1−a)y≥x
又因为
f′(x)
在定义域上递减,
f′(ax+(1−a)y)≤f′(x)
即
k′(x)≤0
在
(x≤y)
成立,所以k(x)递减
k(y)=0
,所以
k(x)≥0
在
x≤y
成立
即
f(ax+(1−a)y)≥af(x)+(1−a)f(y)
成立。
2.21 考虑由为 P(x1)=p , P(x0)=1−p 的一个二元随机变量X的N个独立样本构成的序列。 SN 表示结果为 x1 的次数。
证明:
P(SN=r)≃exp[−N∗D((p,1−p)||(r/N,1−r/N))]
。
证明中会用到Stirling近似,阶乘为:
m!=2πm−−−−√mme−m
根据伯努利大数定律,设μ是n次独立试验中事件A发生的次数,且事件A在每次试验中发生的概率为p,则对任意正数ε,有公式:
limn→∞P(|μn−p|<ε)=1
。
由于当N很大时,单独计算一个位置的
P(SN)
都会是趋近于0的,所以在计算时采用比值的方式,即
P(SN=r)=P(SN=r)1=P(SN=r)P(SN=Np)
设μ=Np
所以
P(SN=r)=CrNpr(1−p)N−rCμNpμ(1−p)N−μ
其中
CrN=N!r!(N−r)!
,
CμN=N!μ!(N−μ)!
所以
P(SN=r)=μ!(N−μ)!pr(1−p)N−rr!(N−r)!pμ(1−p)N−μ
代入Stirling近似公式,且分子分母同除
NN
得:
P(SN=r)=μ(N−μ)r(N−r)−−−−−−√pr(1−p)N−r(rN)r(1−rN)N−r=e−(rln(rNp)+(N−r)ln(N−rN−Np)+ln...√)=e−N(rNln(rNp)+(1−rN)ln(N−rN−Np)+ln...√)
舍弃最后根号内的项,
P(SN=r)≈exp[−N∗D((r/N,1−r/N)||(p,1−p))]
和题目的结果求相对熵的顺序相反-
2.23 扩展拓扑排序算法,使其为PDAG的链分支寻找拓扑排序。
由于是无圈图,在遍历某一个节点无向边时,仅需要考虑这个新节点是否有父节点,而不需要考虑其父节点是否已经在集合中。
算法:生成PDAG的链分支拓扑排序
1.令所有节点未标记
2.初始化集合D={}
3.选择一个未被标记且其所有父节点已经被标记的节点p
5.D←p
6.遍历包含p的所有无向路径上节点pi
7.if pi有未被标记的父节点
8.D={}
9.任意选择一个pi的未被标记的父节点pf,D←pf
10.回到3
11.否则将D←pi
12.输出D回到2
13.直到所有节点被标记
输入
A C 1
C I 1
E I 1
H I 1
B E 1
C F 1
D G 1
F G 0
C D 0
D E 0
结果输出
['H']
['B']
['A']
['C', 'D', 'E']
['G', 'F']
['I']
参考代码
import random
class nodetype:
def __init__(self,n):
self.fathers=set()
self.children=set()
self.nodirect=set()
self.name=n
def solution_2_23():
#节点列表
node_list = []
#节点值得字典
name_map ={}
'''
输入格式
A C 1 表示A->C的有向边
C D 0 表示C--D的无向边
'''
file = open('p2-23-graph', 'r')
while 1:
line = file.readline()
if not line:
break
data = line.split()
if len(data)==3:
for i in [0,1]:
#查看当前节点值是否在字典中存在
index=name_map.get(data[i], -1)
if(index==-1):
node_list.append(nodetype(data[i]))
name_map[data[i]]=len(node_list)-1
data[i]=len(node_list)-1
else:
data[i]=index
#将每条边对应节点的父亲,儿子,无向节点集合更新
if int(data[2])==1:
node_list[data[0]].children.add(node_list[data[1]])
node_list[data[1]].fathers.add(node_list[data[0]])
else:
node_list[data[0]].nodirect.add(node_list[data[1]])
node_list[data[1]].nodirect.add(node_list[data[0]])
#未标记的节点集合
node_set=set(node_list)
#要输出的链分支
link_set=[]
#当还有未被标记的节点
while len(node_set)>0:
#选择一个没有未被标记父节点的节点
for node in node_set:
if len(node.fathers)==0:
tmp_node=[node]
break
#使用一个队列来实现遍历当前节点所能通过无向边到达的节点
i=0;
while len(tmp_node)>i:
for node in tmp_node[i].nodirect:
#如果过程中某个节点有未被标记的父节点,则清空集合
#再随机将其一个未被标记的父节点加入集合,重新开始遍历
if len(node.fathers):
tmp_node = random.sample(node.fathers, 1)
i=-1
break
#如果节点不在集合中,就加入集合
elif node not in tmp_node:
tmp_node.append(node)
i=i+1;
#将临时集合中的点对应的所有边删除
for node1 in tmp_node:
for node2 in node1.children:
node2.fathers.discard(node1)
for node2 in node1.nodirect:
node2.nodirect.discard(node1)
tmp_node=set(tmp_node)
#保存当前的链分支
link_set.append(tmp_node)
#从未标记集合中删除临时集合中的元素
node_set -= tmp_node
#输出节点的值
for nodes in link_set:
names=[]
for node in nodes:
names.append(node.name)
print(names)
solution_2_23()
更多推荐
概率图模型-原理与技术 第二章 基础知识 习题与编程
发布评论