About Me

我的相片
台北市, Taiwan
我是方選,
方白科技(finebind tech.)共同創辦人,
臺大資管所畢,
希望能幫助更多的人!

FB: http://fb.com/function1122
LINE: http://bit.ly/1foeZft (手機開啟點擊網址自動加入)

最新15則讀者回應

最新文章

FUNction's 上課筆記

Label Cloud

Blog Archive

FeedBurner

追蹤者

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

FUNction 於 2010年8月19日 下午5:51 發表

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

 20100814 (13)
▲研究苦悶可以到郊外走走,看見藍天白雲和蔚藍的大海,必能使人心曠神怡(圖為筆者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),代表頻率計數的向量。

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

image (等式1)

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

image
▲圖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)表示。

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

image(等式2)

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

image
▲圖3:排名後圖1的矩陣

image(等式3)

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

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

image (等式4)

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

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

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

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

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

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

image (等式5)

image


▲圖8:透過計算si, j促進效能

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

image
▲表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~~~~~~~~~~~。很多作者使用這種作法架構出文件的主軸,可以作為主題的分界點。
  • 對仗重複:與排比重複類似,基本上就是兩句詞性相同的句子。若這兩句連在一起,通常意義不大(可能為諺語或舉例),但若間格出現時,如同跨句排比,會是兩個主題的分割點。
  • 詞性重複:例如資訊系統可以蒐集、處理、儲存以及散佈資訊,其中對「資訊」這個概念大量的使用了動詞來修飾他,通常這種句子在文中具有相當高的關鍵性。
  • 其他重複:此外還有主詞、動詞的重複,這種重複的權重較低,但是使用重複的句子通常較為重要。

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

繼續閱讀全文 中譯:進階領域獨立的線性文件分段 (Advances in domain independent linear text segmentation)

中譯:使用語彙鏈建立文件摘要(Text Summarzation Using Lexical Chains)

FUNction 於 2010年8月14日 上午11:10 發表

找到這篇是因為看了一篇寫得非常非常好的國內論文《混合式自動文件摘要方法》(這真的寫得非常好,學習Text Mining 非常推薦以之為基礎),想要多了解文法剖析法(Linguistic Approach),因為文中指出Brunn所作的《Text Summarization Using Lexical Chains》提出的系統架構與我的想法相近。但後來發現命題相近的《Using lexical chains for text summarization》可能才是所謂的key paper(引用598次),不過都翻譯了,就丟上來啦。我依照原文的章節形式分段,並用標楷體標註作者提及的內容,文末心得處亦為我讀後的見解,為了避免讀者混淆,特別在此註明。

原文:M. Brunn, Y. Chali and C. J. Pinchak, “Text Summarization Using Lexical Chains”, Proceedings of the Document Understanding Conference, pp.135-140, 2001

摘要
文件摘要(Text summarization)解決兩個問題:選擇文件中最重要的部份以及產生清楚易懂的摘要。在本文中我們呈現2001年萊斯布里奇大學(University of Lethbridge)文件理解研討會(DUC)的一個能高效率使用詞彙鏈的摘要器(summarizer)。

一、介紹
文件摘要器選擇文件中最重要的部分與產生易懂的摘要,在本文中我們描述2001年於萊斯布里奇大學的文件理解研討會發表,基於辨認局部文件重點中最重要部分方法的摘要器。在選擇文件部分時,這個辨認也會顧及連結(connectiveness)的程度,以降低摘要中包含連結不足的句子(poorly linked sentences)。這個目標可以藉由有效的使用詞彙鏈達成。

完整的系統架構可以參考(圖1),它包含幾個模組所組織而成的管線(pipeline)。本文的組織如下:下一段專注於介紹每個系統模組。最後我們以快速地在DUC評估分析系統的效能、概略的描述未來展望做結。

image
▲圖一:系統概觀

二、預處理(Preprocessing)
(一) 文件切割(Segmentation)
為了進行摘要處理,必須將原始的文件送往文件切割器(Text Segmenter)。文件切割器的角色是分割輸入的文件,使每個分割有相同的主題(Topic)。為了完成文件切割的需求,我們選擇2000年Choi 所提出的文件切割器。這個文件切割器在一個文件中產生多個區段,某些區段在內容上比其他的區段緊密。在本系統中文件切割可以獲得多重的子來源(sub-source)文件,每個文件包含討論相同主題的句子。文件切割允許接下來的模組產生更好的分析與摘要。

(二) 貼標籤(Tagging)
在分析器(Parser)中,標籤是不可或缺的,因為它包含了根據區段中語句(part of speech)所代表的意義而產生的文字分類(Classifying Words)。這個過程中文字(words)被單獨考慮,沒有考慮或指派任何標籤給語意結構(semantic structure)。在本系統中使用的標籤是1996年Ratnaparkhi 所提出的,我們選擇的原因是這個方法能夠相當精確地指派標籤。標籤器(Tagger)經由Penn TreebankWall Street Journal 語料庫的0到18段(sections) 進行預先的訓練(pre-trained),沒有證據指出標籤器需要用明顯不同的語料庫重新訓練。

本系統也包含Ratnaparkhi’s MXPOST 標籤器套件中的工具,用以偵測句子的界線。它發表在Reynar 與 Ratnaparkhi 於1997年的文章中,是一個切斷文件使得每個句子成為獨立的一行的工具。標籤器也仰賴在Penn Treebank 大會中被標記化句子,透過由賓州大學(University of Pennsylvania)開發的sed script 工具可以轉換純文字文件成為適當標記化的版本,使文章片段成為標籤器可以接受的格式。

(三) 剖析(Parsing)
剖析是本系統最重要且耗時的模組,剖析模組集合與組織標籤後的文字,建立句法結構(syntactic structure)。我們在本系統中使用Collins 於1997年提出的剖析器(parser)。一個剖析後的文件可以在句子中依照句法的部分(syntactic position)選擇不同的元件(components)或詞組(phrases) 。舉個例子,我們可以在給定的文件中選擇所有的名詞片語(noun phrases)。尋找名詞片語對剖析過的文件可能是個瑣碎的工作,但事實上,本系統的下個階段仰賴在句子中選擇部分句法的能力。

有必要在這裡標明本文的剖析器與標籤器在輸入/輸出上並非完全的相容。剖析器接收的標籤文句必須要在開頭記錄標籤的數量,例如這句有三個標籤,就必須要在句首寫"3",因此必須另外撰寫一個小工具計算每行中的標籤數量作為剖析器的輸入。此外,剖析器也需要接收以"word TAG"格式的文字標籤,故須將標籤器輸出中的底線(underscore)移除。

三、名詞過濾(Noun Filtering)
名詞過濾元件是一個優化器,不是文件摘要系統中必要的元件。名詞過濾從剖析過的文件中選擇性的移除名詞,提升文件摘要的精確度。以下章節描述的詞彙鏈結器(lexical chainer)輸入的是一組名詞;名詞是由標籤器從原始文件中識別產生的,但是這些名詞可能同時增強且減弱文件的主題。

比如模擬資料的傳輸包含訊號(signal)與雜訊(noise),在訊號強且雜訊低的時候傳輸狀況是理想的;但當訊號被雜訊壓過時,傳輸變得難以辨認。與文件中的名詞一樣,形成主題的名詞像訊號,而其他就像雜訊。名詞過濾器的工作是減少「雜訊」,並盡可能地保留「訊號」。

有很多不同過濾「雜訊」名詞的探索方法,我們的概念是主要子句中名詞對主題的偵測比從屬子句中的名詞更有效。但主要子句與從屬子句的探索實為不易,所以在我們系統中,採用的是相對簡單的探索法。由於剖析器建立句子的句法結構,我們可以從原始文件中選擇不同型態的片語。我們辨識第一個名詞片語(noun phrase)以及每句中第一個次句(sub-sentence),即主要子句、從屬子句中的其他片語裡,與第一個動詞片語有關名詞片語。使用探測產生的摘要可以在DUC評量章節中找到。此外,可以開發更複雜的的探測法以尋找辨識一句中主要子句或從屬子句的其他片語,並有其確定實驗成效的必要。

四、詞彙鏈(Lexical Chainer)
銜接(cohesion)的觀念在1976年被Halliday 與Hason 提出,是一個將不同文件部分「黏在一起(sticking together)」使文件完整的方法。一般透過文法性銜接(grammatical cohesion)如參照(reference)、代換(substitution)、省略(ellipsis)、連接詞(conjunction);與詞彙性銜接(lexical cohesion)如語義相關詞(semantically related words)來達成。詞彙性銜接在兩個詞間與一系列相關的字之間都存在,稱之為詞彙鏈(Morris and Hirst, 1991)。詞彙鏈的演算法步驟介紹如下:

  1. 選擇一組候選字(candidate words)。候選字是從名詞過濾器而來(參見第三節),具有名詞片語或符合規則的名字功能的無限語類(open class)的字。無限語類指的是文法書中列舉不完的語類,舉例來說,代名詞、語尾助詞可以在文法書中用表格輕易的完全呈現,但是名詞、動詞卻不行,只有辭典才能囊括語言中所有的名詞、動詞,所以名詞、動詞屬於無法列完的無限語類。
  2. 一組候選字可以透過分類辭典展開成相關字(senses)。本實驗中,我們使用WordNet 分類辭典(Miller et al., 1990)。本階段需要考慮所有的相關字,每個字的相關字由區別的集合表示,並建構其階層。第一層的集合是同義字(synonyms)與反義字(antonyms),第二層是上位詞(hypernyms)與下位詞(hyponyms)與他們的變化型,如meronyms與holonyms…等等。「大冠鳩」的上位詞是「鳥」;「植物」的下位詞有「薰衣草」、「榕樹」…等。
  3. 我們找到根據相關詞集合產生的語意關聯(semantic relatedness)。語意關聯存在兩個相關詞之間,當比較兩個區別字的相關詞時,會發現存在匹配(matching)的現象,兩組字中有交點存在。每個語義關係決定在匹配的路徑長度,該長度與兩個比較集合的階層有關。這句意思應該是語意關係決定在兩個文字概念的距離,距離可以透過將文字概念展開而成的相關字sense之間的距離得出。因為sense是有層次的,所以如果A延伸出來的第2層sense與B延伸出來的第3層sense交疊,則A與B兩個概念的距離就是5,應該啦。
  4. 我們建立詞彙鏈如下:
    image
    ij時,wordi-senseix與wordj-sensejy有語義相關
  5. 我們透過以下的偏好準則(preference criterion),保有最長的詞彙鏈:
    image 
    在我們的實作中,偏好藉由對詞彙鏈中對每個成對的語義關聯指派分數來處理,然後進行分數的加總。因此語彙鏈的分數是基於語彙鏈的長度與成員間關係的型態。成員間關係的型態應該指的是同義詞、反義詞、變化型…等。

在語彙鏈方法中,兩個字在語彙鏈中的關係是兩兩相互的,即是每個相關字(word-sense)都必須其他每個語彙鏈中相關字有語義上的關係。在文件中無限語類字的順序與建立語彙鏈無關。但儘管如此,無限語類的字產生極大量的語彙鏈,因此產生文件更大區段的問題。面對此問題,當遇到長文件的切割時,我們只保留相關字的描述中的同義字;這樣的刪減還能使得效果比基於ISA-2/INCLUDE-2 來的好。此外,也可以從太多單獨區段的狀態下窄化詞彙鏈集的詞幹(stemming)。至於什麼是"ISA-2/INCLUDE-2"我也不知道…如果讀者知道的話請告訴我吧:)

語彙鏈法藉由一組呈現消歧義(disambiguation)相關字的候選集合,整合相關字消歧義的過程。消歧義指的是消除由於不同一詞多義所引起的混淆,例如「大學」既是教育機構又是一本古書,故必須要進行消歧義了。在演算法步驟5的偏好準則中,只保留成員是相關詞的語彙鏈,這些相關詞成為銜接文件的指標。

語彙鏈計算了每個文件區段,作為下一階段的文句萃取器的輸入。

五、文句萃取器(Sentence Extractor)
文句萃取器模組有兩個步驟:區段選擇與文句萃取。

(一)區段選擇(Segment election)
本階段的目標是從文件中選擇與主題相關的文章區段。文章區段選擇的演算法基於區段的評分,如下所示:
image 
score(chainMemberi, segj)是chainMemberi在segj出現的數量,m是他們的數字,si是chainMemberi中區段的數量。

系統選出分數前n高的區段進行文句的萃取。

(二)文句萃取(Sentence extraction)
每句被以詞彙性銜接的總分排名,排名程序的目標是評定每個分數的重要性、為每句結合所有分數成為排名。為了達成這樣的作業,我們根據Hoey 在1991年的實作,為詞彙性銜接定義句子必要連結的最小的數字作為門檻。我們加總超過門檻的句子之詞彙性銜接分數作為句子的排名。根據我們的實證調查,在我們實驗中門檻值為2最為恰當。

每句以與其他句子共享語彙鏈的數量總和為排名。更精確地說,sentencei的分數是決定在sentencei與區段選擇階段時sentencei所包含的語彙鏈的字的數量。

這樣的摘要包含句子的排名清單,因此可以依照需求的壓縮比例調整原始文章的呈現。

六、DUC評量
我們參與單篇文件的DUC評量,評量的工作包含從給定的文件中建立一個近100字長度的摘要。系統輸入30組,每組約10份的文件。根據我們的分析,結果前景看似光明。在語法性的部分,我們產生的摘要獲得3.73分(滿分4分);同樣的,銜接(cohesion)與組織(organization)分別得到2.55、2.66分(滿分4 分)。我們摘要器評量的重要資訊彙整如下(表1):

image
▲表一:評量結果

我們找到排名高分的句子幾乎每次都是都是最重要的。此外,由於句子的萃取包含參考措辭(referring expressions),對我們的系統來說仍是個問題。

七、結論與未來展望
在本文中,我們實作一個高效率詞彙性銜接法的摘要引擎系統。排名的程序使用文件「相關(aboutness)」的方法,在符合使用者需求的摘要比率的文章中選擇最重要、最佳連結的句子。未來,我們計畫進行以下問題的研究:

  • 我們的方法將完整的句子視為單元萃取,使用壓縮技巧(compression techniques)可以提高摘要的縮減並增加品質(Barzilay, McKweon, and Elhadad, 1999; Mani, Gates, and Bloedorn, 1999; Jing and McKeown, 2000; Knight and Marcu, 2000)。
  • 我們摘要的方法只使用語彙鏈代表原始文件,在產生摘要時也可以考慮採用其他聚合(gathered)文字的方法。
  • 在名詞過濾的程序中,我們的假說是去除從屬子句的名詞。我們也許可以進一步證明,根據子句出現處的種類計算權重值的有效性。

心得
我想讀到這你也累了,所以應該沒什麼腦力再看我的心得吧,然後說真的我也累了…我一直覺得這篇只是把很多方法兜起來,看不到真正想看的東西…例如語彙鏈的內容,不過本文提出了很好的模組架構。因為是兜起來的,內容有點過於精簡,也不適合入門讀者,而我最關心的主題切割也沒有加以說明,只指出了一篇論文標題,所以整體而言是失望的

理性面而言,作者使用名詞過濾將他認為重要句子中的名詞片語挑出,建立語彙鏈,再透過語彙鏈定義分數,萃取出分數大於門檻的句子,所以我認為語彙鏈在本研究充其量只是一個「計算分數的方法」,但卻使用了大量的文法剖析、拆解句子、抽取名詞、語彙關聯…我不知道是否有其必要。此外,我認為語彙鏈的分隔度不會太大,且語彙鏈的設計與結果好壞息息相關,語彙鏈不只複雜,而且資訊含量驚人,設計成本相當可觀。至於為什麼說分隔度不會太大,是因為我想語彙鏈(Lexical Chain)其實就是本體論(Ontology)吧!由於有大量的連結,也是一種網路的構造,故可以套用六度分隔理論,在六度分隔理論的假設下,根據我先前做的實驗(關鍵字六度分隔),最長的連結也頂多需要走九步,但這九步可能需要尋覽完所有的詞彙。

閱讀本文的時候,我參考了《中國話的文法》與《上位詞語下位詞的篇章功能》,這兩篇都不是以電腦科學的角度出發,純粹探討語言學的,我覺得他們都寫得很好,也在其中獲得了許多重要的知識。我想中文摘要就詞性而言,比英文難上許多,在《利用向量支撐機辨識中文基底名詞組的初步研究》(這篇論文的"卡司"非常強大,作者來自台大資工/外文與政大資科)提到,中文的動詞可以修飾名詞,會造成複合名詞的誤判,例如「建設公司」與「流浪教師」等。所以是否有更直覺抓重點的方法,就像人不需要知道名詞動詞,只需要靠一種fu,一看就知道哪句是重點,抓起螢光筆馬上作個記號這麼容易呢?

繼續閱讀全文 中譯:使用語彙鏈建立文件摘要(Text Summarzation Using Lexical Chains)

資訊種子:即將大三到碩一的你 請讀這篇可能改變你一生的文章

FUNction 於 2010年8月8日 晚上7:14 發表

「資訊種子」不限資訊相關科系學生參加,是台北縣電腦公會辦的公益(免費)活動,為期一年。聘請經理級以上講師固定於周六下午上課(課程內容包含資訊產業、數位內容、生涯規劃、智慧財產…),此外還有企業參訪、專案參與及海外參訪,最重要的是,誠如我說的,可以完成學生階段「認識不同領域的優秀人才」的目標。

 ITSEED happy3
▲想要成為眾所矚目的焦點,加入資種,你也可以!

好了,其實已經差不多介紹完了!我認為在資訊種子最大的收穫是能夠認識許多優秀、負責且活躍的同儕,這些人脈的培養將會使你在未來的人生上左右逢源。舉個簡單的例子,據我所知,本屆資訊種子的學員報名微軟實習計畫全部都錄取了,由此可知將資訊種子比喻為成功的搖籃毫不為過。

參加資訊種子的人都很厲害耶…我行嗎?
朋友看到了七屆錄取名單,對我說:「資訊種子的學員都很厲害,我怕我不行耶…」。我對他說:「如果你參加了,你就有機會認識34個厲害的人;如果你放棄了,你只能活在原來的小圈子,不知道厲害的人怎麼看事情…」

出自私校的我很清楚總會有點自卑,但是資種也不是只有名校的學生阿。我們要相信:近朱者赤、近墨者黑,應該要更正向的思考,這是一個很難得的機會,因為將來出社會後,生活的範圍常常是同質性的人;在一般的學校團體,也很難認識來自其他學校優秀的人脈…你該不會想著藉由國中同學、高中同學認識不同學校的人吧…那樣是很有限的,而且沒有共事過也不會患難見真情!

IMG_1286
▲策畫台北縣電腦公會的春酒大會,為資訊種子的「春酒專案」。當天與會來賓包括行政院、資策會長官,台灣各縣市電腦公會理事長與產官學界大老。

資訊種子在幹什麼呢?
不知道為什麼總是有朋友對我說不知道資訊種子網站在寫什麼,我這邊具體的再介紹一下好了:

DSC07230
▲大宇資訊總經理為我們介紹《數位遊戲產業的趨勢與經驗》

如何參加資訊種子?
當然你要先報名。接著為了考驗你的態度,你必須繳交一些資料,經過審核後會安排面試。身為熱愛分享的我也不改風格在這裡跟你分享我當年的資料供你參考,不過你要記住,照抄絕對不是一個好的態度:D

最後,如果你順利進入第一階段,你可以參考我的面試心得進行準備。在此附上同學的面試心得:台大生工 王皓元智資傳 劉孟芳(含資種人物介紹)。總之,若想改變人生,資訊種子一年的培訓將會是個不錯的選擇!還等什麼?8/26報名就截止了,機會是不等人的哦

[資訊種子培訓計畫官方網站]

btw,說真的,我的Blog讀者以在職者居多,寫這些似「太青春」而幫不了什麼人XD

繼續閱讀全文 資訊種子:即將大三到碩一的你 請讀這篇可能改變你一生的文章

什麼是 馬...馬可夫鏈(Markov Chains)?

FUNction 於 2010年8月6日 下午5:15 發表

「人生的課題,如果你沒有學會處理,它就會一而再、再而三的讓你練習」…其實也沒那麼嚴肅啦,只是小時候沒學好,最近讀論文的時候一直碰到馬可夫鏈…讓我覺得很卡,於是想說花一些時間把這個關節打通。我希望用一些淺顯易懂的文字寫一些老嫗能解的馬可夫鏈概念(千萬不要像維基百科寫得像天書般),這就是邊學邊寫的最高境界吧,我想!

馬可夫鏈
▲當我聽到「馬可夫鏈」的時候,總會想像一條長長的鏈子,鏈住馬的頭@@

正文開始
我們想像有一些加以編號的桶子,每個桶子裡面裝著數顆編號過的球,如下圖所示:

馬可夫桶子
▲有1~n個桶子,桶子中的球也編有1~n號

接下來玩法是這樣的,例如我們先在2號桶子中抽到3號球,於是我們就跑到3號桶子再抽一顆球;我們發現3號桶子抽出來的球是5號,於是又跑去5號桶子抽…總之從任一個桶子中抽出球的號碼,決定著接下來目的桶子的號碼,然後一直抽到沒完沒了(或某個次數),如此所形成的連續動作就是馬可夫鏈

到這裡已經講完馬可夫鏈了,應該有如醍醐灌頂的感覺吧!那我們接下來看看,這樣的一條鍊子有什麼特別的呢?

馬可夫鏈的特色
馬可夫鏈最主要的的特色在於「下一個狀態決定於上一個狀態裡的機率」,以上面桶子抽球的例子來說,第k次抽球的桶子決定在第k-1次所抽出來的球(與前面抽球的機率都沒有關係)。此外,在同一個時間,馬可夫鏈只會有一個狀態,我們舉下一個例子:慈善賭場中有一個賭徒,身上只有一塊錢,每賭贏一次多一塊,輸一次少一塊(因為是慈善賭場,輸到負的還可以繼續賭XD)。

這樣也構成一個馬可夫鏈,第k次賭博身上所剩的錢,決定在第k-1次身上的錢&輸或贏,所以我們若知道第k-1次身上有10塊錢,就可以推論第k次輸了的話身上剩9塊錢,贏的話會有11塊錢。此外,我們還可以發現,狀態是可能來回循環的,例如可能會重複回到「一塊錢」的狀態。但是如果是三度空間以上的馬可夫鏈,狀態會離原點越來越遠(雖然不一定沿著固定方向)。

總而言之,馬可夫鏈有以下兩點特色:

  • 在任何週期,系統中的事件只存在於一種狀態內。(每一局身上的錢只有一種狀態)
  • 事件由一種狀態轉換到另一種狀態時的機率,決定於前一週期。(第k局加減的錢由第k-1局的機率所決定)

計算馬可夫鏈
一般而言,我們會使用轉移圖來了解馬可夫鏈狀態間的轉換,再搭配矩陣來計算馬可夫鏈的數值。一開始我們可以使用樹狀圖來分析馬可夫鏈,如下圖:

馬可夫鏈表示法
▲以上三張圖都在表示同樣結構的馬可夫鏈,a1, a2, a3 為三種狀態,而互相轉換的機率標在線上

我們都會使用矩陣來進行馬可夫鏈的計算,透過反覆的計算,例如計算第k步時停留在a1狀態的機率,達到一個程度的預測。

總結
馬可夫鏈的應用相當多,可以用來進行物理中排隊理論或統計學的建模,此外也可以應用在人口、生物觀察上(估計的繁殖或死亡狀態)。最值得一提的是,基於馬可夫鏈發展出狀態非顯而易見的隱藏式馬可夫模型(HMM)大量的被應用在辨識技術上,如語音辨識與文件切割等,這也是為什麼馬可夫鏈重要的原因。

參考資料

  • 馬可夫鏈的簡介:這是一篇從概念講起馬可夫鏈的文章,雖然後面寫得有點讓人想飄走,但是可以對馬可夫鏈有個概觀的了解。
  • Ch 10 馬可夫鏈.ppt:朝陽科大資管系李朱惠老師的上課教材,使用例題介紹馬可夫鏈的運算
繼續閱讀全文 什麼是 馬...馬可夫鏈(Markov Chains)?

使用基因演算法進行自動文件切割(Story Segmentation)之研究

FUNction 上午10:42 發表

實不相瞞,我想要找出一種方法,可以偵測一篇文章中論及多少事件,並將這些事件自動切出段落。但目前礙於我搜尋能力的不足,以及論文閱讀速度的限制,實在沒有找到一個合適的方法。今天來介紹成大資工所方國安所撰寫的《應用基因演算法於中文廣播新聞中情境切割及分類》學位論文,希望能得到一些啟發。

這篇論文主要在描述使用基因演算法,試圖對中廣同一個主播連續報導不同新聞事件的語音進行切割。最重要的是對新聞加以分類,並在每個分類中找出具有代表性的專有詞彙,作為辨識新聞主題的工具。下圖描述新聞情境切割的流程,也是本篇文章的主軸。整個演算法主要分成兩大部分:一、找出分界點;二、評估分界點;以下詳述之。

image 
▲新聞內容切割流程圖(Story Segmentation)

使用滑動視窗找出分界點
作者先將新聞分成14群建立類別,再從這14群中找出代表的關鍵字。接著作者對長串的新聞,設計了一個滑動視窗以偵測主題的改變,大小為語料庫中平均故事(Story,這裡指的是一則新聞)長度的一半。滑動視窗每次往下移一個句子,並統計之中文字內容所屬類別(群),依照類別強度繪製強度曲線。我們可以找出類別交錯點,估計新聞主題轉換處。實務上常出現的問題是在轉折處變成緊密夾雜類別的現象,因此要將類別轉換做平滑化的處理。

作者定義「碎裂」為區塊類別持續性小於平均故事的四分之一,而平滑的方式是計算碎裂區塊的向量,看包含哪些所屬的類別,其中強度又為何。如果向量強度偏向於前方的區塊,則往前合併,反之亦然。

使用基因演算法評估分界點
基因演算法通常被用來解決解空間大、計算複雜度大以及需要求全域最佳解的問題。在本研究中,作者對上述方法找出的分界,分別往上與往下算半篇平均故事的長度,形成一個「模糊區塊」。模糊區塊中包含了兩個故事的分界,因此接下來的任務就是透過基因演算法在模糊區塊中找到實際的分界處。

一篇未切割的文件包含n個切割點(n+1個故事),在本實驗中將任一種切割方法視為一個染色體,而n為染色體序列的長度。其中將未切割的文件視為一個染色體(裡面包含多個基因),每個模糊區塊為一個基因,基因的數值k代表從該模糊區塊的第k行作切割。本實驗產生100個染色體族群,則每個族群中染色體的初始值是由亂數產生的(當然不能超過全句數)。世代數為500,交配機率0.25,突變機率0.01,以上均為經驗法則產生之引數。

基因演算法最重要的環節是評估函數,在本實驗中評估函數就是評估分類的正確性,如果切割的解越好,會得到分數越高的分類。再將分類成功度的總數相加,求其最大值。

心得
將基因演算法用在文件切割我認為是非常有創意的,但是必須經過太多的限制與前置條件,才能得到八成的準確率,實際上是否合用還需要要深思。我們注意到,首先必須統計語料庫中的文件,找出通常一則故事的長度;接著必須將故事加以分群,找出每群的特徵。將這兩個重要的預處理做好,才能夠開始切割文件。所以真正的問題是,這樣的切割方法沒辦法用在生活中的語料,例如一篇作文或專題報導;只能夠限定在差不多長度的新聞上

我認為使用統計方法一定會受到這樣的限制,因為電腦始終無法解讀文件內容的涵義,只能瞎子摸象。就算是訓練有素的瞎子,可以精準的摸出每隻大象的眼睛、鼻子、嘴巴或耳朵的位置,但是對象換成一匹馬,瞎子就無法抓出他五官的位置了。因此如果要使電腦能準確的對文件分段,絕不是反覆訓練他摸各種大象,而是告訴他眼睛是什麼、鼻子是什麼、耳朵是什麼…這樣只要不是外星來的生物,應該都有九成以上的辨識能力。


▲瞎子摸象,訓練有素的瞎子不管從大象的何處開始摸,都能摸完整隻大象,但摸別的動物又要重新訓練了…

我想也許還不需要運用到機器學習、人工智慧的技術,但文法剖析對自動分段確有其必要性,如此才能從根本改善分段的準確性。另一個可以思考的方法是我們先對文章進行人工分段,再透過倒傳遞類神經網路找出分段的關鍵,讓機器找到文法剖析的邏輯,也許效能會比我們預先輸入邏輯還蓋面向更廣…但是神經網路該如何設計將是一大挑戰。

最後一點值得考慮的是若要將文件概念分段,畫出文件的樹狀結構也是個不錯的方法,但是就連一般人都需要相當深厚的功力,而且劃分的方法也會因背景知識不同而大相逕庭。不過如果能做出這樣的樹狀結構,在未來將是相當有前瞻性的…也許我該買本國中的歷史地理參考書來看看,找出之中的規則…

主要參考資料方國安,民91,應用基因演算法於中文廣播新聞中情境切割及分類

繼續閱讀全文 使用基因演算法進行自動文件切割(Story Segmentation)之研究

文件自動分段之研究 (含心得)

FUNction 於 2010年8月3日 下午5:11 發表

如果在龐大的語料庫中搜尋「資訊系統」,我們希望得到的是「包含了相互關聯的一組蒐集、處理、儲存以及散佈資訊之單元,以支援組織內的決策與控制」的答案,而不希望出來的是Laudon的MIS一整本書的內容。前述的資訊檢索技術只能提供使用者需要資訊的所在文件,但更進一步我們需要得到的是在文件中哪一個段落,甚至把使用者想要的文句摘錄出來,因此便需要文件自動分段的技術。

資訊系統的定義 
▲Laudon的(周宣光譯)《管理資訊系統─管理數位化公司》一書中對於資訊系統的定義

另一個必須分段的原因在如果一大篇文章講述許多主題,在詞頻統計中的權重就會因為主題分散而被降低,使得排名落後;分段後主題應更為凝聚,比較能與查詢條件匹配,提高了recall與precision。以下介紹常見的自動分段方法:

依文件架構分段(Discourse Passages)
依照文章原有的段、節分割成不同部分。好處是有效率,因為作者已經利用段落切割想表達的概念。缺點是實際上這樣的段落未必正確,因為段落間的概念連貫與文體十分相關。例如將某個概念貫串全文,或是在最後一段總結前面所提到的三個概念,都會影響結果的精確性。因此此法在文件具有高度結構性時表現較好,如百科全書的資訊檢索中。以維基百科為例,在第一段中一定是該名詞的定義,因此在Google搜尋「資訊系統的定義」可以得到網路上 資訊系統 的定義的明確文字敘述。

依文章語意分段(Semantics Passages)
老實說了解這個方法這是我專程來圖書館的重要原因之一,我們一起看下去:「依照文章的語意或主題,加以分析之後,將文章分為概念不同的段落。如[6]中的TextTiling。在原文作者的論文中稱為motivated Segmentation,意思是這種分段方式是有依據可循的。」它的原理是從文件中用詞的相關(lexical connectivity)性判斷,將文件分為不同部分,每個部份內的相關性都很高。

TextTailing 將文件每3-5句組成一個區塊(block),鄰近區塊間比較其相似性。求出區塊間的相似性後,可以依照文章流向和相似性大小畫圖,圖形高峰代表相似性的高峰,而兩個谷底視為段落分割的點。依文章語意分段最大挑戰在調整區塊的大小,區塊大小不同結果大相逕庭。區塊太大會造成夾雜許多概念在文件中的問題,而區塊過小會使區塊相互比較時相似性失去意義(因為可能完全沒有重複的內容,相似度都很低)。

以固定字數分段(Window Passages)
顧名思義,如產生一個長度為200字的文字框,將第1-200個字為第一區塊,201-400為第二個區塊…這樣有個明顯的缺點,相同概念被切成不同段落的機率更高。但是我們必須考慮,在不同的查詢條件下,所需的分段方式可能不同,因此《Passage-Level Evidence in Document Retrival》的作者James P. Callan 在1992年提出了一個方法,從搜尋到的第一個符合查詢條件的字開始,設視窗大小為n,每n/2個字分出一個長度為n的段落。

例如第一個符合查詢條件的字位於第108個字處,而視窗大小是200,則文件會被分為第108~308字、208(108+200/2)~408個字,區塊透過互相重疊降低文字被分至不同段落的機會。經過實驗,在不同種類的文件下,最好的查詢結果視窗大小是不一樣的,因此對一般文件很難找到最佳的區塊大小;在英文裡,區塊通常介於200-400字。

心得
利用隱藏語意索引進行文件分段檢索之硏究的作者研究結果以「依文件架構分段」所產生的分段效果最為滿意,但我個人認為,依文義分段應該是因為詞頻統計的限制,造成效果無發發揮。我們知道,一般詞頻統計採用TF-IDF,但TF-IDF僅針對詞彙出現次數與分布進行關鍵詞的計算,而忽略了重要的文法結構,例如「回指」。「回指」是指語言中提到某事物之後,要再論及該事物時,使用上文參照來表達該事物。例如:「Berry 對 Ray 好,卻不要求他回報。」

其中「卻不要求他回報」就是使用回指的句型,還原後應為「Berry 卻不要求 Ray 回報」。其中使用了兩個回指,一個指向 Berry,一個指向Ray。指向 Berry 的回指因為在文句中完全省略了,所以稱為零形回指(zero anaphora);指向 Ray 的回指使用代詞「他」替代,屬於代詞回指(pronominal anaphora)。在中文中除了上述兩種回指,尚有名詞回指(nominal anaphora)(陳平,1987)。

使用TF-IDF處理的詞彙進行相似度計算時,會因為重要概念的「回指」造成計算的障礙。因為描述相同概念的文句,很可能只有在第一個逗號前講到關鍵概念,而後補充說明的幾句都使用回指簡化句型的重複,基本上我認為一個良好的寫作者會盡量避免文句的相似。因此TF-IDF可能是計算文件中關鍵字的好方法,但應該在小範圍的相似度顯得力不從心。

為了避免這樣的情形,達到文件正確分段,可以考慮從兩方面思考:使用「向心理論」進行回指解析(Anaphora Resolution),將回指替換成真正的名詞後再重新進行文件相似度計算;第二個方法也是依據向心理論而來,透過向心理論找出文句中的主詞,當主詞改變時進行段。方法一顯而易見的只要透過回指替換的預處理就可以繼續使用TF-IDF進行相似度計算,而方法二仍然值得探討。考慮以下文句:

(ㄅ)螃蟹A有四對步足B,(ㄆ)B俗稱「腿兒」,(ㄇ)由於每條腿兒的關節C只能向下彎曲,(ㄈ)C不能向後彎曲,(ㄉ)A爬行時,(ㄊ)A必須先用一邊步足的指尖抓地,(ㄋ)A再由另一邊的步足直身起來,(ㄌ)A把身體推過去。

上述文句中用注音符號表示每一句,底線後加英文字母為出現下指中心(forward-looking center)的地方,而文句中的其他英文字母則為零形回指的上指中心(backward-looking center),指向前面出現過的下指中心。這例子中可以發現文義連貫的句子中主詞會不斷的改變,如上例中的「螃蟹」、「步足」與「關節」,所以主詞改變不一定代表文義的切割,但也許可以建構「共同出現的鍊子」,找出意義的疆界。所謂共同出現的鍊子,在上例中就是:{螃蟹→步足→腿兒→關節},只要在同一句中出現的中心就加入這條集合的鍊子,也就是如果接下來句子的中心出現在集合中,就可以把文句邊界擴大,一直擴大到超出集合為止。

最後一個可以採取的策略是結合「依文章語意分段」與「固定字數分段」。我的想法是如果文件中有句號,就依照句號切割,接下來使用類似n-gram的方法,將每兩到三個句子結合成區塊,最後再進行相似度的計算,藉由句子的重疊,找出相似度的高峰,也是一個可能改善文件分段的方法之一。

以上,顯現我知識不足的粗淺想法,希望能拋磚引玉,共同塑造人類美好生活。

主要參考資料利用隱藏語意索引進行文件分段檢索之硏究 黃卓倫撰

繼續閱讀全文 文件自動分段之研究 (含心得)

文件搜尋的方法 - 資訊檢索(Information Retrieval)

FUNction 下午4:55 發表

資訊檢索系統(Information Retrieval System)可以定義為儲存、展示、組織與存取資訊的系統。文件分析與索引可以協助資訊檢索工作的進行,一般來說可以透過以下模型進行。

基礎方法

布林模型 (Boolean Model)
簡單說就是字串比對,找出「完全符合」搜尋條件字串的文件集合。查詢的條件是單字或片語,並可使用布林運算式:AND/OR/NOT加以連接字串。布林模型的優點是效能高,缺點是不提供查詢結果的相關性排名,使用者無法知道文件符合查詢條件的程度。此外布林模型缺乏彈性,必須要完全符合字串才能被找出。

向量空間模型 (Vector Space Model)
由Gerard Salton提出,他認為資訊檢索過程必須對文件本身進行分析,以建立索引(Indexing)。建立索引的目的是透過索引代表文件集合中的某篇文件,一篇文件可以對應一組索引,這組索引稱為該篇文件的索引向量。一般來說這些索引是利用統計方法對文件產生的關鍵詞所建立的,計算出的文件向量可以代表文件的基本意義,在這個向量之中,每一個關鍵詞上的值代表該文件在這個詞彙所強調的程度,可由如TF-IDF等演算法計算而成。

向量空間模型將查詢字串視為極小篇的文件,將此查詢也以向量方式表示,接著在計算與文件庫中文不同文件向量的內積,計算文件與查詢條件的相關程度。

機率模型 (Probabilistic Model)
其基礎為機率排名原則(Probability Ranking Principle),該原則認為資訊檢索的任務是將文件依查詢條件的機率,與相關的機率加以排序。首先,必須對文件集計算出「檢索出相關文件所花的成本(C1)」與「檢索出不相關文件所花的成本(C2)」;接著使用詞彙統計等方法,計算出使用者認為「某文件與查詢是否相關的機率(R)」,考慮以下算式:

C1 x R + C2 x (1 - R)

算式值越小總成本越低,故排名在越前面。該方法優點在於能找出總成本較低的結果,缺點是詞彙統計只知道詞彙的統計數字,忽略的詞彙所代表的意義,使得無法達到「最佳模型(Perfect Model,只列出所有查詢相關的文件)」。

進階探討

關聯回饋(Relevance Feedback)
由於查詢結果未必符合使用者真正心理需求,調整查詢結果確有其必要。透過使用者對查詢條件的反應,系統重新調整查詢向量中各個不同維度上的權重。一般來說就是將原本查詢條件的向量加上使用者認為相關文件的向量,再減去使用者認為不相關文件的向量,將此結果作為新的查詢向量。每個向量前有一個常數值,透過常數值的反覆調整,產生符合使用者查詢需求的權重向量,相關方法可以參考Standard Rocchio Technique、Ide Regular 與Ide Dec-Hi等方法。

關聯回饋的優點是可以大幅增進查詢效能,缺點是對使用者操作系統造成額外的負擔,這點通常被視為關聯回饋無法普及的原因。

隱性語意索引 (Latent Semantics Indexing, LSI)
詞彙統計的最大問題無法掌握文件中的「概念」,例如許多不同辭彙都可以表示一個相同的概念、而相同詞彙在不同上下文中又可能有不同的概念的問題,LSI是為了解決概念所產生問題的「概念搜尋系統」。LSI也產生文件向量,但採用奇異值分解(Singular Value Decomposition, SVD)縮小文件向量;LSI假設人在使用相關詞彙時有其限制,概念相同的文章通常會有概念相似的詞彙,透過SVD可以去除某些因為詞彙有限產生的詞彙間相關性。

特徵值分析(Eigenvalue Analysis)可以將詞彙加以分類,在最佳情況可以使不同類之下的詞彙完全不相關(G. Salton, Automatic Information Organization and Retrieval, McGraw Hill, 1968, P.135 按:老實說我有點懷疑,鑒於六度分隔理論每個詞彙應該都是有關的)。LSI概念與特徵值分析相同,詳細的步驟可以參考SVD 於資訊檢索與文本搜尋的應用,該文章應用了一個五篇文章的小語料庫對LSI做了詳細的說明,在此對作者周志成(大俠)獻上誠摯的敬意。想了解奇異值分解的推倒,也可以參考他的文章─線性代數基本定理 (四)

LSI最大的問題在與料庫更新後的策略,因為SVD的計算相當耗時,一般來說有兩種方法(加上台大資管所黃卓倫所提出的SVD-Updating成為三種策略),簡述如下:

  • 完全重新計算!
  • Folding-in:假設加入文件不影響詞彙-文件矩陣的特徵值,只計算新增的部分,如此會降低查詢的正確性。
  • SVD-Updating:產生比Folding-in更好的結果,將新文件向輛自成矩陣,附加在原本詞彙-文件矩陣所形成的rank-k approximation matrix 矩陣後,重新計算SVD,但計算複雜度比Folding-in高。

心得
上述方法除了布林模型外,都是建構在詞頻統計上的,因此說詞頻統計是一切資訊檢索的基礎並不為過;另一個重要的工具是「向量」,又牽涉到向量的運算─矩陣。目前的方法都是建立在相似度上的運算再加一些修改,而使用向量相似度似乎也能提供人們一個堪用的結果。在近期的文件探勘文獻中討論到過去使用統計方法居多,但語意理解的方法因為涵蓋較多背景知識,使得發展較緩(《利用機器學習摘要概念為基礎之文件摘要自動建立法》,2007成大資管劉佳宗),而本體論(Ontology)直到近幾年才比較受到重視。

本體論的對應(Mapping)應是LSI的更進一步,使用預先定義好的領域知識,對文件中概念的根源進行探索。例如將「汽車」與「火車」都追朔到「交通工具」,化簡用語不同所造成的「概念」混淆。但不禁讓我思考,我們腦中只有一份本體論,為什麼卻無法在電腦中發展出一本萬用的本體論呢?

我認為問題在於目前的本體論研究缺乏了「構面」的觀念,雖然「概念」間具有「關聯」與「方向性」,但是在不同構面應該產生不同關聯,而構面的決定又依傳入資訊的不同而刺激到不同的區域,引發不同觀念串聯的反應。例如「柳丁」這個概念(原諒我這例子很難舉),在「食物」的本體論中可能會追朔到「水果」,但是在「顏色」的本體論中,可能會追朔到「黃色」,這就是一般研究中說的本體論概念衝突,需要本體論工程師對本體論進行「修剪」。但我認為每個概念都有許多構面,因此不應有衝突的問題。

簡報1 
▲上圖中展現本體論可能有多個構面,每個構面可以再往上歸類,形成一個非常複雜的架構(也應是腦中的資料結構)

雖然我目前仍無法想出一個像專案管理TQC(時間、成本、品質)這麼完善處理概念不同構面的模型,但我想總有一天研究者會發現腦中的資料結構(應該是一種類似物件導向的東西),進行完整本體論的工程。我認為腦中只有兩種資料結構─「事」與「物」,「事」的資料結構較複雜,但「物」較為簡單,也具備繼承、多重繼承的特性。若能突破「物」的本體論,相信在未來電腦解析文件時能產生不亞於人類的理解力。

以上,顯現我知識不足的粗淺想法,希望能拋磚引玉,共同塑造人類美好生活。

主要參考資料利用隱藏語意索引進行文件分段檢索之硏究 黃卓倫撰 P.3-12

繼續閱讀全文 文件搜尋的方法 - 資訊檢索(Information Retrieval)