计算语言学的数学基础

《计算语言学的数学基础》由会员分享，可在线阅读，更多相关《计算语言学的数学基础（19页珍藏版）》请在金锄头文库上搜索。

1、计算语言学工作者需要了解的数学知识 常宝宝 北京大学计算语言学研究所，100871 chbb 计算语言学是一门交叉学科，其中不仅涉及到语言学、计算机科学，还大量应用到 数学知识。尤其是近年来，随着语料库语言学的兴起，统计等数学方法和技术在计算语 言学中更是得到了越来越广泛的应用。 第一节 概率统计基础 一 事件和概率 定义定义 1. 随机事件随机事件: 在一定条件下,可能发生也可能不发生的试验结果称为随机事件，简 称事件事件，一般用大写拉丁字母 A,B,C,表示。 随机事件有两个特殊情况，即必然事件必然事件(在一定条件下，每次试验都必定发生的事 件)和不可能事件不可能事件(在一定条件下，每次试

2、验都一定不发生的事件)，分别记为和。 随机事件在一次试验中是否发生，固然是无法肯定的偶然现象，但当进行多次重复 试验，就可以发现其发生的可能性大小的统计规律性。具体说，如果在相同条件下进行 了 n 次重复试验，事件 A 出现了 v 次，那么事件 A 在 n 次实验中出现的频率频率为是 n v 。当 n 无限增大时呈现稳定性。这一统计规律性表明事件发生的可能性大小是事件本身所固 有的、不以人们主观意志而改变的一种客观属性。 事件之间的关系和运算事件之间的关系和运算 (1) 包含包含 当事件 B 发生时，如果事件 A 也一定发生，则称 A 包含 B 或 A 包含于 B 中， 记作 AB 或 BA。

3、 (2) 等价等价 如果 AB 且 BA，即事件 A 和 B 同时发生或不发生，则称 A 和 B 等价，记作 A=B。 (3) 积积 表示事件 A 和 B 同时发生的事件，称为 A 与 B 的积，记作 AB 或 AB。 (4) 和和 表示事件 A 或事件 B 发生的事件，称为 A 与 B 的和，记作 AB 或 A+B。 (5) 差差 表示事件 A 发生而事件 B 不发生的事件，称为 A 与 B 的差，记作 A-B。 (6) 互斥互斥 如果事件 A 与 B 不可能同时发生，即 AB=，则称 A 与 B 是互斥的。 (7) 对立对立 如果事件 A 与 B 互斥，又在每次试验中不是出现 A 就是出现

4、 B，即 AB=且 A+B=，则称 B 为 A 的对立事件，记作 B=A。 定义定义 2. 概率概率:事件 A 发生的可能性大小称为事件的概率，记作 P(A)。 若读者对概率统计方面的基本概念已经熟知，可以越过本节直接阅读下一节 当试验的次数 n 足够大，可以用事件的频率近似地表示该事件的概率，即 n v AP)( 概率的基本性质概率的基本性质： (1) 0 P(A)1。 (2) P()=P(必然事件)=1。 (3) P()=P(不可能事件)=0。 (4) P(A+B)=P(A)+P(B)-P(AB)。若 A,B 互斥，则 P(A+B)=P(A)+P(B)，若 A1,A2,An两两 互斥，则

5、P(A1+A2+An)=P(A1)+P(A2)+P(An)。 (5) 若 AB，则 P(A)P(B)。 (6) 若 A1,A2,An两两互斥，且 A1+A2+An=，则 P(A1+A2+An)=P(A1)+P(A2)+P(An)= = n i iAP 1 )(=1。 (7) 对任意事件 A，)(1)(APAP=。 定义定义 3 条件概率条件概率 在事件 B 发生的条件下， 事件 A 发生的概率称为事件 A 在事件 B 已发 生的条件下的条件概率，记作 P(A|B)。当 P(B)0 时，规定 )( )( )|( BP ABP BAP= 当 P(B)=0 时，规定 P(A|B)=0。 由条件概率的

6、定义，可得到乘法公式乘法公式 ： P(AB)=P(A)P(B|A) P(A1A2An)=P(A1)P(A2| A1)P(A3 |A2A1)P(An | An-1An-2A1) = = n i iiiAAAAP 1 121).|( 一般而言， 条件概率 P(A|B)与概率 P(A)是不等的。 但在某些情况下， 它们是相等的。 根据条件概率的定义和乘法公式有 P(AB)=P(A)P(B) 这时，称事件 A 与 B 相互独立相互独立的。 贝叶斯贝叶斯(Bayes)公式公式:根据乘法公式，可以得到下面的重要公式，该公式称为贝叶斯公式 )( )()|( )|( BP APABP BAP= 乘法公式在统计

7、自然语言处理中会多次使用到。 一般地，诸事件 A 1,A2,An两两互斥，事件 B 满足 BA1+A2+An，且 P(Ai)0(i=1,2,n)，P(B)0，贝叶斯公式可以推广为 = = + = n i ii jj nn jj j ABPAP ABPAP ABPAPABAP ABPAP BAP 1 11 )|()( )|()( )|()(.)|)( )|()( )|( 实用上称，P(A1)，P(A2)，P(An)的值为验前概率，称 P(A1|B)，P(A2|B)，P(An|B)的值为验后概率，贝叶斯公式便是从验 前概率推算验后概率的公式。 二 随机变量与分布函数 定义定义 4 随机变量随机变量

8、 每次试验的结果可以用一个变量 X 的数值来表示，这个变量称为随机 变量。 随机变量的取值随试验的结果变化，但又遵从一定的概率分布规律。它是随机现象 的数量化。 定义定义 5 分布函数分布函数 给定随机变量 X，它的取值不超过实数 x 的事件的概率 P Xx是 x 的函数，称为 X 的概率分布函数，简称为分布函数，记作 F(x)，即 F(x)=P Xx (-yxI时，x 和 y 高度相关。 当0 ),(=yxI时，x 和 y 高度相互独立。 当0 ),(yxI时，x 和 y 呈互补分布。 定义定义 7: 相对熵相对熵(relative entropy)，设 p(x)、q(x)是随机变量 X 的

9、两个不同的分布密度， 则它们的相对熵定义为： = Xx xq xp xpqpD )( )( log)()( (2.8) 规定0 0 log0= q ，= 0 log p p。 相对熵一般也称谓 Kullback-Leibler 发散度或 Kullback-Leibler 距离。它提供了一 种度量同一个随机变量的不同分布的差异的方法。 从信息论的角度看， 如果一个随机变 量 X 的分布密度是 p(x)，而人们却错误的使用了分布密度 q(x)，相对熵描述了因为错用 分布密度而增加的信息量。 定义定义 8: 交叉熵交叉熵(cross entropy)，设随机变量 X 的分布密度为 p(x)，在很多情

10、况下 p(x)是 未知的，人们通常使用通过统计手段得到的 X 的近似分布 q(x)，则随机变量 X 的交叉 熵定义为： = Xx xqxpqXH)(log)(),( (2.9) 三 噪音信道模型 利用信息论的基本概念， 香农曾经给出了一个通信系统的抽象模型， 该模型可以用 图 2.2 来表示： 编码器 噪声信道 P( y| x) 解码器 WXYW 图 2.2 噪声信道模型 W 是欲经信道传输的消息，在传输之前，首先进行编码使其适于信道传输，编码 后的消息为 X，由于信道噪声的存在，在信道末端，人们并不能精确接收到 X，而是接 收到有噪声在内的编码 Y，信道概率 p( y|x)描述了编码 x 因

11、噪声而变成 y 的概率，当接 收方接到含有噪声的编码后，其任务就变为将 Y 解码，得到最为可能的消息W ) 。作为 通信系统而言，人们最为关心的是，如何将消息编码，以便消息在有噪声存在的情况下 有效可靠地发送到接收方。噪音信道模型在通信以及编码领域得到了广泛的应用。 从 50 年代起，就有人试图利用这一模型解决语言问题，试图用一种量化的手段的 对待语言。由于种种原因，最初的努力并未获得成功。70 年代，人们又一次将噪声信 道模型引入语言处理领域。 目前噪声信道模型已经在一系列语言问题的处理中获得了比 较成功的应用。 在利用噪声信道处理语言问题时，人们并不关心编码问题，而更多关心的是，在有 噪声

12、存在的情况下，如何解码将输出还原为信道输入。因此，人们常常面对的是图 2.3 中的信道模型。 I 噪声信道 P( O| I) 解码器 IO 图 2.3 语言处理应用中的噪声信道模型 这个问题可以用公式(2.10)来描述。即在观察到 O 的情况下，人们可以通过计算找到一 个最为可能产生 O 的输入I ) 来作为原信道输入 I 的估值。 )|(maxargOIpI I = ) (2.10) 利用 Bayes 定理，可以得到公式(2.11) )( )|()( maxarg Op IOpIp I I = ) (2.11) 由于 p(O)是一个常数，故有： )|()(maxargIOpIpI I = )

13、 (2.12) 在(2.12)式中出现了两个概率分布(1) p(I)，一般称为语言模型；(2) p(O|I)，一般称 为信道模型。 作为一个例子， 这里看一下如何把噪声信道模型应用与语言的翻译问题， 假定人们 希望把一篇英语文本翻译成汉语文本。 对于这个任务， 人们可以假定信道的输入是汉语 文本，由于噪声的干扰，在信道末端人们看到的是英语文本，翻译问题就变成如何根据 信道输出的英语文本恢复为信道输入端的汉语文本的问题。 利用信道模型， 人们为翻译 问题找出了一个整齐的数学描述。 除了翻译问题， 信道模型在一系列其它语言处理问题 上得到了较好的应用，例如光学字符识别(OCR)，词性自动标注和语音

14、识别等等。 第三节 隐马尔可夫模型 隐马尔可夫过程(Hidden Markov process)是一种十分重要的随机过程，从目前计算语言 学的研究来看，基于隐马尔可夫过程的语言模型在语言信息处理领域中有着十分广泛的用 途。隐马尔可夫模型的基本理论形成于 60 年代末期和 70 年代初期。70 年代中期，CMU 的 J.K.Baker 以及 IBM 的 F.Jelinek 等人把该模型应用于语音识别问题，语音识别的研究和开发 表明,基于隐马尔可夫模型的方法是一种十分成功的方法。后来，借鉴隐马尔可夫模型在语 音识别领域中的成功经验,人们也在语言信息处理的其他领域采用这种模型，目前比较成功 的例子包

15、括：词类的自动标注、汉语文本的音字转换等等。 隐马尔可夫过程可以看作是马尔可夫过程的一种扩充， 为了引入隐马尔可夫模型， 对马 尔可夫过程有所了解是必要的。隐马尔可夫模型的英语译文是 Hidden Markov Model,一般简 写为 HMM。 一 马尔可夫过程 在日常生活中，我们会碰到很多系统，这些系统的运作和时间有关，随着时间的推移, 系统表现为一组状态的变化， 在某个具体的时刻对这个系统进行观察， 会发现这个系统处在 某个状态。例如，天气的变化，假如可以用阴天(雨雪天气)、晴天和多云来概括天气所有可 能的变化，那么，随着时间的推移，天气总是在这三种情况之间进行变化，但在某个时刻进 行观

16、察，天气又只能是晴天、阴天和多云中的一种情况。而晴天、阴天和多云正是天气这个 系统的三种状态。天气的这种变化可以用图 3.1 来描述。 阴天多云 晴天 0.1 0.2 0.2 0.3 0.3 0.1 0.40.6 0.8 图 3.1 天气变化的马尔可夫模型 在某个具体时刻(例如今天),无法准确预测下一个时刻(例如明天)天气情况,今天如果是 晴天，并不能保证明天一定也是晴天，也可能是阴天或多云。如果对大量的历史数据进行分 析，找出历史上所有的晴天，在观察其后的一天的天气情况，就能得到后一天天气情况的概 率，应用前面介绍条件概率的定义，可以表示为： P(晴天|晴天) P(阴天|晴天) P(多云|晴天) 天气随着时间的变化从一个状态按照一定概率转换到另外一个状态， 恰恰就是马尔可夫 过程的一个具体的例子。完整的马尔可夫模型可用下面的数学描述进行定义 假设 S 是一个由有限个状态组成的集合1, 2,