基于知識表示學習的實時語義數(shù)據(jù)流推理

高 峰 熊 輝 顧進廣

(武漢科技大學計算機科學與技術(shù)學院 湖北 武漢 430065)(湖北省智能信息處理與實時工業(yè)系統(tǒng)重點實驗室 湖北 武漢 430065)

0 引 言

隨著傳感器網(wǎng)絡、社交媒體和移動互聯(lián)網(wǎng)等應用的發(fā)展，網(wǎng)絡上產(chǎn)生了海量數(shù)據(jù)，數(shù)據(jù)的實時處理和分析具有重要意義。將實時數(shù)據(jù)流與知識圖譜技術(shù)結(jié)合，對數(shù)據(jù)流進行知識標注后可得語義數(shù)據(jù)流(Semantic Data Stream)，語義數(shù)據(jù)流處理系統(tǒng)(RDF Stream Processing， RSP)能將靜態(tài)背景知識與動態(tài)信息結(jié)合，實現(xiàn)實時的、基于知識的查詢和推理。

針對實時推理，已經(jīng)出現(xiàn)了不少實時語義數(shù)據(jù)流推理平臺，其中：集中式的系統(tǒng)包括C-SPARQL引擎[1]，這是一種基于ESPER數(shù)據(jù)流處理引擎和Jena查詢的流推理系統(tǒng)；分布式的系統(tǒng)包括基于LARS[2]架構(gòu)的BigSR[3]流推理平臺。它們都能在一定的程度上解決語義推理問題，但是傳統(tǒng)的實時語義流推理平臺在進行傳遞規(guī)則推理，特別是傳遞閉包規(guī)則推理時會產(chǎn)生大量中間結(jié)果，導致推理效率急劇下降[4-5]。

近年來，以深度學習為代表的知識表示學習技術(shù)發(fā)展較快[6]。知識表示學習是指在知識庫中，以實體和關(guān)系為基礎(chǔ)進行表示學習，實現(xiàn)對實體和關(guān)系之間語義信息的向量化表示。這種方式能夠?qū)嶓w之間復雜的語義關(guān)系轉(zhuǎn)化為簡單的向量計算，對于提升推理效率效果明顯。因此，本文提出一種基于C-SPARQL平臺和KALE知識表示學習模型[7]的CSKR(Continuous Sparql with KALE Reasoning)實時流推理平臺。首先通過索引算法對ESPER引擎中實時數(shù)據(jù)流的謂語構(gòu)建索引，再根據(jù)查詢語句以及推理規(guī)則生成預測的三元組集合，最后輸入給擴展的KALE模型并計算出推理結(jié)果。

1 相關(guān)工作

1.1 實時語義數(shù)據(jù)流推理

語義數(shù)據(jù)流中的信息是不斷變化與更新的，因此傳統(tǒng)的語義推理和查詢的方法無法適用于這種情況?，F(xiàn)在已經(jīng)有一些工作能夠處理動態(tài)RDF數(shù)據(jù)流。例如Streaming SPARQL[8]、C-SPARQL、CQELS[9]、EP-SPARQL[10]等。Streaming SPARQL 基于時代關(guān)系函數(shù)，用來擴展SPARQL語言，雖然支持RDF流處理，但是沒有考慮到連續(xù)計算過程中狀態(tài)共享的性能問題。C-SPARQL是一個基于ESPER數(shù)據(jù)流處理引擎和Jena組件的流推理平臺，通過添加新的運算符來擴展SPARQL語言，從而支持對RDF數(shù)據(jù)流的處理。CQELS同時支持靜態(tài)數(shù)據(jù)和動態(tài)數(shù)據(jù)并支持多源RDF流處理，可以提供優(yōu)秀的查詢性能，但是沒有考慮并行的問題，對大數(shù)據(jù)集支持不好，大大降低了流處理性能。EP-SPARQL偏向于復雜事件處理和流推理，它可以轉(zhuǎn)化成一種基于Prolog復雜事務處理框架語言ETALIS[11]，并實現(xiàn)實時語義數(shù)據(jù)流推理和查詢。LARS是一種基于邏輯的推理分析框架，在此基礎(chǔ)上BigSR結(jié)合了Spark和Flink推出了分布式實時語義數(shù)據(jù)流推理平臺，該平臺吞吐量較大并且延遲在毫秒以內(nèi)。雖然此類方法能利用分布式處理有效降低推理延時，但對硬件資源要求較高，本文方法則無此限制。

1.2 知識表示學習模型

在Mikolov等[12]提出了word2vec詞表示學習模型之后，表示學習的方式在知識圖譜的領(lǐng)域受到了廣泛的關(guān)注。Bordes等[13]提出了TransE知識表示學習模型，這是一種既簡單又高效的模型，該模型將三元組中的關(guān)系看作平移向量，表示頭實體與尾實體之間的平移。因此，對于每一個事實三元組，都應當滿足以下條件：

ei+rk≈ej

(1)

式中：ei表示頭實體向量；rk表示關(guān)系向量；ej表示尾實體向量。

TransE模型的真值公式表示為：

(2)

式中：d表示向量空間的維度;I則表示每一個三元組經(jīng)過計算之后得到的真值。

因為TransE模型的參數(shù)簡單、計算復雜度低，但是性能高效的特性，大量研究工作對其進行擴展和應用，并且出現(xiàn)了大量基于TransE模型改進和補充的知識表示學習模型。例如TransH[14]、TransR[15]、TransA[16]TransD[17]等模型。其中：TransH是一種針對TransE當中不能很好解決實體和關(guān)系之間一對多、多對一和多對多問題的改進模型；而TransR認為不同的關(guān)系擁有不同的語義空間，因此它將實體和關(guān)系嵌入到不同的空間中，在對應的關(guān)系空間中實現(xiàn)翻譯。

雖然以上模型都對TransE模型做了相應的改進，但是都沒有利用三元組之間的關(guān)系。KALE模型在TransE模型的基礎(chǔ)上根據(jù)Tim等[18]提出的關(guān)系抽取方式建立了三元組與推理規(guī)則的統(tǒng)一框架，改善了原有TransE模型訓練過程中只利用了實體內(nèi)部的聯(lián)系而忽略了三元組之間推理規(guī)則的問題。因此本文以KALE模型為基礎(chǔ)，提出了相應的KR推理機制，并應用于實時流推理平臺。

2 CSKR平臺框架

傳統(tǒng)語義數(shù)據(jù)流推理中，主要包含ESPER流引擎、推理引擎和Sparql查詢引擎，CSKR將其中的推理引擎轉(zhuǎn)換為KALE模型并加入推理機制，將復雜的規(guī)則推理變成簡單的向量計算，從而大大降低了推理延遲，用來滿足大數(shù)據(jù)情況下的實時推理需求，CSKR推理主要包括以下幾個步驟：

(1) 加載RDF數(shù)據(jù)，通過Jena解析，將RDF數(shù)據(jù)轉(zhuǎn)化為ESPER數(shù)據(jù)流處理引擎可識別的數(shù)據(jù)格式。

(2) 讀取解析后的數(shù)據(jù)，并加上時間戳，放入RDF數(shù)據(jù)流中。

(3) 從ESPER流引擎中取出指定窗口內(nèi)的數(shù)據(jù)，作為輸入數(shù)據(jù)輸入到聯(lián)合嵌入式模型當中。

(4) 聯(lián)合嵌入式模型獲取數(shù)據(jù)后，根據(jù)推理規(guī)則，預測可能存在的三元組集合，并將集合內(nèi)的三元組進行向量計算后，依據(jù)目標函數(shù)的閾值進行分類，得出推理的三元組集合。

(5) 將推理結(jié)果放入Sparql引擎中進行查詢，并返回查詢結(jié)果。

CSKR平臺總體框架如圖1所示。

圖1 CSKR平臺總體框架

3 CSKR推理機制

本文在KALE的基礎(chǔ)上進行擴展，得到針對傳遞性規(guī)則的知識表示模型?；镜腒ALE模型只能應用于鏈接預測和分類的場景，無法直接替換傳統(tǒng)的推理引擎，因此本文提出一種基于三元組預測機制的CSKR推理平臺。

3.1 推理規(guī)則和模型框架

目前傳統(tǒng)實時語義流推理平臺主要采用的推理規(guī)則是RDFS/OWL規(guī)則集。它們在RDF的基礎(chǔ)上增加了對本體的描述和類型約束，并且添加了相關(guān)的推理規(guī)則。但是在推理過程中，因為傳遞規(guī)則尤其是傳遞閉包規(guī)則的復雜性，導致傳統(tǒng)推理方法性能很差，所以產(chǎn)生了大量重復數(shù)據(jù)，計算量呈指數(shù)級的上升。

在知識表示學習方向，KALE模型將三元組之間的規(guī)則嵌入到表示學習過程當中，建立了規(guī)則和三元組之間的統(tǒng)一框架。KALE模型基于Tim等[18]提出的關(guān)系抽取方法，以邏輯連接詞推理的方式對兩種類型的規(guī)則建立了統(tǒng)一得分函數(shù)。

第一種類型為假設(em,rs,en)?(em,rt,en),則根據(jù)關(guān)系抽取以及邏輯連接詞的推導，可以得到如式(3)所示的真值公式。

I(f)=I(em,,rs,en)·I(em,,rt,en)-

I(em,,rs,em)+1

(3)

式中：I表示三元組的真值。同樣的第二種類型為(em,rs,en) ∧(en,rk,el)?(em,rt,el),可以得到如式(4)所示的統(tǒng)一真值公式。

I(f)=I(el,,rs,em)·I(em,,rk,en)·I(el,,rt,en)-

I(em,,rs,en)·I(en,,rk,el)+1

(4)

KALE模型具體框架如圖2所示。

圖2 KALE模型框架

KALE模型利用卷積神經(jīng)網(wǎng)絡分別學習三元組中實體和關(guān)系的描述，得到頭、尾實體和關(guān)系的向量表示em、en、rs。基于上述工作，KALE模型對知識圖譜中的三元組計算統(tǒng)一得分函數(shù)，對于正確的三元組，其得分越低越好；而對于一個負采樣產(chǎn)生的樣本，其得分越高越好，這樣通過訓練模型區(qū)分正負樣本。因此，在模型訓練過程中，采用合頁損失函數(shù)作為訓練目標，并使用隨機梯度下降算法進行優(yōu)化，其損失函數(shù)定義如式(5)所示[7]。

(5)

式中：S+為正實例三元組的集合；S-為負實例三元組的集合；I為統(tǒng)一得分函數(shù)；γ是margin的超參數(shù)，表示正負樣本得分之間的間隔距離。

由于在實時推理中，傳遞性規(guī)則執(zhí)行的效率較差，尤其是傳遞閉包產(chǎn)生大量中間結(jié)果導致性能下降，本文主要在KALE模型的基礎(chǔ)上實現(xiàn)傳遞性規(guī)則和傳遞閉包規(guī)則的實時流推理模型。

3.2 索引分類

數(shù)據(jù)流中的三元組中的主語和賓語變化較為頻繁，而其中的謂語則相對固定，例如存在兩個不同的三元組(e1,r,e2)和(e3,r,e4)，他們的謂語都是r，但是主語和賓語分別為e1、e2和e3、e4,根據(jù)這種情況，本文對謂語建立了相應的索引以提高推理效率。

每當讀取一個新的三元組時，CSKR的數(shù)據(jù)流引擎抽取當前謂語，然后去索引節(jié)點中檢索，如果節(jié)點中不包括該謂語，則對該謂語建立相應的索引，并在這個索引上建立對應的主語集合和賓語集合，最后將這個三元組的主語和賓語分別放入對應的集合；如果節(jié)點中包括當前謂語，則直接將三元組的主語和賓語放入對應的集合。當讀取完所有的三元組數(shù)據(jù)之后，CSKR可以得到如圖3所示的索引結(jié)構(gòu)。

圖3 KR算法索引結(jié)構(gòu)

具體索引算法如算法1所示。

算法1索引算法

輸入:triples。

輸出:out。

begin

valout=outMap

for (tintriples) {

if (out.containsKey(t.p) {

out.get(t.p).get(subject).add(t.s)

out.get(t.p).get(object).add(t.o)

} else {

out.put(t.p,tripleMap)

out.get(t.p).put(subject,subjectSet)

out.get(t.p).put(object,objectSet)

out.get(t.p).get(subject).add(t.s)

out.get(t.p).get(object).add(t.o)

}

}

returnout

end

3.3 三元組預測和分類

為了將KALE應用于推理模型，CSKR首先需要生成預測三元組集合，再將預測三元組集合放入模型中計算得分函數(shù)。由于預測三元組集合的生成會根據(jù)數(shù)據(jù)特性生成不同數(shù)量的冗余數(shù)據(jù)，本文使用關(guān)系生成和實體生成兩種不同的策略來生成預測三元組，并使用如下方式自動選擇恰當?shù)牟呗裕涸谧铋_始的五次計算里，分別計算兩種生成算法生成的預測三元組集合數(shù)量，然后選取數(shù)量少的集合作為輸入?yún)?shù)進行接下來的計算，并對選取的策略標記加一，當五次采樣結(jié)束后，CSKR會選取標記多的策略作為接下來的生成算法。

關(guān)系生成算法首先根據(jù)規(guī)則集中的關(guān)系推理解析查詢語句，當查詢中包含需要推理的規(guī)則時，CSKR會從索引節(jié)點中獲取推理條件中謂語對應的主語集合與賓語集合，并與推理結(jié)果中的謂語組成新的預測三元組。例如存在如下傳遞推理規(guī)則：當三元組數(shù)據(jù)集中包含(e1,r1,e2)和(e2,r2,e3), 則一定可以推理出(e1,r3,e3)這樣的新三元組。根據(jù)關(guān)系生成算法，推理引擎將會先獲取r1的主語集合set1和r2中的賓語集合set2，并將set1中的實體作為主語，set2中的實體作為賓語，最后與r3組成新的預測三元組。其主要生成算法如算法2所示。

算法2關(guān)系生成策略

輸入:tripleMap,rules,gate。

輸出:out。

begin

valout=outSet

for (ruleinrules) {

valsubjectSet=tripleMap.get(rule.p1).get(subject)

valobjectSet=tripleMap.get(rule.p2).get(object)

for (sinsubject) {

for (oinobject) {

out.add(s,rule.p3,o)

}

}

}

returnout

end

實體生成算法則是根據(jù)實體所在的位置生成對應的預測三元組集合。如果一個實體既是某個三元組的賓語，也是另外一個三元組的主語，則生成算法認為該實體在這兩個三元組中對應的主語和謂語可能存在某種傳遞規(guī)則。其具體算法如算法3所示。

算法3實體生成策略

輸入:triples,rules。

輸出:out。

begin

valout=outSet

for (t1intriples) {

for (t2intriples) {

if (t1.o==t2.s) {

for (ruleinrules) {

out.add(t1.s,rule.p,t2.o)

}

}

}

}

returnout

end

在模型訓練中，系統(tǒng)會根據(jù)正實例的排名不斷調(diào)整得分函數(shù)的閾值，當三元組經(jīng)過計算后，其得分大于閾值時，系統(tǒng)判定該三元組為正實例，否則為負實例。訓練完成后，推理引擎將新的預測三元組集合進行重新計算，并將得分大于閾值的三元組作為最后的推理結(jié)果。

4 實驗與結(jié)果分析

4.1 實驗設置

本文實驗所使用的軟件環(huán)境為操作系統(tǒng)Windows 10，采用Java 8作為編程環(huán)境，開發(fā)環(huán)境為IntelliJ IDEA。硬件環(huán)境為CPU i5 10210U@1.6 GHz, 內(nèi)存大小為16 GB。

本文采用并擴展里海大學推出的LUBM(Lehigh University Benchmark)標準數(shù)據(jù)集[19]進行實驗，擴展數(shù)據(jù)集已在Github開源。實驗內(nèi)容主要包括CSKR的推理準確性實驗和推理性能對比實驗。

4.2 推理實驗場景

LUBM數(shù)據(jù)集本身不存在傳遞閉包規(guī)則，因此，為了適應本實驗對傳遞規(guī)則以及傳遞閉包規(guī)則測試的情況，本實驗隨機對LUBM數(shù)據(jù)集部分GraduateStudent實體之間增加了schoolMate關(guān)系，并構(gòu)造了傳遞規(guī)則Rule1和傳遞閉包規(guī)則Rule2,規(guī)則如表1所示。

表1 傳遞規(guī)則以及傳遞閉包規(guī)則

針對以上傳遞規(guī)則，本實驗構(gòu)造了兩個查詢語句Query1和Query2如表2所示。

表2 實驗查詢語句

表2中Query1表示查詢University1的所有成員，在Rule1的條件，假設存在學生GraduateStudent1與學生GraduateStudent2之間擁有schoolMate的關(guān)系，且GraduateStudent2與University1之間擁有memberOf的關(guān)系，那么在查詢結(jié)果當中應當包含可以推理出來的三元組(GraduateStudent1, memberOf, University1)。Query2表示查詢GraduateStudent1的所有校友，在Rule2的條件，假設存在學生GraduateStudent1與學生GraduateStudent2之間擁有schoolMate的關(guān)系，且學生GraduateStudent2與學生GraduateStudent3之間擁有schoolMate的關(guān)系，那么在查詢結(jié)果當中應當包含可以推理出來的三元組(GraduateStudent1, schoolMate, GraduateStudent3)，并且該推理結(jié)果仍然可以作為推理條件去推理新的結(jié)果，具有傳遞閉包性。

4.3 CSKR推理命中率

為了更好地評價本文模型在LUBM數(shù)據(jù)集上的效果，本文沿用了KALE模型中同樣的評價方式。對于每一個測試三元組(s,p,o),模型會打碎主語s,并將其替換為主語集合中的其他主語s′, 構(gòu)成新的負實例三元組(s′,p,o),最后計算該負實例的真值。在所有主語遍歷完后，模型將會得到一個根據(jù)真值降序的列表以及正實例三元組中主語s在列表中的排名。同樣地，在替換完賓語之后，也可以得到一個正實例三元組中賓語o在列表中的排名。最終本文得到兩個指標: (1) MRR(Mean Reciprocal Rank)是一個常用的衡量算法的指標，目前被廣泛用在允許返回多個結(jié)果的問題當中。(2) HITS@N是指正例三元組排在真值降序列表中前n位置的比例。

本實驗將向量空間的維度d的分別設置為{30,40,50}，為了驗證KALE模型對于TransE模型的改進有利于本實驗的數(shù)據(jù)集，加入了TransE模型在相同條件下的對比實驗。根據(jù)設置，實驗后可以得到如表3所示的實驗結(jié)果。

表3 KALE與TransE的推理命中率實驗結(jié)果

根據(jù)實驗結(jié)果可知，隨著d的逐漸增加，KALE模型在LUMB數(shù)據(jù)集上，評價指標越好,并且在相同維度的條件下，KALE模型的結(jié)果均好于TransE模型。

隨著向量矩陣的維度逐漸增加，雖然評價指標有所提升，但是模型計算得分函數(shù)的計算量也會依次增加，而且當維度從30增加到50的時候，HIT@10的結(jié)果提升不到3%, 計算消耗卻增加了70%左右?？紤]到該模型將應用于大數(shù)據(jù)低延遲的場景，因此，本實驗選取d為30的KALE模型作為CSKR的推理引擎，然后與傳統(tǒng)C-SPARQL推理系統(tǒng)做對比。

4.4 CSKR查詢和推理時延

在傳統(tǒng)C-SPARQL推理引擎中，目前遇到的困難是，在碰到復雜的傳遞閉包規(guī)則時，推理會產(chǎn)生大量的重復三元組，急劇增加了推理延遲，降低推理效率，所以不能很好地處理實時數(shù)據(jù)。本實驗選取單位數(shù)量的三元組作為數(shù)據(jù)輸入，并以處理數(shù)據(jù)的延遲作為評價指標，分別設計了普通的傳遞規(guī)則和復雜的傳遞閉包規(guī)則查詢語句，并統(tǒng)計在復雜規(guī)則推理下，兩個系統(tǒng)的平均查詢延遲。

因為ESPER數(shù)據(jù)流處理引擎支持窗口操作，所以本實驗選取的窗口大小分別為{10,20,40},單位為s， 每秒窗口三元組的數(shù)量分別為{200,1 600},單位為個，窗口的步長為1 s。根據(jù)以上的輸入?yún)?shù)得到的實驗結(jié)果如圖4所示。

圖4 LUBM數(shù)據(jù)集的實驗結(jié)果

實驗結(jié)果表明，在相同條件下，CSKR平臺查詢所消耗的延遲明顯低于傳統(tǒng)的C-SPARQL平臺，在普通傳遞規(guī)則下最多能降低80%左右的延遲時間，而在傳遞閉包規(guī)則下最多能降低93%左右的延遲時間。在普通傳遞規(guī)則下，C-SPARQL數(shù)據(jù)量達到每秒32 000個三元組時計算量過大失去響應；在傳遞閉包規(guī)則下，C-SPARQL數(shù)據(jù)量達到每秒16 000個三元組時失去響應，而CSKR吞吐量均能達到每秒64 000個三元組以上，較C-SPARQL有明顯優(yōu)勢。

5 結(jié) 語

本文在傳統(tǒng)的推理系統(tǒng)C-SPARQL上融入了基于知識表示學習的KALE模型，并加入索引和三元組預測機制。實驗結(jié)果表明，在普通傳遞規(guī)則和傳遞閉包規(guī)則下，CSKR較C-SPARQL性能提升十分明顯，前者CSKR時延降低最多能達到80%左右，吞吐量提升2倍以上，而后者時延降低最多能達到93%左右，吞吐量提升4倍以上，并且CSKR的結(jié)合方式也為傳統(tǒng)的實時數(shù)據(jù)流規(guī)則推理系統(tǒng)提供了新的研究方向。

雖然CSKR平臺在生成預測三元組的時候采用了根據(jù)數(shù)據(jù)特性自適應的策略，但是兩種生成算法仍然會產(chǎn)生大量冗余數(shù)據(jù)，造成性能浪費。因此，在未來工作中，如何進一步優(yōu)化預測三元組生成算法依舊是研究重點。