超图(Hypergraph)理论与应用.ppt

超图 Hypergraph 理论与应用 刘未鹏 动机 Motivation 什么是共指消解 CoreferenceResolution 共指消解的各种方法图分割 GraphPartitioning 方法简单图分割方法的潜在缺陷引入超图 Hypergraph 的意义 超图 Hypergraph 超图的定义超图的分割超图真比简单图优越吗 如何将超图运用到共指消解中 什么是共指消解 李明i 怕 高妈妈j 一人呆在家里寂寞 他i 便将 他自己i 家里的电视搬了过来给 她j 共指消解的方法 规则方法利用句法层面的知识 进行启发式消解 统计方法基于训练语料库 统计出概率分布 然后进行预测 机器学习决策树 朴素贝叶斯 规则学习等等 图方法以节点表示名词短语 以边表示名词短语间的共指关联度 图方法 节点表示名词短语边表示短语与短语之间的某种关联 这种关联必须要对 共指 起到贡献 如人称 性别 单复数等属性 边的权值用来表示这种关联对共指起到的贡献的大小 简单图 一条边只能连接两个顶点 超图 一条边可以连接多个顶点 为什么引入超图 一个例子 简单图版本丢失了 同一作者的多篇文章 这一信息 而超图版本则保存了这一信息 在共指消解里面 也有类似的信息 比如 多个指代的性别 gender 相同 多个指代的数量相同 即同为单数或同为复数 等 顶点代表文章 每条边代表两个顶点 文章 享有同一个作者 为什么引入超图 一个例子 假设有三篇文章 v1 v2 v3 它们的作者分别是 v1 A Bv2 B Cv3 C D如果v1 A Bv2 A Cv3 A D 简单图的分割 目标 使分割出来的两个子图之间的关联最小 问题 如何定义 关联最小 简单图分割的数学表达 分割子图间关联最小 跨分割边界的所有边的权值之和最小邻接矩阵 AdjacencyMatrix A i j 顶点i和顶点j之间的所有边的权值之和MinCut G G 根据二次型表达式等价于 MaxYYTAY 其中Yi 1 1 简单图分割的问题 问题 导致退化的分割 Normalized Cut 仅仅做到跨边界的权值和最小还不够 因为可能存在一些孤立点 它们跟外界的联系本身就极小 于是很可能被独立分割出来 Normalized Cut 解决思想 一个cut是 好的 当且仅当对任意一个子图来说 从子图中的节点出发跨越分割边界的边的权值和相比于从子图节点出发的所有边的权值和的比例越小越好 通俗来说就是 任一分割出来的子图跟外界的联系主要来自该子图内部 Normalized Cut NP Hard 拉普拉斯矩阵 LaplacianMatrix 谱 Spectrum 方法 NP Hard谱方法逼近解minz ZTLZ ZTZ 其中Zi r r r i zi0 r i zi 0 i zi 0 不变式 ZTZ n ZT1 0 含义 L是拉普拉斯矩阵L B A 超图理论的目标 将简单图的表达泛化为超图表达 将简单图分割算法推广到超图分割之上 并证明超图分割和简单图分割的内在标准 criteria 是一致的 超图的表示 关键是超边如何表示 用一个点集来表示 令V是一个顶点集合V v1 v2 v3 v4 v5 v6 v7 则每一条超边都是V的一个子集E e1 e2 e3 e4 v1 v2 v3 v2 v3 v3 v5 v6 v4 超图的矩阵表达 顶点的度d v 超边的度 超图的矩阵表达 超图的邻接矩阵 其中W是一对角阵 对角线元素为各超边的权值 A是超图的邻接矩阵 按右边方法表示的A 超图的邻接矩阵 A i i 为0 A i j 为vi和vj共享的所有超边的权值和 Dv为一对角阵 对角线元素为各顶点的度d v 超图的分割 cut 如何将简单图的分割标准推广到超图上面 理解超图cut的含义 将被切割的每一条超边看作一个子图 其中每两个顶点都是两两相连的 连接的权值皆为w e e的度 该子图被切割为e G 和e G 个顶点 因此被切断的边一共有 e G e G 个 超图的Normalized Cut 超图和简单图的Normailzed cut是形式一致的 超图的Normailzed Cut 随机游走 RandomWalk 超图分割的随机游走解释 意义 证明超图分割的确是简单图分割的一个妥善的推广 这对超图分割算法的有效性至关重要 图分割的随机游走解释 一个最优分割须使得随机游走落在同一个子图中的概率最大 同时随机游走跨越分割边界的几率最小 目标 证明超图分割也满足同样的随机游走性质 什么是随机游走 RandomWalk GooglePagerank算法 GooglePagerank算法 基本模型 用一个向量I来代表所有页面的重要性 I的第i个分量Ii就是第i个页面的重要性 另 假设一个页面有lj个向其它页面的链接 那么每个被指向的页面都得到该页面的1 lj的重要性 同时假设一个页面的重要性完全来自指向它的页面的贡献数学表达 其中Pj表示第j个页面 lj表示第j个页面上的链接数 Pj Bi表示第j个页面指向Pi 这么多页面 它们互相之间都有一堆链接 我怎么知道一个特定的页面的重要性是多少呢 GooglePageRank算法 GooglePagerank算法 如何计算I HI中的I I是H的一个特征向量 对应特征值为1 迭代法 Ik 1 HIk GooglePagerank算法 GooglePagerank算法 问题 链接黑洞 只进不出 GooglePagerank算法 解决 随机游走 RandomWalk 理论假设你是一个网络爬虫 在网络上跟着页面链接随机的游走 那么 当你发现自己停在一个页面Pj上 而Pj共有lj个链接 其中一个指向Pi 那么你下一步游走到Pi的几率就是1 lj 在你随机游走的整个过程中 假设你停留在Pj上的时间是Tj 那么你停留在Pi上的时间就是 随机游走模型跟页面重要性模型是一致的 随机游走模型跟页面重要性模型是一致的 GooglePagerank算法 随机游走到页面2 一个链接黑洞 的时候 尽管没有链接 但我们可以假设下一步游走等概率游走到任意一个其它页面 即于是 超图分割de随机游走解释 p u v 表示从顶点u随机游走到顶点v的概率 pi v 表示随机游走停留在v上的概率 超图分割de随机游走解释 超图分割的随机游走解释 随机游走留在分割子图内的几率尽可能大 跨越分割边界的几率尽可能小 超图真的比简单图优越吗 如何将超图运用在共指消解中 跟把简单图运用在共指消解中一样 因为超图是简单图的推广 半指导聚类 惩罚矩阵问题讨论 在共指消解里面 超图的超边表示什么 超边的权值又如何确定 这在那篇论文里面也是一个未决问题