自動構建時間基元規則庫的中文時間表達式識別

鄔桐,周雅倩,黃萱菁,吳立德

(復旦大學計算機科學技術學院,上海200433)

1 引言

時間表達式的識別是信息抽取領域的一項基礎性任務,它可以用于事件跟蹤,時間關系推理,時序定位等。比如在主題檢測與跟蹤任務中,可以用時間來定位事件發生的先后順序;在自動問答系統中,可以用來回答和時間相關的問題如“多久,何時”;在機器翻譯任務中,時間順序的定位可以讓譯文更加順暢易讀;甚至在網頁結構分析方面,也在研究如何用時間表達式特征去提高分析正確率。近幾年來,時間表達式的識別和規范化由于在時序方面的重要應用,涉及的語種也從起初包含的英語、漢語和阿拉伯語,擴展到韓語[1]、法語[2]和西班牙語[3]等。

隨著對時間表達式的關注度逐漸提升,陸續出現了許多相關的評測。自從2004年N IST(National Institute of Standards and Technology)的TERN(Time Expression Recognition and Normalization)評測問世之后,ACE 2005(Automatic Content Extraction)和Sem Eval 2007(Semantic Evaluations)評測也相繼將其納入自己的任務中,時間表達式評測的標準也日益成熟。

TERN評測包含兩個任務,其中 TER(Time Expression Recognition)主要完成語料中時間表達式的邊界識別任務,而TEN(Time Exp ression Normalization)則完成時間表達式的規范化工作,即為每個識別出邊界的時間表達式按照Timex2①Timex2標注方案,TIDES 2005 Standard for the Annotation of TemporalExpressions.規范標注屬性值。本文研究第一個任務,即時間表達式的邊界識別。

時間表達式識別中兩種最為常用的方法是基于人工構建規則的方法和基于機器學習的序列標注方法。

基于人工規則的方法方面,李文婕等人在文章[4]中做了比較具代表性的嘗試,文章提出建立一些語法規則和補充限定規則,通過規則匹配方式識別時間表達式。直到最近,仍有文獻[7]使用基于規則的方法,通過對點時間、段時間、集合時間等不同類型的時間短語平行識別,完成時間表達式的邊界識別任務?；谝巹t的方法使用起來非常簡單,而且規則易于理解,便于擴展和更新。但是最大的缺點就是人工工作量較大,早期的方法完全使用人工方式來構建規則,后期則先通過一些機器標注方法對文本進行預處理,然后對處理后的標注結果構建規則,雖然在一定程度上減少了人力,但仍不能適應實際應用要求。

基于機器學習的序列標注方法方面,D.Ahn[5]和K.Hacioglu[6]分別進行了嘗試。他們首先將語料進行預處理,比如分詞、詞性標注、前后詞提取、首字母提取等,接著有選擇地抽取特征,建立特征向量,通過預先選定的分類器(CRF[5]或者SVM[6])訓練模型。然后對測試語料使用已經訓練好的模型進行時間表達式的標注。實驗表明,這種方法在中文時間表達式識別方面有著不錯的表現。近年來,也有一些更新穎的方法出現,比如哈爾濱工業大學的賀瑞芳等人[8],通過依存句法分析的標注結果結合預先定義的觸發詞表對中文時間表達式進行識別,然后運用TBL模型修正建立在依存句法分析上的規則集合。采用序列標注方法最大的特點就是可以充分利用已標注上下文信息,使得識別召回率較高。但是這類系統過分依賴標注語料的質量,又無法充分利用時間表達式格式相對穩定的特點,僅僅利用一些局部特征信息構建規則。因此,序列標注方法較少被使用于時間表達式識別任務。

綜上所述,基于規則的方法需要人工構建大量規則,代價非常高,且擴展性和領域適應性差;而采用序列標注方法則無法解決訓練語料數據稀疏和詞序依賴這兩個缺點,很難達到較高的識別性能。

本文基于訓練標注語料自動學習規則,并通過錯誤驅動思想對規則庫進行剪枝,既有效地利用了上下文信息,又達到了較高的自動化程度。在ACE07中文語料上的實驗結果顯著超過了現有水平,F-score達到89.9%。

本文結構安排如下：第2節,主要介紹中文時間表達式識別系統的詳細設計結構以及我們所提出的“時間基元”的概念和自動學習結合錯誤驅動剪枝的規則庫構建算法,即auto-pattern算法。第3節,介紹本文所設計的幾個實驗,相關的評測方法和評測結果,并進行原因分析。最后,全文總結并提出未來工作的設想。

2 時間表達式識別的基本原理和方法

2.1 中文時間表達式識別系統結構

本文所設計的中文時間表達式識別系統(詳見圖1)主要包含五個步驟：

1)對訓練語料進行預處理,抽取所有已標注的時間表達式。

2)將這些從標注語料中抽取的表達式進行分詞,構成“時間基元”集合,達到降低粒度以便構建細粒度的正則規則②正則規則：正則表達式形式的規則。全文亦使用“正則規則”進行表述。的目的。

3)通過預定義的規則轉換機制,自動將“時間基元”轉化為與其對應的正則規則,形成自動學習規則庫。

4)運用錯誤驅動思想,根據規則評價函數對規則剪枝,消除規則庫中的“噪聲”,生成最終規則庫。

5)最終規則庫中的規則通過正則表達式匹配,識別測試語料中的時間表達式,將識別出的相鄰表達式進行合并,完成時間表達式的識別任務。

其中1)～4)構成規則學習模塊,5)單獨構成規則應用模塊。

學習模塊中,基于“時間基元”構建規則的設計降低了規則的粒度,可以識別更多細粒度時間表達式,提高了識別系統的召回率,因此,就需要在應用模塊中將相鄰的被系統所識別出的表達式進行合并,構成連續完整的時間表達式。這也符合時間表達式由基本時間單元(“時間基元”)組成的感性認識。

圖1 中文時間表達式識別系統結構圖

2.2 “時間基元”

“時間基元”,即基本時間單元,是構成時間表達式的最小組成單元。比如“2008年5月12日下午2點48分”這個時間表達式中,就包含2008年、5月、12日、下午、2點、48分六個時間基元。

以往時間表達式識別方法,大都構建完整的時間表達式識別規則,然后對整塊表達式進行識別,這樣構建的規則往往會有粒度過粗的缺點,無法識別出很細的時間表達式,而且如果測試語料中,組成表達式的時間單元按照現有形式之外的方式進行組合,那么規則將匹配失效,從而導致系統召回率較低。

而實際上,通過對大量時間表達式結構的深入分析,我們發現,時間表達式往往由獨立代表特定時間概念的基本單元(“時間基元”)所組成,也就是說時間基元與時間基元之間的搭配相對松散,沒有很強的先后依賴關系。

正是因為時間表達式這種弱依賴的特點,我們選擇了對時間基元建立正則規則,然后將識別出的表達式進行相鄰項合并,最終構成完整結構的時間表達式。

2.3 人工構建啟發式規則庫

中文時間表達式雖然不如英文那樣具有良好的書寫規范和很固定的格式,但是也是有一定規律性可循。過去基于規則的研究方法都是利用這個特點,構建了大量的人工規則進而完成識別任務的。然而由于每篇文章構建規則的方法不同,最終的規則庫也不發布,因此很難重復他人的研究工作進行對比實驗,我們只好根據自己的研究經驗構建一部分啟發式規則,作為人工啟發式規則庫。

根據我們對TERN任務的歸納,中文時間表達式大體分為七種類型(見表 1)。針對每個不同類型,我們各自構建了一批人工規則,作為啟發式規則庫。這些人工規則,能夠通過正則表達式匹配方式①本文全部使用Standard Java Developm ent K it 6.0正則表達式引擎,通過正則匹配模式,完成表達式識別。識別出許多中文時間表達式。

表1 人工規則示例

最終,我們整合所有七種類型的人工構建的啟發式規則,得到人工啟發式規則庫

2.4 基于訓練語料自動學習規則

高正確率的人工規則并不能達到很高的綜合性能(F-score),主要是因為人工規則覆蓋能力低,導致召回率較低。而如果充分利用訓練語料覆蓋廣泛的特點,就能非常有效的提高召回率。在這一部分,我們將自動抽取訓練語料中的“時間基元”,并通過預定義的轉化規則將其轉化成目標正則規則,全自動完成規則庫的構建,其中不包含人工過程,使系統有較好的可移植性,將來可以施加較少的變動去適應其他領域的應用。

1)標注語料預處理

對XM L格式的標注語料進行解析,僅保留Timex2節點。接著,對節點進行清洗,得到訓練語料中全部中文時間表達式的字符串集合

該集合中的每一個元素就是一個已標注的時間表達式E Ai。

2)生成“時間基元”集合

就需要將每一個完整的已標注時間表達式按照基本時間單元的概念分解為若干時間基元,即將全部時間基元去冗余整合,得到“時間基元”集合

這里需要指出的是,雖然本文提出了“時間基元”的概念,并在其基礎上自動構建正則規則完成時間表達式的識別,然而“時間基元”尚未給出明確的規范,因此按照怎樣的標準將已標注時間表達式分解成若干對應的時間基元,可以有很多選擇。

為了使整套系統包含最少的人工干預,達到較高的自動化程度,我們選擇使用比較成熟的自動中文分詞系統①本文所使用的中文分詞系統是復旦大學媒體計算與Web智能實驗室基于M UC-6語料所設計并構建的中文分詞系統。對已標注時間表達式進行分詞,將分詞后的細粒度短語作為“時間基元”。這樣既達到了分解較長的完整時間表達式,降低目標短語粒度的目的,同時又較好的解決了系統自動化的需求。

3)正則規則轉化

使用預先設定的三個轉換規則RT1,RT2,RT3,將BA中所有的時間基元轉化為對應的正則規則。RT負責將“時間基元”轉化為正則規則,每個RTi包括識別和轉化兩個部分。

識別部分RT_Ri：用于對時間基元BAi中特定短語進行識別。

轉化部分RT_Ti：對表達式中被第一部分識別的短語進行轉化,生成最終的正則規則PAi。

預設的三個轉換規則,如下：

比如,我們將第一條轉換規則作用于時間基元：BAi=“5年”。按照RT1的識別規則RT_R1可以將BAi中的“5”識別出來,進而再通過 RT_T1將 5轉化為“d+”,這樣轉化后的 PAi=“d+年”。

下表是RTi的應用示例。

表2 正則規則轉化示例

就這樣,每個時間基元短語依次通過全部三個RT的識別與轉化規則處理。最終,生成自動學習階段的正則規則集合：

4)識別結果相鄰項合并

在時間表達式的識別階段,我們使用每條基于“時間基元”構建的正則規則進行時間表達式的識別,再將位置相鄰的被識別表達式進行相鄰項合并,就會得到最終識別結果。

“時間基元”的特性就是基于每個相對獨立的基本時間單元進行規則構建,這樣割裂了時間表達式的整體性。然而,將相對獨立的識別結果進行合并,就會產生出許多新的搭配與組合,即生成許多新的完整的時間組合,擴大了時間表達式的識別范圍。

2.5 基于錯誤驅動思想的規則庫剪枝

基于訓練語料自動獲取與轉化所學習到的正則規則已經可以很好地完成時間表達式的識別任務。然而,與人工規則相比,自動學習的規則在正確率方面有著明顯的降低,雖然召回率有所提升,但是整體性能F-score提高并不夠明顯。最主要原因就是學習過程中,由時間表達式分詞、“時間基元”構建、正則規則轉化等引入了大量噪聲,造成了正確率的大幅度降低。

比如,訓練語料中的一個樣本BAj=“10.1”(中國國慶節),作為時間表達式被提供給自動學習模塊,跟著,RT_R1=“d+”可以將10和1識別,進而通過RT_T1=“d+”將 BAj轉化為PAj=“d+.d+”。那么在測試階段,所有小數形式的表達式,如“3.14”,“10.00”,“25.25” ……都會被誤識 ,產生這種噪聲的原因就是PAj質量不高①如果規則識別出的正確表達式較少,錯誤表達式較多,該規則是質量不高的。該問題可以通過簡單的限制條件加以解決,然而為了在自動學習過程中不引入任何人工干預,我們完整保留自動生成的所有規則。。對此,我們需要對規則庫進行剪枝。

我們通過引入規則評價函數Score(PAi)來對規則庫中的規則進行打分,修剪那些導致系統性能降低的規則而留下對系統識別性能貢獻大的規則,auto-pattern算法正是在這種錯誤驅動思想指導下,設計了最后的規則庫剪枝部分。

下圖即為基于錯誤驅動思想進行規則庫剪枝的流程圖。

圖2 基于錯誤驅動思想的規則庫剪枝

基于錯誤驅動思想對規則庫剪枝的具體算法如下：

輸入：input={PAi}

輸出：output={FPAi}

評價函數：Score(PAi)

評價閾值：λ

1)首先,順次執行識別過程,input中的每個規則PAi,到訓練語料中進行正則匹配,識別語料中的中文時間表達式,所有被識別出的表達式生成針對該規則的系統識別結果,記為Sys_PAi={,,……,},|Sys_PAi|為其計數。

2)接著,將系統識別結果與標注語料結果進行比較,即將Sys_PAi和訓練語料的標注結果進行配對,如果某個對應著標注結果中的一個時間表達式,那么該結果就是一個被規則PAi正確識別的表達式,加入到 True_PAi中;反之,該表達式就是一個對應于規則 PAi的誤識表達式,加入到False_PAi中。這兩個關鍵參數|True_PAi|和|Fa lse_PAi|構成評價函數的重要組成部分。

3)然后,根據預定義的規則評價函數Score(PAi)對當前規則PAi進行打分。

|True_PAi|為PAi正確識別表達式的個數,|False_PAi|為其誤識表達式個數。

這樣,以每條規則的Score值為參考標準,效果比較好的規則分數就會比較高,反之亦然。

4)最終,得分Score(PAi)超過閾值λ的規則PAi,保留在原規則庫中,記為 FPAi;低于閾值λ的,對該規則進行剪枝,完成對規則庫的修正。

迭代每條規則,對規則庫剪枝,得到FPA={FPAi},i=1,2,…,n就是auto-pattern算法最終生成的正則規則庫。

在整個過程中,閾值λ的選擇起著尤為重要的作用,如果選擇過高,則有效規則被剪枝的可能性就越高;如果選擇過低,則不會對目標規則庫有多大的提升作用,也就并沒達到基于錯誤驅動思想的反饋式修正目標規則庫的目的。

3 實驗

3.1 ACE07評測語料以及TERN評測方法

目前,對于時間表達式的處理領域,最廣泛采用的標準就是 Timex2標注規范。ACE07中TERN任務就是采用Timex2作為其評價標準。

ACE07中文語料的基本統計數據如下。

表3 ACE07中文語料統計信息

ACE評測有著悠久的歷史,在命名實體領域更是最為權威的評測之一,每年都有來自全球的許多單位參評,參評語種包括英語、阿拉伯語、漢語等多種語言。TERN任務是ACE07評測中一個很重要的評測項目,也有多家單位參與了TERN任務的評測。

該任務采用自然語言處理領域中經典的“PRF評價標準”,具體評價方法可見ACE07 Evaluation Plan①The ACE 2007 Evaluation Plan：Evaluation of the Detection and Recognition of ACE Entities,Values,Temporal Expressions,Relations,and Events.。

3.2 基于人工啟發式規則的評測結果

對于人工啟發式規則的評測,我們找了不同的人員按照Timex2七個類別構建了初始正則規則,正則表達式外延相同的規則只保留一個,我們得到26個規則,構成人工規則庫。

使用這些規則,到測試語料中識別時間表達式,并將識別結果與已標注時間表達式進行對比,再使用經典“PRF評價標準”進行性能檢驗,評測結果見表4。

表4 基于人工啟發式規則的評測結果

從結果分析,正確率很高而召回率卻非常低,正確率高是因為人工構建的規則經過精挑細選,完全符合時間表達式的基本形式,因此在識別時會得到很高的正確率,而由于人工構建的限制,不可能靠人力來找到所有覆蓋中文時間表達式的正則規則,進而構建出完備的規則庫,因此召回率很低。

3.3 基于時間基元自動學習規則的評測結果

這一部分,我們通過auto-pattern算法的第一部分來自動學習規則?；贏CE07中文訓練語料,從中我們抽得2 214個已標注時間表達式,進而得到881條基于“時間基元”轉化而來的正則規則。

使用這些細粒度規則,識別ACE07測試語料中基于“時間基元”正則規則的中文時間短語,再根據算法說明,將相鄰的時間短語進行合并,構成完整的時間表達式。最后,將這些合并后的表達式與已標注結果進行對比,得到測試結果見表5。

表5 基于自動學習規則的評測結果

實驗結果顯示,與人工啟發式規則相比,基于“時間基元”自動學習的規則的確在召回率方面得到較大幅度的提升,升幅達89.9%,可是卻也損失了相當一部分正確率,其降幅達到17.8%。然而綜合性能F-score 31.2%的提高,表明自動學習方法得到的規則在整體識別性能方面的確有較好的表現。

“時間基元”規則,經過獨立匹配和相鄰項合并,產生很多訓練語料外的新搭配,因此系統召回率有明顯提高。然而,其正確率的下降,也反映出基于“時間基元”所學習的規則產生了大量細粒度的非時間表達式規則,使得系統識別出許多錯誤的結果。錯誤驅動剪枝部分,將會有效地修剪掉那些錯誤的規則,留下高正確率的有效規則。

與人工構建規則方法相比,自動學習方法不僅未加入任何人工過程,節約了人力消耗,而且有效地提高了召回率,識別正確率卻由于訓練語料噪聲的引入而有所降低。但總體來看,系統整體性能F-score確有所提高。

3.4 基于錯誤驅動思想剪枝規則的評測結果

這一部分,按照auto-pattern算法的設計,通過錯誤驅動思想對規則庫進行剪枝,并考察識別整體性能F-score與剪枝閾值λ之間的關系,見圖3。

圖3 調整閾值的評測結果

從λ=0開始,隨著閾值的不斷升高,被系統剪枝的規則也逐漸增多,規則庫識別覆蓋范圍也會隨之縮減,因此召回率慢慢下降,同時由于噪聲的不斷削減,識別正確率自然上升。直到λ=0.6時,召回率的升高和正確率的下降使 F-score達到峰值89.9%。隨著λ的繼續升高,越來越多的規則被剪枝,識別覆蓋能力緩慢降低,但規則庫中的噪聲卻越來越少,最終,留下的少量極高精度的規則使得識別正確率達到100%。

同時,閾值λ∈[0.15,0.95]的區間內,系統整體識別性能F-score基本都可以達到85%以上;更進一步,λ∈[0.30,0.70]的區間內,正確率和召回率也都維持在一個相對穩定的范圍里。這說明基于錯誤驅動思想的規則剪枝部分,對參數的敏感性比較低,參數閾值λ在一個很大的區間范圍內,都會使系統的整體識別性能保持在一個相對較高的程度。

3.5 與其他方法比較

無論是基于規則的方法還是基于序列標注的方法,幾乎所有相關文章所使用的中文時間表達式識別系統都包含大量的人工過程,因此沒辦法按照原文的內容重現其實驗結果。而且大部分中文領域的文章都使用自行標注的語料進行測試,無法進行對比實驗。

在中文公開語料TERN任務評測領域里,將本文的結果與近年來效果最好的系統[9]的評測結果進行對比,具體數據對比如表6、圖4所示。

人工啟發式規則方法(AP-H)的正確率最高,達到92.3%,但是由于人工構建的限制,該規則庫僅覆蓋了很小一部分時間表達式,因此召回率很低;基于“時間基元”自動學習規則方法(AP-AN)的召回率最高,達到91.0%,而細粒度的“時間基元”規則包含了一些低質量規則,因此正確率不高。

表6 與其他方法進行比較

圖4 與其他方法進行比較

最終,結合了錯誤驅動思想進行規則剪枝的高精度規則庫,在剪枝閾值λ=0.6時,使 auto-pattern系統的正確率和召回率達到了比較出色的平衡,F-score為89.9%,比其他方法中性能最佳的GDE方法提高了15.3%,這樣的性能提升是非常顯著的。

4 結論與展望

時間表達式的識別是時間信息時序化過程的前提,也是很多自然語言處理領域問題的基礎。本文提出一種自動學習結合錯誤驅動剪枝的規則庫構建算法,亦即auto-pattern算法。本文將機器學習方法應用到規則自動學習與規則庫剪枝過程中來,在識別正確率和召回率兩方面均獲得了較為平衡的優化,進而使中文時間表達式識別的整體性能有較大幅度提升。這種方法不僅解決了基于規則方法的人工消耗問題,同時解決了傳統序列標注方法詞序依賴和數據稀疏的問題。

根據對時間表達式特性的分析,我們對“時間基元”進行規則構建,并在識別階段進行相鄰項合并,這樣的設計能夠識別大量訓練語料外的時間短語組合,又解決了長規則匹配失效的問題,提高系統召回率。同時,在錯誤驅動剪枝規則庫階段,對規則庫中的大量規則進行修剪,有效的處理了規則學習時所帶來的噪聲,提高了系統正確率,更有針對性地提高了中文時間表達式識別的整體性能。

實驗表明,這種自動學習結合錯誤驅動剪枝構建規則庫算法是行之有效的,而且效果非常理想。同時還要強調本文提出的auto-pattern不僅僅是一個算法,同時是一個自動學習框架,可以很方便的擴展到其他領域。也就是說,auto-pattern作為一個有監督學習框架,只要有相應領域的語料和少量領域知識,該框架就可以構建出基于該領域的一套規則,進而完成特定目標內容的識別工作。

未來,我們將進一步研究如何提高auto-pattern算法的泛化能力,使之適應更廣泛的應用領域;同時,還將研究如何將算法深化,進一步解決中文時間表達式的規范化問題。

[1] Seok Bae Jang,Jennifer Baldw in.Inderjeet M ani Automatic TIMEX2 Tagging o f Korean New s[J].ACM T ransactions on Asian Language Information processing(TALIP),2004,3(1)：51-65.

[2] N ikolai Vazov A System for Extraction of Temporal Expressions from French Texts based on Syntactic and Semantic Constraints[C]//Proceedings of the w orkshop on Temporal and spatial in formation processing,2001,Volume 13：A rticle No.14：1-8.

[3] Estela Saquete,Patricio Martinez-barco.Rafael M ufioz Recognizing and Tagging Temporal Exp ressions in Spanish[C]//Workshop on Annotation Standards for Temporal In formation in Natural Language(LREC),2002：44-51.

[4] MingliWu,Wen jie Li,Qin Lu,Bao li Li.A Chinese Temporal Parser for Extracting and Normalizing Temporal Information[C]//International Joint Conference on Natural Language Processing(IJCNLP),2005,Vo lume 3651：694-706.

[5] David Ahn,Sisay Fissaha Adafre,Maarten De Rijke Tow ards Task-Based Temporal Ex traction and Recognition[C]//Proceedings DagstuhlWorkshop on Annotating,Ex tracting,and Reasoning about Time and E-vents,2005.

[6] Kadri H acioglu,Ying Chen.Benjam in Douglas Automatic Time Expression Labeling for English and Chinese Text[C]//Computational Linguistics and Intelligent Text Processing(CICLing),2005,Volume3406：548-559.

[7] 林靜,曹德芳,苑春法.中文時間信息的TIM EX2自動標注[J].清華大學學報(自然科學版),2008,48(1)：117-120.

[8] 賀瑞芳,秦兵,劉挺,潘越群,李生.基于依存分析和錯誤驅動的中文時間表達式識別[J].中文信息學報,2007,21(5)：36-40.

[9] 賀瑞芳,秦兵,潘越群,劉挺,李生.基于啟發式錯誤驅動學習的中文時間表達式識別[J].高技術通訊,2008,18(12)：1258-1262.