李文杰,穗志方
(1. 北京大學(xué) 計算語言學(xué)研究所,北京 100871;2. 北京大學(xué) 計算語言學(xué)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100871)
概念是反映客觀事物及其特有屬性的思維對象,它是知識表示的核心要素。對概念的提取研究分為: (1)概念實(shí)例提取。例如,提取“疾病”概念下的所有疾病名,包括: “感冒”、“心肌炎”等;(2)提取概念的屬性名(例如,提取“疾病”概念的屬性名“癥狀”、“并發(fā)癥”、“用藥”等)。對概念實(shí)例和屬性的提取研究,不僅對Ontology的自動構(gòu)建,而且對其他的自然語言處理任務(wù)比如自動問答、文本分類等都具有重要地指導(dǎo)作用。
在概念實(shí)例和屬性的自動提取方面,當(dāng)前已有很多研究。有一些方法是利用手工構(gòu)造的模式去進(jìn)行提取,比如文獻(xiàn)[1-5],這種方法準(zhǔn)確率比較高,但是人工干預(yù)比較大,召回率也比較低;還有一些是利用半自動或自動的方法去進(jìn)行提取,比如文獻(xiàn)[6-10],監(jiān)督性比較小,但準(zhǔn)確率比較低。
文獻(xiàn)[1] Hearst提出了一種利用手工指定的模式從非限定性文本中自動獲取上下位關(guān)系的方法,這種方法可以獲得很高地準(zhǔn)確率,但是需要人工制訂模式,這種方法提取出的結(jié)果往往都是有限的。文獻(xiàn)[2-3,6]從Web文檔中提取實(shí)例,其中文獻(xiàn)[6]利用迭代的方式對種子實(shí)例集合進(jìn)行擴(kuò)展,文獻(xiàn)[2-3]利用給定的概念和上下位模式通過在搜索引擎中構(gòu)造查詢請求來自動獲取實(shí)例。文獻(xiàn)[7]是利用搜索引擎的查詢?nèi)罩緛磉M(jìn)行實(shí)例提取,文獻(xiàn)[8]提出一種無指導(dǎo)的方法從半結(jié)構(gòu)化的HTML文檔中提取屬性和屬性值對,文獻(xiàn)[9]利用給定的概念和概念的實(shí)例集合從結(jié)構(gòu)化的網(wǎng)頁文本中提取概念屬性,文獻(xiàn)[4]利用手工指定的模式分別對網(wǎng)頁文件和查詢記錄中提取屬性的結(jié)果進(jìn)行了比較。
以上研究大多關(guān)注的是單獨(dú)的概念實(shí)例和屬性提取,而文獻(xiàn)[5]提出了一種利用非常少的種子屬性從Web文檔和搜索引擎查詢?nèi)罩局型瑫r提取實(shí)例和屬性的方法,文獻(xiàn)[10]提出了一種基于Web弱指導(dǎo)的本體概念實(shí)例和屬性的同步提取方法,利用給定的種子實(shí)例和屬性集,在Web搜索引擎中查詢,通過尋找實(shí)例和屬性共現(xiàn)的上下文模式來提取新的概念實(shí)例和屬性。
本文在文獻(xiàn)[10]基礎(chǔ)上提出了一種基于并列結(jié)構(gòu)的概念實(shí)例和屬性的同步提取方法。在同步提取之前,首先利用并列結(jié)構(gòu)去獲得一些同類詞語集合,然后再用這些集合去擴(kuò)充同步提取結(jié)果。實(shí)驗(yàn)結(jié)果表明這種使用并列結(jié)構(gòu)的方法在不降低準(zhǔn)確率的情況下,能大大提高提取結(jié)果的召回率。
本文的結(jié)構(gòu)如下: 第二部分提出了本方法的基本思想;第三部分介紹了本方法各部分的關(guān)鍵技術(shù);第四部分介紹了實(shí)驗(yàn)設(shè)置及對實(shí)驗(yàn)結(jié)果的分析評價;最后對本文的工作進(jìn)行了總結(jié)。
文獻(xiàn)[10] 假設(shè)概念實(shí)例和屬性往往出現(xiàn)在特定的上下文模式中,利用種子實(shí)例和屬性構(gòu)造形如“IH1AH2”(I為種子實(shí)例,A為種子屬性,H1和H2是上下文)的查詢請求,在搜索引擎返回的結(jié)果中自動提取實(shí)例和屬性共現(xiàn)的上下文模式。然后利用這些模式,再構(gòu)造形如“*H1AH2”的查詢請求去提取候選實(shí)例,構(gòu)造形如“IH1*H2”的查詢請求去提取候選屬性。
這種基于模式的同步提取方法有一個很大的缺點(diǎn)就是召回率比較低,當(dāng)提取出模式后,只有當(dāng)某個實(shí)例或?qū)傩阅芫_匹配該模式時才能被提取出。但是通過觀察,我們發(fā)現(xiàn)語料中存在著很多這樣的句子,例如,“心律失常的并發(fā)癥有冠心病、風(fēng)心病、心肌病、高心病、肺心病等。”和“高血壓的病因、癥狀、預(yù)防、治療等”,即很多情況下多個概念實(shí)例和屬性都是以某種并列結(jié)構(gòu)的形式出現(xiàn)在語料中。如果我們提前能通過句子中的并列結(jié)構(gòu)將這幾種疾病歸為一類,當(dāng)我們利用模式提取“疾病”概念實(shí)例時,若發(fā)現(xiàn)了“冠心病”為一個實(shí)例,則只需將其他的“風(fēng)心病、心肌病、高心病、肺心病”等都加入候選實(shí)例集合即可,這樣可以提取出很多基于模式的方法提取不出的候選實(shí)例,屬性的提取也同樣如此。
因此本文提出了基于并列結(jié)構(gòu)的概念實(shí)例和屬性的提取方法,在進(jìn)行提取時融入了并列結(jié)構(gòu)這樣一種特征,能大大提高系統(tǒng)的召回率。和前面的工作類似,本文也選取搜索引擎作為獲得語料的工具。和單一文本相比,Web的信息冗余性能獲得更好地結(jié)果。
基于并列結(jié)構(gòu)的概念實(shí)例和屬性的同步提取方法,其輸入是少量的種子概念實(shí)例和種子屬性,以Web搜索引擎為語料獲取工具。這種方法的整體結(jié)構(gòu)如圖1所示。
它主要包含四個模塊: 基于并列結(jié)構(gòu)的同類詞語提取、上下文模式的提取、候選實(shí)例的提取及候選屬性的提取,下面對這幾部分涉及到的關(guān)鍵技術(shù)分別予以介紹。
圖1 整體結(jié)構(gòu)框架圖
之所以采用并列結(jié)構(gòu)是由于具有并列關(guān)系的兩個詞語表現(xiàn)為相同概念下的特性,即如果并列結(jié)構(gòu)中的一個詞語是某個概念下的實(shí)例(或?qū)傩?,那么跟它具有并列關(guān)系的其他詞語也非??赡芏际窃摳拍钕碌钠渌麑?shí)例(或?qū)傩?。
本文獲取包含并列結(jié)構(gòu)語料的方法是: 利用給定的種子實(shí)例和種子屬性,將種子實(shí)例兩兩組合和種子屬性兩兩組合作為查詢關(guān)鍵詞,在搜索引擎中進(jìn)行查詢,將每個結(jié)果網(wǎng)頁下載下來,對網(wǎng)頁進(jìn)行預(yù)處理,抽取出網(wǎng)頁中的文本內(nèi)容作為語料。
然后人工構(gòu)造并列結(jié)構(gòu)的規(guī)則,提取出語料中能匹配這類規(guī)則的所有詞語。構(gòu)造的規(guī)則為: “S→、詞、詞”,即出現(xiàn)在三個“、”中間的兩個詞語就被認(rèn)為是具有并列結(jié)構(gòu)關(guān)系的詞語對。我們只選取了這一種規(guī)則,是因?yàn)檫@種規(guī)則準(zhǔn)確度很高。有一些其他的規(guī)則也可能包含并列結(jié)構(gòu)信息,例如,出現(xiàn)在“和”字周圍的兩個詞,但是這些規(guī)則準(zhǔn)確度不高,會提取出很多錯誤的詞語對,這些噪音很大程度上會影響后面的提取結(jié)果。
接著將這些詞語對按照貪心的思想進(jìn)行簡單的分塊,分塊遵循的原則是按并查集算法將具有并列結(jié)構(gòu)關(guān)系的詞語放在同一個集合中,算法偽代碼如算法1描述所示。
分塊完成后會生成一個大的集合記作Φ,Φ中包含有很多個詞語集合Φi,每個集合中包含的是同一類的詞語,并且對于Φ中的任意兩個集合Φi和Φj,它們之間沒有交集,因?yàn)槿籀礽和Φj存在著某個共同的詞語,則它們應(yīng)該會被歸并成同一個集合。
這樣做的好處是,可以通過這種方法盡可能多地將表現(xiàn)相同概念的詞放在同一個集合中。在后面的基于模式的提取過程中,若提取出的某個候選實(shí)例或?qū)傩猿霈F(xiàn)在了某個集合Φi中,則可以認(rèn)為Φi中的其他詞語也都為候選概念實(shí)例或?qū)傩浴?/p>
算法1詞語分塊算法
1. 初始時分好塊的詞語集合Φ為空;
2. 對于通過規(guī)則找出的所有具有并列關(guān)系的詞語對集合NounPairs;
取出每一個詞語對中的每一個詞,若該詞在Φ中的某個集合中,就將該詞的詞頻加1,否則在Φ中新建一個集合Set,令該詞的詞頻為1,將該詞加入到Set中;
3. 再取出每一個詞語對,合并詞語對中的兩個詞在Φ中所屬的集合;
4. 返回Φ;
表1給出了“疾病”概念下利用并列結(jié)構(gòu)規(guī)則提取的同類集合示例列表。
表1 通過并列結(jié)構(gòu)提取出的同類詞語集合
3.3.1 模式的提取
和文獻(xiàn)[10]類似,本文提取模式的方法也是根據(jù)給定的種子實(shí)例和種子屬性,對每個種子實(shí)例ins_seed和種子屬性attr_seed,構(gòu)造這樣的查詢關(guān)鍵詞“ins_seedC1attr_seedC2”(C1、C2為通配符)在搜索引擎中進(jìn)行查詢。提取出每一對匹配到的字符串C1和C2,若C1和C2的長度不超過閾值L,就將{C1,C2}加入到候選模式集合P中。例如,種子實(shí)例是“高血壓”,種子屬性是“癥狀”,就構(gòu)造這樣的關(guān)鍵詞“高血壓*癥狀*”去搜索引擎中查詢,找到匹配的句子,若其中的一條返回結(jié)果是“高血壓的癥狀有”,就將“*的*有”拿出來當(dāng)作一個候選模式。
3.3.2 模式的評價
一個候選模式在語料中出現(xiàn)的次數(shù)越多,則表明該模式是一個比較好的模式,應(yīng)該具有相對較高的權(quán)重。因此對于模式集合P中的每一個候選模式Pi,我們定義了如下的模式評價公式:
(1)
其中Conf(Pi)為模式Pi在語料中出現(xiàn)的頻率,freq(Pi)為模式Pi在語料中出現(xiàn)的頻次。
3.4.1 基于模式的概念實(shí)例提取及評價
? 提取
對于3.3提取出的模式集合P中的每一個模式Pi={C1,C2}和每一個種子屬性attr_seed,我們構(gòu)造這樣的模式“*C1attr_seedC2”去搜索引擎中進(jìn)行查詢。然后搜索每一個以該模式開頭的句子,將匹配“*”部分的字符串抽取出來,通過構(gòu)造停用詞表去掉字符串前后的無用信息,若最后剩下的字符串長度在2~10之間,則將其作為候選實(shí)例記作ins。假設(shè)種子屬性是“癥狀”,上一步獲得的模式是“*的*有”,就構(gòu)造這樣的關(guān)鍵詞“*的癥狀有”去搜索引擎中查詢,若其中的一條返回結(jié)果是“感冒的癥狀有”,就將“感冒”拿出來當(dāng)作一個候選實(shí)例。
? 評價
一個模式的置信度值越高,這個模式就越能反應(yīng)概念實(shí)例和屬性之間的關(guān)聯(lián)程度,出現(xiàn)在該模式周圍的候選實(shí)例和屬性就越有可能是正確的概念實(shí)例和屬性。對于由模式Pi和種子屬性提取出的實(shí)例ins,我們定義如下的公式來計算候選實(shí)例ins的置信度值。
(2)
初始時實(shí)例集合Ins為空。若提取出的候選實(shí)例不在實(shí)例集合Ins中,則令其置信度值直接等于模式的置信度值;若提取出的候選實(shí)例已經(jīng)在實(shí)例集合Ins中,則將其以前的置信度值加上模式的置信度值作為其新的置信度值。
3.4.2 利用同類詞語集合對原始候選進(jìn)行擴(kuò)充
提取出原始候選實(shí)例ins后,接著將ins在3.2提取出的集合Φ中進(jìn)行查找,若發(fā)現(xiàn)ins在Φ中的某個詞語集合Φi中,則Φi中的其他詞語都可看作候選實(shí)例。
且Φi中某個詞語的詞頻越大即其與其他詞語出現(xiàn)過并列結(jié)構(gòu)的次數(shù)越多,該詞也越有可能是概念實(shí)例。因此對于通過候選實(shí)例ins在集合Φi中發(fā)現(xiàn)的每個候選實(shí)例ins_par,我們定義如下的公式來計算其置信度值。
Conf(ins_par)
(3)
若ins_par已經(jīng)在實(shí)例集合Ins中,則不改變其置信度值;若ins_par不在實(shí)例集合Ins中,則通過下面的公式來計算其置信度值,其中freq(ins_par)為ins_par在集合Φi中的頻次,freq(ins)為ins在集合Φi中的頻次,Conf(Pi)為發(fā)現(xiàn)候選實(shí)例ins的模式Pi的置信度值,λ為權(quán)重因子。
3.4.1和3.4.2中的過程可以用下面的偽代碼來描述:
算法2基于并列結(jié)構(gòu)的概念實(shí)例提取算法
1. 基于模式的概念實(shí)例提取及評價:
a) 利用種子屬性和模式構(gòu)造關(guān)鍵詞,去搜索引擎中提取候選實(shí)例;
b) 對基于模式的方法提取出的候選實(shí)例進(jìn)行評價。
2. 利用同類詞語集合對原始候選進(jìn)行擴(kuò)充
對于第1步中提取出的每個候選實(shí)例ins:
a) 將ins在同類詞語集合中進(jìn)行查找,找到ins所在的詞語集合,將集合中的其他詞語都當(dāng)作候選實(shí)例;
b) 對這些通過同類詞語集合擴(kuò)充進(jìn)來的候選實(shí)例進(jìn)行評價。
3.5.1 基于模式的屬性提取及評價
? 提取
和實(shí)例提取的方法類似,對每一個上下文模式Pi={C1,C2}和每一個種子實(shí)例ins_seed,我們構(gòu)造查詢關(guān)鍵詞“ins_seedC1*C2”去搜索引擎中獲取屬性提取的語料。然后構(gòu)造同樣的模式“ins_seedC1*C2”去語料中搜索,將匹配“*”部分的全部字符串抽取出來,若字符串的長度在2~8之間,則將其作為候選屬性記作attr。假設(shè)種子實(shí)例是“高血壓”,上一步獲得的模式是“*的*有”,就構(gòu)造這樣的關(guān)鍵詞“高血壓的*有”去搜索引擎中查詢,若其中的一條返回結(jié)果是“高血壓的并發(fā)癥有”,就將“并發(fā)癥”拿出來當(dāng)作一個候選屬性。
? 評價
候選屬性的評價我們也是采用和實(shí)例評價同樣的方法,通過其和模式之間的關(guān)聯(lián)程度來評價。對于每個通過模式Pi提取出的候選屬性attr,我們定義如下的置信度計算公式。
(4)
3.5.2 利用同類詞語集合對原始候選進(jìn)行擴(kuò)充
同樣的,將候選屬性attr在3.2提取出的集合Φ中進(jìn)行查找。對于通過候選屬性attr在Φ中的某個集合Φj中發(fā)現(xiàn)的每個候選屬性attr_par,我們定義和上面類似的公式來計算其置信度值。
Conf(attr_par)
(5)
3.5.1和3.5.2中的過程也可以用下面的偽代碼來描述:
算法3基于并列結(jié)構(gòu)的屬性提取算法
1. 基于模式的屬性提取及評價:
c) 利用種子實(shí)例和模式構(gòu)造關(guān)鍵詞,去搜索引擎中提取候選屬性;
d) 對基于模式的方法提取出的候選屬性進(jìn)行評價。
2. 利用同類詞語集合對原始候選進(jìn)行擴(kuò)充
對于第1步中提取出的每個候選屬性attr:
c) 將attr在同類詞語集合中進(jìn)行查找,找到attr所在的詞語集合,將集合中的其他詞語都當(dāng)作候選屬性;
d) 對這些通過同類詞語集合擴(kuò)充進(jìn)來的候選屬性進(jìn)行評價。
本文以Web為語料,選取百度為獲得語料的工具。除和文獻(xiàn)[10]一樣選取醫(yī)學(xué)領(lǐng)域的“疾病”概念為實(shí)驗(yàn)對象外,我們還選取了“藥物”、“汽車”、“國家”以及“宗教”這幾個概念來評價本方法的提取效果。對于提取結(jié)果,通過人工去判別其準(zhǔn)確性。因?yàn)閃eb上實(shí)例提取結(jié)果的召回率很難去計算,因此我們選取計算提取結(jié)果在所選的黃金標(biāo)準(zhǔn)中的覆蓋率來代替召回率。
4.2.1 “疾病”概念實(shí)驗(yàn)結(jié)果
醫(yī)學(xué)領(lǐng)域以MESH的現(xiàn)代醫(yī)學(xué)領(lǐng)域Ontology作為實(shí)例和屬性提取的黃金標(biāo)準(zhǔn)。該Ontology中包含有3 904個疾病實(shí)例。本文以文獻(xiàn)[10]為Baseline,使用和文獻(xiàn)[10]相同的種子實(shí)例集{感冒、高血壓、鼻炎、頸椎病、腎結(jié)石}和種子屬性集{癥狀、治療、病因},選取了模式提取的前十個模式進(jìn)行實(shí)驗(yàn),評價時令權(quán)重因子λ=1.0。
表1給出了本文的方法和Baseline在黃金標(biāo)準(zhǔn)所有疾病實(shí)例上的覆蓋率之間的對比,而圖2則給出了本文提取結(jié)果前2 000個的準(zhǔn)確率。
由表2和圖2我們發(fā)現(xiàn),Baseline在不使用并列結(jié)構(gòu)的情況下只找出315個實(shí)例,而本文的方法在仍然保持很高的準(zhǔn)確率上,比Baseline多找出431個實(shí)例,覆蓋率從8.1%提高到了19.1%。甚至在前兩百個實(shí)例的準(zhǔn)確率上,本方法的準(zhǔn)確率還高于Baseline。
表2 實(shí)例提取在黃金標(biāo)準(zhǔn)上的覆蓋率對比
圖2 疾病概念下實(shí)例提取的準(zhǔn)確率對比
通過對屬性結(jié)果進(jìn)行評價,我們發(fā)現(xiàn)本文的方法在屬性提取的準(zhǔn)確率上也有很大地提高,這是因?yàn)橛刹⒘薪Y(jié)構(gòu)提取出的同類詞語具有很高地準(zhǔn)確度。圖3給出了屬性提取的準(zhǔn)確率對比。
圖3 疾病概念下屬性提取的準(zhǔn)確率對比
4.2.2 其他概念實(shí)驗(yàn)結(jié)果
除了選取醫(yī)學(xué)下的“疾病”概念為實(shí)驗(yàn)對象外,本文還選了“藥物”、“汽車”、“國家”和“宗教”這幾個概念下的實(shí)例和屬性提取來比較使用并列結(jié)構(gòu)和不使用并列結(jié)構(gòu)的結(jié)果。在進(jìn)行實(shí)驗(yàn)的時候,我們發(fā)現(xiàn)文獻(xiàn)[10]的方法對種子的依賴很強(qiáng),差的種子會得到很差的結(jié)果,并且當(dāng)實(shí)例不是簡單的出現(xiàn)在句子的開頭時,通過模式的方法提取的候選結(jié)果會很差,而從并列結(jié)構(gòu)獲取的候選往往都比較準(zhǔn)確,這個時候我們可以提高從并列結(jié)構(gòu)獲取候選的權(quán)重因子,來獲得不錯的準(zhǔn)確率。
“藥物”概念以上面的醫(yī)學(xué)領(lǐng)域Ontology列出的1 576種藥物為黃金標(biāo)準(zhǔn);“汽車”概念以汽車之家網(wǎng)站列出的101種汽車品牌為實(shí)例提取黃金標(biāo)準(zhǔn);“國家”概念以當(dāng)前聯(lián)合國的192個會員國為實(shí)例提取黃金標(biāo)準(zhǔn);“宗教”以中文維基百科提供的154種宗教為黃金標(biāo)準(zhǔn)。表3給出了幾個概念的實(shí)例提取結(jié)果對比。
在屬性提取方面,對比前三十個候選屬性的準(zhǔn)確率,不使用并列結(jié)構(gòu)與使用并列結(jié)構(gòu)時,“藥物”概念下準(zhǔn)確率從56.7%提高到86.7%,“汽車”概念下準(zhǔn)確率從46.7%提高到60%,“國家”概念下準(zhǔn)確率從50%提高到63.3%,“宗教”概念下準(zhǔn)確率從 56.7% 提高到70%。表4給出了幾個概念下的屬性提取結(jié)果的前十個候選屬性。
表4 屬性提取結(jié)果
本文提出了一種基于并列結(jié)構(gòu)的概念實(shí)例和屬性的同步提取方法,這種方法在基于模式的方法中融入了并列結(jié)構(gòu)這樣一種特殊結(jié)構(gòu),首先通過并列結(jié)構(gòu)提取出一些同類詞語集合,然后再用基于種子的弱指導(dǎo)方法去提取候選實(shí)例和候選屬性,每提取出一個候選,就將該候選所在的同類詞語集合中的其他詞語都加入到候選集合中。并且和以往的以普通文本和網(wǎng)頁文本為語料的方法不同,本文利用搜索引擎對相關(guān)語料的篩選功能,只選擇搜索引擎結(jié)果返回的每組關(guān)鍵詞的前1 000條網(wǎng)頁title和sinnpet來進(jìn)行實(shí)驗(yàn),能大大提高運(yùn)行速率。實(shí)驗(yàn)結(jié)果表明,和單純的同步提取的弱指導(dǎo)方法比,本文的方法在不降低準(zhǔn)確率的基礎(chǔ)上,能大大提高提取結(jié)果的召回率。
[1] M. Hearst. Automatic Acquisition of Hyponyms from Large Text Corpora[C]//Proceedings of the 14th International Conference on Computational Linguistics. Nantes, France, 1992:539-545.
[2] R. C. Wang, W. W. Cohen. Automatic Set Instance Extraction using the Web[C]//Proceedings of ACL-IJCNLP-09, Suntec City, Singapore, August 2009.
[3] Z. Kozareva, E. Riloff, E. Hovy. Semantic class learning from the web with hyponym pattern linkage graphs[C]//Proceedings of ACL-08: HLT, Columbus, Ohio, June: 2008,1048-1056.
[4] M. Pasca, B. Van Durme, N. Garera. The role of documents vs. queries in extracting class attributes from text[C]//Proceedings of the 16th CIKM (CIKM-07), Lisbon, Portugal, 2007:485-494.
[5] M. Pasca, B.V. Durme. Weakly-Supervised Acquisition of Open-Domain Classes and Class Attributes from Web Documents and Query Logs[C]//Proceedings of the ACL-08: HLT. Columbus, Ohio, USA, June 2008.
[6] R. C. Wang, W. W. Cohen. Iterative Set Expansion of Named Entities using the Web[C]//Proceedings of ICDM 2008. Pisa, Italy,2008.
[7] M. Pasca. Weakly-supervised discovery of named entities using web search queries[C]//Proceedings of CIKM-07, New York, NY, USA, 2007: 683-690.
[8] N. Yoshinaga, K. Torisawa. Open-Domain Attribute-Value Acquisition from Semi-Structured Texts[C]//Proceedings of the OntoLex 2007. Busan, South-Korea, 2007.
[9] S. Ravi, M. Pasca. Using structured text for large-scale attribute extraction[C]//Proceedings of the 17th CIKM (CIKM 2008), Napa Valley, California, 2008: 1183-1192.
[10] 康為,穗志方. 基于Web弱指導(dǎo)的本體概念實(shí)例及屬性的同步提取[J]. 中文信息學(xué)報, 2010, 24(1), 54-59.