知識圖譜 概念與技術(shù) 第5章：百科圖譜構(gòu)建

《知識圖譜:概念與技術(shù)》徐波2018/8/30第5講：百科知識圖譜構(gòu)建2本章大綱圖譜構(gòu)建?實體發(fā)現(xiàn)?知識抽取?實體分類?知識補全圖譜構(gòu)建?本體融合?實體對齊?屬性對齊?屬性值融合2018/8/30第5講：百科知識圖譜構(gòu)建3?是一類以百科類網(wǎng)站作為數(shù)據(jù)源構(gòu)建而成的知識圖譜?區(qū)別譜構(gòu)建42018/8/30第5講：百科知識圖譜構(gòu)建5?每個頁面均圍繞一個實體進(jìn)行全方面的介紹?e.g.,?/wiki/Donald_Trump?/item/唐納德·特朗普板自動生成，包含固定格式的半結(jié)構(gòu)化文本2018/8/30第5講：百科知識圖譜構(gòu)建6百科圖譜分類為通用百科圖譜和領(lǐng)域百科圖譜?來自于通用百科網(wǎng)站?E.g.,?維基百科，百度百科?領(lǐng)域百科圖譜?來自于領(lǐng)域百科網(wǎng)站?E.g.,?電影網(wǎng)站，購物網(wǎng)站2018/8/30第5講：百科知識圖譜構(gòu)建72018/8/30第5講：百科知識圖譜構(gòu)建8基于單源的百科圖譜構(gòu)建?目標(biāo)?輸入：一個百科數(shù)據(jù)源?輸出：一個百科知識圖譜?步驟?實體發(fā)現(xiàn)?知識抽取?實體分類?知識補全2018/8/30第5講：百科知識圖譜構(gòu)建92018/8/30第5講：百科知識圖譜構(gòu)建10?目標(biāo)?獲取一個百科數(shù)據(jù)源中所有網(wǎng)頁?基于Dump數(shù)據(jù)的下載?WikipediaDump形式提供下載WikipediaDump/2018/8/30第5講：百科知識圖譜構(gòu)建11?目標(biāo)?獲取一個百科數(shù)據(jù)源中所有網(wǎng)頁?基于Dump數(shù)據(jù)的下載?WikipediaDump?基于超鏈接的遍歷策略基本假設(shè)：百科數(shù)據(jù)源中所有網(wǎng)頁都通過超鏈接鏈接缺點：部分百科頁面未被其他頁面鏈接，導(dǎo)致無法獲取2018/8/30第5講：百科知識圖譜構(gòu)建12omviewIDhtmomviewhtmomviewhtmomviewhtmomviewhtmcomitemNAMEducomitemiducomitemiducomitemucomitem?目標(biāo)?獲取一個百科數(shù)據(jù)源中所有網(wǎng)頁?基于Dump數(shù)據(jù)的下載?WikipediaDump?基于超鏈接的遍歷策略?基于枚舉的遍歷策略?ID/名稱/哈?；炯僭O(shè)：百科數(shù)據(jù)源中所有網(wǎng)頁的URL的可枚舉性2018/8/30第5講：百科知識圖譜構(gòu)建13?目標(biāo)?篩選出所有介紹實體的網(wǎng)頁方法?選擇滿足特殊規(guī)律的URL可作為一個有效實體頁面?/view/[ID].htm?/item/[NAME]songidID?/subject/[ID]2018/8/30第5講：百科知識圖譜構(gòu)建142018/8/30第5講：百科知識圖譜構(gòu)建15個實體的知識抽取同類型關(guān)系2018/8/30第5講：百科知識圖譜構(gòu)建16一出好戲?存在多義詞 劉德華(中國香港男演員、歌手、制片人、填詞人)2018/8/30第5講：百科知識圖譜構(gòu)建17?同義詞?合并同一實體的不同表示2018/8/30第5講：百科知識圖譜構(gòu)建18x?對實體的結(jié)構(gòu)化總結(jié)?以表格的形式展示?第一列表示屬性?第二列表示屬性值是百科知識圖譜最重要的知識來源之一2018/8/30第5講：百科知識圖譜構(gòu)建19相關(guān)實體/標(biāo)簽關(guān)系抽取?標(biāo)簽?對實體進(jìn)行分類?標(biāo)簽來自于用戶眾包2018/8/30第5講：百科知識圖譜構(gòu)建20基于正則表達(dá)式的抽取2018/8/30第5講：百科知識圖譜構(gòu)建212018/8/30第5講：百科知識圖譜構(gòu)建22單數(shù)據(jù)源屬性融合?屬性名稱相似性?e.g.,英文名，英文名稱?同義詞相似性?外部同義詞庫?人工錄入?啟發(fā)式規(guī)則?等價屬性不同時出現(xiàn)在一個實體中?等價屬性domain和range相同?人工刪除2018/8/30第5講：百科知識圖譜構(gòu)建23數(shù)值屬性值歸一化2018/8/30第5講：百科知識圖譜構(gòu)建24 符串按照某分隔符ore 符串按照某分隔符ore 體列表String 判斷字符串是否存在分隔符 判斷該score是否大于未分割的得分?空格、中文逗號、英文逗號、中?評估第i種分隔符分割后的字符串列表Ti，score(Ti)=σt∈TiP(t)?Pt=1如果t是一個實體?Pt=?1如果t不是一個實體?Tbest=argmaxTiscoreTi2018/8/30第5講：百科知識圖譜構(gòu)建25龍卷風(fēng)(一種自然天氣現(xiàn)象)龍卷風(fēng)(周杰倫創(chuàng)作歌曲)龍卷風(fēng)(一種自然天氣現(xiàn)象)龍卷風(fēng)(周杰倫創(chuàng)作歌曲)龍卷風(fēng)(美國電影名稱)龍卷風(fēng)(動畫片《百變機(jī)獸之洛洛歷險記》角色)龍卷風(fēng)(楊鈺瑩、林翠萍、葉啟田演唱的歌曲)龍卷風(fēng)(游戲《游戲王》中魔法卡名稱)龍卷風(fēng)(口袋妖怪技能)龍卷風(fēng)(游戲《warcraft3》中技能名稱)龍卷風(fēng)(香港漫畫《九龍城寨》中的人物)龍卷風(fēng)(科普圖書《龍卷風(fēng)》)龍卷風(fēng)(skonec制作的同名游戲)龍卷風(fēng)(鄧紫棋翻唱歌曲)龍卷風(fēng)(黃錦祥詩歌《龍卷風(fēng)》)?目標(biāo)?建立實體與實體之間的關(guān)系<周杰倫，代表作品，龍卷風(fēng)(周杰倫創(chuàng)作歌曲)>2018/8/30第5講：百科知識圖譜構(gòu)建26對象屬性值實體鏈接方法?解析超鏈接對應(yīng)的URLbaiducomitem龍卷風(fēng)(周杰倫創(chuàng)作歌曲)<周杰倫，代表作品，龍卷風(fēng)(周杰倫創(chuàng)作歌曲)>2018/8/30第5講：百科知識圖譜構(gòu)建27對象屬性值實體鏈接方法?當(dāng)屬性值存在超鏈接時?解析超鏈接對應(yīng)的URL?建模為分類問題?給定一個(實體，屬性，屬性值)三元組，以及屬性值對應(yīng)或1個正確的實體7s(m,e)=?wi×fi(m,7龍卷風(fēng)(一種自然天氣現(xiàn)象)龍卷風(fēng)(周杰倫創(chuàng)作歌曲)龍卷風(fēng)(美國電影名稱)龍卷風(fēng)(動畫片《百變機(jī)獸之洛洛歷險記》角色)龍卷風(fēng)(楊鈺瑩、林翠萍、葉啟田演唱的歌曲)龍卷風(fēng)(游戲《游戲王》中魔法卡名稱)龍卷風(fēng)(口袋妖怪技能)龍卷風(fēng)(游戲《warcraft3》中技能名稱)龍卷風(fēng)(香港漫畫《九龍城寨》中的人物)龍卷風(fēng)(科普圖書《龍卷風(fēng)》)龍卷風(fēng)(skonec制作的同名游戲)龍卷風(fēng)(鄧紫棋翻唱歌曲)龍卷風(fēng)(黃錦祥詩歌《龍卷風(fēng)》)atednesstRelatednesselatednessangeContextRelatednessainContextRelatedness2018/8/30第5講：百科知識圖譜構(gòu)建282018/8/30第5講：百科知識圖譜構(gòu)建29?將已發(fā)現(xiàn)的實體分類到定義好的Taxonomy中的概念上?人工方法?基于規(guī)則的方法?基于機(jī)器學(xué)習(xí)的方法2018/8/30第5講：百科知識圖譜構(gòu)建30法進(jìn)行分類，參與人員包括領(lǐng)域?qū)nfobox2018/8/30第5講：百科知識圖譜構(gòu)建31基于規(guī)則的方法FTHEN?通用推理規(guī)則?基于等價實體關(guān)系的規(guī)則推理?e1ec?e1=e2?e2ec?基于概念子類關(guān)系的規(guī)則推理?eec1?c1?c2?eec2?啟發(fā)式推理規(guī)則?E.g.,實體名稱后綴為“步槍”的很可能屬于步槍?基于屬性的規(guī)則推理?E.g.,實體包含屬性“畢業(yè)院?！钡膶儆谌宋?E.g.,實體包含屬性-值對(職業(yè)，演員)的屬于演員2018/8/30第5講：百科知識圖譜構(gòu)建32模型訓(xùn)練實體分類結(jié)果特征提取訓(xùn)練數(shù)據(jù)(已分類的實體)模型測試數(shù)據(jù)(未分類的實體)基模型訓(xùn)練實體分類結(jié)果特征提取訓(xùn)練數(shù)據(jù)(已分類的實體)模型測試數(shù)據(jù)(未分類的實體)?訓(xùn)練集構(gòu)建?特征抽取?模型訓(xùn)練?結(jié)果預(yù)測2018/8/30第5講：百科知識圖譜構(gòu)建33AndyLau訓(xùn)練集構(gòu)AndyLau?直接作為訓(xùn)練集?人工方法?優(yōu)點：能保證訓(xùn)練集的質(zhì)量?缺點：高昂的人力成本限制了訓(xùn)練集的規(guī)模?遠(yuǎn)程監(jiān)督方法?優(yōu)點：可以自動標(biāo)注大量的數(shù)據(jù)?缺點：質(zhì)量難以保證dgeBaseAndyLauInstanceOfThingAndyLauInstanceOfAgentAndyLauInstanceOfPersonAndyLauInstanceOfArtistwledgeBaseingntnstanceOfPersonist2018/8/30第5講：百科知識圖譜構(gòu)建34遠(yuǎn)程監(jiān)督訓(xùn)練集質(zhì)量優(yōu)化?實體鏈接錯誤?實體特征缺失?將訓(xùn)練集分為N份，其中每N-1份作為訓(xùn)練集，用來過濾剩下一份的噪聲?每個分類器分別對實體進(jìn)行重新預(yù)測，與原結(jié)果比較，未預(yù)測出的結(jié)果?綜合多個分類器的噪聲數(shù)據(jù)，通過過濾策略對訓(xùn)練集進(jìn)行過濾?大多數(shù)投票過濾?一致性過濾集中的概念集合為{A,B,C,D}2018/8/30第5講：百科知識圖譜構(gòu)建35劉德華出演了最新電影《長城》劉德華出生于1961年9月劉德華出演了最新電影《長城》劉德華出生于1961年9月《忘情水》是劉德華的代表歌曲?一個實體用一組特征集合表示 (職業(yè)，演員) (職業(yè)，歌手) (代表作品，忘情水)香港人標(biāo)簽港臺男歌手藝人“劉德華”的單示例特征集合?多示例特征表示?一個實體用多個示例表示，每?每個示例可能只表示實體部分分類結(jié)果劉劉德華“劉德華”的多示例表示2018/8/30第5講：百科知識圖譜構(gòu)建36單示例實體分類?X=x1,x2,…,xi,…,xN?N為特征總數(shù)?Y=y1,y2,…,yi,…,yM?M為概念總數(shù)?問題歸類?多標(biāo)記分類(Multi-label?一個實體可以屬于多個概念?樸素貝葉斯?Logistic回歸?支持向量機(jī)?決策樹2018/8/30第5講：百科知識圖譜構(gòu)建37------?為每個概念分別構(gòu)建一個分類器?為每個分類器定義其正負(fù)樣本?正樣本?所有屬于該概念的實體?所有屬于該概念的父概念卻不屬于該概念的實體-++?預(yù)測過程fierPredictClassifierClassifierPredict02018/8/30第5講：百科知識圖譜構(gòu)建38MentionTyping人物歌手劉德華演員人物MentionTyping人物歌手演員MentionTyping人物MentionTyping人物歌手劉德華演員人物MentionTyping人物歌手演員MentionTyping人物??MentionTyping+TypeFusion劉德華出生于1961年9月劉德華出演了最新電影《長城》《忘情水》是劉德華的代表歌曲2018/8/30第5講：百科知識圖譜構(gòu)建39?基于人工特征的方法PL-SVM(NguyenandCaruana,2008)CLPL(Couretal.,2011)FIGERLingandWeld2012)FIGERMinGillicketal4)HYENAYosefetal012)ClusTypeRenetal2015)DeepWalkPerozzietal14)LINETangetal.,2015b)PTETangetal.,2015a)WSABIEYogatamaetal.,2015)AFETRenetal,2016)?基于神經(jīng)網(wǎng)絡(luò)的自動特征抽取?方法?HNM(Dongetal.,2015)?METIC(BoXuetal.,2018)?KNET(JiXinetal.,2018)2018/8/30第5講：百科知識圖譜構(gòu)建40TypeFusion?直接合并?一致性投票?大多數(shù)投票?帶約束合并?將其看作是一個整數(shù)線性規(guī)劃?最大化所有mention的分類結(jié)果?約束?概念互斥約束?一個實體不能同時屬于兩個語P(c1)×P(c2) P(c1,c2)?PMIcP(c1)×P(c2)?概念層次化約束人物歌手劉德華人物MentionTyping人物MentionTyping多示例實體分類：多示例學(xué)習(xí)方法人物歌手劉德華人物MentionTyping人物MentionTyping?輸入：一個實體的全部示例?輸出：一個實體的分類結(jié)果?方法?MIML-MAX?MIML-AVG?MIML-MAX-AVGMentionTypingMentionTyping劉德華出生于1961年9月劉德華出演了最新電影《長城》情水》是劉德華的代表歌曲(YadollahYaghoobzadehetal.,2017)2018/8/30第5講：百科知識圖譜構(gòu)建412018/8/30第5講：百科知識圖譜構(gòu)建422018/8/30第5講：百科知識圖譜構(gòu)建43識圖譜中的知識也不完整/item/周杰倫/item/劉德華2018/8/30第5講：百科知識圖譜構(gòu)建44?目標(biāo)?根據(jù)已有知識補全I(xiàn)nfobox關(guān)系?實體標(biāo)簽?實體正文2018/8/30第5講：百科知識圖譜構(gòu)建45利用實體標(biāo)簽進(jìn)行知識補全的一個重要信息g?(劉德華，職業(yè)，演員)?YAGO?Catriple?DFs2018/8/30第5講：百科知識圖譜構(gòu)建46?準(zhǔn)確率高?代價大?需要為每個關(guān)系定制一套正則表達(dá)式gorybirthsRNONDATE2018/8/30第5講：百科知識圖譜構(gòu)建47tt (Country,British) (artist,TheBeatles)?基于Pattern從上下位概念對(conceptpair)中抽取關(guān)系seBeatlessongs (HeyJude,artist,TheBeatles)2018/8/30第5講：百科知識圖譜構(gòu)建48?e.g.,Songsbyartist?e.g.,TheBeatlessongs?抽取方法?從上位概念抽取屬性?從下位概念抽取屬性值?(artist,TheBeatles)?e.g.,Songsbytheme?e.g.,Songsaboutdivorce?抽取方法?從上位概念抽取屬性?從下位概念抽取屬性值?(theme,divorce)2018/8/30第5講：百科知識圖譜構(gòu)建49?抽取方法?從下位概念抽取屬性值ritish?通過投票確定屬性值對應(yīng)的屬性untryBritish?抽取方法?從下位概念抽取屬性值lms?通過投票確定屬性值對應(yīng)的屬性nrefilms2018/8/30第5講：百科知識圖譜構(gòu)建50OstrichOstrichHasSkinCanMoveAroundAnimalBreathesHasFinsCanSwimHasHasFinsCanSwimHasGillsCanFlyHasFeathersinkIsinkIsEdibleSwimsUpstreamToLayEggsCanSingCanBiteThinLegsSalmonIsTaliSalmonYellowIsDangerousCanaryYellowIsDangerousCanarytal?概念的固有特征集合滿足兩個如果一個實體包括某個概念的固有那么它一定屬于這個概念?fc?fe?eec?應(yīng)用?如果一個實體屬于某個概念，那么?eec?fc?fe?應(yīng)用2018/8/30第5講：百科知識圖譜構(gòu)建51數(shù)據(jù)驅(qū)動的概念固有特征發(fā)現(xiàn)?心理學(xué)家通過人工方法為少量義了它們的固?缺點標(biāo)簽InfoboxJayChoualbums(artist,JayChou)peAlbumAmericanscreenwriters(birthPlace,UnitedStates)(occupation,Screenwriter)ersonAmericancrimefilms(country,UnitedStates)(genre,crime)ypeFilm?自動方法ingS2:規(guī)則發(fā)現(xiàn)SS2:規(guī)則發(fā)現(xiàn)固有特征集合發(fā)現(xiàn)RulesofRulesofC-DFsS3:基于規(guī)則的固有特征集合發(fā)現(xiàn)C-DFsS4:知識圖譜填充2018/8/30第5講：百科知識圖譜構(gòu)建52利用實體文本內(nèi)容進(jìn)行知識補全識Lau金馬獎最佳男主角…2018/8/30第5講：百科知識圖譜構(gòu)建53基本思路?為每個屬性構(gòu)建一個抽取器(分類器)中抽取出相應(yīng)屬性的值Lau “英文名稱”Lau“出生日期”劉德華(Andy“出生日期”出生地 “出生地”出生地2018/8/30第5講：百科知識圖譜構(gòu)建54序列數(shù)據(jù)標(biāo)記問題列數(shù)據(jù)標(biāo)記問題?將句子當(dāng)做是一個序列數(shù)據(jù)?屬性值抽取過程即可看作是序列數(shù)據(jù)標(biāo)記過程?1表示為屬性值?0表示不是屬性值“英文名稱”“出生日期”“出生地”“英文名稱”“出生日期”“出生地”|0|0|0|0||0|0|0|0||0|1|1|0|傳統(tǒng)方法?條件隨機(jī)場(CRF)?針對序列數(shù)據(jù)進(jìn)行分類的模型?每個詞組需要人為設(shè)定一組特征?需要專家人為設(shè)計特征?不具有通用性2018/8/30第5講：百科知識圖譜構(gòu)建56基于深度學(xué)習(xí)的方法?不需要人工設(shè)計特征方法?LSTMal2018/8/30第5講：百科知識圖譜構(gòu)建570101010 1010101010101010101YLLLLLLLLLLRRRRRRRRRRRRRRWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCC234567890101010 1010101010101010101YLLLLLLLLLLRRRRRRRRRRRRRRWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCCWCC2345678901LRWCC11劉德華(AndyLau)，1961年9月27日出生于中國香港。 (dy)，于1234567892018/8/30第5講：百科知識圖譜構(gòu)建58基于深度學(xué)習(xí)的方法?不需要人工設(shè)計特征方法?LSTM?LSTM+CRFal2018/8/30第5講：百科知識圖譜構(gòu)建59基于多源的百科圖譜構(gòu)建 2018/8/30第5講：百科知識圖譜構(gòu)建60基于多源的百科圖譜構(gòu)建?目標(biāo)?輸入?每個百科知識圖譜均由一個獨?輸出合后的百科知識圖譜?步驟?概念對齊?實體對齊?屬性對齊?屬性值融合2018/8/30第5講：百科知識圖譜構(gòu)建61概念對齊?跨語言統(tǒng)一概念表示2018/8/30第5講：百科知識圖譜構(gòu)建62[Zhuang[ZhuangYanetal.,2016.]?AlignentityKB1,KB2=e1,e2,cone1eKB1,e2eKB2,cone0,1?con值越大，表示兩個實體越相似KB1對KB2KB1KB2KB1KB2?預(yù)處理?分塊索引?成對對齊?集體對齊譜構(gòu)建[ZhuangYanetal.,2016.]632018/8/30第5講：百科知識圖譜構(gòu)建64預(yù)處理和分塊索引?處理數(shù)據(jù)的多源異構(gòu)性、數(shù)據(jù)定義的不一致性、數(shù)據(jù)表達(dá)的多樣性等?方法?標(biāo)點去除?分塊索引?通過剪枝過濾掉知識庫中不可能相似的實體對，使得相似的實體對盡量分配到一個或幾個區(qū)塊中成為候選對，最終的對齊處理只在這些候選對中進(jìn)行，從而達(dá)到?索引鍵值選擇的考慮因素?特征的質(zhì)量?特征的分布2018/8/30第5講：百科知識圖譜構(gòu)建65成對實體對齊方法?基于屬性相似性?轉(zhuǎn)化為分類問題(匹配、可能?機(jī)器學(xué)習(xí)方法?二元分類問題(匹配，不匹配)?監(jiān)督學(xué)習(xí)方法?SVM?LogisticRegression?DecisionTree?FactorGraph?HeterogeneousNetworkEmbedding2018/8/30第5講：百科知識圖譜構(gòu)建66集體實體對齊方法?基于簡單關(guān)系的集體實體對齊?在計算實體相似性的時候，將實體的關(guān)聯(lián)實體屬性納入計算，即考慮待節(jié)點當(dāng)作平等的實體去計sime1,e2=a×simAttre1,e2+1?a×simNB(e1,e2)2018/8/30第5講：百科知識圖譜構(gòu)建67集體實體對齊方法?基于實體對齊是相互影響的觀察，通過不同匹配決策之間的相互影響調(diào)?方法?基于相似性傳播方法?基本思路?通過初始匹配以bootstrapping方式迭代地產(chǎn)生新的匹配?基于概率模型方法?基本思路?方法2018/8/30第5講：百科知識圖譜構(gòu)建68舉例：跨語言實體對齊?目標(biāo)?將百度百科中的中文實體和維?英文維基實體?中文維基實體?標(biāo)題?超鏈接?標(biāo)簽?作者2018/8/30第5講：百科知識圖譜構(gòu)建69舉例：跨語言實體對齊方法?LinkageFactorGraphModelY={yi}點特征函數(shù)邊特征函數(shù)約束特征函數(shù)xi=ai1,bi22018/8/30第5講：百科知識圖譜構(gòu)建70刪除錯誤屬性對刪除錯誤屬性對找到候選屬性對找到候選屬性對?屬性名稱相似性?e.g.,英文名，英文名稱?同義詞相似性?數(shù)據(jù)驅(qū)動的屬性對齊方法?人工錄入?啟發(fā)式規(guī)則?等價屬性不同時出現(xiàn)在一個實體中?等價屬性domain和range相同?人工刪除2018/8/30第5講：百科知識圖譜構(gòu)建71屬性對齊?屬性名稱相似性?e.g.,(英文名，英文名稱)?方法?同義詞相似性?e.g.,(妻子，老婆)?利用外部同義詞庫?特有方法?知識圖譜中的三元組(S,P,O)?每個屬性Property包含多個?屬性值O類型相似度?屬性的S-Opairs的overlap程度2018/8/30