一種多策略學(xué)習(xí)算法在web信息提取中的應(yīng)用

一種多策略學(xué)習(xí)算法在web信息提取中的應(yīng)用

與普通文本信息不同，web信息具有動(dòng)態(tài)、慢程、無結(jié)構(gòu)等特點(diǎn)。因此，提取web信息通常采用機(jī)器學(xué)習(xí)方法，如j.r.quila提出的foil和ciravenna提出的pioccio。對(duì)于web信息的存儲(chǔ)方法，將機(jī)械學(xué)習(xí)、統(tǒng)計(jì)學(xué)習(xí)和相關(guān)學(xué)習(xí)分為三種類型。機(jī)械學(xué)習(xí)和統(tǒng)計(jì)學(xué)習(xí)適用于web頁的信息提取，相關(guān)學(xué)習(xí)適用于提取web頁之間的鏈接。這種獨(dú)特的學(xué)習(xí)方法在web信息的實(shí)現(xiàn)上有一定的局限性。在此基礎(chǔ)上，我們提出了一種將多種機(jī)會(huì)主義學(xué)習(xí)方法結(jié)合起來的多策略學(xué)習(xí)算法。這三種代表性的機(jī)械學(xué)習(xí)方法相結(jié)合，使不同的方法相互滲透，相互互動(dòng)，提高web信息提取的精度，超過傳統(tǒng)的單一機(jī)械學(xué)習(xí)方法所達(dá)到的水平。1多策略學(xué)習(xí)1.1初始聯(lián)系集的定義針對(duì)Web信息的分布特征,即WWW可以被視作是一個(gè)以網(wǎng)頁為節(jié)點(diǎn)、網(wǎng)頁間超鏈接為邊的有向圖,多策略學(xué)習(xí)算法使用了相關(guān)學(xué)習(xí)的方法來描述Web的圖結(jié)構(gòu),使用特征選取的機(jī)械學(xué)習(xí)和統(tǒng)計(jì)學(xué)習(xí)來描述圖結(jié)構(gòu)中的節(jié)點(diǎn)和邊.因此,在學(xué)習(xí)之前定義以下背景聯(lián)系集作為初始規(guī)則.a.has-word(Page):這個(gè)聯(lián)系集合指出在網(wǎng)頁P(yáng)age中出現(xiàn)了單詞word.一個(gè)特定的聯(lián)系只用于一個(gè)特定的詞(如has-teacher和has-woman等).b.link-to(Hyperlink,Page,Page):這個(gè)聯(lián)系集合代表了數(shù)據(jù)集合中網(wǎng)頁間的超鏈接.對(duì)于一個(gè)給定的超鏈接,第一個(gè)參數(shù)定義了超鏈接的標(biāo)識(shí),第二個(gè)參數(shù)定義了該超鏈接所在的網(wǎng)頁,第三個(gè)參數(shù)定義了該超鏈接所指向的網(wǎng)頁.c.has-anchor-word(Hyperlink):這個(gè)聯(lián)系集合指出在每一個(gè)超鏈接的標(biāo)記文本(如下劃線)中所找到的單詞word.d.not():表示對(duì)以上各個(gè)聯(lián)系集合的取反.1.2新聞特性的生成多策略學(xué)習(xí)算法先采用統(tǒng)計(jì)學(xué)習(xí)與機(jī)械學(xué)習(xí)推導(dǎo)出能夠表述訓(xùn)練集合中大多數(shù)網(wǎng)頁特征的候選語句片斷,然后將其應(yīng)用于背景聯(lián)系集合之上得出可接受的語句片斷,最后運(yùn)用相關(guān)學(xué)習(xí)來完成一條完整Web信息提取規(guī)則的推導(dǎo).算法的具體描述如下.步驟1初始化一條尾部為空的語句L(v1,v2,…,vk).步驟2當(dāng)語句L仍覆蓋反面實(shí)例且不太復(fù)雜時(shí),a.調(diào)用語句片斷生成算法得到新的候選語句片斷Sj(vi);b.根據(jù)背景聯(lián)系集合選擇語句片斷Sj(vi)添加到語句L的尾部;c.生成一個(gè)新的訓(xùn)練集合T′,使得T′與當(dāng)前L中的變量對(duì)應(yīng)起來,對(duì)于T中的每一個(gè)實(shí)例t和語句片段Sj(vi)中的新變量vi,假設(shè)新實(shí)例tvi是連接t和變量vi所得并且tvi滿足Sj(vi),那么將tvi加入T′,其正反屬性與t的正反屬性一致;d.將T′代替T;e.對(duì)于每一條語句片斷Sj(vi),如果Sj(vi)被L選中,那么將其作為背景聯(lián)系保留.步驟3通過去掉無用的語句片段來修改規(guī)則定義.本算法的關(guān)鍵是在步驟2中用到的語句片斷生成算法,它在相關(guān)學(xué)習(xí)的基礎(chǔ)上結(jié)合統(tǒng)計(jì)學(xué)習(xí)思想,生成的語句片斷Sj(vi)是一條一元Boolean類型的斷言,用來描述語句L中的變量vi.它是通過在問題域中的常量特征集合上運(yùn)用統(tǒng)計(jì)學(xué)習(xí)來推演得出的.1.3web信息提取假設(shè)問題域中的每個(gè)常量都屬于一個(gè)類型,每個(gè)類型對(duì)應(yīng)一個(gè)或多個(gè)網(wǎng)頁集合且每一個(gè)給定類型的常量又對(duì)應(yīng)該類型的網(wǎng)頁集合中唯一一張網(wǎng)頁,那么算法的具體描述如下:步驟1輸入尚未完全生成的語句(或規(guī)則)L(v1,v2,…,vk)和各種類型的Web頁集合;步驟2對(duì)于語句L中的每一個(gè)變量vi:對(duì)于與vi的類型相關(guān)的每一個(gè)網(wǎng)頁集合Pj,a.C1={集合Pj中表示與變量vi所綁定的常量的正面實(shí)例},b.C2={集合Pj中表示與變量vi所綁定的常量的反面實(shí)例},c.根據(jù)目標(biāo)類型的公共信息來為集合C1∪C2中的每一個(gè)詞語賦一個(gè)權(quán)值,d.n=|C1∪C2|×e(其中e為有效規(guī)模參數(shù),用來控制n的有效值),e.D={權(quán)值較高的前n個(gè)詞語},f.假設(shè)D={w1,w2,…,wn},那么在特征集合D上運(yùn)用貝葉斯統(tǒng)計(jì)方法,即argmaxP(vi|w1,w2,…,wn),學(xué)習(xí)得出語句片斷Sj(vi).由于Web信息提取規(guī)則需要總結(jié)的是訓(xùn)練集合中大多數(shù)網(wǎng)頁的共同特征,因此在構(gòu)造特征詞語集合D時(shí)不必將訓(xùn)練集合中出現(xiàn)的所有詞語作為貝葉斯的考慮對(duì)象,而是如本步驟2中c,d和e所描述的那樣先為每個(gè)詞語賦權(quán)值并按權(quán)值排序后,取前n個(gè)詞語來構(gòu)成特征集合.2實(shí)驗(yàn)結(jié)果與分析MUC(MessageUnderstandingConference)會(huì)議為信息檢索和信息提取領(lǐng)域內(nèi)的算法性能測試制定了一系列的評(píng)估參數(shù).設(shè)總共需要提取的信息數(shù)目為N,提取正確的信息數(shù)目為Ncorrect,提取錯(cuò)誤的信息數(shù)目為Nincorrect,那么信息查全率Re和提取精確度pr如下:Re=Ncorrect/N;pr=Ncorrect/(Ncorrect+Nincorrect).通常查全率和精確度需要一起考慮.例如,在網(wǎng)頁數(shù)目較少的情況下機(jī)械學(xué)習(xí)算法得出的提取精確度較高,使得它看起來似乎是較強(qiáng)的提取方法,然而較低的查全率表明機(jī)械學(xué)習(xí)的高精確度只是在網(wǎng)頁集合較小的情況下才得到的.因此為了使評(píng)估結(jié)果更全面、更具說服力,在比較多個(gè)提取算法的性能時(shí)通常是將精確度pr和查全率Re結(jié)合成一個(gè)綜合性的數(shù)據(jù)F,定義為如下形式:F=(β2+1.0)prRe/(β2pr+Re)?式中參數(shù)β決定了查全率與精確度的比值.實(shí)驗(yàn)數(shù)據(jù)來源于網(wǎng)上收集的大約5000張包含藥品信息的醫(yī)藥廣告網(wǎng)頁,將結(jié)合前的三種機(jī)器學(xué)習(xí)算法和結(jié)合后的多策略學(xué)習(xí)算法分別應(yīng)用于這個(gè)網(wǎng)頁集合之上,對(duì)集合中每張網(wǎng)頁上的藥品信息按照藥品名稱、批準(zhǔn)文號(hào)、功能主治分別提取出來,并依據(jù)前面提到的評(píng)估策略對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估,得出所提取的藥品信息的查全率Re和精確度pr并計(jì)算出F值.由于本實(shí)驗(yàn)的重點(diǎn)評(píng)估對(duì)象是查全率Re和精確度pr共同構(gòu)成的綜合數(shù)據(jù)F,因此本實(shí)驗(yàn)中假設(shè)Re和pr的比值相同,即β=1.具體實(shí)驗(yàn)結(jié)果如表1所示.實(shí)驗(yàn)結(jié)果表明:多策略學(xué)習(xí)算法對(duì)于每一類藥品信息提取結(jié)果的F值都明顯高于前三種學(xué)習(xí)算法,而且在保持信息提取精確度pr相對(duì)穩(wěn)定且有一定上升的情況下使得信息的查全率Re也大大增加,因此多策略學(xué)習(xí)算法性能優(yōu)于前三種單一的機(jī)器學(xué)習(xí)算法,將其應(yīng)用于Web信息的提取也更加精確、有效.將機(jī)