超圖理論與應(yīng)用第1頁，共38頁，2023年，2月20日，星期二動機(Motivation)什么是共指消解(CoreferenceResolution)共指消解的各種方法圖分割(GraphPartitioning)方法簡單圖分割方法的潛在缺陷引入超圖(Hypergraph)的意義第2頁，共38頁，2023年，2月20日，星期二超圖(Hypergraph)超圖的定義超圖的分割超圖真比簡單圖優(yōu)越嗎？如何將超圖運用到共指消解中第3頁，共38頁，2023年，2月20日，星期二什么是共指消解[李明i]怕[高媽媽j]一人呆在家里寂寞,[他i]便將[他自己i]家里的電視搬了過來給[她j]。第4頁，共38頁，2023年，2月20日，星期二共指消解的方法規(guī)則方法利用句法層面的知識，進行啟發(fā)式消解。統(tǒng)計方法基于訓(xùn)練語料庫，統(tǒng)計出概率分布，然后進行預(yù)測。機器學(xué)習(xí)決策樹、樸素貝葉斯、規(guī)則學(xué)習(xí)等等。圖方法以節(jié)點表示名詞短語，以邊表示名詞短語間的共指關(guān)聯(lián)度。第5頁，共38頁，2023年，2月20日，星期二圖方法節(jié)點表示名詞短語邊表示短語與短語之間的某種關(guān)聯(lián)(這種關(guān)聯(lián)必須要對“共指”起到貢獻，如人稱、性別、單復(fù)數(shù)等屬性)邊的權(quán)值用來表示這種關(guān)聯(lián)對共指起到的貢獻的大小第6頁，共38頁，2023年，2月20日，星期二簡單圖一條邊只能連接兩個頂點第7頁，共38頁，2023年，2月20日，星期二超圖一條邊可以連接多個頂點第8頁，共38頁，2023年，2月20日，星期二為什么引入超圖(一個例子)簡單圖版本丟失了“同一作者的多篇文章”這一信息，而超圖版本則保存了這一信息。在共指消解里面，也有類似的信息，比如“多個指代的性別(gender)相同”、“多個指代的數(shù)量相同”(即同為單數(shù)或同為復(fù)數(shù))等。頂點代表文章，每條邊代表兩個頂點（文章）享有同一個作者第9頁，共38頁，2023年，2月20日，星期二為什么引入超圖(一個例子)假設(shè)有三篇文章，v1，v2，v3。它們的作者分別是：v1:A,Bv2:B,Cv3:C,D如果v1:A,Bv2:A,Cv3:A,D第10頁，共38頁，2023年，2月20日，星期二簡單圖的分割目標(biāo)：使分割出來的兩個子圖之間的關(guān)聯(lián)最小

問題：如何定義“關(guān)聯(lián)最小”？第11頁，共38頁，2023年，2月20日，星期二簡單圖分割的數(shù)學(xué)表達(dá)分割子圖間關(guān)聯(lián)最小

=跨分割邊界的所有邊的權(quán)值之和最小鄰接矩陣(AdjacencyMatrix)A(i,j)=頂點i和頂點j之間的所有邊的權(quán)值之和MinCut(G+,G-)，根據(jù)二次型表達(dá)式等價于：MaxYYTAY，其中Yi∈{+1,-1};第12頁，共38頁，2023年，2月20日，星期二簡單圖分割的問題問題：導(dǎo)致退化的分割第13頁，共38頁，2023年，2月20日，星期二Normalized-Cut僅僅做到跨邊界的權(quán)值和最小還不夠，因為可能存在一些孤立點，它們跟外界的聯(lián)系本身就極小，于是很可能被獨立分割出來。第14頁，共38頁，2023年，2月20日，星期二Normalized-Cut解決思想：一個cut是“好的”當(dāng)且僅當(dāng)對任意一個子圖來說，從子圖中的節(jié)點出發(fā)跨越分割邊界的邊的權(quán)值和相比于從子圖節(jié)點出發(fā)的所有邊的權(quán)值和的比例越小越好。通俗來說就是：任一分割出來的子圖跟外界的聯(lián)系主要來自該子圖內(nèi)部。第15頁，共38頁，2023年，2月20日，星期二Normalized-CutNP-Hard第16頁，共38頁，2023年，2月20日，星期二拉普拉斯矩陣(LaplacianMatrix)第17頁，共38頁，2023年，2月20日，星期二譜(Spectrum)方法NP-Hard譜方法逼近解minz(ZTLZ/ZTZ)其中Zi∈{r+,r-};r+=√|{i:zi<0}|/|{i:zi>0}|r-=√|{i:zi>0}|/|{i:zi<0}|不變式：ZTZ=n;ZT1=0;含義：L是拉普拉斯矩陣L=B–A第18頁，共38頁，2023年，2月20日，星期二

超圖理論的目標(biāo)

將簡單圖的表達(dá)泛化為超圖表達(dá)，將簡單圖分割算法推廣到超圖分割之上，并證明超圖分割和簡單圖分割的內(nèi)在標(biāo)準(zhǔn)(criteria)是一致的第19頁，共38頁，2023年，2月20日，星期二超圖的表示關(guān)鍵是超邊如何表示：用一個點集來表示。令V是一個頂點集合V={v1,v2,v3,v4,v5,v6,v7};則每一條超邊都是V的一個子集E={e1,e2,e3,e4}={{v1,v2,v3},{v2,v3},{v3,v5,v6},{v4}}第20頁，共38頁，2023年，2月20日，星期二

超圖的矩陣表達(dá)頂點的度d(v)超邊的度超圖的矩陣表達(dá)第21頁，共38頁，2023年，2月20日，星期二

超圖的鄰接矩陣其中W是一對角陣，對角線元素為各超邊的權(quán)值。A是超圖的鄰接矩陣按右邊方法表示的A(超圖的鄰接矩陣)，A(i,i)為0，A(i,j)為vi和vj共享的所有超邊的權(quán)值和。Dv為一對角陣，對角線元素為各頂點的度d(v)。第22頁，共38頁，2023年，2月20日，星期二

超圖的分割(cut)如何將簡單圖的分割標(biāo)準(zhǔn)推廣到超圖上面？第23頁，共38頁，2023年，2月20日，星期二

理解超圖cut的含義將被切割的每一條超邊看作一個子圖，其中每兩個頂點都是兩兩相連的，連接的權(quán)值皆為w(e)/(e的度)。該子圖被切割為e∩G+和e∩G-個頂點，因此被切斷的邊一共有|e∩G+||e∩G-|個。第24頁，共38頁，2023年，2月20日，星期二

超圖的Normalized-Cut超圖和簡單圖的Normailzed-cut是形式一致的第25頁，共38頁，2023年，2月20日，星期二

超圖的Normailzed-Cut第26頁，共38頁，2023年，2月20日，星期二隨機游走(RandomWalk)第27頁，共38頁，2023年，2月20日，星期二超圖分割的隨機游走解釋意義：證明超圖分割的確是簡單圖分割的一個妥善的推廣，這對超圖分割算法的有效性至關(guān)重要。圖分割的隨機游走解釋：一個最優(yōu)分割須使得隨機游走落在同一個子圖中的概率最大，同時隨機游走跨越分割邊界的幾率最小。目標(biāo)：證明超圖分割也滿足同樣的隨機游走性質(zhì)。第28頁，共38頁，2023年，2月20日，星期二什么是隨機游走(RandomWalk)

GooglePagerank算法第29頁，共38頁，2023年，2月20日，星期二GooglePagerank算法基本模型：用一個向量I來代表所有頁面的重要性，I的第i個分量Ii就是第i個頁面的重要性；另，假設(shè)一個頁面有l(wèi)j個向其它頁面的鏈接，那么每個被指向的頁面都得到該頁面的1/lj的重要性；同時假設(shè)一個頁面的重要性完全來自指向它的頁面的貢獻數(shù)學(xué)表達(dá)：其中Pj表示第j個頁面。lj表示第j個頁面上的鏈接數(shù)，Pj∈Bi表示第j個頁面指向Pi。這么多頁面，它們互相之間都有一堆鏈接，我怎么知道一個特定的頁面的重要性是多少呢？第30頁，共38頁，2023年，2月20日，星期二GooglePageRank算法第31頁，共38頁，2023年，2月20日，星期二GooglePagerank算法如何計算I=HI中的I？(I是H的一個特征向量，對應(yīng)特征值為1)迭代法：Ik+1=HIk第32頁，共38頁，2023年，2月20日，星期二GooglePagerank算法第33頁，共38頁，2023年，2月20日，星期二GooglePagerank算法問題：鏈接黑洞(只進不出)第34頁，共38頁，2023年，2月20日，星期二GooglePagerank算法解決：隨機游走(RandomWalk)理論假設(shè)你是一個網(wǎng)絡(luò)爬蟲，在網(wǎng)絡(luò)上跟著頁面鏈接隨機的游走。那么，當(dāng)你發(fā)現(xiàn)自己停在一個頁面Pj上，而Pj共有l(wèi)j個鏈接，其中一個指向Pi，那么你下一步游走到Pi的幾率就是1/lj。在你隨機游走的整個過程中，假設(shè)你停留在Pj上的時間是Tj，那么你停留在Pi上的時間就是：隨機游走模型跟頁面重要性模型是一致的隨機游走模型跟頁面重要性模型是一致的第35頁，共38頁，2023年，2月20日，星期二GooglePagerank算法隨機游走到頁面2(一個鏈接黑洞)的時候，盡管沒有鏈接，但我們可以假設(shè)下一