Transformer

Tokenization

考慮到計算機沒有辦法直接識別人類語言，我們將每一個詞映射為一個token使得計算機可以直接識別。
為實現(xiàn)這個目的我們使用BPE算法將每個詞劃分為若干個前綴和后綴，以此拼起來一個詞，節(jié)省vocabulary占用的空間。
這一部分寫于BPE.h

Word2Vec

現(xiàn)在我們把語言tokenize以后，我們希望得到詞匯的詞向量，以完成后續(xù)的embedding操作。
我們考慮如何處理詞向量。首先一個比較簡略的辦法是one-hot表示法，有且僅有一個元素是1，其他全部置0，然后每一個單詞的詞向量都不相同。但是這樣空間利用率不夠高，并且也沒有足夠的區(qū)分度，所以我們考慮去使用一種distributed的表示法，讓每一個維度都表示一個該詞的屬性，所有維度拼起來，就是這個詞的全部意義。

所以我們現(xiàn)在補充一下前置知識，對于機器學(xué)習(xí)，我們評估它的訓(xùn)練質(zhì)量是使用極大似然估計和損失函數(shù)來進行的。

e.g. 如果一個袋子里有若干個紅球，若干個藍(lán)球，取10次球，取到的藍(lán)球個數(shù)為\(x\)，我們得到一個結(jié)果\(E(x) = 7\)，那么我們該怎么反推單次取藍(lán)球的概率？
一個比較直觀的想法是我們?nèi)プ?span id="w0obha2h00" class="math inline">\(P(x = 7)最大\)。

也就是說，我們令\(P(x = 7) = \binom{10}{7} p^7(1-p)^3\)最大，其中\(p\)是單次取藍(lán)球的概率。

由于是指數(shù)級的，我們?nèi)?shù)\(\log P(x = 7) = \binom{10}{7}(7\log p + 3 \log (1-p))\)

令其導(dǎo)數(shù)為0，即\(7 \frac{1}{p} - 3 \frac{1}{1-p} = 0\)，得到p = 0.7

推廣一下，如果說現(xiàn)在有若干種顏色的球，也就是有若干種不同的可能性，每種可能稱為\(D_i\)，且\(D_i\)滿足伯努利分布。

那么我們考慮\(P(X) = \binom{\sum_{i=1}^{n}|D_i|}{|D_1|,|D_2|,|D_3|,...,|D_n|}\prod_{i = 1}^{n}P(D_i)\)

由于組合數(shù)是一個固定的常數(shù)，求導(dǎo)后置0的過程中與它的值無關(guān)，而且有的時候事情的發(fā)生是有順序的，不需要乘上組合數(shù)的系數(shù)，我們大可以忽略掉。

因此我們可以定義\(\log P(X) = \sum_{i = 1}^n \log (D_i) = \sum_{i = 1}^n (\log pD_i + \log(1-p) (1-D_i))\)

由于我們要令這個值最大，所以也就是使得它的負(fù)值最小，于是\(-\log p = -\sum_{i = 1}^n (\log pD_i + \log(1-p) (1-D_i))\)定義為它的交叉熵?fù)p失函數(shù)，我們訓(xùn)練的時候要最小化這個函數(shù)的值。

不過在上面的例子中我們可以直接得出來p在最大值點的取值，依舊是求導(dǎo)。

\(\sum_{i = 1}^n (D_i \frac{1}{p} - (1 - D_i) \frac{1}{1 - p})\)

化簡得：\(p = \frac{1}{n}\sum_{i = 1}^nD_i\)

另一個需要引入的概念是梯度下降法。

假設(shè)有一個目標(biāo)函數(shù)，\(F(x_1,x_2,...,x_n)\)，我們想要令這個目標(biāo)函數(shù)逐漸趨向于最大值，我們就可以設(shè)定一個參數(shù)\(\eta\)稱為學(xué)習(xí)率，我們對每一個自變量求梯度，并\(x_i := x_i + \eta\frac{\partial F}{\partial x_i}\)，最終就可以趨向于最大值。

CBOW

該模型的目的是根據(jù)上下文估算當(dāng)下詞語，學(xué)習(xí)目標(biāo)是最大化它的對數(shù)似然函數(shù)。

\(\mathcal{L} = \sum_{w \in \mathcal{C}}\log p(w|Context(w))\)

其中，\(w\)是上下文集合\(\mathcal{C}\)里的詞，\(Context(w)\)是\(w\)的上下文。

輸入層是上下文詞語的詞向量。（我們的參數(shù)并非是詞向量，我們的主要目標(biāo)是訓(xùn)練這個模型的參數(shù)，詞向量是這個模型的副產(chǎn)物，最初任何詞向量都是隨機值）

緊接著來到投影層，我們在投影層將上下文的向量加和。

最后我們得到輸出向量，并給出概率最大的候選詞。

特別地，對于輸出的向量\(y\)，我們對該向量softmax化來得到最終的概率。

\(softmax(\begin{bmatrix} p(w_i = 1|x_i,\theta) \\ p(w_i = 2|x_i,\theta) \\ ... \\ p(w_i = k|x_i, \theta) \end{bmatrix}) = \frac{1}{\sum_{i=1}^ke^{p(w_i = k|x_i,\theta)}}\begin{bmatrix} e^{p(w_i = 1|x_i,\theta)} \\ e^{p(w_i = 2|x_i,\theta)} \\ ... \\ e^{p(w_i = k|x_i, \theta)} \end{bmatrix}\)

但是我們的候選詞庫是整個語料庫，所以我們直接在\(|\mathcal{C}|\)大小的范圍內(nèi)選，無論是矩陣乘法還是最終選詞時間復(fù)雜度都是非常難以接受的。

因此我們有了別的思路，因為二類選擇問題可以推廣至n類問題，所以我們干脆建一棵哈夫曼樹，讓每一個葉子節(jié)點代表一個候選詞，然后按照從樹根到葉子節(jié)點遍歷的方式得到每一個葉子的概率。

這也就是

Hierarchical Softmax

我們引入一些敘述，\(\boldsymbol{x_w}\)表示\(w\)的上下文向量,

\(p^w\)表示從根節(jié)點到詞語\(w\)的路徑，

\(p^w_1,p^w_2,...,p^w_{|p^w|}\)表示這個路徑上的各個點，編號按照根節(jié)點到該節(jié)點進行編號。

\(d^w_2,d^w_2,...,d^w_{|p^w|} \in \{0,1\}\)表示這些點的編號，特別地，根節(jié)點沒有編號，并且，向左為\(0\)，向右為\(1\)

\(\theta^w_{2},\theta^w_{3},...,\theta^w_{|p^w|}\)表示這些點的參數(shù)向量。

于是根據(jù)條件概率，\(p(w|Context(w)) = \prod_{i=2}^{|p^w|} p(p^w_i|\boldsymbol{x}_w ,\theta^w_i)\)

特別地，\(p(p^w_i) = \left\{\begin{aligned} \sigma(\boldsymbol{x_w}\cdot \theta^w_i), & d^w_i = 1 \\ 1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i), & d^w_i = 0 \end{aligned}\right.\)，其中\(\sigma(x)\)是sigmoid函數(shù)，是softmax的二元形式。

那么就有\(p(p^w_i) = \sigma(\boldsymbol{x_w}\cdot \theta^w_i)^{d^w_i}( 1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i))^{1 - d^w_i}\)

將他們都乘起來\(p(w|Context(w)) = \prod_{i=2}^{|p_w|}p(p^w_i) = \prod_{i=2}^{|p^w|}\sigma(\boldsymbol{x_w}\cdot \theta^w_i)^{d^w_i}( 1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i))^{1 - d^w_i}\)

取對數(shù)，\(\log p(w|Context(w)) = \sum_{i = 2}^{|p^w|}(d^w_i \log(\sigma(\boldsymbol{x_w}\cdot \theta^w_i)) + (1 - d^w_i) \log(1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i)))\)

\(\sigma(x) = \frac{1}{1 + e^{-x}}\)

求導(dǎo)，\(\sigma'(x) = \frac{e^{-x}}{1 + 2e^{-x} + e^{-2x}} = \frac{1}{e^x + 2 + e^{-x}}\)

\(e^{-x} = \frac{1 - \sigma(x)}{\sigma(x)}\)，帶入上式，\(LHS = \frac{1}{\frac{\sigma(x)}{1 - \sigma(x)} + 2 + \frac{1 - \sigma(x)}{\sigma(x)}} = \frac{\sigma(x) - \sigma(x)^2}{\sigma(x)^2 + 2\sigma(x) - 2\sigma(x)^2 + 1 - 2\sigma(x) + \sigma(x)^2} = \sigma(x)(1 - \sigma(x))\)

所以回到取對數(shù)的環(huán)節(jié)，原式求導(dǎo)\(\frac{\partial \log p}{\partial \theta^w_i} = d^w_i \boldsymbol{x_w} \sigma(\boldsymbol{x_w}\cdot \theta^w_i)(1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i)) \frac{1}{\sigma(\boldsymbol{x_w}\cdot \theta^w_i)} - (1 - d^w_i) \boldsymbol{x_w}\sigma(1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i))\sigma(\boldsymbol{x_w}\cdot \theta^w_i) \frac{1}{1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i)} = d^w_i\boldsymbol{x_w}(1 - \sigma(\boldsymbol{x_w}\cdot \theta^w_i)) - (1 - d^w_i)\boldsymbol{x_w}\sigma(\boldsymbol{x_w}\cdot \theta^w_i) = (d^w_i - \sigma(\boldsymbol{x_w}\cdot \theta^w_i) - 1)\boldsymbol{x_w}\)

我們觀察到\(\theta^w_i\)和\(\boldsymbol{x_w}\)是輪換對稱的，所以\(\frac{\partial \log p}{\partial \boldsymbol{x_w}} = (d^w_i - \sigma(\boldsymbol{x_w}\cdot \theta^w_i) - 1)\theta^w_i\)

每次學(xué)習(xí)后，我們只需要\(\theta^w_i := \theta^w_i + \eta (d^w_i - \sigma(\boldsymbol{x_w}\cdot \theta^w_i) - 1)\boldsymbol{x_w}\)，\(\boldsymbol{x} := \boldsymbol{x} + (d^w_i - \sigma(\boldsymbol{x_w}\cdot \theta^w_i) - 1)\theta^w_i\)即可。

問題在于，\(\boldsymbol{x_w}\)是一個整體，是若干個詞向量的向量之和，所以我們均攤一下對于每一個詞的影響即可。

但是這只是單個詞向量的情況，我們的Transformer模型中，每一個詞對應(yīng)三個詞向量\(Q,K,V\)，分別代表Query,Key,Value

具體來講，我們遇到一個詞，想到這個詞會聯(lián)系到什么詞就會調(diào)用\(Q\)向量，去跟其他詞的\(K\)向量做向量點乘，然后得出跟每一個詞的概率，然后加權(quán)地將其他詞的影響加到這個詞身上，權(quán)重是概率，影響是說其他詞的V。

具體來說，有\(Attention(Q,K,V) = Softmax(\frac{Q\cdot K^T}{\sqrt{d_k}}) V\)

我們具體來看這個式子的右邊，第一步是矩陣乘法和系數(shù)除法，即\(\frac{1}{\sqrt{d_k}}\left(\begin{bmatrix}Q_{1,1},Q_{1,2},...,Q_{1,k} \\ Q_{2,1},Q_{2,2},...,Q_{2,k} \\ ... \\ Q_{n,1},Q_{n,2},...,Q_{n,k} \end{bmatrix} \cdot \begin{bmatrix}K_{1,1},K_{1,2},...,K_{1,n} \\ K_{2,1},K_{2,2},...,K_{2,n} \\ ... \\ K_{k,1},K_{k,2},...,K_{k,n} \end{bmatrix}\right)\)，其中\(\begin{bmatrix}Q_{i,1},Q_{i,2},...,Q_{i,k} \end{bmatrix}\)代表token編號為\(i\)的詞的\(Q\)向量，\(\begin{bmatrix}K_{1,i} \\ K_{2,i} \\ ... \\ K_{k,i} \end{bmatrix}\)是token編號為\(i\)的詞的\(K\)向量的轉(zhuǎn)置，詞匯庫總數(shù)是\(n\)，詞向量維度為\(k\)。

得到的結(jié)果是\(\begin{bmatrix}\frac{Q_1 \cdot K_1}{\sqrt{d_k}}, \frac{Q_1 \cdot K_2}{\sqrt{d_k}},..., \frac{Q_1 \cdot K_n}{\sqrt{d_k}} \\ \frac{Q_2 \cdot K_1}{\sqrt{d_k}}, \frac{Q_2 \cdot K_2}{\sqrt{d_k}}, ... , \frac{Q_2 \cdot K_n}{\sqrt{d_k}} \\ ... \\ \frac{Q_n \cdot K_1}{\sqrt{d_k}}, \frac{Q_n \cdot K_2}{\sqrt{d_k}}, ... , \frac{Q_n \cdot K_n}{\sqrt{d_k}} \end{bmatrix}\)

下一步是對每一行Softmax，也就是對于同一個\(Q_i\)，跟所有\(K_j\)點乘后得到的概率分布相加是\(1\)。

\(\begin{bmatrix}\frac{e^{\frac{Q_1 \cdot K_1}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_1 \cdot K_j}{\sqrt{d_k}}}}, \frac{e^{\frac{Q_1 \cdot K_2}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_1 \cdot K_j}{\sqrt{d_k}}}},..., \frac{e^{\frac{Q_1 \cdot K_n}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_1 \cdot K_j}{\sqrt{d_k}}}} \\ \frac{e^{\frac{Q_2 \cdot K_1}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_2 \cdot K_j}{\sqrt{d_k}}}}, \frac{e^{\frac{Q_2 \cdot K_2}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_2 \cdot K_j}{\sqrt{d_k}}}},..., \frac{e^{\frac{Q_2 \cdot K_n}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_2 \cdot K_j}{\sqrt{d_k}}}} \\ ... \\ \frac{e^{\frac{Q_n \cdot K_1}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_n \cdot K_j}{\sqrt{d_k}}}}, \frac{e^{\frac{Q_n \cdot K_2}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_n \cdot K_j}{\sqrt{d_k}}}},..., \frac{e^{\frac{Q_n \cdot K_n}{\sqrt{d_k}}}}{\sum_{j = 1}^ne^{\frac{Q_n \cdot K_j}{\sqrt{d_k}}}} \end{bmatrix}\)

我們不妨簡記\(\frac{e^{\frac{Q_i \cdot K_j}{\sqrt{d_k}}}}{\sum_{l = 1}^ne^{\frac{Q_i \cdot Q_l}{\sqrt{d_k}}}} = p(i,j)\)代表上下文是\(i\)時，候選詞是\(j\)的概率。

最后我們得到一個概率矩陣，然后對于一個固定的\(i\)，我們根據(jù)概率作為權(quán)重去求它的加權(quán)平均數(shù)來得到它的候選詞\(y\)的詞向量\(V'_i\)，即\(\begin{bmatrix}V'_1,V'_2,...,V'_k\end{bmatrix} = \begin{bmatrix}\sum_{j=1}^np(i,j)V_{j,1},\sum_{j=1}^np(i,j)V_{j,2},...,\sum_{j=1}^np(i,j)V_{j,k}\end{bmatrix}\)

容易發(fā)現(xiàn)這就是矩陣乘法的形式。

所以也就是\(\begin{bmatrix}V'_{1,1},V'_{1,2},...,V'_{1,k} \\ V'_{2,1},V'_{2,2},...,V'_{2,k} \\ ... \\ V'_{n,1},V'_{n,2},...,V'_{n,k} \end{bmatrix} = \begin{bmatrix}p(1,1),p(1,2),...,p(1,n) \\ p(2,1),p(2,2),...,p(2,n) \\ ... \\ p(n,1),p(n,2),...,p(n,n) \end{bmatrix} \cdot \begin{bmatrix}V_{1,1},V_{1,2},...,V_{1,n} \\ V_{2,1},V_{2,2},...,V_{2,n} \\ ... \\ V_{n,1},V_{n,2},...,V_{n,n} \end{bmatrix}\)

然后我們就得到了每一個候選詞的詞向量\(V\)。通過跟詞庫里的詞\(V\)比對就可以找到概率最大的。