找到這篇是因為看了一篇寫得非常非常好的國內論文《混合式自動文件摘要方法》(這真的寫得非常好，學習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評估分析系統的效能、概略的描述未來展望做結。

▲圖一：系統概觀

二、預處理(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. 我們建立詞彙鏈如下：
   
   當_i≠_j時，word_i-sense_ix與word_j-sense_jy有語義相關
5. 我們透過以下的偏好準則(preference criterion)，保有最長的詞彙鏈：
    
   在我們的實作中，偏好藉由對詞彙鏈中對每個成對的語義關聯指派分數來處理，然後進行分數的加總。因此語彙鏈的分數是基於語彙鏈的長度與成員間關係的型態。成員間關係的型態應該指的是同義詞、反義詞、變化型…等。

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

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

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

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

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

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

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

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

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

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

▲表一：評量結果

我們找到排名高分的句子幾乎每次都是都是最重要的。此外，由於句子的萃取包含參考措辭(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)

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

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

 
▲想要成為眾所矚目的焦點，加入資種，你也可以！

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

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

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

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

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

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

• 不清楚上課內容？我的上課筆記(雖然沒有每堂課都記到)詳實的紀載老師的一言一行，堪稱資訊種子筆記經典之作 ；孟芳的課程回顧透過生動的描述與豐富的照片，提供你不一樣的視野
• 不清楚學員上課後的看法？這裡彙整了大家每堂課的心得，也許可以在心得中找到線索
• 看看七屆學員怎麼說？元智資傳 劉孟芳、台大農經 柯捷方、台大電機 薛仲祥、中正企管 陳識傑、政大公行 張桂慈、元智工管 程紹幃、成大醫工 陳玟伶…(陸續追加中!!!)

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

• 未來一年的規劃
• 第一題(注：鑒於與今年題目相關，為了避免爭議與提高公平性，暫時將連結拿掉，將於報名截止後恢復)
• 數位落差的原因與改善方式

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

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

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

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

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

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

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

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

▲有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)？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果在龐大的語料庫中搜尋「資訊系統」，我們希望得到的是「包含了相互關聯的一組蒐集、處理、儲存以及散佈資訊之單元，以支援組織內的決策與控制」的答案，而不希望出來的是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的方法，將每兩到三個句子結合成區塊，最後再進行相似度的計算，藉由句子的重疊，找出相似度的高峰，也是一個可能改善文件分段的方法之一。

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

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

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

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

資訊檢索系統(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的更進一步，使用預先定義好的領域知識，對文件中概念的根源進行探索。例如將「汽車」與「火車」都追朔到「交通工具」，化簡用語不同所造成的「概念」混淆。但不禁讓我思考，我們腦中只有一份本體論，為什麼卻無法在電腦中發展出一本萬用的本體論呢？

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

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

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

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

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

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

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

在meeting 中常聽到：

• 你有什麼comment？
• 這是個good point！
• 在這個Algorithm中，我們會先…

雖然既有的單語辨識系統已經漸趨成熟，但在實務上，雙語辨識系統的確有其需要。要建構中英雙語辨識系統，必須要考慮兩種語言的特性，並加以整合。此外，實務應用上的「自發性語音(spontaneous speech)」常伴有許多的停頓、重複、無意義的語助詞或不完整的段落。而且演說者常會把英文說得有點想像中文，例如facebook會說成「非死不可」之類的，也會增加辨識的難度(中:英 = 9:1 左右)。

中英連續語音辨識技術
英文是多音節的拼音語言，一個word可以由一到多個音節所組成，因此音節(或稱音素phoneme)是英文的最小單位。而音素根據發音方式可以分為子因與母音，因此英文辨識以因素為基礎，將音素串辨識為字串。

中文以單音節為基礎，一個字一個音節，往下細分可分成聲母(Initial)、韻母(Final)與聲調(Tone)，其中聲調的部分在辨識時不一定需要，而聲母、韻母就像英文基本單位的子音語母音。中文連續辨識系統都是以辨識次音節(聲母、韻母)為基礎。要辨識出完整的中文字串，就是在連續語音中辨識出「聲 韻 聲 韻 聲 韻」的序列，再根據「聲+韻」不同的組合辨識出不同的單字，進而辨識出完整的字串。由於中文有上萬字，但不計聲調的「聲+韻」組合只有約450個，因此儘管能正確辨識出音節，卻不一定能選出正確相對應的字，也因此必須仰賴辭典及語言模型以得到最可能的字串。就像注音輸入法錯字的問題，基本上注音輸入法能辨識出正確的音節(包含聲母、韻母與聲調)，有1345種可能的變化，但中文也僅10000常用字，卻有可能發生「韓劇跟西洋句一樣差勁，我都不喜歡」辨識成「含巨根吸陽具一樣插進，我都不喜歡」的笑話@@

因此中英混和辨識必須：

• 找出最好的雙語聲學模型：必須解決目前中英兩種單語系聲學基本單位不同的問題，中文基本單位是聲母韻母、英文則是音素
• 建立雙語文字語發音相對應辭典：只要定義出聲學基本單位即可解決這個問題
• 採用最適合的語言模型：過去單語言模型不敷使用，但訓練雙語言模型之語料不易取得

中文與英文在書寫系統上最大的不同，是中文文句沒有明顯的分隔，分隔方法也會影響句子的意義，例如「沒雞、鴨也好」或「沒雞，鴨也好」就是兩種不同的意思。在研究中通常使用辭典斷詞法，斷詞結果完全取決於辭典內的詞。若領域有限，不需要很大的辭典，辭典過大反而會引起混淆，因此如何建立或選擇辭典也是一大考量因素。另一個需要考慮的是語言模型，由於雙語語料為兩種語言混合使用的結果，因此較無規律的語法，須採用「統計式(Statistics-Based)」，由訓練語料根據統計特性得到語言模型。

《以課程錄音為基礎的中英雙語語音辨識之初步研究》的重要方法與成果如下：

• 定義有限領域的中英雙語辭典：使用背景辭典將語料斷詞後，找出出現頻率一次以上的多字詞3940個，語背景辭典常見單字5901個，透過抽詞程式抽取合理的多字詞數個，合成12322個專業領域用詞(中文10767個、英文1555個)
• 聲學模型：定義四套不同音素集
• 語言模型：雙語模型、三連語言模型、以詞群為基礎的語言模型；以兩份不同背景語料建立調適語言模型
• 重要結果：雙語平均單詞正確率51.97%；中文最佳值66.11%；英文最佳值66.77%

雙語語音辨識的基本架構
要讓電腦「聽懂」使用者的話，必須經過一連串的處理程序，如下圖所示：

連續語音辨識不是直接對取樣後的數位訊號加以辨識，因為人類發音器官的限制，聲音訊號是連續且緩慢的，所以必須取一小段時間內相近而穩定的語音訊號，將之視為音框(Frame)，存一個因框中抽取出一組對辨識有用的特徵參數，建立特徵向量，再針對一系列代表實際語言的特徵向量進行辨識。為了避免突兀的訊號變化，通常因框間會彼此重疊，以保證所抽取特徵向量的代表性。辨識結果取決於：

• 聲學模型：由語音資料所建立，中文裡最小單位是聲母跟韻母，英文中是音素。
• 辭典：將發音與詞對照，選擇不同大小、領域、語言的辭典，也會對辨識結果造成影響
• 語言模型：透過足夠的文字資料，經由辭典做適當的斷詞，計算出前後詞之間的相互關係，以其辨識系統能根據語言模型辨識出最合理的文句。因此訓練語言模型的文字語料必須跟目標便是語料相匹配，此外必須能涵蓋辨識的範疇。

聲學模型
要發展多國語言辨識，必須先用「聲學模型」進行判斷，以下介紹一些現有的研究：

• 國語+台語：前專使用國台語混和聲學模型，在辭典中定義國台語的發音，統一以中文輸出(如果先端先辨識是國語還是台語，會造成辨識力低落)
• 廣東話+英語：外語母語化問題相當明顯，故以廣東話為母語的英語語料進行訓練，使用詞性將外語部分分為多個詞群。
• 法語+英語：定義單純法文、英法共用、單純英文三種音素集，從法語母語選出英法共用、單純英文適當的訓練資料，建立統合的聲學模型
• 日文：將外語資料是為辭典外字彙(OOV)，可以先得到主要語言中的資訊

《以課程錄音為基礎的中英雙語語音辨識之初步研究》的作者將實驗語料分成兩部分，文字語料作為語言模型的訓練；語音語料作為聲學模型的訓練及辨識用。

辭典製作與工具
下圖為製作辨識專用辭典的方式。作者將文件經過辭典斷詞後，取出出現一次以上的多字詞，並使用抽辭程式抽出老師上課的文字語料中少數具有詞的特性的多字詞，並將曾出現過的迎文辭會抽出，合併後與單字組成較小的辭典。

研究顯示斷詞與抽取出詞的好壞不會直接影響辨識率，例如複合詞「數位語音處理」與「數位」、「語音」、「處理」，辨識效果後者反而較佳。但若使用過大且內容廣泛的辭典，辨識率會遠低於定義後較小的辭典，辭典大小才是影響辨識率的關鍵。

下表呈現該實驗使用的語音辨識軟體相關工具：

工具	開發單位	用途
HTK Toolkit v3.3/3.4	Cambridge	特徵抽取、聲學模型訓練、辨識搜尋解碼
SRILM	SRI STAR Lab	語言模型訓練
PatTree抽詞程式	琳山大大lab	自目標語料抽出新詞
CKIP	中研院	斷詞

國語音素集使用郵鄭秋豫定義的SAMPA-T標音方式(SAMPA-T包含國、閩南、客語)與梁柏宇的NTU-98；英文採用美國腔的CMU音素集。

語言模型
中文存在相當多的同音字，在一千三百多個合法音節中，對應的合法字元卻超過一萬四千個。透過聲學模型可以輔助系統「猜測」較為合理的詞(具有獨立語意，且扮演特定語法功能的字串)串。N連馬可夫鏈語言模型(N-gram Markov Chain Language Model)是統計式語言模型，估算由詞串所組成字串的出現機率，是目前世上最普遍且效能最好的語言模型。但已三連模型為例，若句子中包含一個未見的三連字串，則無論其餘字串機率為何，計算結果必為0。因此若語言模型的訓練語料不足，造成估測的失準，必須使用平滑法建立更好的語言模型。

SRILM提供的N連語言模型訓練程式使用退化平滑(backoff smoothing)法，透過建立門檻，當三連詞串在訓練語料中出現次數過多時，直接使用該三連字串在訓練語料中出現的機率；出現過少時則使用古德-圖靈函數(Good-Turing Function)調整字串機率；若未出現於訓練語料中，則根據正規化條件，由高斯模型的機率到低階模型的機率(按：這段是啥阿…我好像沒有一句看懂Orz)

實驗結果

• 更改音素集可以得到明顯的進步，特別在中文正確率上。
• 英文單詞進步率之提升，仰賴語言模型的調整。因為語言模型裡中英文比為87:13，而音素集裡中英文模型比為63:39，因此調整語言模型可以提高英文辨識。
• 不符合目標語料的背景語料完全無法為辨識系統帶來任何進步。
• 以詞群為基礎的語言模型幾乎完全無法發揮作用，可能是因為目標語料口語化、沒有明顯語法結構所造成。所以若要使用詞群概念，可能要考慮階層性的詞群。

參考資料：以課程錄音為基礎的中英雙語語音辨識之初步研究
注：本文是我從以上論文所摘錄的重點筆記，圖片均來自該論文中，若有冒犯煩請告知，放在Blog除了作為研究筆記，也希望能促進學術研究與交流風氣，在此深表對研究者的感謝！

繼續閱讀全文　中英混雜自發性語言語音辨識之研究

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

中文語音辨識
語音文件無法被概括性的瀏覽，只能循序瀏覽到最後才能了解整篇文件要表達的含意。相同內容，由不同的人說出來的語音文件，除了聲調、音量外，口音也會使每篇語音文件顯得不同。即使是相同的人，也會因為環境、身體狀況而改變語音文件的品質。

「索引特徵」是資訊檢索、分類系統表示文件或使用者問句的基礎。在中文裡，特徵分為詞(word-level)、字(Character-level)以及音節(syllable-level)三個層次。結構上中文具有以下特質：

• 中文一個字就是一個音節
• 單字通常是詞素(morpheme)，詞素是帶有語意的最小單位
• 詞的界限不明顯
• 有許多的同音字

新詞容易被創造、理解是另一大特色，例如「高鐵」。這些詞通常不存在於檢索分類的辭典，但是他們與文件的核心概念通常密切相關。由此可知，中文的構詞相當具有彈性，要統計中文的詞數其實相當困難。但是中文所有可能的音節只有1345個(不計音調只有450個)，且常用字大概只有7000到10000左右。根據琳山大大實驗室的研究，雖然中文可能的詞總數相當大，但是都是由一到數個字串接而成，而且音節數大於等於3時，唯一性相當高，因此音節段(Syllable Segment)層次的資訊在中文資訊檢索與分類中扮演非常重要的角色。此外中文新詞出現太快，加上詞的界限不明顯，使斷詞工作存在歧異性。但若以音節層次作為索引特徵，對於辭典外詞彙(Out of Vocabulary, OOV)將會有很大的改善。

使用不同特徵詞進行事件偵測
分別使用雙音節(double syllables)、單詞(single word)與雙字(double character)作為索引特徵，在專有名詞與關鍵詞部分，經過語音辨識後用派樹抽詞法(pat-tree)和文字在機率式潛藏語意模型上的主題亂度所擷取出來。研究發現使用不同索引特徵各有其優缺點，使用詞的辨識錯誤率較高，但提供的資訊量較豐富；使用字辨識錯誤率較低，但提供的資訊較含糊；一般而言，使用雙音節結果較好。將方法結合，發現單字結合雙音節，並使用機率式潛藏語意分析或機率模型效果最好。

按：其實我仍然對「單音節」與「單字」的差別不了解，但從研究結果而言，單字的辨識效果較好，所以我的猜測是單字是語音辨識後經過詞庫的比對而產生出來確切的字，例如將「ㄏㄠˇ」(單音節)辨識成「好」(單字)，因為同樣是「ㄏㄠˇ」這個因，仍然有好、郝、恏三個字，所以單字比單音節更為明確。

事件總數之選定
讓電腦決定要分成幾類非常困難，因為就連人類專家也會因為背景知識不同，分類的結果也不盡相同。在新聞的研究中，新聞事件的產生時間受到許多額外因素的影響，所以每則記事沒辦法構成如下的次數-時間分布圖

 
圖中是五個事件被很多不同記事報導的時間頻率圖，從圖可知，若用電腦判斷還可能分不出那些頂峰屬於哪個事件，而錯估了事件的數量

根據研究，使用階層式聚合分群法搭配時間衰退函數，可以產生最準確的結果。演算法概念是先用階層式聚合分群演算法對記事文件分群，直到記事文件的相關度小於某一門檻值即停止分群動作。接下來再根據分群後的群聚數目預測事件總數。

建立事件摘要的方法
目前建立摘要的方法簡單說就是從描述事件的所有句子(Sentence)中計算每句的重要性，擁有最高重要性的句子就成為這個事件的摘要，句子數量是依照使用者喜好調整的。常使用的方法是詞頻反文句頻(TF-ISF)與機率潛藏與一模型的主題亂度，根據使用者測試，詞頻反文句頻的結果較好，如下表所示：

新聞	人工撰寫	TF-ISF	文字-主題亂度
台北市長選戰	台北市長選戰由馬英九和李應元對決，陳水扁總統為李應元站台，發表台灣腳和香港腳談話批評馬英九，而馬英九也反擊回去	年底台北市長選舉 民進黨台北市長候選人李應元再度出招	全國人民自有公道 年底台北市長選舉
辛樂克颱風	中度颱風辛樂克侵台	中度颱風辛樂克來勢洶洶 中度颱風勒克直撲台灣而來	繼續向西前進 檢視了電線桿還有線路
台灣第十度參與聯合國失敗	台灣第十度參與聯合國失敗	台灣參與聯合國第十度叩關失敗 聯合國總務委員會沒有通過中華民國台灣的入會申請案	提案又被封殺 已經表達對我方善意
國內登革熱疫情上升	國內登革熱疫情持續上升，病例數直逼兩千	登革熱疫情持續發燒 動手清除孳生源	動手清除孳生源 要把蚊子趕盡殺絕
第四屆漫畫博覽會	第四屆漫畫博覽會開幕	漫畫博覽會今天開幕 第四屆漫畫博覽會開幕現場三百多個攤位	漫畫博覽會今天開幕 他甚至開玩笑的說

詞頻反文句頻(Term Frequency multiplied by Inverse Sentence Frequency, TF-ISF)與傳統的TF-IDF類似，但將文件單位縮小成句子，公式如下：

TFISFi,j = (1 + ln cnti,j)*ln(Ms/Mfi)

是索引特徵fiy在文具sj中出現次數，Ms是該事件所有的句子總數，Mfi是有出現fi的句子數(文句頻, Sentence Frequency)。有了TF-ISF我們便能計算每一個句子的重要性分數。

事件呈現方法
Robert B. Allen提出了編年式方法呈現事件(按：類似Plurk)，簡而言之，在時間軸上安置多個事件，每個事件可以點開看到多筆記事的標題，點選標題則可聽到語音檔案。

在語音檢索系統中，使用者可以藉由語音輸入查詢相關文件，一般而言被區分為多個模組，如下圖所示：

內容：

• 語音文件收集、模型訓練、轉寫、特徵抽取：是建置系統的前置作業，必須先收集好需要的文件，成為一個文件資料庫，收集好之後便將此文件資料庫當作模型的訓練語料，如前端語音辨識需要的聲學模型、語言模型，文件檢索核心需要機率式潛藏語意模型，事件分析與擷取需要機率模型、把文件加以轉寫、擷取重要資訊(例如TF-IDF、類專有名詞、其他關鍵詞等)。由於模型訓練需要大量時間，所以必須在離現時完成，供其他元件使用。
• 前端語音辨識：使用者執行語音查詢時的互動單元，與文件收集與模型訓練不同之處在於前端語音辨識需要即時(Real Time)完成，故並非所有便是引擎能勝任。
• 文件檢索核心：牽涉兩個重要議題，一是索引技術，如何表示文件與使用者問句；二是如何衡量文件相關程度。
• 結果之視覺化呈現：檢索結果通常包含多筆資料，必須有組織呈現才能減少使用者的檢索成本。在這篇paper中，以樹狀結構將「類專有名詞」作為類別的節點，進行階層式的表達。另一種方式是如前所述，用時間軸前後順率供使用者瀏覽，理論上兩種方法相輔相成。

展望
語音辨識經常使用隱藏式馬可夫模型(Hidden Marko Model)，可以將記事文件的時間當作是所觀察到的現象，如果利用此模型將事件分析與擷取所要進行的工作，或許是不錯的選擇。

參考資料：語音文件之事件偵測與時間分析─以廣播新聞為例 (其實跟上一篇一樣XD)
注：這兩篇是我看以上論文時所摘錄的重點，圖片均來自該論文中，若有冒犯煩請告知，撰寫的目的是作為我研究的筆記，也希望能促進學術研究與交流風氣，故在Blog上發表，在此深表對研究者的感謝！

繼續閱讀全文　建立中文廣播新聞摘要之研究

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

主題事件的分類(TDT, Topic Detection and Tracking)，五大追蹤方向

1. 文件切割(Story Segmentation)：將依則包含許多新聞的文件切割成許多單獨新聞的文章
2. 主題追蹤(Topic Tracking)：找出新進文件是否與之前主題相關
3. 主題偵測(Topic Detection)：將探討鄉圖主題的文件分類
4. 第一則新聞偵測(First Story Detection)：判斷新進文件是否屬於新的主題或是尚未討論過的主題
5. 連結偵測(Link Detection)：隨意取出兩則文件，判斷此兩則文件是否屬於同一主題

大型語料的主題分析最受矚目的是「自組性語意對應圖(Self-Organizing Semantic Map)」，許多研究使用此方法；另外「機率式潛藏語意分析(Probabilistic Latent Semantic Analysis)」所發展的語意對應圖(Probmap)屬於強大且較新的研究。

文件分類大概有三種主要的方法

1. 階層式聚合分類演算法(Hierarcy Agglomerative Clustering Algorithm)：最基本
2. K-means
3. 變色龍演算法(Chameleon Algorithms)：較新穎

主題(Topic)、事件(Event)與記事(Story)

• 記事代表一段可以提供使用者某種資訊的文字，例如一則新聞
• 事件是某件特定的事，有特定的發生時間與地點，由一個或多個描述相通事情的記事所組成
• 主題是由相關的事件合併而成

除了TF-DIF之外，還有海寧格距離(Hellinger Distance)也可以衡量文件的相關程度。事件偵測有兩個特徵，專有名詞與時間資訊，專有名詞通常分為：人名、地名與組織名，通常專有名詞在文件中比一般詞重要，因此在TF-IDF中，通常會將專有名詞作加權總合。所以會將人名、地名與組織名分開計算，再依照權重與一般詞的關聯加總，產生總體的關聯度。最簡單的方法是若兩篇文獻都有相同的專有名詞，相關程度為1，反之為0。

機率式潛藏語意分析(Probability Latent Semantic Analysis)
自傳統潛藏式語意分析理論而來。傳統潛藏式語意分析使用Singular Value Decomposition的方式，對document-word matrix進行簡化。機率式潛藏語意分析以隨機狀態起始，並以最大期望值來做區域最佳化。因此每次不同隨機狀態起始的結果不同，故可結合多個潛藏語意分析模型做出不同變化的語意分析。

在語料庫訓練下，可以估計主題z產生文件d的機率：P(d|z)，結合各個不同主題上的機率後，便可以得到文件d在所有主題上的機率分布。透過貝氏定理可以計算出給定文件d產生主題z的機率。

P(z|d) = (P(d|z)*P(z))/P(d)~P(d|z)*P(z)

利用機率模型進行事件偵測與時間分析
一個記事(Story)可以用四種資訊表達：When、Who(人與組織名)、Where與What(其他關鍵詞)，但是事件(Event)包含兩個時間資訊(記事開始與記事結束)。其他關鍵詞是用機率式潛藏語意模型的主題亂度(Term Entropy)所找到除了類專有名詞外的關鍵詞。假設這四種資訊相互獨立：

P(story) = P(persons)P(location)P(keywords)P(time)

 
記事的生成模型由四個模型所混合─三類名詞單元與時間戳記，上圖中E代表事件、D代表記事，P、L、K分別表示人、地、其他關鍵字，N是名詞；T是時間。所以每篇記事都有四個向量，一份文件的同個向量可以成為一個list(例如人名表)。接著可以藉由計算每個list在事件中發生的機率，取得記事在事件中發生的機率。

重要事件的過濾
判定新聞室否重要需要許多新聞相關的背景知識，例如顯著性(Prominence)、奇異性(Conflict)與鄰境性(Proximity)等。顯著性代表新聞內容的影響力，探討新聞內容影響哪些層面；奇異性代表這則新聞是否報導若干特意少見的事情；鄰境性代表這則新聞所發生的所在地與接收者是否在地理上相近。這些知識大都以人類知識為基礎，加上主觀的判斷而成，故以統計分析難度較高。

因此使用四個過濾器進行事件重要性過濾：

過濾器	內容	效率
類專有名詞與關鍵詞法	若一事件不包含類專有名詞(人名、地名與組織名)與其他關鍵詞，此事件可能不是描述重要記事的文件，可以刪掉一小部分。	只刪掉6篇，錯誤率0
TF-IDF	若TF-IDF低於某門檻值，此事件可能不是描述重要記事的文件。	錯誤率約1/3
文件在機率式潛藏語意模型之主題亂度法	假設只有兩篇記事文件(記事1與記事2)、三個主題(主題A、主題B與主題C)。記事1在三個主題的涵蓋度都很平均；記事2在主題B的機率很高，另外兩個主題很低，代表記事2與主題B明顯相關。因為記事1分布平均，可推測記事1不是描述重要事件的文件。 亂度越低，代表機率分布越不平均。所以可以設定一個門檻，若主題亂度高過這個門檻，則必須將記事刪除。	錯誤率約2/9
文件相關度法	通常重要事件會有許多記事文件報導，通常使用cosin來測量事件的相關度，相關度越高代表越重要。	錯誤率約1/8

所以其實篩選器誤刪正確文章的機率都蠻高的，不可能疊在一起使用。找出正確事件應該有兩種作法：

1. 先用較好的篩選器篩選(留下有意義的事件記事)，再使用階層式+時間將記事分群找出事件
2. 直接使用機率式模型(PROB)對所有的記事進行分群

新聞實驗的語料庫
基本資料(人工專家產生)：

來源	大陸中央社廣播新聞
範圍	2002/7/1~2002/10/1(CBN2002) 共982篇，平均140.2字
類專有名詞	人名517、地名437、組織名695 (派樹抽詞法)
其他關鍵詞	2000個 (機率式潛藏語意模型主題亂度)
事件數	共59個事件(Event)，286個記事(Story)

藉由專家對語料庫的事件辨別，評比分群與過濾的方法，結果發現階層式聚合分群演算法在文件雜訊較多時，效果並不理想；但使用機率式潛藏語意分析或機率模型，對雜訊的抗拒力較高。當文件數量較少、資訊較明確，階層式聚合分群法的結果將會顯著提升，而機率式潛藏語意分析會因為訓練資料較少，進步幅度受到限制，但機率模型的結果仍然不差。

機率式潛藏語意分析家上時間資訊打亂了詞與文件的關係，所以效果比純粹機率式潛藏語意模型還差；事件偵測結果的好壞與係數初始值設定息息相關，利用機率模型系數的初始職可以得到較佳的結果。

參考資料：語音文件之事件偵測與時間分析─以廣播新聞為例

繼續閱讀全文　新聞事件偵測與時間分析之研究

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

我想第一要感謝的還是我的家人，他們知道我要考試讓我能安心念書，不需要操心家務。特別感謝老爸和老弟，是老爸才讓我抓住這個嘗試的機會，而老弟陪我一起念書(雖然我唸書的時間不多，而且考前的周末我老弟還跟朋友去彰化玩三天兩夜XD)，讓我有共同奮戰的感覺！

  
結果我瘋狂的在我家樓下的門貼上榜文，這是我與老爸的合照XD

第二是感謝文昌爺爺，雖然筆試的時候我沒有拜祂，因為我覺得我準備的不夠，拜祂是一種褻瀆。但是我跟我自己講，如果進了口試，我就有資格拜祂。果然他給我力量，讓我在台大獲取更多的資源，造福社會。口試時我一直帶著祂的御守，一定是因為祂的守護，才能讓我能如此順利…

接下來，要感謝我的老師及主管

• 政大的老闆：他給我很多中肯的建議，讓我自己考慮，也使我深深覺得老闆對學生開明的態度幾集體會到他的關愛。他對我說，如果光就名字來說，這兩間學校真的差不多，但是你去那裡勢必多花一年，所以你必須思考這一年是否值得…
• 研究所導師尚孝純老師：我想我能上，有超過一半的原因是尚老師幫我寫的推薦信。老師對我說，學校只是一個同學互動的平台，他告訴我我現在帶著政大的嫁妝，擁有一年研究生的基礎，這是比其他考生來說還更有優勢的。他也很鼓勵我追逐自己的夢想，也給了很多重要的資訊，包括政大推的服務創新、老師在面試時的心態以及書審資料排版的建議…
• 輔大的林文修、吳怡瑾老師：老師們聽到我能有運用兩間學校資源的機會，義不容辭地成為我書審資料的推薦人。真的好感動，離開學校這麼久了，老師們都還是如此熱情，真不愧是我當年覺得的恩師…其實真的覺得輔大好有人情味，這是在很多地方所感受不到的。之前一直說要找機會回學校找老師，到現在都還沒回去，也讓我覺得很對不起他們。
• 微軟的主管Rick：這學期真的承蒙他幫很多忙，不論是雲端運算的演講還是這件事。Rick在facebook聽到我的消息，也是責無旁貸地留下他的聯絡資料，當我的推薦人幫我背書。說真的，這種一臂之力的幫助在這樣重要關頭真的很溫馨，這是我所不敢奢求的，也希望Rick能一切順利…

我政大的夥伴們

• Deduce：你那天的「十幾個人只有三個」一番話，給我很多啟示，讓我在心裡對你說，你認識的第四個人就在你眼前！
• 阿金：你給我許多寶貴的資訊、義不容辭地答應幫我模擬面試(雖然後來因為我時間不夠)，還花了很多時間回答我因為擔心而語無倫次的爛問題，寫mail給我。真的心裡除了感激，我不知道怎麼說才好…
• 小白：你一樣給我許多建議，而且要不是你我可能沒辦法這麼有決心應戰，說好的「同學」，你會一直是我的夥伴。
• Aki：雖然平常在學校講到話的機會不多，但是那陣子你真的幫我大忙，我一輩子也不會忘記。你不只給我中央的那個有用的BBS，還幫我發問，跟我分享面試的經驗以及可能的關卡…雖然最後好像沒有猜中，但是你的熱心讓我很感動！
• 阿塞、Demon、花花與一個學長：你們幫我模擬面試真的太感人了！阿塞的問題好犀利：「你說你想走技術為什麼不報資工」讓我囧了三天。也是因為你們的面試讓我回家仔細思考，才能把在書審資料寫出我想表達的東西，也才能在真正面試表現得這麼順利！另外某個學長的一席話「政大同學都在看，就像王建民一樣大家都會較好」給我很大的鼓勵，那時也讓我覺得我一定會讓你們叫好的！(btw某學長是誰呢…我還是不知道他名字XD)
• 柳橙：那天要走的時候在圖書館前面遇到，你跟我說你想之後很難看到我，然後用簡單的一句話破解了阿塞給我的難題，讓我信心滿滿！

資種的夥伴們

• 神秘人：你堅持不透露姓名，我也就順從你了！感謝你提供研究所的經驗分享資訊，寫了好幾封的mail。但最讓我感動的其實是放榜的後續幫忙，你很熱心地幫我查了好幾次時間，提供我非常多重要的資料。也許你不知道，我真的很佩服你，希望你在未來也一切順利，往後的日子請多多指教了！
• 瑋凌：你很用心！除了伴我考試的御守，還寫了mail跟我分析了很多對考試的重要資訊，真的對我很有幫助。我想有些感謝是難以用一兩句話表達的，這讓我不知道該怎麼辦。總之希望你一切順利，如果有需要幫忙盡管跟我說吧！
• 小熊：謝謝你去台南特別帶的禮物，考試時我一直帶著，果然非常的具有加持的效果！雖然後來你好像忙到爆炸了，不過我真的很感謝你喔^^
• 桂慈：你每次的用心都讓我驚艷！小小的祝福卡片，卻都能給我很大的鼓勵。你知道考試的時候我一直把那些祝福放在我的資料夾中嗎？口試的時候也是一樣。當你說「你已經在榜上看見我名字」，以及每次告訴你好消息你的回應，都能讓我感受到你那炙熱的眼神。
• 可樂：一起擔任春酒的主持人，真的很感謝你對我準備考試的體諒和包容，以及每次每次的祝福。記得有一次你還傳進訊跟我說唸書加油…讓我覺得受到很多很多的支持，果然一句鼓勵可以撼動宇宙阿！跟你合作是段很快樂的時光，真的。
• 浩威：「考試加油？」讓我露了餡，果然是金頭腦那麼有觀察力，真是高深莫測。還有口試時你一樣給我祝福，以及最後送我的鑰匙圈紀念品(雖然有人說那不好看，可是我覺得那跟我很合XD)。總之有金頭腦的祝福果然大大加持阿~
• 尉池：考前的加油簡訊，以及一起念書的短暫時光(抱歉那天一直在嘴砲害你補習遲到)，很謝謝你的鼓勵，也希望你未來一切順利。

我的老夥伴們

• 小觀：那天吃飯謝謝你給我很多非常寶貴的經驗，但最讓我感動的是你晚上還寫mail來關心我、幫我想對策，過幾天也打電話來問我情況。這種關心讓我覺得很滿足，雖然最後沒有採取你的建議，可是我已經充分地感覺到你那種強烈的支持。
• 小朱：雖然是我千里迢迢的到土城跟你借MIS，但是跟你講話就讓我覺得充滿活力，就像以前一起考試一樣，好有信心！總之希望你也能一切順利。
• 玉璋：考前，你的關心總是少不了，而口試完後我跟你說我的情況，你也告訴我不要想太多。真的很感謝你的那種友情贊助！一樣希望你今年考試順利:D
• 尉伶：剛放寒假就找你幫忙，當時剛動完手術，你說你其實可以幫我把書送來台北…讓我聽了很感動！那天原本要請你吃飯的，可惜你堅持要各付各XD雖然後來比較少聯絡，但我深深的覺得，認識你真好！btw後來我還特別到圖書館把那天借的書寫了我已經考上了，並留下mail，希望能幫助輔大的學弟妹，也算是還願…
• 小廖：你一樣阿，總是少不了你的祝福！而且你還會自己去幫我查榜，也太感人了吧XD今年你也要考試了，我對你很有信心，到時候我們再一起慶祝吧!!
• 惠菁：雖然我們不是很熟(可是大一迎新好像還在同一組XD)，但真的很感謝你提供的老師資料，以及撥冗回答我問題。現在容我叫你一聲學姊囉！

還有，很多口頭或MSN、FB上鼓勵我的朋友：歐萌、柏均、103、章威、亞霖、育聖、阿掰、雋文、彥璋、庭宇、蘇宅、國傑…以及默默為我祈禱的你，我知道你一直在那裡。

上一篇：99台大資管所榜眼上榜心得：口試篇

繼續閱讀全文　99台大資管所榜眼上榜心得：感恩篇

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