---
###### tags: `nlp`
---

# Automated Concatenation of Embeddings for Structured Prediction
acl2021
https://aclanthology.org/2021.acl-long.206/
+ 把一堆 embedding 串一起然後輸入 LSTM 來分類 NER label，取得 SOTA 成績
+ 但用了**一大堆模型** 的 embedding，感覺只是用來拚榜而已

# Introduction
+ word embeddings 對於下游任務影響很深，像是 ELMO, Flair, BERT, XLM-R 都取得了 SOTA 成績，而 **embedding 的串接**也能產生更好的效果
+ Neural architecture search (NAS) 是一種能自動尋找最好模型架構 (排列組合) 的方法，並且在 image classification / semantic segmentation / object detection 任務都有背應用上
+ [Neural architecture search 介紹](https://medium.com/ai-academy-taiwan/%E6%8F%90%E7%85%89%E5%86%8D%E6%8F%90%E7%85%89%E6%BF%83%E7%B8%AE%E5%86%8D%E6%BF%83%E7%B8%AE-neural-architecture-search-%E4%BB%8B%E7%B4%B9-ef366ffdc818)



+ 結合以上想法，本文提出 **Automated Concatenation of Embeddings** 來找出最好的 word embedding 串接方式，策略為去優化 **reinforcement learning** 架構中的 controller，並在 6 tasks and 21 dataset 上取得了 SOTA 成績

+ 在每次的 STEP 中，controller 根據 belief model 選出 word embedding 串接方式，用這些參數訓練完模型後取得 accuracy 當作 reward，並去更新 belief model
+ 專注在挑選 embedding 串接方式
+ 新穎的 controller 設計和 reward function
+ efficient and practical(實際的)

# Task model


我們的任務為給定 $x$ ，輸出每個 $y$ 類別的機率 (其實就是 softmax 分類)


任務模型有兩種，一種是基於 sequence，另一種基於 graph

**Sequence**
+ BiLSTM-CRF model
+ Xuezhe Ma and Eduard Hovy. 2016. End-to-end sequence labeling via bi-directional LSTM-CNNsCRF

**Graph**
+ BiLSTM-Biaffine
+ Timothy Dozat and Christopher D. Manning. 2018. Simpler but more accurate semantic dependency parsing

輸入 n 個字，在經過 $L$ 個模型 embedd 後的詞向量序列為$V$
+ d 為所有模型 hidden size 加總
+ $v_i^l$ 代表由第$l$ 個模型產生的第 $i$ 個字的 embedding，
+ $v_i$ 是由多個模型的第 $i$ 個字串接而成
$$
V = [v_1; \cdots ;V_n], V \in \mathbb{R}^{d \times n} \\
v^l_i = embed^l_i(x); \ v_i = [v^1_i;v^2_i;\cdots v^L_i]
$$

在給予輸入$x$ 後產生 $y$ 的機率
$$
P^{seq}(y|x) = BiLSTM-CRF(V,y) \\
P^{graph}(y|x) = BiLSTM-Biaffine(V,y)
$$

digraph structs {
    rankdir=LR
    node [shape=record];
    struct1 [label="<f0> v1^1|<f1> v1^2 |<f2> v1^3"];
    struct2 [label="<f0> v2^1|<f1> v2^2 |<f2> v2^3"];
    struct3 [label="<f0> v3^1|<f1> v3^2 |<f2> v3^3"];
    struct1:f0 -> struct2:f0-> struct3:f0;
    label = "V=[v1;...;Vn]"
}

**Search Space Design**

+ L 個模型所能組成的 embeddings 有 $2^L$ 種
+ binary variable $a^i$ 能控制 embedding 要不要被選用，類似 mask 的概念
$$
v_i = [v^1_ia_1; \cdots ; v^l_ia_l ; v^L_ia_L ]
$$

**Searching in the Space**

+ 我們用參數 $\theta = [\theta_1; \theta_2; \cdots ; \theta_L ]$ 來當作 controller 變數
+ $P(a;\theta)$ 代表在給定變數 $\theta$ 下產生 $a$ 的機率
+ 選擇 concatenation $a$ 的機率分佈 ($\prod$為連乘)

$$
P^{ctrl}(a;\theta) = \prod ^{L}_{l=1} P^{ctrl}_l(a_l;\theta_l)
$$

+ $P^{ctrl}_l$ 為 Bernoulli distribution，σ is the **sigmoid function**
<img src="https://i.imgur.com/TTCZQeH.png" alt="drawing" width="40%" style="right"/>

直觀解釋: 假設我們用了 ELMO 和 BERT，用 $\theta_1$ 控制選擇 ELMO 的機率，用 $\theta_2$ 控制選擇 ELMO 的機率。啟用 ELMO embedding ($a_1=1$) 的機率為 $\sigma(\theta_1)$，不啟用的機率為 $1-\sigma(\theta_1)$

**Train loop**

在訓練過程中，先選擇好 mask，接著依照這個 mask 去訓練模型，並在 development set 上測試得到 ==accuracy R== 當作 reward

由於 R 不能微分計算 gradient，因此根據 **policy gradient method**，controller 的目標為最大化

$$
J(\theta) = \mathbb{E}_{P^{ctrl}}(a;\theta)[R]
$$

為了訓練效率的提升，一次只選擇**一種** $\theta$ 來去計算，而不是把所有的 $\theta$ 可能性都嘗試

+ $b$ 是 baseline function (通常選擇最高的 accuracy)

$$
\nabla_\theta J(\theta) \approx \sum^{L}_{l=1} \nabla_\theta log P^{ctrl}_l (a_l;\theta_l)(R-b)
$$

**Reward**
用 binary vector $|a^t-a^i|$ 來代表 embedding 選擇的變化
+ $a^t$ 是在 time step $t$ 的 embedding 選擇
+ $a^i$ 是在 time step $i$ 的 embedding 選擇
+ $r^t$ 是長度為 $L$ 的 vector，表示了每個 embedding 得到的 reward
$$
r^t = \sum^{t-1}_{i=1}(R_t-R_i)|a^t-a^i|
$$

在以上的基礎，考慮到越遠的 timestep **影響力應該要更小**，因此加入縮放因子 $\gamma \in (0,1)$

$$
r^t = \sum^{t-1}_{i=1} (R_t-R_i) \gamma^{Hamm(a_t-a_i)-1}|a^t-a^i|
$$
重寫式子
$$
\nabla_\theta J_t(\theta) \approx \sum^{L}_{l=1} \nabla_\theta log P^{ctrl}_l (a^t_l;\theta_l) r^t_l
$$

# Training
用字典 $D$ 來存 **串接方式**和**驗證分數**的對應

在 t=1 時候，所有的 embedding 都啟用

t >= 2
1. sample $a^t$
2. 依照 $a^t$ 訓練 task model ，得到 accuracy R
3. 把 $a^t$ 和 $R_t$ 加入 $D$， 讓 t = t+1

+ 在選擇 $a^t$ 時，避免選擇 $a^{t-1}$ 和**全零**的 vector
+ 當 $a^t$ 存在於字典，替換為更高的 R

# embeddings
用超多的
+ ELMo
+ Flair
+ base BERT
+ GloVe word embeddings
+ fastText word embeddings
+ noncontextual character embeddings (Lample et al.,2016)
+ multilingua Flair (M-Flair)
+ M-BERT
+ XLM-R embeddings.

# Result