超图(Hypergraph)理论与应用

超图(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};,(,)(,)uGvGcutGGwuv简单图分割的问题•问题：导致退化的分割Normalized-Cut•仅仅做到跨边界的权值和最小还不够，因为可能存在一些孤立点，它们跟外界的联系本身就极小，于是很可能被独立分割出来。Normalized-Cut•解决思想：一个cut是“好的”当且仅当对任意一个子图来说，从子图中的节点出发跨越分割边界的边的权值和相比于从子图节点出发的所有边的权值和的比例越小越好。通俗来说就是：任一分割出来的子图跟外界的联系主要来自该子图内部。(,)(,)(,)(,)(,)cutGGcutGGNcutGGassoGGassoGG,(,)(,)uGtGassoGGwutNormalized-Cut拉普拉斯矩阵(LaplacianMatrix)谱(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}}超图的矩阵表达{|}()()eEvedvwe(,,)GVEw()||ee1;0;(,)veotherwiseHve顶点的度d(v)超边的度超图的矩阵表达1;0;(,)veotherwiseHve超图的邻接矩阵1;0;(,)veotherwiseHveTvAHWHD其中W是一对角阵，对角线元素为各超边的权值。A是超图的邻接矩阵按右边方法表示的A(超图的邻接矩阵)，A(i,i)为0，A(i,j)为vi和vj共享的所有超边的权值和。Dv为一对角阵，对角线元素为各顶点的度d(v)。超图的分割(cut)如何将简单图的分割标准推广到超图上面？||||(,)()()eGeGeGcutGGwee,(,)(,)uGvGcutGGwuv理解超图cut的含义||||(,)()()eGeGeGcutGGwee将被切割的每一条超边看作一个子图，其中每两个顶点都是两两相连的，连接的权值皆为w(e)/(e的度)。该子图被切割为e∩G+和e∩G-个顶点，因此被切断的边一共有|e∩G+||e∩G-|个。超图的Normalized-Cut(,)(,)(,)(,)(,)cutGGcutGGNcutGGassoGGassoGG(,)(,)(,)(,)(,)cutGGcutGGNcutGGassoGGassoGG超图和简单图的Normailzed-cut是形式一致的(,)()vGassoGGdv超图的Normailzed-Cut11argmin():()cSVcSvolSvolSvolS11argmin():(,)()(,)(,)GGcGcutGGassoGGassoGG随机游走(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=HIkGooglePagerank算法GooglePagerank算法•问题：链接黑洞(只进不出)GooglePagerank算法•解决：随机游走(RandomWalk)理论•假设你是一个网络爬虫，在网络上跟着页面链接随机的游走。那么，当你发现自己停在一个页面Pj上，而Pj共有lj个链接，其中一个指向Pi，那么你下一步游走到Pi的几率就是1/lj。•在你随机游走的整个过程中，假设你停留在Pj上的时间是Tj，那么你停留在Pi上的时间就是：随机游走模型跟页面重要性模型是一致的jijiPBjTTl随机游走模型跟页面重要性模型是一致的jijiPBjTTlGooglePagerank算法•随机游走到页面2(一个链接黑洞)的时候，尽管没有链接，但我们可以假设下一步游走等概率游走到任意一个其它页面，即•于是超图分割de随机游走解释|,()1(,)()()eEuevewepuvedu(,)(,)(,)()()()eEHueHvepuvweduep(u,v)表示从顶点u随机游走到顶点v的概率。pi(v)表示随机游走停留在v上的概率。()()dvvvolV()(,)(,)(,)1()(,)()()(,)()()()(,)()11()(,)()(,)()()uVuVeEuVeEeEuVeEduhuehvehveupuvwewehuevolVduevolVehuedvwehvewehvevvolVevolVvolV超图分割de随机游走解释11()()//cvolScSvolVvolSvolVvolSvolV11argmin():()cSVcSvolSvolSvolS()/()vSvSdvvolSvolVvvolV()()(,)(,)||||()()()(,)(,)()()()()(,)(,)()()(,)()()ccccceSeSueSveSeSueSveSuSvSeSuSvSwewehuehveeSeSvolSvolVvolVevolVeduhuehvewevolVdueduhuehveweupuvvolVdue超图分割的随机游走解释11()()//cvolScSvolVvolSvolVvolSvolV11()()(,)()()()ccuSvSvSvScSupuvvv随机游走留在分割子图内的几率尽可能大，跨越分割边界的几率尽可能小超图真的比简单图优越吗？如何将超图运用在共指消解中•跟把简单图运用在共指消解中一样，因为超图是简单图的推广。•半指导聚类：惩罚矩阵•问题讨论：在共指消解里面，超图的超边表示什么，超边的权值又如何确定(这在那篇论文里面也是一个未决问题)。