基于決策樹和馬爾科夫鏈的互聯(lián)網(wǎng)應(yīng)答系統(tǒng)

基于決策樹和馬爾科夫鏈的互聯(lián)網(wǎng)應(yīng)答系統(tǒng)

1自動答對系統(tǒng)實(shí)驗(yàn)數(shù)據(jù)集和自動抽樣問題隨著互聯(lián)網(wǎng)的快速發(fā)展，人們所需要的大部分知識都可以存在于互聯(lián)網(wǎng)的一些網(wǎng)站上，但如何快速有效地檢索用戶需要的信息，已成為互聯(lián)網(wǎng)應(yīng)用中一個眾所周知的技術(shù)問題。自動問答系統(tǒng)、個性化搜索、社區(qū)搜索、搜索結(jié)果自動排序是解決這些技術(shù)問題的有效研究方法。本文是面向基于問答對庫的自動問答系統(tǒng)的需要,開展互聯(lián)網(wǎng)上問答對的自動抽取研究。自動問答系統(tǒng)是一種支持用戶以自然語言方式給出自己問題(或需要搜索的知識)的答案搜索系統(tǒng),同時反饋給用戶更直接、更精簡的答案。例如當(dāng)用戶希望了解“哪個國家是最大的內(nèi)陸國”時,用戶可以直接將上述自然語言的句子輸入自動問答系統(tǒng),則系統(tǒng)將直接給出答案:“哈薩克斯坦”,而不需要再從通用搜索引擎上搜索“內(nèi)陸國最大”得到的大量網(wǎng)頁鏈接中去找尋真正的答案?；诖笠?guī)模問答對庫的自動問答系統(tǒng)是問答系統(tǒng)中比較簡單和有效的技術(shù)路線,此種技術(shù)對用戶輸入的問題,從預(yù)先保存好的大規(guī)模已經(jīng)回答過的問題中尋找最為合適的,并將其答案部分直接反饋給用戶,所以對答案生成和問題理解技術(shù)相對來說依賴得比較少。問答對的規(guī)模是影響基于問答對的自動問答系統(tǒng)最終性能的主要因素,因此如何搜集大規(guī)模高質(zhì)量的問答對是一項(xiàng)具有實(shí)際意義和研究價值的科研課題。現(xiàn)實(shí)中,互聯(lián)網(wǎng)上已經(jīng)積累了非常大規(guī)模的問答對,這些問答對大多以FAQ頁面或者某些類似于BBS的網(wǎng)站上一問多答方式存在,如圖1所示的是一個典型的包含多個問答對的FAQ頁面。如果能自動收集起來這些問答對,將對基于問答對的自動問答系統(tǒng)提供非常有利的支撐。然而互聯(lián)網(wǎng)上的問答對只是面向網(wǎng)頁瀏覽用戶而設(shè)計(jì)和書寫的,一般僅僅是以HTML甚至簡單文本方式存儲,書寫格式更是沒有統(tǒng)一的規(guī)范,因此如何從這些不規(guī)范的問答對網(wǎng)頁中,抽取出格式化的問答對,是一個比較典型的信息抽取問題,也是一個比較有挑戰(zhàn)的問題。我們在網(wǎng)上搜集了500個網(wǎng)頁(為了得到更多的問答對,這里的網(wǎng)頁通過在商用搜索引擎上搜索關(guān)鍵字“FAQ”獲得的),經(jīng)過統(tǒng)計(jì),明顯帶有表征問題對的關(guān)鍵字(如:“問”、“答”)的問答對只有651對,只占全部2113個問答對的30.81%。本文計(jì)劃聚焦這一問答對抽取問題,提出一種基于決策樹和馬爾科夫鏈的自動抽取算法。實(shí)驗(yàn)結(jié)果表明,我們的方法效果顯著,準(zhǔn)確率達(dá)到了98.97%。就我們的調(diào)研范圍,目前還沒有此方面的研究成果發(fā)表。2基于機(jī)器學(xué)習(xí)的信息抽樣研究一般來說,在信息抽取領(lǐng)域主要存在兩種信息抽取的方法:基于規(guī)則的方法和基于機(jī)器學(xué)習(xí)的方法。由于互聯(lián)網(wǎng)網(wǎng)頁的格式不統(tǒng)一,基于規(guī)則的方法存在規(guī)則不易構(gòu)造且普適性很難保證等問題,因此目前的研究更多采用基于機(jī)器學(xué)習(xí)方法進(jìn)行信息抽取。在本文中我們也采用了基于機(jī)器學(xué)習(xí)的方法進(jìn)行問答對的自動抽取研究?；ヂ?lián)網(wǎng)上信息抽取領(lǐng)域前人已經(jīng)做了很多研究:比如新聞信息的提取;文獻(xiàn)提出了一種在網(wǎng)頁中提取標(biāo)題的方法,本文在特征選擇上部分借鑒了文獻(xiàn)的方法;文獻(xiàn)給出了一種采用統(tǒng)計(jì)方法結(jié)合受限自然語言理解技術(shù)的模糊關(guān)鍵詞集合提取方法。3基于多媒體文件學(xué)習(xí)的時代分類方法本文將采用機(jī)器學(xué)習(xí)和馬爾可夫鏈相結(jié)合的方法進(jìn)行問答對抽取工作。本方法適用于互聯(lián)網(wǎng)上大多數(shù)的網(wǎng)頁。主要分為兩步來完成:訓(xùn)練和抽取。在訓(xùn)練過程中我們首先把HTML文件轉(zhuǎn)變?yōu)镈OM樹的形式,然后針對DOM樹中每一個有內(nèi)容的葉子節(jié)點(diǎn)提取特征,通過C4.5決策樹算法建立分類模型。具體各部分工作如下:3.1樹狀結(jié)構(gòu)的建立由于HTML的“標(biāo)記”只是告訴瀏覽器如何顯示所定義的信息,故由HTML語言所表述的Web頁面不適合由機(jī)器處理。當(dāng)前主要采用DOM樹來進(jìn)行信息抽取。預(yù)處理的目標(biāo)是將新聞網(wǎng)頁的HTML腳本轉(zhuǎn)化為只包含有意義信息的樹狀結(jié)構(gòu)。具體步驟如下:(1)刪除新聞網(wǎng)頁HTML腳本中的與正文抽取不相關(guān)的信息,如注釋、Java代碼等;(2)建立樹狀結(jié)構(gòu)。網(wǎng)頁的HTML腳本本身是嵌套的,因此我們可以比較容易的根據(jù)HTML的腳本建立成對應(yīng)的樹狀結(jié)構(gòu)(即DOM樹),并將所有的文字信息掛接在葉子節(jié)點(diǎn),同時把HTML的轉(zhuǎn)義字符都變換為正常的字符,如“<”變換為“<”,“&”變換為“&”等,并刪除所有不包含任何文字的葉子節(jié)點(diǎn);(3)合并段落。我們通過觀察發(fā)現(xiàn),問答對的問題或答案本身部分一般都不會跨越網(wǎng)頁的段落,因此我們的實(shí)驗(yàn)以段落為最小決策單元。這里的段落指網(wǎng)頁中在同一行內(nèi)顯示,而未被〈p〉、〈br〉、〈h1〉等HTML分段指示標(biāo)記分隔開的文字片段。但是因?yàn)橐粋€段落中有時會因?yàn)榘恍┳煮w約束標(biāo)記等HTML標(biāo)記而在建立樹狀結(jié)構(gòu)時被拆分成了多個葉子節(jié)點(diǎn),因此我們需要進(jìn)行段落合并處理,使得每個葉子對應(yīng)一個段落。合并段落就是把所有中間沒有段落邊界標(biāo)記的相鄰葉子節(jié)點(diǎn)合并為一個節(jié)點(diǎn)。依據(jù)HTML的標(biāo)記定義,通過分析網(wǎng)頁在瀏覽器中的顯示與該頁面的源代碼的對應(yīng)關(guān)系,可以發(fā)現(xiàn)下列的標(biāo)記是分段指示標(biāo)記:〈P〉、〈BR〉、〈H1〉、〈H2〉、〈H3〉、〈H4〉、〈H5〉、〈H6〉、〈TABLE〉、〈TR〉、〈HR〉、〈DIV〉和〈CENTER〉,而源HTML腳本中的回車符則是可以忽略的。我們定義預(yù)處理完成后的樹狀結(jié)構(gòu)為DOM樹,圖2給出了圖1所示網(wǎng)頁對應(yīng)的DOM樹(局部)。3.2學(xué)習(xí)階段和算法DOM樹建立之后,本文以DOM樹上每一個葉子節(jié)點(diǎn)作為問答對的問題或答案的候選,于是文本的研究目標(biāo)就具體化為一個典型的分類決策問題,決策每個葉子節(jié)點(diǎn)是三種類別中的哪一種,三種類別分別是:問題部分、答案部分以及什么都不是(以下分別記為Q,A和N三個類別)。本文計(jì)劃引入機(jī)器學(xué)習(xí)的方法來建立這樣分類器?；跈C(jī)器學(xué)習(xí)的分類器構(gòu)建一般被稱為訓(xùn)練階段,一般需要經(jīng)過三個階段:訓(xùn)練數(shù)據(jù)標(biāo)注、特征提取和分類器訓(xùn)練。本文的訓(xùn)練階段具體操作如下:(1)收集了一批網(wǎng)頁,并生成對應(yīng)的DOM樹,并在專門研發(fā)的標(biāo)注工具支持下,人工標(biāo)注了每個葉子節(jié)點(diǎn)分別是Q、A和N三類別中的哪一類,完成用于訓(xùn)練的標(biāo)注網(wǎng)頁集構(gòu)建;(2)對于這些DOM樹中的每一個節(jié)點(diǎn),本文提取多維特征組成的一個特征向量,并與人工標(biāo)記的類別組合在一起形成一個訓(xùn)練例子,所有這些樣例就組成了訓(xùn)練數(shù)據(jù)文件;(3)基于訓(xùn)練數(shù)據(jù)文件,完成分類器訓(xùn)練。有多種機(jī)器算法可以從這些訓(xùn)練數(shù)據(jù)中訓(xùn)練得到分類模型,本文采用了其中的一種,決策樹算法,具體的本文采用了C4.5算法,具體算法參見文獻(xiàn)。通過C4.5算法的訓(xùn)練程序,我們可以訓(xùn)練得到一棵分類決策樹。當(dāng)我們需要對一個新網(wǎng)頁進(jìn)行問答對抽取時,這一問題可以同理轉(zhuǎn)換為新網(wǎng)頁所對應(yīng)的DOM樹每個葉子節(jié)點(diǎn)分別是哪個類別,這一階段一般被稱為決策或測試階段。這一階段具體操作如下:對每個葉子節(jié)點(diǎn)提取一個同訓(xùn)練階段一樣的特征向量,然后把這一向量輸入到訓(xùn)練過程得到的分類決策樹進(jìn)行判決,以得到這一葉子節(jié)點(diǎn)分別屬于Q、A及N三個類別的決策概率;最后把決策概率最大的類作為判斷結(jié)果輸出。與大部分機(jī)器學(xué)習(xí)算法相似,對于C4.5算法來說最重要的是特征的選擇,特征能否反映分類問題的本質(zhì),決定了整個分類器構(gòu)建的成敗。3.3特征的提取過程在3.2小節(jié)中提到的,要想利用分類模型算法得到很好的分類效果,關(guān)鍵就是找到能夠反映分類問題本質(zhì)的特征。本文中,針對問答對抽取的分類問題,本文最多一共嘗試提取了71維的特征,但考慮到效率和特征對于判斷結(jié)果的影響,最終我們選擇了其中的31維特征,實(shí)驗(yàn)表明這31維特征能夠很好的從所有的DOM樹的葉子節(jié)點(diǎn)中區(qū)分出問題部分以及答案部分。在特征的提取過程中,本文主要考慮了以下信息和結(jié)構(gòu)特征,具體31維特征定義如表1所示。(1)網(wǎng)頁的純文本信息;網(wǎng)頁的結(jié)構(gòu)、格式信息,如當(dāng)前節(jié)點(diǎn)文字的顏色、字體信息,鏈接信息以及相鄰節(jié)點(diǎn)是否有相同結(jié)構(gòu),即兩個節(jié)點(diǎn)的XPath中是否僅僅差別一個索引號,如圖2中選中的“Q第五大區(qū)(電信—上海)…”節(jié)點(diǎn)與其上下并排的幾個節(jié)點(diǎn)就都屬于具有相同結(jié)構(gòu)的節(jié)點(diǎn),簡稱同構(gòu)節(jié)點(diǎn)。XPath的具體定義參見文獻(xiàn);(2)全局信息,利用了BhnI等的研究工作,在文獻(xiàn)中BhnI利用在歸納學(xué)習(xí)過程中加入了上下文規(guī)則較大幅度的提高了查準(zhǔn)率。4問答和提取4.1q、a和n之間的關(guān)系基于決策樹的問答對抽取算法實(shí)現(xiàn)了對每個DOM樹葉子節(jié)點(diǎn)的類別判決,但整個判決過程中假設(shè)各個節(jié)點(diǎn)的類別決策之間相互獨(dú)立。然而這一假設(shè)顯然不成立,因?yàn)?在一個網(wǎng)頁中比較Q、A和N之間存在一定的順序關(guān)系,如A之前一般必須有Q,而Q之后往往也會有A,同時由于一般而言問題極少跨越多個段落(即Q后一般不接Q),而答案部分則比較容易因?yàn)閮?nèi)容較長而分割成多個段落(因此會有多個A連續(xù)出現(xiàn)的情況)。因此為了修正決策樹的獨(dú)立決策的不當(dāng),這些不同的概率特性可以很好。為了克服僅僅基于決策樹的問答對自動抽取技術(shù)的缺陷,同時考慮到上述類別之間的相互關(guān)系可以用馬爾科夫鏈來描述,因此本文加入了一階馬爾可夫鏈模型對決策樹的決策結(jié)果進(jìn)行修正。4.2基于動態(tài)規(guī)劃的viterbi算法這里假設(shè)訓(xùn)練集內(nèi)的每個標(biāo)注頁面都可以按其DOM樹葉子節(jié)點(diǎn)的類別表示為一個Q、A和N三個字母組成的長串,則我們可以從這些長串中統(tǒng)計(jì)得到三個類別之間的3*3的轉(zhuǎn)移矩陣,記為T(d|c),其中c,d∈{Q,A,N},且:T(d|c)=Count(cd)Count(c)(1)Τ(d|c)=Count(cd)Count(c)(1)公式(1)中,Count(cd)表示類別c后緊接著出現(xiàn)類別d的次數(shù),Count(c)表示類別c出現(xiàn)的次數(shù)。因此假設(shè)對于一個新的網(wǎng)頁所對應(yīng)DOM樹,假設(shè)葉子節(jié)點(diǎn)個數(shù)為L個,則基于決策樹的方法可以得到這L個葉子節(jié)點(diǎn)作為每一個類別的概率P(xi=ci),1≤i≤L,ci∈{Q,A,N}?？紤]到各個節(jié)點(diǎn)類別判決結(jié)果之間的相互關(guān)系,本文采用基于動態(tài)規(guī)劃的Viterbi算法從3L種可能的判決結(jié)果中搜索出一條最佳的路徑(記為(c1,…,ci,…,cL)*,ci∈{Q,A,N}),使得該路徑滿足:(c1,c2,?,cL)?=argmax(c1,c2,?,cL)∏i=1LT(ci|ci?1)×P(xi=ci)(2)(c1,c2,?,cL)*=argmax(c1,c2,?,cL)∏i=1LΤ(ci|ci-1)×Ρ(xi=ci)(2)這種方法的實(shí)驗(yàn)結(jié)果與沒有加入馬爾科夫鏈修正的結(jié)果相比效果不但沒有上升,反而下降比較明顯。通過分析發(fā)現(xiàn),這是由于在大部分網(wǎng)頁中問答對存在的數(shù)目與所有的節(jié)點(diǎn)數(shù)目相比要少的多,這使得求出的條件概率中T(N|N)特別大,在(2)式中占主導(dǎo)地位,結(jié)果很容易就把所有的節(jié)點(diǎn)被判為N類。針對這一問題,我們通過大量的觀察統(tǒng)計(jì),發(fā)現(xiàn)了這樣的一條規(guī)律:一般情況下答案(問題)有多行時所對應(yīng)的葉子節(jié)點(diǎn)會集中在一個相同的父節(jié)點(diǎn)之下,這為我們的研究指明了方向,本文正是利用當(dāng)前節(jié)點(diǎn)與其前一節(jié)點(diǎn)是否具有相同結(jié)構(gòu)這一信息來對我們3*3轉(zhuǎn)移概率矩陣T(d|c)進(jìn)行了修正:(1)定義T′(d|c)為:T′(d|c)=Count(cd)Count(c),c與d同構(gòu)(3)Τ′(d|c)=Count(cd)Count(c),c與d同構(gòu)(3)(2)決策時,但前后節(jié)點(diǎn)同構(gòu)時,采用T′(d|c)作為轉(zhuǎn)移概率,否則仍采用T(d|c)。實(shí)驗(yàn)表明,同構(gòu)這一限制使得大部分的N節(jié)點(diǎn)被排除在分母的統(tǒng)計(jì)之中,實(shí)現(xiàn)了Q、A和N三種類別之間的有效平衡。4.3q、a定義的抽樣當(dāng)我們根據(jù)上面的決策和修正算法得到葉子節(jié)點(diǎn)所對應(yīng)的類別序列(c1,…,ci,…,cL)*之后,我們將按Q、A順序出現(xiàn)的相隔最近的一對Q、A定義并抽取為一個問答對,這是由于一般情況下答案都會緊跟在所回答的問題的后面,這樣做在最后的選擇結(jié)果中過濾掉了分類結(jié)果不能構(gòu)成問答對的節(jié)點(diǎn),如比所有Q都先出現(xiàn)的A或是比所有A都后出現(xiàn)的Q。4.4簡化答對的操作為了能把抽取到的問答對應(yīng)用到實(shí)際的自動問答系統(tǒng)中,問答對抽取必須保證有一個很高的準(zhǔn)確率,因此為了進(jìn)一步提高抽取的準(zhǔn)確率,我們對上一小節(jié)得到的問答對我們采用基于以下簡單規(guī)則的取舍操作:(1)刪除最后的問答對,這是由于往往最后一個問答對可能會存在多余的信息;(2)當(dāng)一個網(wǎng)頁的問答對數(shù)目小于兩個時,忽略抽取結(jié)果;(3)當(dāng)答案為多段時,為了得到的答案很完整,當(dāng)答案的段數(shù)大于3時,舍棄這個問答對。這樣操作之后,將在舍棄一部分問答對的基礎(chǔ)上,較明顯的提高抽取出的問答對的準(zhǔn)確率。我們提出這一面向準(zhǔn)確率的抽取方法是考慮到互聯(lián)網(wǎng)的網(wǎng)頁規(guī)模龐大,因此在一個網(wǎng)頁中漏掉的信息很可能可以在其他網(wǎng)頁中找到。5結(jié)果5.1q和a都與q和a一致時為了對比不同問答對自動抽取的效果,本文采用準(zhǔn)確率(Precision)、召回率(Recall)及F1-Score指標(biāo)來進(jìn)行抽取性能的評價。這里我們記A為人工判斷為問答對的集合,B為機(jī)器自動抽取得到問答對的集合。這里我們定義當(dāng)且僅當(dāng)機(jī)器抽取的問答對的Q和A都與人工標(biāo)注的Q和A完全一致時,才認(rèn)為此問答對被正確的抽取。準(zhǔn)確率、召回率及F1-Score定義如下:Precision=∥A∩B∥|B|×100%Recall=∥A∩B∥|B|×100%(4)F1?Score=2*Precision*RecallPrecision+Recall(5)Ρrecision=∥A∩B∥|B|×100%Recall=∥A∩B∥|B|×100%(4)F1-Score=2*Ρrecision*RecallΡrecision+Recall(5)F1-Score是準(zhǔn)確率與召回率結(jié)合起來進(jìn)行評判的方法,更能夠客觀的反映實(shí)驗(yàn)?zāi)Ｐ偷男Ч?.2規(guī)范標(biāo)注網(wǎng)頁集為了實(shí)驗(yàn)本文提出的基于決策樹和馬爾科夫鏈的問答對自動抽取技術(shù),本文數(shù)據(jù)集為以“FAQ”為關(guān)鍵詞利用Google中文搜索引擎搜索得到前500個網(wǎng)頁(2005年9月收集)。我們對這500個網(wǎng)頁轉(zhuǎn)化為DOM樹并基于自行研發(fā)的標(biāo)注工具在DOM樹上標(biāo)注出所有的Q和A類型的葉子節(jié)點(diǎn),形成了標(biāo)注網(wǎng)頁集。統(tǒng)計(jì)表明,此500個網(wǎng)頁的標(biāo)注集上,人工一共標(biāo)注了2113個問答對。鑒于本文建設(shè)的數(shù)據(jù)集規(guī)模較小以及問答對標(biāo)注工作量較大,因此本文采用4-Fold的交叉