Candidate sampling：NCE loss和negative sample

在工作中用到了類似于negative sample的方法，才發現我其實并不了解candidate sampling。于是看了一些相關資料，在此簡單總結一些相關內容。

主要內容來自tensorflow的candidate_sampling和卡耐基梅隆大學一個學生寫的一份notesNotes on Noise Contrastive Estimation and Negative Sampling，還有一部分參考了tensorflow的nce_loss和sampled_softmax_loss的文檔。

What is Candidate Sampling

首先，什么是candidate sampling呢？假設我們有這樣一個問題，給定一個樣本集，其中每個樣本由 $(x_i, T_i)$ ，其中 $x_i$ 是輸入特征， $T_i$ 是一個target小集合，滿足 $T \subset L, |T| << |L|$ 。我們的目標是學習一個 $F(x, y)$ ，使得給定一個 $x$ ，我們可以預測出類別 $y$ 為正的可能性。

如果我們使用正常的softmax方法，那么在計算每一個sample時，我們都需要遍歷整個集合 $|L|$ ，對每一個可能的 $y$ 計算一次 $F(x, y)$ ，這是非常昂貴的操作。尤其是在NLP的相關預測中，這一操作代價更加高昂。所以candidate sampling的方法被提了出來：在計算每一個sample時，我們從整個標簽集合或者負標簽集合中隨機采樣出一個小的candidate集合 $S$ ，將 $S$ 和 $T$ 一起組成當前的candidate集合 $C = S \cup T$ ，并在 $C$ 上計算 $F(x, y)$ 。

常見的candidate sampling方法的特性可以見下表：

在這個表中， $K(x)$ 是一個不依賴于候選類的任意函數。由于Softmax涉及歸一化，因此添加這樣的函數不會影響計算的概率。 $Q(y|x)$ 是 $S_i$ 中類y的期望概率或者期望個數。

NCE和nagetive sample可以適應于 $T_i$ 是multiset的情況，在這種情況下， $P(y|x)$ 等于 $T_i$ 中類y的期望個數。NCE，negative sampling和sampled logistic可以適應于 $S_i$ 是multiset的情況，在這種情況下， $Q(y|x)$ 等于 $S_i$ 中類y的期望個數。

Noise Contrastive Estimation (NCE)

我們考慮一種簡單的也是最常用的情況， $|T| = 1$ 。以經典的word預測為例，此時 $T= {t_i}$ 。我們給定經驗分布 $\widetilde{P}(x)$ 和 $\widetilde{P}(t|x)$ ，則每一個訓練集中的正樣本都相當于從 $\widetilde{P}(x)$ 采樣出一個 $x_i$ ，并在這個 $x$ 的基礎上在 $\widetilde{P}(t|x)$ 上采樣出 $t_i$ ，并標定label $d = 1$ 。同時我們從分布 $Q(x)$ 中采樣出 $k$ 個noise samples，則

P(d, t|x)= \begin{cases} \frac{k}{1 + k}Q(x) & \text{d=0}\\ \frac{1}{1 + k}\widetilde{P}(t|x)& \text{d=1} \end{cases}

那么使用條件概率公式，我們就可以寫出:

$P(d = 0| t, x) = \frac{k * Q(x)}{\widetilde{P}(t|x) + k * Q(x)}$

$P(d = 1| t, x) = \frac{\widetilde{P}(t|x)}{\widetilde{P}(t|x) + k * Q(x)}$

在神經網絡算法中，我們使用 $P_\theta(t,x)$ 來代替 $\widetilde{P}(t|x)$ ，并試圖用梯度下降法來訓練 $\theta$ 。

Negative Sampling

Negative Sampling是NCE的一種近似，比較值得注意的是，negative sampling對于分布Q有強依賴，NCE則沒有這個問題。

tensorflow實現

NCE loss在tensorflow中的文檔可以參考tf.nn.nce_loss。要注意的是，使用這種方法時，標簽必須按照frequency的降序排序，因為默認的采樣方法是tf.nn.log_uniform_candidate_sampler。當然我們也可以實現自己的采樣方法。

Negative sampling則用sampled_softmax_loss來實現，注意sampled_softmax_loss只能處理一個正label的情況。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/388997.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/388997.shtml
英文地址，請注明出處：http://en.pswp.cn/news/388997.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！