Chapter 30  Information extraction

 

Abstract

 

Information extraction 是指在文件中自動辨認欲獲知的實體、關係或事件。

資訊擷取的目標是把文件裡包含的資訊進行結構化處理，變成像表格一樣有組織的形式。輸入原始文件到擷取系統，輸出的是固定格式的資訊。資訊從各式各樣的文件檔案中被擷取出來，以統一的形式呈現。這就是資訊擷取的主要任務。資訊以統一形式呈現的好處是方便檢查和比較，例如比較不同的招標和商品資訊；還有一個好處是能對資料作自動化處理。例如用資料探勘方法發現和解釋資料模型。

資訊擷取技術並不試圖全面理解整篇文件，只是對文件中包含相關資訊的部分進行分析。至於哪些資訊是相關的，那將由系統設計時定下的領域範圍而定。

資訊擷取技術對於從大量的文件中擷取需要的資訊來說是非常有用的。在網路上，同一主題的資訊通常分散存放在不同網站上，表現的形式也各不相同。若能將這些資訊收集在一起，用結構化形式儲存，將會非常有用。在網路日益發達的今天，從大量線上文章中擷取特定資訊的技術變得十分重要。

由於網頁內容主要是文件，所以，資訊擷取技術對於那些把網際網路當成是知識來源的人來說是相當重要的。資訊擷取系統可以看作是把資訊從不同文字檔案中轉換成資料庫記錄的系統。因此，成功的資訊擷系統將把全球資訊網變成一個龐大的資料庫！

這一章將從名稱的辨認和分類，及事件擷取來認識IE。我把從閱讀各小節學到的知識和心得分述如下：

 

30.1 Name Identification and Classification

 

30.1.1 Building a name tagger

 

分類的基本概念：運用大量的pattern來捕捉和分類名稱的子集，pattern中的元素代表特殊的tokens或特徵。 ex.capitalized-word + ‘corp.’表示大寫字母的公司名稱。想要發展一個高品質的分類器需要有系統的方法。典型的方法就是以人工方式標註大量的語料庫，然後將分類器的輸出和人工註解過的語料庫作比較。比較過程中，可以知道哪個pattern是有用的。一個高執行效能的系統還需要特定名詞的列表，幫助辨認諸如公司、人名等特殊名詞。另外，也可以由前後文來推論，例如，當”Fred Smith”和”Mr.Smith”出現在同一篇文章中，可以猜出大概指的是同一個人。

 

30.1.2 Automated training

 

為了因應多種語言和領域的tagger，一些研究團隊不斷研究自動化訓練tagger。自動訓練方法不一定需要專業的知識工程師。系統主要通過學習已經標記好的語料庫獲取規則。任何對該知識領域比較熟悉的人都可以根據事先約定的規範標記語料庫。經訓練後的系統能處理沒有見過的新文本。這種方法要比知識工程方法快，但需要足夠數量的訓練資料，才能保證其處理質量。

 

通常使用統計模型和規則。舉例來說，先標記人名，每個token包括名字的開頭、中間和結尾，token本身的起始和結尾，然後建一個簡單的機率模型。以訓練資料集來決定每個word的機率：p(tag | w)。接著，以 Viterbi search來搜尋機率最高的tag序列。不同的name tagger運用不同的方法，例如descision-tree name tagger，maximum entropy model 和 Hidden Markov model。

 

30.1.3 Using a name tagger

 

對於事件擷取，語法分析和機器翻譯，名詞的標記和分類都是一個重要的步驟。名詞辨認器可以從包含大量專有名詞的文件中萃取資訊，也可以替文件編索引。

 

30.2 Event Extraction

 

從文件中擷取特殊關係或事件。例如，從演講清單中找出每場演講的演講者、題目、日期時間和地點，更進一步的應用則從報章中擷取特定的資訊。

 

30.2.1 Event recognitzers

 

仿照name tagging的方法，先寫出pattern，但因為有太多例外和變異，還夾雜許多特殊名詞。原則上，這些現象必須經由增加pattern的複雜性來解決。

 

30.2.2 Partial Parsing

 

辨認某些形式的組成要素可以處理一些問題。組成要素可以包含一個或多個token，而且有分類和一個以上的特徵。過程中，先辨別名詞，再辨別名詞片語、動詞，其中動詞包含時態的判斷。最後再辨認事件，構成一個由上而下處理的

paserer。

 

30.2.3 Adressing Other Problems

 

有兩種方法曾被用來處理子句句法的變異性，一種方法將parsing延伸到子句結構。對於不同的句型產生相對應的結構。這種方法的困難在於子句結構不能單獨以句法來分析，還必須考慮語意。另一個方法則是使用metarule，先決定一個主動子句，再由此產生被動、關連等相關子句。

另一個要解決的問題是anaphora，我查閱了一些資料，發現這是一個文章中常見的現象。Anaphora指的是文章中出現代詞，其指的是前述文章提及的人事物。例如：”The Queen is not here yet but she is expected to arrive in the next half an hour. ” ，其中she指的是The Queen，這樣的代詞稱作anaphor，被指的詞稱為antecedent，但因為she和The Queen又都另有所指，因為它們其實是表示伊莉莎白女王，像這樣意指真實世界某樣東西的代詞則叫做coreferencial。anaphora resolution專門用來決定和分辨antecedent和anaphor。一個基本的解決機制必須建立一個anaphora的模版，尋找形式最相近的item，並作替換。我們還需要一些機制來作推理，去處理要綜合文章中的許多句子才能推斷出來的訊息。為了解決此問題，許多關於這方面的研究提出更強大的分析技術，一種能深入思考的模型。它包括所有句子的語法分析，全方面的邏輯表示，以及理論證明。然而，此方法並沒有非常成功；要精確地分析所有句子還是有其限制，而且一般語言認知對推論機制的瞭解和相關知識依然很缺乏。

 

30.2.4 Learning Methods

 

每當一個新的關係或事件被擷取時，資訊擷取系統就必須被更新，其中包含新的pattern，語意類別及推理規則。因為這類任務十分費時，有不少研究朝著將此過程自動化努力。大部分研究都是針對全自動化的系統或是利用人工標註的語料庫來建立半自動化的系統。其中包括從已註解的例子中，擷取並產生pattern。

  一個較自動化的系統會嘗試從多個已註解好的例子自動產生pattern。如果這個pattern沒有產生任何錯誤的資訊，則可以用它來生成句子的模版。同樣地，如果兩個不同的例子確有相同的word class，則可以合併。一些領航系統使用機器學習的方法，從已註解的文章中建立資訊擷取系統。這些技術包含特徵學習和機率規則。

  學習過程的對例子的註解很有幫助。一個直覺的方法是註解大量連續文件，但因為只有少數的pattern會重複出現，所以這是非常耗時的。註解大量資料的目標就是要找出存在出現頻率較低的pattern的例子，進一步找出能幫助學習過程的例子。

  利用文件中pattern的分佈可以有效率地找到相關的pattern，而且只需要些許使用者的協助。Riloff提出一個將文章標記為關連或非關連的方法來達成擷取任務，出現在關連文章中的pattern較適合被選用來擷取其他pattern。Yangarber則擴展這個方法，由使用者提供初始的pattern，再由此找出相關的文章，進一步產生更多pattern。

  自動學習過程可以提高擷取半結構化文件的效率，像是分類廣告、公告等。而複雜的自由文本，雖然不斷有學者投入研究，但還未開發出一個完整且全面性的擷取系統。

 

30.2.5 Evaluation

 

八十年代以來，美國政府一直支援MUC對資訊擷取技術進行評測。各屆MUC吸引了許多來自不同學術機構和業界實驗室的研究者參加資訊擷取系統競賽。每個參加單位根據預定的知識領域，開發一個資訊擷取系統，然後用該系統處理相同的檔案資料庫。最後用一個官方的評分系統對結果進行評比。

研討會的目的是探求IE系統的量化評價體系。在此之前，評價這些系統的方法沒有章法可循，測試也通常在訓練集上進行。MUC首次進行了大規模的自然語言處理系統的評測。如何評價資訊擷取系統由此變成重要的問題，評分標準也隨之制定出來。各屆研討會的測試主題各式各樣，包括拉丁美洲恐怖主義活動、合資企業、微電子技術和公司管理層的人事更迭。

資訊擷取技術的評測起先採用經典的資訊檢索(IR)評價指標，即召回率(Recall)和精確率(Precision)，但稍稍改變了其定義。經修訂後的評價指標可以反映IE可能產生的過度概括現象(Over-generation)，即資料在輸入中不存在，但卻可能被系統錯誤地產生出來。

就IE而言，召回率可粗略地被看成是測量被正確擷取的資訊的比例，而精確率用來測量擷取的資訊中有多少是正確的。計算公式如下：

P=TP/TP+FP

R=TP/TP+FN

其中，

TP(true-positive) : 系統識別為實體名稱且屬於實體名稱之實體名稱集合。  

FP(false-positive) : 系統識別為實體名稱但不屬於實體名稱之實體名稱集合。                                                                              

FN(false-negative) : 系統識別為非實體名稱但屬於實體名稱之實體名稱集合。                                                                        

兩者取值在0和1之間，通常存在反比的關係，即P增大會導致R減小，反之亦然。

評價一個系統時，應同時考慮P和R，但同時要比較兩個數值，畢竟不能做到一目了然。許多人提出合併兩個值的辦法。其中包括F值評價方法：

其中是一個預設值，決定對P側重還是對R側重。通常設定為1。

這樣用F一個數值就可很看出系統的好壞。

 

30.2.6 Application

 

   IE可以應用在許多地方。例如，製造商每隔一段時間就要蒐集各個設備的維修狀況報表，他們可能需要分析設備毀損的主要原因；又如公司或國際企業常常要瀏覽新聞，掌握各公司和政府的活動資訊。如果這些資訊能整理成列表式的資料庫，將十分容易搜尋。醫療記錄是另一個讓人感興趣的領域。醫院擁有大量的病人資料，醫學研究為了觀察診斷和治療，治療與療效的關係，往往需要分析這些病歷。自動轉換這些資料成標準的醫學格式將減少人工的耗費。

 

相關文獻涉獵

 

    IE的應用不勝枚舉，我看了幾篇相關論文，以下是心得分享：

1. Xiaohua Hu1， T.Y. Lin， Il-Yeol Song，Xia Lin， Illhoi Yoo，Mark Lechner，Min Song

Ontology-based Scalable and Portable Information Extraction System to Extract Biological Knowledge from Huge Collection of Biomedical Web Documents

Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (WI’04)

 

因為生醫文獻日漸繁多，所以從網路上的生醫文章中自動發現和擷取生醫知識變得越來越重要。這篇論文綜合ontology-based semantic tagging、information extraction和data mining等技術，設計了一個系統SPIE(Scalable and Portable Information Extraction)目標是從PubMed等線上生醫文獻中自動擷取各類不同的生醫知識，提供生物學者作功能性的研究，諸如蛋白質之間的交互作用、基因的功能等。目前IE技術包括的步驟有name-entity tagging(identifying entity names)、syntactic parsing及rule matching。

    然而，過程中必需處理每篇文章，相當費時，對於超過12 x 10^6篇文章的PubMed來說，造成嚴重的瓶頸。如果使用filter技術來處理大量線上生醫文獻資料庫，則需要不少人力針對新的資料庫和專門領域作維護和挑選。所以SPIE希望能兼顧Scalability和Portability，並能有效率地從大量文件中擷取資訊。他們的實驗是從PubMed中擷取蛋白質的交互作用。整個系統的流程如下：

（1）      首先由使用者定義seed tuples，系統由資料庫擷取做為樣本的文章。唯一所需的資訊是使用者定義的屬性關係規格，大大減少了人為的參與。

（2）      文件被自動分類為正或負。正表示文章中至少存在一個tuple，負表示文章中不存在任何一個tuple。

（3）      應用資料探勘演算法導出queries，用來找出和標記為正的範例相似的文章。

（4）      運用ontology作function tagging，從文件中找到欲獲知的句子，並從句子中抓出tuple。

（5）      產生擷取後的pattern，並由相符合的pattern取得新的tuples。

（6）      以第三個步驟產生的query從資料庫中擷取可靠的文章，再從步驟2開始，直到沒有新的tuple產生，或是文章數量已達到最大值。

系統完成後，作者以PubMed作了驗證，只要大約450千篇文章就可以找出9138個不同的protein-protein interaction pair(PPI)，遠比以人工篩選所需的1.4百萬篇文章，效率高了不少。

2. Eugene Agichtein ，Luis Gravano

Snowball: Extracting Relations from Large Plain-Text Collection

ACM DL 2000

 

文本上往往隱含許多有價值的結構式資料。例如，新聞中常常提到公司總部的地點，這些資訊可以用一組tuple <o,l>來表示，o代表Organization，l 代表Location of Headquarters ，像是<Microsoft,Redmond>、<IBM，Amonk>等。Snowball系統運用最新的技術從文本中產生pattern並擷取tuple。Snowball也開發一套評鑑pattern和tuple得方法，只有被認可的pattern和tuple才會被接受。以下是Snowball的架構圖：

 

 

 

修課心得

 

這門課是我這學期修的課中讓我收穫最多的。不僅學到許多計算語言學的知識，還得到不少精神上的啟發。我印象很深的一次是李勤岸教授來授課，一位同學問「為什麼要救快死的語言呢？現在網路這麼發達，很多網頁都是英文的，會不會以後只剩英文一種語言主導世界呢？」我想這個問題也是一般人的想法，現在許多人只想把英文學好，卻不關心日漸式微的本國語言。然而老師的回答讓我十分感動：這就像一個人在生死關頭，我們不也是竭盡全力去救他嗎？語言是一種文化，它可以反映歷史傳統和地方色彩，有它不可磨滅的價值，是人類寶貴的文化資產和智慧結晶。如果世界上只剩下幾種強勢語言，一個地方將失去它獨特的風采和人文特色，我們到哪裡旅行就像在自家門前繞了一圈，毫無樂趣可言。李教授也提到哈佛大學有不少人在全力保存一些少數民族的語言，他們都正視到語言的重要。而且事實也證明，網路語言以邁向多元化，英文網頁的比例逐漸下降，各國語言的網頁有增加的趨勢，我們也應該對台語有信心。

很感謝高老師開這門課，老師不遺餘力地推動台語文，令人佩服，這真的是一個神聖的工作。我也希望以後還能修到相關的課程。

 

Reference

 

1. Line Eikvil 原著（1999.7），陳鴻標譯 (2003.3)，網上資訊抽取技術縱覽。

2.Xiaohua Hu1， T.Y. Lin， Il-Yeol Song，Xia Lin， Illhoi Yoo，Mark Lechner，Min Song.Ontology-based Scalable and Portable Information Extraction System to Extract Biological Knowledge from Huge Collection of Biomedical Web Documents.Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (WI’04).

3.Eugene Agichtein ，Luis Gravano.Snowball: Extracting Relations from Large Plain-Text Collection.ACM DL 2000.