# 文字、數字、語言 、信息
數字、文字和自然語言一樣，都是信息的載體，他們的產生都是為了**記錄和傳播信息**。
但是貌似數學與語言學的關系不大，在很長一段時間內，數學主要用于天文學、力學。
本章，我們將回顧一下信息時代的發展，看語言學如何慢慢與數學聯系起來的。
## 信息
最開始的時候，人類會用**聲音**來傳播信息。
這里面的信息的產生、傳播、接收、反饋，與現在最先進的通信在原理上沒有任何差別。
因為早期人類需要傳播的信息量不多，所以不需要語言文字。
但是當人類進步到一定的程度的時候，就需要語言了。
所以我們的祖先將語言描述的共同因素，比如物體、數量、動作便抽象出來，形成了今天的詞匯。
## 文字和數字
### 文字的產生
隨著人類的發展，語言和詞匯多到一定的程度，大腦已經無法完全記住了。此時就需要一種**文字**，將信息記錄下來。
使用文字的好處在于，信息的傳輸可以跨越時間、空間了，兩個人不需要在同一時間，同一地點碰面就可以進行信息的交流。
那么如何創造文字呢？最直接的方式就是模仿要描述對象的形狀，這就是所謂的象形文字。
### 文字的聚類
早期，象形文字的數量和記錄一個文明的信息量是相關的，也就是說象形文字多，代表著這個文明的信息量大。
但是隨著信息量的增加，沒有人能學會和記住這么多的文字，這樣就需要進行**概括和歸類**了。也就是使用一個詞來表達相同和相似的一類意思。
比如說“日”本來是說太陽，但是它又同時可以是我們講的一天。
這種概念的聚類，和現在自然語言處理或者機器學習的**聚類**很相似，只是在遠古，可能需要上千年，而現在只需要幾小時。
但是文字按照意思來聚類，總會有**歧義性**，也就是弄不清楚一個**多義字**在特定環境下表示其中哪一個含義。
要解決這個問題，都是**依靠上下文**，大多數Disambiguation可以做到，但總有個別做不到的時候。**對上下文建立的概率模型再好，也會有失靈的時候。**
### 翻譯
不同的文明因為地域的原因，文字和語言一般來說是不同的，當兩個文明碰在一起的時候，翻譯的需求就有了。
**翻譯能達成的原因：不同的文字系統在記錄信息的能力上是等價的**，文字只是信息的載體，而不是信息的本身，甚至可以用數字進行搭載。
今天，我們對埃及的了解比瑪雅文明多，要歸功于埃及人通過文字記錄了生活中最重要的信息，對我們的指導意義在于：
- 同一個信息重復三份，只要有一份保留下來，原有的信息就不會丟失，這對信道編碼有指導意義。
- `語料`，也就是語言的數據，至關重要。
### 數字的產生
文字是在頭腦里面已經裝不下信息的時候才出現，而數字則是在財產需要數一數才能搞清楚的時候才產生。
早期的數字沒有書寫的形式 ，只是說掰指頭，這也是我們使用**十進制**的原因。
漸漸地，祖先發現十個指頭也不夠用了，最簡單的方法是把腳趾頭也算上，但是不能解決根本問題。于是他們發明了**進位制**，也就是逢十進一。
那為什么現有的文明多用十進制，而不是二十進制呢？
相比十進制，20進制多有不便，比如說十進制只需要背誦九九乘法表，如果是20進制的話，就需要背19*19的圍棋盤了。
對于不同位數的數字表示，中國人和羅馬人都用明確的單位來表示不同的量級。
中國人是用十百千萬億兆，羅馬人用I表示個，V表示5等等。
這兩種表示法都不自覺的引入了樸素的編碼的概念。
- 用不同的符號代表不同的數字概念。
- 制定了**解碼**的規則：中國的解碼規則是乘法，比如200萬的寫法意味著2 * 100 * 10000，而羅馬的解碼規則是加減法——小數字出現在大數字左邊為減，右邊為加，比如IV表示5-1=4，VII表示5+2=7，這個規則相當復雜，而且對于大的數字難以描述。
從編碼的有效性來說，中國人更高明。
描述數字最有效的是古印度人，他們發明了10個阿拉伯數字，比中國和羅馬的都抽象，這也標志著數字和文字的分離。客觀上讓自然語言與數學在幾千年沒有重復的軌跡。
## 文字和語言背后的數學
### 最短編碼原理
從象形文字到拼音文字是一個飛躍，因為人類在描述物體的方式上，從物體的外表到抽象的概念，同時不自覺的采用了對信息的編碼。
不僅如此，在羅馬體系的文字中，常用字短，生僻字長，在意型文字中，也是一樣，常用字筆畫少，而生僻字筆畫多，這符合信息論中的**最短編碼原理。**
羅馬語言體系：
```flow
st=>start: 楔形文字
op1=>operation: 敘利亞
op2=>operation: 古希臘
op3=>operation: 羅馬人和馬其頓人
en=>end: 羅馬式語言
st->op1->op2->op3->en
```
在紙發明之前，書寫文字并不容易。所以需要惜墨如金，所以古文這種書面文字非常簡潔，但是非常難懂。而口語卻與現在差別不大。這就和現在的信息科學的一些原理類似
- 在通信時，如果信道較寬，信息不必壓縮就可以直接傳遞；
- 而如果信道很窄，信息在傳遞前需要盡可能地壓縮 ，然后在接收端進行解壓縮。
這點就是現在的互聯網與移動互聯網的網頁設計完全一致。
使用寬帶的話，頁面得設計得比較大，而手機終端上的由于受空中頻道帶寬的限制，傳輸速度慢，分辨率低。
### 校驗
《圣經》記錄了創世紀以來，猶太人祖先的故事，《圣經》的寫作持續了很多世紀，有若干人來完成，抄寫的錯誤在所難免，
為了避免抄錯，猶太人發明了一種類似**校驗碼**的方法，他們把希伯來字母對應于一個數字，每行加起來就是一個特殊的數字，這個數字即為**校驗碼**。
當抄完一頁以后，需要把每一行的文字加起來，看看校驗碼與原文是否相同。
### 語法
從字母到詞的構詞法是詞的編碼規則，那么語法則是語言的編碼和解碼規則。
相比較而言，**詞是有限且封閉的集合， 語言則是無限和開放的集合。**從數學上來講，前者有完備的編解碼規則，而語言則沒有，也就是說語言有語法規則覆蓋不到的地方，這就是“病句”
那么到底是語言對，還是語法對呢？有人堅持從真實的語料中出發，有人堅持從規則出發。
## 小結
本章講述了文字、數字、語言的歷史，幫助讀者感受語言和數學內在的聯系。提到了如下的概念
- **通信的原理和信息傳播的模型**
- ( 信 源 ）編碼和最短編碼：文言文。
- 解碼的規則：語法
- 聚類：一個字多個意思
- 校驗位：一個希伯來字對應一個碼 。
- 雙語對照文本，語料庫和機器翻譯：信息載體相同。
- 多義性和利用上下文消除歧義性：概率
# 自然語言處理——從規則到統計
上一章我們說到，語言出現的目的就是為了人類的通信，而字母、文字、數字實際上是**信息編碼**的不同單位。
任何一種語言都是一種編碼方式，而語言的語法規則是編解碼的算法。比如，我們把想要表達的東西通過語言組織起來，這就是進行了一次編碼，如果對方能懂這個語言，它就可以使用這門語言的解碼方式進行解碼。
那么機器是否可以讀懂自然語言呢？當然可以
## 機器智能
自然語言處理發展過程可以分為兩個階段：
- 從 2 0 世 紀 5 0 年代到7 0 年代，科學家的認識局限在人類學習語言的方式上了，也就是用電腦模擬人腦。成果幾乎為0.
- 70年代以后進入了第二階段，也就是**基于數學模型和統計的方法。**取得了實質性的突破。
50年代，學術界對人工智能和自然語言理解的認識是這樣的：要讓機器完成語音識別，必須讓計算機理解自然語言。因為人類就這么做的。這種方法論就稱為“鳥飛派”，也就是看鳥怎么飛的來造出飛機。事實上，人們發明飛機靠的是空氣動力學，而不是仿生學。
那么如何才能理解自然語言呢？
一般需要：
- 分析語句，也就是通過語法。這些語法規則比較容易能用計算機描述。
- 獲取語義。語義比語法更難在計算機中表達出來，
我們可以看一個簡單的句子
> 徐志摩喜歡林徽因
這個句子可以分為主、謂、句號三部分，可以對每個部分進一步分析，得到如下的語法分析樹(Parse Tree)
分析它采用的文法規則稱為**重寫規則**
但是這種方法很快遇到了麻煩。從上圖可以看出**一個短短的句子居然分析出這么一個復雜的二維樹結構**，如果要處理一個真實的句子就非常的麻煩了。
主要有兩個坎兒：
- 要想通過文法規則覆蓋哪怕20% 的真實語句，文法規則的數至少是幾萬條。
而且這些文法規則甚至有矛盾，所以還需要說明規則的使用環境。如果要覆蓋50%以上的語句，文法規則的數量最后會多到每增加一個新的句子，就需要加入新的文法
其實很容易理解，無論在中學或者大學的時候，英語成績多么好，也未必考得好GRE，因為我們學了10年的英語語法也無法覆蓋全部的英語。
- 即使能覆蓋所有的語法，計算機來解析一個復雜的句子也是比較困難的。而且自然語言的詞義與上下文有特定的關系 ，也就是上下文有關文法，所以解析起來的計算量相當大。
那么其實從語法這條路來分析句子，并不靠譜。
## 從規則到統計
上面我們講到了基于規則的句法分析對于語義處理比較麻煩，因為 自然語言中的詞的多義性難用規則來描述，而是依賴于**上下文**。
比如 “The box is in the pen.” 因為這里pen是圍欄的意思。整句話翻譯成中文就是“ 盒子在圍欄里” 。這 里 面 pen是指鋼筆還是圍欄 ，通過上下文已經不能解決，需要常識
1970年以后統計語言學讓自然語言處理重獲新生，里面的關鍵任務是賈里尼和他領導的IBM華生實驗室。最開始的時候，他們使用統計的方法，將當時的語音識別率從70%提升到90%，同時語音識別規模從幾百單詞上升到幾萬單詞
## 小結
基于統計的自然語言處理方法，在數學模型與通信是相通的，因此在數學意義上，自然語言處理又和語言的初衷——**通信**聯系在一起了。
# 統計語言模型
前面的章節，我們一直強調，自然語言從產生開始，逐漸演變成一種上下文相關的信息表達和傳遞方式。
所以要讓機器能處理自然語音，**關鍵在于**為自然語音這種**上下文相關的**特性建立數學模型，這就是**統計語言模型(Statistical Language Model)**
這個模型廣泛應用于機器翻譯、語音識別、印刷體識別、拼寫糾錯、漢字輸入、文獻查詢
## 用數學的方法描述語言規律
語音識別需要解決的一個重要的問題就是計算機給出來的一個文字序列，是否能被人類所理解。70年代以前，人們使用語義分析來解決。
而賈里克從另一個角度來看待這個問題，一個簡單的統計模型就搞定了。
也就是說要看一個句子是否合理，就看看它的**可能性**大小如何 。
比如說一個通順的語句出現的概率為$10^{-20}$，而一個亂七八糟的語句出現的概率為$10^{-70}$，所以通順的語句更有可能。
假定$S$表示一個有意義的句子，由一串特定順序的詞${\omega _1},{\omega _2}, \cdots ,{\omega _n}$組成，這里$n$是句子的長度。現在需要知道這個句子出現的概率
$$P\left( S \right) = P\left( {{w_1},{w_2}, \cdots ,{w_n}} \right)$$
利用條件概率的公式，$S$這個序列出現的概率等于每個詞出現概率相乘
$$P\left( {{w_1},{w_2}, \cdots ,{w_n}} \right) = P\left( {{w_1}} \right)P\left( {{w_2}|{w_1}} \right) \cdots P\left( {{w_n}|{w_1},{w_2}, \cdots ,{w_{n - 1}}} \right)$$
> $P\left( {{w_n}|{w_1},{w_2}, \cdots ,{w_{n - 1}}} \right)$表示詞$w_n$出現的概率取決于它前面的所有詞。
問題就來了，這種條件概率怎么計算呢？
20世紀初，俄國的數學家馬爾科夫給出了一個有效的方法，當遇到這種情況的時候，假設任意一個詞$w_i$出現的概率只與前面的詞$w_{i-1}$有關，與其他詞無關，這就叫**馬爾科夫假設**
所以公式又變成了
$$P\left( {{w_1},{w_2}, \cdots ,{w_n}} \right) = P\left( {{w_1}} \right)P\left( {{w_2}|{w_1}} \right) \cdots P\left( {{w_n}|{w_{n - 1}}} \right)$$
這就叫**二元模型(Bigram Model)**
如果假設一個詞由前面$N-1$個詞決定，對應的模型就叫$N
$元模型，會更復雜。
同樣那么如何估算條件概率$P\left( {{w_i}|{w_{i - 1}}} \right)$,可以先看一下它的定義
$$P\left( {{w_i}|{w_{i - 1}}} \right) = \frac{{P\left( {{w_{i - 1}},{w_i}} \right)}}{{P\left( {{w_{i - 1}}} \right)}}$$
需要做的是估計
- **聯合概率${P\left( {{w_{i - 1}},{w_i}} \right)}$**：連續兩個詞同時出現的概率
- 以及邊緣概率${P\left( {{w_{i - 1}}} \right)}$
**那么這兩種概率如何得到？**
有了大量的語料庫(Corpus)以后，只要數一下${{w_{i - 1}},{w_i}}$在統計的文本前后相鄰出現了多少次${\# \left( {{w_{i - 1}},{w_i}} \right)}$即可。然后除以語料庫的大小#，這樣就可以使用**頻度**來估計概率了。
根據**大數定理**，只要統計量足夠，相對頻度就等于概率。
$$P\left( {{w_i}|{w_{i - 1}}} \right) = \frac{{\# \left( {{w_{i - 1}},{w_i}} \right)}}{{\# \left( {{w_{i - 1}}} \right)}}$$
居然用這么復雜的模型就可以解決復雜的語音識別、機器翻譯的問題。
## 統計語言模型的工程訣竅
### 高階語言模型
二元模型最大的特點在于，每個詞只與前面一個詞有關，太簡化了，更普遍的是某個詞與前面若干詞都有關。
所以$N$元模型指的就是當前詞$w_i$只取決于前$N-1$個詞，這就是`N-1階馬爾科夫假設`
實際中，三元模型用得多更多，所以$N=3$，而更高階的就比較少用了，因為
- 模型階數大，復雜度高。
$N$元模型的大小，幾乎是$N$的指數，所以$N$不能太大。當$N$從1到2，再從2到3的時候，模型的效果上升顯著，而模型從3到4，效果提升就不明顯了，耗費的資源卻很多。所以很少有人使用4元以上的模型
- 縱然是提升了階數，依然不能覆蓋所有的語言現象。比如說從一個段落跨到另一個段落，即使階數更高，對這種情況也無可奈何。這時需要其他的長程依賴性來解決(long Distance Dependency)
### 模型的訓練、零概率問題和平滑方法
使用語言模型需要知道模型中所有的**條件概率**，我們稱之為`模型的參數`。
通過對語料的統計，得到這些參數的過程稱作`模型的訓練`。
之前我們講過，只需要統計出相鄰兩個字符同時出現的次數以及${w_{i - 1}}$單獨出現的次數，然后計算一下比值即可。
但是有一種情況我們沒有考慮，如果相鄰兩個詞并沒有同時出現過，也就是$\# \left( {{w_{i - 1}},{w_i}} \right) = 0$怎么辦，是否就說明概率為0。
當然不是，這就涉及到統計的**可靠性**了。
在數理統計中，我們之所以敢用采用數據來預測概率，是因為**大數定理**，它的要求是有足夠的觀測值。也就是如果樣本太小，則使用次數來預測概率當然不靠譜。
那么如何正確的訓練一個語言模型呢？
- 直接的方法就是**增加數據量**。但是也依然會遇到零概率的問題，稱之為`“不平滑”`
- 對于不平滑的的概率，我們不能認為它發生的概率為零，可以從概率的總量中，分配一個很小的比例給予這些沒有看見的事件。
這樣一來，看見的那些事件的概率總和就要小于1了，因此，需要將所有看見的亊件概率調小一點。至于小多少，要根據**“越是不可信的統計，對它的折扣越多”**的方法進行。
下面以統計詞典中每個詞的概率來具體講講。
假定在語料庫中出現$r$次的詞有$N_r$個，$N$表示語料庫的大小。
$$N = \sum\limits_{r = 1}^\infty {r{N_r}} $$
也就是說每個詞出現的$r$詞的詞的個數與出現了多少次相乘。
當$r$比較小，說明出現的次數不夠多，那么在計算它們的概率的時候要使用一個更小一點的次數，比如$d_r$
$${d_r} = \left( {r + 1} \right)\frac{{{N_{r + 1}}}}{{{N_r}}}$$
而且
$$\sum\limits_r {{d_r}{N_r}} = N$$
一般來說，**出現1次的詞的數量比出現兩次的多，同樣出現兩次比出現三次的多。**
也就是出現的次數$r$越大，詞的數量$N_r$越小，所以${N_{r + 1}} < {N_r}$，可以看出${d_r} < r$，這樣估算是因為$d_r$是我們要找的那個比$r$更小的數，而當只出現0次的時候${d_0}>0$
這樣，
- 對頻率超過一定閾值的詞，它們的概率估計就是語料庫中的相對頻度
- 對于頻率小于閾值的詞，概率估計就小于他們的相對頻度。
對于二元模型，
其中
- $T$是一個閾值，一般在8~10左右。
- $f_{gt}()$表示經過平滑處理以后的相對頻度
- 而$Q(w_{i-1})$可以保證所有的頻率加起來為1.
這種平滑的方法最早是由IBM的卡茨提出來的，所以稱為**卡茨退避法**
還有一種方法是**刪除差值**法，也就是用低階模型和高階模型進行線性插值的方法來平滑處理，但是因為效果差于卡茨退避發，所以很少使用了。
### 語料的選取問題
模型訓練中另一個重要問題是**訓練數據**，或者說是語料庫的選取，如果訓練預料和模型應用的領域相脫節，模型的效果也要大打折扣。
比如對于建立一個語言模型，如果應用是網頁搜索，它的訓練數據就應該是**雜亂的網頁數據**和用戶輸入的搜索串，而不是傳統的、規范的新聞稿 ，即使前者夾雜著噪音和錯誤。因為訓練數據和應用一致，搜索質量反而更好。
訓練數據通常是越多越好，高階模型因為參數多，需要的訓練數據也相應會多很多，遺憾的是，并非所有的應用都能有足夠的訓練數據，比如機器翻譯的雙語語料，這個時候，追求高階的大模型沒有任何意義。
如果訓練數據和應用數據一致了，而且訓練量足夠大了以后，訓練預料的噪音高低也會對模型產生影響。所以訓練之前需要進行預處理，對于可以找到規律的而且還比較多的噪音需要進行處理，比如制表符
# 中文分詞
## 演變
對于西方拼音來說，詞之間有明確的分界符(Delimit)。但是對于中文來講，詞之間沒有明確的分界符。所以需要先對句子進行分詞。
最容易想到的方法就是**查字典**也就是說，從左到右掃描一遍，遇到字典里面有的詞就標識出。
但是這種方法遇到復雜的問題就不行了。比如說遇到**二義性**的分割時。像“發展中國家”，正確的分割是“發展-中-國家”，而從左向右查字典會分割為“發展-中國-家”
同樣我們可以使用**統計語言模型**來解決分詞二義性的問題。
假定一個句子$S$有幾種分詞方法：
$$\begin{array}{l}
{A_1},{A_2},{A_3}, \cdots ,{A_k}\\
{B_1},{B_2},{B_3}, \cdots ,{B_m}\\
{C_1},{C_2},{C_3}, \cdots ,{C_n}
\end{array}$$
**最好的分詞方法**就是分完詞以后，這個句子出現的概率最大。
當然如果窮舉所有的分詞方法，并計算每種可能性下的句子的概率，那么計算量是相當大的。
可以看作是一個**動態規劃(Dynamic Programming)**問題，并利用**維特比(Viterbi)算法**快速的找到最佳分詞
語言學家對詞語的定義不完全相同，比如說“北京大學”，有人認為是一個詞，有人認為是兩個詞。折中的方法就是先當做一個四字詞，然后再進一步找到細分詞“北京”和“大學”
## 工程上的細節
人工分詞產生不一致性的主要原因在于人們對詞的**顆粒度**的認識問題。
比如說“清華大學”，有人認為是一個整體，有人認為“清華”是修飾“大學”的。這里不需要去強調誰的觀點正確，而是應該知道，在不同的應用里面，會有一種顆粒度比另一種更好的情況。
比如說在機器翻譯中，顆粒度大翻譯效果好，比如“聯想公司”如果拆分為開，很難翻譯為“Lenovo”。但是在網頁搜索里面，小的顆粒度會比大的要好，比如用戶查詢“清華”而不是“清華大學”一樣可以查詢到清華大學的主頁。
如果為不同的應用構建不同的分詞器，太過浪費。可**以讓一個分詞器同時支持不同層次的詞的切分。**
- 首先需要一個基本的詞表和一個復合詞表。
基本詞表包括“清華”、“大學”、“賈里尼克”這樣無法再分的詞
復合詞表包含復合詞以及它們由哪些基本詞構成，包括像“清華大學：清華-大學”
- 接下來需要根據**基本詞表**和**復合詞表**各建立一個語言模型：L1,L2
- 根據基本詞表和L1進行分詞，就得到小顆粒度的分詞結果。一般來說，基本詞比較穩定，偶爾才會增加點新詞。
- 最后，再用復合詞表和L2進行第二次分詞，此時輸入的是**基本詞串**，輸出的是復合詞串。
也就是說先把句子按照基本詞進行分割，再把基本詞串按照復合詞模型再分割。
