在给大家引入概念之前，我想先举一个我工作中经常遇到的例子。我几乎每天都需要输入同一个英文单词，但是我的TT练得不好，经常输错，常把它打成：unoin。请大家帮我纠正一下，我到底想输入的是神马单词呢？
知道我工作背景的同学可能一下子就说出答案了，但我希望你们暂时抛开我的工作背景来分析。你首先可能会想到，你应该想打union吧？因为键盘上o和i相邻，比较容易打反。有的人开始说我扯淡了，说这样的猜想不科学，虽然o和i相邻，但毕竟相同位置上有两个字母出错了，而unoil（除油）跟unoin只相差一个字母，所以unoil错误地打成unoin可能性高一点。貌似双方都很有道理，争持不下。这时，第三个声音出来了：你们只考虑单词输错成另外一个单词的可能性，就不考虑一下单词本身出现的可能性了吗？对哦，假如我刚才没有用括号注释，大家知道unoil是“除油”的意思吗？而union表示联盟，则是大部分人都应该知道的（在我读书的年代，union是个小学初中词汇，现在应该推到更前了）。所以，一个我都不认识的单词，我会想到去输入它，还输错了？!这概率得有多低啊！
上面的这个例子，活生生地为我们展现了贝叶斯推断（Bayesian inference）的一个过程。假如P(c)表示正确拼写的单词c出现的概率，P(w)表示输入一个错误单词w的概率。那么实际上我们求的就是P(c|w)的最大值，在观察到输入一个错误单词w的条件下，最有可能是想输入c的概率P(c|w)是多少。利用贝叶斯定理，我们得到：
P(c|w) = P(c) * P(w|c) / P(w)
对于任意错误的单词w，我们可以认为它们出现的概率是一样的，从而我们在上式把它忽略，写成：
P(c|w) ∝ P(c) * P(w|c)
∝这个符号是“正比于”的意思。P(c)上面说了，是一个正常单词c在文章中出现的概率。它的概率由语言环境决定，所以我们给它一个名称：“语言模型”。P(w|c)表示用户想输入c却错误地打成w的概率，这里我们称之为“误差模型”。一个猜测P(c|w)的好坏，就取决于这个猜测（我们猜它“背后隐藏”的单词是c，也就是P(c)）本身的先验概率（Prior probability），和这个猜测生成我们的观察数据（错误的单词w）的可能性（Likelihood，这里也就是想输入c却打成w的似然概率P(w|c)）的乘积。我们想要获得最大可能性的猜想（Pmax(c|w)），实际上就是要让P(c)和P(w|c)的乘积最大。
这就解释了我们一开始的例子，为什么我们光有似然概率，还不能做出推断，还必须考察单词本身在语言模型中出现的概率。因为光靠似然概率可能不靠谱（有的时候，我们对先验概率一无所知，或者先验概率本身分布均匀，那也只能靠似然概率做预测），观测数据总是有噪声的。例如我打字的时候有个美女走过，我为了看她，就打错了。这种噪声你怎么预测？怎么拟合？而加上先验概率这个因素则不同了，它是大量统计数据的结果，而且先于我们当前观察的数据，能够平滑处理随机噪声，让我们的结果更加健壮。
贝叶斯定理与我们的生活息息相关。想想“那些年，我们一起调戏的siri”，不就是服务器根据接收到的语音信号，来推测用户想表达的意思吗？想想垃圾邮件识别大概是怎么做的（Paul Graham在他的书《黑客与画家》中，通篇大谈技术哲学，但却花了整整一章谈如何用贝叶斯方法过滤垃圾邮件，非常有趣）？想想google suggest是怎么给你提示的？再想想一开始我的那个例子，你把它写成程序，不就是搜索引擎（或者输入法之类）里的拼写纠错吗？
扯了这么久，有人怒了，说好的中文分词呢？别急，高潮总是在后半部分的。
既然如此，又来举例子。对于这样一个句子：“上网站联盟加入我们”，我们怎么分词比较好？如果从左到右，用贪婪算法（也就是最长匹配机械分词，通过“查字典”的方法来实现，我去年大概差不多这个时候也曾经写过，据说目前精灵用的就是这个算法），那么“上网”首先会被分词出来。然后对于“站联盟”，程序不知怎么处理了，最理想的情况下只能将“站”和“联盟”分词出来，然后是“加入”、“我们”。那么整个句子分词后变成“上网|站|联盟|加入|我们”，这显然不是我们要的结果。
如果我们用贝叶斯方法呢，结果会是怎样？我们令X为句子：“上网站联盟加入我们”，S为一种分词方案（如“上网|站|联盟|加入|我们”，或者“上|网站|联盟|加入|我们”，等等），我们需要找到一个S，使得P(S|X)最大。利用贝叶斯公式，得到：
P(S|X) = P(S) * P(X|S) / P(X)
这里，我们再次省略分母，因为对于任意S，X的概率P(X)都是一样的，所以有：
P(S|X) ∝ P(S) * P(X|S)
再进一步，由于不管我们怎么分词，得到这个句子X的概率总是为1（我们只要把每种分词的分隔符取走，就精确还原出同一个句子X了）。所以上式进一步简化：
P(S|X) ∝ P(S)
也就是我们的分词优劣取决于我们的语言模型了，利用联合概率（Joint probability）公式展开P(S)，得到：
P(S) = P(W1, W2, W3, ... , Wn)
= P(W1) * P(W2|W1) * P(W3|W2,W1) * ... * P(Wn|Wn-1, ... , W1)
W1，W2，... ，Wn是一组特定的词串，也就是我们一种分词方案。这里我们发现，公式的最后一项，Wn这个单词竟然依赖于它的前n-1个单词。所谓的数据稀疏问题（也就是高维诅咒）在这个时候突如其来，感觉hold不住了。因为无论多大的语料库（corpus），都无法统计出一个n阶的P(Wn|Wn-1, ... , W1)出来的。庆幸的是，计算机科学家们发现，我们不需要统计n阶，我们假设单词只依赖于它前k个词，也能获得很理想的实践效果。k一般不超过3，如果完全去掉依赖，只计算每个单词的独立概率，那就是一元模型（unigram）；如果只依赖前一个单词，就是2元模型（2-gram），同理有3-gram 、 4-gram 等。
在这个强大假设的前提下，我们可以简化上面的式子。特别地，我们取k=1，也就是2-gram（亦即马尔可夫假设），得到一条马尔可夫链：
P(S) = P(W1) * P(W2|W1) * P(W3|W2) * ... * P(Wn|Wn-1)
有了这样一个强大的数学工具，再来解决刚才的分词例子就水到渠成了。假定我们现在拥有大量的机读文本，包含大量常见单词对在文章中的出现次数。我们先分析“上网”-“站”，“上网”后面跟个“站”是什么意思呢？上网“站”什么？“站撸”吗？这不是坑爹呢？！根本就没有这样的单词对出现过！概率直接为0了（当然，实际编程中我们为了处理字典里没有的词，不会直接设为0，而是设置为一个足够小的值，这也是统计语言模型中非常重要的平滑问题）。同理，对于“站”-“联盟”也是一样，出现的次数也为0。我们换一种切分：“上|网站|联盟”。“上”-“网站”这个词组经常出现，能在统计文本中找到它的概率，而“网站”-“联盟”这个就更不用说了。贝叶斯方法使得我们后面这一更符合人的直觉的分词方案得以胜出。
直观例子说完，讲讲更具体的操作。接下来，我们要做的就是枚举句子的各种切分，求出它们在2-gram模型下概率最大的切分，那就是我们最好的分词方案。然而，对于一个长度为n的句子（也就是有n个字），尝试不同切分的时间复杂度是O(2^n)（因为n个字之间有n-1个空隙，每个空隙都可以选择分隔或者不分隔），一个32字的句子我要进行20亿次的计算，复杂度太高了，一般机器很难在理想的时间内跑出来。
我们对这个分词过程进行仔细观察，一个词串S的概率P(S)，等于它分出来的第一个词first的概率P(first)，乘以剩下的词串remain的概率P(remain)：
P(S) = P(first) * P(remain)
这个性质对于求解它的子问题，remain的切分也同样适用，也就是满足可递归性。进一步观察，我们发现：
P(S)max = P(first) * P(remain)max
也就是说，整个问题的最优解由子问题的最优解构成。这两个线索透露出一个重要信息：我们的分词算法可以用动态规划（Dynamic programming）来建模。
具体做法，我们利用一个表，记录递归过程中求解过的子问题的最优答案，在下次遇到的时候直接返回，避免重复求解。例如我们在求解子问题“网站联盟加入我们”时，已经得到它的最优解是“网站|联盟|加入|我们”。那么当我们求解“上网站联盟加入我们”时，就发现，假如我们尝试做第一下切分，得到“上”、“网站联盟加入我们”这两块，我们只需要求P(“上”)。而Pmax(“网站联盟加入我们”)我们已经求解过了，直接返回，和P(“上”)相乘，得到其中一个候选结果（candidate）。在这一个递归层面（Hierachy），继续枚举，求出概率最大的分词方案（optimal candidate），又记录在表里，返回上一层，如此迭代。特别地，我们设定最长的单词不会超过L（这里，我令L=10），那么函数递归的效率为O(nL)，加上每一次调用递归函数时，我们需要进行O(L)次的切分枚举，所以整个算法的复杂度为O(nL^2)。
可以看到，通过这样一种空间换时间的策略，我们一下子把问题的复杂度从指数级别（2的n阶）降低到多项式级别（n的一次方程，由于L^2可能比n还大，所以也可以近似地看成是O(n^2)的复杂度），这是我们设计算法惯用的手段。实际上，这也是维特比算法（Viterbi algorithm）的实现，上面提到的记录子问题最优解的表，叫做维特比表（Viterbi table）。由于递归程序受到栈大小的限制，所以这种top-down的遍历会有“爆栈”的危险，你可能会更偏向于用bottom-up的方式构建拓扑排序（Topological order）。不过没关系，只是实现起来稍微麻烦一点，这也留给喜欢思考的大家去想了。
不过统计语言模型的麻烦之处，在于它需要不断更新词汇统计结果，不然它就变成死水，永远不认识新的单词了。这也很合理，正如人一段时间不学习，他也会跟社会脱节，跟别人产生代沟。十年前我不可能知道“坑爹”、“我擦”、“神马”会是一个词，而现在我自己每天都在说。机器学习虽然不像人一样，能够深入事物的底层去观察一些更本质的联系（至少目前是这样），它只能在一个浅层（shallow）的表面进行一些统计，来获取、推理一些信息。但它跟人一样，必须不断更新它的“知识”，来解决不断变化的问题。至于如何让机器能在更高抽象层面（例如“意识”、“意图”）工作，则是人工智能需要解决的问题了。
分词就分完了，那到底我要用它来干嘛呢？不卖关子了，其实是我要用来做智能广告。顾名思义，智能广告就是不需要用户选择广告，我们自动为他选择。如果没有程序的帮忙，我们可能想到的办法，就是人工上他的网站看下，从他的页面内容判断这是一个什么站点，受众是些什么人，最适合放什么样的广告。有了程序，我们可以利用爬虫（crawler），抓取页面信息，进行匹配，然后给他推送最合适的广告。分词的过程，实际上是帮助机器理解站点的一个过程。有了一个对页面文本的分词结果，我们就可以通过某种手段对匹配过程进行量化处理，计算一个归一化的数值。这到底是怎么计算的？暂时先不说，我们留到下一篇文章再进行分享。