Softmax

Softmax是神經(jīng)網(wǎng)絡(luò)中常用的一種激活函數(shù)，用于多分類任務(wù)。Softmax函數(shù)將未歸一化的logits轉(zhuǎn)換為概率分布。公式如下：

$$P(y_i)=\frac{e^{z_i}}{{\sum }_{j=1}^N{e}^{z_j}}$$
其中，$z_i$是類別$i$的logit，$N$是類別總數(shù)。

在大型詞匯表情況下，計(jì)算Softmax需要對(duì)每個(gè)詞的logit進(jìn)行指數(shù)運(yùn)算并歸一化，這會(huì)導(dǎo)致計(jì)算成本隨詞匯表大小線性增長(zhǎng)。因此，當(dāng)詞匯表非常大時(shí)，計(jì)算Softmax的代價(jià)非常高。

層次Softmax

層次Softmax（Hierarchical Softmax）是一種通過(guò)樹(shù)結(jié)構(gòu)來(lái)加速Softmax計(jì)算的方法。它將詞匯表組織成一個(gè)樹(shù)結(jié)構(gòu)，每個(gè)葉節(jié)點(diǎn)代表一個(gè)詞，每個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)路徑選擇的二分類器。通過(guò)這種方式，可以將計(jì)算復(fù)雜度從O(N)降低到O(log(N))。

層次Softmax的詳細(xì)步驟

1. 構(gòu)建層次結(jié)構(gòu)：

   • 將詞匯表組織成一棵二叉樹(shù)或霍夫曼樹(shù)。霍夫曼樹(shù)可以根據(jù)詞頻來(lái)構(gòu)建，使得高頻詞的路徑更短，從而進(jìn)一步加速計(jì)算。

2. 路徑表示：

   • 對(duì)于每個(gè)詞，通過(guò)樹(shù)從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑來(lái)表示。例如，假設(shè)詞“banana”的路徑為[根 -> 右 -> 左]。

3. 路徑概率計(jì)算：

   • 每個(gè)內(nèi)部節(jié)點(diǎn)都有一個(gè)二分類器，計(jì)算左子節(jié)點(diǎn)或右子節(jié)點(diǎn)的概率。
   • 目標(biāo)詞的概率是從根節(jié)點(diǎn)到該詞的路徑上所有內(nèi)部節(jié)點(diǎn)概率的乘積。

   對(duì)于目標(biāo)詞$w$，其概率表示為：

   $$P(w|context)=\prod _{n\in path(w)}P(n|context)$$

   其中，$path(w)$表示從根節(jié)點(diǎn)到詞$w$的路徑上的所有內(nèi)部節(jié)點(diǎn)。

4. 訓(xùn)練過(guò)程：

   • 使用負(fù)對(duì)數(shù)似然損失函數(shù)進(jìn)行優(yōu)化。
   • 對(duì)于每個(gè)訓(xùn)練樣本，計(jì)算從根節(jié)點(diǎn)到目標(biāo)詞的路徑上的所有內(nèi)部節(jié)點(diǎn)的概率，并根據(jù)實(shí)際路徑更新模型參數(shù)。

對(duì)比分析

特點(diǎn)	Softmax	層次Softmax
計(jì)算復(fù)雜度	O(N)	O(log(N))
適用場(chǎng)景	小型詞匯表	大型詞匯表
實(shí)現(xiàn)復(fù)雜度	簡(jiǎn)單	復(fù)雜，需要構(gòu)建樹(shù)結(jié)構(gòu)
計(jì)算效率	隨詞匯表大小增加而增加	隨詞匯表大小增加，增長(zhǎng)較慢

為了更詳細(xì)地展示層次Softmax與傳統(tǒng)Softmax的對(duì)比，并包括實(shí)際數(shù)據(jù)和計(jì)算過(guò)程，下面我們使用一個(gè)簡(jiǎn)化的例子來(lái)說(shuō)明。

案例說(shuō)明 - 詞匯表及其層次結(jié)構(gòu)

假設(shè)我們有以下詞匯表（詞匯頻率為假定）：

詞匯	頻率
apple	7
banana	2
cherry	4
date	1

根據(jù)詞匯頻率，我們構(gòu)建如下霍夫曼樹(shù)：

       (*)/     \(apple)  (*)/ \(cherry) (*)/ \(banana) (date)

計(jì)算Softmax概率

假設(shè)在某個(gè)上下文下，模型輸出以下logits：

詞匯	Logit $z$
apple	1.5
banana	0.5
cherry	1.0
date	0.2

Softmax計(jì)算步驟：

1. 計(jì)算每個(gè)詞的指數(shù)：

$$e^{1.5}=4.4817$$
$$e^{0.5}=1.6487$$
$$e^{1.0}=2.7183$$
$$e^{0.2}=1.2214$$

2. 計(jì)算所有指數(shù)的總和：

$$Z=4.4817+1.6487+2.7183+1.2214=10.0701$$

3. 計(jì)算每個(gè)詞的概率：

$$P(apple)=\frac{4.4817}{10.0701}\approx 0.445$$
$$P(banana)=\frac{1.6487}{10.0701}\approx 0.164$$
$$P(cherry)=\frac{2.7183}{10.0701}\approx 0.270$$
$$P(date)=\frac{1.2214}{10.0701}\approx 0.121$$

計(jì)算層次Softmax概率

我們使用以下假設(shè)的特征向量和模型參數(shù)來(lái)計(jì)算每個(gè)內(nèi)部節(jié)點(diǎn)的概率：

模型參數(shù)：

• 根節(jié)點(diǎn)二分類器：
  • 權(quán)重 $w_{root}=[0.5,?0.2]$
  • 偏置 $b_{root}=0$
• 右子節(jié)點(diǎn)二分類器：
  • 權(quán)重 $w_{right}=[0.3,0.4]$
  • 偏置 $b_{right}=?0.1$
• 子樹(shù)根二分類器：
  • 權(quán)重 $w_{subtree}=[?0.4,0.2]$
  • 偏置 $b_{subtree}=0.2$

上下文特征向量：

• $x_{context}=[1,2]$

1. 計(jì)算根節(jié)點(diǎn)概率

$$z_{root}=w_{root}?x_{context}+b_{root}$$
$$z_{root}=0.5\times 1+(?0.2)\times 2+0$$
$$z_{root}=0.5?0.4$$
$$z_{root}=0.1$$

使用sigmoid函數(shù)計(jì)算概率：

$$P(left|context{)}_{root}=\sigma (z_{root})$$
$$P(left|context{)}_{root}=\frac{1}{1+e^{?0.1}}$$
$$P(left|context{)}_{root}\approx \frac{1}{1+0.9048}$$
$$P(left|context{)}_{root}\approx 0.525$$

$$P(right|context{)}_{root}=1?P(left|context{)}_{root}$$
$$P(right|context{)}_{root}=1?0.525$$
$$P(right|context{)}_{root}\approx 0.475$$

2. 計(jì)算右子節(jié)點(diǎn)概率

$$z_{right}=w_{right}?x_{context}+b_{right}$$
$$z_{right}=0.3\times 1+0.4\times 2?0.1$$
$$z_{right}=0.3+0.8?0.1$$
$$z_{right}=1.0$$

使用sigmoid函數(shù)計(jì)算概率：

$$P(left|context{)}_{right}=\sigma (z_{right})$$
$$P(left|context{)}_{right}=\frac{1}{1+e^{?1.0}}$$
$$P(left|context{)}_{right}\approx \frac{1}{1+0.3679}$$
$$P(left|context{)}_{right}\approx 0.731$$

$$P(right|context{)}_{right}=1?P(left|context{)}_{right}$$
$$P(right|context{)}_{right}=1?0.731$$
$$P(right|context{)}_{right}\approx 0.269$$

3. 計(jì)算子樹(shù)根節(jié)點(diǎn)概率

$$z_{subtree}=w_{subtree}?x_{context}+b_{subtree}$$
$$z_{subtree}=?0.4\times 1+0.2\times 2+0.2$$
$$z_{subtree}=?0.4+0.4+0.2$$
$$z_{subtree}=0.2$$

使用sigmoid函數(shù)計(jì)算概率：

$$P(left|context{)}_{subtree}=\sigma (z_{subtree})$$
$$P(left|context{)}_{subtree}=\frac{1}{1+e^{?0.2}}$$
$$P(left|context{)}_{subtree}\approx \frac{1}{1+0.8187}$$
$$P(left|context{)}_{subtree}\approx 0.55$$

$$P(right|context{)}_{subtree}=1?P(left|context{)}_{subtree}$$
$$P(right|context{)}_{subtree}=1?0.55$$
$$P(right|context{)}_{subtree}\approx 0.45$$

計(jì)算各個(gè)詞的層次Softmax概率

1. apple

路徑為[根 -> 左]

$$P(apple)=P(left|context{)}_{root}\approx 0.525$$

2. banana

路徑為[根 -> 右 -> 右 -> 左]

$$P(banana)=P(right|context{)}_{root}\times P(right|context{)}_{right}\times P(left|context{)}_{subtree}$$
$$P(banana)\approx 0.475\times 0.269\times 0.55$$
$$P(banana)\approx 0.0702$$

3. cherry

路徑為[根 -> 右 -> 左]

$$P(cherry)=P(right|context{)}_{root}\times P(left|context{)}_{right}$$
$$P(cherry)\approx 0.475\times 0.731$$
$$P(cherry)\approx 0.3472$$

4. date

路徑為[根 -> 右 -> 右 -> 右]

$$P(date)=P(right|context{)}_{root}\times P(right|context{)}_{right}\times P(right|context{)}_{subtree}$$
$$P(date)\approx 0.475\times 0.269\times 0.45$$
$$P(date)\approx 0.0575$$

概率總結(jié)

詞匯	Softmax 概率	層次Softmax 概率
apple	0.445	0.525
banana	0.164	0.0702
cherry	0.270	0.3472
date	0.121	0.0575

以上結(jié)果顯示了傳統(tǒng)Softmax和層次Softmax的概率計(jì)算方法及其結(jié)果。通過(guò)構(gòu)建霍夫曼樹(shù)，層次Softmax顯著減少了計(jì)算復(fù)雜度，特別適用于處理大規(guī)模詞匯表的任務(wù)。

Softmax與層次Softmax總結(jié)

特點(diǎn)	Softmax	層次Softmax
計(jì)算復(fù)雜度	O(N)	O(log(N))
優(yōu)點(diǎn)	簡(jiǎn)單直接，適用于小型詞匯表	計(jì)算效率高，適用于大規(guī)模詞匯表
缺點(diǎn)	計(jì)算量大，隨著詞匯表大小增加而線性增加	需要構(gòu)建和維護(hù)層次結(jié)構(gòu)，模型復(fù)雜性增加
適用場(chǎng)景	詞匯表較小的多分類問(wèn)題	詞匯表非常大的自然語(yǔ)言處理任務(wù)，如語(yǔ)言建模和機(jī)器翻譯

總結(jié)來(lái)說(shuō)，層次Softmax通過(guò)樹(shù)結(jié)構(gòu)優(yōu)化了大詞匯表的概率計(jì)算，使其在處理大型詞匯表的任務(wù)中具有顯著優(yōu)勢(shì)，而傳統(tǒng)Softmax則更適合小型詞匯表的場(chǎng)景。