一個基本的搜索引擎的工作，基本上可以分成以下三個部分：

1. 利用網(wǎng)絡(luò)爬蟲下載網(wǎng)頁，分析網(wǎng)頁關(guān)鍵詞，制成索引備用；
2. 理解用戶輸入，確定檢索關(guān)鍵詞；
3. 根據(jù)關(guān)鍵詞和網(wǎng)頁索引，按照相關(guān)性排序列出搜索結(jié)果。

第一個部分主要涉及網(wǎng)絡(luò)爬蟲技術(shù)、圖論、自然語言處理等技術(shù)；第二個部分主要涉及自然語言處理；第三個部分同樣涉及自然語言處理。

自然語言，即是人類用來交流的語言。

由此可見，自然語言處理（NLP, Natural Language Processing）是現(xiàn)代搜索引擎很重要的內(nèi)容，其終極目的是將自然語言轉(zhuǎn)化為計算機(jī)容易處理的形式。

從分詞的角度來看文法分析與統(tǒng)計模型

分詞是 NLP 需要解決的基礎(chǔ)問題，分詞算法的好壞直接影響 NLP 的結(jié)果。

這里我們先從一個簡單的例子說起，逐步探討合理的分詞算法。

從一個簡單的句子說起

現(xiàn)在有一個句子，比如：

• 我去電腦城買了一臺電腦。

如果要讓計算機(jī)對這個句子做分詞處理，進(jìn)而理解這個句子，你會有怎樣的思路呢？

大多數(shù)人首先會思考一下自己是怎么理解這個句子的。對于中國人來說，這樣一個簡單的句子，可能不需要什么特殊的思維過程。句子的文字形式和句子背后的含義可以在瞬間反映出來。稍有漢語文法知識的讀者，可能會想：

1. 句子可以分成幾個部分
   • 我 - 主語
   • 去電腦城買了一臺電腦 - 謂語
     • 去電腦城 - 狀語
     • 買了 - 謂語動詞
     • 一臺電腦 - 動詞賓語（名詞短語）
   • 。 - 句子結(jié)束的標(biāo)識
2. 分別理解每個部分的意思
3. 將意思拼合起來，變成完整的句意

它先通過文法分析，將句子拆分成一個二維的語法樹，然后再理解各個部分的含義，最后做拼接。

這樣的方案（或者說是算法）是基于文法規(guī)則的，清晰明了，也易于實現(xiàn)（在計算機(jī)里就是幾個循環(huán)判斷）。對于程序員來說，這樣的算法也特別親切。因為程序員使用的高級編程語言（比如 C++）的語法規(guī)則和這樣的方案非常相似。

由于這樣的算法直觀、易于實現(xiàn)，所以人們相信在有了愈加全面的文法概括和愈加強(qiáng)大的計算能力時，人們就能徹底解決自然語言處理的問題了。

文法分析的困境

然而，如果你仔細(xì)觀察文法分析的過程就會發(fā)現(xiàn)，這么一個簡單的句子被分成了一個這樣復(fù)雜的二維樹狀結(jié)構(gòu)，耗費(fèi)了六條注釋。用計算機(jī)來處理這樣一個過程當(dāng)然不難，但是要處理現(xiàn)實生活中遇到的真實句子，往往就不那么容易了：

• 由于理解（understanding）自然語言，需要關(guān)于外在世界的廣泛知識以及運(yùn)用操作這些知識的能力，自然語言認(rèn)知，同時也被視為一個人工智能完備（AI-complete）的問題。

這個句子依然可以用上述方法來處理：

• 先分成主謂部分
• 再仔細(xì)拆分謂語部分

比如：

• 自然語言認(rèn)知 - 主語 - 偏正短語
  • 自然語言 - 名詞作定語修飾
  • 認(rèn)知 - 名詞
• 由于理解（understanding）自然語言，需要關(guān)于外在世界的廣泛知識以及運(yùn)用操作這些知識的能力 … 同時也被視為一個人工智能完備（AI-complete）的問題 - 謂語
  • 由于理解（understanding）自然語言，需要關(guān)于外在世界的廣泛知識以及運(yùn)用操作這些知識的能力 - 原因狀語
    • …
    • …
  • 同時也被視為 - 謂語動詞短語
    • 同時 - 狀語
    • 也被視為 - 謂語動詞
  • 一個人工智能完備（AI-complete）的問題 - 動詞賓語
    • 一個 - 定語
    • 人工智能完備的 - 定語
    • 問題 - 名詞
  • 。 - 句子結(jié)束的標(biāo)志

這個句子的語法分析樹我沒有寫完，因為實在太復(fù)雜了。顯而易見，單純基于文法分析的分析器是很難處理生活中的真實句子的。

那么問題出在哪里？我認(rèn)為至少有兩個問題。

1. 文法規(guī)則數(shù)量巨大，上萬條語法規(guī)則才只能覆蓋約 20% 的真實句子；且有些為了處理特殊情況的語法規(guī)則和其他規(guī)則相互矛盾。
2. 自然語言與程序設(shè)計語言不同，自然語言中詞匯的具體含義與上下文相關(guān)，而程序設(shè)計語言則沒有這樣的歧義性。

從算法復(fù)雜度的角度來說，單純基于文法分析的分析器，用于分析自然語言，其復(fù)雜度比分析程序設(shè)計語言要高出四個量級。從直觀的印象來說，上述句子在一臺現(xiàn)代計算機(jī)上用文法分析的方式處理，也需要至少一分鐘的時間。這種低效是無法接受的。

查字典分詞法

在之前的文法分析方法里，分詞依賴于文法分析的結(jié)果。程序要先輸出語法樹，然后才能得到分詞結(jié)果。而這樣的方法已經(jīng)被證明是低效的。

這樣的低效來源于復(fù)雜的文法分析過程。為了提高效率，人們很自然地想到：是否有辦法繞開文法分析，直接嘗試分詞呢？對于中文分詞，北京航空航天大學(xué)的梁南元教授提出了查字典分詞法。做法相當(dāng)簡單，比如對于下列句子：

• 山東大學(xué)數(shù)學(xué)學(xué)院是中國最好的數(shù)學(xué)基礎(chǔ)教育基地之一。

我們讓計算機(jī)從左到右掃描整個句子，每掃到一個字，就往字典里查詢，遇到字典里有的詞就標(biāo)注出來。于是整個句子就被分割成了這樣：

• 山東|大學(xué)|數(shù)學(xué)|學(xué)院|是|中國|最好的|數(shù)學(xué)|基礎(chǔ)|教育|基地|之一。

看起來結(jié)果不錯。不過細(xì)心的讀者很快就會發(fā)現(xiàn)：山東大學(xué)和基礎(chǔ)教育都是完整的詞，在它們之間不應(yīng)該再做劃分。會出現(xiàn)這種情況也不意外，我們要求計算機(jī)從左到右掃描。當(dāng)計算機(jī)遇到「山東」二字的時候，就認(rèn)為這是一個詞了，自然不會再去尋找下一個字去尋求匹配。同理基礎(chǔ)教育。

梁教授提出了一個方案，即總是搜尋盡可能長的分詞。這在計算機(jī)科學(xué)領(lǐng)域叫做「貪婪」。運(yùn)用貪婪的辦法，上述句子的分詞就會變成：

• 山東大學(xué)|數(shù)學(xué)|學(xué)院|是|中國|最好的|數(shù)學(xué)|基礎(chǔ)教育|基地|之一。

看起來就沒什么問題了。

不過，漢語博大精深，這種辦法也不能一勞永逸。比如：

• 大學(xué)生活區(qū)

正確的分詞應(yīng)該是：

• 大學(xué)|生活區(qū)

但是按照貪婪的辦法，會被分詞成：

• 大學(xué)生|活|區(qū)

這就不對了。

又比如：

• 發(fā)展中國家

正確的分詞應(yīng)該是：

• 發(fā)展中|國家

而不是：

• 發(fā)展|中國|家

可見，查字典的辦法雖然效率很高，但是時有出錯，并不牢靠。

查字典的辦法遇到的困境來自于自然語言的歧義性。人類在閱讀自然語言時，會結(jié)合上下文判斷有多個意向的詞匯在文中的具體含義，但是計算機(jī)卻沒有這個能力。實際上，中國傳統(tǒng)文學(xué)里說的「句讀」，其目的就是通過分詞斷句來消除歧義。那么，怎么讓計算機(jī)具備這樣的能力呢？

千呼萬喚始出來的統(tǒng)計模型

行文至此，數(shù)學(xué)終于要第一次展現(xiàn)其威力和美麗。

我們之前提到，對一個句子做分詞，其正確與否和詞匯的二義性緊密相關(guān)。由于計算機(jī)無力綜合上下文判斷詞匯含義，解決二義性，所以查字典的辦法陷入了困境。

數(shù)學(xué)中有所謂的「反證法」。在這里我們不講反證法，但是要講講反證法的思想。反證法的核心思想就是「正難則反」：正面突破很困難，那就不走大路，開個后門照樣進(jìn)城。在這里，既然計算機(jī)沒有能力綜合上下文解決詞匯的二義性，那么我們就不依賴計算機(jī)智能去解決，轉(zhuǎn)而借助人工的力量解決。當(dāng)然，我說的不是找一個工人實時干預(yù)程序的運(yùn)行，幫助程序作出正確的判斷；而是說，讓計算機(jī)經(jīng)過大量的文本訓(xùn)練，吸取人類的「分詞經(jīng)驗」。而這個方法，就是統(tǒng)計模型。

假定一個句子 可以有幾種分詞的方案，比如有以下三種：

123.png

其中， 等都是漢語的詞匯。這樣一來，如果 (1)是最好的分詞，那么(1)出現(xiàn)的概率應(yīng)該最大。也就是說，分詞方案 (1)應(yīng)該滿足(4)。

4.png

答案就是這么簡單。

當(dāng)然，如何處理 (4)需要一點統(tǒng)計知識和技巧；得到這些分詞方案也需要依靠動態(tài)規(guī)劃算法（不然計算量太大）；還有諸如分詞顆粒大小之類的細(xì)節(jié)問題需要處理。這些內(nèi)容我們放在后續(xù)的小節(jié)里討論，在這里，讀者只需要知道這種利用統(tǒng)計的方法處理分詞效果好、效率高就可以了。

小結(jié)

對于分詞來說，統(tǒng)計模型的方法效率比文法分析的方法高，同時效果也要好。這里效率的提升是十分顯著的。

此外，我們發(fā)現(xiàn)一個優(yōu)秀算法背后的數(shù)學(xué)模型是十分簡潔優(yōu)美的。統(tǒng)計模型只需要一個概率不等式組就可以描述，而文法分析模型幾乎無法構(gòu)建一個可讀的數(shù)學(xué)模型。我們在設(shè)計算法的時候，要盡可能追求簡潔優(yōu)美的數(shù)學(xué)模型，從簡單粗暴做起，逐步完善完美。正如牛頓爵士所言「真理在形式上總是簡單的，而不是復(fù)雜含混的」。

最后，文法分析方法是十分容易想到的，十分自然的處理方法，然而這種「自然」也使人誤入歧途。這提醒我們，不可固執(zhí)，不可迷信經(jīng)驗。

• 自然語言處理的數(shù)學(xué)原理（二）

本文轉(zhuǎn)載自：https://liam0205.me/2015/07/25/mathematics-theory-of-natural-language-processing-1/