网站怎么做可以增加点击率,常州网站制作多少钱,wordpress4.9.8升级包,phpcms仿行业网站动态规划 (Dynamic Programming)
动态规划#xff08;Dynamic Programming#xff0c;简称 DP#xff09;是一种通过将问题分解为较小子问题来优化计算效率的技术。它特别适用于优化最优解问题#xff0c;比如序列标注#xff08;sequence tagging#xff09;这类任务。…动态规划 (Dynamic Programming)
动态规划Dynamic Programming简称 DP是一种通过将问题分解为较小子问题来优化计算效率的技术。它特别适用于优化最优解问题比如序列标注sequence tagging这类任务。
序列标注 (Sequence Tagging)
序列标注是自然语言处理NLP中常见的任务之一。它的目标是为输入的每个单词或者子序列分配一个标签。这个标签集通常是固定且有限的。最常见的例子是
命名实体识别NER为句子中的每个单词分配一个类别例如表示人名、地点、组织等。词性标注POS tagging为每个单词标记它的词性例如名词、动词、形容词等。
在序列标注中标签是来自一个固定的标签集合且序列长度已知且固定。
问题描述
独立预测的局限性
在许多基础的机器学习模型中每个标签都是独立预测的。这种方法存在一个问题就是 独立预测可能会导致不一致的结果。例如在词性标注任务中模型可能会错误地标记某个单词的词性但这个错误可能会影响后续预测。
贪心预测的缺点
贪心算法greedy approach逐步做出局部最优的选择但由于缺乏全局视野这种方法可能会导致全局的错误。例如贪心算法可能错误地为某个词分配了标签导致后续的标注结果不一致。
举个例子“the old man the boat”这个句子中如果我们贪心地预测每个词的标签可能会错误地预测man作为动词即“the old man [to] the boat”。但由于模型只关注当前词错误直到后续预测时才会变得明显。
动态规划在序列标注中的应用
动态规划DP是解决这类问题的有效工具。它的基本思想是通过将问题分解为子问题并存储子问题的解避免重复计算进而提高效率。在序列标注中DP通过计算每个词的标签得分以及标签之间的转移得分来有效地找到最高得分的标签序列。
序列标注模型中的得分计算
序列标注任务的模型通常会涉及两个主要部分
发射模型Emission Model表示当前单词与某个标签的关联。例如对于命名实体识别任务发射模型会计算每个单词属于某个实体类型如人名、地点等的概率。转移模型Transition Model表示从一个标签转移到另一个标签的概率。例如标签 “动词” 转移到标签 “名词” 的概率。
计算得分的步骤
初始化步骤Start State首先计算从开始状态start state到每个标签的概率通常用发射模型来计算。 p r o b 1 e / t prob1e / t prob1e/t
其中 e 是发射概率t 是转移概率。
递归计算Intermediate Scores对于每个单词基于其与当前标签的发射概率和从前一个标签到当前标签的转移概率计算所有可能路径的得分。 prob4 e × max ( t × prob pre ) \text{prob4} e \times \max(t \times \text{prob pre}) prob4e×max(t×prob pre)
其中 prob pre 是前一个状态的概率。
最终得分Final Score当所有单词都标注完成时计算最终的得分。 prob10 max ( t pre × prob pre ) \text{prob10} \max(t_{\text{pre}} \times \text{prob pre}) prob10max(tpre×prob pre)
其中 tpre 是前一个标签到当前标签的转移概率prob pre 是前一个标签的得分。
时间复杂度
O(|words| * |labels|²)对于标准的序列标注任务时间复杂度是 O(单词数×标签数^2)因为对于每个单词我们需要计算标签之间的转移概率而转移的计算需要遍历每对标签。O(|words| * |labels|³)如果我们在模型中加入了更多的标签上下文例如考虑更长的标签序列历史时间复杂度会增加到 O(单词数×标签数^3)这意味着计算量会更大。
模型的应用
这种基于动态规划的序列标注方法可以应用于不同类型的模型包括
线性模型Linear Models比如条件随机场CRF模型能够有效地处理序列标注问题。前馈神经网络Feedforward Networks可以用于对每个单词进行独立标注尽管没有考虑标签之间的转移关系。循环神经网络RNN能够在处理序列数据时保持对上下文的记忆。变换器Transformer能够捕捉全局依赖关系用于序列标注任务。
扩展提高标签上下文
如果我们希望引入更多的上下文信息例如考虑每个词的前后标签可以将模型扩展为联合模型Joint Model。这种模型将多个标签的上下文信息一起处理提高了模型的复杂性但也可能带来更好的性能。
语法解析Graph Parsing
在自然语言处理中语法解析Syntactic Parsing用于识别句子的语法结构它能够帮助我们解析一个句子的结构解决歧义问题。一句话可能有多种解释语法解析的目标是通过建立词语之间的关系树来解决这种歧义。
1. 什么是图解析Graph Parsing
在图解析中我们通过构建依存关系树dependency tree来表示句子的语法结构。这种结构通常由弧arc、边edge和依赖关系dependencies组成表示一个词语与另一个词语之间的语法关系。
头部head词语是句子的核心它决定了其他词语的语法角色。从属词dependent是依赖于头部词语的词表示与头部的语法关系。
2. 解析树的要求
为了确保生成的语法树是正确的解析算法必须满足以下几个要求
生成一棵树结果必须是一个树结构。没有交叉弧树中不能有交叉的依赖关系。有且仅有一个根树中必须有一个唯一的根节点。树有最高的得分在所有可能的树中得分最高的树是最终的解析结果。
3. 动态规划方法
图解析可以使用动态规划Dynamic Programming来高效地推导出最优的解析树。解析的过程通常基于项目items和规则rules。
项目表示在解析过程中需要构建的中间结构。规则定义如何从已有的项目中组合出新的项目。
解析过程遵循以下步骤
为每个项目定义规则逐步组合项目。保持每个项目的最佳得分对于每个步骤我们保存当前最优的解析树。
4. 图解析的过程
图解析算法通常基于如下思路
对每个项目进行分析存储最优的解析路径。最终从最顶层开始逐步向下回溯得到最优的解析树。
这个过程类似于金字塔结构从底部逐步构建解析树的各个部分最后得到完整的句子结构。
5. CKY算法Cocke-Younger-Kasami Algorithm
CKY算法是一种常用的动态规划算法它可以有效地进行语法分析。其时间复杂度为
O(∣rules_comb∣⋅∣words∣^3 ∣rules_arc∣⋅∣words∣^2)
其中|rules_comb| 是组合规则的数量|words| 是句子中单词的数量|rules_arc| 是依赖关系的数量。
6. 为什么图解析在LLM时代依然重要
虽然大规模语言模型LLM在许多自然语言处理任务中表现出色但在某些领域语法解析仍然是非常有用的尤其是在一些特定的专业领域如医疗和法律中。以下是一些原因
专业领域的需求例如医疗领域的文本通常包含复杂的术语和结构这时准确的语法解析对于理解句子至关重要。作为系统的一部分语法解析可以作为其他任务如信息抽取、机器翻译等的组成部分。它能提供更好的句法结构帮助后续任务提高准确性。LLMs的局限性尽管LLMs在处理自然语言时非常强大但在某些任务例如抽象意义表示 AMR上仍然存在挑战而图解析可以在这些任务中提供帮助。
7. 共同指代Coreference
共同指代指的是文本中多个提及相同实体的现象。例如在句子中提到“John”和“he”我们需要确定“he”是否指代“John”。
实体链接/维基化Entity Linking/Wikification将文本中的每个实体链接到外部知识库如维基百科。
共同指代的搜索空间非常庞大可能存在多种方式来将不同的提及聚类在一起。为了解决这个问题我们可以采用以下简化方法
提及检测和过滤首先检测文本中所有的提及然后筛选出可能的共同指代。链接提及对对每一对提及找到最可能的前一个提及并将它们标记为共同指代。寻找传递闭包通过逐步传递的方式建立完整的共同指代关系。
8. 简单而有效的推理算法
有时候简单的推理算法就足够解决问题。通过上述的简化方法我们可以有效地解决共同指代问题尽管这些方法看起来很基础但在许多实际应用中仍然非常有效。
