概率上下文无关文法(PCFG)详解

概率上下文无关文法(PCFG)详解

引用

CSDN

1.

https://blog.csdn.net/qq_64091900/article/details/144089225

概率上下文无关文法（PCFG）是自然语言处理中用于句法分析的重要工具。本文将详细介绍PCFG的基本概念、基本问题及其求解方法，帮助读者更好地理解这一理论框架及其在实际应用中的价值。

0. 关于语句法解析

1️⃣模型描述：

1. 条件：给定一个句子s及其语法G，以P(t|(s,G))概率生成分析树t，并且∑tP(t|(s,G))=1
2. 目的：找出最大化P(t|(s,G))的t，即最有可能的句法树

2️⃣与语言模型：

1. 句子概率：语言模型中句子以P(s)概率生成，若考虑句法结构则有P(s)=∑tP(s,t)
2. 最优分析：句法分词旨在最大化P(t|s)→P(s)是关于t的常数P(t|s)=P(t,s)P(s)P(s)是关于t的常数 变为直接最大化P(t,s)

1. 一些基本概念与假设

1️⃣句子结构：

2️⃣上下文无关文法(CFG)：

3️⃣句法树：用树状结构表示句子内部语法层次

4️⃣模型假设

2. 概率上下文无关文法基本问题

2.1. 问题1: 句子概率P(w1:m|G)计算

1️⃣Chomsky范式语法

1. 两种规则：

• 规则：N^i(一个非终结符)→N^jN^k(一个非终结符)，规则概率P(N^i→N^jN^k|G)
• 规则：N^i(一个非终结符)→w^j(一个终结符)，规则概率P(N^i→w^j|G)

2. 参数空间：对于空间{N^1,N^2,...,N^n,w^1,w^2,...,w^V}

• 规则数量：二元规则共n^3个，一元规则共nV个
• 规则概率：需满足∑r,sP(N^j→N^rN^s)+∑kP(N^j→w^k)=1

2️⃣句子概率P(w1:m)=∑t:yield(t)=w1mP(t)

3️⃣示例：考虑句子astronomers saw stars with ears

1. 句法树：

• t1:with ears修饰stars
• t2:with ears修饰saw

2. 规则概率：

3. 生成概率

2.2. 问题2: 最佳句法分析

1️⃣问题描述

1. 目的：找到使句子概率最大的句法树，即最优句法树
2. 形式化：

• 定义δi(p,q)：即以非终结符Ni且覆盖字句wp:q情况下，最佳解析树的概率
• 求解方法：动态规划

2️⃣类Viterbi风格的动态规划求解

1. 二元规则：δi(p,q)←Np:qi子树由Np:rj/Nr+1:qk构成maxj,k,r(P(Ni→NjNk)×δj(p,r)×δk(r+1,q))
2. 一元规则：δi(p,p)←由叶节点Np:pi直接生成wjP(Ni→wp)

2.3. 问题2: 文法训练

1️⃣Inside-Outside算法

1. 内部概率&外部概率

2. 算法公式：P(规则N→α在wp:q)=αi(p,q)×P(N→α)×∏β(子结构)×1P(w1:m)

2️⃣EM算法：优化规则的概率P(N→α)

1. E步：使用Inside-Outside算法，算出规则在未标注语料中出现次数的期望
2. M步：更新每条规则中的概率为P(N→α)=规则N→α的期望值所有以N为左部规则的期望值总和