鄧加原 姬東鴻 費(fèi)超群 任亞峰

摘要：推特文本中包含著大量的非標(biāo)準(zhǔn)詞，這些非標(biāo)準(zhǔn)詞是由人們有意或無(wú)意而創(chuàng)造的。對(duì)很多自然語(yǔ)言處理的任務(wù)而言，預(yù)先對(duì)推特文本進(jìn)行規(guī)范化處理是很有必要的。針對(duì)已有的規(guī)范化系統(tǒng)性能較差的問(wèn)題，提出一種創(chuàng)新的無(wú)監(jiān)督文本規(guī)范化系統(tǒng)。首先，使用構(gòu)造的標(biāo)準(zhǔn)詞典來(lái)判斷當(dāng)前的推特是否需要標(biāo)準(zhǔn)化。然后，對(duì)推特中的非標(biāo)準(zhǔn)詞會(huì)根據(jù)其特征來(lái)考慮進(jìn)行一對(duì)一還是一對(duì)多規(guī)范化；對(duì)于需要一對(duì)多的非標(biāo)準(zhǔn)詞，通過(guò)前向和后向搜索算法，計(jì)算出所有可能的多詞組合。其次，對(duì)于多詞組合中的非規(guī)范化詞，基于二部圖隨機(jī)游走和誤拼檢查，來(lái)產(chǎn)生合適的候選。最后，使用基于上下文的語(yǔ)言模型來(lái)得到最合適的標(biāo)準(zhǔn)詞。所提算法在數(shù)據(jù)集上獲得86.4%的F值，超過(guò)當(dāng)前最好的基于圖的隨機(jī)游走算法10個(gè)百分點(diǎn)。

關(guān)鍵詞：

規(guī)范化；無(wú)監(jiān)督學(xué)習(xí)；二部圖；隨機(jī)游走；拼寫(xiě)檢查

中圖分類號(hào)： TP391； TP18 文獻(xiàn)標(biāo)志碼：A

0引言

近年來(lái)，由于微博的快速發(fā)展，用戶生成內(nèi)容的數(shù)量大幅度增加。推特作為最流行的微博服務(wù)之一，它擁有10億個(gè)活躍用戶，每天產(chǎn)生5億條微博（http：//expandedrambling.com）。然而，由于其快速發(fā)布的性質(zhì)，推特文本中包含了大量由用戶有意或無(wú)意中創(chuàng)造的非標(biāo)準(zhǔn)詞。比如：用數(shù)字替換字母2gether（together）和2morrow（tomorrow）；重復(fù)字母來(lái)強(qiáng)調(diào)要表達(dá)的內(nèi)容coollll（cool）和birthdayyyy（birthday）；省略元音字母ppl（people）；用發(fā)音相似的字母來(lái)替換fon（phone）。除此之外，還有另外一種類型的非標(biāo)準(zhǔn)詞，主要包括多個(gè)連續(xù)的標(biāo)準(zhǔn)詞之間省略了空格、標(biāo)點(diǎn)和字母，例如：theres（there is）、loveyousomuch（love you so much）、ndyou（and you）和untiltheend（until the end）等。根據(jù)對(duì)1000條推特進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)其中包括了1329個(gè)非標(biāo)準(zhǔn)詞，其中大約22%的比例（294個(gè)）需要規(guī)范化為兩個(gè)或者更多的標(biāo)準(zhǔn)詞。

推特作為極有價(jià)值的信息源，引起來(lái)了眾多自然語(yǔ)言處理任務(wù)和應(yīng)用的關(guān)注。比如信息抽取[1]、自動(dòng)摘要[2]、情感分析[3-4]、災(zāi)難檢測(cè)[5]和事件發(fā)現(xiàn)[6-7]等。然而，推特文本中的非標(biāo)準(zhǔn)詞嚴(yán)重限制了這些任務(wù)和應(yīng)用的性能[1，8]。比如：對(duì)于標(biāo)準(zhǔn)的自然語(yǔ)言處理工具來(lái)說(shuō)，命名實(shí)體識(shí)別在推特文本中從90.8%驟降到45.8%[9]；詞性標(biāo)注和依存句法分析分別下降了12.2%和20.65%[10]?；诖?，為了使得推特文本能有效被用于標(biāo)準(zhǔn)的自然語(yǔ)言處理任務(wù)，設(shè)計(jì)合理的文本規(guī)范化算法至關(guān)重要。

近年來(lái)，涌現(xiàn)了一批文本規(guī)范化系統(tǒng)來(lái)將非標(biāo)準(zhǔn)詞規(guī)范化為標(biāo)準(zhǔn)詞[8，11-15]，但是，這些工作假設(shè)一個(gè)非標(biāo)準(zhǔn)詞對(duì)應(yīng)于一個(gè)標(biāo)準(zhǔn)詞。比如hiiiii規(guī)范化為hi，值得注意的是，在先前的系統(tǒng)中，theyre規(guī)范化為they，itmay規(guī)范化為it，這些系統(tǒng)會(huì)丟失一些關(guān)鍵的信息，這顯然是不夠合理的。

本文主要集中于推特文本的規(guī)范化處理工作，其主要面臨以下兩個(gè)挑戰(zhàn)：

1）對(duì)一個(gè)非標(biāo)準(zhǔn)詞，它應(yīng)該被規(guī)范化為一個(gè)還是多個(gè)標(biāo)準(zhǔn)詞？

2）推特文本的規(guī)范化系統(tǒng)應(yīng)該具有很高的準(zhǔn)確率和召回率，才能使得其作為標(biāo)準(zhǔn)自然語(yǔ)言處理工具的預(yù)處理步驟中產(chǎn)生較好的作用。

本文提出了一個(gè)創(chuàng)新的無(wú)監(jiān)督文本規(guī)范化系統(tǒng)來(lái)解決應(yīng)對(duì)上述兩個(gè)挑戰(zhàn)。首先，根據(jù)非標(biāo)準(zhǔn)詞的特性，基于前向和后向搜索將一個(gè)非標(biāo)準(zhǔn)詞轉(zhuǎn)化成所有可能的多詞組合（由標(biāo)準(zhǔn)詞和非規(guī)范化詞構(gòu)成）；然后，整合二部圖的隨機(jī)游走算法和誤拼檢測(cè)算法，為非規(guī)范化詞產(chǎn)生候選列表；最后，根據(jù)基于上下文的語(yǔ)言模型來(lái)確定最合適的解。

1相關(guān)研究

近年來(lái)，隨著社交網(wǎng)絡(luò)的快速發(fā)展，文本規(guī)范化吸引了眾多研究者的關(guān)注。最近的工作主要集中于推特文本的規(guī)范化，把非標(biāo)準(zhǔn)詞轉(zhuǎn)化為其標(biāo)準(zhǔn)形式。

Han等[8]基于詞的形態(tài)和音位的相似性構(gòu)造分類器來(lái)規(guī)范化非標(biāo)準(zhǔn)詞。Gouws等[16]提出了基于字符串和分布相似性的方法構(gòu)造標(biāo)準(zhǔn)詞典，來(lái)檢測(cè)非標(biāo)準(zhǔn)詞?；诜植己妥址南嗨菩?，Han等[12]提出了一個(gè)相似的方法，來(lái)為一個(gè)非標(biāo)準(zhǔn)詞產(chǎn)生多個(gè)標(biāo)準(zhǔn)的候選。

更近的，Hassan等[13]首次提出了基于二部圖來(lái)發(fā)現(xiàn)候選詞，然后使用N元語(yǔ)法模型選出最較好的規(guī)范化詞。Wang等[14]提出了集束搜索（beam search）解碼器有效地結(jié)合了不同的規(guī)范化操作，并將其規(guī)范化系統(tǒng)有效地應(yīng)用到中英文翻譯系統(tǒng)。Li等[15]提出整合各種不同的規(guī)范化系統(tǒng)的候選結(jié)果，基于詞向量的語(yǔ)義相似性和其他基于距離的相似性策略對(duì)候選結(jié)果進(jìn)行重排序，以此來(lái)提高候選集合的質(zhì)量。

上述的已有方法無(wú)法獲得能滿足實(shí)際應(yīng)用的效果。主要原因歸結(jié)于這些方法都假設(shè)非標(biāo)準(zhǔn)詞到標(biāo)準(zhǔn)詞的關(guān)系是一對(duì)一的關(guān)系。然而，現(xiàn)實(shí)中有很多非標(biāo)準(zhǔn)詞（例如howyou和havent）應(yīng)該被規(guī)范化為多個(gè)標(biāo)準(zhǔn)詞，如果把這些詞規(guī)范化為單個(gè)標(biāo)準(zhǔn)詞，會(huì)損失很多重要的信息。在本文提出的系統(tǒng)中，一個(gè)標(biāo)準(zhǔn)詞將根據(jù)其特性被規(guī)范化為一個(gè)或多個(gè)標(biāo)準(zhǔn)詞，使得規(guī)范化系統(tǒng)在自然語(yǔ)言處理任務(wù)中能夠取得更好的結(jié)果。

2推特文本規(guī)范化系統(tǒng)

本文旨在將非規(guī)范化的推特文本作為輸入，輸出其對(duì)應(yīng)的標(biāo)準(zhǔn)化文本。所提出的主要框架如圖1所示。對(duì)于一個(gè)推特文本，標(biāo)準(zhǔn)詞典被用于檢測(cè)該推特是否需要進(jìn)行規(guī)范化。然后，推特中的非標(biāo)準(zhǔn)詞，將會(huì)被根據(jù)其特征來(lái)考慮進(jìn)行一對(duì)一（11）還是一對(duì)多（1N）規(guī)范化。對(duì)于需要一對(duì)多的非標(biāo)準(zhǔn)詞，通過(guò)前向搜索和后向搜索算法，計(jì)算出所有可能的多詞組合。對(duì)于多詞組合中的非規(guī)范化詞，基于二部圖隨機(jī)游走算法和誤拼檢查，產(chǎn)生合適的候選。最后使用基于上下文的語(yǔ)言模型來(lái)得到最合適的標(biāo)準(zhǔn)詞。接下來(lái)詳細(xì)介紹本文提出的系統(tǒng)。

2.1預(yù)處理和標(biāo)準(zhǔn)詞典

所提系統(tǒng)的第一步是判斷一條推特文本是否需要規(guī)范化。根據(jù)推特文本本身的特性，在判斷是否需要規(guī)范化之需要一些預(yù)處理，下述幾種類型的詞不需要作規(guī)范化處理：

1）以#或@開(kāi)頭所構(gòu)成的詞（例如：#kingJames，@michael）；

2）由純數(shù)字所構(gòu)成的單詞（例如：2014）；

3）表情符和URL（Uniform Resource Locator）。

在推特文本中，還有很多表示人名或者地名的命名實(shí)體不需要規(guī)范化，因此，使用的標(biāo)準(zhǔn)詞典必須足夠廣闊以至于能夠盡可能地包含這些命名實(shí)體。為了獲得較合適的標(biāo)準(zhǔn)詞典，基于一個(gè)大規(guī)模的語(yǔ)料LDC（Linguistic Data Consortium）統(tǒng)計(jì)了所有單詞的出現(xiàn)頻率，并且刪除所有頻率低于5的單詞。然后，使用GNU ASpell詞典（v0.60.6）過(guò)濾掉一些單詞。剩下大約68000個(gè)單詞構(gòu)成本文使用的標(biāo)準(zhǔn)詞典。自然而然地，本文認(rèn)為，凡是沒(méi)有出現(xiàn)在這個(gè)標(biāo)準(zhǔn)詞典中的詞都應(yīng)該是需要規(guī)范化的非標(biāo)準(zhǔn)詞。

2.2統(tǒng)計(jì)規(guī)則

2.1節(jié)中討論了哪些詞需要規(guī)范化。接下來(lái)，一個(gè)重要的挑戰(zhàn)就是判斷一個(gè)非標(biāo)準(zhǔn)詞應(yīng)該被規(guī)范化為一個(gè)還是多個(gè)標(biāo)準(zhǔn)詞。通過(guò)觀察和分析大量的非標(biāo)準(zhǔn)詞，對(duì)其特性進(jìn)行了總結(jié)。對(duì)符合以下特性的非標(biāo)準(zhǔn)詞進(jìn)行11規(guī)范化：

1）如果某個(gè)非標(biāo)準(zhǔn)詞所所包含的字符總數(shù)少于4個(gè)，則直接將其規(guī)范化為一個(gè)標(biāo)準(zhǔn)詞，例如，u（you）和r（are）；

2）如果某個(gè)非標(biāo)準(zhǔn)詞是字母和數(shù)字的組合，則將其直接規(guī)范化為一個(gè)標(biāo)準(zhǔn)詞，例如，be4（before）和2day（today）。

在本文提出的系統(tǒng)中，符合以上特性的非標(biāo)準(zhǔn)詞，將直接進(jìn)行11規(guī)范化；否則，該非標(biāo)準(zhǔn)詞將會(huì)被考慮有可能規(guī)范化為多個(gè)標(biāo)準(zhǔn)詞。當(dāng)然，上述兩條規(guī)則沒(méi)有捕獲所有的情況，比如ur可能需要規(guī)范化為you are，也有可能需要規(guī)范化為your或者our。這類非標(biāo)準(zhǔn)詞由于長(zhǎng)度太短，本身具有太大的歧義，需要依靠特定的上下文，但是符合上述特性的非標(biāo)準(zhǔn)詞絕大多數(shù)情況是屬于11規(guī)范化的。

本文也分析和總結(jié)了另一類非標(biāo)準(zhǔn)詞，這類非標(biāo)準(zhǔn)詞應(yīng)該被規(guī)范化為兩個(gè)或者更多的標(biāo)準(zhǔn)詞。這類非標(biāo)準(zhǔn)詞主要包括以下3種類型。

類型1非標(biāo)準(zhǔn)詞主要由兩個(gè)或更多的標(biāo)準(zhǔn)詞構(gòu)成，標(biāo)準(zhǔn)詞之間的空格被用戶有意識(shí)或無(wú)意識(shí)地省略。例如，iloveyou（i love you）和rememberwith（remember with）。

類型2非標(biāo)準(zhǔn)詞由一個(gè)或多個(gè)標(biāo)準(zhǔn)詞，連同一個(gè)非規(guī)范化詞構(gòu)成。例如，wasnt（was not）和ndyou（and you）。

類型3非標(biāo)準(zhǔn)詞由兩個(gè)或者更多的標(biāo)準(zhǔn)詞的單個(gè)字母縮略構(gòu)成。例如，ur（you are）和sm（so much）。

類型3的非標(biāo)準(zhǔn)詞是非常有限的，這種類型的非標(biāo)準(zhǔn)詞本身也具有很大的歧義性。本文提出的系統(tǒng)將整合互聯(lián)網(wǎng)用戶整理的俚語(yǔ)表（slang dictionary（http：//www.noslang.com/dictionary）），連同算法所計(jì)算出的候選集合。最終根據(jù)語(yǔ)言模型來(lái)計(jì)算出最合適的標(biāo)準(zhǔn)詞。

2.3前向搜索和后向搜索

對(duì)于一個(gè)非標(biāo)準(zhǔn)詞，本研究提出使用前向搜索和后向搜索算法，為其找出所有可能的多詞組合。前向搜索能夠解決兩種類型的非標(biāo)準(zhǔn)詞：第1種類型是非標(biāo)準(zhǔn)詞由一個(gè)或多個(gè)標(biāo)準(zhǔn)詞和一個(gè)非標(biāo)準(zhǔn)詞按順序組成，例如，theyre（they are）和wouldnt（would not）。第2種類型是由兩個(gè)或者多個(gè)標(biāo)準(zhǔn)詞組成，例如，aboutthem（about them）和iloveyou（I love you）。具體的前向搜索如算法1所示。

算法1前向搜索ForwardSearch。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：?jiǎn)卧~查找樹(shù)的當(dāng)前節(jié)點(diǎn)node，存儲(chǔ)組合的列表（Set），將要匹配的字符串word，已經(jīng)匹配到的字符串matchedWord。

輸出：所有可能的多詞組合。

1）

If（node.state==1）

2）

{

3）

Set set2；

4）

matchedLength=len（matchedWord）

5）

word=word.subString（matchedLength）

6）

matchedWord=′ ′；

7）

ForwardSearch（Trie.root，set2，word，matchedWord）

8）

For（String str：set2）

9）

{ set.add（matchedWord+″ ″+str）；}

10）

}

11）

If（len（word）！=0）

12）

{

13）

char c=word.charAt（0）；

14）

int index=c-′a′；

15）

if（node.next[index]！=null）

16）

{

17）

word=word.subString（1）

18）

matchedWord+=c；

19）

ForwardSearch（node.next[index]，set，word，matchedWord）；

20）

}

21）

}

程序后

需要指出的是，算法1中，Trie是由標(biāo)準(zhǔn)詞典構(gòu)造的單詞查找樹(shù)，可方便用于快速查找一個(gè)非標(biāo)準(zhǔn)詞中所包含的標(biāo)準(zhǔn)詞。

類似于前向搜索，后向搜索算法也能解決兩種類型的非標(biāo)準(zhǔn)詞：第1種類型是非標(biāo)準(zhǔn)詞由一個(gè)非標(biāo)準(zhǔn)和一個(gè)或多個(gè)標(biāo)準(zhǔn)詞按順序組成，例如，ndyou（and you）和looveyou（love you）。第2種類型是由兩個(gè)或者多個(gè)標(biāo)準(zhǔn)詞組成。后向搜索算法的過(guò)程與前向搜索類型，唯一不同的是單詞查找的構(gòu)造和搜索的順序都是逆序的。

對(duì)于一個(gè)非標(biāo)準(zhǔn)詞，基于前向搜索和后向搜索后，可以找到非標(biāo)準(zhǔn)詞所有可能的多詞組合。例如，theyre的前向搜索有“the yre”和“they re”兩種組合結(jié)果。然后將所有組合中的非規(guī)范詞（yre和re）進(jìn)行11規(guī)范化。與此同時(shí)，非標(biāo)準(zhǔn)詞本身（theyre）也要進(jìn)行11規(guī)范化，確保不會(huì)遺漏任何可能存在的情況。在后面的章節(jié)，將討論如何對(duì)非規(guī)范詞進(jìn)行11規(guī)范化。

2.4隨機(jī)游走和誤拼檢查

非規(guī)范化詞有很多類型，例如，重復(fù)字母用來(lái)強(qiáng)調(diào)、字母替換、字母到數(shù)字的替換、字母發(fā)音替換等。一個(gè)很自然的想法就是通過(guò)誤拼檢查來(lái)將非規(guī)范化詞進(jìn)行規(guī)范化，但是，誤拼檢查僅僅能還原用戶無(wú)意的漏掉個(gè)別字符的非規(guī)范化詞。同時(shí)，為了能為用戶刻意創(chuàng)造的非規(guī)范化詞找到合適的候選，本研究使用基于二部圖的隨機(jī)游走算法來(lái)找到候選集，因此，對(duì)于一個(gè)非規(guī)范化詞，為了進(jìn)行11規(guī)范化，本文整合基于二部圖的隨機(jī)游走算法和誤拼檢查來(lái)產(chǎn)生候選集合。

本文提出使用上下文的相似性來(lái)為非標(biāo)準(zhǔn)詞找到其可能的標(biāo)準(zhǔn)詞的候選集合。比如任意5元語(yǔ)法序列，如果兩個(gè)中心詞的前后兩個(gè)詞完全一樣，那么這兩個(gè)中心詞可能就是同一個(gè)詞或者語(yǔ)義相關(guān)的詞。例如，非規(guī)范詞be4和標(biāo)準(zhǔn)詞before，由于其共享上下文“the day * the day”和“dress yourself * contract me”，因此，可以認(rèn)為這兩個(gè)詞是同一個(gè)詞或者語(yǔ)義相關(guān)的詞。最終通過(guò)基于字符串的相似度和基于上下文的語(yǔ)言模型可以判定，“before”就是“be4”的規(guī)范化結(jié)果。上述分析證明了非規(guī)范詞和標(biāo)準(zhǔn)詞可以通過(guò)大規(guī)模的推特語(yǔ)料來(lái)獲取，基于此，本文提出使用基于二部圖的隨機(jī)游走算法，來(lái)為一個(gè)非規(guī)范詞，通過(guò)上下文相似性，找到其對(duì)應(yīng)的標(biāo)準(zhǔn)詞候選集合。首先介紹二部圖的構(gòu)造。

2.4.1構(gòu)造二部圖

上下文的相似性可以用二部圖來(lái)表示：第1種類型的節(jié)點(diǎn)代表詞；第2種類型的節(jié)點(diǎn)代表可能被詞共享的上下文。詞節(jié)點(diǎn)的類型可能是非規(guī)范詞，也可能是標(biāo)準(zhǔn)詞。圖2顯示了二部圖G（W，C，E）的一個(gè)樣例，其中藍(lán)色灰色這樣描述是否符合要求？請(qǐng)明確。的節(jié)點(diǎn)表示標(biāo)準(zhǔn)詞。

二部圖G（W，C，E）中，W表示非規(guī)范詞或者標(biāo)準(zhǔn)詞，C表示所有的上下文，E表示連接詞節(jié)點(diǎn)和上下文節(jié)點(diǎn)的邊，邊的權(quán)重是詞節(jié)點(diǎn)和上下文節(jié)點(diǎn)共現(xiàn)的次數(shù)。二部圖的構(gòu)造如算法2所示。

算法2構(gòu)造二部圖。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：推特語(yǔ)料。

輸出：二部圖G（W，C，E）。

1）

Extract all 5gram sequences from corpus；

2）

Store all sequences into NgramTable；

3）

For each sequence NgramTable；

4）

W*Add（CenterWord）；

5）

C*Add（Context）；

6）

E*Add（Context，CenterWord，Count）

程序后

2.4.2隨機(jī)游走產(chǎn)生候選集

基于二部圖的隨機(jī)游走算法首先被Norris所定義[17]，然后被廣泛應(yīng)用于各種自然語(yǔ)言處理任務(wù)中。例如，Hughes等[18]提出在WordNet圖上使用隨機(jī)游走算法來(lái)檢測(cè)詞語(yǔ)的語(yǔ)義相關(guān)性；Das等[19]提出在兩種語(yǔ)言上使用圖模型的標(biāo)簽傳播來(lái)進(jìn)行跨語(yǔ)言的知識(shí)轉(zhuǎn)移；Minkov等[20]提出一種基于受限路徑圖的隨機(jī)游走算法來(lái)計(jì)算圖中節(jié)點(diǎn)的相關(guān)性；Hassan等[13]提出使用Twitter和LDC語(yǔ)料構(gòu)造的二部圖來(lái)考慮詞語(yǔ)規(guī)范化。不同于上述算法，本文僅僅使用大規(guī)模的推特語(yǔ)料，使用二部圖的隨機(jī)游走算法來(lái)為非規(guī)范詞找到合適的候選集合。

對(duì)于一個(gè)非規(guī)范詞，隨機(jī)游走算法使用輪盤賭的方式隨機(jī)游走4步來(lái)遍歷二部圖。算法從非規(guī)范詞節(jié)點(diǎn)開(kāi)始，到標(biāo)準(zhǔn)詞節(jié)點(diǎn)或者走完最大步數(shù)結(jié)束。在本文提出的框架中，對(duì)于每個(gè)非標(biāo)準(zhǔn)詞，其隨機(jī)游走的過(guò)程都迭代100次。

考慮一個(gè)二部圖隨機(jī)游走過(guò)程，以圖2中的二部圖為例，假設(shè)隨機(jī)游走算法從非規(guī)范詞節(jié)點(diǎn)be4出發(fā)，通過(guò)輪盤賭隨機(jī)移動(dòng)到上下文節(jié)點(diǎn)context2，然后再移動(dòng)到標(biāo)準(zhǔn)詞節(jié)點(diǎn)before，本次隨機(jī)游走結(jié)束，這次的隨機(jī)游走將be4和before聯(lián)系起來(lái)。同時(shí)，在下次的隨機(jī)游走過(guò)程中，非規(guī)范詞節(jié)點(diǎn)be4可以通過(guò)隨機(jī)游走將將非規(guī)范詞節(jié)點(diǎn)be4同after聯(lián)系起來(lái)：

be4 → context1 → b4 → context3 → after

那么對(duì)于非規(guī)范詞be4，如何判斷候選詞的好壞，即對(duì)于be4來(lái)說(shuō)，after和before，哪個(gè)是更好的候選。

本文中，對(duì)于一個(gè)非標(biāo)準(zhǔn)詞，通過(guò)計(jì)算置信度ConValue（N，S）對(duì)其隨機(jī)游走的候選結(jié)果進(jìn)行排序，其中N表示非規(guī)范詞，S表示標(biāo)準(zhǔn)詞，ConValue（N，S）的計(jì)算如下：

ConValue（N，S）=α*F（S）+β*Sim（N，S）（1）

其中α和β是權(quán)重，這里使用均勻插值，即設(shè)置α=β=0.5。F（S）的計(jì)算如下：

F（S）=S_frequency/total_frequency（2）

其中：S_frequency表示標(biāo)準(zhǔn)詞S在100次隨機(jī)游走中最終被識(shí)別的次數(shù)，total_frequency表示在100次隨機(jī)游走中找到的標(biāo)準(zhǔn)詞個(gè)數(shù)。Sim（N，S）是基于最長(zhǎng)公共子序列比率的字符串相似度函數(shù)[21-22]，其計(jì)算方式如下：

Sim（N，S）=LCS（N，S）/MaxLength（N，S）ED（N，S）（3）

其中：LCS（N，S）表示N和S的最長(zhǎng)公共子序列，ED（N，S）表示N和S的編輯距離。

對(duì)于一個(gè)非規(guī)范詞，可以使用隨機(jī)游走算法為其計(jì)算出可能的候選集合，并通過(guò)ConValue（N，S）值選取Top5對(duì)候選集合進(jìn)行修剪。隨機(jī)游走算法的優(yōu)點(diǎn)是可以為絕大多數(shù)非規(guī)范詞找到合適的候選詞。然而，由于數(shù)據(jù)集的規(guī)模限制，基于二部圖的隨機(jī)游走算法不可能為所有的非規(guī)范化詞找到候選集合，因此必須同時(shí)結(jié)合其他方法，為一個(gè)非規(guī)范詞產(chǎn)生一定的候選集合。本文采用經(jīng)典的誤拼檢查算法來(lái)產(chǎn)生候選，將其結(jié)果同隨機(jī)游走算法產(chǎn)生的候選整合到一起作為整個(gè)候選集合。

2.4.3誤拼檢查

對(duì)于誤拼寫(xiě)錯(cuò)的非規(guī)范詞，誤拼檢查算法是個(gè)簡(jiǎn)單并且有效的規(guī)范化方法。本文中采用Jazzy spell checker（http：//jazzy.sourceforge.net/），并且同時(shí)整合DoubleMetaphone聲音匹配算法，來(lái)考慮單詞之間的字符的取代、插入、刪除和交換等操作。本文設(shè)置編輯距離為2之內(nèi)的所有標(biāo)準(zhǔn)詞來(lái)作為一個(gè)非規(guī)范詞的候選集合。

2.4.4產(chǎn)生Topn候選集

對(duì)于一個(gè)非標(biāo)準(zhǔn)詞N，通過(guò)隨機(jī)游走算法和誤拼檢查為其產(chǎn)生了一定數(shù)量的候選，需要對(duì)這些候選進(jìn)行排序，除了比較字符串的相似性外，還考慮了其語(yǔ)義相似性，對(duì)于非標(biāo)準(zhǔn)詞N，其所有候選的得分通過(guò)式（4）來(lái)計(jì)算：

S（N，S）=Sim（N，S）+Cos（vec（N），vec（S））（4）

Sim（N，S）的計(jì)算方法已在前面介紹過(guò)，函數(shù)Cos（vec（N），vec（S））表示非標(biāo)準(zhǔn)詞N和標(biāo)準(zhǔn)詞S的詞向量之間的余弦相似度，為了計(jì)算詞N和詞S的詞向量，本文使用了谷歌的開(kāi)源工具word2vec（http：//code.google.com/p/word2vec/），基于800萬(wàn)條推特語(yǔ)料來(lái)訓(xùn)練，詞向量的維度被設(shè)置為200。基于S（N，S），最終為每個(gè)非標(biāo)準(zhǔn)詞選取Topn個(gè)候選詞（n=1，3，5）。

2.4.5基于語(yǔ)言模型來(lái)規(guī)范化推特

對(duì)于一個(gè)非標(biāo)準(zhǔn)詞，整合隨機(jī)游走和誤拼檢查為其產(chǎn)生Topn個(gè)候選詞。為了確定該非標(biāo)準(zhǔn)詞的最佳候選，需要考慮該非標(biāo)準(zhǔn)詞的上下文信息?；诖笠?guī)模的文本數(shù)據(jù)，通過(guò)使用3元和4元語(yǔ)法模型來(lái)對(duì)維特比（Viterbi）路徑進(jìn)行打分，基于此來(lái)選擇最合適的候選，進(jìn)行規(guī)范化。本文在使用基于上下文的語(yǔ)法模型時(shí)，分別考慮了3種不同類型的數(shù)據(jù)。

3實(shí)驗(yàn)

3.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中使用了5個(gè)數(shù)據(jù)集，數(shù)據(jù)集（1）和數(shù)據(jù)集（2）將用于詞級(jí)別（wordlevel）的評(píng)估；數(shù)據(jù)集（3）不僅用于詞級(jí)別的評(píng)估，還用于句子級(jí)別（messagelevel）的評(píng)估。值得注意的是，數(shù)據(jù)集（1）和數(shù)據(jù)集（2）的非標(biāo)準(zhǔn)詞，僅僅需要被規(guī)范化為一個(gè)標(biāo)準(zhǔn)詞。5個(gè)數(shù)據(jù)集的介紹如下。

數(shù)據(jù)集（1）3802個(gè)非標(biāo)準(zhǔn)詞及其對(duì)應(yīng)的人工標(biāo)注的標(biāo)準(zhǔn)詞。這些非標(biāo)準(zhǔn)詞來(lái)自于2009年到2010年之間的6150條推特文本[11]。

數(shù)據(jù)集（2）2333個(gè)非標(biāo)準(zhǔn)詞及其對(duì)應(yīng)的人工標(biāo)注的標(biāo)注詞，這些非標(biāo)準(zhǔn)詞來(lái)自于2577條推文本[15，23]。

數(shù)據(jù)集（3）邀請(qǐng)了3個(gè)母語(yǔ)為英語(yǔ)的學(xué)生標(biāo)注的1000條推特文本。其中有850條推特需要進(jìn)行規(guī)范化的，另外150條不需要規(guī)范化。該數(shù)據(jù)集中總共包含1345個(gè)非標(biāo)準(zhǔn)詞，其中297個(gè)非標(biāo)準(zhǔn)詞需要被規(guī)范化為兩個(gè)或更多的標(biāo)準(zhǔn)詞。

數(shù)據(jù)集（4）通過(guò)推特流API（http：//dev.twitter.com/docs/streamingapis）獲取的800萬(wàn)條推特文本數(shù)據(jù)，這些推特來(lái)自于2014年10月到12月。該數(shù)據(jù)被用于構(gòu)建隨機(jī)游走的二部圖。

數(shù)據(jù)集（5）來(lái)自英文LDC Gigaword（http：//www.ldc.upenn.edu/Catalog/LDC2011T07），該語(yǔ)料被用于構(gòu)建標(biāo)準(zhǔn)詞典。

詞級(jí)別（wordlevel）的規(guī)范化旨在判斷非標(biāo)準(zhǔn)詞對(duì)應(yīng)的標(biāo)準(zhǔn)詞是否在所產(chǎn)生的候選集合中，因此，對(duì)于一個(gè)非標(biāo)準(zhǔn)詞，系統(tǒng)通過(guò)其候選集Topn中是否包含其標(biāo)準(zhǔn)詞來(lái)判定它是否被正確地規(guī)范化。為了同已有算法相比較，分別計(jì)算了在不同Topn設(shè)置下的準(zhǔn)確率。對(duì)于文本級(jí)別（messagelevel）的評(píng)價(jià)，基于不同類型的大規(guī)模文本數(shù)據(jù)，分別構(gòu)造語(yǔ)言模型來(lái)計(jì)算準(zhǔn)確率、召回率和F值來(lái)評(píng)估Top1、Top3和Top5設(shè)置下的系統(tǒng)性能。

3.2詞級(jí)別實(shí)驗(yàn)結(jié)果

詞級(jí)別的結(jié)果呈現(xiàn)在表1中，本文分別在數(shù)據(jù)集（1）和數(shù)據(jù)集（2）中進(jìn)行評(píng)估，分別展示了Top1、Top3和Top5的準(zhǔn)確率。

從表1中可知，僅僅使用誤拼檢查，數(shù)據(jù)集（1）和（2）上的準(zhǔn)確率為40%到60%，這說(shuō)明僅僅通過(guò)比較詞的相似性無(wú)法有效規(guī)范化用戶有意識(shí)創(chuàng)造和使用的非標(biāo)準(zhǔn)詞。同時(shí)，隨機(jī)游走算法取得了相對(duì)較好的結(jié)果，在兩個(gè)數(shù)據(jù)集中獲得了65%到80%的準(zhǔn)確率，比起誤拼檢查，隨機(jī)游走能夠有效地捕獲人們有意創(chuàng)造的非標(biāo)準(zhǔn)詞。最后，本文提出的系統(tǒng)，通過(guò)整合誤拼檢查和隨機(jī)游走作為整個(gè)候選集，在Top5混合系統(tǒng)中獲得了90%到94%的準(zhǔn)確率，這證實(shí)本文算法的有效性。

比起當(dāng)前的算法最好的算法文獻(xiàn)[13]算法，本文提出的無(wú)監(jiān)督文本規(guī)范化系統(tǒng)能獲得更高的準(zhǔn)確率，主要原因歸結(jié)于本文的系統(tǒng)所產(chǎn)生的候選集，整合了隨機(jī)游走算法和誤拼檢查的結(jié)果，能更好地覆蓋到人們有意或者無(wú)意創(chuàng)造的非標(biāo)準(zhǔn)詞。

3.3文本級(jí)別實(shí)驗(yàn)結(jié)果

文本級(jí)別的規(guī)范化旨在為推特文本的每個(gè)非標(biāo)準(zhǔn)詞找到最符合上下文的候選?；跀?shù)據(jù)集（3），表2中呈現(xiàn)了文本級(jí)別的規(guī)范化結(jié)果。

在表2中，“w/o context”表示的是Top1詞級(jí)別的系統(tǒng)設(shè)置下的規(guī)范化結(jié)果。值得注意的是，盡管Top1僅有一個(gè)候選詞，但由于本文所提出的系統(tǒng)的高效性，最終獲得了84%的F值。為了計(jì)算Top3和Top5設(shè)置下的實(shí)驗(yàn)結(jié)果，使用3種不同類型的文本數(shù)據(jù)，基于語(yǔ)言模型（LM），采用維特比算法來(lái)解碼。在使用推特文本（Twitter）的語(yǔ)言模型中，能夠看到準(zhǔn)確率和召回率隨著候選集合大小n（1，3，5）的增大而增大，在n=5時(shí)，獲得本文所提出的系統(tǒng)可獲得高達(dá)86.4%的F值。同時(shí)，從表2可以看到混合文本語(yǔ)言模型（Mixed LM）和推特文本語(yǔ)言模型（Twitter LM）超過(guò)了當(dāng)前算法的性能。

需要指出的是，基于LDC語(yǔ)料的語(yǔ)言模型（LDC LM），其結(jié)果隨著候選集合大小n的增大而變差，其主要原因有推特文本的性能所決定，對(duì)推特文本來(lái)說(shuō)，即使非標(biāo)準(zhǔn)詞被規(guī)范化后仍然會(huì)存在一些語(yǔ)法上的錯(cuò)誤。這不難解釋單純使用推特文本的語(yǔ)言模型（Twitter LM）會(huì)比混合語(yǔ)言模型（Mixed LM）有更好的結(jié)果。

同時(shí)，從表2中可以看出，比起當(dāng)前的系統(tǒng)[13，15]，本文提出的系統(tǒng)在F值上有超過(guò)10%的提高了10個(gè)百分點(diǎn)以上，主要原因在于提出的系統(tǒng)考慮了非標(biāo)準(zhǔn)詞一對(duì)多的規(guī)范化，而之前的工作全都集中在一對(duì)一的情況，限制了該任務(wù)的性能。

3.4結(jié)果分析

圖3呈現(xiàn)了數(shù)據(jù)集（3）的3個(gè)原始推特，經(jīng)過(guò)不同系統(tǒng)規(guī)范化后的結(jié)果。在圖3中，S表示原始推特，B表示當(dāng)前的方法[15]，O表示本文提出的系統(tǒng)。在第一條推特文本中，所有的非標(biāo)準(zhǔn)詞都能被正確規(guī)范化，但是，對(duì)于后兩條推特，現(xiàn)有的系統(tǒng)使用一對(duì)一的規(guī)范化損失了一些關(guān)鍵的信息，使得規(guī)范化的結(jié)果出現(xiàn)一定的錯(cuò)誤。而在本文提出的無(wú)監(jiān)督文本規(guī)范化系統(tǒng)中，根據(jù)非標(biāo)準(zhǔn)詞的特性，為其產(chǎn)生一個(gè)或多個(gè)標(biāo)準(zhǔn)詞，來(lái)作為規(guī)范化的結(jié)果，更能滿足實(shí)際應(yīng)用。基于上述分析，可以證實(shí)本文提出系統(tǒng)的有效性。

4結(jié)語(yǔ)

本文提出了一個(gè)無(wú)監(jiān)督的推特文本規(guī)范化系統(tǒng)。對(duì)于一個(gè)非標(biāo)準(zhǔn)詞，根據(jù)其特性，基于前向搜索和后向搜索將其劃分為可能的多詞組合。然后，整合隨機(jī)游走算法和誤拼檢查為非規(guī)范詞產(chǎn)生可能的多個(gè)候選。最后，使用基于上下文的語(yǔ)言模型來(lái)為非標(biāo)準(zhǔn)詞計(jì)算出最合適的候選。實(shí)驗(yàn)結(jié)果證實(shí)本文所提算法的有效性，比起當(dāng)前算法，本文提出的算法在F值獲得超過(guò)10%的上提高了10個(gè)百分點(diǎn)以上。本文提出的無(wú)監(jiān)督文本規(guī)范化系統(tǒng)能夠有效用于自然語(yǔ)言處理任務(wù)的預(yù)處理。

參考文獻(xiàn)：

[1]

RITTER A， CLARK S， MAUSAM M， et al. Named entity recognition in tweets： an experimental study [C]// Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing. Stroudsburg， PA： Association for Computational Linguistics， 2011： 1524-1534.

[2]

LIU F， LIU Y， WENG F. Why is “SXSW” trending？ Exploring multiple text sources for twitter topic summarization [C]// Proceedings of the 2011 ACL Workshop on Language in Social Media. Stroudsburg， PA： Association for Computational Linguistics， 2011： 66-75.

[3]

MUKHERJEE S， BHANACHARYYA P. Sentiment analysis in twitter with lightweight discourse analysis [C]// Proceedings of the 26th International Conference on Computational Linguistics. New York： ACM， 2012： 1847-1864.

[4]

TANG D， WEI F， YANG N， et al. Learning sentimentspecific word embedding for Twitter sentiment classification [C]// Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. Stroudsburg， PA： Association for Computational Linguistics， 2014： 1555-1565.

[5]

SAKAKI T， OKAZAKI M， MATSUO Y. Earthquake shakes Twitter users： realtime event detection by social sensors [C]// Proceedings of the 19th International Conference on the World Wide Web. New York： ACM， 2010： 851-860.

[6]

WENG J， LEE BS. Event detection in Twitter [C]// Proceedings of the 5th International Conference on Weblogs and Social Media. Menlo Park， CA： AAAI Press， 2011： 401-408.

[7]

BENSON E， HAGHIGHI A， BARZILAY R. Event discovery in social media feeds [C]// Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2011： 389-398.

[8]

HAN B， BALDWIN T. Lexical normalisation of short text messages： mken sens a #twitter [C]// Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2011： 368-378.

[9]

LIU X， ZHANG S， WEI F， et al. Recognizing named entities in tweets [C]// Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2011： 359-367.

[10]

FOSTER J， CETINOGLU O， WAGNER J， et al. #hardtoparse： POS tagging and parsing the twitter verse [C]// Proceedings of the AAAI Workshop on Analyzing Microtext. Menlo Park， CA： AAAI Press， 2011： 20-25.

[11]

LIU F， WENG F， WANG B， et al. Insertion， deletion， or substitution？ normalization text messages without precategorization nor supervision [C]// Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2011： 19-24.

[12]

HAN B， COOK P， BALDWIN T. Automatically constructing a normalization dictionary for microblogs [C]// Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Learning. Stroudsburg， PA： Association for Computational Linguistics， 2012： 421-432.

[13]

HASSAN H， MENEZES A. Social text normalization using contextual graph random walks [C]// Proceedings of the 51st Annual Meeting of the Association for Computation Linguistics. Stroudsburg， PA： Association for Computational Linguistics， 2013： 1577-1586.

[14]

WANG P， NG H T. A beam search decoder for normalization of social media text with application to machine translation [C]// Proceedings of the 2013 Conference of the North American Chapter of the Association for Computation Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2013： 471-481.

[15]

LI C， LIU Y. Improving text normalization via unsupervised model and discriminative reranking [C]// Proceedings of the ACL 2014 Student Research Workshop. Stroudsburg， PA： Association for Computational Linguistics， 2014： 86-93.

[16]

GOUWS S， HOVY D， METZLER D. Unsupervised mining of lexical variants from noisy text [C]// Proceedings of the First workshop on Unsupervised Learning in NLP. Stroudsburg， PA： Association for Computational Linguistics， 2011： 82-90.

[17]

NORRIS J R. Markov Chains [M]. Cambridge， UK： Cambridge University Press， 1997： 35-38.

[18]

HUGHES T， RAMAGE D. Lexical semantic relatedness with random graph walks [C]// Proceedings of the 2007 Conference on Empirical Methods in Natural Language Processing. Stroudsburg， PA： Association for Computational Linguistics， 2007： 581-589.

[19]

DAS D， PETROV S. Unsupervised partofspeech tagging with bilingual graphbased projections [C]// Proceedings of the 49th Annual Meeting of the Association for Computation Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2011： 600-609.

[20]

MINKOV E， COHEN W W. Graph based similarity measures for synonym extraction from parsed text [C]// TextGraphs712： Workshop Proceedings of TextGraphs7 on Graphbased Methods for Natural Language Processing. Stroudsburg， PA： Association for Computational Linguistics， 2011： 20-24.

[21]

MELAMED I D. Bitext maps and alignment via pattern recognition [J]. Computational Linguistics， 1999， 25（1）： 107-130.

[22]

CONTRACTOR D， FARUQUIE T， SUBRAMANIAM V. Unsupervised cleaning of noisy text [C]// Proceedings of the 23rd International Conference on Computation Linguistics. New York： ACM， 2010： 189-196.

[23]

PENNELL D， LIU Y. A characterlevel machine translation approach for normalization of SMS abbreviations [C]// Proceedings of the 5th International Joint Conference on Natural Language Processing. Stroudsburg， PA： Association for Computational Linguistics， 2011： 974-982.

本文的主要貢獻(xiàn)如下：

1）本文提出的文本規(guī)范化系統(tǒng)中，一個(gè)非標(biāo)注詞可以轉(zhuǎn)化為一個(gè)或多個(gè)標(biāo)準(zhǔn)詞。這種一對(duì)多的推特文本正規(guī)化是被首次提出的，更能滿足實(shí)際的應(yīng)用。

2）實(shí)驗(yàn)結(jié)果表明本文提出的系統(tǒng)取得了最較好的性能，比起之前最好的系統(tǒng)，本文所提方法在F值上提高了10%，這樣的結(jié)果可以使得提出的系統(tǒng)作為推特文本自然語(yǔ)言處理任務(wù)的預(yù)處理步驟。