devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Neuralizing Regular Expressions for Slot Filling 流程解析

作者：羊村懒王 | 2024-06-02 19:09:39

赞

踩

neuralizing regular expressions for slot fillin

Neuralizing Regular Expressions for Slot Filling 流程解析

1. 论文简介

  神经网络模型和正则表达式等符号规则在各项任务上各有优劣。本文将正则表达式转换为神经网络，研究两种方法结合来完成槽填充任务。在zero-shot和few-shot的情况下仍有着良好的表现。

2. 对正则表达式进行预处理

  • 与普通的正则表达式不同，该方法中引入了新的符号
符号意义
$词的通配符
OO标签的通配符
<:>词的标志
  • 其余符号意义未改变

Example 1

// fromloc.city_name
$<:>OO * from $<:>B-fromloc.city_name $<:>I-fromloc.city_name ? to  $<:>OO *

  • 1
  • 2

Example 2

// aircraft_code
@aircraft_code@=(767|737|747|757|dc10|f28|72s)
$<:>OO * @aircraft_code<:>aircraft_code@ $<:>OO *

  • 1
  • 2
  • 3

处理流程

  1. 移除注释 //
  2. 移除多行运算符 \
  3. 替换变量
  4. 补全 O 标签

Example 1 parsed

$<:>OO * from<:>O $<:>B-fromloc.city_name $<:>I-fromloc.city_name ? to<:>O $<:>OO *

  • 1

Example 2 parsed

$<:>OO * ( 767<:>B-aircraft_code | 737<:>B-aircraft_code | 747<:>B-aircraft_code | 757<:>B-aircraft_code | dc10<:>B-aircraft_code | f28<:>B-aircraft_code | 72s<:>B-aircraft_code ) $<:>OO *

  • 1

3. 构建正则表达式的DFA

  • 将正则表达式转换为DFA过程分为三步
  1. 将正则表达式转换为NFA
  2. 将NFA通过“子集构造法”转化为DFA
  3. 将DFA通过“分割法”进行最小化

3.1 正则表达式转换为NFA

  • 正则表达式构建NFA规则如下图

在这里插入图片描述

Example（该例题出自Google book）

在这里插入图片描述

3.2 子集构造法

在这里插入图片描述

  • 第一列第一行Ⅰ的意思是从NFA的起始节点经过任意个ε所能到达的结点集合。Ⅰa表示从该集合开始经过一个a所能到达的集合，经过一个a的意思是可以略过前后的ε。同样Ⅰb也就是经过一个b，可以略过前后任意个ε。第二行以及后面的I则是对之前的未在Ⅰ列出现过的Ⅰa和Ⅰb进行运算。
  • 对上表中的集合进行编号，得到下表，并表示出DFA

在这里插入图片描述

DFA

在这里插入图片描述

3.3 分割法将DFA最小化

  • 最小状态DFA的含义
  1. 没有多余状态
  2. 没有相互等价状态

Example

在这里插入图片描述
1. 将Ｍ的状态分为两个子集一个由终态k1=｛Ｃ，Ｄ，Ｅ，Ｆ｝组成，一个由非终态k2=｛Ｓ，Ａ，Ｂ｝组成

2. 考察｛Ｓ，Ａ，Ｂ｝是否可分

  • 因为Ａ经过a到达C属于k1.而S经过a到达A属于k2.B经过a到达A属于k2，所以K2继续划分为{S，B},{A}

3. 考察｛Ｓ，Ｂ｝是否可再分

  • B经过b到达D属于k1.S经过b到达B属于k2，所以S，B可以划分。划分为{S},{B}

4. 考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分

  • 因为Ｃ，Ｄ，Ｅ，Ｆ经过a和b到达的状态都属于｛Ｃ，Ｄ，Ｅ，Ｆ｝=k1所以相同，所以不可再分

5. ｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝来代替，因为CDEF相同，也可以用C、E、F来代替。最小化的DFA如图：

在这里插入图片描述

3.4 文中规则转换的例子

  • 选用 2 中预处理过后的规则

Example 1

$<:>OO * from<:>O $<:>B-fromloc.city_name $<:>I-fromloc.city_name ? to<:>O $<:>OO *

  • 1
  • NFA

在这里插入图片描述

  • DFA

在这里插入图片描述

  • mDFA

在这里插入图片描述

Example 2

$<:>OO * ( 767<:>B-aircraft_code | 737<:>B-aircraft_code | 747<:>B-aircraft_code | 757<:>B-aircraft_code | dc10<:>B-aircraft_code | f28<:>B-aircraft_code | 72s<:>B-aircraft_code ) $<:>OO *

  • 1
  • NFA

在这里插入图片描述

  • DFA

在这里插入图片描述

  • mDFA

在这里插入图片描述

3.5 合并DFA并转换为i-FST

  • i-FST 指的是每个标签输出都独立于输入和源状态

FST

在这里插入图片描述

i-FST

在这里插入图片描述

  • 上述例子中的q2`状态就是新增状态，保证了输出的独立性

3.5.1 FST转换为i-FST的原因

一个有限状态自动机可以定义为一个六元组： τ = < Q , Σ , Γ , Q I , Q F , Ω > \tau = <Q, \Sigma, \Gamma, Q_I, Q_F, \Omega > τ=<Q,Σ,Γ,QI​,QF​,Ω>

  • Q Q Q: 一个有限的状态集合 ∣ Q ∣ = K |Q|=K ∣Q∣=K
  • Σ \Sigma Σ: 一个有限的输入词表 ∣ Σ ∣ = V |\Sigma|=V ∣Σ∣=V
  • Γ \Gamma Γ: 一个有限的输出词表 ∣ Γ ∣ = L |\Gamma|=L ∣Γ∣=L
  • Q I Q_I QI​: 一个有限的开始状态集合，是 Q Q Q的子集
  • Q F Q_F QF​: 一个有限的终止状态集合，是 Q Q Q的子集
  • Ω = Σ × Γ × Q × Q \Omega=\Sigma \times \Gamma \times Q \times Q Ω=Σ×Γ×Q×Q 表示所有的转移可能$
  • × \times ×: 表示笛卡尔积

于是我们可以用一个4阶的tensor： T Ω ∈ R V × L × K × K T_\Omega \in R^{V \times L \times K \times K} TΩ​∈RV×L×K×K 来表示转移权值，两个K维向量 u u u和 v v v来表示起始和终止状态的权值，权值为0/1。路径 w 1 , . . . , w m w_1,...,w_m w1​,...,wm​ 与起始状态 q i q_i qi​ 和终止状态 q j q_j qj​ 得分计算公式如下：
μ [ i ] ⋅ ( ∏ k = 1 m T Ω ( w k ) ) ⋅ v [ j ] \mu [i] · (\prod^{m}_{k=1}T_\Omega(w_k)) · v[j] μ[i]⋅(k=1∏m​TΩ​(wk​))⋅v[j]
给定一个序列 x = x 1 , . . . , x m x=x_1,...,x_m x=x1​,...,xm​ ，通过FST推理出输出标签 y = y 1 , . . . , y m y=y_1,...,y_m y=y1​,...,ym​。 y y y 的得分定义为所有匹配输入和输出的接受路径的得分和，但是直接找到一个序列的最高得分已经被证明是NP-Hard，于是采用如下算法做近似推理：

在这里插入图片描述
四阶的tensor导致了如下几个问题：

  1. 高空间复杂度 O ( V L K 2 ) O(VLK^2) O(VLK2)
  2. 高时间复杂度 O ( L K 2 ) O(LK^2) O(LK2)
  3. 张量难以分解

基于i-FST的独立性，可以改用一个3阶的tensor： T ∈ R V × K × K T \in R^{V \times K \times K} T∈RV×K×K 来表示给定输入状态直接的转换，同时用一个矩阵表示结束状态到输出标签的映射 O ∈ R K × L O \in R^{K \times L} O∈RK×L。原本的4阶tensor可以表示为： T Ω [ σ , γ , i , j ] = T [ σ , i , j ] × O [ j , γ ] T_\Omega[\sigma,\gamma,i,j]=T[\sigma,i,j] \times O[j,\gamma] TΩ​[σ,γ,i,j]=T[σ,i,j]×O[j,γ]。i-FST的近似推理算法如下：
在这里插入图片描述

4. 张量分解转换为FSTRNN

  • 采用基于张量分解的方法并且修改了Algorithm 2中的第2步和第3步。（ α t \alpha_t αt​ 和 β t \beta_t βt​ 和BiRNN中的前向和后向隐状态相似）

应用CP Decomposition（CPD）将T分解成三个矩阵 E R ∈ R V × R , D S ∈ R K × R , D E ∈ R K × R E_R \in R^{V \times R}, D_S \in R^{K \times R}, D_E \in R^{K \times R} ER​∈RV×R,DS​∈RK×R,DE​∈RK×R，R是秩（rank）一个超参数。Algorithm 2中的第5行修改成：
v t = E R [ x t ] g = ( α t − 1 ⋅ D s ∘ v t ) α t = ( g ⋅ D E T ) ∘ o T v_t=E_R[x_t] \\ \quad \\ g=(\alpha_{t-1}·D_s \circ v_t) \\ \quad \\ \alpha_t=(g·D^T_E) \circ o^T vt​=ER​[xt​]g=(αt−1​⋅Ds​∘vt​)αt​=(g⋅DET​)∘oT
E R ∈ R V × R E_R \in R^{V \times R} ER​∈RV×R 被看作是由原正则表达式导出的特殊的词嵌入矩阵。 v t v_t vt​ 则是词 x t x_t xt​ 从 E R E_R ER​ 中选出的embedding.
同样地，修改第8行为：
v t = E R [ x t ] α = ( ( β t ∘ o T ) ⋅ D E ) ∘ v t β t − 1 = ( α ⋅ D S T ) v_t=E_R[x_t] \\ \quad \\ \alpha = ((\beta_t \circ o^T)·D_E) \circ v_t \\ \quad \\ \beta_{t-1}=(\alpha·D^T_S) vt​=ER​[xt​]α=((βt​∘oT)⋅DE​)∘vt​βt−1​=(α⋅DST​)

5. 整合外部embedding

5.1 GloVE等静态词嵌入

令 E w ∈ R V × D E_w \in R^{V \times D} Ew​∈RV×D 表示要合并的词嵌入矩阵， E w [ x t ] E_w[x_t] Ew​[xt​] 则表示词 x t x_t xt​ 的 D维词向量。引入一个 D × R D \times R D×R维的可训练矩阵 G G G 将预训练词向量从D维转为R维。 G G G 初始化为 E w t E R E_w^{t}E_R Ewt​ER​， E w t E_w^t Ewt​ 是 E w E_w Ew​ 的伪逆， E w [ x t ] ⋅ G E_w[x_t]·G Ew​[xt​]⋅G 近似于 E R [ x t ] E_R[x_t] ER​[xt​]。对这两个R维向量利用超参数 η \eta η 进行插值得到新的 v t v_t vt​。
v t = η E R [ x t ] + ( 1 − η ) E w [ x t ] ⋅ G v_t=\eta E_R[x_t]+(1-\eta)E_w[x_t]·G vt​=ηER​[xt​]+(1−η)Ew​[xt​]⋅G

5.2 Bert等动态词嵌入

首先采用两种方法获得一个中间的静态词嵌入矩阵 E w ∈ R V × D E_w \in R^{V \times D} Ew​∈RV×D

  1. 集合法，由Bommasni提出
  2. 建立一个随机矩阵 E w ∼ N ( 0 , 0.5 ) E_w \sim N(0, 0.5) Ew​∼N(0,0.5) 然后将 G G G 初始化为 E w t E R E_w^{t}E_R Ewt​ER​， v t v_t vt​ 由下式可得， u t u_t ut​ 是 x t x_t xt​ 上下文词嵌入。
    v t = η E R [ x t ] + ( 1 − η ) u t ⋅ G v_t=\eta E_R[x_t]+(1-\eta)u_t·G vt​=ηER​[xt​]+(1−η)ut​⋅G

6. 模型增强方法

  • 在不损害模型近似FST的前提下增强模型
  • （不是主要流程，日后补充）

6.1 Non-linearity

6.2 Dummy States

6.3 Gated Variants

7. 解码

  • FST推理会在每个位置t上产生一个标签得分向量 c t c_t ct​

首先将每个位置的标签得分输入一个优先级层解决不同捕获组捕获同一个词的冲突问题。优先级关系由人类专家决定，表示为一组逻辑规则。我们利用MLP将这些规则应用，以 c t c_t ct​ 为输入并输出一个更新后的向量 c t c_t ct​` ∈ R L \in R^L ∈RL。
 

FSTRNN-Softmax

在解码之前，设定一个阈值 τ ∈ ( 0 , 1 ) \tau \in (0, 1) τ∈(0,1) 处理通配符 l ∘ l_\circ l∘​， l ∘ l_\circ l∘​ 代表不确定，在这种情况下输出label O。FSTRNN-Softmax解码算法如下：

在这里插入图片描述

FSTRNN-CRF

同样地，利用阈值处理通配符 l ∘ l_\circ l∘​ 。然后将标签分数作为CRF的发射分数，并用维特比算法产出输出序列。最后将通配符 l ∘ l_\circ l∘​ 换为 O。FSTRNN-CRF解码算法如下：

在这里插入图片描述

论文Github地址

RE2NN-SEQ

参考文献

Neuraling Regular Expressions for Slot Filling
NFA–>DFA

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/663983
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号