面向高效越南語分詞的有監(jiān)督集成學習框架

劉伍穎,王 琳

1(廣東外語外貿(mào)大學 語言工程與計算實驗室,廣州 510420)

2(上海外國語大學 賢達經(jīng)濟人文學院，上海 200083)

1 引 言

類似于泰國語、日本語和漢語,越南語書面文本中詞與詞之間也沒有明顯的分隔符.因此,在上述亞洲語言信息處理中,詞邊界自動識別至關(guān)重要[1].相應(yīng)的分詞算法在各種自然語言處理軟件中有著廣泛的應(yīng)用[2].越南語文本的自然形式單位是Ting,相當于語言學中的一個音節(jié).而越南語文本的基本語義單位是詞,也就是最小獨立表義的語言單元.正是由于自然形式單位與基本語義單位不完全一一映射,因此采用計算機處理越南語文本的意義時,需要為每個基本語義單位識別形式上的邊界,也就是越南語分詞.例如一個原始未分詞的越南語句子(Cái làm nênhdcua game chính làchan包含13個Ting.與之對應(yīng)的分詞形式(Cái làm_nêncua game chính là則包含8個詞,其中詞làm_nên是雙音節(jié)詞,而詞和則是三音節(jié)詞.

從上述例句可以看出除標點符號外,越南語文本可視為一個連續(xù)的音節(jié)序列,而且每兩個連續(xù)音節(jié)之間都由一個空格符分隔.在原始文本中,該空格符屬于一種重載標識符,即在詞內(nèi)作為音節(jié)連接符,而在詞間作為單詞分隔符.基于此視角,我們將越南語分詞任務(wù)重新定義為針對全部空格符的二值分類問題.在分詞結(jié)果中,若某個空格符是詞內(nèi)連接符,就替換輸出一個下劃線(′_′);若某個空格符是詞間分隔符,就將其以空格(′ ′)的形式予以保留.

2 相關(guān)研究工作

越南語分詞是越南語信息處理的基本步驟,該步效果的優(yōu)劣制約著各層次信息處理應(yīng)用的效能.例如某個詞被錯分,隨后的命名實體識別、詞性標注、句法分析和語義角色標注等就會受到影響[3].因此,研究者很早就開始關(guān)注越南語分詞問題,迄今已提出了多種有效的越南語分詞算法[4].最早的分詞算法主要是基于詞典的,包括最大匹配(Maximum Matching,MM)算法和逆向最大匹配(Reverse Maximum Matching,RMM)算法.基于詞典的算法易于實現(xiàn),但其性能很大程度上取決于詞典的規(guī)模和質(zhì)量[5,6].之后,有些高級機器學習方法將分詞視為序列標注問題,例如最大熵(Maximum Entropy,ME)、條件隨機場(Conditional Random Fields,CRF)和支持向量機(Support Vector Machines,SVM)等方法在越南語分詞中取得了較好的效果.已有的研究成果包括:結(jié)合加權(quán)有限狀態(tài)機和神經(jīng)網(wǎng)絡(luò)的分詞模型[7];構(gòu)建了10MB的原始語料庫,使用N-gram信息優(yōu)化分詞概率總和[8];使用ME框架和迭代算法對標注語料庫進行訓(xùn)練[9];使用CRF和SVM模型進行分詞[10]等.

近來,混合方法和面向具體任務(wù)(如文本分類或自動問答)的分詞研究逐漸興起,同時也有研究者嘗試利用搜索引擎構(gòu)建大規(guī)模語料庫進行分詞.為解決分詞歧義問題,還出現(xiàn)了結(jié)合有限狀態(tài)機、正則表達式和最大匹配技術(shù)的混合算法,并據(jù)此實現(xiàn)了一個高精度的越南語分詞器(vnTokenizer)[11];面向文本分類,不使用標注訓(xùn)練語料庫,使用商業(yè)搜索引擎直接抽取統(tǒng)計信息,用遺傳算法尋找最合理的分詞結(jié)果[12];還有把詞性標簽作為一種附加資源用于分詞算法中[13,14].

圖1 有監(jiān)督集成學習框架Fig.1 Supervised ensemble learning framework

還有研究表明集成學習[15]具有統(tǒng)計、計算和表示的優(yōu)勢[16].在垃圾郵件過濾[17]和文本分類[18]研究中,集成學習可以提高現(xiàn)有算法的性能.利用集成學習的上述優(yōu)勢,我們提出一套完整的有監(jiān)督集成學習(Supervised Ensemble Learning,SEL)框架,作為集成各種已有分詞算法的元框架.在此框架下,我們設(shè)計實現(xiàn)了一種基于有監(jiān)督集成學習的分詞(SEL-based Word Segmentation,SELWS)算法.

3 有監(jiān)督集成學習

3.1 框架

為了綜合發(fā)揮各種分詞算法的優(yōu)勢,我們提出一套完整的有監(jiān)督集成學習框架.如圖1所示,該框架總體上包括一個詞匯形態(tài)處理主體部分外加文檔形態(tài)和字符形態(tài)兩個預(yù)處理部分.

文檔形態(tài)處理負責分析越南語文檔的篇章形態(tài),通過分段器和分句器自動將越南語文檔處理成段落和句子組成的結(jié)構(gòu)化篇章.

字符形態(tài)處理負責對每個句子進行字符形態(tài)分析.其中:

1)字符清洗器主要進行句子前置空格、句后空格、連續(xù)空格、特殊字符等進行處理;

2)大小寫字符轉(zhuǎn)換器主要針對越南語字母大小寫進行形態(tài)轉(zhuǎn)換,越南語大小寫字母映射如表1所示.

表1 越南語大小寫字母映射Table 1 Vietnamese letter mapping between upper and lower

3)新舊雙元音字符轉(zhuǎn)換器是越南語形態(tài)處理特有的,主要解決復(fù)合韻母等義異形拼寫轉(zhuǎn)換問題,越南語復(fù)合韻母映射如表2所示.

表2 越南語復(fù)合韻母映射Table 2 Vietnamese compound vowel mapping

詞匯形態(tài)處理采用類似加權(quán)投票的策略,根據(jù)Bayesian條件概率模型,實現(xiàn)有監(jiān)督集成分詞算法.該主體部分主要包含n個<基本分詞器-有監(jiān)督學習器>對和一個集成分詞器.對于每個基本分詞器,配置一個有監(jiān)督學習器來接收分詞標準答案和相應(yīng)基本分詞器產(chǎn)生的自動分詞結(jié)果,并從這對文本<答案-自動分詞結(jié)果>中學習出一個有監(jiān)督集成模型.該模型被存儲成二元音節(jié)頻率索引(Bigram Ting Frequency Index,BTFI)數(shù)據(jù)結(jié)構(gòu).集成分詞器根據(jù)BTFI集成多個基本分詞器的分詞結(jié)果并輸出最終預(yù)測.

用于存儲有監(jiān)督集成模型的BTFI是一種Hash表數(shù)據(jù)結(jié)構(gòu).如圖2所示,每個表項是鍵-值對.其中,每個鍵TiTj表示一個連續(xù)兩音節(jié)的序列,相應(yīng)的值由四個整型數(shù)值組成.整型數(shù)值fc(·)表示正確預(yù)測次數(shù),整型數(shù)值fm(·)表示錯誤預(yù)測次數(shù).符號(′_′)代表連續(xù)兩音節(jié)Ti和Tj屬于同一個詞,符號(′ ′)代表連續(xù)兩音節(jié)Ti和Tj不屬于同一個詞.Hash函數(shù)hash(TiTj)將TiTj序列映射到四個整型數(shù)值的存儲地址.

圖2 二元音節(jié)頻率索引Fig.2 Bigram ting frequency index

在BTFI數(shù)據(jù)結(jié)構(gòu)支持下,我們設(shè)計并實現(xiàn)了一種基于有監(jiān)督集成學習的分詞(SELWS)算法,該算法包括有監(jiān)督集成學習(selearners)和有監(jiān)督集成預(yù)測(sepredictor)兩個函數(shù).在有監(jiān)督集成預(yù)測時,利用有監(jiān)督集成學習得到的歷史分詞準確率作為集成加權(quán)系數(shù).

3.2 算法

我們提出的SELWS算法將有監(jiān)督集成學習過程實現(xiàn)成一個索引更新過程,將有監(jiān)督預(yù)測過程實現(xiàn)成一個索引檢索過程.圖3為SELWS算法的有監(jiān)督集成學習偽碼,當輸入一個已知分詞標準答案文本(sst)時,selearners函數(shù)調(diào)用n個基本分詞器得到n個自動分詞結(jié)果,通過對比自動分詞結(jié)果和標準答案來更新BTFI中的數(shù)值.

圖3 有監(jiān)督集成學習偽碼Fig.3 Pseudocode of supervised ensemble learners

SELWS算法的有監(jiān)督集成預(yù)測偽碼如圖4所示,當輸入一個待分詞文本(ust)時,sepredictor函數(shù)執(zhí)行下列步驟:(I)調(diào)用n個基本分詞器得到n個自動分詞結(jié)果;(II)檢索當前BTFI并根據(jù)歷史分詞準確率按公式(1)為每個空格符(′·′)計算出一個概率得分;(III)按公式(2)集成n個概率得分形成一個最終得分,使用一個固定閾值(score=0)為每個空格符做出最終的二值預(yù)測.

(1)

(2)

圖4 有監(jiān)督集成預(yù)測偽碼Fig.4 Pseudocode of supervised ensemble predictor

SELWS算法是一個獨立于任何具體分詞算法的元算法,其時空復(fù)雜度主要取決于selearners和sepredictor函數(shù)中循環(huán)時間開銷,以及BTFI的存儲空間開銷.根據(jù)Hash函數(shù),BTFI更新和檢索的時間開銷都是常數(shù)量級.又由于索引文件本身就是壓縮存儲的,因此BTFI是空間高效的.而且BTFI存儲空間和訓(xùn)練文本中連續(xù)兩個音節(jié)的數(shù)量成正比,與訓(xùn)練文本數(shù)量無關(guān).SELWS算法的最大空間復(fù)雜度O(np)和最大時間復(fù)雜度O(nq)在實際的自然語言處理應(yīng)用中都是可以接受的.其中n表示基本分詞器數(shù)量,通常是一個較小數(shù)值;p表示兩個連續(xù)音節(jié)的數(shù)量;q表示文本總數(shù).

4 實 驗

4.1 實現(xiàn)

根據(jù)SELWS算法,我們實現(xiàn)了一個有監(jiān)督集成學習分詞器(SELSegmenter,SEL),該分詞器集成了三個基本分詞器:vnTokenizer(VNT),RMMSegmenter(RMM)和MMSegmenter(MM).其中VNT使用了混合分詞算法,RMM和MM分別通過基于詞典的逆向最大匹配算法和正向最大匹配算法實現(xiàn).在實現(xiàn)SEL時,對VNT,RMM和MM都進行了有監(jiān)督詞典擴展,也就是在訓(xùn)練和測試之間增加了一個有監(jiān)督詞典擴展訓(xùn)練步驟,將訓(xùn)練語料中的全部詞匯作為詞典擴展添加到原有的詞典當中.

我們還實現(xiàn)了一個簡單有監(jiān)督集成學習分詞器(SSELSegmenter,SSEL),采用簡單多數(shù)投票策略集成上述VNT、RMM和MM.由于被集成的三個基本分詞器的輸出是二值結(jié)果,因此每次預(yù)測時一定存在兩個基本分詞器輸出結(jié)果一致的情況,我們的SSEL就采用這個一致的結(jié)果作為最終預(yù)測.SSEL沒有學習精準的集成概率,類似于粗糙版的SEL,其性能將作為實驗的基準.

4.2 語料與評價

實驗使用公開的標準數(shù)據(jù)集(Corpus for Vietnamese Word Segmentation,CVWS),該數(shù)據(jù)集包括305篇多領(lǐng)域越南語新聞文本,共7807個已標注詞邊界的句子.例如圖5所示的CVWS局部數(shù)據(jù)包含21個原始句子以及相應(yīng)的分詞形式.

圖5 CVWS局部數(shù)據(jù)Fig.5 CVWS partial data

我們使用國際Bakeoff[19]評價標準和相關(guān)評價方法.實驗報告經(jīng)典的準確率(P)、召回率(R)、F1值(F1)和錯誤率(ER),以此評價分詞器的性能.P、R、F1的值域為[0,1],1為最優(yōu),ER的值域也為[0,1],但0為最優(yōu).

P=C/(C+M)

(3)

R=C/N

(4)

F1=2PR/(P+R)

(5)

ER=M/N

(6)

以上四項評價指標分別通過公式(3)到公式(6)計算.其中N表示人工分詞文本的總詞數(shù),C表示自動分詞結(jié)果中正確切分的詞數(shù),M表示自動分詞結(jié)果中錯誤切分的詞數(shù).

4.3 結(jié)果與討論

實驗中,我們使用三折交叉驗證,將CVWS數(shù)據(jù)集等分成三部份,使用其中兩份作為訓(xùn)練語料,剩下的第三份作為測試語料.在進行三輪訓(xùn)練-測試后,將三次運行結(jié)果的平均值作為最后結(jié)果.

圖6 分詞器實驗結(jié)果Fig.6 Experimental result of segmenters

針對越南語分詞任務(wù),我們分別運行五個分詞器(VNT、RMM、MM、SSEL和SEL).圖6顯示的實驗結(jié)果表明:(I)有監(jiān)督集成學習分詞器的四項評價指標優(yōu)于每個單獨分詞器的,例如SSEL和SEL的R值分別是0.926和0.936,而VNT,RMM,MM的R值分別為0.907,0.920和0.924;(II)有監(jiān)督集成學習分詞器的四項評價指標優(yōu)于簡單有監(jiān)督集成學習分詞器的,例如SSEL和SEL的P值分別為0.952和0.955;(III)SEL的四項評價指標均為最優(yōu),例如SEL的F1值為最高的0.945.實驗結(jié)果證明SEL框架可以有效提高現(xiàn)有越南語分詞算法的性能,且采用歷史分詞準確率進行集成的策略優(yōu)于采用簡單多數(shù)投票的策略.SELWS算法可以通過綜合基本分詞器形成集成分詞器以取得最優(yōu)性能,甚至超過一些高級機器學習分詞算法的性能.從計算時間上看,RMM和MM最快,VNT次之,SSEL和SEL最慢.這是由于SSEL和SEL的計算時間是在VNT、RMM、MM計算時間之和的基礎(chǔ)上再加上各自的集成時間,因此犧牲了時間開銷.

上述實驗結(jié)果表明有監(jiān)督集成學習是有效的,這是因為:(1)統(tǒng)計上,每個基本分詞器學習出的假設(shè)空間都能覆蓋某一部分實際的目標空間,通過集成可以使得各個假設(shè)和實際目標之間的誤差得到一定程度的抵消;(2)計算上,直接找到目標函數(shù)是很困難的,但通常能很自然地把目標函數(shù)分解為多個獨立的函數(shù),再把多個函數(shù)的學習結(jié)果集成起來能夠使得最終的結(jié)果更加接近實際的目標函數(shù)值;(3)表示上,由于假設(shè)空間是人為規(guī)定的,在大多數(shù)機器學習應(yīng)用中實際目標空間并不在假設(shè)空間中,如果假設(shè)空間在某種集成運算下不封閉,那么我們通過把假設(shè)空間中的一系列假設(shè)集成起來就有可能表示出不在假設(shè)空間中的目標空間.

雖然以上三方面因素使得有監(jiān)督集成學習能夠獲得更優(yōu)的學習效果,但并非所有的有監(jiān)督集成學習都有效.有監(jiān)督集成學習有效的條件是每個基本分詞器的錯誤率都應(yīng)當?shù)陀?.5,否則集成的結(jié)果反而會提高錯誤率[20].此外,進行有監(jiān)督集成學習的每個基本分詞器還應(yīng)當盡量各不相同,如果每個基本分詞器的結(jié)果差不多,則集成后的決策和單個基本分詞器做出的決策沒有什么差異,這樣就不能保證集成的有效性.

5 結(jié) 論

我們提出的SEL框架可以充分發(fā)揮各種分詞算法的互補優(yōu)勢,對于提高現(xiàn)有越南語分詞算法的性能非常有用.此外,SEL框架適合于并行計算環(huán)境.若對多個基本分詞器進行硬件重復(fù)部署,SEL框架用于分詞的計算時間理論上接近于最慢基本分詞器的計算時間.

下一步的研究主要關(guān)注在SEL框架下的其他序列標注問題(如命名實體識別、詞性標注、句法分析和語義角色標注).而且我們會將上述研究成果遷移到其他適合的亞洲語言,如泰國語、日本語和漢語等.

：

[1] Zhu Qian,Wu Chen-ni,Zhu Zhi-liang,et al.Research and implementation of nutch Chinese word segmentation in hadoop cloud platform [J].Journal of Chinese Computer Systems,2013,34(12):2772-2776.

[2] Doan Nguyen.Query preprocessing:improving web search through a vietnamese word tokenization approach [C].The 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Singapore,Singapore,2008:765-766.

[3] Li Ying,Guo Jian-yi,Yu Zheng-tao,et al.Constituent to dependency conversion for vietnamese [J].Journal of Frontiers of Computer Science and Technology,2017,11(4):599-607.

[4] Quang Thang Dinh,Hong Phuong Le,Thi Minh Huyen Nguyen,et al.Word segmentation of Vietnamese texts:a comparison of approaches [C].The 6th International Conference on Language Resources and Evaluation,Marrakech,Morocco,2008:1933-1936.

[5] Liu Wu-ying,Wang Lin.How does dictionary size influence performance of vietnamese word segmentation [C].The 10th International Conference on Language Resources and Evaluation,Portoro,Slovenia,2016:1079-1083.

[6] Liu Wu-ying,Wang Lin.Unsupervised ensemble learning for vietnamese multisyllabic word extraction [C].The 20th International Conference on Asian Language Processing,Tainan,China,2016:353-357.

[7] Dien Dinh,Hoang Kiem,Nguyen Van Toan.Vietnamese word segmentation [C].The 6th Natural Language Processing Pacific Rim Symposium,Tokyo,Japan,2001.

[8] Ha Le An.A method for word segmentation in Vietnamese [C].Corpus Linguistics,2003.

[9] Dinh Dien and Vu Thuy.A maximum entropy approach for Vietnamese word segmentation [C].The 4th International Conference on Computer Sciences:Research,Innovation and Vision for the Future,Ho Chi Minh City,Vietnam,2006:248-253.

[10] Cam Tu Nguyen,Trung Kien Nguyen,Xuan Hieu Phan,et al.Viet namese word segmentation with CRFs and SVMs:an investigation [C].The 20th Pacific Asia Conference on Language,Information and Computation,Wuhan,China,2006:215-222.

[11] Hong Phuong Le,Thi Minh Huyen Nguyen,Azim Roussanaly,et al.A hybrid approach to word segmentation of Vietnamese texts [C].The 2nd International Conference on Language and Automata Theory and Applications,Tarragona,Spain,2008:240-249.

[12] Nguyen Doan.Using search engine to construct a scalable corpus for vietnamese lexical development for word segmentation [C].The 7th Workshop on Asian Language Resources,2009.

[13] Oanh Thi Tran,Cuong Anh Le,Thuy Quang Ha.Improving vietnamese word segmentation and POS tagging using MEM with various kinds of resources [J].Information and Media Technologies,2010,5(2):890-909.

[14] Dang Duc Pham,Giang Binh Tran,Son Bao Pham.A hybrid approach to vietnamese word segmentation using part of speech tags [C].The 1st International Conference on Knowledge and Systems Engineering,Hanoi,Vietnam,2009:154-161.

[15] Zhang Wei,Miao Duo-qian,Gao Can,et al.Semi-supervised data attribute reduction based on rough-subspace ensemble learning [J].Journal of Chinese Computer Systems,2016,37(12):2727-2732.

[16] Thomas G.Dietterich.Ensemble methods in machine learning [C].The 1st International Workshop on Multiple Classifier Systems,Cagliari,Italy,2000:1-15.

[17] Liu Wu-ying,Wang Ting.Multi-field learning for email spam filtering [C].The 33rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Geneva,Switzerland,2010:745-746.

[18] Liu Wu-ying,Wang Ting.Online active multi-field learning for efficient email spam filtering [J].Knowledge and Information Systems,2012,33(1):117-136.

[19] Richard Sproat,Thomas Emerson.The first international Chinese word segmentation Bakeoff [C].The 2nd SIGHAN Workshop on Chinese Language Processing,Sapporo,Japan,2003:133-143.

[20] Josef Kittler,Mohamad Hatef,Robert P W Duin,et al.On combining classifiers [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(3):226-239.

附中文參考文獻：

[1] 朱 潛,吳辰鈮,朱志良,等.Hadoop云平臺下Nutch中文分詞的研究與實現(xiàn)[J].小型微型計算機系統(tǒng),2013,34(12):2772-2776.

[3] 李 英,郭劍毅,余正濤,等.越南語短語樹到依存樹的轉(zhuǎn)換研究[J].計算機科學與探索,2017,11(4):599-607.

[15] 張 維,苗奪謙,高 燦,等.基于粗糙集成學習的半監(jiān)督屬性約簡[J].小型微型計算機系統(tǒng),2016,37(12):2727-2732.