《超图理论与应用》.pptVIP

Google PageRank算法 超图(Hypergraph)理论与应用 刘未鹏 动机(Motivation) 什么是共指消解(Coreference Resolution) 共指消解的各种方法 图分割(Graph Partitioning)方法 简单图分割方法的潜在缺陷 引入超图(Hypergraph)的意义 超图(Hypergraph) 超图的定义 超图的分割 超图真比简单图优越吗？ 如何将超图运用到共指消解中 什么是共指消解 [李明i ]怕[高妈妈j ]一人呆在家里寂寞,[他i ]便将[他自己i]家里的电视搬了过来给[她j]。 共指消解的方法 规则方法 利用句法层面的知识，进行启发式消解。 统计方法 基于训练语料库，统计出概率分布，然后进行预测。 机器学习 决策树、朴素贝叶斯、规则学习等等。 图方法 以节点表示名词短语，以边表示名词短语间的共指关联度。 图方法 节点表示名词短语 边表示短语与短语之间的某种关联(这种关联必须要对“共指”起到贡献，如人称、性别、单复数等属性) 边的权值用来表示这种关联对共指起到的贡献的大小 简单图 一条边只能连接两个顶点 超图 一条边可以连接多个顶点 为什么引入超图(一个例子) 简单图版本丢失了“同一作者的多篇文章”这一信息，而超图版本则保存了这一信息。 在共指消解里面，也有类似的信息，比如“多个指代的性别(gender)相同”、“多个指代的数量相同”(即同为单数或同为复数)等。 顶点代表文章，每条边代表两个顶点（文章）享有同一个作者 为什么引入超图(一个例子) 假设有三篇文章，v1，v2，v3。它们的作者分别是：v1:A,B v2:B,C v3:C,D 如果v1:A,B v2:A,C v3:A,D 简单图的分割 目标：使分割出来的两个子图之间的关联最小 问题：如何定义“关联最小”？ 简单图分割的数学表达 分割子图间关联最小 = 跨分割边界的所有边的权值之和最小 邻接矩阵(Adjacency Matrix) A(i, j) = 顶点i和顶点j之间的所有边的权值之和 Min Cut(G+, G-)，根据二次型表达式 等价于：MaxY YTAY，其中Yi ∈ {+1, -1}; 简单图分割的问题 问题：导致退化的分割 Normalized-Cut 仅仅做到跨边界的权值和最小还不够，因为可能存在一些孤立点，它们跟外界的联系本身就极小，于是很可能被独立分割出来。 Normalized-Cut 解决思想：一个cut是“好的”当且仅当对任意一个子图来说，从子图中的节点出发跨越分割边界的边的权值和相比于从子图节点出发的所有边的权值和的比例越小越好。通俗来说就是：任一分割出来的子图跟外界的联系主要来自该子图内部。 Normalized-Cut NP-Hard 拉普拉斯矩阵(Laplacian Matrix) 谱(Spectrum)方法 NP-Hard 谱方法逼近解 minz(ZTLZ/ZTZ) 其中 Zi ∈ {r+ , r-}; r+ = √|{i:zi0}|/|{i:zi0}| r- = √|{i:zi0}|/|{i:zi0}| 不变式：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是形式一致的 超图的Normai