# 新詞發現
###### tags: `Text` `Unsupervised`
中文有所謂的分詞歧義難題，如"已結婚的和尚未結婚的青年都要實行計劃生育"，還有更難的問題是"未登錄詞"，如機構、品牌、專有名詞、縮寫詞及網路新詞。所以透過"發現新詞"來增加機器字典量，即可更有效的完美斷詞。

## Information Entropy, 資訊熵(ㄕㄤ)
如果說機率是對事件確定性的度量，那麼資訊(包含資訊量和資訊熵)就是對事件不確定性的度量。資訊熵是由香濃(C. E. Shannon)在1948年發表的"A Mathematical Theory of Communication"中提出的概念。他借用熱力學中熱熵的概念(熱熵是表示分子狀態混亂程度的物理量)，解決了對資訊的量化度量問題，也常用來對不確定性進行度量。

* 資訊量在數學上表示為$I(X)=-logP(X)$
* 資訊熵則被定義為對平均不確定性的度量。一個離散隨機變數X的資訊熵H(X)定義為$H(X)=\sum_{X}P(X)log\dfrac{1}{P(X)}=-\sum_{X}P(X)logP(X)$

“資訊熵”是一個非常神奇的概念，它能夠反映知道一個事件的結果後平均會給你帶來多大的信息量。如果某個結果的發生概率為 p ，當你知道它確實發生了，你得到的信息量就被定義為 $–log(p)$。p 越小，你得到的信息量就越大。如果一顆骰子的六個面分別是1 、 1 、 1 、 2 、 2 、 3 ，那麼你知道了投擲的結果是1 時可能並不會那麼吃驚，它給你帶來的信息量是$–log(1/2)$，約為0.693 。知道投擲結果是 2 ，給你帶來的信息量則是$–log(1/3) ≈ 1.0986$。知道投擲結果是 3 ，給你帶來的信息量則有$– log(1/6) ≈ 1.79$。但是，你只有1/2 的機會得到0.693 的信息量，只有1/3 的機會得到1.0986 的信息量，只有1/6 的機會得到1.79 的信息量，因而**平均情況**下你會得到$0.693/2 + 1.0986/3 + 1.79/6 ≈ 1.0114$的信息量。這個 1.0114 就是那顆骰子的**資訊熵**。現在，假如某顆骰子有 100 個面，其中 99 個面都是 1 ，只有一個面上寫的 2 。知道骰子的拋擲結果是2 會給你帶來一個巨大無比的信息量，它等於$–log(1/100)$，約為4.605 ；但你只有百分之一的概率獲取到這麼大的信息量，其他情況下你只能得到$–log(99/100) ≈ 0.01005$的信息量。平均情況下，你只能獲得 0.056 的信息量，這就是這顆骰子的資訊熵。再考慮一個最極端的情況：如果一顆骰子的六個面都是 1 ，投擲它不會給你帶來任何信息，它的資訊熵為$–log(1) = 0$。

什麼時候資訊熵會更大呢？換句話說，發生了怎樣的事件之後，你最想問一下它的結果如何？直覺上看，當然就是那些結果最不確定的事件。沒錯，資訊熵直觀地反映了一個事件的結果有多麼的隨機。

:::info
* 資訊熵的本質是資訊量的期望。
* 資訊熵是對隨機變數不確定性的度量。隨機變數X的熵越大，說明他的不確定性也越大。若隨機變數退化為定值，則熵為0。
* 平均分布是"最不確定"的分佈。
* P越小，得到的資訊量越大。
* 反應一個事件的結果有多麼的隨機
:::

## Pointwise Mutual Information(PMI), 逐點互信息
探討兩個字之間是否帶有某種訊息。如果某兩個字的出現是獨立事件, 則 PMI = 0；若有兩個字出現的機率不是獨立事件, 某個字出現時提升另一個字的出現的機率, 則 PMI > 0。也就是說, 如果這兩個字的出現越不是偶然, 則PMI算出來的值越高, 越有可能帶有某種訊息。
$PMI(X, Y)=log\dfrac{P(X, Y)}{P(X)P(Y)}$
三次互信息: $MI^{3}(X, Y)=log\dfrac{P(X, Y)Count(X, Y)^{2}}{P(X)P(Y)}$

## 新詞指標
可能的方法: 首先不依賴於任何已有的詞庫，僅僅根據詞的共同特徵，將一段大規模語料中**可能成詞**的文本片段全部提取出來，不管它是新詞還是舊詞。然後，再把所有抽出來的詞和已有詞庫進行比較，不就能找出新詞了嗎？

### 詞頻
最簡單的方法，從這個文本中提取出現次數超過某個閾值的片段，作為該語料中的詞彙輸出。
:::success
詞組概率越大，則候選字串作為新詞的概率越小
$P_{phrase}(S)=\dfrac{P_{BC}(S)}{\prod_{i=1}^{n}P_{BC}(w_i)}$

$P_{BC}$: S在背景語料庫中出現的機率
:::

不過，光是出現頻數高還不夠，一個經常出現的文本片段有可能不是一個詞，而是多個詞構成的詞組。像是“的電影”出現了389 次，“電影院”只出現了175 次，然而我們卻更傾向於把“電影院”當作一個詞，因為直覺上看，“電影”和“院”凝固得更緊一些。

### 內聚程度
為了證明“電影院”一詞的內部凝固程度確實很高，我們可以計算一下，如果“電影”和“院”真的是各自獨立地在文本中隨機出現，它倆正好拼到一起的概率會有多小。在整個 2400 萬字的數據中，“電影”一共出現了 2774 次，出現的概率約為 0.000113 。 “院”字則出現了 4797 次，出現的概率約為 0.0001969 。如果兩者之間真的毫無關係，它們恰好拼在一起的概率就應該是 0.000113 × 0.0001969 ，約為 $2.223 × 10^{-8}$次方。但事實上，“電影院”在語料中一共出現了 175 次，出現概率約為 $7.183 × 10^{-6}$次方，是預測值的 300 多倍。類似地，統計可得“的”字的出現概率約為0.0166 ，因而“的”和“電影”隨機組合到了一起的理論概率值為0.0166 × 0.000113 ，約為$1.875 × 10^{-6}$，這與“的電影”出現的真實概率很接近——真實概率約為$1.6 × 10^{-5}$次方，是預測值的8.5 倍。計算結果表明，“電影院”更可能是一個有意義的搭配，而“的電影”則更像是“的”和“電影”這兩個成分偶然拼到一起的。
:::success
* 預測和實際上相差越多倍，代表放在一起的機率越大且有意義。
* 預測和實際上相差越接近，代表越是偶然拚在一起。
:::
#### PMI
當然，作為一個無知識庫的抽詞程序，我們並不知道“電影院”是“電影”加“院”得來的，也並不知道“的電影”是“的”加上“電影”得來的。錯誤的切分方法會過高地估計該片段的凝合程度。如果我們把“電影院”看作是“電”加“影院”所得，由此得到的凝合程度會更高一些。因此，為了算出一個文本片段的凝合程度，我們需要枚舉它的凝合方式——這個文本片段是由哪兩部分組合而來的。令p(x) 為文本片段x 在整個語料中出現的概率，那麼我們定義“電影院”的凝合程度就是p(電影院) 與p(電) · p(影院) 比值和p(電影院) 與p (電影) · p(院) 的比值中的較小值，“的電影”的凝合程度則是p(的電影) 分別除以p(的) · p(電影) 和p(的電) · p(影) 所得的商的較小值。
:::success
挑選互信息最小的作為單詞切分及內聚程度:

$MinMI^{3}(S)=\min_{0 < i \leq n}log\dfrac{P(S)Count(S)^{2}}{P(w_1, w_2, ..., w_i)P(w_{i+1}, w_{i+2}, ..., w_n)}$

e.g. S=電影院, $w_1=$電, $w_2=$影, $w_3=$院
:::
凝合程度最高的文本片段就是諸如“蝙蝠”、“蜘蛛”、“徬徨”、“忐忑”、“玫瑰”之類的詞了，這些詞裡的每一個字幾乎總是會和另一個字同時出現，從不在其他場合中使用。

### 自由程度(外部表現)
光看文本片段內部的凝合程度還不夠，我們還需要從整體來看它在外部的表現。考慮“被子”和“輩子”這兩個片段。我們可以說“買被子”、“蓋被子”、“進被子”、“好被子”、“這被子”等等，在“被子”前面加各種字；但“輩子”的用法卻非常固定，除了“一輩子”、“這輩子”、“上輩子”、“下輩子”，基本上“輩子”前面不能加別的字了。 “輩子”這個文本片段左邊可以出現的字太有限，以至於直覺上我們可能會認為，“輩子”並不單獨成詞，真正成詞的其實是“一輩子”、“這輩子”之類的整體。

#### 資訊熵
我們用資訊熵來衡量一個文本片段的左鄰字集合和右鄰字集合有多隨機。考慮這麼一句話“吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮”，“葡萄”一詞出現了四次，其中左鄰字分別為{吃, 吐, 吃, 吐} ，右鄰字分別為{不, 皮, 倒, 皮} 。根據公式，“葡萄”一詞的左鄰字的資訊熵為$– (1/2) · log(1/2) – (1/2) · log(1/2) ≈ 0.693$ ，它的右鄰字的資訊熵則為$– (1/2) · log(1/2) – (1/4) · log(1/4) – (1/4) · log(1/4) ≈ 1.04$ 。可見，在這個句子中，“葡萄”一詞的右鄰字更加豐富一些。

> 在人人網用戶狀態中，“被子”一詞一共出現了956 次，“輩子”一詞一共出現了2330 次，兩者的右鄰字集合的資訊熵分別為3.87404 和4.11644 ，數值上非常接近。但“被子”的左鄰字用例非常豐富：用得最多的是“曬被子”，它一共出現了162 次；其次是“的被子”，出現了85 次；接下來分別是“條被子”、 “在被子”、“床被子”，分別出現了69 次、 64 次和52 次；當然，還有“疊被子”、“蓋被子”、“加被子”、“新被子”、“掀被子” 、“收被子”、“薄被子”、“踢被子”、“搶被子”等100 多種不同的用法構成的長尾⋯⋯所有左鄰字的資訊熵為3.67453 。但“輩子”的左鄰字就很可憐了， 2330 個“輩子”中有1276 個是“一輩子”，有596 個“這輩子”，有235 個“下輩子”，有149 個“上輩子”，有32 個“半輩子”，有10 個“八輩子”，有7 個“幾輩子”，有6 個“哪輩子”，以及“n 輩子”、“兩輩子”等13 種更罕見的用法。所有左鄰字的資訊熵僅為 1.25963 。因而，“輩子”能否成詞，明顯就有爭議了。 “下子”則是更典型的例子， 310 個“下子”的用例中有294 個出自“一下子”， 5 個出自“兩下子”， 5 個出自“這下子”，其餘的都是只出現過一次的罕見用法。事實上，“下子”的左鄰字資訊熵僅為 0.294421 ，我們不應該把它看作一個能靈活運用的詞。當然，一些文本片段的左鄰字沒啥問題，右鄰字用例卻非常貧乏，例如“交響”、“後遺”、“鵝卵”等，把它們看作單獨的詞似乎也不太合適。我們不妨就把一個文本片段的自由運用程度定義為它的左鄰字資訊熵和右鄰字資訊熵中的較小值。

#### Accessor Variety, 鄰接變化數
$AV(S)=\min(LAV(S), RAV(S))$
- LAV(S): S的不同前驅字符的數目 + S在句首出現的次數
- RAV(S): S的不同後繼字符的數目 + S在句尾出現的次數

歸一化$NAV(S)=\dfrac{\min(LAV(S), RAV(S))^{2}}{Count(S)}$
:::success
"詞"應該能夠靈活地出現在各種不同的環境中，具有非常豐富的左鄰字集合和右鄰字集合。
* 自由度越大，代表越可能成詞
* 自由度 = min(LIE, RIE)，左鄰字資訊熵和右鄰字資訊熵中的較小值
:::

## 混合運用
文本片段的凝固程度和自由程度，兩種判斷標準缺一不可。只看凝固程度的話，程序會找出“巧克”、“俄羅”、“顏六色”、“柴可夫”等實際上是“半個詞”的片段；只看自由程度的話，程序則會把“吃了一頓”、“看了一遍”、“睡了一晚”、“去了一趟”中的“了一”提取出來，因為它的左右鄰字都太豐富了。

### 執行流程
1. 確定詞彙邊界: 挑選候選詞，需設定詞的長度上限
2. 確定新詞語義: 計算這些候選詞的**詞頻、內聚程度、自由程度**，並各設定閥值
3. 以上下界值過濾，提取出所有滿足閥值要求的候選詞
4. 將所有抽取出來的詞與已有詞庫做對比，即可得到新詞!
5. 人工驗證哪些詞是否要加入字典

## [Python 實作例子](https://github.com/Rayarrow/New-Word-Discovery)
### Workflow
1. 中文斷詞: 使用jieba，cut_all默認為False(精確模式)，HMM默認為True(新詞識別)。
* 精確模式: 試圖將句子最精確地切開，適合文本分析
* HMM: 對於未登錄詞，採用了基於漢字成詞能力的 HMM 模型，使用了 Viterbi 算法
2. 新詞發現: 考量特徵包含
* term frequency
* aggreagation coefficient
* max neighboring entropy
* min neighboring entropy
3. 字典: 包含專家已給定的單詞&常用單詞(如我們、上班)。
4. 關鍵字抽取: 識別相對重要的新詞。jieba.analyse.textrank(doc, topK=20, withWeight=True, allowPOS=nouns)
5. 若候選新單詞有出現在關鍵字中，則視為較重要的新單詞。


### 新詞類型
* 拉丁詞，包括：純數字 (2333, 12315, 12306)、純字母 (iphone, vivo)、數字字母混合 (iphone7, mate9)
* 兩個中文字符的unigram (unigrams被定義為分詞器產生的元素):馬蓉，優酷，楊洋
* 三個中文字符的unigram:李易峰，張一山，井柏然
* bigrams, 每個bigram由兩個unigram組成: 圖片大全，英雄聯盟，公交車路線，穿越火線

## 延伸
新詞發現包含兩個基本任務
1. 確定詞彙邊界: 建議閱讀Stanford NLP Group的專著Foundations of Statistical Natural Language Processing第5章關於collocations的相關介紹。
2. 確定新詞語義: 典型任務包括相關詞發現、領域詞擴展等等，像latent topic models、word representation、explicit semantic analysis等模型都可以用於解決這個問題。

## 參考
* [互联网时代的社会语言学：基于SNS的文本数据挖掘](http://www.matrix67.com/blog/archives/5044)
* [Java 實作例子](https://github.com/sing1ee/dict_build)
* [jieba github](https://github.com/fxsjy/jieba)
* [结合无监督学习和迁移学习的新词发现实践](https://zhuanlan.zhihu.com/p/32459531)