超圖(Hypergraph)理論與應(yīng)用

1、劉未鵬動(dòng)機(jī)(Motivation) 什么是共指消解(Coreference Resolution) 共指消解的各種方法 圖分割(Graph Partitioning)方法 簡單圖簡單圖分割方法的潛在缺陷潛在缺陷 引入超圖引入超圖(Hypergraph)的意義的意義超圖(Hypergraph) 超圖的定義超圖的定義 超圖的分割超圖的分割 超圖真比簡單圖優(yōu)越嗎？超圖真比簡單圖優(yōu)越嗎？ 如何將超圖運(yùn)用到共指消解中什么是共指消解李明i 怕高媽媽j 一人呆在家里寂寞,他i 便將他自己i家里的電視搬了過來給她j。共指消解的方法 規(guī)則方法 利用句法層面的知識(shí)，進(jìn)行啟發(fā)式消解。 統(tǒng)計(jì)方法 基于訓(xùn)練語料庫，統(tǒng)計(jì)

2、出概率分布，然后進(jìn)行預(yù)測。 機(jī)器學(xué)習(xí) 決策樹、樸素貝葉斯、規(guī)則學(xué)習(xí)等等。 圖方法圖方法 以節(jié)點(diǎn)表示名詞短語，以邊表示名詞短語間的共指關(guān)聯(lián)度。圖方法圖方法 節(jié)點(diǎn)表示名詞短語 邊表示短語與短語之間的某種關(guān)聯(lián)(這種關(guān)聯(lián)必須要對(duì)“共指”起到貢獻(xiàn)，如人稱、性別、單復(fù)數(shù)等屬性) 邊的權(quán)值用來表示這種關(guān)聯(lián)對(duì)共指起到的貢獻(xiàn)的大小簡單圖一條邊只能連接兩個(gè)頂點(diǎn)超圖一條邊可以連接多個(gè)頂點(diǎn)為什么引入超圖為什么引入超圖(一個(gè)例子一個(gè)例子)簡單圖版本丟失了“同一作者的多篇文章同一作者的多篇文章”這一信息，而超圖版本則保存了這一信息。 在共指消解里面，也有類似的信息，比如“多個(gè)指代的性別(gender)相同”、“多個(gè)指代的

3、數(shù)量相同”(即同為單數(shù)或同為復(fù)數(shù))等。頂點(diǎn)代表文章，每條邊代表兩個(gè)頂點(diǎn)（文章）享有同一個(gè)作者為什么引入超圖為什么引入超圖(一個(gè)例子一個(gè)例子) 假設(shè)有三篇文章，v1，v2，v3。它們的作者分別是：v1:A,B v2:B,C v3:C,D 如果v1:A,B v2:A,C v3:A,D簡單圖的分割 目標(biāo)目標(biāo)：使分割出來的兩個(gè)子圖之間的關(guān)聯(lián)最小 問題問題：如何定義“關(guān)聯(lián)最小關(guān)聯(lián)最小”？簡單圖分割的數(shù)學(xué)表達(dá) 分割子圖間關(guān)聯(lián)最小關(guān)聯(lián)最小 = 跨分割邊界的所有邊的跨分割邊界的所有邊的權(quán)值之和最小權(quán)值之和最小 鄰接矩陣(Adjacency Matrix) A(i, j) = 頂點(diǎn)i和頂點(diǎn)j之間的所有邊的權(quán)值之

4、和 Min Cut(G+, G-)，根據(jù)二次型表達(dá)式二次型表達(dá)式 等價(jià)于：等價(jià)于：MaxY YTAY，其中Yi +1, -1;,(,)( , )u G v Gcut G Gw u v簡單圖分割的問題 問題問題：導(dǎo)致退化的分割Normalized-Cut 僅僅做到跨邊界的權(quán)值和最小還不夠，因?yàn)榭赡艽嬖谝恍┕铝Ⅻc(diǎn)，它們跟外界的聯(lián)系本身就極小，于是很可能被獨(dú)立分割出來。Normalized-Cut 解決思想解決思想：一個(gè)cut是“好的”當(dāng)且僅當(dāng)對(duì)任意一個(gè)子圖來說，從子圖中的節(jié)點(diǎn)出發(fā)跨越分割邊界的邊的權(quán)值和相比于從子圖節(jié)點(diǎn)出發(fā)的所有邊的權(quán)值和的比例越小越好。通俗來說就是：任一分割出來的子圖跟外界的聯(lián)系

5、主要來自該子圖內(nèi)部。(,)(,)(,)(, )(, )cut G Gcut G GNcut G Gasso G Gasso G G,(, )( , )u G t Gasso G Gw u tNormalized-Cut拉普拉斯矩陣(Laplacian Matrix)譜(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 超圖理論的目標(biāo) 將簡單圖的表達(dá)泛化為超圖表達(dá)，將簡單圖分割

6、算法推廣到超圖分割之上，并證明超圖分割和簡單圖分割的內(nèi)在標(biāo)準(zhǔn)內(nèi)在標(biāo)準(zhǔn)(criteria)是一致的是一致的超圖的表示 關(guān)鍵是超邊如何表示：用一個(gè)點(diǎn)集來表示。 令V是一個(gè)頂點(diǎn)集合V=v1, v2, v3, v4,v5,v6,v7; 則每一條超邊都是每一條超邊都是V的一個(gè)子集的一個(gè)子集 E = e1,e2,e3,e4 = v1,v2,v3,v2,v3, v3,v5,v6,v4 超圖的矩陣表達(dá)|( )( )e Ev ed vw e( , , )GV E w( ) | |ee1;0;( , )v eotherwiseH v e頂點(diǎn)的度d(v)超邊的度超圖的矩陣表達(dá)1;0;( , )v eotherwis

7、eH v e 超圖的鄰接矩陣1;0;( , )v eotherwiseH v eTvA HWHD其中W是一對(duì)角陣，對(duì)角線元素為各超邊的權(quán)值。A是超圖的鄰接矩鄰接矩陣陣按右邊方法表示的A(超圖的鄰接矩陣)，A(i,i)為0，A(i,j)為為vi和和vj共享的所有超邊的權(quán)值和共享的所有超邊的權(quán)值和。Dv為一對(duì)角陣，對(duì)角線元素為各頂點(diǎn)的度d(v)。 超圖的分割(cut)如何將簡單如何將簡單圖的分割標(biāo)圖的分割標(biāo)準(zhǔn)推廣到超準(zhǔn)推廣到超圖上面？圖上面？|(,)( )( )eGe Ge Gcut G Gw ee,(,)( , )u G v Gcut G Gw u v 理解超圖理解超圖cut的含義的含義|(,)

8、( )( )eGe Ge Gcut G Gw ee將被切割的每一條超邊看作一個(gè)子圖每一條超邊看作一個(gè)子圖，其中每兩個(gè)頂點(diǎn)都是兩兩相連的，連接的權(quán)值皆為w(e)/(e的度)。該子圖被切割為eG+和eG-個(gè)頂點(diǎn)，因此被切斷的邊一共有| eG+ | eG- |個(gè)。 超圖的Normalized-Cut(,)(,)(,)(, )(, )cut G Gcut G GNcut G Gasso G Gasso G G(,)(,)(,)(, )(, )cut G Gcut G GNcut G Gasso G Gasso G G超圖和簡單圖超圖和簡單圖的的Normailzed-cut是形式一是形式一致的致的(,

9、)( )v Gasso G Gd v 超圖的Normailzed-Cut11argmin ( ):()cS Vc Svol SvolS volS 11argmin ():(,)()(, )(, )GGc Gcut G Gasso G Gasso G G隨機(jī)游走(Random Walk)超圖分割的隨機(jī)游走隨機(jī)游走解釋 意義意義：證明超圖分割的確是簡單圖分割的一個(gè)妥善的推廣，這對(duì)超圖分割算法的有效性至關(guān)重要。 圖分割的隨機(jī)游走解釋圖分割的隨機(jī)游走解釋：一個(gè)最優(yōu)分割須使得隨機(jī)游走落在同一個(gè)子圖中的概率最大，同時(shí)隨機(jī)游走跨越分割邊界的幾率最小。 目標(biāo)目標(biāo)：證明超圖分割也滿足同樣的隨機(jī)游走性質(zhì)。什么是隨

10、機(jī)游走隨機(jī)游走(Random Walk)Google Pagerank算法算法Google Pagerank算法 基本模型：用一個(gè)向量I來代表所有頁面的重要性，I的第i個(gè)分量Ii就是第i個(gè)頁面的重要性；另，假設(shè)一個(gè)頁面有l(wèi)j個(gè)向其它頁面的鏈接，那么每個(gè)被指向的頁面都得到該頁面的1/lj的重要性；同時(shí)假設(shè)一個(gè)頁面的重要性完全來自指向它的頁面的貢獻(xiàn) 數(shù)學(xué)表達(dá)： 其中Pj表示第j個(gè)頁面。lj表示第j個(gè)頁面上的鏈接數(shù)，PjBi表示第j個(gè)頁面指向Pi。這么多頁面，它們互相之間都有一堆鏈接，我怎么知道一我怎么知道一個(gè)特定的頁面?zhèn)€特定的頁面的重要性是多的重要性是多少呢？少呢？Google PageRank算

11、法Google Pagerank算法 如何計(jì)算I=HI中的I？(I是H的一個(gè)特征向量，對(duì)應(yīng)特征值為1) 迭代法：Ik+1 = HIkGoogle Pagerank算法Google Pagerank算法 問題：鏈接黑洞問題：鏈接黑洞(只進(jìn)不出只進(jìn)不出)Google Pagerank算法 解決解決：隨機(jī)游走隨機(jī)游走(Random Walk)理論 假設(shè)你是一個(gè)網(wǎng)絡(luò)爬蟲，在網(wǎng)絡(luò)上跟著頁面鏈接隨機(jī)的游走。那么，當(dāng)你發(fā)現(xiàn)自己停在一個(gè)頁面Pj上，而Pj共有l(wèi)j個(gè)鏈接，其中一個(gè)指向Pi，那么你下一步游走到Pi的幾率就是1/lj。 在你隨機(jī)游走的整個(gè)過程中，假設(shè)你停留在Pj上的時(shí)間是Tj，那么你停留在Pi上的時(shí)

12、間就是：隨機(jī)游走模隨機(jī)游走模型跟頁面重型跟頁面重要性模型是要性模型是一致的一致的jijiPBjTTljijiPBjTTlGoogle Pagerank算法 隨機(jī)游走到頁面2(一個(gè)鏈接黑洞鏈接黑洞)的時(shí)候，盡管沒有鏈接，但我們可以假設(shè)下一步游走等概率游走到任意一個(gè)其它頁面，即 于是 超圖分割超圖分割de隨機(jī)游走解釋隨機(jī)游走解釋|,( )1( , )( ) ( )e Eu ev ew ep u ve d u ( , )( , )( , )( )( )( )e EH u e H vep u vw ed uep(u,v)表示從頂點(diǎn)表示從頂點(diǎn)u隨機(jī)游走到頂點(diǎn)隨機(jī)游走到頂點(diǎn)v的概率。的概率。pi (v)表

13、示隨機(jī)游走表示隨機(jī)游走停留在停留在v上的概率。上的概率。( )( )d vvvolV( )( , ) ( , )( , )1( ) ( , )( )( ) ( , )( )( )( )( , )( )11( ) ( , )( ) ( , )( )( )u Vu Ve Eu Ve Ee Eu Ve Ed uh u e h v eh v eu p u vw ew e h u evolVd uevolVeh u ed vw e h v ew e h v evvolVevolVvolV 超圖分割超圖分割de隨機(jī)游走解釋隨機(jī)游走解釋11( )()/cvol Sc SvolV volS volVvolSv

14、olV11argmin ( ):()cS Vc Svol SvolS volS ( )/( )v Sv Sd vvolS volVvvolV( )( ) ( , ) ( , )|( )( )( ) ( , ) ( , )( )( )( )( )( , ) ( , )( )( ) ( , )( )( )ccccceSeSu e Sv e SeSu e Sv e Su Sv Se Su Sv Sw ew e h u e h v eeS eSvol SvolVvolVevolVed u h u e h v ew evolV d ued uh u e h v ew eu p u vvolVd ue 超圖分割的隨機(jī)游走解釋超圖分割的隨機(jī)游走解釋11( )()/cvol Sc SvolV volS volVvolSvolV11( )( ) ( , )()( )( )ccu