• 検索結果がありません。

A twophase Approach to Chinese Unknown Word Extraction: Application of Pattern Mining and Machine Learning

N/A
N/A
Protected

Academic year: 2018

シェア "A twophase Approach to Chinese Unknown Word Extraction: Application of Pattern Mining and Machine Learning"

Copied!
8
0
0

読み込み中.... (全文を見る)

全文

(1)

應用樣式探勘與機器學習方法於中文未知詞擷取之研究

楊傑程

國立中央大學資訊工程研究所

955202037@cc.ncu.edu.tw

張嘉惠

國立中央大學資訊工程研究所

chia@csie.ncu.edu.tw

摘要

中文的自然語言處理中,中文斷詞是一個極為 重要的問題。中文斷詞的領域裡,有兩個主要的問 題:歧義性及未知詞。本篇論文針對未知詞的問題 進行兩個階段的偵測與擷取。第一階段的單音節已 (未)知詞偵測,我們運用了一個 pattern mining 的方 法在語料庫中找出已知詞的偵測規則,這些規則可 以有效率的區別單一中文字是已知詞或未知詞的 一部份。第二階段的未知詞辨識,將套用未知詞的 偵測規則,再搭配文章的上下文與統計資訊,並運 用機器學習中的分類演算法與序列學習的方法進 行擷取的實驗。實驗資料來自於中研院的平衡語料 庫。結果顯示,在不使用人工型態規則輔助特定類 型的未知詞擷取下,我們的召回率能夠達到 66% 的水準。

1. 序論

近年來,中文的資訊處理逐漸獲得廣泛的重 視。然而,我們必須先解決中文的斷詞問題,才能 將一篇文章轉換成可使用的資訊。例如以下例句:

“中油加油站昨天生意興隆”,還未斷詞前,很難 以整個句子來進行與其他句子相似度的比較或處 理。經過正確的中文斷詞後,會變成以下的詞串:

“中油 加油站 昨天 生意 興隆”,我們才有 辦法做後續的檢索及應用。因此正確的辨識並區隔 出句子中的每一個中文詞,在中文的自然語言處理 上是一項很重要的課題。

中文斷詞有兩個最主要的問題 — 歧義性問 題以及未知詞問題。歧義性(ambiguity)的問題發生 在同一個中文字串,可以有不同的斷詞結果。本篇 論文主要是解決未知詞的問題,因此歧義性的問題 在 此 不 多 做 介 紹 。 所 謂 中 文 未 知 詞 (unknown word),指的是不包括於詞典或是訓練語料庫的中 文詞,可能的原因是該詞彙為一新詞彙,或是為不 知名的中文人名、外來譯名等專有名詞。由於詞典 不可能包含所有的詞彙,而斷詞又依賴於詞典進行 詞彙的辨識,因此未知詞的存在往往導致斷詞無法 完全正確。

(1) 未斷詞: 王義氣熱衷研究生命。

(2) 初步斷詞: 王 義氣 熱衷 研究 生命。 (3) 正確斷詞: 王義氣 熱衷 研究 生命。

中文斷詞常見的處理方式,是將未斷詞的文章 或句子如(1),首先經由辭典辨識,進行初步斷詞: 存在於辭典內的已知詞,能夠被正確的區隔出來; 而不存在於辭典內的詞,會被斷詞系統錯誤地斷開 成一至多個部分,如(2)的“王 義氣”(人名)。因 此,未知詞擷取的任務,就是針對錯誤切割的多個 字元部分,重新結合成一個正確的詞彙,如(3)的

“王義氣”。

如上所述,未知詞的擷取來自於數個錯誤分割 的字元重新結合。由於未知詞的種類繁多,其中有 些具有固定的型態,如中文人名,可以透過型態的 規則來擷取;有些卻沒有,必須仰賴統計資訊提供 擷取的線索。然而,直觀的依照結合的頻率,不考 量語言學知識(linguistic knowledge)的情況之下,卻 可能提供錯誤的資訊,如:兩個非未知詞字元“總 是”、“以”結合後的頻率亦很高,卻不是未知 詞;亦有可能兩個未知詞字元其結合的頻率很低, 而屬於該結合的未知詞。因此,2002 年 Chen 等人 [4]提出,假如能夠事先進行未知詞的偵測(如上頭 的“以”判斷為已知詞),就能夠避免錯誤的結合 產生。作者將未知詞問題分成兩個階段的解決方 式:第一階段,先進行單音節已(未)知詞的偵測; 第二階段的未知詞辨識,再針對被偵測到的未知詞 字元,進行未知詞的擷取。本研究將參考[4]的解 決方法,以兩階段方式處理未知詞的問題。

由於辭典容易將未知詞切割成長度較小的多 個字1,尤其是長度為 1 的單音節字元,Chen 等人 於 [1] 所做的統計提到 96%以上的未知詞組合, 經初步斷詞後至少有一個單音節字元存在。因此, 進行已知詞偵測時,會特別著重單音節字元的屬性 判斷,是屬於能夠單獨存在的已知詞,還是未知詞 的一部分。近年來學者漸漸地開始使用語料庫學習 的方式,自動的找尋偵測規則。1998 年 Chen 等人 [1] 使 用 中 央 研 究 院 的 平 衡 語 料 庫 作 為 資 料 來 源,找尋所有三個字長度以下的已知詞偵測規則, [4]亦延續[1]的作法。本篇論文採用 Huang 等人[7] 的 連 續 性 樣 式 探 勘 方 法 (continuity pattern mining),應用於相同的語料庫,有效率的找出單 音節字元屬於已知詞(未知詞)的偵測規則。

1本文使用字來描述初步斷詞後的一個詞或字元的 單位,字的長度不限定於 1,長度為 2 以上的字稱 為多音節字(詞),長度為 1 的字稱為單音節字(字 元)。字可能為已知詞,或是未知詞的一部分。

(2)

在未知詞辨識的部分(第二階段),Chen 等人[4] 針對特定類型的未知詞建立型態規則予以擷取。近 年來的研究走向,則是朝向一般性的解決方法來發 展,本文的目標亦同。我們將針對偵測到的單音節 未知詞字元,加入包括其所處的位置之上下文資 訊,並計算統計資訊(頻率、條件機率等),以及詞 性,作為擷取時的判斷依據。本篇論文使用序列學 習的直接式(Direct)與間接式(Indirect)方法,進行未 知詞的辨識。

本篇論文後續的章節內容如下:第二章將簡略 摘要出未知詞偵測與結合的相關研究。第三章敘述 整體的流程架構。第四章與第五章分別針對我們所 提出的單音節已知詞偵測、未知詞辨識的方法,做 完整的說明。第六章為實驗。最後是本篇論文的結 論與未來可以改善加強之方向。

2. 未知詞偵測與萃取的相關研究

到目前為止,未知詞的研究已經持續了十餘年 之久。未知詞種類繁多,包含人名、地名、組織名、 上述名稱縮寫,以及衍生詞、複合詞與數字型態 等。而不同類型的未知詞,有不同的樣式與規則, 因此研究學者提出相關資訊的搭配應用來尋找不 同類型的未知詞。

Chen 與 Lee [2] 偵測三種類型的專有名詞(中 文人名、外來譯名、組織名)並分類之。作者透過 不同層級的觀測內容(字元、句子、段落),運用頻 率、上下文或是字元的特性等擷取中文人名;接著 對樣式較不固定的外來譯名,觀察是否為常見的翻 譯字元以及字元順序的發音是否符合外來人名的 規則以判別之;最後,作者將組織名定義為名稱與 組織型態的組合,例如: 華碩+電腦(公司),針對左 邊的名稱字元,進行上下文的關連性、字元的獨立 性與詞性的觀察,作為組織名判斷的依據。

除了特定類型未知詞的研究,開始有學者提出 整體性的方法,擷取所有型態的未知詞。首先,透 過未知詞的偵測方法,系統能夠事先辨別出可能的 未知詞位置並給予標記。未知詞的偵測方法大略可 以分成兩種。

兩階段式的偵測與擷取

中研院陳克建博士等人於 1998~2003 年提出 了三篇未知詞研究的相關論文([1], [4], [9]),採用的 就是規則式的未知詞偵測方法,縮小可能的未知詞 範圍後,再搭配規則式的擷取方法進行未知詞擷 取。以下分別介紹三篇論文的研究。

Chen 等人 [1] 認為,經過詞典比對進行初步 斷詞之後,剩下的落單字元不是單音節已知詞,就 是未知詞的一部份。因此作者透過語料庫學習法, 找尋單音節字元屬於已知詞的樣式規則。在偵測 時,只要符合上述的樣式規則,即視為單音節已知 詞,不然則視為未知詞的一部分。

2002 年 Chen 等人 [4] 延續了上述論文的作 法,偵測出未知詞後,根據樣式較為固定的未知詞 類型建立型態規則,再運用上下文資訊,訂出 12 項統計規則予以過濾,結合成為未知詞的擷取規 則。該論文針對 1160 個未知詞(中文人名、外來譯 名與複合名詞)進行擷取,實驗結果達到 89%的準 確率與 68%的召回率。

2003 年 Ma 等人 [9]有鑒於之前的未知詞擷 取,大多只能處理特定類型的未知詞,因此撰寫了 context free grammar,其限制為: 未知詞組合中至 少要有一個以上的單音節未知詞語素。偵測到的語 素會根據統計資訊、句法資訊等,決定是否與鄰近 的語素結合,形成一個正確的未知詞。Ma 等人期 望透過這個 bottom-up merging algorithm 的一般性 方法,擷取更多類型的未知詞。實驗取自於網路上 的文章作測試,結合 [4]的型態規則與本篇的一般 性方法,結果有 75%的準確率與 57%的召回率。

規則式的未知詞處理方法,是將未知詞的問題 切割成兩階段來處理。偵測上使用語料庫學習的偵 測規則,並給予單音節字元已知或未知的標示。擷 取上搭配型態規則或是一般性規則的擷取法則找 尋未知詞。本文的做法類似於此類研究,採用兩階 段的處理方式與規則式的偵測方法,不過在擷取 上,我們只採用機器學習的方法。

序列學習方法

近年來,中文的斷詞處理愈來愈常運用機器學 習 中的 監督 式序 列學習 法(Supervised Sequential Learning)。[5]將常見的 SSL 問題之解決方法分成 兩類,第一種是直接式(direct)方法,由 sequence data 直接產生一個對應的統計模型,如 Hidden Markov Model (HMM)([6])、Conditional Random Field (CRF)([10])。該方法從已標記的語料庫學習 相關的參數估計,進行初步斷詞(詞典由部分的訓 練語料庫建立)與詞性的標記,再透過上述資訊找 尋最佳化的斷詞序列(Viterbi Algorithm)。Goh 等人 [6] 使 用 HMM 進 行 初 步 斷 詞 與 詞 性 標 記 (part-of-speech),再搭配 Support Vector Machine (SVM)做未知詞擷取,擷取的效能為 63.8%的準確 率與 58.3%的召回率。Tsai 等人[10]使用 CRF 進行 中文斷詞,並以英文、數字字元的分群與長字元的 範本比對(template matching)輔助,未知詞的召回率 最高可到達 73%。以上不難看出,統計模型式的未 知詞偵測方法並無細分偵測與擷取,而是視為同一 個階段。

第二種是間接式(Indirect)方法,能夠將監督 式序列學習的問題,轉換成監督式分類學習(亦即 判斷是否為未知詞)的問題。此類型常見的有: Sliding Window 方法與 Recurrent Sliding Windows 方法。對於直接式與間接式兩種序列學習方法,本 研究都將採納為未知詞擷取的方法。

(3)

3 系統架構

本論文的完整系統架構如下圖。首先,未斷詞 文章會經由傳統經驗法則([3])的方式以及詞典輔 助下進行初步斷詞。接著我們使用 Prowl 這個連續 性 樣 式 探 勘 (Continuity Pattern Mining) 的 工 具 ( [7] ),針對中研院的平衡語料庫(已斷詞)找尋偵測 的規則。第二階段的未知詞辨識(使用第一階段的 測試資料作為訓練資料),對偵測的未知詞字元, 結合上下文資訊與統計資訊,並應用機器學習的分 類演算法與序列學習方法來進行擷取的訓練與測 試。如圖所示,第一階段使用 8/10 語料庫訓練以 找尋偵測規則,接著對另外的 1/10 語料庫資料進 行未知詞偵測的測試,並以該資料作為第二階段的 訓練資料。兩階段總計使用 9/10 語料庫的訓練資 料,再對剩下的 1/10 語料庫作最後的未知詞擷取 之實驗,實驗效果可看出兩階段式的訓練方式,從 偵測到辨識能夠真正找尋出多少個未知詞。一旦未 知詞能夠被正確的擷取並結合,就能有效提升斷詞 的正確率。

圖.1 未知詞處理的整體系統架構圖 接下來的 4、5 兩章,分別就本文所提出的單 音節已知詞偵測與未知詞辨識兩階段的方法進行 介紹。

4 單音節已知詞偵測

一開始我們會先對未斷詞文章,經由傳統經驗 法則([3])的方式以及詞典輔助下進行初步斷詞,並 採用 8/10 中研院平衡語料庫(已斷詞且標示詞性) 當做訓練資料,找尋偵測規則。本文以單一個中文 字元或標點符號(或對應的詞性)為單位,產生三個 字元以下所有組合的樣式。不同於[4]找尋所有長 度 3 以下樣式的作法,我們使用 Prowl 這個連續性 樣式探勘的工具,有效率地對訓練資料產生可能的 樣式(pattern)並計算這些樣式在訓練資料中出現的 頻率,再根據這些樣式及頻率產生偵測用的規則。

探勘單音節已知詞 偵測規則 初步斷詞

單音節字元偵測 未斷詞句子

套用規則

探勘的工具(Prowl) 詞典

訓練資料語料庫 斷詞後的字串

斷詞後的字串附上偵測的標記,形成第二階段的訓練資料 圖.2 單音節已知詞偵測的系統架構圖 Huang 等人於 2004 年[7]採用的樣式探勘演算 法 -- Prowl,是找尋連續性樣式的演算法,與一般 的序列樣式(sequential pattern)定義不同。序列樣式 允許樣式內夾雜其他項目(noise),只要樣式要求的 項目有出現並符合順序即可。不過,連續性樣式嚴 格 要 求 樣 式 內 的 項 目 (item) 必 須 是 連 續 出 現 (contiguous)且完全符合的。舉例來說:若有一個連 續性樣式為<打 * 球>,則<(打 棒 球)>視為符合 (support), <(打 躲 避 球)>就不符。運用連續性 樣式探勘方法能夠準確並有效率的找尋所有符合 樣式的規則。Prowl 首先找尋長度 1 的頻繁樣式 (1-frequent pattern),假如有兩個長度 1 的頻繁樣式 相鄰,系統會試著將前後兩個樣式結合成一個長度 2 樣式,假如結合後的長度 2 樣式亦為頻繁的,我 們就產生此長度 2 的頻繁樣式(2-frequent pattern)。 依相同原則有條件的延伸至長度更大的樣式。

找尋樣式(pattern)的同時,也會得到這些樣式 在一整份訓練資料中出現的次數,以及這些樣式中 某個字屬於已知詞的次數為何。每一個樣式都會產 生相對應的規則。舉例來說,“{義} 氣”為一條規 則,其意義為:在文章中連續出現義、氣這二個字 的情況下,義這個字被包含在已知詞裡。透過以下 的計算:正確率=A1=P(義 被包含在已知詞 | 義 氣),我們可以得知此規則的正確率為多少。

(4) 王義氣 非常 義氣。

如上述(4)這一句,“義氣”存在於字典裡, 但“王義氣”不存在,因此在這裡正確率=A1=0.5。 正確率為我們篩選規則的門檻。假設在測試的時候 設門檻值為 0.4,則義會被標為已知: 義(),反之, 若門檻值設為 0.6,則義會被標為未知,即 :義(?)。 上述的規則並沒有使用到詞性(POS),同理, 加上詞性之後組合更多,產生的規則也更多。本文 找尋樣式的長度雖然與[4]相同,不過[4]於長度 3 的樣式中只尋找偵測字元搭配上下文詞性的規則 (未搭配字元),且偵測字元(大括號內的字元)僅限 制於前述詞或後述詞的位置。我們在尋找長度 3 樣 式中,亦包含了偵測字元出現於置中位置的樣式規 則,如表.1 的第二筆規則。表.1 為含有“王(Na) 義 氣(VH)”這兩個詞的訓練資料所產生其中一部分 的規則與對應準確率:

(4)

表. 1 已知詞偵測規則與對應準確率

規則 準確率

{王(Na)} 義(VH) 氣 0.93 王(Na) {義(VH)} 氣 0.92 王(Na) 義(VH) {氣} 0.79

有了訓練出來的偵測規則以後,我們會把未 斷詞的文章當做測試資料,先經過傳統的經驗法則 斷詞,這種斷詞法容易把未知詞拆成多個落單的中 文字元,因此,經驗法則斷詞後的測試資料出現單 一個中文字有三種情形 — 1.多音節未知詞的一部 份、2.單音節未知詞以及 3.單音節已知詞,我們訓 練出來的規則就是要去預測這些單一的中文字,找 出不屬於單音節已知詞的中文字。

在預測方面,我們設定一個門檻值來篩選所有 的規則,然後經由這些篩選過的規則來預測每個單 一的中文字為已知或未知,如果是多音節的詞,我 們會直接標示為已知詞,不管其是否為未知詞的一 部分。標示過後的資料將成為第二階段的訓練資 料。

5 未知詞擷取

第二階段(未知詞擷取)的任務,就是運用相關 資訊,將偵測到的未知詞擷取出來。Chen 等人 [4] 提出了型態規則 (Morphological Rule) 和統計規 則 (Statistical Rule) 的運用,以規則的模式作為未 知詞擷取的判斷依據。本篇論文並無針對任何未知 詞種類訂定型態規則,純粹採用上下文、POS 詞性 以及統計資訊,並搭配機器學習中分類方法與序列 學習的方法,將訓練資料轉換成一筆筆可進行分類 (是否為未知詞)的資料格式,以供模型使用。

下圖為第二階段(未知詞擷取)的流程圖。

圖.3 未知詞擷取的系統架構圖(包含實驗步驟)

第 二 階 段 的 訓 練 資 料 包 含 下 列 的 資 訊 : 字 元、POS 詞性(part-of-speech)、字元的型態屬性等。 下表採自第二階段的訓練資料某篇文章中的句子 (初步斷詞),包含每個字元的相關資訊:

表. 2 第二階段訓練資料(某句)

本文採用 TnT POS tagger 標記句子中每個字 的詞性,POS 詞性總共含有 55 種詞性,包括名詞 (Na、Nb…)、動詞(VC、VH…)、形容詞與標點符 號等,我們會另外產生一個新的種類以供 missing value 使用。

另外,除了上一章所提到單音節字元的兩種標 記之外,其他的字根據詞長、詞性等特性,另有四 種標記。我們稱這一類型的標記為字的型態屬性。 型態屬性有下列六種:

ms ( ),表示單音節已知詞,例如: 你、我、他。 ms(?),表示單音節的未知詞一部分,如(3)~(5) ds( ),為雙音節已知詞,例如: 學校、電腦。 ps( ),為多音節 (詞長>2) 已知詞,例如: 多媒體。 dot( ),為標點符號,例如: 逗點“,”、括號“(”。 none2,當該字元不具備上述資訊時(missing value)。

表.2 的 3 種相關資訊,將在接下來的機器學習 方法中運用。

機器學習

本文使用機器學習中的分類演算法與序列學 習方法,作為未知詞擷取的訓練與測試之用。如第 二章所提,序列學習方法分為兩種,我們將使用間 接式(indirect)方法結合分類演算法 SVM ( Support Vector Machine )作為第一種方法;另外我們亦使用 HMM ( Hidden Markov Model )作為直接式(direct) 方法的應用。兩者的基本觀念與運用細節,介紹如 下。

SVM (間接式(indirect)方法)

SVM 是一種超平面 (hyper-plane)模型,找到 一個超平面,能將座標上的所有點分成兩個區間, 而且能夠切割得愈明顯愈好(兩個區間距離超平面 最近的點,與超平面的距離能夠愈大愈好(maximal margin)。我們運用 SVM 來做二項分類(未知詞的結 合與否)。

2 如本節表.3 資料(1),prefix 的位置。

(1) (2) (3) (4) (5) …

字元 四年 甲班 王 姿 分

POS Nd Na Nb Na Vc … 型 態

屬性

ds( ) ds( ) ms(?) ms(?) ms(?) .

(5)

在 SVM 的使用上,我們採取序列學習中的間 接式(indirect)方法,將中文文章裡未知詞辨識的問 題,轉換成交由 SVM 進行分類的問題。其中一種 方法為 Sliding Window 方法([5]),該方法將序列資 料切割成一個個固定大小的視窗,前一個視窗往下 移動一個字元形成下一個視窗。經過這個步驟, SVM 就能夠針對每個視窗的資料,進行分類的預 測。

我們定義了三種不同長度(n)的未知詞之模型 (model ),分別是 2-gram SVM model、3-gram SVM model 以及 4-gram SVM model。定義的標準來自於 未知詞組合所包含的字數。每一筆 n-gram Sliding Window 的資料,除了 n-gram 資料外,尚加入上下 文(前後字元)的資訊,以提升未知詞擷取的準確 度。下面的例句出自於第二階段的訓練資料: 運動會( ) ‧( ) 四年( ) 甲班( ) 王(?) 姿(?) 分(?) 。( ) 本校( ) 為( ) 響( ) 應( )…. 我們以 3-gram Sliding Window 舉例,由上述例句所 產生的資料格式如下表:

表. 3 3-gram Sliding Window 資料

Prefix 3-gram Suffix 判斷 (1) Space 運動會

( )

‧ ( )

四年 ( )

甲班 ( )

過濾

(2) 運動會 ( )

‧ ( )

四年 ( )

甲班 ( )

王 (?)

過濾

(3) ( )

四年 ( )

甲班 ( )

王 (?)

姿 (?)

負面

(4) 四年 ( )

甲班 ( )

王 (?)

姿 (?)

分 (?)

負面

(5) 甲班 ( )

王 (?)

姿 (?)

分 (?)

。 ( )

正面

(6) 王 (?)

姿 (?)

分 (?)

。 ( )

本校 ( )

過濾

.. .. .. .. .. .. ..

由上表,可以看出每個視窗的資料,往右移動 一個字元後可以得到下一個視窗的資料。

資料(1)的前述詞(Prefix),為一系統產生值。 由於“運動會”是文章的開頭,前面無其他字元,系 統會自動產生一個值,避免之後機器學習的模型遇 到 missing value 的問題,POS 詞性與型態屬性亦另 外產生一類別(none)。未知詞的組合中,必須要包 含至少一個型態屬性為單音節未知詞(ms(?))的字 元,表.3 例子(1)、(2)不符,不產生該筆資料至 SVM 的訓練模型內。另外,除了外來譯名中可能包含

“‧”這個標點符號外,其他類型的未知詞皆不會 包含標點符號。因此,我們亦會過濾 n-gram 含有

“‧”以外其他標點符號的該筆資料,如表.3 (6), 最後,表.3(5)為 3-gram SVM model 的正面(Positive) 資料,表示該 3-gram 結合後隸屬於一正確詞彙(人 名)的肯定例子。而範例(3)、(4)雖然符合型態屬性 與不包含“‧”以外的標點符號規定,不過該 3-gram 不為結合目標,因此屬於負面資料。訓練的 分類演算法模型將會納入不過濾的正負面資料。

統計資訊

我們使用 n-gram 字元組合的格式,計算下列 的統計資訊。以 4-gram 為例子,每一筆資料組成 為 4-gram 組合加上前述詞 prefix 與後述詞 suffix 共六個字元。如下述的表格:

Prefix 0

1 2 3 4 Suffix 5 我們以 index 0~5 分別表示整筆資料中,prefix 到 suffix 的這六個字元,統計下列的資料: 1. 4-gram 頻率 (1+2+3+4)

2. Probability (prefix | 4-gram) 3. Probability (suffix | 4-gram) 4. Probability (1 | 2+3+4 ) 5. Probability (4 | 1+2+3 )

6. Probability (#POS (prefix) / #POS (prefix in training positive)):prefix 之 POS 詞性在訓練中 的正面資料 prefix 之所有 POS 詞性的比重。 7. Probability (#POS (suffix) / #POS (suffix in

training positive)):suffix 之 POS 詞性在訓練中 的正面資料 suffix 之所有 POS 詞性的比重。

我們將納入以上的統計資訊於 SVM 的訓練/ 測試模型中,以輔助 SVM 判斷未知詞結合的能力。

HMM (直接式(direct)方法)

HMM 是一種以統計為基礎的機率模型演算 法,主要是透過可見的觀測符號,來預測不可見的 狀態為何。本篇論文使用 HMM 作為序列學習方法 中直接式(direct)方法的應用。

HMM 主要的參數為觀測符號與狀態符號。本 文使用的觀測符號有三種資料,第一種為字元本 身,第二種為字元的型態屬性,第三種為字元的 POS 詞性,觀測符號可以由上述三種資料搭配組合 而成。狀態符號為字元的位置標記,包含有位於詞 的開始 B (Begin)、詞的中間 I (Intermediate)、詞的 結束 E (End)、獨立詞 S (Singular)四種([8])。未知 詞會有 BI*E(*表示 0~2 個)的標示。HMM 並未使 用本文計算的統計資訊,原因為該資訊是建構在 n-gram 的運用上,HMM 只看單一時態的觀測符號。

(6)

6 實驗

6.1 未知詞偵測

第一階段的實驗,我們採用 8/10 的已斷 詞平衡語料庫(version 3.1 約 575 萬個字)當做訓練 資料,並隨機選約 1/10 的 未斷詞平衡語料庫 (不 包含在訓練資料中)當做測試資料,篩選規則的方 法使用正確率(Accuracy)當作門檻值。

在召回率(Recall)的算法上,我們只考慮 初步斷詞後可以被拆成至少有一個 ms(?)的未知 詞。下面是召回率(Recall)與準確率(Precision)的公 式。

Recall = 找到的未知詞個數 / 未知詞個數 Precision= 正確標示(?)的個數 / 標示(?)的個數 F-measure= 2PR/(P+R)

實 驗 結 果 如 表 .2 所 示 , 最 後 一 個 欄 位 的 F-measure 是 Chen 等人於 1998 年[1] 那一篇的實 驗結果,最高到 77%而我們可以提升到 79.5%。

表.2 第一階段的實驗結果

6.2 未知詞擷取

第二階段的實驗,我們從剩下的 1/10 平 衡語料庫中取部分當作測試資料。我們將使用第 5 章所介紹的兩種機器學習方法來進行未知詞擷取 的實驗。

6.2.1 SVM (間接式(indirect)方法)

首先,在 SVM 的部份,我們採用的是台 灣大學林智仁教授所開發出來的 LibSVM 工具。為 了符合 LibSVM 的資料格式,我們將所有的資料轉 成數值形式,並且將對應的資料依照順序排列,每 一筆 n-gram 模型,我們將列出從前述詞到後述詞 總共 n+2 個字元的 POS 詞性與型態屬性,接著再 列出之前所介紹的七種統計資訊,依此順序形成一 筆 n-gram 的 SVM 訓練/測試資料。

n-gram 過濾

接下來我們尚要解決,當包含同一個字的不同

組 合 皆 判 定 要 結 合 時 , 改 採 用 何 種 結 合 方 式 (overlap),與採用何種 n-gram 模型(conflict)來結 合。舉例來說,“律師 班 奈 特”這個字串中,有 兩種結合方式的可能(律師+班 或 班+奈+特)。 Chen 等人[4]倚靠下列權重的比較: 結合後的組合 之出現頻率*結合的長度 來決定。

本篇論文設計了三種不同長度的 n-gram 模 型。因此,我們將未知詞結合的選擇分成兩種過濾 方式: 首先,對於同一種 n-gram 的結合方式先進 行 過 濾 (overlap) , 我 們 使 用 下 列 條 件 機 率 : P(combine | overlap),也就是重複字元(overlap)傾向 與前後的字元一起出現的機率比較。

接著,對不同長度的 n-gram 之選擇(conflict), 直觀的判斷方式是比較不同的 n-gram 在文件中出 現的頻率。不過 J. Y. Nie 等人 [10]提到,不同長度 的 n-gram 發生重疊(overlapping)時,較長的 n-gram 頻率亦會被較短的 n-gram 計算進去,例如:“醫 學 院”出現時,不僅增加該 3-gram 的頻率,“醫 學” 與“學 院”等較短的 2-gram 頻率也被錯誤的增 加 。 為 了 修 正 這 個 錯 誤 , Nie 等 人 [10] 提 出 : freq(X)= freq(X)-freq(Y),假如 n-gram X 被包含於 較長的 n-gram Y 之中。我們參考這個修正的頻率 以挑選不同 n-gram 間的結合方式。假如修正後的 頻率仍無法分出勝負,我們會使用 n-gram 組合的 前述詞與後述詞之型態屬性進一步的判斷。舉例來 說,“學生 王 小 明”此字串中,2-gram(小+明)與 3-gram(王+小+明)都判定為結合,由於兩者的後述 詞相同,我們比較兩種 n-gram 組合的前述詞之型 態屬性,2-gram 為 ms(?)-單音節未知詞(王),3-gram 為 ds()-雙音節已知詞(學生),因為單音節未知詞比 雙音節已知詞更容易包含於未知詞組合中,換句話 說,亦比較不應該出現於前述詞的位置。因此這個 範例中,我們選擇 3-gram 結合(前述詞出現雙音節 已知詞較合理)。

以下為我們使用 SVM 的測試結果。由於未知 詞問題的正面資料數量遠小於負面資料數量,因此 資料有不均衡問題。[11]介紹了數種處理該問題的 解決方法。在此我們使用 under-sampling 的方式, 對負面資料進行採樣(sampling)。下表的第一欄, 只使用一種 n-gram,表示只擷取長度為 n 的未知詞 (overlap 過濾)。Total 表示擷取長度為 2~4 的未知 詞(overlap 與 conflict 過濾)。

表.3 第二階段的實驗結果(SVM)

Threshold Precision Recall F-measure

(ours)

F-measure (AS) 0.7 0.932 0.431 0.589 0.713 0.8 0.901 0.529 0.666 0.752 0.9 0.834 0.715 0.770 0.770 0.95 0.764 0.829 0.795 0.766 0.98 0.686 0.879 0.770 0.744

n-gram Precision Recall F1-score 4-gram 39.2% 51.3% 0.444 3-gram 66.9% 75.7% 0.71 2-gram 69.2% 69.2% 0.692 Total 68.6% 66% 0.674

(7)

如上所述,我們採用 under-sampling 的方式對 負 面 資 料 進 行 採 樣 , 採 樣 的 方 式 是 隨 機 挑 選 (random)。為了避免結果不準確,我們總共採樣三 次,也就是產生三次的訓練模型,三次訓練後的測 試結果再使用 ensemble method 的投票機制([11]), 產生最後的結果如表.3。

從表.3 結果進一步分析,3-gram 的表現最 好。此項結果並不意外,3-gram 未知詞包含大多數 的中文人名,其固定型態的特徵通常會有較好的表 現。4-gram 的表現最差,仔細觀察語料庫的 4-gram 未知詞,可以發現比例最高的是 4 字成語、複合詞 等型態較不固定的未知詞,因而影響擷取的水準。

另一方面,未知詞的整體召回率達到了近七成 的效果,考量到我們實驗的未知詞並未設限,同樣 的實驗方式,Ma 與 Chen 在 2003 年[9]整體的召回 率為 57%,相比之下,我們的召回率表現得較為出 色。Chen 等人 [4]只考慮中文人名、外來音譯人名 與複合名詞的擷取,我們亦特別對這三種類型未知 詞的擷取表現作比較,召回率為 66.1%,小幅輸給 他們的 68%。儘管我們的準確率差了一截,不過我 們並未針對上述類型產生人工的規則進行較精確 的擷取,其效果仍有不錯的水準。

6.2.2 HMM (直接式(direct)方法)

使用 HMM 作為未知詞擷取的部份,我們只考 慮字元本身、型態屬性與 POS 詞性標記做為觀測 符號,分別以 H、A 與 P 表示如下表。HMM 的未 知詞擷取系統,並未如 SVM 一般,產生多種模型, 訓練與測試階段也並未加入統計資訊。表.4 為 HMM 的未知詞擷取結果。其中以型態屬性搭配 POS 詞性的觀測符號組合表現最佳,該結果也驗證 了我們在 SVM(間接式方法)的模型內,使用字元的 型態屬性與 POS 詞性以取代字元本身的選擇是正 確的。

表.4 第二階段的實驗結果(HMM)

觀測符號

組合

Precision Recall F-score

A 0.53 0.208 0.299 H=HAP 0.43 0.296 0.351 AP 0.516 0.343 0.412

序列學習的結果分析

本文在實驗時測試了兩種序列學習方法,分別 是 indirect 方法與 direct 方法。其中 indirect 方法使 用 Sliding Window 方法搭配 SVM 分類模型,direct 方法則使用 HMM 統計模型。實驗結果顯示,使用 較多資訊的 indirect 方法效果比 direct 方法出色。 表現的差異部分可歸因於兩者使用的資訊量不

同,而且 indirect 方法使用了 under-sampling 方法 以解決資料不均衡問題,的確提升了 indirect 方法 的表現。

7. 結論及未來改進的方向

本篇論文研究中文未知詞的問題,並分成兩個 階段來解決。第一階段(單音節已知詞偵測),我們 使用了連續性樣式探勘(continuity pattern mining) 方法有效率地找尋單音節已知詞的偵測規則,分辨 單音節字元的屬性。此方法比起一般的序列樣式探 勘(sequential pattern mining),在節省成本與效能的 控制上,得到改善。找尋未知詞的偵測規則,有助 於後續未知詞擷取的效率。

第二階段(未知詞辨識),對於偵測到的未知詞 語素,我們記錄了相關的自然語言資訊與上下文資 訊,並進行若干統計資訊的計算。我們運用機器學 習的分類模型與序列學習的方法,辨識並結合出正 確的未知詞。在不依靠任何的型態規則或統計規 則,亦不限制特定類型的未知詞擷取之情況下,整 體召回率(Recall)達到 66%,準確率(Precision)亦 有 68.6%的水準。相關研究指出,搭配其他的資訊 (如:[10]使用英文、數字字元的分群與長字元的 範本比對來幫助未知詞的擷取)與某些特製的規則 (如:[4]使用中文人名的型態規則),都有改善準 確率的效果。未來的方向可考慮搭配規則的使用, 提升準確率不足之處。

參考文獻

[1]K. J. Chen and M. H. Bai, “Unknown Word Detection for Chinese by a Corpus-based Learning Method”. International Journal of Computational linguistics and Chinese Language Processing, Vol.3, #1, 1998, pp.27-44.

[2] H. H. Chen andJ. C. Lee, “Identification and Classification of Proper Namesin Chinese Texts”. In Proceedings of the 16th conference on

Computational linguistics - Volume 1, 1996. [3] K. J. Chen and S. H. Liu,“Word Identification for

Mandarin Chinese Sentences”, In Proceedings of COLING 1992, pages 101-105.

[4]K. J. Chen and W. Y. Ma, “Unknown Word Extraction for Chinese Documents”, In Proceedings of COLING 2002, pages 169-175. [5]T. G. Dietterich, “Machine Learning for

Sequential Data: A Review”. In Proceedings of Structural, Syntactic, and Statistical Pattern Recognition (SSPR), 2002, pages 15-30.

[6] C. L. Goh, M. Asahara, and Y. Matsumoto,

“Machine Learning-based Methods to Chinese Unknown Word Detection and POS Tag Guessing”, Journal of Chinese Language and Computing 16 (4), 2006.

(8)

[7]K. Y. Huang, C. H. Chang, and K. Z. Lin, “Prowl: An Efficient Frequent Continuity Mining Algorithm on Event Sequences”, In Proceedings of 6th International Conference on Data Warehousing and Knowledge Discovery (DaWak'04), volume 3181 of Lecture Notes in Computer Science, 2004, pages 351-360. [8] T. Kudo and Y. Matsumoto, “Chunking with

Support Vector Machines”, In Second meeting of the North American Chapter of the Association for Computational Linguistics on Language

technologies 2001.

[9] W. Y. Ma and K. J. Chen, “A Bottom-up Merging Algorithm for Chinese Unknown Word Extraction”, In Proceedings of Second SIGHAN Workshop on Chinese Language Processing, pp. 31-38, 2003.

[10] J. Y. Nie, M-L. Hannan, and W. Jin, “Unknown Word Detection and Segmentation of Chinese using Statistical and heuristic Knowledge”. In Communications of COLIPS, 1995

[11] P. N. Tan, M. Steinbach, and V. Kumar, 2006. Introduction to Data Mining.

[12] R. T-H. Tsai, H. J. Dai, H. C. Hung, and C. L. Sung, “Chinese Word Segmentation with Minimal Linguistic Knowledge: An Improved Conditional Random Fields Coupled with Character Clustering and Automatically Discovered Template Matching”. IEEE, 2006.

参照

関連したドキュメント

These results indicate an interferenceeffectof visual context in picture detection and a facilitation effect of semanticcontext in word detection.. However,Experiment2 using

This paper aims to study the history of Chinese educational migration and state policies which influence overseas Chinese students, to explore the mobility tendency of

2022 年9月 30 日(金)~10 月 31 日(月)の期間で東京・下北沢で開催される「下北沢カレーフェステ ィバル 2022」とのコラボ企画「MANKAI

We study a Neumann boundary-value problem on the half line for a second order equation, in which the nonlinearity depends on the (unknown) Dirichlet boundary data of the solution..

In this paper, we have proposed a modified Tikhonov regularization method to identify an unknown source term and unknown initial condition in a class of inverse boundary value

Let T (E) be the set of switches in E which are taken or touched by the jump line of E. In the example of Fig. This allows us to speak of chains and antichains of switches.. An

ここで, C ijkl は弾性定数テンソルと呼ばれるものであり,以下の対称性を持つ.... (20)

Tone sandhi rule for pattern substitution in Suzhou Chinese: Verification using words beginning with a Ru syllable Masahiko MASUDA Kyushu University It is well known that in Wu