About Me

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

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

最新15則讀者回應

最新文章

FUNction's 上課筆記

Label Cloud

Blog Archive

FeedBurner

追蹤者

顯示具有 資訊檢索 標籤的文章。 顯示所有文章
顯示具有 資訊檢索 標籤的文章。 顯示所有文章

碼上會! mmseg4j 中文斷詞java 實作 (55行)

FUNction 於 2010年10月16日 晚上10:06 發表

好,我承認標題下得有點好笑,而且也很意外寫這種實作的文章(我早就往理論派轉型了)。總之照著這篇文章的步驟,你可以使用java 將一串正體(繁體)中文的字串依照詞彙切開,以方便進行中文文字探勘(Text Mining)等計算詞頻的工作。

image
▲mmseg4j中文斷詞結果,可以看到它把「處理」、「文章」等詞分割出來

首先呢,為了簡化開發,程式都在Eclipse 上開發,以下用簡單兩句話說明Eclipse 如何安裝:

  • Java網站,下載並安裝JRE (請選擇合適的作業系統)
  • Eclipse官網,下載Eclipse Classic 版本,將之解壓縮之後,執行資料夾中的Eclipse.exe ,就可以用它來寫Java 程式了

簡單介紹MMSeg 與mmseg4j
mmseg4j 是採用蔡志浩先生在2000 年發表的一個中文分詞演算法 ─ MMSeg,它使用兩套演算法與四個模糊解析規則,據稱能達到98.41% 中文斷詞準確率(理論請參考MMSeg官網)。這樣的準確率已經近似於大陸中科院的ICTCLAS,973計畫專家組評測第一名的98.5%,此外mmseg4j在斷詞速度表現良好,高達1900kb/s(Simple版本),根據5樓網友實測表示比庖丁(Paoding)還快。

此外可喜可賀的是,mmseg4j詞庫採用utf-8編碼(不像ICTCLAS使用GB)而且可以自訂,因此只要替換詞庫就可以用來將優美的正體中文進行斷詞,以下來稍微介紹一下詞庫。mmseg4j 預設使用sogou 詞庫(去除無意義詞),並合併rmmseg (Ruby中文斷詞套件)的詞庫,共14多萬詞。詞庫放在jar裡面,若使用WinRAR等軟體,將下載解開的mmseg4j裡面的mmseg4j-all-X.X.X-with-dic.jar 再解開,裡面的data 資料夾就是詞庫檔預設的位置。

  • chars.dic:單一字和對應的頻率,提供complex模式使用。
  • units.dic:單位詞,如:分、秒、年。主要是在數位後面的單位資訊切分好,不與words.dic中的詞有混淆。
  • words.dic:核心的詞庫檔,一行一詞,不需要其它任何資料,採utf-8編碼。

若要自訂辭典,檔案名必需是 “words” 為首碼和“.dic”為副檔名,例如wordsXXX.dic。然後我們可以把這個些自訂的詞庫集中在某個資料夾,並在程式中設定讀取這些詞庫檔(稍後會示範),也可以把這樣的純文字文件用WinRAR壓縮回mmseg4j-all-X.X.X-with-dic.jar 的data 資料夾中。

官網(簡體)下載mmseg4j:mmseg4j (請選擇最新的zip檔案,名稱會如「mmseg4j-1.8.3.zip」)

下載mmseg4j 正體(繁體)中文詞庫
以下詞庫是筆者透過程式工具將原本的詞庫轉為正體字,以方便台港使用者研究學習,歡迎下載分享,但請註明來源:)

來吧!我們來斷詞
當然不免俗的啟動Eclipse之後,我們必須先建立一個專案。檔案 > 新增 > Java專案

image
▲名稱取作SegChinese

image
▲下一步到Java 設定的地方,選擇新增外部JAR,然後瀏覽到剛剛下載來的mmseg4j-all-X.X.X-with-dic.jar,新增後按下完成。接著展開左邊專案目錄,在src上按右鍵,選擇新增類別,取個類別名稱,在這裡我還是取為「SegChinese」。

55行java 程式「碼上會」
我們要import這些東西,如下:

import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;

import com.chenlb.mmseg4j.ComplexSeg;
import com.chenlb.mmseg4j.Dictionary;
import com.chenlb.mmseg4j.MMSeg;
import com.chenlb.mmseg4j.Seg;
import com.chenlb.mmseg4j.Word;


值得注意的是import com.chenlb.mmseg4j.ComplexSeg代表使用Complex 版本的斷詞(包含四個模糊規則);若要使用簡單版本,請換成import com.chenlb.mmseg4j.SimpleSeg;。



接下來,我們在class裡面宣告一個字典型態的變數dic(儲存詞庫),並建立建構子與設定一些程式資訊,如下:

protected Dictionary dic;

public SegChinese() {
System.setProperty("mmseg.dic.path", "./src/SegChinese/data"); //這裡可以指定自訂詞庫
dic = Dictionary.getInstance();
}

protected Seg getSeg() {
return new ComplexSeg(dic);
}


Seg方法可以指定要使用的分詞器,在這邊使用Complex(複雜版的),並將字典及放入分詞器中。這裡一定要提一下,自訂的字典可以藉由 System.setProperty("mmseg.dic.path", "路徑"); 來指定,其中路徑若是相對路徑的話,是相對於專案資料夾的目錄,在上面的例子中,我故意將字典資料夾放在專案資料夾中的src/SegChinese裡的data資料夾中,我們可以在data資料夾中放入多個字典檔,就可以使用多個字典。



再來我們要建構程式的斷詞核心部分,如下:

public String segWords(String txt, String wordSpilt) throws IOException {
Reader input = new StringReader(txt);
StringBuilder sb = new StringBuilder();
Seg seg = getSeg();
MMSeg mmSeg = new MMSeg(input, seg);
Word word = null;
boolean first = true;
while((word=mmSeg.next())!=null) {
if(!first) {
sb.append(wordSpilt);
}
String w = word.getString();
sb.append(w);
first = false;
}
return sb.toString();
}


這裡我們傳入一個字串與一個希望用來作為分隔的符號,接著使用MMSeg進行分詞,每個詞可以用.next()取得,最後把它變為字串回傳。



最後我們建立一個run 方法,用來傳入測試段詞的文字。以及main 方法以測試程式執行,如下:

protected void run(String[] args) throws IOException {
String txt = "這行文字是要被中文斷詞處理的文章,可以從執行結果看斷詞是否成功 莊圓大師";

if(args.length > 0) {
txt = args[0];
}

System.out.println(segWords(txt, " | "));
}

public static void main(String[] args) throws IOException {
new SegChinese().run(args);
}


在run中我傳入直線(|)作為分隔符號,以上短短55行就完成了中文斷詞,輸出結果頁首所示。我把這份java 檔附在文末,也歡迎下載測試。



附件下載:SegChinese.java



結語

在這裡我要感謝前輩Deduce的提點,讓我能花相對少的摸索找到這套工具。當然這只是一篇讓讀者很快了解如何使用mmseg4j的小品文,所以只精簡的介紹了最基本以及常用的功能。我在java/text mining上的確是晚輩,所以若有撰寫不當也請各界多多包含與指教。

繼續閱讀全文 碼上會! mmseg4j 中文斷詞java 實作 (55行)

中譯:進階領域獨立的線性文件分段 (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)

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

FUNction 於 2010年8月3日 下午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)