王珏-结构+平均-读Daphne_Koller的“概率图模型”.ppt

结构 平均 读DaphneKoller的 概率图模型 王珏 中国科学院自动化研究所模式识别国家重点实验室2011年4月7日 一 引子二 表示三 推断四 学习五 结束语 讲座分为五个部分 开头一个引子 说明讲座的动机 最后一个结束语 从历史发展的角度讨论关注概率图模型的原因 中间三个部分 介绍Koller这本书的三个部分 表示 representation 推断 inference 和学习 learning 的基本思想和主要方法 标题 AI与ML 采用 结构 平均 作为标题 没有使用 结构 统计 或者 人工智能 统计学 或 图 概率 结构 与 统计 似乎不具有同等地位 人工智能 与 统计学 水火不相容 图 概率 直观确切 其本质对应 结构 与 平均 对中文 结构 平均 更美一些 思考 人工智能 AI 与统计机器学习 ML 是否存在一个结合点 但是 在理念上 AI强调因果率 结构 不惜对排中率破缺 统计方法强调排中率 不惜对因果率破缺 两者水火不相容 鉴于两者均已遇到根本性困难 有没有一种折衷的理念 Koller这本书应该是这种折中的理念 极端的例子 对任意三角形识别 最简单的图形 如果采用句法 单纯结构 方法 需要 上下文敏感文法 描述 没有Parsing算法 成都地区暴雨预报 十年的数据 神经网络 平均 获得模型 验证 误报5 误报中有一个样本 预报大暴雨 实际是晴天 各种因素均说明有暴雨 但是 单纯结构或单纯平均需要满足严厉的条件 否则无效 湿度指标低 没有水 当然没有暴雨 平均将这个重要指标与其他指标一起平均了 小学生不会犯的差错 80年代末 书中 学生 的例子 课程 D 难 0 易 1 智力 I 聪明 0 一般 1 考试 G A B C SAT S 好 0 坏 1 推荐 L 强 0 弱 1 以推荐作为查询变量 L If D 0 G A then L 0 If I 0 G A then L 0 If D 1 I 1 G A then L 1 问题是 If D 1 I 0 G A then L 这就是人工智能遇到的难题 无法泛化 不同查询 不同规则 构造一个函数 L f D I G S 观察一组学生 获得样本集 基函数L 1D 2I 3G 4S设计算法 确定 获得模型 问题 模型为真需要多少样本 对高维数据 不知道 模型不可解释 这就是统计机器学习遇到的难题 可以泛化 精度未知 不可解释 根据观察和专家经验 构造规则集 问题本身的语义 课程难易程度与考试分数有关 学生智力与考试成绩有关 学生智力与SAT有关 考试成绩与 推荐信强弱 有关 AI方案充分考虑了这种语义 但是 将这种语义强化到唯一表示程度 当且仅当 缺失灵活性 统计学习方案完全不考虑这种语义 尽管具有灵活性 泛化 但是 需要充分的观察样本 两者的共同代价是 维数灾难 前者 需要考虑所有可能的组合的规则集合 后者 需要考虑充分的样本集合 这种语义可以根据统计分布获得 也可以根据常识经验获得 ML强调给定变量集合张成的空间上计算平均的方法 抹煞变量之间的结构 AI强调变量的独立性 忽视变量之间的条件独立关系 是否可将变量子集 甚至一个变量 的局部分布 根据变量之间内在的结构 转变为对变量集合整体的联合分布 这样 就可以既顾及了变量之间存在结构 又考虑了平均的必要性 概率图模型应该是一个这样的方案 这本著作包罗万象 1200页 这个讲座是根据我个人偏好 抽出最基本的思考 研究方法 以及实现这个思考的基本理论 而书中罗列的大量具体的方法则认为 不是解决问题的唯一途径 而是存在的问题 这本著作数学符号体系繁杂 谈不上 优美 著作有四个部分 表示 推断 学习和actionanddecision 我们只讨论前三个部分 致谢 在我准备这个 笔记 之前 王飞跃 宗成庆和我的12个学生参加了我们的一个讨论班 大家一起通读了Koller的这本书 这个讨论班对我准备这个 笔记 有很大的帮助 这些学生是 王飞跃教授的学生 顾原 周建英 陈诚和李泊 宗成庆教授的学生 庄涛和夏睿 我的学生韩彦军 马奎俊 孙正雅 黄羿衡和吴蕾 以及吴高巍博士 在此表示谢意 特别感谢韩素青和韩彦军帮助我检查和修改了全部ppt 一 引子二 表示三 推断四 学习五 结束语 为什么 表示 是一个专题 统计机器学习的表示 基函数 确定基函数 没有表示问题 给定变量集 完全图或完全不连接 平凡 图的结构 不完全连接 统计上条件独立 因子 条件独立的集合 I map 成为图结构的表征 联合分布与边缘分布是图结构的概率描述 不完全图 条件独立 两种表示 非平凡 概率图模型 Bayes网 BayesianNetwork BN 有向图 Markov网 MarkovNetwork MN 无向图 各种局部概率模型 CPD 从联合分布构造Bayes网 BN 学生问题 五个变量排成一个任意的序 I D G L S 其联合分布 左 对应的完全BN 右 P I D G S L difficulty Intelligence Grade SAT Letter P I P S I D G L P D I P G I D P L I D G 构造Bayes网 因子 完全图 节点G上的条件概率分布 CPD 图上的独立性 P I D G L S P I P D I P G I D P L I D G P S I D G L P I P D I与D相互独立 L只与G有关 与其他独立 P G I D P L G S只与I有关 与其他独立 P S I 分布P中的条件独立 P X 是随机变量集X中所有变量的联合分布 P Xi Z 是Xi关于Z的条件分布 Z X Xi X且Xi Z 条件独立 如果两个变量Xi Xj X 对条件Z独立 iffP XiXj Z P Xi Z P Xj Z 满足条件独立的所有断言 Xi Xj Z 构成一个集合 称为关于P的I map 记为I P 对图G 所有彼此不相连的节点对集合为I G 如果I G I P G是一个对独立集合I P 的I map BN上的独立 Y Z X Y Z X a d 绝对独立 X Z d Y Z X c Y X Z b Y Z X e 复杂的图可以考虑为由一些三个节点简单图构成 令X Y与Z三个节点 学生例子 X 智力 Z 推荐信 Y 成绩 a b Y未被观察 成绩未知 从学生聪明X 推断学生分数高Y 可能强推荐 Y已被观察 Z只与Y有关 与X独立 X Z Y c Y未被观察 从X可能推断Z Y已被观察 两者独立 e 如何 复杂 v 结构 e X Y Z 成绩Y优秀 如果课程X困难 可以推出智力Z聪明 这样 X与Z相关 如果Y未知 X和Z独立 这个结构称为v 结构 G是BN 存在三个节点X Y Z X与Z是独立 则 1 对v 结构 Y与它的全部子孙是未被观察 e 2 Y已被观察 a b c BN最麻烦的是v 结构 用树结构近似BN 就是删除v 结构 这时 BN上 两个节点之间没有连线 它们一定独立 Y Z X BN上判定独立的规则 不满足条件 只能说不能保证独立 因子化 factorization 链式规则 P D I G S L P I P D P G I D P L G P S I 满足条件独立假设的链式规则一般形式 令PaX是图G上变量X的所有父结点 变量集合的联合分布可以表示为 P X1 Xn P Xi PaXi 其中P Xi PaXi 称为因子 定理 如果图G是一个对I P 的I map 则P可以根据G因子化 注意 因子的定义 满足条件独立假设 逆定理成立 注意 仅是因子化 而不是任意P可以使用G描述 I G I P 最小map 分布的结构 就是将所有 独立 的边移除的图 最小map 令G是一个对I P 的最小I map 如果它是对I P 的I map 且从G上移除任何一个单边 它将不再是I map 不在I P 中 如果G是一个最小 map 我们似乎可以从中读出分布的所有结构 即 从图上读出P的所有独立I P 由于图的生成依赖变量序 即 不同的变量序将导致不同的图 而不同的图 可以分别具有最小I map 具有不同的结构 没有唯一性 这个结论不成立 P map perfect P map 如果I G I P G是一个P map 意义 对任何一个P 是否保证存在一个G的P map 对P A C B D 与 B D A C 存在使得A与C B与D不相连接的BN 考察 B D A C 考察 A C B D 考察 A C B D A C B A B C是 b 如果B已知 成立 A C D A D C是 b 如果D已知 成立 B D A D A B是 c A已知 成立 B D C D C B v 结构 C已知 B与D不独立 B D C 不成立 B D A C 不成立 A C B D 成立 C D A c类 D已知 A C C B A B已知 A C D C B v C已知 D B 不成立 回答是不能保证 概率图模型 Bayes网 BayesianNetwork BN 有向图 Markov网 MarkovNetwork MN 无向图 各种局部概率模型 CPD Markov网 MN 尽管MN 无向图 以完全子图的因子为基础 但是 MN上的完全子图依赖条件独立 因为节点之间连线的删除 将直接导致不同的完全子图 因子是一个从变量D子集到正实数域 上的映射 函数 表示联合分布与因子 其中 Di i 1 k 是MNH上的完全子图 典型是clique 1 D1 k Dk 称为分布P 的因子集合 1 D1 k Dk 满足 P称为Gibbs分布 Z称为划分函数 与BN比较 联合分布是对完全子图势能的平均 计算Clique 最大完全子图 是NPC 势能函数 C A D B I map与因子化 I map I P 是在P中形如 X Y Z 独立的集合 与BN定义一致 MN与BN一样 有一个关于因子化的定理 BN MN 令P 0 G是一个P的I map iffP可被因子化为 令P 0 H是一个P的I map iffP可被因子化为 完全子图的势函数 注意 G 或H 是一个P的I map就是I G I P 偶对 独立 IP H X Y U X Y X Y H 意味着 不连接的偶对节点在其他节点条件下相互独立 A D B C E B C A D E D E A B C D A B C E Blanket独立 这是 偶对 独立的推广 令B X 是节点X在H MN 的所有直接邻居节点集合 IL H X U X B X B X X H 意味着 X在所有直接邻居条件下 与其他节点独立 对节点B B B A D E B与C是Blanket独立 独立形式与构图方法 d 分离 在任意节点x X与y Y通路上 存在一个节点Z已知 在Z下 其他节点相互独立 I P D A C B 偶对 不连接的偶对独立 IP P IP H X Y U X Y X Y H A D B C E Blanket 对X的所有直接邻居 X与其他节点独立 IL P 节点B B B A D E 与C是Blanket独立 IP P IL P I P 如果P 0 正分布 则IP P IL P I P 构图方法 偶对或Blanket 构成的MN 均是唯一最小I map BN的Moral图 BN MN G是BN的Moral图是一个无向图 对两个节点X与Y满足 1 G中 连接的节点保持连接 2 G中 X与Y有共同子孙 X与Y连接 v 结构 BN BN的Moral图 v 结构 D K I 如果K未被观察 D与I独立 K以被观察 D和I就相关 相连 概率图模型 Bayes网 BayesianNetwork BN 有向图 Markov网 MarkovNetwork MN 无向图 各种局部概率模型 各种CPD 局部概率模型 讨论了网络的结构之后 需要关注附加在节点 边 上的各种不同描述的条件 局部 概率分布 CPD 如何确定因子 满足 P x paX 1 各种CPD TabularCPD 使用表描述P X PaX 0 判定CPD 判定函数 LogisticCPD 线性高斯CPD 树与规则CPD 网图有两个要素 其一 网图的结构 其二 网图节点上的条件概率分布 在学习时 这两个要素将成为学习的两个方面 结构可以由经验来构造 对节点上的概率分布的学习 将基于这些CPD表示形式 可以理解为学习的 基函数 局部表示 经验知识可以无障碍地被引入 一 引子二 表示三 推断四 学习五 结束语 查询问题 基于图的推断 概率查询 Y边缘 根据给定图 计算P Y E e 其中 E是证据变量 Y是查询变量 读为 在证据e条件下 Y出现的概率 边缘概率 MAP查询 计算MAP W e argmaxwP w e 其中 W E 读为 在证据e条件下 在W中求出最适合的赋值 边缘MAP查询 令Z Y E 计算MAP Y e argmaxYP Y Z e 边缘查询 基于图的推断 边缘查询原理 1 根据BN 计算联合分布P P Xi PaXi 2 计算在E下 变量Y的边缘分布 P Y E X Y EP 这个貌似简单的任务 由于计算边缘分布需要取遍非查询变量所有值的组合 十分困难 学生聪明i1 不高兴h0 BN下 查询学生工作机会 P J i1 h0 变量集合 C D I G S L J H 根据BN 计算联合分布P 在证据E下的J的边缘分布 P J i1 h0 WP W J H I 精确推断是NPC 无论BN还是MN 其上的推断是NPC问题 计算近似推断也不能幸免 近似推断 图近似 本质近似 目标近似和计算近似 包括算法近似 概率图模型推断研究的焦点是 精度和效率之间有效折中 推断 问题的解法 提取公因子 以避免变量的重复计算 空间换时间 折中 动态规划 动态规划 Clique树法 优化法 以相对熵为目标 多种方法之一 将概率查询变为有约束的优化问题 并使用拉格朗日乘子法求解 将无向图构成clique树 采用消息传播的方法 计算查询的分布 对图上任何节点的查询有效 BN变量消去法 计算P D BN网 A B C D 对D的边缘分布 P D C B AP A P B A P C B P D C 1 P D CP D C BP C B AP A P B A 2 令 1 A B P A P B A 1 B A 1 A B 消去A 3 计算 2 B C 1 B P C B 2 C B 2 B C 消去B 最后 计算出P D 联合分布 P A B C D P A P B A P C B P D C MN变量消去法 因子边缘化 对BN 条件概率P X Y 为因子 在MN中 因子 X Y 尽管图结构不同 有向vs 无向 但是 在变量消去法上 没有本质区别 称为因子边缘化 P D C B A A B C D 满足交换律和结合律 C B C D A A B C D B C A A B 其中 Z X Y A B C 即 从变量集合中删除查询变量的变量集合 是因子集合 Z 是和积形式 它是从联合分布计算边缘分布的基本形式 推断 问题的解法 提取公因子 以避免变量的重复计算 空间换时间 折中 动态规划 动态规划 Clique树法 将无向图构成clique树 采用消息传播的方法 计算查询的分布 对图上任何节点的查询有效 Clique树 2与4有G 通路上3 5也有 2 4构成cluster图上的一个通路 注意 边是有向的 所有cluster的消息流向一个cluster 7 计算出最后结果 其称为根 满足RIP的cluster图称为clique树 Ci与Cj是cluster图上一通路的两个cluster 至少存在一个变量X 使得X Ci且X Cj 如果这个通路上的所有cluster均将包含X 称其满足 RIP RunningIntersectionProperty 一条通路满足RIP 将保证这条通路均有某个变量 同时 构成的cluster图与MN具有相同的连接形式 拓扑结构 Clique树 基于clique树的变量消去法 1 C1 根据 C 1 C D 消去C 并将其作为消息 1 2 D 送到C2 2 C2 2 G D I 1 2 D 2 G D I 消去D 2 3 G I 送到C3 3 C3 3 G S I 2 3 G I 3 G S I 消去I 3 5 G I 送到C5 4 C4 H 4 H G J 消去H 送消息 4 5 G J 到C5 5 C5 5 G J S L 3 5 G S 4 5 G J 5 G J S L 5 P G J L S 是联合分布 求P J 只需计算 G L S 5 C 是初始势能 对BN C D P C P D C 注意 消息 2 3 G I D 2 G D I Clique变量消去算法 消息传播 1 每个cliqueCj赋予初始势能 每个因子对应一个clique 2 计算Cj的邻居Ci向其传播消息 总计为 3 计算根节点的信度 计算联合分布 方法的优点 设定不同根节点 可以计算任意变量的边缘分布P C 改变根节点只涉及个别消息传播 对传入多个消息的clique也是如此 4 计算查询变量的边缘分布 消元步骤 i 被校准的Clique树 图近似 Clique树的主要问题之一是消息 i k k i可能不成立 满足右式的两个clusterC1与C2 称为被校准 Clique树上所有cluster是被校准 这个树称为被校准的clique树 这样 连接两个节点的信度定义为 被校准的clique树是联合分布的替代表示 被校准clique树的联合分布 Gibbs 其中 将 与 代入上式 分子 分母 因为每个 在分子分母只出现一次 可以消去 联合分布为各个clique初始能量的乘积 意义 Clique树可以作为联合分布的替代表示 但需假设校准成立 近似 推断 问题的解法 提取公因子 以避免变量的重复计算 空间换时间 折中 动态规划 动态规划 Clique树法 优化法 将无向图构成clique树 采用消息传播的方法 计算查询的分布 对图上任何节点的查询有效 以相对熵为目标 多种方法之一 将概率查询变为有约束的优化问题 并使用拉格朗日乘子法求解 1 变量消去法与clique树消去法等价 2 后者可以同时获得多个查询结果 且与变量序无关 校准条件 基于优化的推断 P与Q分别是精确推断与优化推断 使得Q与P的距离最小 三个步骤 1 距离 2 图结构的目标函数和约束函数 3 求解优化问题 优化推断分为优化精确推断和优化近似推断 前者是目标和约束空间精确 后者是两者至少存在一个非精确 目标 相对熵最小 能量泛函最大 相对熵 注意 取对数 令能量泛函 代入相对熵 计算一个Q使得其与精确推断P 的相对熵最小 由于lnZ与Q无关 这样 以相对熵最小的目标可以使用能量泛函最大代替 由此 优化变为计算能量泛函最大的Q 其中X为所有变量的集合 Q是P 的近似 Clique树的因子能量泛函 上述泛函涉及所有变量的联合分布 不易设计优化算法 Clique树使用因子能量泛函 定义为 初始势能与传递的能量 消息 Clique树节点Ci的固有势能的期望 Clique树分布 传递的能量 的对数形式 是信度 节点 cluster 上的信息 是i与j传递的所有消息 边上的信息 这是研究校准clique树的原因之一 Clique树的约束精确优化推断 计算 使得 最大 对约束 是信度 节点 是i与j传递的所有消息 边上 Q是节点和边上信息的并集 即 消息的网图上的传播 基于clique树的优化推断算法 使用拉格朗日乘子 将上述约束变为下述方程的优化问题 以后类似感知机算法的推导 对 与 计算偏导 获得下式 这是一个迭代式 据此 可以设计优化精确推断的算法 基于优化的近似推断 一般地说 基于优化的近似推理的直接考虑是两个近似因素 其一 目标函数 其二 约束空间 但是 其关键是 表示问题的图结构 如果为了计算等原因 使用了一种近似表示的图结构 这类图将更容易构造 相对精确描述 其目标函数和约束空间是近似的 Cluster图 采用消息传播方法的前提 其一 图结构是树 其二 满足RIP Cluster图放弃条件1 不要求树 但需要满足被扩展的RIP 被扩展的RIP 如果存在一个变量X 使得X Ci且X Cj 则 在Ci与Cj之间 存在一个单一的通路 在这个通路的所有边e上 包含这个变量 X Se 关键 对一个变量 两个clusters之间只有一个单一通路 例如 3与2之间 对变量B 3 4 2与3 4 1 2两个通路 如果1与2的边上是B 就不满足扩展RIP 这是对图结构的约束 构造cluster图 对Cluster图近似 不同的图可能导致完全不同的解答 这样 就存在一个选择哪个cluster图的问题 一般的原则是在高效计算和精度之间的折中 左图是一个问题的两个Cluster图 差别在于 上图的4 2连线在下图不存在 在1 2连线上的变量下图从C变为 B C 几种构图的方法 动机是容易处理 但不能违反RIP 1 偶对MN 2 BetheCluster图 构造 偶对 Pairwise MN 这类图有两类cluster 其一 单变量势能 i Xi 其二 变量偶对势能 i j Xi Xj 后者可以理解为cluster边上的势能 ClusterCi与Cj对应单变量Xi与Xj clusterC i j Xi Xj 对应Xi Xj边 可以证明 偶对MN 是cluster图 这样 这个图就可以使用消息传播的方式求解推断 对MN 构造容易 BetheCluster图 这类图有两层 其一 大 cluster 是表现MN结构的因子 Cluster或clique 其二 小 cluster 是单变量 大 cluster包含的变量与对应 小 变量cluster使用边连接 可以证明 这个图也是cluster图 可以使用消息传播方法求解推断 这类图容易构造 Cluster图的优化推断算法 事实上 对cluster图 因子能量泛函也不能优化成精确解 理由 1 对边缘分布构成的多面体 每个cluster信度 不一定在这个多面体上 信度是对边缘分布的近似 2 判定信度集合是否在多面体上是NP难解 优化从多面体上变为局部一致 定义如下 多面体上 伪边缘 Cluster图的优化 以下使用拉格朗日乘子推出具体算法 步骤如前 与clique树优化约束的形式完全一样 其区别仅在 与 的作用域 clique是在clique树上 这个约束是在图的一个局部U上 在图结构下推断的本质是 计算查询变量的边缘分布 P 关键是 是计算所有非查询变量取值的全组合 这个看似简单的问题 其复杂性远远超过我们的想象 总结 近似推断主要涉及三类近似的方法 1 研究对图结构描述的近似 这是本质近似 2 研究对目标函数的近似 对给定图结构的近似 3 研究计算近似算法 精确算法无效 计算近似 概率图模型近似推断核心是 精度和效率 的折中 归根结底是表示的研究 BN如何直接使用各种近似 三类近似没有一个容易 特别是其误差性质 除了计算近似之外 并没有本质进展 相当复杂 遍地问题 一 引子二 表示三 推断四 学习五 结束语 概率图模型学习任务 假设 给定结构且样本是完整 所有变量被赋值 的 任务 学习参数 参数估计 CPD方法 1 最大似然估计 2 Bayes预测 假设 结构未知 但是 样本完整 任务 学习结构和参数 考虑一个可能结构的假设空间 结构选择变为优化问题 假设 样本不完整 或某些变量未知 任务 发现非显现表现的变量 知识发现 对BN 工具 最大似然和Bayes估计 特点 从局部到整体的学习 困难 鲁棒性 泛化 对MN 工具 最大似然 Bayes估计 迭代优化特点 鲁棒性 泛化 困难 整体的划分函数和推断 BN的学习 目标函数 学习就是计算使得L D 最大的 似然函数 数据集合D BN的参数 或 与 图G的似然函数L D 其中 可以是参数 给定BN结构 或者是 学习结构 学习就是计算使得P D 最大的 由于后验概率依赖先验概率与似然函数 问题变为计算这两个函数的问题 Bayes预测 数据集合D BN的参数 或图G的后验概率 P D 其中 可以是参数 给定BN结构 或者是图G 学习结构 BN的似然函数 假设BN结构给定 任务是确定参数 令Xi是给定BN上的一个节点 变量 其父辈节点集合为Pai Xi的CPD 因子 为P Xi PaXi 给定数据集合D P Xi PaXi 对D的似然 其中 xi m 是D中变量X的第m个样本的值 对给定样本集合 给定BN的似然为 基于MLE的学习算法 命题 令D是对变量X1 Xn的完全数据集合 G是定义在这个变量集合上的BN 令是使得最大的参数 则使得L D 最大 意义 满足一定假设 BN的整体最大似然 可以从局部最大似然获得 学习算法 对BN的每个节点 在其父辈的条件下 根据数据集合 分别计算这个节点的最大似然 即 根据上述命题 即可获得最后解答 BN的Bayes预测学习 任务 计算后验概率分布P D 仅需计算似然函数P D 和先验概率分布P Bayes预测学习就是计算这两个函数 给定BN 参数考虑为随机变量 表述为分布函数 似然函数 对样本逐一计算 根据当前参数 修正参数 预测 先验分布函数 希望先验与后验表示形式相同 Dirichlet分布 对BN的预测学习 关键是需要将整体分布分解为局部分布 其中 似然计算 似然函数P D 的计算采用预测新样本的分布 给定BN 从DM获得参数 的分布 对新的观察x M 1 可以使用链式规则 其中DM是数据集合D中 前M个样本构成的集合 DM M 对x M 1 独立 这暗示 从样本集学习参数 可以一个一个样本逐步进行 预测x M 1 变为 根据后验 对所有参数平均 期望 先验分布P 的选择 Dirichlet分布 满足先验概率与后验概率形式一致的要求 k 样本k值出现频率 优点一 形式一致且紧凑 修改参数容易 后验 P x M 1 xk D EP D k 对Dirichlet分布 E k k j j 优点二 新参数是基于对已有参数的平均 这避免某个参数过学习的误差 带到新参数的估计 学习MN 对学习而言 MN与BN的区别是 MN的平均是在图结构整体上 划分函数Z 与图结构的所有参数相关联 不能分解 由此 不得不使用迭代的优化方法 好消息 似然函数能够保证收敛到全局最优 坏消息 每次迭代需要推断 注释 对图结构 BN学习依赖数据集合分布P D 由于D是给定的 因此 BN可以分解为部分求解 删除任何条件独立的边 对MN则依赖划分函数 Z 1 X1 k Xk 这意味着 改变任何一个势函数 j Z将改变 分解为局部是不可能的 这是MN不得不求助优化的原因 MN的似然函数 MN已知 并表示为 将 写成权值和特征函数的形式 i Di ifi Di 似然函数为 其中 是表示变量关系的势函数 这里的Di表示 i涉及的变量观测 在MN上的完全子图 取对数 注意 在特征函数中 zeta 表示第m个样本中与f有关变量的数值 这恰恰反映了MN的结构 方括号内是M个样本 MN参数估计算法 对数似然函数 为了计算最大似然 对 求导 并令其为0 右边第1项是对所有样本的平均 经验 第2项是对参数 的平均 期望 如果 是最大似然参数 iff对所有i ED fi E fi 学习结构 对一个由变量集合构成的图结构 有两个极端情况 平凡 所有变量两两相连 所有变量不相连接 学习 部分相连 A B E C D 目标 1 根据给定数据集发现变量之间的关系 知识发现 2 密度估计 其本质是泛化 加边 删边 核心 从数据集发现变量之间的独立关系I map 困难 1 噪音 没有绝对独立 2 稀疏解答 结构学习的基本方法 1 假设空间的模型选择 设计一个图结构对给定数据集合符合程度的评分准则 2 Bayes模型平均 有些类似Bagging 假设空间 模型选择的学习 假设空间 待选的图模型 评分函数间接描述假设空间 评分函数 模型复杂程度和对给定数据集合的符合程度 评分函数 似然评分函数 Bayes评分函数 似然评分函数 令G是一个待选的图结构 G是这个图结构上的参数 对给定数据集合D 关于G与 G的似然函数 L D 目标 从待选的图模型中选择似然最大的图模型 结构和参数 似然评分函数 其中l是MLE参数下 对G的似然函数的对数形式 Bayes评分函数 与MLE的考虑类似 只是计算给定数据集合的图结构G的后验概率 给定数据集合D G表示图结构 计算G的后验概率 Bayes评分函数 scoreB G D logP D G logP G 其中似然函数 第一项就是似然评分 Bayes评分就是增加了第二项 以使得我们获得更稀疏的图模型 MN结构学习 MN结构未知 与BN研究方法一样 考虑 1 假设空间 2 目标函数 评分函数 3 优化算法 假设空间的形式 其中 M是一个对数线性结构模型 任务就是根据给定样本集合 选择一个结构稀疏的MN模型 评分函数 缺点 偏爱结构复杂的模型 需要限制 例如 如果 M1 M2 scoreL M1 D scoreL M2 D 这个限制太严厉 大多数情况难以满足 似然评分函数 其中 dim是模型的维数 参数空间的自由度 缺点是这个维数很难估计 Bayes评分函数 BN的优点是它的因子形式P X PaX 这意味着 计算任何节点的分布 只与它的父辈有关 而与其它节点无关 然而 这也是它的最大缺点 即 每个节点分布的计算必须准确 否则误差将被传递 总结 MN的优点是它的因子形式与划分函数Z有关 这意味着 节点分布的误差 可以被整体平均消除 然而 这也是它的最大缺点 使得学习结构与参数不得不与推断相关联 一 引子二 表示三 推断四 学习五 结束语 读 表示 耳目一新 概率图模型表示的核心问题是 条件独立 其中 条件 是关键 在传统统计学中 独立往往是假设 这个假设满足 研究简化 但是 不会将其作为核心研究课题 条件概率分布 CPD 因子与图结构对应 这样图结构上条件独立断言集合I map成为描述模型的标志和关键 经验知识 无论有向图还是无向图 局部概率模型 即 CPD 通过图结构整合为整体概率模型 这是最有吸引力的思考 而CPD的描述可以多种多样 传统统计模型 传统人工智能模型 既可泛化又可解释的模型 望眼欲穿 结构 平均 读 推断 扼腕叹息 对问题使用带有复杂结构的表示 其推断就一定是一个复杂课题 AI就是如此 定理证明 而ML由于使用简洁的基函数作为表示 例如 多项式基 因此 推断不会是其研究的问题 概率图模型的麻烦就在于推断 无论精确推断还是计算近似推断 图模型上的推断均是NPC 近似图结构 近似目标函数和近似优化算法等近似被采用 全面近似 然而 从近似程度到有效计算 遍地问题 NPC 当头一棒 没有免费的午餐 与AI和ML相比较 这类模型的推断灵活 对不同查询 无需重新建模 读 学习 喜忧参半 给定图结构的学习没有什么新的考虑 基于表示的研究 从给定结构派生似然函数或Bayes后验概率函数没有困难 计算优化解将遇到推断的困难 从给定数据学习结构就不是一件轻松的事情了 这类问题的可分解性需要严厉的条件 计算考虑迭代 遇到推断 大麻烦 由于划分函数的整体性 MN一开始就遇到推断 图近似是关键 绕不开的推断 五味俱全 机会乎 陷阱乎 预测与描述 预测与描述是数据挖掘提出的两个任务 但是 数据挖掘的描述任务一直开展不好 啤酒和尿布 被嘲笑 图模型既可以消除噪音且表示紧凑 相对AI的穷举 还可以对模型的各个部分可解释 前者是预测 泛化 后者是描述 发现 金融和生物等领域 计算机科学有两个策略 其一 代替领域专家 从数据建立可靠 泛化 的模型 其二 为领域提供工具 简化专家的工作 知识发现 对这些领域 描述可能更好 对网络 语言 图像等领域 泛化是重要的 但是 发现同样重要 概率图模型为数据挖掘的两个任务提供工具 思考 继续研究泛化 重启发现研究更重要 概率图模型前景如何 历史的故事 线性感知机 基于最小二乘的Rosenblatt的感知机 1956 其本质是平均 1943年 McCulloch和Pitts的神经元工作方式 1949年 Hebb的学习律 只能解决线性问题 不能满足实际的需要 埋下 祸根 20世纪70年代面临的选择 统计优化 平均 感知机统计模式识别 复杂信息系统 结构 专家系统句法模式识别 选择 非线性问题计算效率 专家系统合理复杂问题求解实现智能系统的理想 DudaandHart 73 AI 1969年 M Minsky发表颠覆性的报告 Perceptron 表象是以XOR问题向以平均为基础的感知机发难 本质是试图以结构方法代替平均 全书使用拓扑作为工具 1956年 以复杂信息处理为契机 提出AI 其动机有二 其一 发展处理符号的方