基于Ontology擴展查詢的數學表達式檢索模型

李新福,徐 筱,田學東

(河北大學 計算機科學與技術學院,河北 保定 071000)

0 概述

數學表達式檢索技術的發展加強了相關人員對數學信息的交流,滿足了不同用戶的檢索需求。為提高數學檢索的適用性,擴大使用人群,開發面向語義的數學公式搜索引擎意義深遠。

國內外已逐步針對數學表達式檢索進行相關研究,并構建DLMF Search[1]、MathDex[2]、MathWeb Search[3]、LeActiveMath[4]、EgoMath[5]、 WikiMirs[6]、MIaS[7]、SFE[8]等原型系統。其中,文獻[8]對LaTeX格式的表達式提出了序列化特征提取方法,該方法具有不破壞表達式原有結構的特性,相較于其他檢索系統,能高速且準確地檢索出表達式的不同層次,滿足不同用戶的檢索需求。

以上檢索系統能夠實現不同程度的數學表達式檢索匹配,檢索性能表現良好,但均需借助排版工具將二維的公式轉換成更適宜處理的一維表現形式,普通用戶并不熟悉排版工具的排版格式,大大降低了系統的使用范圍;同時,被檢索數學公式脫離了原本的語境范圍,不同的語境下不同語義但形式相同的表達式均會被檢索出,換言之,未從語義層面對表達式進行區分。

文獻[9]在NTCIR[10]-11Math2 Task中,提出將數據集分成公式和公式所在的上下文兩組,分別進行特征提取,結合公式的語義和公式結構檢索到相關文檔。自然語言千變萬化,涉及范圍較廣,該實驗中選取的數據集龐大,且在特征選取時只依賴公式前后的3句話,所獲取的文本特征不足以表達公式本身的語義。受此啟發,建立表達式對應的文本概念及概念之間的聯系,可以針對表達式進行不同程度的語義檢索。鑒于此,本文將有推理功能且用于多種領域信息檢索[11-17]的本體論知識,運用在基于SFE的數學公式檢索中作為語義表達的基礎。

本體[18]作為一個很好的概念建模工具,曾被Tom Gruber[19]定義為“概念模型(conceptualization)的明確的規范說明”,不僅能從知識和語義上對信息進行描述和組織,還支持滿足一定規則的邏輯推理操作,具有代表性的應用有Ontoseek[20]、Swoogle[21]等。文獻[22]提出了基于網絡本體處理數學公式間的關系,文獻[23]以表達式中數學公式部分作為基點歸納出4類數學表達式多元信息的關聯關系,使用改進后的通配符表示方法來構建數學表達式本體庫,從而實現數學表達式的語義檢索。本文在上述研究的基礎上,提出一種基于Ontology擴展查詢的數學表達式檢索方法。

1 基于Ontology的數學表達式檢索

基于SFE的數學表達式檢索過程加入本體概念可實現語義檢索的目的,其實現過程可分為以下4個層次:

1)在領域專家的協助下,運用結構化、半結構化和非結構化的方式抽取數據并建立數學名詞與表達式之間關系,整合數據后構建相關的領域本體。

2)利用本體中的概念標注數學名詞和表達式資源并以特定的格式存儲,結果以RDF文檔的方式存儲,也可在本體工具中直接查詢,并可根據一定的推理規則基于本體進行語義推理。

3)采集的html、xml等格式的數據集要對文本進行樣式、格式、分詞等預處理,有些網頁會提供多種格式的數學表達式,如LaTeX、MathML等,因SFE檢索結構針對LaTeX表達式,故提取LaTeX格式數據并預處理,避免因為書寫習慣等因素產生噪音對檢索結果造成影響。

4)數學表達式經過SFE檢索后初步確定的目標文檔,結合用戶查詢詞在Ontology中查詢擴展后的關聯本體,從語義上2次判斷該文檔與用戶查詢詞的關聯性,并將高于一定相關性的文檔輸出到檢索界面。

分析上述基于Ontology的數學表達式檢索思想,構建語義檢索模型如圖1所示,該檢索系統的核心在于本體構建、設計匹配規則,下文將詳細闡述。

圖1 語義檢索模型結構框架

2 Ontology構建

表達式或符號是全世界通用的一門數學語言,正因為它能高度抽象地表達一類概念,即過于抽象,往往會在不同的學科領域,或相同學科不同的應用背景下被賦予不同的含義,如表1所示。

表1 不同語境下相同表達式表示的不同語義

此外,數學表達式的變形、推導以及不同的證明方法往往也會導致不同表現形式的表達式具有相同的內在語義,如表2所示。

表2 不同表達式表示的相同語義

無論是表2的哪種情況,在現有的數學表達式檢索系統中,如果不加以語義的約束,則往往達不到想要的檢索效果,本文引入本體的概念來改善這些問題。

Cuarino[24]從領域依賴程度將本體劃分為頂級本體、領域本體、任務本體、應用本體。領域本體指依賴于具有特定含義的概念以及概念之間關系的領域。本文著力于建立數學領域中表達式以及其專有名詞概念之間的聯系,屬于領域本體的范疇,通常領域本體的構建需要依賴領域專家的參與,建立合適且正確的通用聯系。本文以權威著作《數學辭海》[25]為參考資料。

本體構建是整個語義檢索系統的核心所在,建立合適且全面的領域本體能夠提高檢索的查全率查準率。下面按照從局部到整體的思路,首先分別從表達式和術語概念2個方面出發建模,然后從整體上建立兩者之間的聯系,最終建成數學表達式及其概念本體庫。

2.1 概念

文獻[26]總結認為Ontology一般有如下5種常規建模元語(modeling primitives):類/概念(classes/concepts),公理(axioms),關系(relations),函數(functions)和實例(instances)。類是相似術語所表達的概念集合;公理是確實存在不必證明的邏輯永真式;關系是領域內兩概念間相互關系;函數是本體中一種特殊的關系;實例在本體工具中一般也稱為個體(individual),是對類或概念的具體化,具有不可再分性。

《數學辭海》共6卷,以第1卷為例,卷中目錄分為一級標題(如“平面幾何”)、二級標題(如“面積”)和具體條目(如“勾股定理”)。初步規定,一級標題為類,二級標題為一級標題的子類,具體條目作為兩者的實例,無論是類還是實例在本體工具中都稱為本體On。卷中每個詞條都有相應的文本注解和公式,將每個本體On的注解以一個文檔的形式存儲,形成文檔集:

docS=(D1,D2,…,Dn)

(1)

摘錄卷中目錄為數學專有名詞上下位關系表,記為mfn.dct。基于此,表對ICTCLAS分詞系統作出改進,并對卷中文本進行分詞處理,原子切分之前采用逆向最大匹配算法首先在上下文關系表中匹配。使得程序有效區分數學專業名詞術語,又增加了切分數據的準確性。然后依據固定出現的語法句式,如“……即……”“……亦稱為……”等編寫程序得到數學專有名詞同義詞表,記為slmt.dct,以及去停用詞等操作后提取原子詞匯作為本體On的文本特征,記為:

F=(fn1,fn2,…,fnk)

(2)

提取公式集合,記為:

latS=(L1,L2,…,Ln)

(3)

當本體On在文檔Dn中有相對應注解的公式Ln時,F也同樣作為公式Ln的文本特征項。

采用向量空間模型(SVM)將公式Ln的文本特征表示為Ank,并存入數據庫mysql中。

Ank=(fn1,wn1,fn2,wn2,…,fnk,wnk)

(4)

其中,fnk是公式Ln的特征項,wnk是特征項fnk所占權重,這里將fnk的tf(term frequency)值作為其權重wnk的值。以On為關鍵詞在百度搜索引擎反饋頁面取TopN條為計算tf值的依據,公式如下:

(5)

其中,Mi代表文檔i中總的詞匯量,Nik代表在文檔i中特征詞fnk出現的次數。

2.2 概念間關系

通過以上步驟提取了概念在水平與垂直層級的關系和相應公式以及公式對應的文本特征。但在實際操作中存在以下情況:

1)詞條無特定公式注解,如詞條“立體幾何學”;

2)詞條無特定公式注解但有常用的表達式或符號,如“代數余子式”對應Aij,“圓周率”對應π;

3)多個詞條對應一個公式,如“勾股定理”“勾股弦定理”“畢達哥拉斯定理”都對應著公式a2+b2=c2;

4)一個詞條對應多個公式,如公式a2+b2=c2是公式2ab+(b-a)2=c2進行推演后形成的,也即“勾股定理”對應這2個公式。

因此,在構建本體時不光要考慮到數學名詞語義性,還要考慮數學表達式的同義性以及特殊的具有標識作用的符號或子式,在查詢詞擴展時按照一定策略都可作為關聯本體以便有效地擴大檢索范圍。

本文根據實際需求建立如表3所示的關系。

表3 本體關系

在原有數據的基礎上加入以上關系構建本體,其中數學表達式部分采用LaTeX格式進行處理,因其能實現數學表達式從二維結構到一維結構的轉化操作,且在這個轉化過程中LaTeX完整地保留了數學公式包含的所有信息,每一個確定的數學公式都有唯一的LaTeX公式與其對應,沒有語義誤差。一段簡單的本體片段如圖2所示。

圖2 本體關系片段

使用本體將關鍵字級別的零散的詞匯提升為概念級別的關聯,不同以往,綜合地從關鍵詞以及數學表達式2個方面建模,便于對用戶輸入查詢詞進行語義擴展。其中,同義公式以及具有標識作用的符號的加入提高了查全率,再用文本概念及文本特征Ank限定查準率,以期達到更深層次的數學表達式語義檢索。

3 改進的SFE檢索匹配

3.1 SFE特征提取原理

序列化特征提取(SFE)表達式特征提取方法認為一個表達式的結構特征(s)可分為以下3種:運算結構特征(o),常量結構特征(c),變量結構特征(v)。其中,運算結構特征由公式中的運算符及所有符號在公式二維結構內的位置信息構成,常量結構特征由表達式中的數字構成,變量結構特征由表達式中的字符性符號構成。3種特征分量的不同組合可以實現不同層次的表達式特征匹配,特征提取的流程如圖3所示。該程序還對LaTeX符號指令自定義了編碼字典,避免因解析過程中指令內字符的干擾而匹配到有誤的檢索結果。

與傳統提取方式相比,基于SFE特征提取的檢索系統使得檢索范圍更準確,檢索結果層次性更好,獲得的匹配公式與查詢公式相似度高,但該方法不涉及公式所在文檔與查詢公式的語義關聯性。故在此特征提取的基礎上進行擴充,加入本體知識判斷語料庫中公式與其所在文檔的關聯程度,進一步限定檢索范圍,使得查詢結果偏于語義化。

圖3 特征提取原理流程

3.2 查詢詞擴展及數據預處理

本文運用斯坦福大學的Protégé5.2構建本體,并用Jena實現推理機制。對用戶的查詢請求通過查詢轉換器按照ontology將其轉換為規定格式,并進行查詢詞擴展。也可用Protégé自帶的可視化工具OntoGraf進行可視化查詢擴展,當檢索一個關鍵詞時有多種查詢模式可供選擇以滿足不同查詢需求,生成的圖存為DOT文件,由于涉及諸多中文,選擇utf8進行轉碼即可查看。

用戶輸入的查詢詞qW在本體庫中按照關系查詢擴展后的關聯本體為:

relO=(o1,o2,…,on)

(6)

找出與查詢詞qW最相關的表達式Lr以及“has_part”部分的子式Lj和“has_equivalence”的同義公式Lk,再從數據庫中找出向量Ark表示的表達式Li的文本特征:

Ark=(fr1,wr1,fr2,wr2,…,frk,wrk)

(7)

數據集以單個文檔方式存儲到數據庫中,記為:

Docmn=(d1,d2,…,dn)

(8)

對每篇文檔dn的每一段落pn進行改進后的分詞處理、去停用詞,并對出現的原子及其在該段落的詞頻使用向量Bnj進行語義標注,記為:

Bnj=(pn1,wn1,pn2,wn2,…,pnj,wnj)

(9)

3.3 改進SFE的檢索匹配

考慮到以往的數學表達式檢索系統中,用戶被要求輸入相應排版格式的數學公式,不熟悉該排版格式的用戶無法正確輸入要查詢的表達式導致用戶體驗差,用戶群體局限等問題。本文系統在查詢入口做了更適宜用戶操作的改變,實現步驟如下:

輸入自然語言或LaTeX格式表達式

輸出含LaTeX格式表達式的文獻

步驟1用戶輸入查詢詞qW,若匹配Ontology執行步驟2;否則執行步驟5。

步驟2qW在Ontology中進行查詢擴展出關聯本體集合relO,關聯公式Lr和同義公式Lk以及Lr的特征集Ark,執行步驟3。

步驟3對Lr和同義公式Lk進行SFE三層特征提取并初次篩選語料庫dn,得到目標文檔dq。找到目標文檔dq中公式所在段落pq,提取pq的標注Bqj并與關聯本體集relO匹配,若滿足{x|?x=pnj∩on}則認定相關并執行步驟8;否則執行步驟4。

步驟4將Bqj按照Lr的文本特征Ark進行修改:將Bqj中滿足{x|x=(pnj∩frk)}的特征項保留,其余剔除;在Bqj中添加滿足{x|x=frk-(pqj∩frk)}的特征項并令其權重為0。修改后的向量記為:

(10)

(11)

從而算出段落pq對關聯公式Lr的語義關聯度:

support(pq,Lr)=cosθ+φ

(12)

其中,φ代表文檔中其他影響因子,視所有文檔中影響因子都為相等值φ。

當support(pq,Lr)>α時,認定該文檔與原始查詢詞是相關的,執行步驟8。

步驟5判斷查詢詞qW是否為公式,若是則執行步驟6;否則執行步驟7。

步驟6對qW進行SFE特征提取并檢索語料庫dn,執行步驟7。

步驟7對語料庫進行關鍵字檢索并檢索語料庫dn,執行步驟8。

步驟8輸出最終被檢索的相關文檔并結束。

4 實驗結果與分析

為了驗證基于Ontology和SFE判斷數學表達式與文檔的關聯關系的有效性和可行性,收集了中學數學、化學和物理學科的課本、試卷和習題等相關資料,共獲得含LaTeX公式的文檔為7 268篇。這里針對實際情況設定如下前提條件:

1)因數據涉及多種學科領域,待檢索的語料庫中通常不會完全出現整個公式,而是存在包含、內嵌等情況,故被檢索表達式經過SFE三層特征匹配命中的文檔都認為與原查詢公式形式相關。

2)如果通過支持度計算出被檢索段落與查詢詞相關,則認為該文檔與查詢詞相關。

4.1 評價標準的建立

本文根據常見檢索系統性能指標和評定標準,對系統進行查全率和查準率比較,并按照實際情況規定擴展率。

例如:語料庫M,當檢索樣本A時,語料庫中與A相關的文檔數為relD;普通的數學公式檢索(這里模擬SFE檢索)命中的文檔數為DSsfe,其中與查詢樣本A確切相關的文檔數為DStrue;經由本體改進后的系統檢索文檔數為DOontology,其中與查詢樣本A確切相關的文檔數為DOtrue。其中,relD、DSsfe和DOtrue均采用人工統計方法。據此給出如下評價指標的定義:

定義1查準率為檢索結果集內判斷正確的文檔數量與檢索結果集內的文檔總數的比值。

設SFE系統的查準率為:

(13)

設本文系統的查準率為:

(14)

定義2查全率為檢索結果集內正確的文檔數量與檢索結果集內實際正確的文檔數量的比值。

設SFE系統的查全率為:

(15)

設本文系統的查全率為:

(16)

定義3擴展率(Extension ratio,E)為基于本體查詢擴展后結果集內增加的正確文檔數量與擴展后結果集內總文檔數量的比值。

設系統擴展率為E:

(17)

例如:語料庫M,當檢索樣本A時語料庫中確切相關的文檔總數為relD=550;模擬SFE檢索后得到文檔總數DSsfe=2 500,其中,與A語義相關的有DStrue=200,樣本A在基于本體檢索后得到的文檔總數DOontology=500,與查詢樣本A確切相關的文檔數為DOtrue=450。參考以上評價標準,計算相應參數如表4所示。

表4 樣本A評價參數 %

4.2 實驗對比分析

因為本文系統可以輸入自然語言,在驗證自然語言時,基于SFE的查詢,找到自然語言相應的標準表達式再做驗證。數據集中類似“y=ax2+by+c”的標準樣式表達式數量極少,本文選用的樣本盡量簡化為常出現在公式中的局部表達式、符號或字母。實驗樣本選取如表5所示。

表5 實驗樣本選取

在數據集中分別模擬SFE檢索和基于Ontology的數學表達式檢索,對以上選取的樣本返回結果進行數據統計并記錄如表6所示。

表6 實驗數據

對上述數據計算得到評價標準如表7所示。

表7 實驗數據評價值 %

圖4所示為以柱狀圖形式,分析4個樣本經過改進后檢索系統中擴展率在檢索結果集上的分布情況。為進行直觀有效對比,在展示擴展率E的同時,統計改進前檢索正確的相關文檔占改進后檢索的總文檔的百分比,記為保持率,和改進后檢索的錯誤文檔占總文檔的百分比,記為錯誤率。其中,橫坐標為樣本編號,縱坐標為以上3類在結果文檔中所占比例。4個樣本的檢索結果如表8所示。

圖4 基于Ontology的數學表達式檢索結果分布

%

從表7可以看出,改進后的系統無論從查全率還是查準率均比原系統有所提高,尤其是查全率接近百分百。影響查全率RO的因素在于,文檔中有一部分與待檢索查詢詞確實有關聯,但只出現查詢詞或相關查詢詞并未出現對應表達式,在初次檢索中已經被錯誤地過濾掉,屬于該系統中的不可控因素。

從圖4可以看出,每個樣本在有一定保持率的前提下,均有不同程度的擴展,說明經過本體查詢擴展后擴大了原系統的查詢范圍,使得最終檢索結果中與初始查詢詞語義相關的文檔增多,進而顯示出本體查詢擴展的必要性。圖4錯誤率占比較少,表明改進后的系統并不單純地匹配表達式形式,對可能涉及多種學科多種領域的返回文檔使用本體進行語義限定:將初次檢索文檔中表達式形式相同但表示其他學科語義的文檔剔除,或者將表達式相同也在數學領域但表示不同概念的文檔加以區分,使得最終結果語義關聯性大、正確率高。

5 結束語

本文提出一種基于Ontology擴展查詢數學表達式的檢索方法。依據本體在查詢擴展中的優勢同時對查詢詞進行不同程度的詞匯和表達式擴展,在檢索階段達到輸入自然語言或LaTeX格式表達式匹配不同的檢索策略,從而實現與初始查詢詞語義相關的表達式所在文獻的輸出。實驗結果表明,基于本體改進的數學表達式檢索效率比基于SFE的檢索系統在語義檢索方面更優,在查全率、查準率上均有提升,一定程度上擴大了查詢范圍,在語義上限設定了檢索范圍,使得檢索語義明確且集中,更傾向于了解用戶檢索意圖,提升用戶檢索體驗。下一步將增加與完善數學表達式中本體之間的關系構建,并對最終輸出結果集進行相關性排序。

[1] MILLER B R,YOUSSEF A.Technical aspects of the digital library of mathematical functions[J].Annals of Mathematics and Artificial Intelligence,2003,38(1-3):121-136.

[2] MathDex search tool [EB/OL].[2017-04-13].http://www.mathdex.com/8080/mathfind/search.

[3] Math Web search [EB/OL].[2017-04-13].http://kware.eees.iu-bremen.de/.

[4] LIBBRECHT P,MELIS E.Semantic search in leactivemath[C]//Proceedings of the 1st WebALT Conference.Eindhoven,Holland:[s.n.],2006:97-109.

[5] MISUTKA J,GALAMBOS L.Mathematical extension of full text search engine indexer[C]//Proceedings of the 3rd International Conference on Information and Communication Technologies:From Theory to Applications.Damascus,Syria:[s.n.],2008:1-6.

[6] HU X,GAO L,LIN X,et al.WikiMirs:a mathematical information retrieval system for wikipedia[C]//Proceedings of the 13th ACM/IEEE-CS Joint Conference on Digital Libraries.New York,USA:ACM Press,2013:11-20.

[7] SOJKA P,LISKA M.Indexing and searching mathematics in digital libraries[C]//Proceedings of Conference on Intelligent Computer Mathematics.Berlin,Germany:Springer,2011:228-243.

[8] 李 彬.基于SFE的LaTeX表達式檢索系統[D].保定:河北大學,2017.

[9] PINTO J M G,BARTHEL S,BALKE W T.QUALIBETA at the NTCIR-11 math 2 task:an attempt to query math collections[C]//Proceedings of the 11th NTCIR Conference.Tokyo,Japan:[s.n.],2014:103-107.

[10] NTCIRmath 2 wikipedia task[EB/OL].[2017-01-27].http://ntcir11-wmc.nii.ac.jp/index.php/NTCIR-11.

[11] DRAGONI M,PEREIRA C D C,TETTAMANZI A G B.A conceptual representation of documents and queries for information retrieval systems by using light ontologies[J].Expert Systems with Applications,2012,39(12):10376-10388.

[12] KARA S,ALAN O,SABUNCU O,et al.An ontology-based retrieval system using semantic indexing[J].Information Systems,2012,37(4):294-305.

[13] 孟紅偉,張志平,張曉丹.基于領域本體的文獻智能檢索模型研究[J].情報雜志,2013,32(9):180-184.

[14] 張 勝.一種基于領域本體的語義檢索模型[J].軟件導刊,2014,13(3):18-20.

[15] REMI S,VARGHESE S C.Domain ontology driven fuzzy semantic information retrieval[J].Procedia Computer Science,2015,46(2):676-681.

[16] 王旭陽,尉醒醒.基于本體和局部共現的查詢擴展方法[J].計算機科學,2017,44(1):214-218.

[17] RUY E B,GUIZZARDI G,FALBO R A,et al.From reference ontologies to ontology patterns and back[J].Data and Knowledge Engineering,2017,109 :41-69

[18] 鄧志鴻.Ontology 研究綜述[J].北京大學學報,2002,38(5):730-737.

[19] GRUBER T R.A translation approach to portable ontology specifications[C]//Proceedings of Japanese Knowledge Acquisition for Knowledge-based Systems Workshop.Tokyo,Japan:[s.n.],1992:89-108.

[20] NAVIGLI R,VELARDI P.Learning domain ontologies from document warehouses and dedicated websites[J].Computational Linguistics,2004,30(2):151-179.

[21] DRUMOND L,GIRARDI R.A Survey of ontology learning procedures[C]//Proceedings of IEEE Workshop on Ontologies & Their Applications.Washington D.C.,USA:IEEE Press,2008:427.

[22] ANNAMALAI M,STERLING L.Dealing with mathematical relations in web-ontologies[C]//Proceedings of IEEE OAS’03.Washington D.C.,USA:IEEE Press,2003:1-8.

[23] 王小龍.基于本體的數學表達式檢索技術研究[D].重慶:重慶大學,2014.

[24] GRUBER T R.A translation approach to portable onto-logies[J].Knowledge Acquisition,1993,5(2):199-220.

[25] 《數學辭海》編輯委員會.數學辭海(第一卷)[M].太原:山西教育出版社,2002.

[26] PEREZ A G,BENJAMINS V R.Overview of knowledge sharing and reuse components:ontologies and problem-solving methods[C]//Proceedings of Workshop on Ontologies and Problem-Solving Methods.Washington D.C.,USA:IEEE Press,1999:1-15.