中譯：進階領域獨立的線性文件分段 (Advances in domain independent linear text segmentation)

這依然是一篇逐字翻譯的文章，需要注意的是第四節「評估」我沒有完全翻完，因為我已經在第三節「演算法」找到我想看的東西了，而第四節主要就有點老王賣瓜的比較與其他分段方法的優越性，因此我只翻譯了第四節的結論，有興趣的讀者可以閱讀原文。本文分段完全依照原文所訂，對照起來應該相當容易，末段「心得」為我的見解，也一併與你分享。當然，翻譯的目的依然是讓中文為母語的讀者能快速掌握這些知識，以利後進學者的研究。

 
▲研究苦悶可以到郊外走走，看見藍天白雲和蔚藍的大海，必能使人心曠神怡(圖為筆者6:40 在墾丁南灣飯店所攝)

原文：Choi, Freddy Y. Y. 2000. Advances in domain independent linear text segmentation. In Proceedings of the Sixth Applied Natural Language Conference (ANLP-00) and the First Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-00), pages 26–33.

摘要
本文描述一個線性文件分段的方法，比Reyner 在1998年提出的state-of-the-art 精準兩倍、快七倍。我們使用文內排名(rank in the local context)取代跨句相似度(Inter-sentence similarity)；使用分裂群集法(divisive clustering)偵測邊界的位置。

一、介紹
一般的長篇文件通常都會包含多個主題或相同主題的不同觀點，線性文件分段的宗旨是探索文件的主題邊界。資訊檢索(information retrieval)、摘要(summarization)、文件理解(text understanding)、回指解析(anaphora resolution)、語言塑模(language modelling)與改進視障的文件導航都會使用到這個程序。

本文聚焦在與領域無關的書面文件分段方法，我們提出了一個基於Reynar 先前研究的新演算法。最大的區別在相似度矩陣(similarity matrix)，我們使用排名體系(ranking scheme)與餘弦相似度法(similarity measure)。我們希望短文件段落的相似度在統計上是顯著的，使我們在群集時只需依照它們的順序或排名。

二、背景
既有的研究屬於詞彙性銜接(lexical cohesion)法或多來源法(multi-source methods)這一兩個類別(Yaari, 1997)。研究的先驅是1976年的Halliday 與Hasan，他們提出有相似字彙的文件段落可能是凝聚的主題段落(coherent topic segment)的部分，實作偵測凝聚(coherent)的方法有字根(word stem)重複、內容向量(context vectors)、實體重複(entity repetition)、語義相似度(semantic similarity)、文字距離模型(word distance model) 與文字頻率模型(word frequency model)等；尋找主題邊界的方法包含滑動視窗(sliding window)詞彙鏈(lexical chains)、動態程式規劃(dynamic programming)、叢集聚合(agglomerative clustering) 與分裂群集(Reynar, 1994)。為了加強資訊檢索，在群集中的書面文件分段通常使用詞彙性銜接法。

多來源法結合詞彙性銜接與其他主題改變的指標，例如提示語(cue phrases)、韻律特徵(prosodic features)、參照(reference)、語法或詞彙吸引力、使用決策樹與機率模型等。這個領域的研究由「主題偵測追蹤(TDT)」發起，聚焦在錄製展現格式與規律的提示可以精準切割的口語文件與廣播新聞事件的分段。

三、演算法
我們的分段演算法以一串標計化語句作為輸入，使用1994年Grefenstette 與Tapanainen 提出的標記器、句子界限消歧義演算法或Reynar 等在1997年的EAGLE 可以轉換文字文件成為可接受的輸入格式。

(一) 相似度法(Similarity measure)
使用簡單的正規表達式與停用字移除每句中的標點符號非資訊文字(uninformative words)，接著對剩下的標記(token)以1980年Porter 提出的詞幹(stemming)演算法取得字根。為每句建立字根頻率字典(dictionary of word stem frequencies)，代表頻率計數的向量。

令f_i,j代表文字j在句子i中的頻率，句子x 與y 的相似度使用餘弦法計算如(等式1)。對每句使用這樣的方法產生相似度矩陣。

(等式1)

相似度矩陣1的例子如(圖1)，明亮部分代表相似度值高。左下角與右上角分別為第一句與最後一句的自我相似度。值得注意的是矩陣是沿著對角線對稱的且包含明亮的方型區域，這些區域代表凝聚的文件段落。

▲圖1：相似度矩陣1的例子

(二) 排名(Ranking)
對短篇的文件段落，sim(x, y)的絕對值是不可靠的。除非文件區段(分母)很大，因為額外的常見字(分子)會造成相似度sim(x, y)不成比例的增加。由於在一般的情況下，文件段落每個區段小於100 個資訊性的標記，因此只能使用公制(metric)來估計句子間相似度相似度的順序，例如a 比c 相似b。

此外，語言使用變化貫串整份文件。舉例而言，概觀的段落比特定主題的段落凝聚度低。因此，直接比較相似度矩陣不同區域的相似度值並不恰當。

在非參數統計分析中，當值性的行為相似但絕對量不可靠時，我們比較資料集的排名。在此展示一個改編自1992年O’Neil 與Denos 提出的排名體系。

在相似度矩陣以本地區域內(local region)的排名取代每個值，排名是鄰近元素中相似度較低的數值。以下展示一個使用3 × 3 排名遮罩與輸出範圍{0, 8}的圖片排名(image ranking)的例子(圖2)。在文件分段的實務上，我們使用11×11 的排名遮罩。為了避免正規化問題(考慮到排名遮罩超過圖片的情況)，輸出以r 率(等式2)表示。

▲圖2：圖片排名操作的例子。

(等式2)

為了展現圖片排名的效果，程序將套用(圖1)的矩陣以產生(圖3)，值得注意的是我們使圖片的對比更加明顯。(圖4)展現我們的排名體系中更不易察覺的效果。r(x)是f(x) 的排名(使用1 × 11 的遮罩)、是個有衰退平均數(decaying mean)、震幅和頻率的正弦波(等式3)。

▲圖3：排名後圖1的矩陣

(等式3)

▲圖4：我們的排名體系中更不易察覺的效果

(三) 群集(Clustering)
最後階段找出主題界線的位置，使用Reynar 的最大化演算法(maximisation algorithm)。文件段落由兩個句子i 與j 所定義(包含)，它沿著排名矩陣的對角線以一個方形的區域表示。設s_i,j 代表段落中排名數值的總和，內部的區域是a_i,j = (j – i + 1)²。B = {b₁, …, b_m} 是m個凝聚文件段落的清單。s_k 與a_k 指的是B 中段落k 的排名和區域的總和。D 是B 內部的密度(等式4)。

(等式4)

為了初始化程序，整個文件被放在B 中視為一個凝聚的文件段落。每個處理的步驟切割B 中的一個段落，切割點(split point)使D 達到最大值，是潛在的邊界。(圖5)展示實施的例子。

▲圖5：分裂群集(divisive clustering)演算法的實施例子

段落的數量m 是自動產生的，D⁽ⁿ⁾是n 個段落的內部密集度，斜率(gradient)是δD⁽ⁿ⁾ = D⁽ⁿ⁾ - D^(n-1)。當文件有b 個潛在的界限，則分裂群集產生{D⁽¹⁾,…, D^(b+1)} 與{δD⁽²⁾,…, δD^(b+1)} 的b 個步驟(圖6、圖7)。在δD 中極大的化簡促使獲得最佳群集(optimal clustering)，見(圖7)n = 10 時。令μ 代表δD⁽ⁿ⁾的平均數、v 代表變異數，n ∈ {2, …, b + 1}。套用δD的門檻值μ + c × √̅v 得到m (實務中c = 1.2 表現較好)。

▲圖6：所有層級段落的內部密度

▲圖7：使用斜率找到最佳的段落

(四) 速度優化
每個階段的執行時間由s_k的計算過程所支配。由於s_{i, j}是常數，我們的演算法藉由先計算所有的值來改善效能。程序從主對角線(main diagonal)開始沿著對角線走向角落求值，這樣的方法複雜度big O 為3/2n²。令r_{i, j}參考排名矩陣R 的排名值與排名矩陣的加總S。若R 為n × n ，使用三個步驟計算S (等式5)。(圖8)展示程序使用(圖5)排名矩陣的計算結果。

(等式5)

▲圖8：透過計算s_{i, j}促進效能

四、評估 (按：由於評估分成六個步驟，有點冗長，故直接以評估的總結帶過)
實驗結果(表8)展示我們的C99 演算法比既有的演算法精確，精確性高兩倍且速度快七倍(C99_(b)與R98比較)。如果不管段落的精確性，H94是效能最佳的演算法(線性)，C99、K98 與R98 是多項式時間的演算法。我們的結果透過t 檢定與KS 檢定證實其重要性

▲表8：我們實驗結果的摘要

五、結論與未來工作
分段的演算法有兩個關鍵的元素，群集策略與相似度方法。我們的結果展示分裂群集(R98)在找出主題界限上，比滑動視窗與詞彙鏈(K98)更為精確。

驗證四個相似度方法後，餘弦係數(cosine cofficient)(R98_{(s, cos)})與點密集度(dot density)法(R98_{(m, dot)})得到相似的結果。我們基於語義(semantic)方法(R98_{(m, sa)})的促動擴散(spread activation)理論改善精確度。這樣確定即使Kozima 的實作計算成本高，他可以產出較精確的分段結果。

最大的改善是由於我們線性了餘弦係數的排名體系。實驗顯示當資料不足時，餘弦法的值性行為比真實的數值可靠。

即使我們的評量體系對這個比較性研究而言是充足的，但未來的研究需要更大範圍的、任務獨立的基準點(benchmark)。使用TDT文集(corpus)比較C99與1999年Beeferman 提出的多來源法(multi-source method)一定很有趣。我們也想要開發一個線性時間與多來源版本的演算法。

心得
話說剛剛念一念就睡著了，在夢裡我跟亞霖討論最近的研究，聽到他也在做主題分段，高興了一下，醒來猜發現只是一場夢。不過很開心得地方是在夢裡有討論出一點心得，看來多討論對研究還是有幫助的，不要老是跟自己meeting 了。

基本上這篇文章內容很紮實，看完很有收穫。但是從我的理解，本文主要的貢獻是提升的文件分段的效率，在精準度的突破著墨較少，也是較為可惜的地方。本文使用句子的相似度製作相似度矩陣，從矩陣中切割出凝聚力高的句子，作為分段的參考。而句子的相似度是將單字回歸到字根，再將每個字視為向量，計算兩句間的夾角值而得。所以簡言之，仍建立在一個很基本的假設 ─ 討論相同主題的文句，會使用相近的詞彙。只是文中作者也說，會因為在文章中的位置，有不同的寫作風格，例如總結的段落講的內容欠缺凝聚力，而影響的計算結果的準確。因此作者採用相對相似度的「排名」，取代絕對相似度的「分數」。

我之前提過，一個好的作者會盡量避免使用的文辭重複，但若仔細觀察人們的習慣，好的作者也會刻意塑造文辭的重複，這也許是個所謂的提示語(cue phrases)或韻律特徵(prosodic features)。我們回想一下，著名的美國民權運動領袖馬丁路德金恩(Martin Luther King, Jr.)的演說《我有一個夢》：

由於全文太長了，我就不再贅述，有興趣練習聽力的人可以到這個網站搭配文字稿，沒興趣的人也可以看中文翻譯。聰明的你應該在超聰明的我帶領之下發現，重要的句子在文章中會不斷的重複。重複的構句往往表達出文章的核心概念，而且架出了整篇文章的框架。這邊「重複」在我的歸納下可以分成幾種：

• 完全重複：例如I have a dream，通常為文件段落的切割，下一句通常是關鍵；可以將每個完全重複的下一句結合濃縮成單一主題。
• 排比重複：是最常見的重複形式，分成單句與跨句。單句內的排比往往包含表達重要概念的文句，例如廣闊的土地，勤勞的人民，悠久的歷史，這就是我們中華民族。這樣這整句是文件的關鍵；而跨句的排比，例如資訊系統與組織：blah~~~~~~~~。資訊系統與管理：blah~~~~~~~~~~~。很多作者使用這種作法架構出文件的主軸，可以作為主題的分界點。
• 對仗重複：與排比重複類似，基本上就是兩句詞性相同的句子。若這兩句連在一起，通常意義不大(可能為諺語或舉例)，但若間格出現時，如同跨句排比，會是兩個主題的分割點。
• 詞性重複：例如資訊系統可以蒐集、處理、儲存以及散佈資訊，其中對「資訊」這個概念大量的使用了動詞來修飾他，通常這種句子在文中具有相當高的關鍵性。
• 其他重複：此外還有主詞、動詞的重複，這種重複的權重較低，但是使用重複的句子通常較為重要。

以上是我粗淺的使用經驗法則的分類，沒有看過相關的研究(將重複應用在文件摘要上)；雖然有點粗糙且缺乏實證，但我想也許是一個有價值的發現吧，在這裡就坦誠的與你分享了。至於使用的方法，我最近會做一些嘗試，有進一步結果依然會在這邊跟忠實的讀者你報告。

Tags: 資訊檢索, 邊學邊寫, Text Mining

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有18 意見