开塔兰数(Catalan numbers,记作Cn),即如果句子中存在这样n(n为自然数)个介词短语,Cn可以由下式获得[Samuelsson and Wiren,2000]:


  • 对于句法分析,基于单一标记的短语结构规则是不充分的;
  • 短语结构规则在真实文本中的分布呈现严重的扭曲。换言之,有限数目的短语结构规则不能覆盖大规模真实语料中的语法现象,这与原先的预期大相径庭。NLP技术的发展在很大程度上受到这两个事实的影响。从这个意义上说,本领域中称得上里程碑式的成果有三个:

    1. 复杂特征集和合一语法的提出;
    2. 语言学研究中词汇主义的建立;
    3. 语料库方法和统计语言模型的广泛运用。

大规模语言知识的开发和自动获取成为目前NLP技术的瓶颈问题。因此,语料库建设和统计学理论将成为该领域中研究的关键课题。实际上,近几年来在众多词汇资源的开发过程中,语料库和统计学方法发挥了很大的作用,这也是经验主义方法和理性主义方法相互融合的可喜开端。


最大(极大)似然估计

给定一堆数据,假如我们知道它是从某一种分布中随机取出来的,可是我们并不知道这个分布具体的参,即“模型已定,参数未知”。例如,我们知道这个分布是正态分布,但是不知道均值和方差;或者是二项分布,但是不知道均值。 最大似然估计(MLE,Maximum Likelihood Estimation)就可以用来估计模型的参数。MLE的目标是找出一组参数,使得模型产生出观测数据的概率最大:

argmax(μ) p(X;μ)

其中p(X;μ)就是似然函数,表示在参数μ下出现观测数据的概率。我们假设每个观测数据是独立的,那么有

为了求导方便,一般对目标取log。 所以最优化对似然函数等同于最优化对数似然函数:

举一个抛硬币的简单例子。 现在有一个正反面不是很匀称的硬币,如果正面朝上记为H,方面朝上记为T,抛10次的结果如下:

T,T,T,H,T,T,T,H,T,T

求这个硬币正面朝上的概率有多大?

很显然这个概率是0.2。现在我们用MLE的思想去求解它。我们知道每次抛硬币都是一次二项分布,设正面朝上的概率是,那么似然函数为:

x=1表示正面朝上,x=0表示方面朝上。那么有:

求导:

令导数为0,很容易得到:

也就是0.2 。

参考资料:https://www.cnblogs.com/sylvanas2012/p/5058065.html


联合熵、条件熵、相对熵、交叉熵

困惑度

噪声信道模型

支持向量机
线性不可分
构造核函数


一般地,描述一种语言可以有三种途径[刘颖,2002;石青云(译),1987]:

  1. 穷举法:把语言中的所有句子都枚举出来。显然,这种方法
    只适合句子数目有限的语言。
  2. 文法(产生式系统)描述:语言中的每个句子用严格定义的
    规则来构造,利用规则生成语言中合法的句子。
  3. 自动机法:通过对输入的句子进行合法性检验,区别哪些是语言中的句子,哪些不是语言中的句子。
    文法用来精确地描述语言和其结构,自动机则是用来机械地刻画对输入字符串的识别过程。用文法来定义语言的优点是:由文法给予语言中的句子以结构,各成分之间的结构关系清楚、明了。但是,如果要直接用这些规则来确定一个字符串是否属于这套规则所定的语言似乎并不十分明确。而由自动机来识别一个字符串是否属于该语言则相对简单,但自动机很难描述语言的结构。所以自然语言处理中的识别和分析算法,大多兼取两者之长。

形式语言

用一组数学符号和规则来描述语言的方式称为形式描述,而把所用的数学符号和规则称为形式语言。

字母表和符号

字母表:元素的非空有穷集合,记为∑。
例如:∑={0‚1} ∑1={a‚b,c}

  • 字母表中至少包含一个元素。
  • 字母表中的元素,可以是字母、数字或其他符号。
  • 不同的语言有不同的字母表。

符号串及其运算

符号串是由字母表中的符号组成的任何有穷序列。

例如:0,00,10是字母表∑={0‚1}上的符号串
a,ab,aaca是∑1={a‚b,c}上的符号串

符号串中的符号是有序的,顺序不同,意义不同。

例如: ab和ba不同

不含任何符号的符号串称为空串,用ε表示。
符号串长度: 符号串中含有符号的个数。

例如: |abc|=3 |ε|=0

符号串的连接
设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy。

例如:x=ST,y=abu,则xy=STabu
显然εx = xε=x

符号串的方幂
把符号串a自身连接n次得到的符号串an = aa…aa。

例如: a1=a a2=aa a0=ε

符号串集合的乘积
若集合A中所有元素都是某字母表Σ上的符号串,则称A为字母表Σ上的符号串集合。
符号串集合A和B的乘积定义为:

AB ={xy|x∈A且y∈B},

即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。

例如:集合A = {ab,cde},B = {0,1}
则 AB = {ab0,ab1,cde0,cde1}
显然 {ε}A = A{ε} = A
注意:{ε}并不等于空集合{>注意:{ε}并不等于空集合{ }>

符号串集合的方幂
设A是符号串的集合,则称An为符号串集A的方幂,其中n是非负整数。

A0 ={ε}
A1 = A
A2 = A A
An = AA......A(n个)
例如: X= {abc},
X0 ={ε},X1 ={abc} ,X2 = {abcabc}

符号串集合的正闭包

Σ+ = Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。 Σ+ 表示Σ上的除ε外的所有有穷长串的集合。
例如:设A={ a, b },则:
A+={ a, b, aa, ab, ba, bb, aaa, aab, …}

符号串集合的自反闭包

Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…称为Σ的自反闭包。 Σ*表示Σ上所有有穷长的串的集合。
例如:设有字母表Σ={0,1},则
Σ*={ε,0,1,00,01,10,11,000,…}

自反闭包与正闭包的关系

  • Σ* = Σ0∪Σ+
  • Σ+ = ΣΣ = ΣΣ

定义3-10(形式语法)

形式语法(Grammar)是一个四元组G=(N,Σ,P,S),其中,

  • N是非终结符(non-terminal symbol)的有限集合(有时也称变量集或句法种类集);
  • Σ是终结符号(terminal symbol)的有限集合,N∩Σ=∅;
  • V=N∪Σ称为总词汇表(vocabulary);
  • P(Production)是一组重写规则的有限集合:P={α→β},其中,α,β是由V中元素构成的串,但是,α中至少应含有一个非终结符号;
  • S∈N称为句子符或初始符。

文法的分类

对文法中的规则施加不同限制,将文法和语言分为四大类:

  • 0型文法(PSG): 0型语言或短语结构语言;
  • 1型文法(CSG):1型语言或上下文有关语言;
  • 2型文法(CFG):2型语言或上下文无关语言;
  • 3型文法(RG):3型语言或正则(正规)语言。

0型文法
如果对于文法G,P中每个规则具有下列形式:

α → β

其中α∈V+ ,β∈V*,则该文法G为0型文法。相应的语言称为0型语言。

例如:文法G=(VN,VT,P,S),其中VN={A,B,S} VT={0,1}
P={ S→0AB,1B→0,B→SA|01,A1→SB1,A0→S0B }
描述的 0 型语言为 L0(G[S])={ }

1型文法(上下文有关)
若文法G=(VN,VT,P,S)中的每一条规则的形式为:

αAβ → αμβ

其中A∈VN , α, β∈(VN∪VT)* ,μ∈(VN∪VT)+,
则该文法G为1型文法。相应的语言称为1型语言。

例如:文法G=(VN,VT,P,S),其中VN={B,S} VT={a,b,c}
P={ S→abc|aSBc , bB→bb , cB→Bc }
描述的1型语言为L1(G[S])={anbncn | n>1}

2型文法(上下文无关)
若文法G=(VN,VT,P,S)中的每一条规则的形式为:

A → β

其中A∈VN , β∈(VN∪VT)* , 则该文法G为2型文法。相应的语言称为2型语言。

例如:文法G=(VN,VT,P,S),其中VN={A,B,S},VT={a,b}
P={S→aB|bA, A→a|aS|bAA,B→b|bS|aBB }
描述的2型语言为L2(G[S])={x|x∈{a,b}+ 且x中a和b的个数相同}

3型文法(右线性文法和正规文法)
若文法G=(VN,VT,P,S)中的每一条规则的形式为:

A → a或 A → aB

其中A,B∈VN , a∈VT* , 则该文法G为3型文法。相应的语言称为3型语言。

例如:定义标识符,用I代表标识符; l代表任意一个字母; d代表任意一个数字; 则定义标识符的文法为:

P: I→ l | lI | dI

4种文法的比较

文法类别产生式形式产生的语言说明
0型文法(短语文法)α→β,α∈V+ ,且至少含一个非终结符,β∈V*0型语言对产生式基本无限制
1型文法(上下文有关文法)见下①1型语言(上下文有关语言)将A替换成b时,必须考虑A的上下文
2型文法(上下文无关文法)A→β,A∈VN,β∈V*2型语言(上下文无关语言)无需考虑A在上下文中的出现情况
3型文法(右线性文法)A→aB 或 A→a,A,B∈VN ,a∈VT*(a∈VT,正规文法)3型语言产生式全部是规定形式

①α→β,|β|≥|α|,α=r1Ar2,β=r1br2,A∈VN, α,β∈V* b∈V+

如何判断4种文法

  • 1型文法:|β|≥|α|≥1,规则左部至少有一个非终结符;
  • 2型文法:规则左部是单个非终结符;
  • 3型文法:看格式。

语言和语法

句型、句子和语言
设有文法G[S],若符号串α是从开始符推导出来的,即 S =>α ,且α∈V,则称α是文法G的句型。若α仅由终结符组成,即 S =>α ,且α∈VT,则称α是文法G的句子。

所有的句子一定是句型,句型不一定是句子。
例如:文法G[S]: S→0S1, S→01
S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 00001111
句型:S,0S1,00S11,000S111,00001111
句子:00001111

语言:由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即

L(G)={x|S =>+ x,且 x∈VT* }

例如:文法G: S→0S1, S→01
S ⇒ 0S1 ⇒ 00S11 ⇒ 03S13 ⇒ … ⇒ 0n-1S1n-1 ⇒ 0n1n
L(G)={0n1n|n≥1}
文法G生成的每个终结符号串都在L(G)中,L(G)中的每个串确实能被G生成。
文法一旦确定,语言也就唯一,语言可由不同的文法表示。

语法树
例如:They are students and teachers of the Physics Department.

图片1.png

它的结点由符号组成。根结点对应于开始符号。只有非终结符号对应的结点有子结点。并且,一个结点和它的子结点分别对应于文法中的一个产生式的左部和右部。
作为识别句子的辅助工具,语法树可以表示句子的结构。
直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S),对于G的任何句型都能构造与之关联的语法树。

语法树的相关概念

  • 结点:每个树的结点对应于一个符号。结点的名字就是该符号。
  • 边:两个结点之间的连线。
  • 根结点:没有边进入的结点。
  • 分支:某个结点向下射出的边和其结点称为分支。
  • 末端结点:没有向下射出的边的结点成为末端结点。在相对于句型的语法树中,末端结点可能是非终结符号。

语法树的特征
给定文法G=(VN,VT,P,S),对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征:

  • 根结点的标记是开始符号S;
  • 每个结点的标记都是V中的一个符号;
  • 若一棵子树的根结点为A,且其所有直接子孙的标记从左向右的排列次序为A1A2…AR,那么 A → A1A2..AR一定是P中的一条规则;
  • 若一标记为A的结点至少有一个除它以外的子孙,则A∈VN。

构造语法树
方法:把开始符号做为根结点,对每一步直接推导画一个分支,分支的名字是所用产生式右部的符号(按左右顺序依次出现),分支的个数是产生式右部符号串的长度。以此往下,直到再无分支可画结束。

例如:文法G[S]:
S→AB, B→cBd,
A→ab, B→cd
符号串abccdd的推导过程如下:
S ⇒ AB ⇒ AcBd ⇒ Accdd ⇒ abccdd

TIM截图20190118230230.jpg

文法和语言的一些特性

  • 无用非终结符:某个非终结符不出现在文法的任何一个句型中,并且不能从它推出终结符号串。含有该非终结符的规则即不可终止。
  • 不可达文法符号:如果一个非终结符(开始符号除外)不出现在该文法的任何其他的产生式的右部。该非终结符为不可达文法符号,含有该非终结符的规则即不可达规则。
  • 有害规则:U→U ,无用且引起文法的二义。
  • 可空非终结符: 2型文法允许以下产生式 S→ε,该产生式称为空产生式,S称为可空非终结符。在消除左递归方法中用到空产生式。
例如:文法G[S]:
(1)S→Be (2) B→Af (3) A→Ae
(4) A→e (5) C→Cf (6) D→f
多余规则为:(5)不可终止 (6)不可到达

最左推导、最右推导和规范推导

  • 最左推导:是指对于一个推导序列中的每一步直接推导 α=>β,都对 α 中的最左非终结符进行替换。
  • 最右推导:是指对于一个推导序列中的每一步直接推导 α=>β,都对 α 中的最右非终结符进行替换。
  • 最右推导也称为规范推导,用规范推导推导出的句型称为规范句型。
例:已知文法G[S]:S→AB,A→A0|1B,B→0|S1求句子101001的最右、最左推导。
S右=>AB=>AS1=>AAB1=>AA01
=>A1B01=>A1001=>1B1001=>101001
S左=>AB=>1BB=>10B=>10S1=>10AB1
=>101BB1=>1010B1=>101001

文法的二义性(Ambiguity)
例如:文法G:E→E+E|E×E|(E)|i

最左推导1:E ⇒ E+E ⇒ E×E+E ⇒ i×E+E ⇒ i×i+E ⇒ i×i+i
最左推导2:E ⇒ E×E ⇒ i×E ⇒ i×E+E ⇒ i×i+E ⇒ i×i+i

句子 i×i+i 对应的语法树:
TIM截图20190118230519.jpg

如果一个文法存在某个句子对应两棵或者两棵以上不同的语法树,则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左(右)推导。

消除文法的二义性

  • 方法一:不改变文法中原有的语法规则,仅加进一些语法的非形式规定。
  • 方法二:构造一个等价的无二义性的文法,即把排除二义性的规则合并到原有文法中,改写原有的文法。

分析方法简介

对于2型文法,如何识别一个符号串是否为某文法的句型或句子,有两种分析方法:

  • 自顶向下分析法 (Top-Down parsing)
  • 自底向上分析法 (Bottom-Up parsing)

自顶向下的分析方法
定义:从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导。
语法树的构造:将文法的开始符号作为语法树的根,向下逐步建立语法树,使语法树的末端结点符号串正好是输入符号串。
例如:

文法G:S → cAd
A → ab
A → a
识别输入串w=cabd是否为该文法的句子。
推导过程: S =>cAd =>cabd

TIM截图20190118231314.jpg
自底向上的分析方法
定义:从输入符号串开始,在其中寻找句柄,此句柄如果与某一产生式右部相匹配,就用产生式左部去替换句柄,替换之后得一新符号串,继续进行同样的句柄替换处理。这种处理过程是一种归约过程,直至归约到文法的开始符号。
语法树的构造:从输入符号串开始,以它作为语法树的末端结点符号串,自底向上的构造语法树。
例如:

文法G:S → cAd
A → ab
A → a
识别输入串w=cabd是否为该文法的句子。
归约过程: cabd |-cAd|-S

TIM截图20190118231422.jpg