文本信息处理预备知识.

文本信息处理章成志DepartmentofInformationManagement,SchoolofEconomicsandManagement,NanjingUniversityofScienceandTechnologyE-Mail:[e-mail]:@章成志Blog:预备知识预备知识•概率统计基础•信息论基础•集合论基础•线性代数基础•实验数据•性能评价•编程工具3——宗成庆.统计自然语言处理.北京：清华大学出版社,2008.——刘群.计算语言学课件概率统计基础•样本空间•事件、随机变量•概率•条件概率•联合概率•独立事件•贝叶斯原理•期望与方差•概率分布•协方差、相关系数•参数估计•极大似然估计•随机过程•马尔科夫过程4概率统计基础•概率(Probability)5概率是从随机实验中的事件到实数域的函数，用以表示事件发生的可能性。如果用P(A)作为事件A的概率，是实验的样本空间，则概率函数必须满足如下公理：公理1（非负性）：P(A)0公理2（规范性）：P()=1公理3（可列可加性）：如果对任意的i和j(i≠j)，事件Ai和Aj不相交(Ai∩Aj＝Φ)，则有：概率统计基础•最大似然估计(MaximizationLikelihoodEstimation)6概率统计基础7概率统计基础•条件概率(ConditionalProbability)8概率统计基础•全概率公式9概率统计基础10概率统计基础•贝叶斯法则(Bayes’Theorem)11概率统计基础•贝叶斯决策理论(BayesianDecisionTheory)12概率统计基础•例子假设某一种特殊的句法结构很少出现，平均大约每100,000个句子中才可能出现一次。我们开发了一个程序来判断某个句子中是否存在这种特殊的句法结构。如果句子中确实含有该特殊句法结构时，程序判断结果为“存在”的概率为0.95。如果句子中实际上不存在该句法结构时，程序错误地判断为“存在”的概率为0.005。那么，这个程序测得句子含有该特殊句法结构的结论是正确的概率有多大？13概率统计基础假设G表示事件“句子确实存在该特殊句法结构”，T表示事件“程序判断的结论是存在该特殊句法结构”。那么，我们有：14求：P(G|T)=?概率统计基础•二项式分布(BinomialDistribution)15概率统计基础•二项式分布(BinomialDistribution)16概率统计基础•二项式分布(BinomialDistribution)17在自然语言处理中，常以句子为处理单位。一般地，我们假设一个语句独立于它前面的其它语句，句子的概率分布近似地认为符合二项式分布。概率统计基础•期望(Expectation)18概率统计基础•方差(Variance)19N元语法模型20N元语法模型21信息论基础•信息量•互信息•熵•联合熵、条件熵•交叉熵•困惑度、混乱度Perplexity•噪声信道模型22信息论基础•熵(Entropy)23•香农(ClaudeElwoodShannon)于1940年获得MIT数学博士学位和电子工程硕士学位后，于1941年加入了贝尔实验室数学部，并在那里工作了15年。1948年6月和10月，由贝尔实验室出版的《贝尔系统技术》杂志连载了香农博士的文章《通讯的数学原理》，该文奠定了香农信息论的基础。•熵是信息论中重要的基本概念。信息论基础•熵(entropy)24信息论基础•熵(entropy)25熵又称为自信息（self-information），表示信源X每发一个符号(不论发什么符号)所提供的平均信息量。熵也可以被视为描述一个随机变量的不确定性的数量。一个随机变量的熵越大，它的不确定性越大。那么，正确估计其值的可能性就越小。越不确定的随机变量越需要大的信息量用以确定其值。信息论基础•例子26计算下列两种情况下英文（26个字母和空格，共27个字符）信息源的熵:(1)假设27个字符等概率出现；(2)假设英文字母的概率分布如下：信息论基础•解：27说明：考虑了英文字母和空格实际出现的概率后，英文信源的平均不确定性，比把字母和空格看作等概率出现时英文信源的平均不确定性要小。信息论基础•词熵、字母熵、汉字熵28冯志伟计算出：–汉字的熵为9.65比特–法语一个字母的熵为3.98比特–意大利语一个字母的熵为4.00比特–西班牙语一个字母的熵为4.01比特–英语一个字母的熵为4.03比特–德语一个字母的熵为4.12比特–俄语一个字母的熵为4.35比特信息论基础29•1970年代末期冯志伟首先开展了对汉字信息熵的研究，经过几年的语料收集和手工统计，在当时艰苦的条件下测定了汉字的信息熵为9.65比特(bit)。•1980年代末期，刘源等测定了汉字的信息熵为9.71比特，而汉语词的熵为11.46比特。•汉语词汇平均长度约为2.5个汉字。信息论基础30信息论基础31•联合熵(JointEntropy)信息论基础32•条件熵(ConditionalEntropy)信息论基础33信息论基础34•例：假设(X,Y)服从如下联合分布：请计算H(X)、H(Y)、H(X|Y)、H(Y|X)和H(X,Y)各是多少？信息论基础35信息论基础36信息论基础37信息论基础38信息论基础39•相对熵(RelativeEntropy,或Kullback-Leiblerdivergence,KL距离)两个概率分布p(x)和q(x)的相对熵定义为：(18)信息论基础40对熵常被用以衡量两个随机分布的差距。当两个随机分布相同时，其相对熵为0。当两个随机分布的差别增加时，其相对熵也增加。信息论基础•交叉熵(CrossEntropy)41(19)信息论基础•困惑度(Perplexity)42(20)信息论基础•互信息(MutualInformation)43如果(X,Y)~p(x,y)，X,Y之间的互信息I(X;Y)定义为：I(X;Y)=H(X)–H(X|Y)(21)(22)信息论基础44信息论基础•应用：中文分词问题45利用互信息值估计两个汉字结合的强度：互信息值越大，表示两个汉字之间的结合越紧密，越可能成词。反之，断开的可能性越大。信息论基础46信息论基础47信息论基础48•噪声信道模型(NoisyChannelModel)•在信号传输的过程中都要进行双重性处理：一方面要通过压缩消除所有的冗余，另一方面又要通过增加一定的可控冗余以保障输入信号经过噪声信道后可以很好的恢复原状。信息编码时要尽量占用少量的空间，但又必须保持足够的冗余以便能够检测和校验错误。接收到的信号需要被解码使其尽量恢复到原始的输入信号。•噪声信道模型的目标就是优化噪声信道中信号传输的吞吐量和准确率，其基本假设是一个信道的输出以一定的概率依赖于输入。信息论基础49信息论基础50信息论基础51(23)信息论基础52(24)信息论基础53信息论基础54(25)信息论基础55信息论基础56集合论基础57集合论基础58线性代数基础59•向量空间模型线性代数基础60向量的内积61nnyxyxyxyx2211],[令：的内积。与称为向量yxyx],[121x例如：013,yyx,=5011231xx,=6)1(21222定义：设有n维向量nxxxx21nyyyy21向量的长度62⑴定义22221],[nxxxxxx称为n维向量x的长度(或范数).6,121)1(21222xxxx其长度为：如：⑵向量长度的性质①非负性：当0x时，0x；当x=0时，0x。②齐次性：xx③三角不等式：yxyx向量的单位化63实验数据64•训练集TrainingSet–用来获得模型参数•测试集TestSet–从训练集以外独立采样–反映系统面对真实世界的处理能力•封闭测试与开放测试•交叉验证Cross-Validation–将数据集分为k个子集–用k-1个子集作训练集，1个子集作测试集，然后k次交叉验证•公开测评数据集-LDC,Chinese-LDC性能评价65性能评价66编程工具•编程语言：Python,java,C++•编程工具：NLTK67什么是Python?68Python的特点•历史短（不到10年），但应用广泛–大范围应用，尤其在AI和Web领域•非常容易学习–很多学校用把Python作为入门语言•编程方便–相比C、C++、Java代码短得多•容易阅读与维护–类似于自然语言和数学公式的语法69“HelloWorld!”70NLTK工具•NLTK：NaturalLanguageToolkit•NLTK是用Python实现的一套自然语言处理软件工具•NLTK包括：–与NLP相关的基本数据类型–NLP的标准函数接口：切词、标注、句法分析等–NLP中常见任务的具体实现–NLP任务演示（句法分析、组块分析、聊天机器人）–详尽的文档、教程与参考书目–随工具包发布的数据：词典、语料库等等71Thanks!Q/AE-mail:[e-mail]