《自然语言处理综论》学习笔记

ZhuYuanxiang 2019-06-06 00:00:00
Categories： Tags：

Ch16 语言和复杂性

16.1 Chomsky层级

形式语言（formal language）是在有限字母表上的符号串的集合。

不同的形式化方法写的语法的类别具有不同的生成能力。

如果一种语法能够定义一种语言，而另一种语法不具备这个能力，就说明前一种语法具有更加强大的生成能力或者更大的复杂性。

Chomsky层级是一种理论工具，可以用于比较不同形式化方法的表达能力或者复杂性。

1
2
3
4
5
6
7
8
9
10
11
12
graph TB
    subgraph 递归可枚举语言
    subgraph 上下文有关语言
    subgraph 柔性上下文有关语言
    subgraph 上下文无关语言
    subgraph 正则或右线性语言
    end
    end
    end
    end
    end

类型 通用名称 规则基干 语言学例子
0 Turing等价 $\alpha\rightarrow\beta,\text{s.t.}\alpha\neq\varepsilon$ 中心语驱动的短语结构语法、词汇功能语法、最简方案
1 上下文有关 $\alpha A\beta\rightarrow\alpha\gamma\beta,\text{s.t.}\gamma\neq\varepsilon$
- 柔性上下文有关 树邻接语法、组合式范畴语法
2 上下文无关 $A\rightarrow\gamma$ 短语结构语法
3 正则 $A\rightarrow xB, A\rightarrow x$ 有限状态自动机

Chomsky层级包含了4种语法：（图16.1和 图16.2）

16.2 正则语言的判定

证明一种语言是正则语言的方法：为这种语言建立起正则表达式，再根据正则语言对于并运算、毗连运算、Kellne*运算、补运算、交运算等都是封闭的就可以了。

16.2.1 抽吸引理（pumping lemma）

如果一种语言能够被有限状态自动机模拟，那么根据这种记忆约束量来判定任何符号串是否在该语言中。这个记忆约束量对于不同的符号串不会增长得很大。

如果一个正则语言具有任意长的符号串（比自动机中的状态数还长），那么在该语言的自动机中必定会存在某种回路。即如果一种语言没有这种回路，那么它就不是正则语言。

抽吸引理：设$L$是一个有限的正则语言。那么，必定存在着符号串$x,y,z$，使得对于 $n\geq 0$，有 $y\neq\varepsilon$，并且 $xy^n z\in L$。

如果一种语言是正则语言，那么就存在着一个符号串$y$，这个$y$可以被适当的抽吸。

上下文无关语言也有一个抽吸引理，这个引理可以用来鉴别一种语言是不是上下文无关的。

16.2.2 证明各种自然语言不是正则语言

证明过程存在纰漏。

16.3 自然语言是上下文无关的吗？

在交叉序列依存（cross-serial
dependencies）中，语言中的单词或者更大的结构按照从左到右的顺序联系的形式。如果一种语言具有任意长的交叉序列依存。

16.4 计算复杂性和人的语言处理

句子理解的困难：意思太复杂、句子的歧义特征严重、使用少见的单词、书写质量太差，这些问题似乎都与记忆的有限性有关

人的剖析模型，称为依存定位理论（Dependency Locality Theory，DLT）

计算复杂性似乎都是与记忆有关的。

计算复杂性与概率剖析之间的关系。

由于记忆因素引起的计算复杂性和由于信息论和统计剖析因素引起的计算复杂性之间的关系。

16.3 小结

《自然语言处理综论》学习笔记
《自然语言处理综论》学习笔记