NLP实践

您所在的位置：网站首页 › 反复吟唱的短语结构 › NLP实践

NLP实践

2024-07-06 00:41| 来源: 网络整理| 查看: 265

任务描述

本关任务：补充代码实现CYK算法。

相关知识

为了完成本关任务，你需要掌握：1.基于概率上下文无关文法，2.CYK算法。

基于概率上下文无关文法

PCFG（ Probabilistic Context Free Grammar ）是基于概率的短语结构分析方法，是目前研究最为充分、形式最为简单的统计句法分析模型，也可以认为是规则方法与统计方法的结合。

PCFG是上下文无关文法的扩展，是一种生成式的方法，其短语结构文法可以表示为一个五元组(X，V，S，R，P)。其具体含义为：

X 是一个有限词汇的集合（词典），它的元素称为词汇或终结符；

V 是一个有限标注的集合，称为非终结符集合；

S 称为文法的开始符号，其包含于 V，即 S∈V；

R 是有序偶对 (α，β) 的集合,也就是产生的规则集；

P 代表每个产生规则的统计概率。

当只考虑乔姆斯基范式时，规则只有两种形式：A→α，α为终结符，A→BC，B、C为非终结符

CYK算法

CYK算法即Cocke–Younger–Kasami算法，是一种上下文无关文法的句法分析算法，采用了动态规划的思想，通过合理的构造决策表减少计算复杂度。标准的CYK算法只能运用于符合乔姆斯基范式的上下文无关文法。其伪代码如下：

pi = # Initialzie the backpointers tableprobs = # Initialzie the probabilities tablefor length=2…n:for i=0…(n-length):j = i + lengthfor k=i+1…j-1:for A ∈ N:M={A|A->BC∈R and B ∈ pi[i,k] and C∈ pi[k,j]pi[i,j]=pi[i,j] union M# ---or (put probability into consideration)---pi[i,j,A] = max P(A->BC)*pi[i,k,B]*pi[k,j,C] 决策表如何构造

对一个规则A->BC：本实验中构造两张决策表，probs的数据类型为字典，其键（i,j）表示决策表的位置，其值为一个字典。此字典键为非终结符名称A，值为最大概率。 pi的整体结构与probs相同，但其值的值不是概率而是记录概率最大的规约方法。为与回溯方法（get_tree函数）相匹配，记录规约方法的形式为((非终结符名称B, 坐标, 坐标), (非终结符名称C, 坐标, 坐标))

编程要求

根据提示，在右侧编辑器补充代码，实现CYK算法

测试说明

平台会对你编写的代码进行测试：

测试输入：['friday', 'afternoon', '.'] 预期输出： ('TOP', ('NP', ('FRIDAY', 'friday'), ('AFTERNOON', 'afternoon')), ('PUN', '.'))

测试输入：['tuesday', '.'] 预期输出： ('TOP', ('NP', 'tuesday'), ('PUN', '.'))

测试输入：['what', 'about', 'after', 'seven', 'p.m', '.'] 预期输出： ('TOP', ('FRAG', ('X', ('WHAT', 'what'), ('ABOUT', 'about')), ('PP', ('AFTER', 'after'), ('NP', ('SEVEN', 'seven'), ('P.M', 'p.m')))), ('PUN', '.'))

提示： probs与pi中只需记录最大概率和最大概率对应的规约方法。

import math from grammar import Pcfg class CkyParser(object): """ A CKY parser. """ def __init__(self, grammar): """ Initialize a new parser instance from a grammar. """ self.grammar = grammar def parse_with_backpointers(self, tokens): """ Parse the input tokens and return a parse table and a probability table. """ n = len(tokens) pi = dict() # Initialzie the backpointers table probs = dict() # Initialzie the probabilities table for i in range(n + 1): for j in range(i + 1, n + 1): pi[(i, j)] = dict() probs[(i, j)] = dict() for i, word in enumerate(tokens): for key, values in self.grammar.rhs_to_rules.items(): # key: 包含终结符的一元数组，例如('friday',)，或包含两个非终结符的二元数组('FRIDAY','AFTERNOON') # values: 对给定BC，有规则A1->BC，A2->BC，则values的值为[(A1,(B,C),p1),(A2,(B,C),P2)]，对给定非终极符a，有规则A1->a，A2->a，则values的值为[(A1,(a,),p1),(A2,(a,),p2)]。p为统计得到的该规则使用的概率 if word == key[0]: for items in values: pi[(i, i + 1)][items[0]] = word probs[(i, i + 1)][items[0]] = math.log(items[2]) # 概率取对数，将乘法运算改变为加法 # for length=2…n: # for i=0…(n-length): # j = i + length # for k=i+1…j-1: # for A ∈ N: # M={A|A->BC∈R and B ∈ pi[i,k] and C∈ pi[k,j] # pi[i,j]=pi[i,j] union M # ---or (put probability into consideration)--- # pi[i,j,A] = max P(A->BC)*pi[i,k,B]*pi[k,j,C] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length for k in range(i + 1, j): for key, values in self.grammar.rhs_to_rules.items(): # 遍历推理规则的集合，确定现在观察的一对输入能否被规约 for B in pi[(i, k)]: for C in pi[(k, j)]: if key[0] == B and key[1] == C: # A->BC∈R，找到了推理规则可以规约正观察的词 for items in values: probability = math.log(items[2]) + probs[(i, k)][B] + probs[(k, j)][C] if items[0] in pi[(i, j)]: # 若在决策表的ij处已记录了一种方法 #任务：在决策表pi的ij处记录概率最大的规约方法，在表probs的ij处记录最大概率 #********** Begin **********# if probability > probs[(i, j)][items[0]]: pi[(i, j)][items[0]] = ((key[0], i, k), (key[1], k, j)) probs[(i, j)][items[0]] = probability #********** End **********# else: pi[(i, j)][items[0]] = ((key[0], i, k), (key[1], k, j)) # pi[i,j]= M probs[(i, j)][items[0]] = probability return pi, probs def get_tree(chart, i, j, nt): """ Return the parse-tree rooted in non-terminal nt and covering span i,j. """ if type(chart[(i, j)][nt]) == str: return (nt, chart[(i, j)][nt]) left_child = chart[(i, j)][nt][0] right_child = chart[(i, j)][nt][1] return (nt, (get_tree(chart, left_child[1], left_child[2], left_child[0])), (get_tree(chart, right_child[1], right_child[2], right_child[0]))) # if __name__ == "__main__": # with open('/data/workspace/myshixun/src/atis3.pcfg', 'r') as grammar_file: # grammar = Pcfg(grammar_file) # parser = CkyParser(grammar) # toks = ['flights', 'from', 'miami', 'to', 'cleveland', '.'] # table, probs = parser.parse_with_backpointers(toks) # tree = get_tree(table, 0, len(toks), grammar.startsymbol) # dynamic programming # print(tree) # ('TOP', ('NP', ('NP', 'flights'), ('NPBAR', ('PP', ('FROM', 'from'), ('NP', 'miami')), ('PP', ('TO', 'to'), ('NP', 'cleveland')))), ('PUN', '.'))

【本文地址】

NLP实践

NLP实践

今日新闻

推荐新闻