朱文琰 鄭肖雄

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院智能信息處理重點實驗室 上海 200433)

基于正則表達(dá)式構(gòu)建學(xué)習(xí)的網(wǎng)頁信息抽取方法

朱文琰 鄭肖雄

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院智能信息處理重點實驗室 上海 200433)

正則表達(dá)式作為信息抽取領(lǐng)域中的一種常用方法已經(jīng)被廣泛應(yīng)用多年。然而構(gòu)建高質(zhì)量并且復(fù)雜度較高的正則表達(dá)式通常需要耗費大量人工成本，為此，提出一種基于正則表達(dá)式狀態(tài)轉(zhuǎn)換的算法來學(xué)習(xí)復(fù)雜正則表達(dá)式的構(gòu)建過程。該算法需要給定輸入初始正則以及正反例樣本，初始正則表達(dá)式在經(jīng)過析取分離與合并交叉兩大類正則表達(dá)式狀態(tài)轉(zhuǎn)換之后，得到候選正則表達(dá)式集合，利用F值評估候選項的信息抽取效果，通過貪心的啟發(fā)式策略選擇一個最優(yōu)正則表達(dá)式作為輸出。在多種數(shù)據(jù)集上對算法進(jìn)行測評。實驗表明，該算法性能與準(zhǔn)確度均優(yōu)于常規(guī)的機(jī)器學(xué)習(xí)方法。尤其在較小規(guī)模訓(xùn)練集和跨數(shù)據(jù)集上依然有較好的效果。

正則表達(dá)式構(gòu)建 狀態(tài)轉(zhuǎn)換 Web信息抽取

0 引 言

大部分的信息抽取任務(wù)可以通過精心構(gòu)建的正則表達(dá)式來抽取相應(yīng)的實體。例如郵箱地址、電話號碼、信用卡號碼和身份證號碼、基因和蛋白質(zhì)名稱等。在標(biāo)準(zhǔn)的正則表達(dá)式構(gòu)建過程中，以上提到的這些實體所代表的特征模式均能夠被很好地表現(xiàn)出來。構(gòu)建這樣的正則表達(dá)式原型是非常簡單直接的，但事實上，考慮到方法的健壯性要求，通常就需要更加復(fù)雜的規(guī)則。盡管信息抽取領(lǐng)域已有許多機(jī)器學(xué)習(xí)的方法，包括最大熵馬爾科夫模型[1]、監(jiān)督學(xué)習(xí)[2]、字符類模型[3]、半監(jiān)督學(xué)習(xí)[4]、無監(jiān)督學(xué)習(xí)[5]等。但是在實際的信息抽取任務(wù)中，人工構(gòu)建的正則表達(dá)式依然被廣泛采用[6]。事實上，如何通過自動學(xué)習(xí)的方法來減少在構(gòu)建正則表達(dá)式過程中的人工消耗是信息抽取領(lǐng)域的一個難題。本文提出了一個基于正則表達(dá)式學(xué)習(xí)的信息抽取方法，將標(biāo)注過的正反例樣本以及一個初始的正則表達(dá)式作為輸入，通過一系列正則表達(dá)式的狀態(tài)變換得到一組備選正則集合，在多組備選集合上根據(jù)其在標(biāo)注樣本上的信息抽取效果，選出最優(yōu)正則表達(dá)式作為輸出。通過實驗可以證明，該方法能夠顯著減少在信息抽取初期構(gòu)造復(fù)雜正則表達(dá)式的人工成本，在一些特定類型的信息抽取任務(wù)中具有較好的效果。尤其是在較小規(guī)模的訓(xùn)練集以及跨數(shù)據(jù)集上有不錯的表現(xiàn)，能夠構(gòu)造出高質(zhì)量的正則表達(dá)式。

1 相關(guān)工作

信息抽取是自然語言處理研究中的重要部分，網(wǎng)頁信息抽取是指在半結(jié)構(gòu)化的網(wǎng)頁內(nèi)容中抽取結(jié)構(gòu)化數(shù)據(jù)的過程。目前，信息抽取系統(tǒng)在實現(xiàn)上主要分為兩大類，分別是基于統(tǒng)計學(xué)習(xí)的方法和基于規(guī)則模式的匹配方法。兩者互有優(yōu)劣，統(tǒng)計學(xué)習(xí)的方法具有可移植性和魯棒性，但是都需要大量訓(xùn)練數(shù)據(jù)來完成對參數(shù)的設(shè)置以及對系統(tǒng)的優(yōu)化?；谝?guī)則的匹配方法具有較高的效率和準(zhǔn)確率。但是規(guī)則的生成需要較高的代價。所以規(guī)則的自動生成是信息抽取領(lǐng)域的重要問題。

第一個實現(xiàn)規(guī)則的機(jī)器學(xué)習(xí)方法的是 Cristal 信息抽取系統(tǒng)[7]。這個系統(tǒng)先從訓(xùn)練樣本中生成規(guī)則集合，抽取方法是每一個實例提取出一個原始規(guī)則。然后循環(huán)從規(guī)則集合中選擇兩個相似度最高的規(guī)則進(jìn)行合并，最后得到最小規(guī)則集。 Crystal 系統(tǒng)目前只能夠支持單槽的信息抽取，它的缺陷是無法確定目標(biāo)字段的界限。WHISK[8]抽取系統(tǒng)通過將規(guī)則的約束條件不斷增加來得到最終的結(jié)果。此系統(tǒng)首先確定能夠能覆蓋所有樣例的規(guī)則最普通范式，然后通過訓(xùn)練樣本對規(guī)則增加特征和限制進(jìn)行拓展，滿足一定的錯誤率要求后停止訓(xùn)練，得到最終的集合。AutoSlog 是基于模板詞典的規(guī)則構(gòu)造器，它能夠自動地構(gòu)造指定領(lǐng)域的詞典，這樣的模板也叫做概念節(jié)點。一個概念節(jié)點包含如下部分:概念位元、 語言規(guī)則以及觸發(fā)條件[9]。其中位元包含了一系列用于觸發(fā)的詞組，觸發(fā)條件對 生成的語言規(guī)則在語法上進(jìn)行了一些約束。RAPIER[10]是基于邏輯的一種信息抽取系統(tǒng)，從訓(xùn)練語料上歸納出所需要的抽取規(guī)則。RAPIER 采用的是自底向上的學(xué)習(xí)算法，從具體某一個樣本的規(guī)則歸納為 覆蓋全集的范式。RAPIER系統(tǒng)在執(zhí)行規(guī)則生成的過程中運(yùn)用了語義和句法的信息。SRV[11]是一種基于關(guān)聯(lián)的信息抽取系統(tǒng)，采用了自頂向下的歸納式算法進(jìn)行信息抽取。該系統(tǒng)應(yīng)用分類算法來完成抽取任務(wù)，具有相同大小的文本數(shù)據(jù)被選取為候選項，這些候選項將在后續(xù)作為分類器的輸入。候選短語在文本訓(xùn)練數(shù)據(jù)上的覆蓋率是其在規(guī)則中出現(xiàn)的概率估計。

近年來，關(guān)于通過正負(fù)樣本來學(xué)習(xí)正則語言的方法有很多[12-15]。其中大部分的工作通常假設(shè)所學(xué)習(xí)的目標(biāo)表達(dá)式比較簡單。例如在DNA定序應(yīng)用的模式學(xué)習(xí)中[16]，輸入序列被看作是由序列間隙隔開的多個原子事件。每一個原子事件都可以通過一個簡短的正則表達(dá)式來表示，于是問題就簡化為簡單正則表達(dá)式的學(xué)習(xí)問題。在XML DTD 推斷中[17]，通常XML文件會使用簡單的DTD來描述文件主題內(nèi)容，利用DTD就可以對XML文件信息進(jìn)行提取。然而，考慮到方法的魯棒性和結(jié)果的準(zhǔn)確性，通常需要構(gòu)建更加復(fù)雜的正則表達(dá)式來獲得更有效的信息抽取。

在信息抽取領(lǐng)域，傳統(tǒng)正則學(xué)習(xí)的方法大多著眼于在相對小的字符表上進(jìn)行正則表達(dá)式的學(xué)習(xí)[18]。常見的情況是在詞性標(biāo)注[19]、形態(tài)分析[20]、詞典匹配[21]等文本處理過程之后產(chǎn)生的標(biāo)注詞上進(jìn)行正則表達(dá)式的學(xué)習(xí)，字符表的大小就由以上分析步驟產(chǎn)生的標(biāo)注結(jié)果所決定。另外，之前的幾乎所有工作都將問題限制在一個特定的正則類型中[22]，禁用或限制了某些正則符號和操作的使用。

2 問題描述

對于一個信息抽取任務(wù)，需要獲取實體ε，令R0表示初始輸入的正則表達(dá)式，M(R0,D)表示將R0作用于文本D上所得到的結(jié)果。令：

Mp(R0,D)= {x∈Mp(R0,D) :x是實體ε的實例}

(1)

Mn(R0,D)= {x∈Mn(R0,D) :x不是實體ε的實例}

(2)

分別表示R0的正例和反例的匹配結(jié)果。任務(wù)目標(biāo)就是輸出一個比初始輸入的R0效果更好的正則表達(dá)式。

對于一個候選正則R，及其所應(yīng)用的目標(biāo)文檔D，如果想要判斷R是否比R0有更好的效果，那么就必須對R所匹配的結(jié)果進(jìn)行正負(fù)分類。如果R所匹配的結(jié)果是所有已有結(jié)果的子集，那么就能夠進(jìn)行判斷，因此有如下假定：

假定1 對于字符集Σ上的正則表達(dá)式R0，任何其他的正則表達(dá)式R是一個更優(yōu)候選者當(dāng)且僅當(dāng)M(R,D)?M(R0,D)。

在此假定的基礎(chǔ)上，仍然會得到近乎無限多的候選正則表達(dá)式，為了進(jìn)一步通過學(xué)習(xí)得到一個最優(yōu)正則式，需要一個在不同正則表達(dá)式之間進(jìn)行轉(zhuǎn)換的方法，以及評價一個正則表達(dá)式抽取信息效果的目標(biāo)函數(shù)。下面給出兩者的定義：

定義1 令R表示字符集Σ上所有的正則表達(dá)式的集合，正則表達(dá)式的轉(zhuǎn)換就是一個函數(shù)F:R→2R,?R0∈F(R),L(R0)?L(R)。L(R)表示R所匹配的結(jié)果。

舉例來說，對于正則表達(dá)式(d+-)+d+來說，可以將第二個數(shù)量符號+替換為一個特定的范圍，例如{1，2}或{3，4}，于是就得到了新的表達(dá)式(d+-){1，2}d+ ，(d+-){3，4}d+。將數(shù)量符號+替換為一個具體的范圍就是正則表達(dá)式轉(zhuǎn)換的一個特例，后面會進(jìn)一步說明，現(xiàn)階段可以將正則的轉(zhuǎn)換看作是能夠產(chǎn)生一系列候選正則集合的函數(shù)。下面給出本文學(xué)習(xí)問題的搜索空間的定義：

定義2 給定一個輸入正則表達(dá)式R0和一系列的轉(zhuǎn)換T，學(xué)習(xí)問題的搜索空間為T(R0)，即將轉(zhuǎn)換T重復(fù)作用在R0上所得到的所有正則表達(dá)式的集合。

選擇使用信息檢索領(lǐng)域的常用指標(biāo)F1-Measure來比較檢索空間中不同正則表達(dá)式抽取信息的效果，使用之前提到的Mp(R,D)和Mn(R,D)分別定義一下指標(biāo)：

(3)

(4)

(5)

最終的正則表達(dá)式學(xué)習(xí)任務(wù)就可以由如下最優(yōu)化問題來定義：

定義3 對于給定的輸入正則表達(dá)式R0，文檔集合D，正反例樣本集合Mp(R,D)和Mn(R,D)以及一系列正則轉(zhuǎn)換T，輸出一個最優(yōu)正則表達(dá)式 ：

Rf=argmaxR∈T(R0)F(R,D)

(6)

3 正則表達(dá)式轉(zhuǎn)換

3.1 現(xiàn)代正則引擎

現(xiàn)代正則引擎主要可以分為基本不同的兩大類[18]：一種是DFA(確定型有窮自動機(jī))，另一種是NFA(不確定型有窮自動機(jī))。使用DFA的工具主要有egrep、awk、lex和flex。而使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNUEmacs、ed、sec、vi、grep的多數(shù)版本，甚至還有某些版本的egrep和awk。也有一些系統(tǒng)采用了混合引擎，它們會根據(jù)任務(wù)的不同選擇合適的引擎，甚至對同一表達(dá)式中的不同部分采用不同的引擎，以求得功能與速度之間的平衡。NFA和DFA都發(fā)展了很多年了，產(chǎn)生了許多不必要的變體，以致現(xiàn)在的情況比較復(fù)雜。POSIX標(biāo)準(zhǔn)的出臺，就是為了規(guī)范這種現(xiàn)象，POSIX標(biāo)準(zhǔn)清楚地規(guī)定了引擎中應(yīng)該支持的元字符和特性。

3.2 正則表達(dá)式轉(zhuǎn)換定義

下面介紹如何利用現(xiàn)代正則引擎的句法規(guī)則實現(xiàn)正則表達(dá)式的轉(zhuǎn)換，首先考慮這樣一個信息抽取任務(wù)：從一段文本中找出所有的軟件名稱，一個簡單的模式是R= ([A-Z]w*s*)+[Vv]?(d+.?)+，即為以一個或多個大些字母開頭的單詞，后面跟一個數(shù)字版本號。將R應(yīng)用于實際數(shù)據(jù)中會發(fā)現(xiàn)，一方面R確實能夠提取出正確的結(jié)果，如Office2010,Python2.7,AdobeGoLive5,DeelexInstallerv1.0，另一方面，一些非軟件名稱的結(jié)果也會被提取到，例如Building17,Chapter3.2,ENGLISH202。針對以上出現(xiàn)的非軟件名稱結(jié)果，大體可以從兩個角度來改進(jìn)：

1) 對于像ENGLISH202 這樣的全大寫單詞的課程代碼，可以將R的前半部分單詞的表達(dá)式改為R1= ([A-Z][a-z]*s*)+，即變?yōu)橐砸粋€大寫字母開頭的單詞，這樣就能夠過濾掉之前匹配到的錯誤結(jié)果。

2) 另一個改進(jìn)的方法是利用現(xiàn)代正則引擎中的前向否定符”?!”來顯式地去除掉Building,Chapter,ENGLISH之類的單詞，前向否定就是除了正常的搜索匹配之外繼續(xù)查找，檢查是否出現(xiàn)某些特定內(nèi)容以達(dá)到在正常匹配到內(nèi)容的基礎(chǔ)上，過濾掉某種不想要的內(nèi)容。舉例來說：(?!Ra)Rb返回的是匹配Rb并且不匹配Ra的內(nèi)容?；氐缴厦娴睦右粋€改進(jìn)的方法是將前半部分表達(dá)式改為 (?!Building|Chapter|ENGLISH)[A-Z]w*s*。

以上兩個角度給出了正則表達(dá)式轉(zhuǎn)換的基本原則，通過抽取出一個正則表達(dá)式的一部分并對其進(jìn)行一定的修改以獲得原正則匹配結(jié)果的真子集。這樣的修改分為析取分離與合并交叉兩類。析取分離主要作用在由一系列析取項組成的子表達(dá)式上，通過分離掉一個或多個析取項從而進(jìn)行正則的轉(zhuǎn)換。合并交叉則是將某一限定的子表達(dá)式與其他表達(dá)式進(jìn)行合并，從而得到轉(zhuǎn)換后的表達(dá)式。具體定義如下：

定義4 令R是屬于RΣ中的一個正則表達(dá)式，且有R=Raλ(X)Rb,λ(X)表示正則集合X={R1,R2,…,Rn}上的析取R1|R2|…|Rn，對于某一Y?X，Y作用于R的析取分離轉(zhuǎn)換后的正則為DD(R,X,Y)=Raλ(Y)Rb。

定義5 令R是屬于RΣ中的一個正則表達(dá)式，且有R=RaXRb,對于某一RΣ中的Y，合并交叉轉(zhuǎn)換后的正則為II(R,X,Y)=Ra(X∩Y)Rb。

3.3 正則表達(dá)式轉(zhuǎn)換實現(xiàn)

下面介紹具體如何運(yùn)用不同的句法規(guī)則來實現(xiàn)析取分離和合并交叉的正則表達(dá)式轉(zhuǎn)換，包含以下部分：

1) 字符類限制約束

字符類通常表示一系列字符析取結(jié)果的縮寫，例如元字符d表示(0|1|…|9)，w表示(a|…|z|A|…|Z|0|1…|9|_)。字符類可以用層級結(jié)構(gòu)來表示，其中每一層的節(jié)點所包含的字符范圍都比他的父親節(jié)點更少。在正則中對某一字符類用其后代節(jié)點對其代替就是析取分離轉(zhuǎn)換的一種實現(xiàn)形式。

2) 數(shù)量符約束

數(shù)量符用來定義一段重復(fù)序列出現(xiàn)的次數(shù)范圍，例如x{a,b}表示的是序列x出現(xiàn)至少a次，至多b次。由于數(shù)量符也可以被看成是其范圍中每一項的析取，如a{1,3}相當(dāng)于a|aa|aaa，所以如定義4所描述，將某一正則表達(dá)式R{m,n}替換為R{m′,n′}(m≤m′≤n′≤n)也是一種析取分離轉(zhuǎn)換的形式。需要注意的是，在進(jìn)行這樣的析取分離轉(zhuǎn)換之前，需要對a+和a*這樣的通配符限制在一個實現(xiàn)設(shè)置好的范圍max中，轉(zhuǎn)變?yōu)閍{1,max}和a{0,max}。

3) 否定詞典

對于一個給定的正則表達(dá)式，交叉合并轉(zhuǎn)換可以作用在其每一個有效子表達(dá)式上，對于一個正則表達(dá)式R=RaXRb和它的子表達(dá)式X，交叉合并轉(zhuǎn)換需要另一個表達(dá)式Y(jié)來得到轉(zhuǎn)換后的表達(dá)式Ra(X∩Y)Rb。由于在轉(zhuǎn)換后所得到的表達(dá)式會比原來的表達(dá)式有更好的效果，那么可以通過構(gòu)建所有R的反例匹配，找出其中與X所對應(yīng)的匹配字串，然后通過啟發(fā)式規(guī)則找出其中的一部分構(gòu)成否定詞典Y′。于是利用前向否定符構(gòu)造的正則表達(dá)式Ra(?!Y′)XRb就是利用交叉合并Ra(X∩Y′)Rb后的結(jié)果。

4) 否定詞典的啟發(fā)式構(gòu)造策略

交叉合并轉(zhuǎn)換過程需要建立在否定詞典合理構(gòu)造的基礎(chǔ)上，S(X)表示正則表達(dá)式R的反例匹配中對應(yīng)子表達(dá)式X的所有字符串集合，理論上說，所有S(X)的子集都有可能構(gòu)成一個否定詞典，這樣就會有指數(shù)級數(shù)量的轉(zhuǎn)換可能。為了減少轉(zhuǎn)換的數(shù)量，使用一種貪心的啟發(fā)式策略，對于每一個元素，如果能夠單獨提高F值，那么就將其加入否定詞典。

4 基于正則表達(dá)式學(xué)習(xí)的信息抽取算法

4.1 算法流程

算法1描述了對于定義3的正則表達(dá)式學(xué)習(xí)問題的算法流程?？傮w來說，該算法是一個不斷迭代的過程，通過對初始輸入的正則表達(dá)式進(jìn)行不同形式的轉(zhuǎn)換，在每一輪迭代過程中，得到一組候選正則表達(dá)式的集合，并從中貪心地選擇在訓(xùn)練集上具有最高F值的正則表達(dá)式R。為了避免過擬合的情況，當(dāng)出現(xiàn)以下兩種情況中的任一種時，算法就會終止。(1) 當(dāng)R在訓(xùn)練集上的效果沒有提升；(2) 當(dāng)R在測試集上的效果下降。

算法1 正則表達(dá)式構(gòu)建學(xué)習(xí)算法

Input:

Mtrain: set of labeled matches used as training data

//訓(xùn)練集數(shù)據(jù)

Mtest: set of labeled matches used as test data

//測試集數(shù)據(jù)

R0: user-provided regular expression

//用戶輸入初始正則表達(dá)式

T : set of regular expression transformation

//正則轉(zhuǎn)換集合

Output : one regular expression with highest F-measure

//輸出結(jié)果

Procedure RegexLearning(Mtrain, Mtest, R0,T)

0. Rnew= R0

1. while(true)

2. for each transformation ti∈T

//遍歷正則轉(zhuǎn)換集合

3. Candidatei= Transformation(Rnew, ti)

4. Candidates = ∪iCandidatei

5. R′= argmaxR∈CandidatesF(R,Mtrain)

//選擇最優(yōu)結(jié)果

6. if (F(R′,Mtrain) <= F(Rnew,Mtrain)) return Rnew

7. if (F(R′,Mtest) < F(Rnew,Mtest)) return Rnew

8. Rnew= R′

9. end while

End procedure

4.2 復(fù)雜度分析

下面討論算法1的時間復(fù)雜度，根據(jù)之前提到的兩個算法終止條件，在算法的每一輪迭代中選出的具有最高F值得正則表達(dá)式R′都是嚴(yán)格優(yōu)于Rnew的，由假定1可知，R′所得到的匹配結(jié)果是Rnew匹配結(jié)果的子集，所以R′所匹配的反例結(jié)果嚴(yán)格小于Rnew所匹配的反例結(jié)果，因此，總的迭代次數(shù)至多為|Mn(R0,Mtrain)|。

對于一個正則表達(dá)式R，令ncc(R)和nq(R)分別表示R中字符類和數(shù)量符的個數(shù)，R中子表達(dá)式的個數(shù)至多為|R|2,令MaxQ(R)表示自定義的R中單個數(shù)量符所限定的數(shù)量范圍，F(xiàn)cc表示字符類層級樹中的最大分支數(shù)，令Ri表示在i輪迭代開始時的輸入正則，經(jīng)過正則表達(dá)式轉(zhuǎn)換后的候選正則數(shù)量為：

NumREG(Ri,Mtrain)≤ncc(Ri)×Fcc+nq(Ri)×

MaxQ(Ri)+|Ri|2

令TRE(D)表示將正則表達(dá)式作用于文檔D上的平均時間。對于字符類替換和數(shù)量符限制的析取分離轉(zhuǎn)換時間是與候選正則數(shù)量成正比的，而對于通過構(gòu)造否定詞典的交叉合并轉(zhuǎn)換，由于否定詞典的貪心式啟發(fā)式規(guī)則，所需要的時間也與子表達(dá)式以及反例匹配數(shù)量相關(guān)?？偟臉?gòu)造候選正則表達(dá)式集合的時間為：

TCandidate(Ri,Mtrain)≤c×(ncc(Ri)×Fcc+nq(Ri)×

MaxQ(Ri)+|Ri|2×Mn(Ri,Mtrain)×TRE(Mtrain))

最后，從候選正則表達(dá)式集合中選出最優(yōu)正則表達(dá)式，包括將候選集中的每一個正則作用于訓(xùn)練集以及測試集上的時間：

TPick(Ri,Mtrain,Mtest)=NumREG×(TRE(Mtrain)+

TRE(Mtest))

Ti(Ri,Mtrain,Mtest)=TCandidate(Ri,Mtrain)+

TPick(Ri,Mtrain,Mtest)

Ttotal(Ri,Mtrain,Mtest)=∑Ti(Ri,Mtrain,Mtest)

≤|Mn(R0,Mtrain)|×t0

所以每一輪迭代的總時間為：

Ti(Ri,Mtrain,Mtest)=TCandidate(Ri,Mtrain)+

TPick(Ri,Mtrain,Mtest)

由于每一輪迭代的總時間是單調(diào)遞減的，所以最終算法的時間復(fù)雜度為(t0是第一輪迭代所需要的時間)：

Ttotal(Ri,Mtrain,Mtest)=∑Ti(Ri,Mtrain,Mtest)

≤|Mn(R0,Mtrain)|×t0

5 實驗分析

在本節(jié)中，將通過四種不同的信息抽取任務(wù)來評估本文中的算法在復(fù)雜正則表達(dá)式學(xué)習(xí)問題上的效果，并與常規(guī)的機(jī)器學(xué)習(xí)方法進(jìn)行了比較。實驗中用到了數(shù)據(jù)集有三個，分別為從yahoofinance選取的2000多個上市公司網(wǎng)頁進(jìn)行爬取所得內(nèi)容，以及從密歇根大學(xué)網(wǎng)站[23]上爬取的5000個頁面數(shù)據(jù)和3000個的電子郵件內(nèi)容信息。后兩者均為互聯(lián)網(wǎng)上的公開數(shù)據(jù)。實驗的四個信息抽取任務(wù)分別為電話號碼、課程代碼、超鏈接、公司名稱的信息抽取。實驗結(jié)果通過F值來評估，每個數(shù)據(jù)集被分為10個大小相同的子數(shù)據(jù)集，分別使用10%、30%、70%的數(shù)據(jù)作為訓(xùn)練集，剩下的作為測試集。實驗結(jié)果如圖1-圖4所示。

圖1 電話號碼任務(wù)抽取效果

圖2 課程代碼任務(wù)抽取效果

圖3 超鏈接任務(wù)抽取效果

圖4 公司名稱任務(wù)抽取效果

分析實驗結(jié)果可見：

如果使用10%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，對于公司名稱、課程代碼以及電話號碼三個信息抽取任務(wù)，本文的算法比傳統(tǒng)的條件隨機(jī)場方法F值會有顯著提高。

隨著訓(xùn)練數(shù)據(jù)的增加，兩種方法的抽取效果均有提升，兩者之間的差別也隨之減小。在使用較大的訓(xùn)練集時，本文的方法在公司名稱以及電話號碼兩個信息抽取任務(wù)上效果較好，而傳統(tǒng)機(jī)器學(xué)習(xí)方法則在另外兩個任務(wù)上有更優(yōu)的表現(xiàn)。

以上實驗結(jié)果說明在有限的訓(xùn)練數(shù)據(jù)上，本文的算法比傳統(tǒng)的機(jī)器學(xué)習(xí)算法有一定的提升。通常情況下，由于獲取標(biāo)注數(shù)據(jù)通常需要花費大量的時間，所以如何能夠在有限的訓(xùn)練集上獲得高質(zhì)量的信息抽取效果是非常重要的。也正因為如此，理想中的情況是在一個訓(xùn)練集上訓(xùn)練出的抽取器能夠在其他的數(shù)據(jù)集上也有較好的效果，表1展示了兩種方法在跨數(shù)據(jù)集上的信息抽取效果?？梢钥闯?，在不同規(guī)模的數(shù)據(jù)集上，本文的算法均有較好的效果，相比于同數(shù)據(jù)集上的實驗結(jié)果，傳統(tǒng)的條件隨機(jī)場方法在跨數(shù)據(jù)集上的表現(xiàn)有顯著下降。

表1 跨數(shù)據(jù)集測試(F值)

6 結(jié) 語

在信息抽取領(lǐng)域，基于正則表達(dá)式的實體抽取一直是一種實際應(yīng)用中廣泛使用的有效方法。本文提出了一種基于正則表達(dá)式學(xué)習(xí)的信息抽取方法，在給定輸入初始正則的前提下，通過機(jī)器學(xué)習(xí)的方法找到最優(yōu)結(jié)果。介紹了正則表達(dá)式狀態(tài)轉(zhuǎn)換的概念及其實現(xiàn)方法，并且給出了選取最優(yōu)正則表達(dá)式的算法，通過實驗驗證了該方法在一些特定類型的信息抽取任務(wù)中具有較好的效果。尤其是在較小規(guī)模的訓(xùn)練集以及跨數(shù)據(jù)集上有不錯的表現(xiàn)。本文的方法仍有許多不足之處，例如在某些信息抽取任務(wù)中無法保持較高的準(zhǔn)確率與召回率，可能的原因是在選擇最優(yōu)正則表達(dá)式使用貪心的啟發(fā)式策略，但這也是與時間復(fù)雜度的一個權(quán)衡。

[1] McCallum A,Freitag D,Pereira F C N.Maximum entropy Markov models for information extraction and segmentation[C]//Proceedings of the Seventeenth International Conference on Machine Learning,2000:591-598.

[2] Soderland S.Learning information extraction rules for semi-structured and free text[J].Machine Learning,1999,34(1):233-272.

[3] Klein D,Smarr J,Nguyen H,et al.Named entity recognition with character-level models[C]//Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003.Association for Computational Linguistics,2003:180-183.

[4] Carlson A,Betteridge J,Wang R C,et al.Coupled semi-supervised learning for information extraction[C]//Proceedings of the Third ACM International Conference on Web Search and Data Mining.ACM,2010:101-110.

[5] Wang J,Lochovsky F H.Wrapper induction based on nested pattern discovery:HKUST-CS-27-02[R].Technical Report of Hong Kong University of Science and Technology,2002.

[6] Chiticariu L,Li Y,Reiss F R.Rule-based information extraction is dead! Long live rule-based information extraction systems![C]//Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing,2013:827-832.

[7] Sekine S.On-demand information extraction[C]//Proceedings of the COLING/ACL on Main Conference Poster Sessions.Association for Computational Linguistics,2006:731-738.

[8] Kluegl P,Toepfer M,Beck P D,et al.UIMA Ruta:rapid development of rule-based information extraction applications[J].Natural Language Engineering,2016,22(1):1-40.

[9] Fagin R,Kimelfeld B,Reiss F,et al.Spanners:a formal framework for information extraction[C]//Proceedings of the 32nd Symposium on Principles of Database Systems.ACM,2013:37-48.

[10] 鄭家恒,王興義,李飛.信息抽取模式自動生成方法的研究[J].中文信息學(xué)報,2004,18(1):48-54.

[11] Fagin R,Kimelfeld B,Reiss F,et al.Document spanners:a formal approach to information extraction[J].Journal of the ACM (JACM),2015,62(2):1-51.

[12] 楊博,蔡東風(fēng),楊華.開放式信息抽取研究進(jìn)展[J].中文信息學(xué)報,2014,28(4):1-11,36.

[13] Denis F.Learning regular languages from simple positive examples[J].Machine Learning,2001,44(1):37-66.

[14] Denis F,Lemay A,Terlutte A.Learning regular languages using RFSAs[J].Theoretical Computer Science,2004,313(2):267-294.

[15] Fernau H.Algorithms for learning regular expressions[C]//16th International Conference on Algorithmic Learning Theory.Springer,2005:297-311.

[16] Garofalakis M,Gionis A,Rastogi R,et al.XTRACT:a system for extracting document type descriptors from XML documents[N].ACM SIGMOD Record,2000,29(2):165-176.

[17] Galassi U,Giordana A.Learning regular expressions from noisy sequences[C]//6th International Symposium on Abstraction,Reformulation and Approximation.Springer,2005:92-106.

[18] Bex G J,Neven F,Schwentick T,et al.Inference of concise DTDs from XML data[C]//Proceedings of the 32nd International Conference on Very Large Data Bases.VLDB Endowment,2006:115-126.

[19] Wu T,Pottenger W M.A semi-supervised active learning algorithm for information extraction from textual data:research articles[J].Journal of the American Society for Information Science and Technology,2005,56(3):258-271.

[20] Minkov E,Wang R C,Cohen W W.Extracting personal names from email:applying named entity recognition to informal text[C]//Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing.Association for Computational Linguistics,2005:443-450.

[21] Chen H,Chiang R H L,Storey V C.Business intelligence and analytics:from big data to big impact[J].MIS Quarterly,2012,36(4):1165-1188.

[22] Cohen W,McCallum A.Information extraction from the world wide web[C]//Tutorial Note at the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2003),2003.

[23] Intranet Transactional Search[OL].http://www.eecs.umich.edu/db/transactionalSearch/.

A WEBPAGE INFORMATION EXTRACTION METHOD BASED ON REGEX CONSTRUCTION LEARNING

Zhu Wenyan Zheng Xiaoxiong

(ShanghaiKeyLabofIntelligentInformationProcessing,SchoolofComputerScience,FudanUniversity,Shanghai200433,China)

As one of the main methods in the field of information extraction, the method based on regular expression has been widely used for many years. However, the construction of regular expressions is with high quality and high complexity, it is usually required to spend a lot of manual efforts. Therefore, a method based on regular expression state transition is proposed to learn the construction of complex regular expressions. The method takes in a given initial input RegEx and both positive and negative labeled samples, a collection of candidate RegEx is got after applying two main kind of regular expressions transformation on the input RegEx, based on F value assessment of the candidate RegEx on the information extraction task, the algorithm selects an optimal regular expressions as output by greedy heuristic strategy. The performance of this algorithm is evaluated on multiple datasets. Experiments show that the performance and accuracy of the proposed method outperforms those of the standard machine learning methods. And it still has a good effect on condition of small scale training set and cross domain data set.

RegEx construction State transition Web information extraction

2016-01-22。朱文琰，碩士，主研領(lǐng)域：金融信息處理。鄭肖雄，碩士。

TP3

A

10.3969/j.issn.1000-386x.2017.02.003