超圖Hypergraph理論與應(yīng)用_第1頁
超圖Hypergraph理論與應(yīng)用_第2頁
超圖Hypergraph理論與應(yīng)用_第3頁
超圖Hypergraph理論與應(yīng)用_第4頁
超圖Hypergraph理論與應(yīng)用_第5頁
已閱讀5頁,還剩36頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

問題:如何定義“關(guān)聯(lián)最小”?第10頁/共41頁簡(jiǎn)單圖分割的數(shù)學(xué)表達(dá)分割子圖間關(guān)聯(lián)最小

=跨分割邊界的所有邊的權(quán)值之和最小鄰接矩陣(AdjacencyMatrix)A(i,j)=頂點(diǎn)i和頂點(diǎn)j之間的所有邊的權(quán)值之和MinCut(G+,G-),根據(jù)二次型表達(dá)式等價(jià)于:MaxYYTAY,其中Yi∈{+1,-1};第11頁/共41頁簡(jiǎn)單圖分割的問題問題:導(dǎo)致退化的分割第12頁/共41頁Normalized-Cut僅僅做到跨邊界的權(quán)值和最小還不夠,因?yàn)榭赡艽嬖谝恍┕铝Ⅻc(diǎn),它們跟外界的聯(lián)系本身就極小,于是很可能被獨(dú)立分割出來。第13頁/共41頁Normalized-Cut解決思想:一個(gè)cut是“好的”當(dāng)且僅當(dāng)對(duì)任意一個(gè)子圖來說,從子圖中的節(jié)點(diǎn)出發(fā)跨越分割邊界的邊的權(quán)值和相比于從子圖節(jié)點(diǎn)出發(fā)的所有邊的權(quán)值和的比例越小越好。通俗來說就是:任一分割出來的子圖跟外界的聯(lián)系主要來自該子圖內(nèi)部。第14頁/共41頁Normalized-CutNP-Hard第15頁/共41頁拉普拉斯矩陣(LaplacianMatrix)第16頁/共41頁譜(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第17頁/共41頁

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

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

超圖的矩陣表達(dá)頂點(diǎn)的度d(v)超邊的度超圖的矩陣表達(dá)第20頁/共41頁

超圖的鄰接矩陣其中W是一對(duì)角陣,對(duì)角線元素為各超邊的權(quán)值。A是超圖的鄰接矩陣按右邊方法表示的A(超圖的鄰接矩陣),A(i,i)為0,A(i,j)為vi和vj共享的所有超邊的權(quán)值和。Dv為一對(duì)角陣,對(duì)角線元素為各頂點(diǎn)的度d(v)。第21頁/共41頁

超圖的分割(cut)如何將簡(jiǎn)單圖的分割標(biāo)準(zhǔn)推廣到超圖上面?第22頁/共41頁

理解超圖cut的含義將被切割的每一條超邊看作一個(gè)子圖,其中每?jī)蓚€(gè)頂點(diǎn)都是兩兩相連的,連接的權(quán)值皆為w(e)/(e的度)。該子圖被切割為e∩G+和e∩G-個(gè)頂點(diǎn),因此被切斷的邊一共有|e∩G+||e∩G-|個(gè)。第23頁/共41頁

超圖的Normalized-Cut超圖和簡(jiǎn)單圖的Normailzed-cut是形式一致的第24頁/共41頁

超圖的Normailzed-Cut第25頁/共41頁隨機(jī)游走(RandomWalk)第26頁/共41頁超圖分割的隨機(jī)游走解釋意義:證明超圖分割的確是簡(jiǎn)單圖分割的一個(gè)妥善的推廣,這對(duì)超圖分割算法的有效性至關(guān)重要。圖分割的隨機(jī)游走解釋:一個(gè)最優(yōu)分割須使得隨機(jī)游走落在同一個(gè)子圖中的概率最大,同時(shí)隨機(jī)游走跨越分割邊界的幾率最小。目標(biāo):證明超圖分割也滿足同樣的隨機(jī)游走性質(zhì)。第27頁/共41頁什么是隨機(jī)游走(RandomWalk)

GooglePagerank算法第28頁/共41頁GooglePagerank算法基本模型:用一個(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ù),Pj∈Bi表示第j個(gè)頁面指向Pi。這么多頁面,它們互相之間都有一堆鏈接,我怎么知道一個(gè)特定的頁面的重要性是多少呢?第29頁/共41頁GooglePageRank算法第30頁/共41頁GooglePagerank算法如何計(jì)算I=HI中的I?(I是H的一個(gè)特征向量,對(duì)應(yīng)特征值為1)迭代法:Ik+1=HIk第31頁/共41頁GooglePagerank算法第32頁/共41頁GooglePagerank算法問題:鏈接黑洞(只進(jìn)不出)第33頁/共41頁GooglePagerank算法解決:隨機(jī)游走(RandomWalk)理論假設(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í)間就是:隨機(jī)游走模型跟頁面重要性模型是一致的隨機(jī)游走模型跟頁面重要性模型是一致的第34頁/共41頁GooglePagerank算法隨機(jī)游走到頁面2(一個(gè)鏈接黑洞)的時(shí)候,盡管沒有鏈接,但我們可以假設(shè)下一步游走等概率游走到任意一個(gè)其它頁面,即于是第35頁/共41頁

超圖分割de隨機(jī)游走解釋p(u,v)表示從頂點(diǎn)u隨機(jī)游走到頂點(diǎn)v的概率。pi

(v)表示隨機(jī)游走停留在v上的概率。第36頁/共41頁

超圖分割de隨機(jī)游走解釋第37頁/共41頁

超圖分割的隨機(jī)游走解釋

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論