Chapter-02-new

第二讲语言知识的形式化表示提纲„1自然语言现象举例„2关于自然语言的知识„3知识的表示¾3.1有限状态自动机（正则表达式）¾3.2上下文无关文法¾3.3特征结构与合一运算„4小结31自然语言现象举例IvanA.Sag&ThomasWasow,1999,SyntacticTheory:AFormalIntroduction,CSLIPublications例1A.ItisunlikelythatLeewillbeelected.B.ItisimprobablethatLeewillbeelected.A’.Leeisunlikelytobeelected.B’.*Leeisimprobabletobeelected.4自然语言现象举例（续）例2aC.张三爱好下围棋D.张三喜欢下围棋C’.下围棋是张三的爱好D’.*下围棋是张三的喜欢5自然语言现象举例（续）例2bC.读过那本书的学生不多D.参观故宫的学生回来了C’.那本书读过的学生不多D’.*故宫参观的学生回来了6自然语言现象举例（续）例3E.这件事容易办F.这件事好办E’.办这件事容易F’.办这件事好7自然语言现象举例（续）例4G.马文才害死了梁山伯H.梁山伯被马文才害死了G/*HI.，欺骗了祝英台。8自然语言现象举例（续）例5J.桌子上有两本书K.有两本书在桌子上J?KL.，一盏台灯，一个笔筒，还有一摞练习本92关于自然语言的知识对于自然语言，人具有以下三个层面的能力：‹人们一般可以判断一个表达形式是否属于一种语言，比如上面例1和例2中，人们能够判断出句子A'不属于英语（即不被说英语者接受），句子C'不属于汉语（即不被说汉语者接受）；‹对于一种语言中的两个表达形式，人们一般可以判断二者之间是否具有某种关系，比如同义关系，两个表达式所对应的命题之间的逻辑蕴含关系，等等。像上面例3，人们能够判断句子E跟E‘是同义关系，但F跟F’不是同义关系。‹对于一种语言中两个同义的表达式，人们一般可以判断在特定场合下使用哪一个表达式更好，比如上面例4和例5。10语言知识的分层„句法知识★★★★★„语义知识★★★„语篇知识★语音知识（参见附录）11语言知识（1）“X的Y”结构形式：dzjg（2）X＝名词、形容词、动词；Y＝名词（3）“爱好”＝动词|名词“喜欢”＝动词“张三”＝名词12?（1）好1，好2，容易＝形容词（2）A+B:zzjg（A=形容词，B＝动词）（3）B+A:zwjg（4）zzjg(a,b)Ùzwjg(b,a)（5）“好1”只能进入zzjg（＝“easy”）“好2”只能进入zwjg（＝“good”）“容易”可以进入zzjg,zwjg语言知识（续）BbAa∈∈;13对语言知识的认识代数学（理性主义）的定义方法–确定性定义方法–语言是由规则所定义的句子的集合统计学（经验主义）的定义方法–不确定性定义方法–语言就是一个概率分布，又称为语言模型–语言中的每一个句子都有自己的出现概率143知识的表示„用自然语言来描述关于自然语言的知识„用形式语言来描述关于自然语言的知识对象语言（ObjectLanguage）元语言（MetaLanguage）15从自然语言到形式语言„避免混淆，“动词”不是动词„避免罗嗦，“从前有个山，山上有个庙……”„可计算，结构化的数据16形式语言（FormalLanguage）的一些例子™2＋5＝7™2H2+O2=2H2O™P&Q（P:董永是放牛郎；Q:董永喜欢七仙女）™IS_COWBOY(x)&IS_Vega(y)&LOVE(x,y)17计算机语言#includestdio.hmain(){printf(\n\thello,world);return0;}一个C语言例子18如何描述（严格定义）一个语言„枚举„给出语言中的所有句子„对于含无限多个句子的语言不合适„文法„给出生成语言中所有句子的方法„当且仅当能够用该方法产生的句子才属于该语言„自动机„给出识别该语言中句子的机械方法过程性定义描述性定义列举性定义193.1有限状态自动机εq0q1q2NNVN有限状态自动机（FiniteStateAutomata）20状态转移表（statetransitiontable）q1q2q2q2q1q1q1q0VN弧(输入)状态转移ε21状态转移过程示例→字符串状态转移过程NVq0q1q2NVNq0q1q2q2NVNVNq0q1q2q2q1q2q2…………→→→→→→→→→→22有限状态自动机(FSA)的形式定义„一个有限状态自动机M是一个五元组：(Q,Σ,q0,F,δ)„有限个状态组成的状态集:Q„有限字母组成的字母表:Σ„开始状态q0∈Q„终止状态的集合F⊆Q„状态转移函数δ(q,i):QxΣÆQ23识别一个十进制实数的自动机q1+-0~9.0~90~9q3q2q00~924正则表达式（RegularExpression）(\+|-)?[0-9]+(\.[0-9]*)?q1+-0~9.0~90~9q3q2q00~9Jurafsky&Martin(2000),第2章25Eliza中的正则表达式操作„人：Myboyfriendmademecomehere.„Eliza:YourBoyfriendmadeyoucomehere.„人：HesaysI’mdepressedmuchoftime.„Eliza:Iamsorrytohearyouaredepressed.正则表达式替换：1）/(.*)my(.*)/=/\1your\2/2）/(.*)I’m(.*)/=/\1youare\2/3）/.*youare(depressed|sad).*/=/Iamsorrytohearyouare\1/Eliza的操作就是做一连串的正则表达式的匹配和替换。Jurafsky&Martin(2000),第2章，pp32-33.26弧上带输出的FSTN：Transducerq0q1q2N:nN:nV:vN:n董永喜欢七仙女－Dong_YonglovesQi_Xiannv董永七仙女喜欢－Dong_YongQi_Xiannvloves有限状态转录机27课堂练习„构造一个有限状态转移网络，可以接受汉语的重叠形式AABB，ABB，ABAB，…28课堂练习„构造识别名词词组的FSA三本书语法书阿Q的书阿Q的三本书阿Q的三本语法书阿Q的三本汉语语法书阿Q的三本古代汉语语法书阿Q和他的三本汉语语法书……29从FSA到上下文无关文法（CFG）„FSA：无法描述自然语言的层次结构特性听说服装设计很吃香——听说那套服装设计得很有品位听说孩子丢了——听说孩子丢了一只鞋听说北京队大败——听说北京队大败上海队303.2上下文无关文法„符号„字母表：有限个任意符号组成的非空集合Σ„例1：所有汉字组成的集合构成一个字母表。„例2：汉语中所有的词也构成一个字母表。„例3：字母a,b,c也组成一个字母表。„字符串：由字母表Σ上的字符组成的长度有限的序列„若字母表Σ＝{a,b}，则a,b,ab,aba,aabb等等都是字母表上的字符串。31语言的形式定义语言：是字母表上的字符串的任意集合。例1.若Σ={a,b}，则定义在Σ上的语言可以是L1={ab,ba}L2={ab,abab,ababab,…}32形式文法形式文法：一个形式文法G由四个部分组成，可记作G={VN,VT,S,P}，其中：VN：称为文法G的非终结符号字母表，VN不出现在G所表示的语言集合的句子中；VT：称为文法G的终结符号字母表，G所表示的语言的句子由VT中的元素组成，VN∩VT=；S：代表句子符号，S∈VN。P：代表一组式子组成的集合，P中的式子具有如下形式：βα→φ33形式文法（续）产生式规则（productionrule）重写规则（rewritingrule）产生式需要满足下面的条件：1）α可以是VN和VT上的任意字符串，不能是空字符；2）β可以是VN和VT上的任意字符串，可以是空字符；3）P中至少有一个产生式中的α得由S来充当；βα→34上下文无关文法„对产生式规则做如下约定：βα→1=αNV∈α*)(TNVVU∈β这样的形式文法就是“上下文无关文法”。35一个上下文无关文法的例子设文法G0=(VN,VT,S,P)，其中VN={S,NP,VP,N,V},VT={喜欢,知道,董永,七仙女},P中产生式如下：1.S-NPVP2.VP-VPNP3.VP-VPS4.VP-V5.NP-N6.N-董永7.N-七仙女8.V-喜欢9.V-知道36直接推导、推导、句型、句子、语言直接推导：S=NPVP推导：S=NPVP=NPV=NV上式可以简写为：SNV句型：NPVP,NPV,NV,…是G0的句型句子：仅含终结符号的句型，NV语言：给定一个文法G0，该文法所产生的所有句子组成的集合，称为该文法所定义的语言⇒*37G0所描述的语言L0S1:董永喜欢七仙女S2:董永知道董永喜欢七仙女S3:七仙女知道董永S4:七仙女喜欢董永知道董永S5:七仙女喜欢董永董永董永七仙女……38不属于L0的字符串S1’:知道喜欢知道七仙女S2’:董永董永七仙女知道喜欢S3’:七仙女董永喜欢……39句子结构的树形描述SNPVPVPSNPVPVPNPNVNVN董永知道董永喜欢七仙女1234567891011121314句法结构分析树40文法的三个作用„生成；产生语言L中所有的句子；„判定：一个字符串（String）是否属于语言L；„分析：得到L中句子的结构树；分析出句子的结构是进行自然语言信息处理的基础比如移位变换，就必须建立在结构分析的基础上张三知道李四不会当逃兵-当逃兵，张三知道李四不会-*知道李四，张三不会当逃兵41句法结构分析的效用：控制转换张三知道李四不会当逃兵npvpnpsvpvpnvndvvnvpsvpdpvpvpnp当逃兵张三知道李四不会npsvpvnnvndvvpsdpvpvpnpvpvpnps42练习对于语言L={ab,aabb,aaabbb,…,anbn,…}n是自然数。（1）请写出L的上下文无关文法；（2）要求产生式右部不能超过两个符号；43乔姆斯基范式（ChomskyNormalForm）„AÆBC„AÆaAÆBCDAÆBXXÆCDABCDABXCD112一个三分支规则可以转换为两个二分支规则引入一个新的非终结符X44练习1写出汉语表示自然数的词的CFG2用你写的CFG，画出下列数字的分析树：一亿零三百万三万六千五百八十一45基于简单范畴的文法的缺陷„范畴划分有不同的颗粒度（granularity）例如英语句子的构成规则：SÆNPVP如果考虑到英语主谓语单复数的搭配，就要将NP和VP分成NPsingular和NPplural和VPsingular和VPplural，并其将规则改写成：SÆNPsingularVPsingularSÆNPpluralVPplural„范畴划分有不同的角度（perspective）np_countnp_animatenpnpnp_uncountnp_inanimate463.3特征结构与合一运算„特征结构（FeatureStructure）复杂特征集（ComplexFeatureSet）„特征结构定义为“特征”的集合„所谓“特征”，是一个由“属性”和“值”组成的二元组，“属性”也称为“特征名”，“值”也称为“特征值”„在特征结构中，要求所有的“特征”的“属性”互不相同„空特征结构：不含任何特征的特征结构attribute1=value1attribute2=value2………attributen=valuen¾引入特征结构弥补简单范畴的不足记作：[]47特征结构的嵌套与共享1）“特征值”可以是一个字符串值或数值等简单类型，也可以是另一个特征结构，这就是所谓的特征结构的“嵌套”；为了区别于特征结构形式的特征值，我们把简单的字符串形式的特征值称为原子（atom）2）两个特征可以共享一个值，这是所谓的特征值的“共享”（也称为“重入”/Reentr