UCAS - AI学院 - 自然语言处理专项课 - 第8讲 - 课程笔记_pcfg的优缺点

句法分析·短语结构分析

概述

• 完全句法分析：获得句子完整的句法分析树
• 目标：实现高准确率、高鲁棒性、快速句子结构自动分析过程
• 困难：结构歧义（Catalan Number）
• 基本方法
  • CFG规则分析方法
    • 线图分析
    • CYK
    • Earley
    • LR / Tomita
  • PCFG规则分析方法
  • NN改进的分析方法

线图分析法

• 三种策略
  • bottom-up：词到句子的规约
  • top-down：句子到词的推导
  • combining
• 自底向上Chart分析算法
  • 给定一组CFG规则
  • 给定一个句子的词性序列（保留多个词性）
  • 构造一个线图（结点和边的组合，边为对应词的词性）
  • 建立一个二维表（每一条边的起始和终止）
  • 操作：查看任意相邻几条边上的词性串是否与某条重写规则右部相同，则增加一条跨边，标记为重写规则的左部，直到没有新的边产生
  • 点规则：用于表示规则右部被归约的程度
    • 活性边：规则右部未被完全匹配
    • 非活性边：规则右部完全匹配
• 数据结构
  • 线图Chart：分析过程中已经建立的成分、位置，$n\times n$数组
  • 代理表Ageda：重写规则代表的成分，栈或者队列
  • 活动边集Active Arc：未完全匹配的处理规则，数组或者列表
• 算法P28
• 时间复杂度分析
  • $C$式非终结符数目，$n$为句子长度，$S$为点规则状态数目
  • Agenda表中最大元素个数$C{n}^2$
  • Active Arc表中最大元素个数$S{n}^2$
  • Chart表中最大元素个数$C{n}^2$
  • 操作·非终结符插入到Agenda表，最多$C$次（规则个数）
  • 操作·取出Agenda表中的一个元素，最多1次操作
  • 操作·每条规则加入Active Arc表，最多$S{n}^2$次操作
  • 操作·扩展弧·非终结符插入Chart表，最多1次操作
  • 操作·扩展弧·将扩展的活动便插入Agenda表，最多$S{n}^2$次操作
  • 操作·扩展弧·扩展点规则插入Active Arc表，最多$S{n}^2$次操作
  • 每处理一个单词，需要最多操作数$2+C+3S{n}^2$
  • 对整个句子，总最大操作数$n\times (2+C+3S{n}^2)$
  • 时间复杂度$O(K{n}^3)$
• 优点：简单易于实现
• 弱点：效率低、需要高质量规则、难以区分歧义结构（可以得到多个分析结果，但是无法确定哪个是对的）

CYK分析法

• 算法
  • 对Chomsky文法进行规范化
    • $A\to w$，标记
    • $A\to BC$，多标记展开
  • 自下而上的分析方法
  • $(n+1)\times (n+1)$识别方阵，$n$为句子长度
• 识别矩阵构成
  • 主对角线以下全部为0
  • 主对角线以上由文法$G$的非终结符狗哼
  • 主对角线上元素由句子终结符构成
• 识别矩阵构造
  • $t_{0,0}=0$，从$t_{1,1}$到$t_{n,n}$放入单词$w_i$
  • 靠主对角线元素$t_{i,i+1}$，开始分析
    • 对规则$A\to w_1$，那么$t_{0,1}=A$
    • 后续以此类推，沿平行主对角线方向推导（无规则可用时，直接复制没分析的那一项）
    • 对规则$A\to BC$，$B\in t_{i,k}$，$C\in t_{k,j}$，则$t_{i,j}=A$
  • 句子由$G$生成，当且仅当$t_{0,n}=S$
• 优点：实现简单，执行效率高
• 缺点：需要对文法范式化处理，无法区分歧义

基于PCFG的分析法

• 概率上下文无关文法

  • $A\to \alpha ,p$
  • ${\sum }_{\alpha }p(A\to \alpha )=1$

• 计算分析数概率的基本假设

  • 位置不变性：子树的概率与其管辖的词在句子中的位置无关
  • 上下文无关性：子树概率与管辖范围以外的词无关
  • 祖先无关性：子树概率推导与子树祖先结点无关

• 将子树视为独立事件，子树概率计算可以使用其包含子树概率连乘得到

• 三个问题

  • 给定句子$W$和PCFG$G$，快速计算$p(W|G)$
  • 给定句子$W$和PCFG$G$，快速选择最佳句法结构树
  • 给定句子$W$和PCFG$G$，调节$G$使$p(W|G)$最大

• 假设文法只有两种形式（规范化，Chomsky范式）

  • $A\to w$，标记
  • $A\to BC$，多标记展开

• 快速计算句法树概率：内向或外向算法

  • 内向算法：动态规划，计算由非终结符$A$推导出字串片段$w_i\dots w_j$的概率${\alpha }_{ij}(A)$，而句子的概率则是由$S$推导出字串的概率${\alpha }_{1n}(S)$
    • ${\alpha }_{ij}(A)=p(A{\Rightarrow }^{\ast }{w}_i\dots w_j)$
    • 递推公式：${\alpha }_{ii}(A)=p(A\to w_i)$
    • 递推公式：${\alpha }_{ij}(A)={\sum }_{B,C\in V_N}{\sum }_{i\le k\le j}p(A\to BC){\alpha }_{ik}(B){\alpha }_{(k+1)j}(C)$
    • 初始化：${\alpha }_{ii}(A)$
    • 归纳计算：$j=1\dots n,i=1\dots n-j$，计算${\alpha }_{i(i+j)}(A)$
    • 终止：$p(S{\Rightarrow }^{\ast }{w}_1\dots w_n)={\alpha }_{1n}(S)$
    • 内向归纳，自底向上
  • 外向算法：外箱变量${\beta }_{ij}(A)$是由文法初始符号$S$推导语句$W$的过程中，到达扩展符号串$w_1\dots w_{i-1}A{w}_{j+1}{w}_n$的概率
    • ${\beta }_{ij}(A)=p(S{\Rightarrow }^{\ast }{w}_1\dots w_{i-1}A{w}_{j+1}{w}_n)$
    • ${\beta }_{ij}(A)={\sum }_{B,C}{\sum }_{k>j}{\beta }_{ik}(B)p(B\to AC){\alpha }_{(j+1)k}(C)+{\sum }_{B,C}{\sum }_{k<i}{\beta }_{ik}(B)p(B\to CA){\alpha }_{k(i-1)}(C)$
      • 推导到$B$的概率，乘上扩展$B$的概率，再乘上扩展另外一侧到字串的概率
    • 表示除了$A$为根节点的子树以外的概率
    • 初始化：${\beta }_{1n}(A)=\delta (A,S)$
    • 归纳计算：$j=n-1\dots 0,i=1\dots n-j$，计算${\beta }_{i(i+j)}(A)$
    • 终止：$p(S{\Rightarrow }^{\ast }{w}_1\dots w_n)={\sum }_A{\beta }_{ii}(A)p(A\to w_i)$
    • 自顶向下，外向扩展

• 最佳搜索：Viterbi算法

  • ${\gamma }_{ij}(A)$是由非终结符$A$推导出语句$W$中字串$w_i\dots w_j$的最大概率
  • ${\Psi }_{i,j}$用于保存Viterbi分析结果
  • 注意与$\alpha$的区别：前者算综合，后者算最大
  • 初始化：${\gamma }_{ii}(A)=p(A\to w_i)$
  • 归纳计算：$j=1\dots n,i=1\dots n-j$，${\gamma }_{i(i+j)}(A)={\max }_{B,C\in V_N,i\le k\le i+j}p(A\to BC){\gamma }_{ik}(B){\gamma }_{(k+1)j}(C)$，${\Psi }_{i(i+j)}(A)=\arg {\max }_{B,C\in V_N,i\le k\le i+j}p(A\to BC){\gamma }_{ik}(B){\gamma }_{(k+1)j}(C)$
  • 终止：$\max p(S{\Rightarrow }^{\ast }{w}_1\dots w_n)={\gamma }_{1n}(S)$

• 参数估计：内外向算法

  • 使用大量语料直接估计参数

    • $\hat{p}(N^j\to \zeta )=\frac{C(N^j\to \zeta )}{{\sum }_{\gamma }C(N^j\to \gamma )}$

  • 没有大量语料，EM算法

    • 初始随机赋值，得到模型

    • 训练语料，得到期望值

    • 最大似然估计

    • 得到新的模型，迭代训练

    • $$\begin{array}{rl}C(A\to BC)& =\sum _{1\le i\le k\le j\le n}p(A_{ij},B_{ik},C_{(k+1)j}|w_1\dots w_n,G)\\ & =\frac{1}{p(w_1{\dots }_n|G)}\sum _{1\le i\le k\le j\le n}p(A_{ij},B_{ik},C_{(k+1)j},w_1\dots w_n|G)\\ & =\frac{1}{p(w_1{\dots }_n|G)}\sum _{1\le i\le k\le j\le n}{\beta }_{ij}(A)p(A\to BC){\alpha }_{ik}(B){\alpha }_{(k+1)j}(C)\end{array}$$

      • 推导到$A$的概率，扩展$A$的概率，全部扩展到字串的概率

    • $$\begin{array}{rl}C(A\to a)& =\sum _{1\le i\le k\le j\le n}p(A_{ii}|w_1\dots w_n,G)\\ & =\frac{1}{p(w_1{\dots }_n|G)}\sum _{1\le i\le k\le j\le n}p(A_{ii},w_1\dots w_n|G)\\ & =\frac{1}{p(w_1{\dots }_n|G)}\sum _{1\le i\le k\le j\le n}{\beta }_{ii}(A)p(A\to a)\delta (a,w_i)\end{array}$$

    • $\hat{p}(A\to \mu )=\frac{C(A\to \mu )}{{\sum }_{\mu }C(A\to \mu )}$

• Learning Algorithm -> PCFG -> CYK / Chart

• 优点：利用概率进行剪枝，减少搜索空间，加快分析效率；可以定量比较两个句法分析器性能（概率置信度）

• 缺点：对概率计算条件比较苛刻（三个假设）

句法分析性能评估

• PARSEVAL评测
  • 精度：正确短语个数占比
  • 召回率：正确短语个数占正确答案比例
  • F-值：常取F-1值
  • 交叉括号数：分析树中与其他分析树边界交叉成分个数的平均值
    • 标记格式$XP-(SP,TP)$
    • 短语标记，起始位置，终止位置
• 汉语句子分析性能低于英文

局部句法分析

• 浅层句法分析 / 语块划分
• 语块识别 + 语块之间依存关系分析
• 英语语块
  • 词
  • 非递归名词短语、动词词组
    • Base NP，简单、非嵌套名词短语，看作基本分类问题识别（序列标注，IOB，）
  • 非递归副词短语、介词短语
  • 子句
• 基于SVM的识别方法（Base NP）
  • 三类特征：词、词性、Base NP标志

句法分析·依存句法分析

概述

• 一切接结构句法现象可以概括为关联、组合和转位三个核心
  • 关联——词之间的从属关系
  • 动词是句子的中心，并支配其他成分，本身不受任何成分支配
• “价”的概念：动词所能支配的行动元（名词词组）的个数
• 依存关系：词语之间支配和被支配的关系
• 有向图表示：有向弧表示两个成分的依存关系，由支配者出，到达被支配者
• 依存树表示：子节点依存于父节点，也可以表示成依存投射树
• 依存语法的4条公理
  • 一个句子只有一个独立的成分（单一父节点）
  • 句子的其他成分都从属于某一成分（联通）
  • 任何一成分都不能依存于两个或多个成分（无环）
  • 如果成分A直接从属于成分B，而成分C在句子中位于A和B之间，那么，成分C或者从属于A，或者从属于B，或者从属于A和B之间的某一成分（可投射）
• 不可投射的：依存关系树中虚线于实线相交的情形
• 优势
  • 简单，天然此会化的
  • 不过多强调句子中的固定顺序
  • 受深层语义结构驱动
  • 形式化程度较浅，更加灵活

依存关系分析方法

• 输入：句子
• 输出：依存结构，有向图描述
• 生成式分析方法
  • 采用联合概率模型$\mathrm{Score}(x,y|\theta )$，生成一系列语法树，赋予概率分值，取最大概率作为最终结果
  • 优点：大规模样本可以获得好的性能
  • 弱点
    • 联合概率模型，需要各种假设简化，不易加入语言特征
    • 全局搜索，复杂度较高，$O(n^3)$或$O(n^5)$
• 判别式分析方法
  • 采用条件概率模型$\mathrm{Score}(x|y，\theta )$，使目标最大的$\theta$作为模型的参数
  • 最大生成树模型
    • 整棵树的分值$s(\mathbf{x},\mathbf{y})={\sum }_{(i,j)\in y}s(i,j)={\sum }_{(i,j)\in y}\mathbf{w}\cdot \mathbf{f}(i,j)$
    • $s(i,j)$两节点之间的边的分值，$\mathbf{f}(i,j)$为二元特征函数向量，$\mathbf{w}$为对应特征函数的权值
  • 优点
    • 避开了联合概率需要的独立性假设
    • 较好的可计算性，可应用更多方法，可处理非投射现象
    • 分析准确率较高
  • 弱点
    • 整句内全局搜索，不易使用动态特征
    • 算法复杂度较高
• 决策式分析方法
  • 模仿人的认知过程，按照特定方向每次读入一个词，每一步由当前状态做出决策（判断依存关系），不再改变
  • 移进-规约算法（Shift-Reduce）
    • 三元组：S（栈顶词），I（当前词），A（依存弧集合）
    • 两种动作：规约（左 / 右的依存关系建立）、移进（移入栈中）
    • 改进（Arc-eager）四个动作：LArc（依存弧向左指）、RArc（依存弧向右指）、规约（退出当前考察，非根词移出栈）、移进，由stack和queue维护
    • 算法P23
    • 基于动作转移的方法（决策之间逐步专业）
    • 优点
      • 之前产生的所有句法结构作为特征
      • 新型时间复杂度$O(n)$
    • 弱点
      • 局部最优代替全局最优，导致错误传递
      • 不可处理非投射现象
• 依存句法分析器实现（Arc-eager）
  • 动作转换
  • 足够多的训练集
  • 每个数据结构维护两个指针（顶和次顶）
  • 左弧——可直接规约
  • 右弧——不可直接规约，需等待判断进一步的右弧

依存关系分析性能评估

• 无标记依存准确率UA：所有词中正确支配词所占百分比，未找到支配词的词也算在内
• 带标记依存准确率LA：所有词中正确支配且依存关系类型也正确的百分比，根节点也算在内
• 依存正确率DA：所有非根结点词中找到其正确支配词的词所占的百分比
• 根正确率RA
  • 定义1：正确根结点的个数与句子个数的比值
  • 定义2：所有句子中找到正确根结点的句子所占的百分比
  • 对单根节点语言，二者等价
• 完全匹配率CM：所有句子中无标记依存结构完全正确的句子所占的百分比

短语结构与依存关系

• 短语结构可转换为依存结构
  • 定义中心词抽取规则，产生中心词表（中文短语中，中心词往往在最后）
  • 根据中心词表，为句法树中每个节点选择中心子节点（中心词自底向上传递得到）
  • 将非中心子节点的中心词依存到中心子节点的中心词上，得到相应的依存结构

基于深度学习的句法分析

• 面向决策式依存分析的离散特征和连续特征相结合方法
  • 结合词向量中的非线性关系
  • Word2vec（融入连续特征） + CRFs（动作序列分类）
  • 连续特征离散化后于原离散特征相结合（利用离散特征的鲁棒稀疏优势）
  • 连续特征隐层向量与原离散特征结合（计算各动作的分值）
• 基于机器翻译原理的句法分析方法
  • 句法树——短语标记序列
  • 机器翻译——句子翻译成短语标记序列

英汉句法结构特点对比

• 不考虑汉语分词和词性兼类带来的影响
• 汉语更少地使用功能词，且没有形态变化；不适用限定词的名词普遍存在，复数标记有限且很少出现
• 英语短语绝大部分以左部为中心；汉语比较复杂，大多数以右部为中心，动词和介词的补语在中心词的后面
• 汉语句子普遍存在没有主语的情况——难以判断是句子还是短语
• 英语是结构性语言，分句间结构联系；汉语是表意型语言，分句间结构独立
• 汉语长句分析方法：句群——分析森林
  • 对包含“分割”标点的长句进行分割
  • 对分割后的各个子句分别进行句法分析(第一级分析)，各个最大概率的子树根节点的词类或短语类别标记作为第二级句法分析的输入
  • 通过第二遍分析各子句或短语之间的结构关系，从而获得整句的最大概率分析树