高 峰 熊 輝 顧進廣

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

0 引 言

隨著傳感器網(wǎng)絡(luò)、社交媒體和移動互聯(lián)網(wǎng)等應(yīng)用的發(fā)展，網(wǎng)絡(luò)上產(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ī)則生成預(yù)測的三元組集合，最后輸入給擴展的KALE模型并計算出推理結(jié)果。

1 相關(guān)工作

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

語義數(shù)據(jù)流中的信息是不斷變化與更新的，因此傳統(tǒng)的語義推理和查詢的方法無法適用于這種情況。現(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復雜事務(wù)處理框架語言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)系看作平移向量，表示頭實體與尾實體之間的平移。因此，對于每一個事實三元組，都應(yīng)當滿足以下條件：

ei+rk≈ej

(1)

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

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

(2)

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

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

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

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ī)則，預(yù)測可能存在的三元組集合，并將集合內(nèi)的三元組進行向量計算后，依據(jù)目標函數(shù)的閾值進行分類，得出推理的三元組集合。

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

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

圖1 CSKR平臺總體框架

3 CSKR推理機制

本文在KALE的基礎(chǔ)上進行擴展，得到針對傳遞性規(guī)則的知識表示模型。基本的KALE模型只能應(yīng)用于鏈接預(yù)測和分類的場景，無法直接替換傳統(tǒng)的推理引擎，因此本文提出一種基于三元組預(yù)測機制的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ù)。

第一種類型為假設(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)絡(luò)分別學習三元組中實體和關(guān)系的描述，得到頭、尾實體和關(guān)系的向量表示em、en、rs?；谏鲜龉ぷ鳎琄ALE模型對知識圖譜中的三元組計算統(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ù)這種情況，本文對謂語建立了相應(yīng)的索引以提高推理效率。

每當讀取一個新的三元組時，CSKR的數(shù)據(jù)流引擎抽取當前謂語，然后去索引節(jié)點中檢索，如果節(jié)點中不包括該謂語，則對該謂語建立相應(yīng)的索引，并在這個索引上建立對應(yīng)的主語集合和賓語集合，最后將這個三元組的主語和賓語分別放入對應(yīng)的集合；如果節(jié)點中包括當前謂語，則直接將三元組的主語和賓語放入對應(yīng)的集合。當讀取完所有的三元組數(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 三元組預(yù)測和分類

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

關(guān)系生成算法首先根據(jù)規(guī)則集中的關(guān)系推理解析查詢語句，當查詢中包含需要推理的規(guī)則時，CSKR會從索引節(jié)點中獲取推理條件中謂語對應(yīng)的主語集合與賓語集合，并與推理結(jié)果中的謂語組成新的預(yù)測三元組。例如存在如下傳遞推理規(guī)則：當三元組數(shù)據(jù)集中包含(e1,r1,e2)和(e2,r2,e3), 則一定可以推理出(e1,r3,e3)這樣的新三元組。根據(jù)關(guān)系生成算法，推理引擎將會先獲取r1的主語集合set1和r2中的賓語集合set2，并將set1中的實體作為主語，set2中的實體作為賓語，最后與r3組成新的預(yù)測三元組。其主要生成算法如算法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ù)實體所在的位置生成對應(yīng)的預(yù)測三元組集合。如果一個實體既是某個三元組的賓語，也是另外一個三元組的主語，則生成算法認為該實體在這兩個三元組中對應(yīng)的主語和謂語可能存在某種傳遞規(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)判定該三元組為正實例，否則為負實例。訓練完成后，推理引擎將新的預(yù)測三元組集合進行重新計算，并將得分大于閾值的三元組作為最后的推理結(jié)果。

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

4.1 實驗設(shè)置

本文實驗所使用的軟件環(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ī)則，因此，為了適應(yīng)本實驗對傳遞規(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的條件，假設(shè)存在學生GraduateStudent1與學生GraduateStudent2之間擁有schoolMate的關(guān)系，且GraduateStudent2與University1之間擁有memberOf的關(guān)系，那么在查詢結(jié)果當中應(yīng)當包含可以推理出來的三元組(GraduateStudent1, memberOf, University1)。Query2表示查詢GraduateStudent1的所有校友，在Rule2的條件，假設(shè)存在學生GraduateStudent1與學生GraduateStudent2之間擁有schoolMate的關(guān)系，且學生GraduateStudent2與學生GraduateStudent3之間擁有schoolMate的關(guān)系，那么在查詢結(jié)果當中應(yīng)當包含可以推理出來的三元組(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的分別設(shè)置為{30,40,50}，為了驗證KALE模型對于TransE模型的改進有利于本實驗的數(shù)據(jù)集，加入了TransE模型在相同條件下的對比實驗。根據(jù)設(shè)置，實驗后可以得到如表3所示的實驗結(jié)果。

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

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

隨著向量矩陣的維度逐漸增加，雖然評價指標有所提升，但是模型計算得分函數(shù)的計算量也會依次增加，而且當維度從30增加到50的時候，HIT@10的結(jié)果提升不到3%, 計算消耗卻增加了70%左右。考慮到該模型將應(yīng)用于大數(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ù)的延遲作為評價指標，分別設(shè)計了普通的傳遞規(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個三元組時計算量過大失去響應(yīng)；在傳遞閉包規(guī)則下，C-SPARQL數(shù)據(jù)量達到每秒16 000個三元組時失去響應(yīng)，而CSKR吞吐量均能達到每秒64 000個三元組以上，較C-SPARQL有明顯優(yōu)勢。

5 結(jié) 語

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

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