超图Hypergraph理论与应用.pptx
《超图Hypergraph理论与应用.pptx》由会员分享,可在线阅读,更多相关《超图Hypergraph理论与应用.pptx(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、动机(Motivation)什么是共指消解(Coreference Resolution)共指消解的各种方法图分割(Graph Partitioning)方法简单图分割方法的潜在缺陷引入超图(Hypergraph)的意义第1页/共41页超图(Hypergraph)超图的定义超图的分割超图真比简单图优越吗?如何将超图运用到共指消解中第2页/共41页什么是共指消解李明i 怕高妈妈j 一人呆在家里寂寞,他i 便将他自己i家里的电视搬了过来给她j。第3页/共41页共指消解的方法规则方法 利用句法层面的知识,进行启发式消解。统计方法 基于训练语料库,统计出概率分布,然后进行预测。机器学习 决策树、朴素贝
2、叶斯、规则学习等等。图方法 以节点表示名词短语,以边表示名词短语间的共指关联度。第4页/共41页图方法节点表示名词短语边表示短语与短语之间的某种关联(这种关联必须要对“共指”起到贡献,如人称、性别、单复数等属性)边的权值用来表示这种关联对共指起到的贡献的大小第5页/共41页简单图一条边只能连接两个顶点第6页/共41页超图一条边可以连接多个顶点第7页/共41页为什么引入超图(一个例子)简单图版本丢失了“同一作者的多篇文章”这一信息,而超图版本则保存了这一信息。在共指消解里面,也有类似的信息,比如“多个指代的性别(gender)相同”、“多个指代的数量相同”(即同为单数或同为复数)等。顶点代表文章
3、,每条边代表两个顶点(文章)享有同一个作者第8页/共41页为什么引入超图(一个例子)假设有三篇文章,v1,v2,v3。它们的作者分别是:v1:A,B v2:B,C v3:C,D如果v1:A,B v2:A,C v3:A,D第9页/共41页简单图的分割目标:使分割出来的两个子图之间的关联最小 问题:如何定义“关联最小”?第10页/共41页简单图分割的数学表达分割子图间关联最小=跨分割边界的所有边的权值之和最小邻接矩阵(Adjacency Matrix)A(i,j)=顶点i和顶点j之间的所有边的权值之和Min Cut(G+,G-),根据二次型表达式等价于:MaxY YTAY,其中Yi +1,-1;第
4、11页/共41页简单图分割的问题问题:导致退化的分割第12页/共41页Normalized-Cut仅仅做到跨边界的权值和最小还不够,因为可能存在一些孤立点,它们跟外界的联系本身就极小,于是很可能被独立分割出来。第13页/共41页Normalized-Cut解决思想:一个cut是“好的”当且仅当对任意一个子图来说,从子图中的节点出发跨越分割边界的边的权值和相比于从子图节点出发的所有边的权值和的比例越小越好。通俗来说就是:任一分割出来的子图跟外界的联系主要来自该子图内部。第14页/共41页Normalized-CutNP-Hard第15页/共41页拉普拉斯矩阵(Laplacian Matrix)第
5、16页/共41页谱(Spectrum)方法NP-Hard谱方法逼近解minz(ZTLZ/ZTZ)其中 Zi r+,r-;r+=|i:zi0|r-=|i:zi0|/|i:zi0|不变式:ZTZ=n;ZT1=0;含义:L是拉普拉斯矩阵 L=B A第17页/共41页 超图理论的目标 将简单图的表达泛化为超图表达,将简单图分割算法推广到超图分割之上,并证明超图分割和简单图分割的内在标准(criteria)是一致的第18页/共41页超图的表示关键是超边如何表示:用一个点集来表示。令V是一个顶点集合V=v1,v2,v3,v4,v5,v6,v7;则每一条超边都是V的一个子集E=e1,e2,e3,e4=v1,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 超图 Hypergraph 理论 应用
限制150内