hip*_*ail 7 algorithm nlp ambiguity data-structures ambiguous-grammar
我正在寻找专门用于处理歧义的算法或数据结构.
在我特定的当前感兴趣的领域,我正在研究对自然语言的模糊解析,但我认为在计算中必须有许多领域,其中模糊性起作用.
我可以找到很多关于试图避免模棱两可的内容,但很少关于如何接受歧义和分析模棱两可的数据.
假设解析器生成这些替代令牌流或解释:
A B1 CA B2 CA B3 B4 C可以看出,流的某些部分在解释(A... B)之间共享,而其他部分则分支到其他解释中,并且经常与主流会合.
当然,可能会有更多的解释,替代方案的嵌套以及没有主流的解释.
这显然是某种带节点的图形.我不知道它是否有确定的名称.
是否存在我可以研究的现有算法或数据结构,旨在处理这种模糊的图形？
鉴于你的问题的普遍性,我试图匹配这种普遍性.
一旦你考虑一个f: A -> B非内射的映射或函数,就会出现歧义的概念.
内射函数(也称为一对一函数)是这样的,当a≠a'时f(a) ? f(a').给定一个函数f,你通常有兴趣逆转它:给定f的codomain B的元素b,你想知道域A的元素a是这样的f(a)=b.注意,如果函数不是满射的(即上),则可能没有.
当函数不是单射的时,A中可能存在多个值a f(a)=b.换句话说,如果您使用B中的值通过映射f实际表示A中的值,则您有一个模糊的表示b,可能无法确定唯一的值.
从这一点你意识到歧义的概念是如此普遍,即使将其限制在计算机科学和编程中,也不太可能存在统一的知识体系.
但是,如果您希望考虑反转创建此类歧义的函数,例如f'(b)={a?A | f(a)=b}根据某个最优性标准计算集合或该集合中的最佳元素,则可以使用某些技术来帮助您问题可以分解为通常使用相同参数重新出现的子问题.然后,如果你记住遇到的各种参数组合的结果,你永远不会计算两次相同的东西(子问题被称为备忘录).请注意,子问题也可能存在歧义,因此某些子问题实例可能有多个答案,或者其他几个问题可能存在最佳答案.
这相当于在需要使用这组参数解决它的所有情况之间共享子问题的单个副本.整个技术称为动态编程,难以找到正确的分解为子问题.动态编程主要是一种共享解决方案的重复子计算的方法,以降低复杂性.但是,如果每个子计算产生的结构片段在较大的结构中递归地重复使用以找到作为结构化对象的答案(例如图表),则子计算步骤的共享可能导致在所有子结构中共享相应的子结构需要的地方.当要找到许多答案时(例如由于含糊不清),这些答案可以共享子部分.
可以使用动态编程来找到满足一些最优性标准的那些,而不是找到所有答案.这要求问题的最优解决方案使用子问题的最优解.
在语言学和语言处理方面,事情可以更具体.为此,您必须确定要处理的域以及与这些域一起使用的函数类型.
语言的目的是交换存在于我们大脑中的信息,概念和想法,并且非常近似地假设我们的大脑使用相同的功能来用语言表达这些想法.我还必须大大简化一些事情(对不起),因为这不完全是完整的语言理论的地方,无论如何都会有争议.我甚至不能考虑所有类型的句法理论.
因此,从人P到人Q的信息,思想的语言交换如下:
idea in P ---f--> syntactic tree ---g--> lexical sequence ---h--> sound sequence
|
s
|
V
idea in Q <--f'-- syntactic tree <--g'-- lexical sequence <--h'-- sound sequence
第一行是关于在人P中发生的句子生成,第二行是关于在人Q中发生的句子分析.该函数s代表语音传输,并且应该是身份函数.函数f',g'和h'应该是函数f,g和h的倒数,它们计算连续表示直到想法的口头表示.但是这些函数中的每一个都可能是非单射的(通常是),因此在每个级别引入歧义,使得Q难以逆转然后从它接收的声音序列中检索原始含义(我故意使用单词声音来避免深入细节).对于书面通信,相同的图表具有一些细节上的变化.
我们忽略了f和f',因为它们关注语义,这可能不太正式化,而且我没有能力.语法树通常由语法形式定义(这里我跳过重要的改进,如特征结构,但它们可以被考虑在内).
函数g和函数h通常都不是单射的,因此是模糊性的来源.由于语音链固有的各种错误,实际上存在其他歧义的来源,但我们将简单地忽略它,因为它没有太大改变问题的性质.由于句子生成或传输或者说话者和听众之间的语言规范不匹配而存在错误是一种额外的歧义来源,因为听众试图纠正潜在的错误而不知道他们可能已经存在什么或是否存在于所有.
我们假设听者不会犯错误,并且他试图根据自己的语言标准和知识(包括错误来源和统计数据的知识)来最好地"解码"句子.
给定声音序列,收听系统必须将词汇生成函数g的效果与函数g'相反.第一个探测器是几个不同的单词可以给出相同的声音序列,这是模糊性的第一个来源.第二个问题是收听系统实际上接收到对应于一串单词的序列,并且可能没有指示单词开始或结束的位置.因此,它们可以是将声音序列切割成对应于可识别单词的子序列的不同方式.当噪音在单词之间产生更多混淆时,这个问题可能会恶化.
一个例子是从网上摘录的以下全息诗,其发音或多或少相似:
Ms Stephen, without a first-rate stakeholder sum or deal,
Must, even with outer fur straight, stay colder - some ordeal.
声音序列的分析可以由有限状态非确定性自动机执行,在动态编程模式中解释,其产生有向无环图,其中节点对应于单词分离,并且边缘对于已识别的单词.通过图表的任何最长路径对应于将声音序列分析为单词序列的可能方式.
上面的例子给出了(相当简单的)字格(从左到右):
the-*-fun
/ \
Ms -*-- Stephen \ without --*-- a first -*- ...
/ \ / \ /
* * *
\ / \ / \
must --*-- even with -*- outer fur -*- ...
因此,声音序列也可以对应于以下单词序列(以及其他几个单词序列):
Ms Stephen, with outer first-rate ...
Must, even with outer first-rate ...
这使得词汇分析模糊不清.
概率可用于选择最佳序列.但也有可能保持所有可能阅读的模糊性,并在句子分析的下一阶段使用它.
请注意,单词晶格可以被视为有限状态自动机,它生成或识别单词序列的所有可能的词汇读数
句法结构通常基于无上下文语法框架.无上下文语言的模糊性问题是众所周知和分析的.已经设计了许多通用的CF解析器来解析模糊的句子,并产生可以从中提取所有解析的结构(在某种程度上变化).这种结构已被称为解析林或共享解析林.
众所周知,在语法语法被二值化的情况下,即在每个规则中右手边(或更多)不超过2个非终端的情况下,结构在分析句子的长度上可以是最坏的立方体.简单地说,每条规则右手边不超过2个符号).
实际上,所有这些通用的CF解析算法都围绕一个简单的概念或多或少复杂的变化:有限状态自动机A的语言L(A)与CF语法G的语言L(G)的交集.一个交叉点可以追溯到关于无背景语言的早期论文(Bar-Hillel,Perles和Shamir 1961),并且旨在作为封闭属性的证明.花了大约30年的时间才意识到它在1995年的论文中也是一种非常通用的解析算法 .
这种经典的交叉积结构产生了两种语言L(A)和L(G)的交集的CF语法.如果你考虑一个句子W¯¯被解析,表示为词汇元素序列,它也可以被看作是有限状态机W在所述仅生成了一句w ^.例如:
this is a finite state automaton
=> (1)------(2)----(3---(4)--------(5)-------(6)-----------((7))
是一个有限状态自动机W只接受句子 w ="这是一个有限状态自动机".所以L(W)= { w }.
如果语言的语法是G,则交叉点结构给出了一个语法G_ 瓦特的语言L(G_ 瓦特)= L(W)∩L(G).
句子w不在L(G)中,则L(G_ w)为空,并且句子不被识别.否则L(G_ w)= { w }.此外,可以容易地再证明该语法G_ 瓦特生成句子瓦特完全相同的分析树(因此相同的模糊度)作为语法G,直至所述非端子的简单的重新命名.
语法G_ W¯¯是(共享)解析森林中W¯¯,和一套分析树的W¯¯恰恰是一套与此语法推导的.因此,这给出了组织概念的简单视图,并解释了共享解析林和通用CF解析器的结构.
但还有更多内容,因为它展示了如何推广到不同的语法和不同的结构进行解析.
通过跨产品结构对常规集合的交集进行构造性闭包对于许多语法形式是常见的,这些形式主义将CF语法的功能稍微扩展到上下文敏感领域.这包括树邻接语法和线性无上下文重写系统.因此,这是如何构建这些更强大的形式主义通用解析器的指南,这些解析器可以处理歧义并生成共享解析林,它们只是相同类型的专用语法.
另一个概括是,当存在词汇歧义时,词汇分析产生许多由词格共享表示的候选句子,这个词格可以被读作识别所有这些句子的有限状态自动机.然后,相同的交集结构将消除所有不在语言中的句子(不是语法),并产生CF语法,该语法是来自单词网格的所有可接受(语法)句子的所有可能解析的共享解析林.
根据问题的要求,只要与可用的语言或话语信息兼容,就会保留所有可能的模糊读数.
噪声和不良句子的处理通常也用有限状态设备建模,因此可以通过相同的技术来解决.
实际上还有许多其他问题需要考虑.例如,有许多方法可以构建共享林,或多或少地共享.用于预编译下推自动机以用于一般上下文无关解析的技术对共享的质量有影响.太聪明并不总是很聪明.
另请参阅我在SE上就此主题所做的其他答案: