賈丙靜，張振強(qiáng)

（安徽科技學(xué)院信息與網(wǎng)絡(luò)工程學(xué)院，蚌埠 233000）

0 引言

大數(shù)據(jù)時(shí)代，網(wǎng)絡(luò)中每天都會(huì)產(chǎn)生大量的文本、圖片和視頻等數(shù)據(jù)，這些數(shù)據(jù)來(lái)源多、規(guī)模大、表述不規(guī)范，為人們獲取知識(shí)帶來(lái)了極大的挑戰(zhàn)。知識(shí)圖譜［1］以圖的形式幫助人們組織現(xiàn)實(shí)世界中雜亂無(wú)章的數(shù)據(jù)，實(shí)現(xiàn)客觀世界的知識(shí)映射。它的基本組成單位是三元組<實(shí)體，關(guān)系，實(shí)體>，其中實(shí)體表示真實(shí)世界中存在的客觀事物，如人、國(guó)家和公司等；關(guān)系則表示不同實(shí)體之間的某種聯(lián)系，如某個(gè)影視明星和某個(gè)電影之間的主演關(guān)系，某個(gè)教師和某個(gè)課程之間的講授關(guān)系等。目前比較流行的知識(shí)圖譜有Wikipedia［2］、Freebase［3］、復(fù)旦大學(xué)的CN-DBpeida［4］和清華大學(xué)的XLore［5］等。知識(shí)圖譜能夠?yàn)檎Z(yǔ)義檢索、智能問(wèn)答和情感分析等提供知識(shí)支撐，然而，知識(shí)圖譜普遍存在不完備的問(wèn)題，現(xiàn)實(shí)世界中知識(shí)是不斷變化的，人們對(duì)世界的描述也在不斷更新和修正。因此，為了更好地滿足系統(tǒng)應(yīng)用的需求，必須不斷地對(duì)知識(shí)圖譜進(jìn)行知識(shí)擴(kuò)充。早期的知識(shí)圖譜通常依賴人工構(gòu)建和擴(kuò)充，不僅效率低而且成本極高，針對(duì)上述問(wèn)題，擬從實(shí)體鏈接的角度進(jìn)行知識(shí)擴(kuò)充，將文本中挖掘的新實(shí)體鏈接到已有的知識(shí)庫(kù)中。為了提高實(shí)體鏈接的效果，首先研究如何學(xué)習(xí)多源、多模態(tài)和異質(zhì)的數(shù)據(jù)表示，并對(duì)這些特征進(jìn)行篩選和融合；然后使用ID3決策樹(shù)算法對(duì)待鏈接數(shù)據(jù)進(jìn)行深層次分析，實(shí)驗(yàn)結(jié)果表明該算法能夠去除噪音，將實(shí)體鏈接到知識(shí)庫(kù)正確的候選上，從而達(dá)到知識(shí)擴(kuò)充的效果。

1 研究現(xiàn)狀

知識(shí)擴(kuò)充是提高知識(shí)圖譜完整性的重要手段，已發(fā)展成為自然語(yǔ)言領(lǐng)域新的研究熱點(diǎn)。其主要目標(biāo)是將網(wǎng)絡(luò)中獲取的新知識(shí)與知識(shí)圖譜中已有的知識(shí)進(jìn)行關(guān)聯(lián)，更新到知識(shí)圖譜中。目前文本中獲取的實(shí)體與知識(shí)圖譜中的實(shí)體的關(guān)系類別有兩種，一種是在知識(shí)圖譜中能找到映射實(shí)體，即通過(guò)實(shí)體鏈接［6］方法就可以擴(kuò)充知識(shí)圖譜；另一種是在知識(shí)圖譜中不存在映射實(shí)體，需要通過(guò)實(shí)體分類［7］的方法進(jìn)行知識(shí)合并。其中，實(shí)體鏈接獲得了研究人員的廣泛關(guān)注，主要包括單實(shí)體鏈接和集成實(shí)體鏈接兩種方法。單實(shí)體鏈接表示在把實(shí)體鏈接到知識(shí)圖譜的過(guò)程中不考慮同一文本中其它實(shí)體對(duì)其的影響，MPME 模型［8］認(rèn)為實(shí)體的歧義會(huì)影響相同語(yǔ)義空間的建模，對(duì)于字面表達(dá)相同的實(shí)體采用同一向量表示顯然是不全面的，因此聯(lián)合文本和知識(shí)圖譜為不同含義的實(shí)體學(xué)習(xí)不同的特征。

EAT模型［9］把文本中的實(shí)體和知識(shí)圖譜中的實(shí)體放在同一個(gè)文本序列中，來(lái)學(xué)習(xí)對(duì)象的統(tǒng)一表示，避免單獨(dú)學(xué)習(xí)后的重新對(duì)齊。集成實(shí)體鏈接在實(shí)現(xiàn)的過(guò)程中綜合考慮上下文待鏈接實(shí)體之間的語(yǔ)義相關(guān)性，進(jìn)行聯(lián)合推斷?；诰W(wǎng)狀結(jié)構(gòu)的圖可以表示對(duì)象之間的復(fù)雜關(guān)系，為集成實(shí)體鏈接提供了新的思路。REL-RW 模型［10］認(rèn)為當(dāng)前的主流方法對(duì)一些不知名的實(shí)體指稱可能并不適用，由此提出在構(gòu)建圖時(shí)不僅要考慮知識(shí)圖譜中實(shí)體之間的直接關(guān)聯(lián)，還要考慮它們的間接聯(lián)系，在信息論的基礎(chǔ)上綜合考慮所有候選實(shí)體的相關(guān)度。PPRSim［11］模型通過(guò)個(gè)性化隨機(jī)游走結(jié)合整篇文檔的語(yǔ)義特征能過(guò)濾掉非正確候選實(shí)體帶來(lái)的噪音。但是，有些模型只考慮了部分特征，沒(méi)用充分利用不同粒度級(jí)別的信息，為了改善鏈接的效果，需要使用各層次的信息，并對(duì)這些信息進(jìn)行篩選。因此，分別使用詞向量、先驗(yàn)流行度和編輯距離來(lái)學(xué)習(xí)待鏈接實(shí)體的詞語(yǔ)級(jí)別、統(tǒng)計(jì)級(jí)別和文檔級(jí)別的特征，然后基于ID3決策樹(shù)算法對(duì)這些特征進(jìn)行篩選，并預(yù)測(cè)最終的鏈接結(jié)果。

2 ID3決策樹(shù)算法

2.1 基本原理

ID3算法屬于有監(jiān)督學(xué)習(xí)，通過(guò)構(gòu)建樹(shù)模型將數(shù)據(jù)分類，每次通過(guò)信息增益來(lái)選擇劃分的屬性，即每次選擇信息增益最好的屬性，體現(xiàn)了屬性與標(biāo)簽之間的函數(shù)映射關(guān)系。信息增益和信息熵是ID3算法中描述樣本集合純度的一種常用指標(biāo)，假設(shè)當(dāng)前樣本集合S中第i個(gè)樣本所占的比例是Pi，則S的信息熵可以表示為

其中，k表示數(shù)據(jù)集S中樣本預(yù)測(cè)結(jié)果的種類，Ent(S)越大，數(shù)據(jù)集S的純度越高。

同樣，設(shè)屬性t還有W個(gè)可能的特征值t1,t2,…,tw，利用屬性t對(duì)數(shù)據(jù)集S進(jìn)行分類，將產(chǎn)生W個(gè)分支節(jié)點(diǎn)，其中第W個(gè)分支節(jié)點(diǎn)包含S中所有在屬性t上取值為tw的樣例，記為SW，然后根據(jù)公式（1）計(jì)算出信息熵。由于不同分支節(jié)點(diǎn)所包含的數(shù)據(jù)個(gè)數(shù)不同，給每個(gè)分支節(jié)點(diǎn)賦予一個(gè)權(quán)重 |S|，即數(shù)據(jù)個(gè)數(shù)越多的分支節(jié)點(diǎn)對(duì)預(yù)測(cè)性能影響越大，于是可以計(jì)算出屬性t劃分?jǐn)?shù)據(jù)集S所獲得的信息增益，其公式為

2.2 算法流程

對(duì)于給定數(shù)據(jù)集，每個(gè)樣本上的屬性可能有多個(gè)，不同屬性對(duì)分類的作用有大有小，而決策樹(shù)的實(shí)現(xiàn)過(guò)程就是不停地確定跟分類標(biāo)簽最相關(guān)的屬性。ID3算法實(shí)現(xiàn)流程為：①對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，初始化根節(jié)點(diǎn)包含所有的數(shù)據(jù)；②遍歷所有的屬性，選擇信息增益最大的屬性作為決策樹(shù)的根節(jié)點(diǎn)，并將此屬性刪除；③根據(jù)根節(jié)點(diǎn)將數(shù)據(jù)分叉，在剩余的屬性中遞歸地尋找每個(gè)分支的最優(yōu)屬性；④當(dāng)決策樹(shù)到葉子節(jié)點(diǎn)或者數(shù)據(jù)已經(jīng)不需要再分，算法停止。

3 信息處理

3.1 實(shí)體嵌入

詞嵌入通過(guò)詞向量描述一個(gè)詞，計(jì)算詞與詞之間的語(yǔ)義相似度。Le 等［12］認(rèn)為如果一個(gè)詞經(jīng)常和另一個(gè)詞一起出現(xiàn)，那么它們是相似的。然而，詞嵌入模型忽略了短語(yǔ)或?qū)嶓w內(nèi)在的意義。以Wikipedia 為例，候選實(shí)體之間是有關(guān)聯(lián)的，錨文本和單詞也可能同時(shí)出現(xiàn)在一篇文章中，這就為在同一連續(xù)空間中聯(lián)合學(xué)習(xí)詞和實(shí)體的嵌入提供了便利條件。最新研究表明通過(guò)學(xué)習(xí)實(shí)體和詞的嵌入可以提高實(shí)體鏈接的效果，Yamada 等［13］先從Wikipedia中提取豐富的結(jié)構(gòu)化信息，再設(shè)計(jì)Wikipedia2Vec 學(xué)習(xí)高質(zhì)量的單詞和實(shí)體嵌入。在訓(xùn)練詞和實(shí)體向量時(shí)，從Wiki?pedia中抽取文本和錨文本，并基于鏈接結(jié)構(gòu)測(cè)量候選實(shí)體對(duì)之間的關(guān)系，因此可以同時(shí)得到詞和候選的嵌入。υ(m)和υ(e)分別表示文本中的實(shí)體向量和知識(shí)圖譜中的候選實(shí)體向量，它們之間的相似度可以通過(guò)公式（3）的余弦相似度計(jì)算。

3.2 實(shí)體流行度

實(shí)體流行度表示實(shí)體的流行程度，它是基于知識(shí)圖譜的一種統(tǒng)計(jì)特征。根據(jù)知識(shí)圖譜中候選實(shí)體的超鏈接信息計(jì)算得到，在不知道上下文的情況下，觀察候選實(shí)體是文檔中實(shí)體鏈接對(duì)象的概率。例如，“李白”有90%的概率指向“李白（唐代著名浪漫主義詩(shī)人）”，10%的概率指向“李白（李榮浩演唱歌曲）”，參照文獻(xiàn)［14］中的方法計(jì)算實(shí)體流行度。

3.3 實(shí)體上下文

實(shí)體本身的名字包含的字符信息比較少，表層特征差異性比較大，無(wú)法提供足夠的證據(jù)進(jìn)行鏈接。而圍繞實(shí)體的上下文中含有一些關(guān)鍵信息，比如當(dāng)實(shí)體“李白”的周圍出現(xiàn)“詩(shī)詞”或者“唐代”等信息時(shí)，就暗示該實(shí)體鏈接的對(duì)象是詩(shī)人“李白”而不是歌曲“李白”。另外，候選實(shí)體所在的背景知識(shí)圖譜也提供了豐富的文本信息，可以基于編輯距離對(duì)待鏈接實(shí)體和候選實(shí)體的上下文語(yǔ)義關(guān)聯(lián)度進(jìn)行分析。編輯距離表示一個(gè)字符串轉(zhuǎn)化為另一個(gè)字符串需要的最少編輯次數(shù)，可進(jìn)行的操作有：替換、插入和刪除，距離越小說(shuō)明它們?cè)较嗨疲瑢?shí)體m和待鏈接候選實(shí)體e之間的上下文相似度可以通過(guò)公式（4）計(jì)算得到，其中max len(m,e)表示二者中的較長(zhǎng)者。

4 實(shí)驗(yàn)結(jié)果

背景知識(shí)圖譜采用Wikipedia 官方網(wǎng)站提供的2016 年4 月版本，里面包含豐富的上下文描述文本，鏈接信息和類別信息等。同時(shí)，利用詞向量工具wikipedia2vec 學(xué)習(xí)實(shí)體嵌入，維度是300。選擇在AIDA 標(biāo)準(zhǔn)數(shù)據(jù)集上驗(yàn)證模型效果，它是Hoffart 等［15］在CoNLL2003 的基礎(chǔ)上重新標(biāo)注的，整個(gè)數(shù)據(jù)集包含1393 篇新聞文檔，被劃分為訓(xùn)練集AIDA-Train，驗(yàn)證集AIDA-A和測(cè)試集AIDA-B三部分。

利用精確率、召回率和F1 值來(lái)客觀評(píng)估實(shí)驗(yàn)結(jié)果，只考慮在背景知識(shí)圖譜中能找到對(duì)應(yīng)鏈接對(duì)象的實(shí)體，假設(shè)T表示測(cè)試數(shù)據(jù)集中所有待鏈接實(shí)體在知識(shí)圖譜中的正確結(jié)果集合，O表示決策樹(shù)算法的輸出結(jié)果，可根據(jù)公式（5）、（6）和（7）計(jì)算決策樹(shù)算法在該數(shù)據(jù)集上的精確率（P）、召回率（R）和F1值。

ID3是一種貪心算法，在構(gòu)造決策樹(shù)的過(guò)程中，除了計(jì)算特征的信息增益外，還要考慮樹(shù)的深度影響，在用sklearn 包實(shí)現(xiàn)該算法的過(guò)程中，比較不同樹(shù)深度下的精確率、召回率和F1值，結(jié)果如圖1 所示，樹(shù)的深度默認(rèn)從3 開(kāi)始，當(dāng)深度為14 時(shí)整體效果最好，這時(shí)精確率P為0.74，召回率R為0.78，F(xiàn)1值為0.76。

圖1 不同樹(shù)深度下的精確率、召回率和F1值對(duì)比

5 結(jié)語(yǔ)

隨著人工智能和大數(shù)據(jù)的發(fā)展，網(wǎng)絡(luò)上每天都會(huì)涌現(xiàn)新的知識(shí)，知識(shí)融合將新知識(shí)鏈接到已有的知識(shí)圖譜中去，從而解決知識(shí)圖譜不完整問(wèn)題。ID3算法的核心思想就是以信息增益來(lái)度量屬性的選擇，選擇分裂后信息增益最大的屬性進(jìn)行劃分，該算法采用自頂向下的貪婪搜索遍歷可能的決策空間。在此算法的基礎(chǔ)上，研究實(shí)體嵌入、先驗(yàn)流行度和實(shí)體上下文特征如何將文本中的實(shí)體鏈接到知識(shí)圖譜對(duì)應(yīng)候選中去，從而完成新知識(shí)的融合。