PDF《马尔科夫逻辑网络》

有限的常数集为C = {c1,c2,...cn}. 马尔科夫逻辑网ML,C : ? L中的任意闭原子(ground atom)都对应了ML,C中的一个二值节点. 若此闭原子为真,则对应的二值节点取值为1;

若为假,则取值为0. ? L中的任意闭规则(ground formula)都对应着一个特征值.若此闭 规则为真,则对应的特征值为1;

若为假,则特征值为0.并且这个 特征值Fi的权重为二元项中该规则对应的权重wi. 一个例子 ? 学生的智商(Intelligence)影响了他的SAT成绩;

? 而考题难度(Difficulty)和智商共同决定影响了他的平时成 绩(Grade);

? 平时成绩和SAT影响到他能不能拿到导师的推荐信(Letter);

? 两个成绩和推荐信又影响到他能不能找到工作(Job) ;

? 有没有工作决定了他是不是快乐(Happy). 给出上述例子的MLN 另一个例子 ? 某单位有一个健身房,所有员工都有权利去健身;

? 有两个同事是好朋友,那么他们有很大的概率(w=3)一起 去健身或者不一起去健身;

? 如果一个员工整天去健身,那么他/她有较高的概率(w=2) 被炒鱿鱼. 基于一阶逻辑的知识表示 ? 某单位有一个健身房,所有员工都有权利去健身;

? 有两个同事是好朋友,那么他们有很大的概率(w=3)一起 去健身或者不一起去健身;

? 如果一个员工整天去健身,那么他/她有较高的概率(w=2) 被炒鱿鱼. 需要同时满足! Friends(A, A) Friends(B, B) Friends(A, B) Friends(B, A) Plays(A) Plays(B) Constants: Alice (A) and Bob (B) Friends(A, A) Friends(B, B) Friends(A, B) Friends(B, A) Plays(A) Plays(B) Fired(B) Fired(A) Plays(A) Plays(B) 那么请问Alice和Bob是朋友,他们都整天去健身,而且他们都没有被炒鱿鱼的 可能性? Friends(A, A) Friends(B, B) Friends(A, B) Friends(B, A) Plays(A) Plays(B) Fired(B) Fired(A) Friends(x,y) Plays(x) Plays(y) w T T T

3 T F T

0 F T T

3 F F T

3 T T F

0 T F F

3 F T F

3 F F F

3 Friends(A, A) Friends(B, B) Friends(A, B) Friends(B, A) Plays(A) Plays(B) Fired(B) Fired(A) Friends(A, A) Friends(B, B) Friends(A, B) Friends(B, A) Plays(A) Plays(B) Fired(B) Fired(A) Friends(A, A) Friends(B, B) Friends(A, B) Friends(B, A) Plays(A) Plays(B) Fired(B) Fired(A) Plays(x) Fired(x) w T T

2 T F

0 F T

2 F F

2 问题1:那么请问Alice和Bob是朋友,他们都整天去健身,而且他们都没有被炒鱿鱼 的可能性? ? ni(x)是Fi在X中所有取真值的公式的数量 ? 而x{i}是Fi中为真的原子 问题1:那么请问Alice和Bob是朋友,他们都整天去健身,而且他们都没有被炒鱿鱼 的可能性? Friends(A,B) Plays(A) Plays(B) ω True True True

3 Friends(x,x) Plays(x) ω True True

3 Plays(x) Fired(x) ω True False

0 Friends(A,A) =1 Friends(B,B) =1 Friends(A,B) =1 Friends(B,A) =1 Plays(A)=1 Plays(B)=1 Fired(B)=0 Fired(A)=0 MLN特例:一阶逻辑 ? 只有一条规则 ?x R(x)? S(x)、权重为w,常数集C = {A} ? 只有4个事件 {? R(A),? S(A)},{? R(A),S(A)},{R(A),? S(A)},{R(A),S(A)} P({R(A),? S(A)})=1/(3ew+1) 其他均为 ew /(3ew+1) 马尔科夫网推理 MLN推理 ? 条件概率查询(Conditional Probability Query) ? 证据:? = ? ? ? 查询:变量?的子集 ? 计算:? ? ? = ? ? ? 最大化后验(Maximum a Posterior, MAP) ? 证据: ? = ? ? ? 查询:所有其他变量?(? = ?1, ?2, … , ?? ? ?) ? 计算: MAP ? ? = ? ? = argmax ? ? ? ? = ? ? ? = ? ? BN中的和积(Sum-Product) MN中的和积(Sum-Product) 证据:Reduced Factors 证据:Reduced Factors 证据:Reduced Factors 变量消除算法 算法 ? 精确算法 ? 变量消除(Variable elimination) ? 近似算法 ? 信念传播(Belief propagation) ? 随机采样(Random sampling) ? Markov chain ? Gibbs sampling 变量消除算法 ? 基本思想 ? 为得到精确解,必须计算和积 ? 通常一个变量不会出现在所有的因子中 变量消除算法 变量消除算法 图模型中的变量消除 图模型中的变量消除 图模型中的变量消除 图模型中的变量消除 带证据的变量消除 重复继续…… 带证据的变量消除 MN中的变量消除 归一化…… 变量消除算法 ? 基本思想 ? 根据给定的证据,得出需要约简的因子集Φ ? 对每一个非查询的变量X,将其从Φ消除 ? 连乘所有余下的因子 ? 正则化…… 变量消除算法 ? 小结 ? 对BN和MN均有效 ? BN中计算的是条件概率分布 ? MN中计算的是势函数 ? 任何一种消除次序都可以导致正确的结果 ? 计算复杂性NP-hard…… 思考和讨论 1. 变量消除算法的计算复杂度分析? 2. 如何设计有效的变量消除次序? 3. MLN与一阶谓词逻辑的关系? 4. MLN与BN的异同和联系? 实验 1. ……. 要求:可以用任何语言,需要有日志说明搜索路径,实验报告分析效率 和启发式函数设计.*月**日前发给助教,检查. 作业提交到公共