在Word2Vec原理詳解中介紹了詞嵌入吊趾，跳字模型的核心在于使用softmax運算得到給定中心詞 $w_c$ 來生成背景詞 $w_o$ 的條件概率

$P(w_o|w_c)=\frac{{\rm exp}(\boldsymbol u_o^{\top} \boldsymbol v_c)}{\sum_{i \in \mathcal{V}} {\rm exp}(\boldsymbol u_i^{\top} \boldsymbol v_c)}$

該條件概率相應的對數(shù)損失

$- {\rm log} P(w_o|w_c)= - \boldsymbol u_o^{\top} \boldsymbol v_c + {\rm log} \Big( \sum_{i \in \mathcal{V}} {\rm exp}(\boldsymbol u_i^{\top} \boldsymbol v_c) \Big)$

由于softmax運算考慮了背景詞可能是詞典 $\mathcal{V}$ 中的任一詞澳腹，以上損失包含了詞典大小數(shù)目的項的累加肢预。任何的更新或者對目標函數(shù)的評估都要花費 $O(|\mathcal{V}|)$ 的時間復雜度。一個簡單的想法是不去直接計算润绎，而是去求近似值真椿。

Mikolov 在論文《Distributed Representations of Words and Phrases and their Compositionality》中提出了負采樣和層級softmax丽声，這是兩種有效的近似訓練方法。

1. 負采樣（Negative Sampling）

負采樣修改了原來的目標函數(shù)壤短。給定中心詞 $w$ 的一個背景窗口设拟，我們把背景詞 $c$ 出現(xiàn)在該背景窗口看作一個事件，并將該事件的概率計算為

$P(D=1|w, c,\theta) = \sigma (\boldsymbol v_c^{\top} \boldsymbol v_w)=\frac{1}{1+e^{(-\boldsymbol v_c^{\top} \boldsymbol v_w)}}$

我們先考慮最大化文本序列中所有該事件的聯(lián)合概率來訓練詞向量久脯。負采樣通過采樣并添加負類樣本使目標函數(shù)更有意義纳胧。考慮最大化聯(lián)合概率 $P(D=1|w,c)$ 帘撰，如果中心詞和上下文詞確實不在語料庫中跑慕，就最大化概率 $P(D=0|w,c)$ 。我們對這兩個概率采用一個簡單的極大似然估計的方法（這里我們把 $\theta$ 作為模型的參數(shù)，在例子中是 $\mathcal{V}$ 和 $\mathcal{U}$ 核行。

$\begin{align} \theta &= \mathop{\arg\max}_{\theta} \prod_{(w,c) \in D} P(D=1|w,c,\theta) \prod_{(w,c) \in \widetilde{D}}P(D=0|w,c,\theta) \\ &= \mathop{\arg\max}_{\theta} \prod_{(w,c) \in D} P(D=1|w,c,\theta) \prod_{(w,c) \in \widetilde{D}}\left(1-P(D=1|w,c,\theta)\right) \\ &= \mathop{\arg\max}_{\theta} \sum_{(w,c) \in D} {\rm log} P(D=1|w,c,\theta) \sum_{(w,c) \in \widetilde{D}}{\rm log}\left(1-P(D=1|w,c,\theta)\right) \\ &= \mathop{\arg\max}_{\theta} \sum_{(w,c) \in D} {\rm log} \frac{1}{1+e^{(-\boldsymbol u_w^{\top} \boldsymbol v_c)}} \sum_{(w,c) \in \widetilde{D}}{\rm log}\left(1-\frac{1}{1+e^{(-\boldsymbol u_w^{\top} \boldsymbol v_c)}}\right) \\ &= \mathop{\arg\max}_{\theta} \sum_{(w,c) \in D} {\rm log} \frac{1}{1+e^{(-\boldsymbol u_w^{\top} \boldsymbol v_c)}} \sum_{(w,c) \in \widetilde{D}}{\rm log}\left(\frac{1}{1+e^{(\boldsymbol u_w^{\top} \boldsymbol v_c)}}\right) \end{align}$

最大化似然函數(shù)等同于最小化負對數(shù)似然：

$J = - \sum_{(w,c) \in D} {\rm log} \frac{1}{1+e^{(-\boldsymbol u_w^{\top} \boldsymbol v_c)}} - \sum_{(w,c) \in \widetilde{D}}{\rm log}\left(\frac{1}{1+e^{(\boldsymbol u_w^{\top} \boldsymbol v_c)}}\right)$

其中 $\widetilde{D}$ 表示“假的”或者“負的”語料牢硅。

對于 Skip-Gram 模型，我們對給定中心詞 $c$ 來觀察的上下文單詞 $c-m+j$ 的新目標函數(shù)為

$-{\rm log} \sigma \left(\boldsymbol u_{c-m+j}^{\top} \cdot \boldsymbol v_c\right)-\sum_{k=1}^K {\rm log} \sigma \left( - \tilde {\boldsymbol u}_k^{\top} \cdot \boldsymbol v_c \right)$

對 CBOW 模型芝雪，我們對給定上下文向量 $\hat{v}=\scriptstyle{\frac{v_{c-m} + v_{c-m+1} + ... + v_{c+m}}{2m}}$ 來觀察中心詞 $\boldsymbol u_c$ 的新的目標函數(shù)為

$-{\rm log} \sigma \left( \boldsymbol u_c^{\top} \cdot \hat{\boldsymbol v} \right) - \sum_{k=1}^K {\rm log} \sigma \left( - \tilde {\boldsymbol u}_k^{\top} \cdot \hat{\boldsymbol v} \right)$

在上面的公式中减余， $\{ \tilde {\boldsymbol u}_k | k=1...K \}$ 是從 $P_{n}(w)$ 中抽樣。

現(xiàn)在惩系，訓練中每一步的梯度計算開銷不再與詞典大小相關位岔，而與 $K$ 線性相關。當 $K$ 取較小的常數(shù)時堡牡，負采樣在每一步的梯度計算開銷較小赃承。

層序Softmax （Hierarchical Softmax）

層序softmax是另一種近似訓練法，相比普通的 softmax 這是一種更有效的替代方法悴侵。在實際中瞧剖，hierarchical softmax 對低頻詞往往表現(xiàn)得更好，負采樣對高頻詞和較低維度向量表現(xiàn)得更好可免。它使用了二叉樹這一數(shù)據(jù)結構抓于，樹的每個葉結點代表詞典 $\mathcal V$ 中的每個詞。

層序softmax

假設 $L(w)$ 為從二叉樹的根結點到詞 $w$ 的葉結點的路徑（包括根結點和葉結點）上的結點數(shù)浇借，以上圖為例捉撮， $L(w_3)=4$ 。設 $n(w,j)$ 為該路徑上第 $j$ 個結點妇垢，并設該結點的背景詞向量為 $v_{n(w,j)}$ 巾遭。因此 $n(w,1)$ 是根結點，而 $n(w,L(w))$ 是 $w$ 的父結點〈彻溃現(xiàn)在對每個內部結點 $n$ 灼舍，我們任意選取一個它的子節(jié)點，定義為 $ch(n)$ （一般是左結點）涨薪。層序softmax將跳字模型中的條件概率近似表示為

$P(w|w_i) = \prod_{j=1}^{L(w)-1} \sigma \left( \left[ n(w,j+1)=ch(n(w,j)) \right] \cdot \boldsymbol v_{n(w,j)}^{\top} \boldsymbol v_{w_i} \right)$

其中

$[x]=\begin{cases} 1 \quad &{\rm if} \: x \: {\rm is} \: {\rm true} \\ -1 &{\rm otherwise} \end{cases}$

首先骑素，我們將根據(jù)從根節(jié)點 $n(w,1)$ 到葉結點 $(w)$ 的路徑的形狀來計算相乘的項。如果我們假設 $ch(n)$ 一直都是 $n$ 的左節(jié)點刚夺，然后當路徑往左時 $[n(w,j+1)=ch(n(w,j))]$ 的值返回 1献丑，往右則返回 -1。

此外侠姑， $[n(w,j+1)=ch(n(w,j))]$ 提供了歸一化的作用创橄。在節(jié)點 $n$ 處，如果我們將去往左和右節(jié)點的概率相加莽红，對于 $\boldsymbol v_n^{\top} \boldsymbol v_{w_i}$ 的任何值則可以檢查妥畏，

$\sigma (\boldsymbol v_n^{\top} \boldsymbol v_{w_i}) + \sigma (- \boldsymbol v_n^{\top} \boldsymbol v_{w_i}) = 1$

歸一化也保證了 $\scriptstyle{\sum_{w=1}^{\mathcal V} P(w|w_i) =1}$ ，和在普通的 softmax 是一樣的。

最后我們計算點積來比較輸入向量 $\boldsymbol v_{w_i}$ 對每個內部節(jié)點向量 $\boldsymbol v_{n(w,j)}^{\top}$ 的相似度咖熟。下面我們給出一個例子圃酵。以上圖中的 $w_2$ 為例，從根節(jié)點要經(jīng)過兩次左邊的邊和一次右邊的邊才到達 $w_2$ 馍管，因此

$\begin{align} P(w_2|w_i) &= P(n(w_2,1),{\rm left}) \cdot P(n(w_2,2),{\rm left}) \cdot P(n(w_2,3),{\rm right}) \\ &= \sigma \left( {\boldsymbol v}_{n(w_2,1)}^{\top} \boldsymbol v_{w_i} \right) \cdot \sigma \left( {\boldsymbol v}_{n(w_2,2)}^{\top} \boldsymbol v_{w_i} \right) \cdot \sigma \left( {- \boldsymbol v}_{n(w_2,3)}^{\top} \boldsymbol v_{w_i} \right) \end{align}$

我們訓練模型的目標是最小化負的對數(shù)似然 $-{\rm log} P(w|w_i)$ 郭赐，不是更新每個詞的輸出向量，而是更新二叉樹中從根結點到葉結點的路徑上的節(jié)點的向量确沸。

此外捌锭，由于 $L(w_o)?1$ 的數(shù)量級為 $O(log_2|\mathcal V|)$ ，當詞典 $\mathcal V$ 很大時罗捎，層序softmax在訓練中每一步的梯度計算開銷相較未使用近似訓練時大幅降低观谦。

該方法的速度由構建二叉樹的方式確定，并將詞分配給葉節(jié)點桨菜。Mikolov 在論文《Distributed Representations of Words and Phrases and their Compositionality》中使用的是哈夫曼樹豁状，在樹中分配高頻詞到較短的路徑。

Word2Vec近似訓練原理

Word2Vec近似訓練原理

1. 負采樣（Negative Sampling）

層序Softmax （Hierarchical Softmax）

Word2Vec近似訓練原理

1. 負采樣 （Negative Sampling）

層序Softmax （Hierarchical Softmax）

1. 負采樣（Negative Sampling）