如题，L-抗坏血酸镇。配色是H-α线的颜色——这个宇宙可见光波段最亮的颜色。




一楼说点废话。
本帖的意思一是科普计算机自然语言处理，二是隐晦地吐槽吐槽锑度读贴，读的太差劲，我已经开始在怀疑度娘的工程师理论水平问题了。副标题是组织材料用的。还有：
千万不要把本帖的算法真拿去编程！
千万不要把本帖的算法真拿去编程！！
千万不要把本帖的算法真拿去编程！！！
重要的事情说三遍！
本帖的算法仅供理论探讨，实际编程是需要大量数据的，真想做个好的把本帖的那些数学工具的能力全部发挥出来你需要几百台服务器的数据再加上几百台服务器进行分布式计算！出了事别怪我！我先去弹一曲图样图森破去[光速逃]


在贴完之前，禁止插楼。


以上。最后，向那些前辈们致敬！@江藤纪之介护贴。
本文参考文献主要是吴军老师的《数学之美》。在此特别感谢并强烈卖安利。

二楼供插楼、

1.人和电脑的通信问题
在计算机科学中自然语言处理是相当重要的一环，这个问题可以视作人与计算机进行通信。各位想想，计算机只能处理0与1，顶多做个布尔代数就不错了【在计算机中，加减乘除乘方开方等都被转化为布尔代数，这个问题暂时不细讲】，然而自然语言即使拼音文字也有十几个到三十几个字母，汉字等就更多了，光GB2312标准里的最常用字就有六千多个，Unicode里收了八万多个汉字【其实上应该叫中日韩越统一表意文字，里面汉字占绝大部分】，计算机如何处理这些符号？这些符号对于电脑就是天书！所以我们先进入我们今天要讲的第一个问题——人和电脑的通信问题，后面的问题都可以归到它的框架下。

首先我们得回到百万年前的旧石器时代甚至更早，那是语言产生的时刻。语言的目的就是为了在人和人之间传播信息。举个例子：
两个原始人张三和李四在树林里狩猎，张三看见某棵树的后边有一只老虎。为了提醒同伴注意，张三发出一串奇怪的叫声，表示“那边那棵树后面有只老虎”。李四听到后可能咿咿呀呀地回复两声，表示“我知道了”，或者再用另一串奇怪的叫声回复，表示“我们用石头打它”。
这个例子虽然很简单，但是却包括了现在通信的所有要素——这个是雅各布森提出来的——发送者，信道，接受者，信息，上下文和编码。这个例子中【先以张三作分析】，张三是发送者，空气的震动造成的声音是信道，接受者是李四，信息是“那边那棵树后面有只老虎”，上下文是他们在的狩猎环境，编码是他们的那一串奇怪的叫声。

在旧石器时代，人类了解和需要传播的信息是很少的，几声怪叫基本上就能描述日常的一切，但是随着文明的发展，需要表达的东西越来越多，不是几声怪叫就能解决一切问题的，语言——有其符号与处理规则的用于沟通的一套方式——就产生了。这其中就蕴含了编码的思想，对周围的事物试图用同一套系统进行描述，随着社会生产力的发展，我们的祖先需要处理大量新鲜事物，语言也越来越丰富，抽象概念也进入其中，祖先开始对周围的事物等进行第一次编码——物体、数量、动作开始抽象出来，慢慢演化为词汇。

当语言和词汇发展到一定地步外加社会生产力发展到一定地步的时候，人类仅靠大脑已经记不住所有的词汇了，这就如同今天没有是通才一样。高效记录信息的要求由此产生了，这就是文字的起源。有了语言和文字，人和人之间的通信更方便了，人类的知识积累量开始爆炸性地加快，一直到现在。

现在回到我们开头讲的问题，人和计算机之间如何通信？答案就在上面的故事里——以计算机能够接受的形式对语言进行编码！文字天生适合这一套，于是是文字被编码进入计算机而不是声音信号【当然到最后我们还要回到这个问题上，先等一会】。其实自然语言的发展在冥冥之中都受着数学规律特别是信息学规律的指导，只不过我们的祖先是朴素感性地进行处理，我们现代科学是定量精确地加以处理而已。于是为了解决人与计算机通信的基本问题之一，人们开始了对文字的编码，Unicode和ASCII都是这个伟大努力的尝试。至于这两个东西本身，网络上的资料非常多，就不在这里细讲了。

2.计算机收到文字信号后的处理
光有1中的编码步骤还是不行的，输入计算机之后要进行处理。
我们每次说话或者写作，就是把头脑中想要表达的信息通过语言的语法作为编码规则进行编码然后以声音或者文字进行输出，接受者在脑中也使用语言语法作为解码规则得到信息，这就是语言的数学本质。问题来了，计算机处理自然语言的方法是不是跟人类一样呢？答案是——错！

在20世纪50年代到70年代时，绝大多数专家在自然语言处理方面走了弯路，认为计算机要处理自然语言方法一定跟人类差不多，使用语法规则什么的，分析语句获取语义，但是事实是无情的，这种方法非常麻烦，举个例子：
张三打李四。
这个句子的主语是【张三】，谓语是【打李四】这个短语，可以再细分为动词【打】和名词【李四】，（不同的人对句法分析结果经常不一致我的仅为举例说明问题），最后还有个句号，然而问题来了，一个五个字的句子对他的分析结果却有这么长，那么下面这个句子呢：
哥伦比亚总统胡安·曼努埃尔·桑托斯和哥伦比亚革命武装力量－人民军在古巴哈瓦那共同签署停火协议。
虽然这个句子仍然符合“句子→主语谓语句号”这条规则：
主语【哥伦比亚总统胡安·曼努埃尔·桑托斯和哥伦比亚革命武装力量－人民军】动词短语【在古巴哈瓦那共同签署停火协议】。
然后主语又可以分成两个名词短语【哥伦比亚总统胡安·曼努埃尔·桑托斯】和【哥伦比亚革命武装力量－人民军】，如此等等，这样，一个句子可以如此分析，甚至根据从粗到细构成一个树——句法分析树，这个树非常庞大以至于都无法画在一张纸上，所以，基于规则的语法分析器会在遇到这种句子时死机。这还是一句非常简单非常普通的句子！自然语言是上下文有关的，上下文有关文法一直是计算量让人想吐（O(n^6)）！

在20世纪70年代时，上面讲的方法走到了尽头。对于语义的处理甚至更麻烦，首先严重依赖上下文，其次还需要常识，比如，The one有时候指【特定的那一个】，但是，经常这个短语的意思是【救世主】，这个时候就需要结合上下文和常识来进行判断，这样绝对会把机器逼疯！

Frederick Jelinek在20世纪70年代时领导IBM的华生实验室，他们当时要解决自然语言处理的一个方面——语音识别问题，他们想到了一个绝妙的至今都在用的手段——统计，采用基于统计的方法，IBM将语音识别率从70%提升到了90%，并且将语音识别的规模从几百单词上升到几万单词，这是一个历史性的成就！
现在，我们来介绍统计方法，比如计算机要输出这个句子：
热带风暴艾米莉是2011年8月一场强度虽弱，但却在加勒比地区北部大部分地区降下瓢泼大雨的北大西洋热带气旋，也是同年大西洋飓风季第五场获得命名的风暴。
这句话非常通顺，意思也很明白。
如果这句话变成了这样：
艾米莉热带风暴是8月2011年一场强度虽弱，但却在加勒比地区北部大部分地区降下大雨瓢泼的北大西洋热带气旋，也是大西洋飓风季命名获得的风暴同年第五场。
就很不通顺疑似含混了，虽然大概还能知道这句话要说什么。
如果成了这样：
艾热带风暴米莉是8月2011年场一虽弱强度，但却在北部加勒比大部分地区地区大雨瓢泼降下的大北西洋气热带旋，也是飓风大西洋季命名获得的风暴同年第五场。
基本就不知所云了。

问题来了这三个句子为什么有这么大差距呢？
20世纪70年代以前的科学家是这么想的：
第一个句子合乎语法语义清晰，第二个句子语义清晰但不合乎语法，第三个句子连语义都不清晰了。
如上部分所示，这样计算机根本无法操作。

然而Frederick Jelinek换了一个角度想：一个句子合不合理通不通顺，就看看它出现的可能性大小如何。上面第一个句子出现的概率是10^-21，第二个句子出现的概率数量级是10^-25，第三个句子是10^-60到10^-70，怎么样，句子通不通顺一目了然吧？现在来做具体分析：

假定A是一个句子，由一连串顺序排列的词w1，w2……wn组成，这里n为这个句子里的词数，现在，我们想知道给出一段语料A在其中出现的可能性P(A)。
Plan A：
把人类从发明语言以来说过的所有话写过的所有书统计一下，然后用简单的除法就知道P(A)了，当然只要不是智障就能看出来这方案行不通。
Plan B：
既然A是由w1，w2……wn拼出来的，那么不妨把P(A)展开
P(A)=P(w1，w2……wn在一句中有序同现)【下文中我们记为P(w1，w2……wn)】

用条件概率【条件概率：P(A|B)在B条件下A的概率】，A=w1，w2……wn这个序列出现的概率是
P(A)=P(w1)×P(w2|w1) ×P[w3|(w1,w2)]……×P[wn|(w1,w2,……,wn-1)]

P(w1)就是第一个词w1的概率，P(w2|w1)是已知句子开头是w1的情况下，w2出现的概率，如此等等。
但是……问题来了，第一项很好算，第二项也还行，第三项就让人头大了,算到最后就无法想象了，尼玛涉及如此多的变量基本每个变量都要查一遍字典……尼玛这玩我哪？！
这个时候，一个伟大的俄国数学家Andrey Markov于1906年站出来解决了这个问题，他的思路是这样的：
“打得过就打，打不过就跑”，这是一种非常有效的策略，既然我们打不过那么大的计算量，那么我们就跑！管不了那么多了，那么一长串全部砍掉，变成这样：
P(A)=P(w1)×P(w2|w1) ×P(w3|w2)……×P(wn|wn-1)
即：第x个词wx出现的概率只和它前面一个词有关！这叫做马尔可夫假设，应用马尔可夫假设之后，计算量大大减低，这个式子可以投入使用了！【这叫做二元语言模型，即条件概率考虑两项，以此类推还有更高阶的语言模型】
现在问题是如何估计这里面的各项概率。
根据它的定义：
P(wx|wx-1)=P(wx-1,wx)/P(wx-1)
而估计后面两项的概率就非常简单了，去互联网上用爬虫扒个几十TB的网页回来，然后数一数wx-1，wx这对词出现了几次，以及wx本身出现了多少词，再除以这些网页的总次数N就可以了，再加上大数定理，问题就解决了！这么困难的问题被简化的如此简单！这真是极好的！

当然你肯定不信这么简单的东西能解决什么问题，但是自然语言处理的一些经典问题——分词、 语音识别、机器翻译等等，都是用这个模型解决的！效果比基于规则的手段高到不知道哪里去了！

——————回归主线，论计算机如何把人话念得像人话———————
假设输入了一大串文本，我们记为T。现在我们的任务是让计算机把T念得像人话。
作战是有方案的，解决问题也要有方案。
可能你想到的最简单的方案是照着字典或者汉语拼音标准念，确实这也是一种解决办法，但问题是你先得解决怎么注音，别忘了，汉语里面重音字非常多，多音字也非常多，这些问题都是依赖上下文的，上下文有关的计算机从来就没有处理好过。还有，别光觉得照着汉语拼音标准念就行了，还有断句，语气等等问题，这些问题不解决好一听就知道肯定是程序念的，那就是任务失败了。通常的方法在这方面效果都不是很好，O(n^6)的计算复杂度摆在这呢。不过按照分治算法的精神，我们先来解决主要矛盾，再来解决其他问题，把大矛盾分成若干个较方便解决的小矛盾，然后再来分别解决这些小矛盾，这是我们的战略思想。
先来解决第一个矛盾：给文本T注音。
其实，我们可以把给文本T注音的问题看成通信问题，计算机和人通信，而我们的算法是一个将文本T转换为注音方案Y的转换器，T里的每一个字可以对应着多个拼音，把一个汉字串从左到右连起来，就是一张有向图，它被成为网格图或者篱笆图，是长这个样子的：【把T里的每一个字记为L1，L2，L3……Ln，对应的拼音记为Y1，Y2，……Yn】




【Y1a是L1的第一个候选注音，Y2b是L2的第二个候选注音，如此等等】
从第一个字到最后一个字可以组成很多很多念法，每一个念法和图里的一条路径一一对应，我们的算法的任务就是在里面找到一个最优的念法，即对于文本T找到一个最对的拼音，即对于文本T每个字的拼音Y1，Y2……Yn出现概率最大，这个方案Y记作Y=ARG_MAX[P(Y1,Y2,……Yn|T)]或者Y= ARG_MAX[P(Y1,Y2,……Yn|L1,L2……Ln)]【ARG的意思是参数，Argument，在这里意为取能获得最大值的那个方案】，对应到上图里，我们可以说找一条最短路径，然后我们把转换拼音的问题变成了寻找最短路径的问题，当然我们先得定义距离函数d，这个时候我们就要回来讲马尔可夫模型和大名鼎鼎的动态规划算法了【这里是维特比算法】。

在讲马尔可夫模型之前，我们还要回到通信问题上。
设我们观测到了一串信号M，由信号S1，S2，……，Sn构成，我们的任务是根据这串信号推测出最可能产生这串信号的信息串I =I1，I2……，In？很简单，根据上面讲的你自己都能推测出来了，I=ARG_MAX[P(I|M)]！于是问题就变成了求P(I|M)。
还是展开【用到了贝叶斯公式，不细讲】，于是公式就变成了：
P(I|M)=P(S1，S2，……，Sn|I1，I2……，In)*P(I1，I2……，In)/P(S1，S2，……，Sn)
第一项P(S1，S2，……，Sn|I1，I2……，In)表示信息I1，I2……，In在通信后变成S1，S2，……，Sn的可能性，P(I1，I2……，In)表示I1，I2……，In本身比较合理的可能性，最后，P(S1，S2，……，Sn)表示S1，S2，……，Sn比较合理的可能性。
这里面可以简化的部分非常多，一旦信号产生了，S1，S2，……，Sn就不变了，P(S1，S2，……，Sn)就可以忽略了，所以现在问题变成
P(I|M)=P(S1，S2，……，Sn|I1，I2……，In)*P(I1，I2……，In)←它很重要，我们标记一下
现在这个问题就可以用大名鼎鼎的马尔可夫模型解决了。

首先我们来解决这个问题：
一个句子K，由词w1，w2……wn构成，问题来了，给出w1，w2,……wm（m<n），再随机给一个词w，问题来了，w是wm+1的概率是多少？
用条件概率的知识，我们要求的就是P(w|w1，w2,……wm)，我们上面讲过了这个非常难算，这个时候我们的马尔可夫同志偷了个懒，硬性假定随机过程问题中各个状态【对我们来说是词wm】的概率分布只和它的前一个状态wm-1有关，即P(w|w1，w2,……wm)=P(w|wm-1)。当然这个假设未必每次都管用，但好歹给不少情况给出了能用的近似解，这个假设被命名为马尔可夫假设，符合这个假设的随机过程被称作马尔可夫过程，下面给出一个典型的马尔可夫过程的图：

这段里不知道有什么敏感，就只能转换成图发

首先只要对于合理数据就总会有一套模型M0最可能产生它，那么我们这么想：
首先随意找一组参数能够产生F1，F2……Ft，（这一定有，使用概率均匀分布就可以了，均匀分布的时候能产生任何输出），现在有这么一个模型Ma，我们需要找到一个更好的模型，我们先假定解决了P(Ft|ηt)和P(ηt|ηt-1)的计算问题，那么我们使用这些数据就可以算出P(M0产生F1，F2……Ft)而且能够找到所有可能的路径和对应概率，这些可能路径其实跟往前数第二张图一样，因此可以看做“已经标注的数据”，并且拿它直接计算，算个几十次，到质量没有明显提高就可以了，这就是算法原理【期望最大化——EM大法好！虽然对于非凸函数不太有用容易掉进局部最优解】。

模型制作好了，那么如何确定概率最大值呢？这就需要维特比算法了。
维特比算法是以著名科学家和企业家Andrew Viterbi名字命名的，毫不夸张的讲，他的贡献改变了世界，今天基于CDMA的3G通信标准就是他和另外一位朋友创立的高通公司制定的。首先把上面的一个图再贴一遍：


我们需要在里面找一个最可能的路径，首先我们可以枚举，但是显然很麻烦，计算数量级对于一个合理的句子在10^16左右，正常计算机差不多要算一天……Viterbi在1967年首次提出了这样一个算法：
1. 如果概率最大的路径【或者是最短路径，对数把连乘变为加法，取负数问题解决】过某个状态，那么从起点到这个状态的子路径一定也是最短路径，否则就能找到一条更短路径，构成矛盾
2. 从起点到终点路径必定经过中间的某个状态，假定第x个地方有y个状态，如果记录了从S到第x时刻的所有y个状态的最短路径，那么最终的最短路径肯定在里面。

3. 由上两点，我们从状态Lp进入状态Lp+1时，从起点到Lp的各个节点Yp的最短路径都已找到并且已经记录，那么在计算从起点到Lp+1的下面的某个状态最短路径时，只要考虑从起点到Lp的所有节点Yp的最短路径以及从这些Yp到我们要找的节点的最短路径即可。
具体操作：
Step1.从起点出发，对于第一个状态L1的各个节点Y1xx，不妨假定有k1个，计算出从起点到他们的距离d(起点,Y1xx)，因为只有一步，所以这些距离都是最短的
Step2.【重点来了！】对于第二个状态的L2的各个节点Y2xx，要计算出从起点到它们的最短距离。我们知道，对于特定的节点Y2i，从起点到它的路径可以经过状态L1中的任意一个节点Y1j，当然对应的路径长d(起点，Y2i)=d(起点,Y1j)+d(Y1j,Y2i)，由于有许多可能性，这些路径我们都要一一计算，然后找到最小值，我们记为d_min(起点，Y2i)。
然后对于L3等，如此重复操作，一格一格的计算就可以了，最后走到终点就得到最短路径了。如果假定这个图节点最多的状态有R个节点，这个网格有D个状态，那么很容易就能得出这个算法的复杂度为O(R^2·D)，把常见句子的参数带入就会发现它的计算量只有10^3-10^4左右，和上面的10^16有天壤之别！！！！！！

好了，现在注音问题已经解决了，我们成功把文本T转换为了一个最优的拼音方案P，但是，读文本光念准句子是不行的，还有各种因素，比如断句等，这种就必须依赖上下文和主题信息等，有两个办法解决这个问题：
Plan A：
回到隐含马尔可夫模型那个地方，直接用Baum-Welch算法和大量数据训练模型，然后直接跳到下面的输出步骤去，这个方法简单粗暴，效果也还说得过去，但是需要的数据量过大，大约几百万到几千万词的语料可以训练一个有用的三元模型【二元模型可以少一到两个数量级，不过效果不咋地】，一个专业播音员或者歌手一辈子都不会念这么多词的语料，所以这个办法也基本行不通。
Plan B：
将上面的注音数据在里面进行断句等信息的标记，然后交付前段合成引擎，这样的需要的数据量只需要找个人把汉语拼音标准念念好就行了，但是仍然需要大量人读语料进行断句等的收集，不过这回不限于特定人了甚至不需要语音数据【Plan A需要限于特定人的语音数据，要不然一堆人的平均在一起听起来会非常奇怪】，于是问题就变成了，在给出上下文、标点和主题等信息的情况下，对注音数据进行断句等的处理。为方便讨论，我们只考虑上下文、标点和主题这三个信息，只对注音数据进行断句和语速以及语调的标记。

简化过的问题看起来还是很麻烦对吧，那我们先考虑这样一个问题：
有一个骰子，看起来很普通很标准，那么，随意抛起来，它一个特定的点数（比如4点）朝上的概率是多少？答案很明显，六分之一，问题来了为什么？理由也很简单，一个正常的骰子随意抛起来每个面朝上是等可能的，既然我们对它什么都不知道，那么我们就只能假设它是等可能的（我们显然不该主观假定它像韦小宝的骰子一样灌了铅）。问题来了，这骰子被我南门二特殊处理过了，已知随意抛起来三点朝上的概率是三分之一，问题来了，随意抛起来之后一点朝上的概率是多少？绝大部分人估计的答案会是十五分之二，理由也跟上面一样，已知条件必须满足，剩下的我们仍然一无所知所以仍然只能等可能处理，事实上这种猜测很准确，因为它服从了一个数学原理——最大熵原理。它指出，需要对一个随机事件的概率分布进行预测时，我们的预测应该满足所有已知条件，而对未知条件不要做任何主观假设，在这时，概率分布最均匀，风险最小，信息熵最大，所以被叫做最大熵原理。【这句话有个通俗版本，鸡蛋别放一个篮子里】。

回到上面的例子，我们已知文本T的大概主题【可以用聚类很容易地找到，聚类的方法可以用EM、矩阵奇异值分解或者余弦定理，在这里不详述】，文本T里也有标点，还有上下文能给与的一些提示，我们需要找到一种模型能够同时满足这些信息，匈牙利著名数学家、香农奖得主I.Csiszar证明，对一组不自相矛盾的信息，这个最大熵模型存在且唯一！而且形式也很简单，指数函数。下面这个模型是根据上下文和主题以及标点预测是否应该在此处停顿的模型【其他特征可以照此办理】：[记在当前文本的第x个词/标点处停顿这个事件为p0，当前句子、前一句、后一句、主题、此处的标点以及语法参考这些条件分别记为p1，p2，p3，p4，p5，p6]
P(p0|p1，p2，p3，p4，p5,p6)=1/Z(p1,p2,p3,p4,p5)*e^[S1(p1,p0)+S2(p2,p0)+S3(p3,p0)+S4(p4,p0)+S5(p5,p0)+S6(p6,p0)]
Z(p1,p2,p3,p4,p5,p6)=Σe^[S1(p1,p0)+S2(p2,p0)+S3(p3,p0)+S4(p4,p0)+S5(p5,p0)+S6(p6,p0)]【起始为p0】，这个东西的左右是为了保证概率加起来为1
这里有很多的模型参数S1(p1,p0)，S2(p2,p0)……S6(p6,p0)需要通过训练来获得。首先这个东西可以使用上面提到的EM过程来训练，但是实际这个方法并不好，计算量实在太大太大了，后来Della Pietra兄弟提出了IIS算法，而吴军老师【他是中国人，还是本文参考文献《数学之美》的作者，极其牛逼】给出了一个对于大部分应用时间复杂度比IIS少一到两个数量级的算法，这才让最大熵模型能用。它实现很复杂，有需要的可以去读他的论文，真的很好。

好了，现在读文本的辅助信息也标记好了，交付前段合成引擎然后输出。

那么具体地怎么合成呢？当然因为篇幅和我的水平等限制，只讲大概算法。我们又要用到一个数学工具了，当然它不是概率方面的了，这个工具是傅里叶级数。
对于某周期为T的不是数学家用来恶搞【意思是连续，无断点】的函数f(t)，都可以写成a0+a1cosωt+b1sinωt+a2cos2ωt+b2sin2ωt+……的形式，ω=2π/T，a和b等皆为常数，这样可以把一个周期函数分解为无数简单的正弦和余弦波的叠加。【给空降本文的大神：实际上它更方便计算机使用的方式是e的虚指数幂，但是这里为了说明问题我还是使用三角函数形式】
稍微有点物理和数学常识的人可以看出来，只要仔细调节这里的a和b系列的常数，那么音色、音调、响度这三个量都可以控制【请回忆高中数学必修4讲三角函数的部分】，可视化的可以查阅维基百科的傅里叶级数条目，具体调节方案已经由上一步给出，只要把上面收集的念标准汉语拼音方案的音源按照注音拼起来并对调节方案给出的要求加以注意就可以了，怎么操作那就是工程问题了，而且也已经比较成熟了。最后的任务就是输出了，这也是工程细节，不细讲，再说了，再往下细讲你们肯定也没耐心看了，这么多数学公式你们到现在肯定想打死我了。


本帖完。谢谢！

技术贴没人

顶

顶

顶

顶

顶

顶

顶

顶