知識圖譜前沿課程 | 知識圖譜的質量控制

05-14

知識圖譜前沿課程是一個系列課程，已經在復旦大學、華東師範大學、蘇州大學舉辦了三次，該課程旨在集中展示知識圖譜的當前在學術界和工業界的進展，討論現有主要問題，為下一步知識圖譜方向的研究工作做好規劃。
知識圖譜前沿課程（華東師範大學站）是由復旦大學知識工場實驗室負責人肖仰華教授、華東師範大學林欣教授和蘇州大學李直旭教授組織並參與主講的課程。
本文整理自蘇州大學李直旭教授在知識圖譜前沿課程（華東師範大學站）所做的報告，題目為《知識圖譜的質量控制》。

獲取完整PPT，請前往 Workshop 2017

非常榮幸有這個機會來華師大與大家分享我們在知識圖譜質量控制方面的一些工作。

我今天主要介紹以下幾部分內容，首先，從資料庫的角度去看傳統的數據質量問題。其次，看看在知識圖譜構建當中可能會遇到什麼樣的數據質量問題。

大家都知道，近十年數據呈爆炸式增長，在爆炸式增長的背後，數據質量卻在急劇下降。

這張圖呈現出幾根曲線，其中有一條線是數據的容量，可以看到容量越來越大。現今我們每一個企業或者個人都可以去產生大量的數據，致使數據的多樣性也在逐步提高。但是我們同樣可以看到，人類社會的知識量並沒有因為數據量的劇增也同步急劇增長，而是呈平滑的增長態勢。知識量變化不大，但數據量卻急劇增長，這種現象說明，數據質量是在急劇下降的。

針對數據質量下降這個問題，不管是資料庫學者，還是企業人士都十分關注。這裡舉幾個簡單的例子，介紹一下數據質量主要關注哪些問題。首先是DBLP的例子，DBLP相對來說是一個結構化的，質量比較高的資料庫，這裡可以檢索到大量學者，特別是資料庫學者的論文。針對這個資料庫，可以舉一個簡單的例子，我的一個研究生同學，他在出國之前的名字是「Pei Li」，但是出國後發現，國外「Li」的發音不像中文裡的發音，於是把名字改成了「Pei Lee」，這樣一來，DBLP里就有兩個關於他的頁面，但實際上這兩個頁面上的論文都是同一個人發表的，搜索者如果只是知道他原來的名字，但是想追蹤他後面的工作的話，可能就會遇到問題了。另外一個例子就是，叫「Wei Wang」的人其實很多，「Wei Wang」就相當於一詞多義，這種情況在資料庫里就會造成很大的麻煩，光是「Wei Wang」在DBpedia里就有十幾個，有一些會標註其所在的單位，但是如果搜索者不了解這個人，或者有些新出來的「Wei Wang」是沒有標註的話，就很有可能會把他們的工作混在一起，這樣也會造成搜索者的困擾。

還有一個關於搜索引擎的例子，用戶搜索一個關注人物，可能不同的用戶對同一個關注人物名稱的叫法是不一樣的，或者說可能會輸錯字，比如小甜甜布朗尼，她的名字不算難拼，但是在圖片上呈現的Google里一個小時的搜索記錄，就出現這麼多各種不同的拼法。這也說明了用戶在輸入搜索關鍵字的時候，也是會有數據質量問題的，這也會造成後續處理的困擾。

還有一個例子就是最常見的資料庫，像圖片里的這些信息，這些信息在不同的學校或者公司系統里，大家登記的標準，填寫的信息量都是不一樣的，如果公司想要統計數據，各個部門的數據想要整合起來，實際上就會遇到數據融合的問題。這個問題其實也困擾著很多公司內部系統。

簡單來說，數據質量主要分為以下六個維度，首先，是否是一個完整的數據，裡面有沒有空缺；其次，是否是有效數據，數據表述是否正確，會不會造成誤解；第三，數據的準確性是否高；第四，資料庫里的數據是否一致，有沒有相互矛盾的地方；第五，數據在物理意義上是否完整性，比如說某人填寫畢業學校，但如果這個學校根本就不存在，那麼就是缺失完整性。第六，數據的時效性，是否是當下最新的數據。

從另外一個角度看數據質量，這張圖就可以概括一下，數據質量主要是單源數據和多源數據問題。單源的數據可能涉及到模式的好壞問題。而實例相關，就是看有沒有拼寫錯誤，冗餘，矛盾的數據。多源數據的質量問題就更多了，首先在模式層，如果多個資料庫要做融合的話，這些資料庫的數據模式是否一致，如何把表圖融合到一起等等，都要進行考慮。實例相關的問題也很多，包括表述是否一致，時間點和聚集層級是否一致等，這些都會在數據融合時造成困擾。

其實大家關注的問題就是這幾點，首先是數據融合，這裡面包括表圖的融合，記錄的匹配。第二個問題，就是錯誤數據的發現和糾正。第三個大問題是數據的填補，如果有一些缺失數據，特別是比較重要的缺失數據，應該如何處理，是在統計學上找一個代替？還是去發現它的真實值？

DataProvenance，這個是數據溯源，國家網信辦很注重謠言在網上的傳遞，所有謠言都要追溯到源頭，數據溯源問題不光是在網路上存在，在各種信息系統和資料庫里都會存在。還有一個Data uncertainty，也就是數據的不確定性，我們不可避免包含概率的真實數據，這種數據該如何處理，傳統的資料庫，一個空只能填寫一個數據，但是包含概率的話，一個空可能有兩到三個不同的答案，需要思考如何把包含概率的真實數據作為一個新的形式存在下來。還有就是數據的約束條件，這些條件可以輔助我們約束數據質量，提高數據質量。

剛才簡要的介紹了一下在數據質量方面大家關注的點，接下來我們講一下，在構建知識圖譜的時候會遇到什麼樣的數據質量問題。第一個就是數據清洗，我們在構建知識圖譜的時候，如何清洗裡面的錯誤數據。

構建知識圖譜不光是利用結構化數據，更多的時候，是從文本類非結構化數據中提取相關信息。現在有很多這方面的工作，像KnowItAll, SnowBall, probase等，實際上都是藉助自然語言處理的技術，做迭代學習，發現更多的實例，放到資料庫裡面。但是我們發現迭代的機制往往存在很大的問題，剛開始迭代可能質量比較高，但是幾輪迭代過後，就會發現數據質量是急劇下降的。這個統計圖是微軟亞洲研究院probase的數據，第一輪的時候質量是比較高的，可能百分之八九十，但是在幾輪迭代以後，因為每次得到的新的內容都是基於剛剛學到的內容，然後再去學到新的模式，這樣就會造成質量下降的非常快。

這樣還會存在噪音引入的問題。圖裡表示的是兩種機制如何引入噪音。第一個機制叫Semantic-based bootstrapping mechanism， S1的這句話「animals such as dog，cat,pig and chicken grow fast」。這句話里我們實際上可以得到的是isA關係，如果知道chicken是一種animal的話，那麼pig、 cat、 dog 在這句話里也應該被解析為一種動物，這句話解析出來當然是正確的。但是，接下來第二輪就會出問題，chicken可能會幫助系統去解析S3「common food from animals such as pork，beef and chicken」，這句話可以發現，其實前面有兩個概念，一個是food，一個是animal，後面有三個實例，很顯然，這三個實例是一種food，並不是animal。但是資料庫在第一輪的時候僅僅知道，chicken是一種animal，那麼在第二輪的時候就很有可能把pork，beef也列入animal中，由此就會造成一些噪音，接下來pork，beef會把大量的food捲入到animal裡面，這就造成了數據質量的大幅度下降。

還有一個機制Syntax-basedbootstrapping mechanism，這個機制是，一開始有一些種子實例，根據種子實例可以學習到一些模式，模式又會幫助找到更多的新實例到animal這個概念裡面，但是如果我們發現的模式不僅僅適用於animal的話，比如P2這個模式「sometimes，X is as clever as human beings」，跟人一樣聰明的，不光是動物，也可能是robot或者是computer，這種情況，就會引入噪音到animal裡面，往後噪音會越來越多。

為了解決這個問題，現有工作有很多，下面介紹幾個主流的方法。

首先是Mutual ExclusionBootstrapping，就是在做迭代的時候，要考慮到當下學到的實例或者模式是不是僅僅屬於一個概念，會不會在多個概念中被提及，如果在多個概念中提及，這個學到的實例或者模式就會被拋棄，這樣會損失一些召回率，但是能保證精確度。

第二個是傳統的自然語言處理，進行一些語法分析，標註實體類型，自然語言處理是可以標註到機構，人物，地點這樣的層次的，如果實體是一個學校，那麼首先它得是一個機構，如果一開始都不滿足type這個規定的話，那麼它肯定不會是目標概念下的實例。我們可以通過簡單的type把它去除掉。

第三種是Random WalkRanking，這個方法先進一點，簡單來說，就是把所有學到的實例和模式構成一個圖，圖的邊表示被抽取的次數，最後在圖上去做Random Walk。穩定下來以後，可以把出現的次數比較少，比較偏的實體和模式刪除掉，這種做法有高效合理的地方，當然也存在問題，有一些長尾的概念或者實體，實際上就是被抽取的次數很少的，貿然刪除可能造成大量召回率的損失。

還有一種是Pattern-Relation Duality Ranking，基本思路也是通過輸入一些種子實體，希望學習到一些模式，學習模式的過程是藉助一些搜索引擎，搜索到一些相關的文本，從文本里抽取相關的模式，最後把模式形成可以用來作為下一次抽取的有效的新模式。得到新的模式以後，可以再次利用搜索引擎，搜到相關的文檔，再從文檔里抽取關注的新的實體。這個過程跟前面的SnowBall是很類似的，只不過這個方法藉助了搜索引擎。這個方法還有一個可取之處，就是每一輪做迭代的時候，都會注意去做一個質量控制，做質量控制的時候也用到了Random Walk的思想，但是它考慮到了精確率和召回率兩個方面。每一個點是一個實體或模式，這個方法需要把每一個點上的精確率和召回率都標註出來，這樣會形成兩個圖，在圖上再去做Random Walk，迭代之後會有精確率的值和召回率的值。這種方法比單純的Random Walk會好一點。

最後介紹一下在這個問題上我們所做的工作，以上的方法都有可取之處，可以很好的提高精準率，但是往往會犧牲非常大的召回。剛才提到的工作都是藉助一些可能會發生錯誤的特徵去做的，嘗試抓住特徵，然後刪除掉。事實上，特徵並不是一個一定的東西，每一個錯誤都有自己錯誤的原因，我們研究發現，錯誤的發生都是有一個起始點的，我們稱這個起始點是Drifting Point，就是漂移發生點。漂移點有更明顯的特徵，如果能發現這些點，把由它引起的相關的指令去除掉，這樣就可以避免錯刪很多正確的實體，也可以很好的去抑制錯誤的引入。

我們通過研究發現漂移點大概有兩種，一種是一詞多義的漂移點，像上面舉的chicken的例子一樣，chicken本身就是一個多義詞，既是雞肉，又可以表示小雞。還有一種漂移點，它本身是單義詞，由於在網頁解析的時候出錯，造成錯誤的引入，比如說「Countries such as France, Germany, Japan and New York」，可以看出such as後面應該都是指國家，但是出現了一個New York，這個new York可能本意想指美國，但是寫成了一個城市，這就是一個錯誤的引入，New York在接下來的迭代里可能會引入更多的錯誤。類似這種錯誤一旦發現，我們就會終止，不讓它繼續引入新的錯誤。

根據以上漂移點的兩個定義，我們發現了許多漂移點的特徵。第一個特徵是，由漂移點所引發的在後繼輪的抽取結果，應該跟同一個概念里其他的實體抽取結果是不一樣的。如圖所示，「chicken」引發的結果跟其他的就不一樣。第二個特徵是，如果是一個多義詞的話，那應該在多個概念里可以學習到。第三個特徵是，通常情況下，如果是一個偶發的錯誤，這樣的漂移點是很少出現的，被抽取到的概率很小。第四個特徵是，由一個漂移點引發的錯誤抽取，很少能被非漂移點支持。基於以上這幾點，我們可以建一個比較複雜的模型，把這些特徵放進去。模型細節不述，有興趣可以去看論文。

這個模型可以發現大量的這兩類漂移點，基於這兩類漂移點，看看如何可以消除裡面的錯誤。我們是從一句話這樣的一個單元裡面抽取信息，對於一句話的處理，首先看這句話是不是由偶發的漂移點所引發的，如果是，我們就可以全部拋棄，如果不是，可以繼續看是不是被多義詞漂移點所引發，如果不是，就留下，因為這樣就可以推斷出它不是由任何一類漂移點引起的。如果是由多義詞漂移點引起的，就應該去計算一下，因為有時候多義詞的漂移點所引發的是對的，有時候引發的是錯的，不能一概而論拋棄或者留下，這個時候需要考慮的就比較多。

這個方法我們在幾個數據集上做過實驗，一個是微軟的Probase，還有一個是英文常用的數據集，最後發現我們的方法對錯誤的識別率是非常高的，基本上可以達到百分之九十多，清洗過的數據的精確率和召回率都已經高了很多，清洗之前是百分之四十多，清洗完了之後可以達到百分之八十多。

接下來介紹在知識圖譜構建當中的第二個問題——實體鏈接。實體鏈接在知識圖譜里是非常重要的，因為每一個實體的表達，最終還是落實到詞，而詞的表達是千差萬別的，同一個詞可能有多種表達意思，不同的詞也可能會有同一個意思。歸納一下，實體鏈接就是兩個問題，一個是一詞多義，一個是多詞一義。

一詞多義這裡舉的例子是Jordan，這句話是「Duringhis standout career at Bulls, Jordan also acts in the movies Space Jam.」顯然這句話大家看完都知道，講的是球星Michael Jordan，但是現實生活中，尤其是在美國，光是知名人物，叫Michael Jordan的就有好幾個，不光是NBA球員，還有一個伯克利的教授，一個美國的演員，這種情況下，如果我們想把這句話里的Jordan對應到知識圖譜的實體，那到底應該對應哪一個Jordan呢？這個就是一詞多義引發的問題。只有正確解析Jordan，才能得到剩下的相關信息。

關於這個問題，所做工作也相當多，我們介紹以下幾個方法，還是以Jordan的例子為例。

第一個方法是純粹基於本地的知識。簡單來說，這所有的黑色的框裡面，裝的都是知識圖譜里的實體，三個白框是剛才這句話里解析出來的三個詞，知識圖譜里的實體和剛解析出來的三個詞，它們之間都是有概率匹配的，從圖中可以看出Jordan和bulls這兩個詞都是有歧義的，我們就要做消歧工作，看看到底是跟哪個實體能鏈接上。

第二種方法慢慢就提升了一些，會從詞與詞的關聯角度去考慮，這句話里明明有三個詞，按道理，在一定語境下，兩個詞的關聯度是非常高的，那就可以藉助沒有歧義的那個詞，幫助我們去跟實體做對應，比如說，這句話里說Jordan參演了一部電影，而這個電影跟資料庫里的電影是沒有歧義的對應的，這句話里的電影跟這個Jordan也是完全對應的，這樣就可以找出正確的實體。

第三個方法，可以提高準確率，但是很耗時間，效率比較低。

最後一個方法是用一個圖去表現所有的關係，最後整個圖是去做Random Walk也好，還是大圖上的分析也好，發現這三個詞跟哪個實體的接近度是最高的，從而達到實體鏈接的目的。

多詞一義舉的是奧巴馬的例子，奧巴馬全稱貝拉克·海珊·奧巴馬，但很少會去這樣表述，特別是在資料庫，都會表述的很簡單，那同一個詞，就比如奧巴馬，如何去識別？

第一種方法比較原始，但是用得也很多，純粹基於String method去做一個匹配，像Edit Distance, Jaccard, Cosine, Hybrid Metrics，發現兩個實體純粹在文字上有什麼相似性，從而去做一個匹配，這個匹配在某些時候是比較有效的，但是不同的場景，要選取不同的匹配方法，才能起效果。

第二種方法是Collective alignment methods。比如已經有一個這樣的訓練集，希望發現一些特徵，然後建立一個匹配模型，把相關技術拿過來，去做一個概率匹配。

第三種方法是直接把兩個知識庫做實體鏈接。這兩個知識庫可能是不同語言的，也可能是不同表達方式的，如圖，已經有一些鏈接好的種子，根據這個種子，期望可以學習到圖中這樣的矩陣，根據這個矩陣，我們可以學習到知識庫里剩下的數據可以通過怎樣的轉換，跟另外一個知識庫里的數據做好關聯關係。

（由於時間關係，後面不多做陳述，大家有興趣可以自行下載PPT。）

最後總結一下，現在是大數據時代，同樣也是大量臟數據時代，數據量大了，機遇也大，可以用大數據做很多事情，同時也提出了很多的挑戰。大資料庫里的數據可以輔助我們做一些本地資料庫上的清洗、整合，以獲得更高的精確率和召回率。同時，我們也需要關注為了達到這個目的，所要在時間效率、空間效率、人力成本各方面付出的代價。

謝謝大家！