文本表示綜述及其改進
主要內(nèi)容:
現(xiàn)階段文本表示的主要技術
已有的工作對我們的啟發(fā)
已有的改進工作的介紹
我們的改進(可行性?)
計算機如何解決文本分類問題?
一個中文文本表現(xiàn)為一個由漢字和標點符號組成的字符串，由字組成詞，由詞組成短語，進而形成句、段、節(jié)、章、篇等結(jié)構(gòu)。
自然語言理解
借助統(tǒng)計學這個有力的工具
現(xiàn)階段文本表示的主要技術
向量空間模型
特征項的粒度選擇
預處理去除停用詞
特征選擇
特征項權(quán)重計算
特征重構(gòu)
VSM
向量空間模型（Vector Space Model）Salton的概念
文檔（Document）
特征項（Term）
特征項的權(quán)重（Term Weight）
向量空間模型（VSM）
相似度（Similarity）
特征項的粒度
字
簡單高效,國家標準GB2312-80 中定義的常用漢字為6763個 .
表示能力比較差，不能獨立地完整地表達語義信息。
詞
詞是最小的能夠獨立運用的語言單位 .
詞的個數(shù)在10萬個以上,面臨復雜的分詞問題
特征項的粒度(2)
短語特征
和詞相比頻率更低,表現(xiàn)力更強
概念特征
“爸爸”=“父親”,在自動文摘領域很有幫助
N元組特征
“中國人民銀行”
2元組: 中 中國 國人 人民 民銀 銀行 行
主要用于自動糾錯.
特征項的粒度(3)
重復串特征?
分詞程序的統(tǒng)計逼進
新的粒度?
David Lewis的結(jié)論:
單個word作為特征效果好于phrase和cluster of phrase以及cluster of words.
phrase的低頻率和高同義性(synonymy)大大的影響其性能 ;(抵消了phrase的低歧義性的好處) 而cluster of words的效果不佳主要的原因應該還是訓練集不夠大的緣故 .
預處理去除停用詞
虛詞,助詞出現(xiàn)頻率高,對于表達意義的貢獻卻不大.
如:“著” 、“了” 、“過” 、“的” 、“地” 、“得”
統(tǒng)計詞頻時過濾掉這些停用詞.
停用詞無用嗎?
紅樓夢作者考證
李賢平 1987
利用120回中每一回用的47個虛字（之，其，或，亦……，呀，嗎，咧，罷……；的，著，是，在，……；可，便，就，但，……，兒等）出現(xiàn)的頻率進行聚類.
前80回基本聚成一類,后40回聚類情況較零散.
得出結(jié)論:
前80回與后40回之間有交叉。
前80回是曹雪芹據(jù)《石頭記》寫成，中間插入《風月寶鑒》，還有一些別的增加成分。
后40回是曹雪芹親友將曹雪芹的草稿整理而成，寶黛故事為一人所寫，賈府衰敗情景當為另一人所寫。
特征選擇
目標
表達力強
頻率較高
區(qū)分度高
合理的特征評價函數(shù)
消除干擾,提高分類準確率
特征空間降維,減少運算量
特征選擇(2)
文檔頻次 (DF)
根據(jù)預先設定的閾值去除那些文檔頻次特別低和特別高的特征項。
合理的閾值往往難以得到 !
互信息(MI)
出現(xiàn)頻率差異很大的特征項的互信息大小不具有可比性 !(即低頻特征具有較高的MI)
同時,訓練集中不同類別相差較大時,低頻詞也有較大MI.
實踐證明,互信息方法是效果最差的特征選擇方法!
特征選擇(3)
χ2統(tǒng)計量:用于度量特征項w 和類別C 之間的獨立性
對低頻特征項的區(qū)分效果也不好 !
信息增益(IG):該特征項為整個分類所提供的信息量
將長文檔和短文檔視為等同.頻率信息.
特征選擇性能比較:
特征項權(quán)重計算
布爾權(quán)重
詞頻權(quán)重
TFIDF權(quán)重(為什么?)
權(quán)重計算(2)
TFC權(quán)重: 對TFIDF進行歸一化
LTC權(quán)重:降低TF的作用(最常用)(不區(qū)分長短文章)
熵權(quán)重: (效果)
特征重構(gòu)
LSI：(Latent Semantic Indexing)
一詞多義和多詞一義的等現(xiàn)象使得文本特征項向量中的不同分量之間互相關聯(lián).
LSI 方法 通過矩陣奇異值分解(SVD),將特征項空間中的文本矩陣轉(zhuǎn)換成概念空間中的正交矩陣 ,概念空間中各個特征之間是相互獨立的.
進行奇異值分解過程中信息損失過大，因此在自動文本分類問題中往往性能不佳!
VSM潛在的問題:
長文檔(黃萱菁 )
VSM把文檔看成是文檔空間的一個向量 ,實踐結(jié)果表明對長文檔來說不適宜.長文檔內(nèi)容比較豐富,必須對文檔長度進行正規(guī)化出現(xiàn)問題.解決的辦法是對長文檔進行分割。(如何定義“長”?)
特征項的獨立性假設
如果我們把詞看做特征項,那么詞之間的獨立性即意味著一個詞的上下文信息對于這個詞的信息沒有任何作用!這顯然是與人們的常識相違背的.
思路啟發(fā) 1:特征項順序關系 (卜東波)
中文文本由特征項的頻率及相互的順序表達 .考慮順序信息,必然使用有向指針,使得文本變成復雜的圖結(jié)構(gòu) .由于難以定義合理的距離函數(shù)描述兩個由圖結(jié)構(gòu)表示的文本是否相似,因此不得不舍棄順序信息 .
要盡可能的考慮特征項間的順序關系.
思路啟發(fā) 2:上下文信息貢獻 (魯松)
引入信息增益方法確定上下文各位置的信息量后，構(gòu)造上下文位置信息量函數(shù)，最終通過多項式積分確定85%信息量的上下文邊界，即漢語核心詞語最近距離[-8,+9]和英文[-16,+13]位置之間的上下文范圍。
要盡可能的考慮特征項的上下文貢獻.
思路啟發(fā) 3:分類器集成
分類器集成思想的提出:
不同的分類算法往往適用于不同的特定問題,沒有的分類算法.
希望把不同的方法綜合在一起,盡可能的減小錯誤的發(fā)生.
分類器集成(2)
Condorcet陪審團定律 (1785)
對于二分問題,假設每一個分類器的錯誤率都小于0.5,那么一組相互獨立分類器采用投票方式得到的分類結(jié)果,其錯誤率將小于每個單個分類器的錯誤率.
設P=0.3,L=3,得到結(jié)果僅為0.216
設P=0.3,L=5,得到結(jié)果僅為0.163
…
設P=0.3,L=21,得到結(jié)果僅為0.026
分類器集成(3)
前提條件是要證明不同的分類器之間具有獨立性(實際問題中常常轉(zhuǎn)化為不同分類器的錯誤之間具有獨立性). 困難!
實際情況中,分類器的準確性和獨立性之間存在一個折中: 分類器越是準確,他們間獨立性就越差!
啟發(fā):采用投票方式的多次判別有利于提高分類的準確性,(召回率??)但是分類器集成的方法卻效果不明顯.考慮用一個分類器對文檔的不同部分分塊判別,不同塊間的錯誤相互獨立是一個比較容易令人接受的假設.
考慮了特征項間關系(context)的分類算法的介紹:
最重要的是RIPPER算法(Cohen 1995)和sleeping-experts算法(Freund 1997).
兩個算法的共同優(yōu)點:
分類算法是線性或者是亞線性的;
文本的直接的表示方法:表示成有序特征項的鏈(完全不同于VSM的表示方式) ;
特征項的context信息影響分類結(jié)果;
context在分類器的訓練過程同時生成,不需要額外的context生成算法.
(在對于短文本分類問題中,詞頻不具有統(tǒng)計信息,更適于規(guī)則判定)
RIPPER算法:
RIPPER算法是一個松弛的規(guī)則匹配算法,context就是不同的規(guī)則.
訓練得到一個規(guī)則集合
規(guī)則集合可以看做是若干個規(guī)則的析取(或)表達式
每個規(guī)則是若干個特征項的合取(與)表達式
每個規(guī)則的特征項之間是沒有次序的,每個特征項可以出現(xiàn)在文檔的任何地方
規(guī)則總是和分類正相關的.
RIPPER算法的基本思想 :
訓練過程分為兩部分 :
根據(jù)貪心原則(greedy)采用啟發(fā)式方法(heuristics)利用信息增益的手段構(gòu)造一個最初的規(guī)則集合 ;
通過一個優(yōu)化過程剪除(prune)規(guī)則集合并提高規(guī)則集合的準確性.
分類過程:
文檔滿足某個規(guī)則就認為它屬于該類.
RIPPER算法的問題
訓練過程復雜(啟發(fā)式算法);
新的文本表示方法,忽略了測試文檔中特征項的頻率信息;
不考慮特征項在文檔中的位置,無法利用多次判別提高分類的準確性了.
如何調(diào)整規(guī)則的次序?
sleeping-experts算法
sleeping-experts是一個嚴格的規(guī)則匹配算法,context稱為稀疏短語(sparse phrase) .
定義:一個有序的N個詞組成的鏈表,這N個詞不需要連續(xù)出現(xiàn)因此稱為稀疏短語.
每個稀疏短語就是一個expert,如果滿足這個稀疏短語就是該expert做出了一個判定.
sleeping-experts算法的基本思想
同時滿足的N個experts之間不僅僅是簡單的voting方法,而是利用對不同experts的效果的估計調(diào)整其加權(quán)系數(shù).
訓練過程中,疊代依次生成稀疏短語,若該稀疏短語對該類是起正向作用,則擴大其加權(quán)系數(shù);反之,縮小其加權(quán)系數(shù).
Sleeping-experts算法的問題
Context定義過于嚴格?影響召回率?
算法的簡化?沒有特征選擇,直接生成稀疏矩陣,使得experts的數(shù)目極多!
分類結(jié)果
我們的想法:
文章的傾向性判定.
基于context(相對位置)的分類方法改進.
文章的傾向性判定
利用核心詞將文章分塊,以多次判定.
準確率提高,(召回率為平均召回率?)
如何選取核心詞?
表達力強,頻率較高,區(qū)分度低(實詞?)
方法:TFDF原則
參數(shù)調(diào)整:
對每一個“塊”的分類方法
基于規(guī)則(更快)
基于中高頻詞構(gòu)造規(guī)則.
松弛的規(guī)則,保證一定的召回率;
多次判定提高準確率.
SVM(更準)
對伊拉克戰(zhàn)爭的傾向性
手工建立訓練集
希望SVM直接分類,基于規(guī)則分塊分類,SVM分塊分類結(jié)果比較.
基于context的分類方法
用特征的組合代替原有的特征
特征的組合可以反映特征間的序.
組合特征出現(xiàn)的頻率將大大降低,不再具有統(tǒng)計意義,因此考慮將一個組合特征看做一個規(guī)則.
sleeping-experts算法的簡化和改進
稀疏短語內(nèi)部可以沒有次序關系.
采用簡單的voting方法,不考慮復雜的加權(quán)策略.
主要內(nèi)容:
現(xiàn)階段文本表示的主要技術
已有的工作對我們的啟發(fā)
已有的改進工作的介紹
我們的改進(可行性?)
計算機如何解決文本分類問題?
一個中文文本表現(xiàn)為一個由漢字和標點符號組成的字符串，由字組成詞，由詞組成短語，進而形成句、段、節(jié)、章、篇等結(jié)構(gòu)。
自然語言理解
借助統(tǒng)計學這個有力的工具
現(xiàn)階段文本表示的主要技術
向量空間模型
特征項的粒度選擇
預處理去除停用詞
特征選擇
特征項權(quán)重計算
特征重構(gòu)
VSM
向量空間模型（Vector Space Model）Salton的概念
文檔（Document）
特征項（Term）
特征項的權(quán)重（Term Weight）
向量空間模型（VSM）
相似度（Similarity）
特征項的粒度
字
簡單高效,國家標準GB2312-80 中定義的常用漢字為6763個 .
表示能力比較差，不能獨立地完整地表達語義信息。
詞
詞是最小的能夠獨立運用的語言單位 .
詞的個數(shù)在10萬個以上,面臨復雜的分詞問題
特征項的粒度(2)
短語特征
和詞相比頻率更低,表現(xiàn)力更強
概念特征
“爸爸”=“父親”,在自動文摘領域很有幫助
N元組特征
“中國人民銀行”
2元組: 中 中國 國人 人民 民銀 銀行 行
主要用于自動糾錯.
特征項的粒度(3)
重復串特征?
分詞程序的統(tǒng)計逼進
新的粒度?
David Lewis的結(jié)論:
單個word作為特征效果好于phrase和cluster of phrase以及cluster of words.
phrase的低頻率和高同義性(synonymy)大大的影響其性能 ;(抵消了phrase的低歧義性的好處) 而cluster of words的效果不佳主要的原因應該還是訓練集不夠大的緣故 .
預處理去除停用詞
虛詞,助詞出現(xiàn)頻率高,對于表達意義的貢獻卻不大.
如:“著” 、“了” 、“過” 、“的” 、“地” 、“得”
統(tǒng)計詞頻時過濾掉這些停用詞.
停用詞無用嗎?
紅樓夢作者考證
李賢平 1987
利用120回中每一回用的47個虛字（之，其，或，亦……，呀，嗎，咧，罷……；的，著，是，在，……；可，便，就，但，……，兒等）出現(xiàn)的頻率進行聚類.
前80回基本聚成一類,后40回聚類情況較零散.
得出結(jié)論:
前80回與后40回之間有交叉。
前80回是曹雪芹據(jù)《石頭記》寫成，中間插入《風月寶鑒》，還有一些別的增加成分。
后40回是曹雪芹親友將曹雪芹的草稿整理而成，寶黛故事為一人所寫，賈府衰敗情景當為另一人所寫。
特征選擇
目標
表達力強
頻率較高
區(qū)分度高
合理的特征評價函數(shù)
消除干擾,提高分類準確率
特征空間降維,減少運算量
特征選擇(2)
文檔頻次 (DF)
根據(jù)預先設定的閾值去除那些文檔頻次特別低和特別高的特征項。
合理的閾值往往難以得到 !
互信息(MI)
出現(xiàn)頻率差異很大的特征項的互信息大小不具有可比性 !(即低頻特征具有較高的MI)
同時,訓練集中不同類別相差較大時,低頻詞也有較大MI.
實踐證明,互信息方法是效果最差的特征選擇方法!
特征選擇(3)
χ2統(tǒng)計量:用于度量特征項w 和類別C 之間的獨立性
對低頻特征項的區(qū)分效果也不好 !
信息增益(IG):該特征項為整個分類所提供的信息量
將長文檔和短文檔視為等同.頻率信息.
特征選擇性能比較:
特征項權(quán)重計算
布爾權(quán)重
詞頻權(quán)重
TFIDF權(quán)重(為什么?)
權(quán)重計算(2)
TFC權(quán)重: 對TFIDF進行歸一化
LTC權(quán)重:降低TF的作用(最常用)(不區(qū)分長短文章)
熵權(quán)重: (效果)
特征重構(gòu)
LSI：(Latent Semantic Indexing)
一詞多義和多詞一義的等現(xiàn)象使得文本特征項向量中的不同分量之間互相關聯(lián).
LSI 方法 通過矩陣奇異值分解(SVD),將特征項空間中的文本矩陣轉(zhuǎn)換成概念空間中的正交矩陣 ,概念空間中各個特征之間是相互獨立的.
進行奇異值分解過程中信息損失過大，因此在自動文本分類問題中往往性能不佳!
VSM潛在的問題:
長文檔(黃萱菁 )
VSM把文檔看成是文檔空間的一個向量 ,實踐結(jié)果表明對長文檔來說不適宜.長文檔內(nèi)容比較豐富,必須對文檔長度進行正規(guī)化出現(xiàn)問題.解決的辦法是對長文檔進行分割。(如何定義“長”?)
特征項的獨立性假設
如果我們把詞看做特征項,那么詞之間的獨立性即意味著一個詞的上下文信息對于這個詞的信息沒有任何作用!這顯然是與人們的常識相違背的.
思路啟發(fā) 1:特征項順序關系 (卜東波)
中文文本由特征項的頻率及相互的順序表達 .考慮順序信息,必然使用有向指針,使得文本變成復雜的圖結(jié)構(gòu) .由于難以定義合理的距離函數(shù)描述兩個由圖結(jié)構(gòu)表示的文本是否相似,因此不得不舍棄順序信息 .
要盡可能的考慮特征項間的順序關系.
思路啟發(fā) 2:上下文信息貢獻 (魯松)
引入信息增益方法確定上下文各位置的信息量后，構(gòu)造上下文位置信息量函數(shù)，最終通過多項式積分確定85%信息量的上下文邊界，即漢語核心詞語最近距離[-8,+9]和英文[-16,+13]位置之間的上下文范圍。
要盡可能的考慮特征項的上下文貢獻.
思路啟發(fā) 3:分類器集成
分類器集成思想的提出:
不同的分類算法往往適用于不同的特定問題,沒有的分類算法.
希望把不同的方法綜合在一起,盡可能的減小錯誤的發(fā)生.
分類器集成(2)
Condorcet陪審團定律 (1785)
對于二分問題,假設每一個分類器的錯誤率都小于0.5,那么一組相互獨立分類器采用投票方式得到的分類結(jié)果,其錯誤率將小于每個單個分類器的錯誤率.
設P=0.3,L=3,得到結(jié)果僅為0.216
設P=0.3,L=5,得到結(jié)果僅為0.163
…
設P=0.3,L=21,得到結(jié)果僅為0.026
分類器集成(3)
前提條件是要證明不同的分類器之間具有獨立性(實際問題中常常轉(zhuǎn)化為不同分類器的錯誤之間具有獨立性). 困難!
實際情況中,分類器的準確性和獨立性之間存在一個折中: 分類器越是準確,他們間獨立性就越差!
啟發(fā):采用投票方式的多次判別有利于提高分類的準確性,(召回率??)但是分類器集成的方法卻效果不明顯.考慮用一個分類器對文檔的不同部分分塊判別,不同塊間的錯誤相互獨立是一個比較容易令人接受的假設.
考慮了特征項間關系(context)的分類算法的介紹:
最重要的是RIPPER算法(Cohen 1995)和sleeping-experts算法(Freund 1997).
兩個算法的共同優(yōu)點:
分類算法是線性或者是亞線性的;
文本的直接的表示方法:表示成有序特征項的鏈(完全不同于VSM的表示方式) ;
特征項的context信息影響分類結(jié)果;
context在分類器的訓練過程同時生成,不需要額外的context生成算法.
(在對于短文本分類問題中,詞頻不具有統(tǒng)計信息,更適于規(guī)則判定)
RIPPER算法:
RIPPER算法是一個松弛的規(guī)則匹配算法,context就是不同的規(guī)則.
訓練得到一個規(guī)則集合
規(guī)則集合可以看做是若干個規(guī)則的析取(或)表達式
每個規(guī)則是若干個特征項的合取(與)表達式
每個規(guī)則的特征項之間是沒有次序的,每個特征項可以出現(xiàn)在文檔的任何地方
規(guī)則總是和分類正相關的.
RIPPER算法的基本思想 :
訓練過程分為兩部分 :
根據(jù)貪心原則(greedy)采用啟發(fā)式方法(heuristics)利用信息增益的手段構(gòu)造一個最初的規(guī)則集合 ;
通過一個優(yōu)化過程剪除(prune)規(guī)則集合并提高規(guī)則集合的準確性.
分類過程:
文檔滿足某個規(guī)則就認為它屬于該類.
RIPPER算法的問題
訓練過程復雜(啟發(fā)式算法);
新的文本表示方法,忽略了測試文檔中特征項的頻率信息;
不考慮特征項在文檔中的位置,無法利用多次判別提高分類的準確性了.
如何調(diào)整規(guī)則的次序?
sleeping-experts算法
sleeping-experts是一個嚴格的規(guī)則匹配算法,context稱為稀疏短語(sparse phrase) .
定義:一個有序的N個詞組成的鏈表,這N個詞不需要連續(xù)出現(xiàn)因此稱為稀疏短語.
每個稀疏短語就是一個expert,如果滿足這個稀疏短語就是該expert做出了一個判定.
sleeping-experts算法的基本思想
同時滿足的N個experts之間不僅僅是簡單的voting方法,而是利用對不同experts的效果的估計調(diào)整其加權(quán)系數(shù).
訓練過程中,疊代依次生成稀疏短語,若該稀疏短語對該類是起正向作用,則擴大其加權(quán)系數(shù);反之,縮小其加權(quán)系數(shù).
Sleeping-experts算法的問題
Context定義過于嚴格?影響召回率?
算法的簡化?沒有特征選擇,直接生成稀疏矩陣,使得experts的數(shù)目極多!
分類結(jié)果
我們的想法:
文章的傾向性判定.
基于context(相對位置)的分類方法改進.
文章的傾向性判定
利用核心詞將文章分塊,以多次判定.
準確率提高,(召回率為平均召回率?)
如何選取核心詞?
表達力強,頻率較高,區(qū)分度低(實詞?)
方法:TFDF原則
參數(shù)調(diào)整:
對每一個“塊”的分類方法
基于規(guī)則(更快)
基于中高頻詞構(gòu)造規(guī)則.
松弛的規(guī)則,保證一定的召回率;
多次判定提高準確率.
SVM(更準)
對伊拉克戰(zhàn)爭的傾向性
手工建立訓練集
希望SVM直接分類,基于規(guī)則分塊分類,SVM分塊分類結(jié)果比較.
基于context的分類方法
用特征的組合代替原有的特征
特征的組合可以反映特征間的序.
組合特征出現(xiàn)的頻率將大大降低,不再具有統(tǒng)計意義,因此考慮將一個組合特征看做一個規(guī)則.
sleeping-experts算法的簡化和改進
稀疏短語內(nèi)部可以沒有次序關系.
采用簡單的voting方法,不考慮復雜的加權(quán)策略.