無為

第一章 ???????? 導論

?

信息抽取（ Information Extraction: IE ）的目標是把文本里包含的信息進行結構化處理，變成表格一樣的組織形式。輸入信息抽取系統的是原始文本，輸出的是固定格式的信息點。信息點從各種各樣的文檔中被抽取出來，然后以統一的形式集成在一起。這就是信息抽取的主要任務。

信息以統一的形式集成在一起的好處是方便檢查和比較。例如比較不同的招聘和商品信息。還有一個好處是能對數據作自動化處理。例如用數據挖掘方法發現和解釋數據模型。

信息抽取技術并不試圖全面理解整篇文檔，只是對文檔中包含相關信息的部分進行分析。至于哪些信息是相關的，那將由系統設計時定下的領域范圍而定。

信息抽取技術對于從大量的文檔中抽取需要的特定事實來說是非常有用的。互聯網上就存在著這么一個文檔庫。在網上，同一主題的信息通常分散存放在不同網站上，表現的形式也各不相同。若能將這些信息收集在一起，用結構化形式儲存，那將是有益的。

由于網上的信息載體主要是文本，所以，信息抽取技術對于那些把因特網當成是知識來源的人來說是至關重要的。信息抽取系統可以看作是把信息從不同文檔中轉換成數據庫記錄的系統。因此，成功的信息抽取系統將把互聯網變成巨大的數據庫！

信息抽取技術是近十年來發展起來的新領域，遇到許多新的挑戰。

本文首先在第二章簡要介紹信息抽取技術，第三章介紹網頁分裝器 (wrapper) 的開發，第四章介紹已經開發出來的網站信息抽取系統，第五章介紹信息抽取技術的應用范圍以及首批已經進入商業運作的商用系統。

第二章 ???????? ? 信息抽取技術概述

信息抽取原來的目標是從自然語言文檔中找到特定的信息，是自然語言處理領域特別有用的一個子領域。所開發的信息抽取系統既能處理含有表格信息的結構化文本，又能處理自由式文本（如新聞報道）。 IE 系統中的關鍵組成部分是一系列的抽取規則或模式，其作用是確定需要抽取的信息 [52] 。網上文本信息的大量增加導致這方面的研究得到高度重視。

本章首先介紹信息抽取領域的發展。第 2.1. 節比較了信息抽取和信息檢索的區別；第 2.2. 節介紹 IE 的歷史。接下來兩節解釋評價 IE 系統的指標和常用的兩派技術方法。信息抽取技術所處理的文本類型將在第 2.5. 節中說明。第 2.6. 節描述信息抽取技術可利用的網頁特征。

第2.1.節 ????????? IR 和 IE

IR 的目的是根用戶的查詢請求從文檔庫中找出相關的文檔。用戶必須從找到的文檔中翻閱自己所要的信息。

就其目的而言， IR 和 IE 的不同可表達如下： IR 從文檔庫中檢索相關的文檔，而 IE 是從文檔中取出相關信息點。這兩種技術因此是互補的。若結合起來可以為文本處理提供強大的工具 [24] 。

IR 和 IE 不單在目的上不同，而且使用的技術路線也不同。部分原因是因為其目的差異，另外還因為它們的發展歷史不同。多數 IE 的研究是從以規則為基礎的計算語言學和自然語言處理技術發源的。而 IR 則更多地受到信息理論、概率理論和統計學的影響 [24] 。

第2.2.節 ????????? IE 的歷史

自動信息檢索已是一個成熟的學科，其歷史與文檔數據庫的歷史一樣長。但自動信息抽取技術則是近十年來發展起來的。有兩個因素對其發展有重要的影響：一是在線和離線文本數量的幾何級增加，另一是“消息理解研討會”（ MUC ）近十幾年來對該領域的關注和推動。

IE 的前身是文本理解。人工智能研究者一直致力于建造能把握整篇文檔的精確內容的系統。這些系統通常只在很窄的知識領域范圍內運行良好，向其他新領域移植的性能卻很差 [53] 。

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

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

過去五、六年， IE 研究成果豐碩。英語和日語姓名識別的成功率達到了人類專家的水平。通過 MUC 用現有的技術水平，我們已有能力建造全自動的 IE 系統。在有些任務方面的性能達到人類專家的水平 [53] 。不過自 1993 年以來，每屆最高組別的有些任務，其成績一直沒有提高（但要記住 MUC 的任務一屆比一屆復雜）。一個顯著的進步是，越來越多的機構可以完成最高組別的任務。這要歸公于技術的普及和整合。目前，建造能達到如此高水平的系統需要大量的時間和專業人員。另外，目前大部分的研究都是圍繞書面文本，而且只有英語和其他幾種主要的語言。

第2.3.節 ????????? 評價指標

信息抽取技術的評測起先采用經典的信息檢索 (IR) 評價指標，即回召率 (Recall) 和查準率 (Precision) ，但稍稍改變了其定義。經修訂后的評價指標可以反映 IE 可能產生的過度概括現象 (Over-generation) ，即數據在輸入中不存在，但卻可能被系統錯誤地產生出來（ Produced ） [24] 。

就 IE 而言，回召率可粗略地被看成是測量被正確抽取的信息的比例 (fraction) ，而抽準率用來測量抽出的信息中有多少是正確的。計算公式如下：

P= 抽出的正確信息點數 / 所有抽出的信息點數

R= 抽出的正確信息點數 / 所有正確的信息點數

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

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

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

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

第2.4.節 ????????? IE 系統設計的兩大方法

IE 系統設計主要有兩大方法：一是知識工程方法（ Knowledge Engineering Approach ），二是自動訓練方法 (Automatic Training Approach) 。

知識工程方法主要靠手工編制規則使系統能處理特定知識領域的信息抽取問題。這種方法要求編制規則的知識工程師對該知識領域有深入的了解。這樣的人才有時找不到，且開發的過程可能非常耗時耗力。

自動訓練方法不一定需要如此專業的知識工程師。系統主要通過學習已經標記好的語料庫獲取規則。任何對該知識領域比較熟悉的人都可以根據事先約定的規范標記語料庫。經訓練后的系統能處理沒有見過的新文本。這種方法要比知識工程方法快，但需要足夠數量的訓練數據，才能保證其處理質量。

第2.5.節 ????????? 自由式、結構化和半結構化文本

自由式文本 ：信息抽取最初的目的是開發實用系統，從自由文本中析取有限的主要信息。例如，從報道恐怖襲擊活動的新聞中析取襲擊者、所屬組織、地點、受害者等信息；又如，從醫藥研究報告的摘要中提取新產品、制造商、專利等主要信息點。

處理自由文本的 IE 系統通常使用自然語言處理技巧，其抽取規則主要建立在詞或詞類間句法關系的基礎上。需要經過的處理步驟包括：句法分析、語義標注、專有對象的識別（如人物、公司）和抽取規則。規則可由人工編制，也可從人工標注的語料庫中自動學習獲得。

自由文本信息點抽取技術的現有水平不可與人的能力同日而語，但還是有用的，不管其抽取規則是人工編制的還是通過機器學習的 [52] 。雖然自然語言理解是漫長的期待，但是，信息抽取技術確實可行，因為這項技術對其需要搜索的模式類型有很強的限定，而這種限定是有根有據的。

結構化文本 ：此種文本是一種數據庫里的文本信息，或者是根據事先規定的嚴格格式生成的文本。從這樣的文本中抽取信息是非常容易的，準確度也高，通過描述其格式即可達到目的。所用的技巧因而相對簡單。

半結構化文本 ：這是一種界于自由文本和結構化文本之間的數據，通常缺少語法，象電報報文，也沒有嚴格的格式。用自然語言處理技巧對這樣的文本并不一定有效，因為這種文本通常連完整的句子都沒有。因此，對于半結構化文本不能使用傳統的 IE 技巧，同時，用來處理結構化文本的簡單的規則處理方法也不能奏效。

在半結構化文本中確實存在一些結構化的信息，但是，抽取模式通常依賴字符和象 html 標記那樣的分隔標志。句法和語義信息的作用則非常有限。

第2.6.節 ????????? 網頁

因特網提供了一個巨大的信息源。這種信息源往往是半結構化的，雖然中間夾雜著結構化和自由文本。網上的信息還是動態的，包含超鏈接，以不同的形式出現，而且跨網站和平臺，全網共享。因此，因特網是一個特殊的挑戰，一直推動著從結構化和半結構化文本中抽取信息的研究向前邁進。

有些研究者把所有網頁都歸入半結構化文本，但 Hsu[31] 對網頁類型做了頗有用的定義：若能通過識別分隔符或信息點順序等固定的格式信息即可把“屬性 - 值”正確抽取出來，那么，該網頁是結構化的。半結構化的網頁則可能包含缺失的屬性，或一個屬性有多個值，或一個屬性有多個變體等例外的情況。若需要用語言學知識才能正確抽取屬性，則該網頁是非結構化的。

網頁的結構化程度總是取決于用戶想要抽取的屬性是什么。通常，機器產生的網頁是非常結構化的，手工編寫的則結構化程度差些，當然有很多例外。

傳統的 NLP 技巧對抽取半結構化文本的信息并不是很有用，因其缺少規范的語法結構，而且， NLP 方法的處理速度通常比較慢，這對于網上海量信息來說是一個大問題。

網上大部分內容都以屬性列表的形式呈現，例如很多可搜索的網頁索引。這種外觀上的規律性可被利用來抽取信息，避免使用復雜的語言學知識。

網頁上的組織結構和超鏈接特性是需要認真考慮的重要因素。例如，可能需要打開鏈接的內容才能找到你想要的信息。網頁的組織結構不同，抽取規則也不同。

網上數據庫查詢的結果通常是一系列的包含超級鏈接的網頁。文獻 [14] 把這類網頁分成三類：一層一頁，即一個頁面即包含了所有的查詢結果；一層多頁，即需要調出多個鏈接才能獲得所有的結果；兩層頁面，即第一層是列表式條目鏈接，點擊鏈接后才能看到詳細資料。

第2.7.節 ????????? 小結

IE 領域是近十年來新發展起來的研究領域，一是由于“消息理解研討會” (MUC) 的推動，二是由于網上內容的大量增加。

IE 對自由文本和結構化文本都能處理。 NLP 技巧通常用于自由文本，對結構化和半結構化文本并不是太適合。相反，基于分隔符和字符的方法更能奏效。

因特網是包含大量半結構化文本的信息源。網頁與傳統的文本相比，有許多特點：量大，常更新，變化多，頁面的一大半包含結構化的文字塊，還可能有超鏈接。因此，網頁為信息抽取研究帶來新的挑戰。

第三章 ? 分裝器生成

第3.1. 節 ??????????????? 分裝器

第3.2. 節 ??????????????? 從 IE 發展成 WG

第3.3. 節 ??????????????? 分裝器生成

第3.4. 節 ??????????????? 分裝器的歸納學習

第3.5. 節 ??????????????? 小結

?

各網站的信息內容互相獨立，要收集起來有困難。信息抽取技術就是沖著解決此困難而來的。

因特網上還存在一個被稱為“暗藏網”（ the hidden web ），即那些網上數據庫系統。文獻 [37] 估計因特網上 80% 的內容存在于這種看不見的因特網中。搜索引擎的“網絡爬蟲”抓不到這些網頁。這就意味著需要一種獨立的工具從這些網頁中收集數據。

從網站中抽取信息的工作通常由一種叫做“分裝器”（ Wrapper ，也譯“包裝器”）的程序完成。以下 3.1. 和 3.2. 節將介紹分裝器的概念及分其生成（ Wrapper Generation, WG ）研究的歷史。第 3.3 節總結了構造分裝器的不同方法。手工制造分裝器的工作繁重，因此，自動生成的研究變得非常重要。機器學習的方法非常誘人，第 3.4 節介紹了歸納式學習的相關技巧。

第3.1.節 ??????????????? 分裝器

分裝器是一個程序，用于從特定的信息源中抽取相關內容，并以特定形式加以表示。在數據庫環境下，分裝器是軟件的組成部分，負責把數據和查詢請求從一種模式轉換成另外一種模式。在因特網環境下，分裝器的目的是把網頁中儲存的信息用結構化的形式儲存起來，以方便進一步的處理。

因特網分裝器可接受針對特定信息源的查詢請求，并從該信息源中找出相關的網頁，然后把需要的信息提取出來返回給用戶。它由一系列的抽取規則以及應用這些規則的計算機程序代碼組成。通常，一個分裝器只能處理一種特定的信息源。從幾個不同信息源中抽取信息，需要一系列的分裝器程序庫。分裝器的運行速度應該很快，因為它們要在線處理用戶的提問。它還要能應付網絡經常變化、運行欠穩定的特點。比如，網絡連接失敗、文檔格式混亂、格式變化等。

建造針對網頁的分裝器主要有兩個好處：一是提高了從某一特定信息源獲取相關信息的能力，二是能把不同信息源的信息整合到數據庫中，用通用查詢語言即可查找信息。

第3.2.節 ??????????????? 從 IE 發展成 WG

人們需要能從不同網頁資源抽取并整合數據的工具。這種需求造就了分裝器生成研究領域的發展。分裝器生成（ WG ）領域獨立于傳統的 IE 領域。典型的 WG 應用系統能從網上數據庫返回的查詢結果網頁中抽取數據。這些網頁構成一個被 WG 業內人稱之為“半結構化”的信息源。為了能把這些網頁的數據整合在一起，必須把相關的信息從這些網頁中抽取出來。因此，分裝器實質上是針對某一特定信息源的 IE 應用系統。

傳統的 IE 系統采用基于句法和語義條件相結合的抽取模式。如前所述，對于半結構化信息源，基于語言知識的模式并不是很管用。典型的 WG 系統生成的是基于分隔符的抽取模式。由于這類網頁均是在一個統一的模板上即時生成的，因此，只要學習了幾個樣本網頁后，系統即能識別分隔符特征串，構成不同的模板區域。

從網頁中抽取信息并不容易，要考慮許多問題，例如信息量膨脹的問題、系統靈活性的問題等。

第3.3.節 ??????????????? 分裝器生成

可用人工或半自動的辦法生成分裝器。手工生成分裝器通常需要編寫專用的代碼，要花很多時間理解文檔的結構并將其轉換成程序代碼。雖然處理半結構化的網頁要容易一些，但并仍然還是比較煩瑣而且容易出錯。

有一些工具可幫助手工生成分裝器。使用的方法之一是利用描述性語法對網頁結構進行描述，并且提供工具生成代碼。不過，編寫語法本身就是一項很艱巨和耗時的工作，而且需要高水平的專家。

手工構造的 IE 系統不能適應處理對象所屬領域的變化。每個領域都要有相應的分裝器，維護成本很高。對于網上信息源來說，這些缺點尤為明顯，因為網頁數量龐大，內容和結構繁雜，而且新的信息源不斷增加，舊的信息還會改變，因此，幫助生成自動抽取網頁信息的分裝器的技術變得非常重要。

半自動化生成分裝器的技術得益于上述分裝器生成的支持工具。一種方法是使用向導讓用戶告訴系統那些信息是需要抽取的。通過圖形界面，用戶即可以通過演示編寫程序，標示出需要抽取的區域。這意味著在分裝器編碼過程中不需要專業知識，而且比手工編碼少產生錯誤。但是，用這種方法也需要對新的站點進行重新的學習，因為這種系統不能自己學習新的網站結構，也不能處理舊網站的結構變化。

全自動分裝器的生成利用機器學習的技巧，開發學習算法，設計出從非常簡單到相對復雜的分裝器。即使是全自動的方法也需要人工專家的少量參與。系統必須通過學習階段，從例子中歸納出規則。通常，這個過程是由人工指導的。

分裝器歸納法是一種自動構造分裝器的技術。主要思想是用歸納式學習方法生成抽取規則。用戶在一系列的網頁中標記出需要抽取的數據，系統在這些例子的基礎上歸納出規則。這些規則的精確度如何取決于例子的質量如何。如果能代表那些需要處理的網頁，那么，這些例子就是高質量的。

第3.4.節 ??????????????? 分裝器的歸納學習

用于 IE 的機器學習方法有很多，如符號化學習法， ILP （歸納邏輯設計法），分裝器歸納法，統計法和語法歸納法。在分裝器歸納法中，分裝器的生成被描述成一種歸納學習問題。

在最高層次，歸納學習法是從一些實例中完成未知目標概念的計算任務，是對現象的一種概括。主要思路是，如果歸納出來的規則能解釋觀察到的實例，或者在新事例出現時能做出準確的預測，那么，這種歸納是成功的。在分類、知識獲取、知識發現等任務中被證明是有用的。

歸納學習法是通過推論來完成的。推論是一種從部分到整體、從個別到一般、從個體到普遍的推理過程。老師提供幾個實例給學生，學生則從中歸納出普遍適用的規則。人類的學習是基于實驗性的觀察過程中的，對于我們來說，提供好的觀察事例要比提供明確的完整的規則要容易。總的說來，歸納式學習法是一種建立在假設的基礎上的研究方法。

有指導的歸納式學習法可以分為兩類：零階 (zero-order) 和一階 (first-order) 學習法。兩者的區別在于其訓練數據和所形成的理論的表達方式的不同。

零階學習法所采用的事例是事先分好類的。每個事例都由對應于固定屬性集合的特定值描述。這類系統發展的理論以決策樹（ Decision Tree ）或生成規則（ Production Rules ）的形式出現，把事例的類和它的屬性值聯系起來。不幸的是，決策樹的學習系統缺少表達能力，因為它們建立在命題邏輯的基礎上，不能學習到對象之間的關系（如家族成員的關系）之類的概念。從數據庫角度看，他們只能處理“屬性 - 值”這種關系。

關系型一階學習法可在帶有結構信息的例子中進行歸納，例如一階邏輯謂詞和函數，無界限結構體（ Unbounded Structures ，如列表，樹）等。尤其是 ILP 方法，專門研究從例子中歸納一階邏輯形式的規則，邏輯編程的學習以及其他關系型知識。

ILP 的研究介于機器學習和邏輯編程兩種傳統研究領域之間。許多其他的機器學習算法均限定于處理有限的基于特征表達的例子和概念，而不能處理復雜的關系型和遞歸型知識。但 ILP 借助一階邏輯的表達能力，可以學習關系和遞歸概念。 ILP 還可以學習更豐富的表達式和比決策樹更復雜的概念，因此，已應用于解決從包含復雜結構和關系的文檔中抽取信息的學習中。

ILP 算法采用兩種不同的歸納方法：一是自下而上（概括），另一是自上而下（具體化）。自下而上的方法是數據驅動的。先選擇幾個例子，在此基礎上提出一個假設，使之能處理這些例子。然后把這個假設推而廣之，使之能處理其余例子。自上而下的方法則先從最普遍的假設開始，通過引入反例，把假設規則不斷具體化。總的說來，自上而下算法可以歸納出一大類的邏輯程序，但需要相對多的樣例。而自下而上算法有為數不多的例子就行了，但只能歸納出一小類的程序。

目前已經有了幾個實驗 ILP 系統，包括有名的 FOIL[47] 和 GOLEM[39] 。 FOIL 由 Quinlan 于１９８９年開發，采用自上而下的算法。在一個既有正又有反的事實的訓練集中，先找出一個只覆蓋正例而不涉及反例的邏輯子句 (clause) ，然后把這個子句覆蓋的事實從訓練集中刪除。如此直到訓練集中沒有正例為止。 GOLEM （ Muggleton and Feng 1990 ）采用貪婪覆蓋算法（ Greedy Covering Algorithm ）。子句的生成是自下而上的，建立在更多具體子句的“最少概括”（ least-general ）的概括生成上。概括一直進行直到所有的正例都被覆蓋而無一個反例被涉及。

第3.5.節 ??????????????? 小結

可以預計，網上結構化信息將不斷增加。通過查詢網上數據庫所獲得的網頁也將不斷增加。這些網頁是無法讓搜索引擎獲取的。因此，越來越需要可以把相關信息從這些網頁中抽取出來的工具。

分裝器是專門從特定信息源中抽取需要的信息并返回結果的程序。對于從不同信息源中整合信息資料是非常有用的。由于這種需求不斷增加，分裝器生成的研究領域從傳統的 IE 領域中脫穎而出。相比之下，生成分裝器所采用的技術比較少依賴句子的全面語法分析和 NLP 技術。

分裝器可由程序員直接編寫，或手工指定網站結構再由程序自動生成規則和代碼。無論是哪種情況，這個過程都是費時費力的，而且網頁的結構經常變化，新網頁層出不窮。這樣，必須建造新的分裝器。為此，網上信息抽取的研究轉向了半自動和自動生成分裝器的工作上。

分裝器歸納法是用機器學習方法自動生成分裝器的方法。在歸納法中，分裝器的生成被看成是歸納學習的問題，其任務是從一組例子中計算出一般規則，以解釋觀察到的事實。教師提供例子，學生在例子的基礎上作出歸納，推導出規則。

歸納邏輯編程方法處于傳統的機器學習領域和邏輯編程之間，使用一階邏輯規則。得益于一階邏輯豐富的表達能力， ILP 方法可以學習關系型和嵌套概念。這是大多數基于“屬性 - 值”表達方式的機器學習算法所無法達到的。 ILP 方法為此被應用到學習如何從復雜結構和關系的文檔中抽取信息。

第四章 ???????? 分裝器生成系統簡介

第 4.1. 節 ??????? 處理結構化和半結構化網頁的系統 ...

第 4.1.1. 節 ???? ShopBot

第 4.1.2. 節 ???? WIEN..

第 4.1.3. 節 ???? SoftMealy.

第 4.1.4. 節 ???? STALKER.

第 4.2. 節 ??????? 處理半結構化和非結構化網頁的系統 ...

第 4.2.1. 節 ???? RAPIER.

第 4.2.2. 節 ???? SRV.

第 4.2.3. 節 ???? WHISK.

第 4.3. 節 ??????? 小結 ...

早期從網站上抽取信息的方法基本上是基于手工操作的。程序員認真研究網站的結構后手工編寫代碼，開發一個分裝器程序，把網頁的邏輯特征抽取出來并把他們存入到數據庫。 TSIMMIS[13 ， 25 ， 28 ， 29] 系統和“斯坦福 -IBM 多信息源管理系統（ 1995 ）”是比較早的幫助建造分裝器程序的框架系統。 TSIMMIS 的目標是以一體化的方式獲取不同信息源的信息并且保證所獲取信息一致性。其重點是開發支持這種包裝過程的語言和工具。

對于數據量大，結構動態變化的網站而言，需要一種更為有效的分裝器建造方法。一般說來，數據庫領域的人把注意力放在錯綜復雜的信息如何進行整合，分裝器則用手工建造。另一方面， AI 領域的人則把重點放在機器學習的方法如何能用在網站結構的自動學習上。本章將重點介紹分裝器的自動或半自動的生成系統。

分裝器及其自動生成的復雜度和難易度將取決于網站結構的層次。第 4 .1. 節介紹的系統主要是針對結構化程度相對好的網站。這類系統多數是源自分裝器生成領域的研究者。第 4.2. 節介紹了能處理結構缺少規范化的網頁。這類系統較多地受到傳統的 IE 領域的影響。

第4.1.節 ??????????????? 處理結構化和半結構化網頁的系統

本節介紹 ShopBot, WIEN, SoftMealy 和 STALKER 系統。這類系統可以說是屬于分裝器生成系統，專門用來從網站數據庫系統生成的網頁。采用分隔符為主的抽取規則，無需用到句法和語義知識，局限于處理比較結構化的數據。

第4.1.1.節 ??????? ?ShopBot

開發者： R. B. Doorenbos, O. Etzioni, D. S. Weld (1996/1997)[17,18] 。

ShopBot 是比價代理系統，專門從網上賣家的網站上抽取信息，因此，比其他系統的局限性要大。其算法主要針對以表單形式提供查詢的頁面，而且返回的搜索結果是以表格形式顯示的產品信息頁面。從結果頁面中抽取信息的技巧結合了啟發式搜索、模式匹配和歸納式學習。

ShopBot 的運行分兩個階段：離線學習階段和在線比價階段。在學習階段，系統分析每個購物網站，獲得其符號化描述，然后在比價階段，利用獲得的符號化描述，從網站上抽取信息，找到用戶指定的產品的最低價格。

在學習階段，系統利用簡單的啟發式方法找到正確的檢索表單，學習如何向該表單發送查詢請求。學習程序還必須判定查詢結果頁面的格式。一般包括頭部、主體和尾部等三部分。頭尾兩部分在所有的結果頁面中都是一致的，而主體則包含了想要的產品信息。結果頁面的格式是通過三個步驟判定的：

第 1 步：獲取“找不到產品”的失敗頁面。用不存在的詞（如“ xldccxx-no-product” ）作為關鍵字查詢數據庫，然后分析返回的頁面。

第 2 步：找到頭尾部分。用可能存在的產品名稱去查詢數據庫，通過分析返回的頁面找到頭尾部分。

第 3 步：判定包含產品信息的主體格式。首先用 HTML 標記和字串對可能的產品信息摘要進行定義和表示。網頁主體被切分成“邏輯行”，代表“垂直空格分隔” (vertical-space-delimited) 的文本。學習程序用邏輯行比較不同的摘要形式，找到最佳匹配。這樣可以找到產品的描述格式，但是不能歸納出信息欄的名稱。最關鍵的價格信息是用手工編碼的方法獲取的。

第4.1.2.節 ??????? ?WIEN

開發者： N. Kushmerick (1997) [33,34] 。

“分裝器歸納生成環境”（ WIEN-Wrapper Induction Environment ）是輔助分裝器生成的工具，為網頁的自動分析而設計，受到 ShopBot 的影響。不過， Kushmerick 是第一個提出分裝器歸納生成這一術語的。其方法不只局限于某一領域，適用于所有包含表格信息的結構化文本，也不只是用于 HTML 文本。

這種方法可以處理被他們稱之為具有 HLRT 結構的網頁：頭分隔符、左右分隔符（在每個待抽取的事實的左右）和尾分隔符。系統尋找標記信息點開始和結尾的統一的分隔符，以及那些把表格信息與其他周圍信息分開的分隔符。符合這一規則的頁面幾乎都是搜索數據庫所得的結果頁面。

Kushmerick 力圖盡量自動化，避免用人工標記樣例，因此開發了一系列自動標記樣例的方法。標記算法需要輸入特定領域（ domain-specific ）的啟發學習規則，目標是找到待抽取屬性的值。系統雖然需要輸入學習規則，但卻不管這些規則是如何獲得的，可以手工編制。即使是這樣，比起標記整個網站來，其工作量要小。

系統采用歸納學習法，從查詢結果樣例中生成分裝器。歸納算法是：把標記好的網頁作為輸入，然后搜索由“ HLRT 分裝器模型”定義的分裝器空間（ space of wrappers ），反復嘗試所有可能的分隔符，直到找到與標記網頁相一致的 HLRT 分裝器。系統還采用基于機器學習理論的模型來預測需要學習多少個例子，以保證所生成的分裝器的出錯幾率控制在一特定的范圍內。

由于 WIEN 只考慮與待抽取數據緊相鄰的分隔符，因此不能包裝那些數據不全或信息項次序不固定的網頁。系統采用的是多欄（ Multi-slot ）規則，這就意味著能把相關的信息聯在一起，而單欄規則只能抽取孤立數據（例如，若一篇文檔包含多個姓名和地址，使用單欄規則不能辨認出哪個地址是屬于某人的）。

第4.1.3.節 ??????? SoftMealy

開發者： C-H. Hsu (1998)[30,31] 。

Kushmerick 之后，有好幾個別的系統研發出來，力圖改進 WIEN 的分裝器歸納算法。 SoftMealy 是一個通過學習分裝器學習從半結構化網頁中抽取信息的系統。其分裝器被稱為“非確定有限自動機”（ non-deterministic finite automata ）。這種表達模式和學習算法據說可以處理缺失值、一欄多值和變量改變（ permutations ）的情況。

系統從訓練樣例中歸納上下文規則。訓練樣例提供一個有順序的事實列表以及事實間的分隔符。歸納生成分裝器時，把一系列帶標記元組（ labeled tuples ）作為輸入。這些元組提供了分隔符的位置和事實次序變化的信息。這些信息被歸納為上下文規則作為結果輸出。

歸納生成的分裝器是一個“非確定有限自動機”。其狀態代表待抽取的事實，狀態的轉換代表定義分隔符的上下文規則。狀態的轉換由上下文規則的匹配結果來確定。分裝器通過識別事實周圍的分隔符來抽取事實。

SoftMealy 的規則允許使用通配符，而且能處理信息缺失和次序變化。然而，為了能處理不同次序的事實，系統需要學習其各種可能的次序。總的說來， SoftMealy 的抽取模式比 WIEN 規定的要更有表達能力。

第4.1.4.節 ??????? STALKER

開發者： I. Muslea, S. Minton, C. Knoblock. (1998) [42,43,44] 。

STALKER 采用指導學習的算法歸納抽取規則。訓練例子由用戶提供。用戶需選擇若干樣例頁面并把有用的數據（即所謂“ EC 樹”的葉子）標記出來。頁面被標記好后，系統可生成一符號序列（ the sequence of tokens ），用來表示頁面的內容，還生成代表信息點開始的符號索引。符號系列（字、 HTML 標記）和通配符被作為定位標志，用于找到頁面上的數據。分裝器歸納算法產生抽取規則并表示為簡單的標志語法（ landmark-grammars ）。此法可處理文本，但不能處理鏈接信息。

網頁文檔用所謂的“內嵌目錄”（ Embedded Catalog ）表示。那是一個樹形結構，其內部節點或是同構的（ homogeneous ）信息點列表，或是異構信息點元組（ tuples ）。根節點是整篇文檔，任一節點的內容代表其父節點內容的一個接續（ subsequence ）。末節點即是用戶需要抽取的數據。 ?

STALKER 采用線性覆蓋算法（ sequential covering algorithm ）。首先生成線性標志自動機（ landmark automata ）。這些自動機能產生盡可能多的訓練正例（ positive training examples ）。該自動機實際上是一個“非確定有限自動機”。其狀態的變化只有在字符串輸入為了目前狀態與下一狀態間的轉換而被接受時才發生。然后系統試圖生成新的自動機以覆蓋剩余的例子，一直到所有的訓練例子都被覆蓋為止。這時， STALKER 返回一個被稱之為 SLG （簡單標記語法）的解決方法。其每個分支都對應一個學習獲得的標記自動機。

STALKER 可以包裝有任意層結構的信息源。每個節點的抽取與其子節點獨立，因此，文檔中信息點的次序是沒有關系的。對于信息點缺失或次序多變的文檔一樣能處理。這就比只能處理固定次序的 WIEN 等系統更靈活。與同樣能處理信息點缺失或次序多變文檔的 SoftMealy 不同， STALKER 無需把各種可能的次序變化都學習到。

STALKER 采用的規則與 WIEN 的不同，是單欄的。不過由于 STALKER 利用 EC 樹把從多欄模板中取出的單個信息點集在一起，因此沒有什么缺陷。

第4.2.節 ??????????????? 處理半結構化和非結構化網頁的系統

本節介紹 RAPIER ， SRV 和 WHISK 系統。這些系統比上節介紹的要復雜一些，能處理的文本類型要多一些。雖然如此，它們并不依賴語義和句法信息，只是在可能的情況下利用這些知識，而且能發揮混合抽取模式的作用。

這些系統更接近傳統的信息抽取方法，可以說處于 IE 和 WG 中間，因為它們的重點是開發用機器學習方法來解決 IE 問題。所用的方法以歸納邏輯編程（ inductive logic programming ）或關系學習（ relational learning ）為基礎，而且與歸納算法有關，比如 FOIL 算法（ SRV ， WHISK 采用）和 GOLEM 算法（ RAPIER 采用）。

第4.2.1.節 ????????????? RAPIER

開發者： E. Califf (1997) [11,12] 。

RAPIER （ Robust Automated Production of Information Extraction Rules ，健壯的信息抽取規則自動生成系統）以半結構化文本為處理對象，學習抽取規則，為整個 IE 過程服務。系統需要輸入指明待抽取信息的“文檔 - 充實模板”（ filled template ）組對作為訓練內容，從中獲得模式匹配規則，抽取“填充子”（ filler ）填充模板中的空槽。

學習算法結合了多個歸納邏輯編程系統所采用的技巧，能學習無界限模式。這些模式包含了對詞的限制條件和填充子周圍的詞性。學習算法由一個從具體到一般（即自下而上）的搜索，從訓練中與目標槽匹配的最具體的規則開始。隨機從規則庫中抽取一對對規則，然后橫向搜索（ beam search ），以圖找到這兩條規則的最佳概括，采用最少概括的概括方法（ a least general generalization ），增加限制條件，不斷重復后直到不再有進展為止。

RAPIER 的抽取規則是建立在分隔符和內容描述的基礎上的，即使用了能利用句法和語義信息的模式所表達的規則。系統使用了一個詞性標注程序獲取句法信息，使用了一個語義類別詞典獲取語義信息。標注程序以句子為輸入單位，把詞標注為名詞、動詞、形容詞等，速度和健壯性都比完全句法分析器快和優，但給出的信息有限。

信息抽取規則用模板名和格欄（ slot ）名索引，由三部分組成：前填充子（ pre-filler ）：一個應匹配目標文本之前的文本的模式（ pattern ）；填充子：一個應匹配目標文本的模式；后填充子：一個應匹配緊接目標文本之后的文本的模式。

一個模式是一串模式信息點（ pattern items ），要求一個一個詞匹配，或者是模式列表（ pattern lists ），可匹配 N 個詞。文本必須滿足模式規定的條件才算匹配成功。可能的條件包括文本必須是（ I ）一組詞，其中一個必須與文檔文本匹配；（ II ）一組句法標記，其中一個標記必須與文檔文本的標記匹配；或者（ iii ）一組語義類別，文檔文本必須屬于其中一類。

這種以目標詞組為中心設定抽取區域的方法意味著系統只能進行單格抽取。但是，若把文本分成超過三個區域，系統或許能進行多格抽取。

第4.2.2.節 ????????????? SRV

開發者： D. Freitag (1998) [21,22,23] 。

SRV(Sequence Rules with Validation ，帶確認功能的次序規則 ) 是一種自上而下、關系型的信息抽取算法。其輸入是一系列的網頁，上面標記了待抽取區域的實例（ instance ），以及一系列基于字串 (token) 的特征。輸出是一系列的抽取規則。

SRV 把信息抽取問題看成是一種分類問題。文本中所有可能的短語（取最長者）都是實例。文檔中的候選實例被提交到分類器。系統會給每個短語賦一個測量值，用于反映該短語作為目標格填充子的信度。最初版本的 SRV 采用的分類器是一個關系型規則的學習器，使用的歸納方法類似于 FOIL 的自上而下的辦法。在文獻 [23] 中，他們采用了另外兩個分類器，機械背誦學習器（ rote learner ）和簡單貝葉斯分類器 (na?ve Bayes classifier) ，并與原來的分類器作了比較。

SRV 利用的特征分兩種：簡單特征和關系特征。字詞的長度、類型、拼寫、詞性等屬于簡單特征。關系特征反映字詞的相鄰度。正是這一特征使 SRV 具有關系型的特點。

SRV 的學習素材包括訓練集文檔中與最短實例區（ field instance ）一樣長（以詞的個數計算）的字串，但不能長過最長的實例。抽取過程即是檢驗長度適合的字串是否與規則匹配的過程。

SRV 與 FOIL 一樣，從學習所有正反例子開始。所謂反例是沒有被標記為實例區的字串。歸納過程也是用正排除法，即當一條規則覆蓋的例子全部是正例，或該規則已無法繼續具體化時，所有與之匹配的正例將被從訓練集中刪除。然后重復以上過程。

SRV 的規則具有較強的表達能力，且無需先進行句法分析。 SRV 與 STALKER 和 RAPIER 有類似之處，能把與其他相關信息點獨立的特定信息點抽取出來。關系型學習器也與 RAPIER 的一樣用于抽取單格信息點。這與 WIEN 等抽取多格信息的系統不一樣。

第4.2.3.節 ????????????? WHISK

開發者： S. Soderland (1998) [52] 。

WHISK 系統能處理的文本對象很全面，從結構化程度很強的文本到網頁等半結構化文本，還能處理新聞等純文本。處理結構化或半結構化文本時， WHISK 無須事先經過句法分析，但處理自由文本時，最好能先對文本作句法和語義標注。

系統采用指導學習算法，而且需要輸入一系列手工標注的訓練實例。標注和學習過程是交織在一起的。每次循環，系統將提交一批實例讓用戶標注，系統則從標注的實例中歸納出規則。

開始時，輸入的文本是未標注的，訓練集也是一個空集。系統會從文本中挑選一批實例（即小于整個文檔的文字單位），讓用戶把需抽取的部分加上標記。怎樣的字串會被選為實例呢？這取決于文檔的類型。對于結構化和半結構化文檔來說，系統根據 HTML 標記或其他字符串表達式把文本切成多個實例。對自由文本，實例的切分將由一個句子分析器完成。在這種情況下，一個實例可能是一個句子或者句子的一部分。

訓練實例上的標記將指導抽取規則的生成，并且檢驗規則的效果。如果規則被成功應用到一個實例上，那么該實例則被認為被規則“覆蓋”了。如果抽取出來的詞組與實例上的標記相吻合，則認為該詞組的抽取是正確的。

WHISK 屬于機器學習算法家族中的覆蓋學習法，與自上而下的學習分類歸納法相關。首先，找到一個最寬泛（ general ）的能覆蓋規則種子的規則，然后一次加一個條件，直到錯誤率為零，或者滿足一個事先設定的標準為止。用來衡量新條件增加的標準是規則的 Laplacian 期望錯誤值。計算公式如下： 。 N 是訓練集中抽取出來的字串數， e 是這些字串中應用規則所產生的錯誤數。學習過程一直進行，直到能覆蓋所有該被覆蓋的抽取字串都被覆蓋為止。最后把那些過適（ overfitting ）規則刪除掉。

WHISK 與 SRV 、 RAPIER 等一樣可以處理結構化和非結構化文本，但沒有“單格”抽取法的缺陷。象 WIEN 一樣， WHISK 通過多格“格框架”（ Case Frame ），把有關的信息聯系在一起。 WHISK 與 SRV 和 RAPIER 也不同，操作的對象不是整個文檔，而是象句子或類似長度的文本。

WHISK 象 SoftMealy 一樣可以處理信息點順序變化的情況，但需要輸入各種例子，以便學習所有可能的排序。由于其特征集的表達能力不強，因此不能表達否定特征（ negated features ），比 SRV 的性能要差一些。

第4.3.節 ??????????????? 小結

本章比較了幾個分裝器的自動學習系統。 表 4. 1 總結了這些系統的特點。

表 4. 1. 七 個系統的功能特征比較

第五章 ???????? 商用系統簡介

第 5.1. 節 ??????? 應用范圍 ...

第 5.2. 節 ??????? 商用系統 ...

第 5.2.1. 節 ???? Junglee.

第 5.2.2. 節 ???? Jango.

第 5.2.3. 節 ???? MySimon.

第 5.3. 節 ??????? 小結 ...

因特網上的海量信息是世界各地的用戶都能獲得的，因此，能幫助完成信息自動收集和分析的代理程序是非常有用的。具有如此技術的應用程序有很多。

本章第 1 節介紹了信息抽取應用系統已被試用的幾個領域。第 2 節介紹了首批商用系統。

第5.1.節 ????????? 應用范圍

網上有很多有用的信息，例如電話黃頁、產品目錄、股票行情、天氣預報等。這些信息可能不是由一個網上數據庫提供，而是分散在多個數據庫中。這些數據庫可供用戶輸入關鍵字等查詢條件進行搜索，然后自動生成網頁，把結果顯示出來。

一般說來，把來源分散的數據集中在一起是非常有用的。但是，以瀏覽器為界面的瀏覽方式不直接支持把不同網站的數據集成起來，因此，信息抽取工具便有了用武之地。

前一章節介紹的系統對幾種不同的網頁信息進行了處理。下面重溫一下其中幾類：

l ?????? 產品描述

ShopBot 專為此設計 [17 ， 18] ，用于比價購物。所抽取的產品信息按價格排序。

l ?????? 餐廳指引

STALKER 被用來抽取不同網站上的餐廳信息，如餐廳名稱、菜肴種類、價格、烹調方法、地址、電話和評價。 [42 ， 43]

l ?????? 講座通知

SRV 試用在講座信息的抽取任務上，把講者、地點、時間等信息抽取出來。

l ?????? 招聘廣告

RAPIER 和 WHISK 被用于招聘廣告的信息抽取。需抽取的信息點包括職位名稱、工資、地點等。

l ?????? 人事更迭公告

這項任務需要處理自由式文本，屬于傳統的信息抽取任務。 WHISK 曾被實驗從一堆華爾街金融雜志的文章中分析出公司管理層的人事更迭事件 [52] 。目標是抽取出公司名稱、職位、新任人員的姓名、卸任人的姓名。

以上只是這種技術可發揮作用的許多應用領域中的很小的一部分。其他還有很多例子，例如，租賃廣告、地理信息、假日旅游信息、天氣預報、參考書目信息等。

總的說來，具有信息抽取和收集功能的代理程序可以用于處理任何列表式的、分散在一堆網頁上的數據。

第5.2.節 ????????? 商用系統

在上節提到的應用中，比價購物是主要的商用領域之一。其原因之一是近來對電子商務的普遍關注以及因特網上與此相關的應用在不斷增長。

另一原因是這類網上商店網站專門為用戶快速找到商品而設計，具有統一的外觀和風格。這就為比價系統自動處理商品信息帶來了便利。

由于不同商家經常經營同一商品，因此，從不同商家網站中收集并比較同一產品的價格的服務受到網上購物用戶的歡迎。通常，網上商店提供的商品信息是存在數據庫系統中的。用戶需要這些信息時，系統將根據用戶的請求從數據庫中提取數據，當即顯示給用戶。這部分的信息成為了“暗藏網”（ hidden web ），因為搜索引擎查不到這些數據。比價系統成為除手工收集以外的這類信息獲取的唯一途徑。

下面將介紹三種商用比價系統： Junglee ， Jango 和 MySimon 。它們是市面上最引人注目的系統，實現方法各有千秋。 Jango 和 mySimon 用的是在線模式，即當用戶發出請求時馬上到各網站查找信息。 Junglee 則先把數據收集下來，在必要的時候進行更新。

每個系統都是在用戶的請求下返回產品清單，用戶可對清單上的價格作出比較并決定從哪個商家中購買。下面對以上系統作一簡要介紹。

第5.2.1.節 ??????? Junglee

1996 年斯坦福大學的研究生們創建了 Junglee 。 1998 年 Amazon 以大約 1 億 8 千萬美圓的價格收購了該系統。 Junglee 使用的是一種被成為虛擬數據庫（ Virtual Database, VDB ）的技術，并利用 HTML 和 XML 的混合形式表示從多個網站中獲取的信息 [46 ， 48] 。

VDB 把分散的數據收集下來，規范化并整合起來，為程序員提供一個單一數據庫的界面。分裝器負責與數據源對接，把數據轉換成數據庫。

VDB 有兩個主要組成部分：數據整合系統和數據發布系統。前者完成數據的抽取，后者定期完成數據庫更新。數據整合系統有三個組成部分：一組分裝器、一個影射器和一個抽取器。分裝器提供對不同網站的統一接口，用描述性編程語言建造，特別針對網站結構和鏈接網站間的特點而設計。

影射器用預定義的影射規則，把抽取出來的數據轉換成統一的格式。抽取器用字典和語言學規則從非結構化的文本中歸納出其組織結構。兩者都采用了特殊設計的語言來編寫規則。針對每個網站都有一個單獨的分裝器，而抽取器則針對所有類似網站。

第5.2.2.節 ??????? Jango

Jango 的前身是 ShopBot ，是 NETbot 的產品。發源于華盛頓大學的研究者 Oren Etzioni 和 Dan Weld 的研究成果 [17 ， 18] 。 1997 年 10 月 Excite 用 3500 萬美圓收購了 NetBot ，把 Jango 整合進其購物頻道。

Jango 由四部分組成 [8] ：（ I ）一個自然語言前端，能將用戶請求轉換成產品描述的邏輯表示；（ ii ）一個查詢路由器（ query router ），能判定產品類別，找出相關的一系列網站；（ iii ）一個集成引擎，能平行向選定的網站提交查詢；（ iv ）一個過濾器，能用類似于 ShopBot 的方法，把信息抽取出來。

在學習階段， Jango 根據網上商店首頁的 URL 和產品領域知識，學習如何在網站購物，能學得每個商店的產品描述的格式，獲取價格等產品屬性。在購物階段，這些學得的描述將被用于抽取用戶指定的產品信息。信息抽取是在線平行進行。結果以價格排序顯示給用戶。

第5.2.3.節 ??????? MySimon

MySimon 是 Michael Yang 和 Yeogirl Yun 在１９９８年４月一起創建的。一種被稱為虛擬學習代理（ Virtual Learning Agent － VLA ）的技術由 Yeogirl Yun 開發并用于網站的學習中。

VLA 生成若干智能代理，能模仿人的采購行為，經過訓練可從任何一個購物網站上抽取信息。

代理的訓練過程是通過一個圖形界面進行的。訓練者無須是編程人員。在瀏覽網上商店的同時，系統會復制其獲得的信息。根據訓練者的操作行為和復制的信息，系統會生成能使代理運行的編碼。

第5.3.節 ????????? 小結

信息抽取技術可以發揮作用的地方有許多。不過，最成功的要數比價購物。最近兩年來，比價購物系統已經投入商用。其中比較出色的是 Jango, MySimon 和 Junglee 。

Jango 在線進行抽取，用機器學習方法學得網站結構。 MySimon 也以在線方式抽取信息，但使用的學習方法不同。非程序員通過實際上網購物，教會智能代理學習如何從網站上抽取相關的信息。

Junglee 把數據抽取出來并儲存在數據庫中，然后用數據庫作為比價系統的信息源。一種專用的語言被用來描述網站結構并生成抽取過程所需的代碼。