文 | 徐瀾玲
源 | RUC AI Box

引言：負(fù)采樣方法最初是被用于加速 Skip-Gram 模型的訓(xùn)練，后來被廣泛應(yīng)用于自然語言處理 (NLP)、計(jì)算機(jī)視覺 (CV) 和推薦系統(tǒng) (RS) 等領(lǐng)域，在近兩年的對比學(xué)習(xí)研究中也發(fā)揮了重要作用。本文聚焦于負(fù)采樣方法，將各領(lǐng)域的相關(guān)工作分為五類進(jìn)行介紹：靜態(tài)負(fù)采樣、強(qiáng)負(fù)例采樣、對抗式負(fù)采樣、基于圖的負(fù)采樣和引入額外信息的負(fù)采樣。

開始之前先介紹一下！RUC AI Box 開發(fā)和維護(hù)了一個(gè)統(tǒng)一、全面、高效的推薦系統(tǒng)代碼庫 RecBole（發(fā)表在 CIKM 2021）。

https://github.com/RUCAIBox/RecBole

RecBole 可以通過參數(shù)?neg_sampling?改變負(fù)采樣策略，支持推薦系統(tǒng)中的隨機(jī)負(fù)采樣 (RNS,?uniform) 、基于流行度的負(fù)采樣 (PNS,?popularity) 和動(dòng)態(tài)負(fù)采樣 (DNS,?dynamic) 三種經(jīng)典的方式。大家也可以在此基礎(chǔ)上進(jìn)行拓展，歡迎 Clone, Fork 和 Star ~

目錄

• 1. 研究背景

  • 1.1 什么是負(fù)采樣？

  • 1.2 為什么需要負(fù)采樣？

  • 1.3 為什么需要高質(zhì)量的負(fù)采樣？

• 2. 負(fù)采樣方法分類梳理

  • 2.1 靜態(tài)負(fù)采樣

  • 2.2 強(qiáng)負(fù)例采樣

  • 2.3 對抗式負(fù)采樣

  • 2.4 基于圖的負(fù)采樣

  • 2.5 引入額外信息的負(fù)采樣

• 3. 未來展望

  • 3.1 偽負(fù)例問題

  • 3.2 融入課程學(xué)習(xí)

  • 3.3 負(fù)采樣比例

  • 3.4 去偏采樣

  • 3.5 無采樣

• 4.?小結(jié)

  • GitHub Repo

1. 研究背景

1.1 什么是負(fù)采樣？

在深度神經(jīng)網(wǎng)絡(luò)模型中，數(shù)據(jù)集中的每個(gè)句子、每對交互、每張圖片都可以看作是模型的正樣本，也稱正例 (postive example)。在模型的訓(xùn)練過程中，一種常見的訓(xùn)練方式是同時(shí)給模型提供正例與負(fù)例 (negative example，不一定真實(shí)存在)，并構(gòu)造損失函數(shù)增大正負(fù)例的區(qū)分度，從而學(xué)到數(shù)據(jù)中的信息。基于一定的策略構(gòu)造與正例相對的負(fù)例的過程，稱為負(fù)采樣 (Negative Sampling) 。

在 NLP 中隨機(jī)替換連貫句子中的詞語、在 CV 中不同圖片數(shù)據(jù)增強(qiáng)的樣例，以及 RS 中選擇用戶未交互的商品，都可以看作是在進(jìn)行負(fù)采樣。相關(guān)的損失函數(shù)有貝葉斯個(gè)性化排序損失 (BPR, viz. Bayesian Personalized Ranking loss)、二元交叉熵?fù)p失函數(shù) (BCE, viz. Binary Cross Entropy loss) 和對比學(xué)習(xí)中常用的 InfoNCE loss 等。

1.2 為什么需要負(fù)采樣？

對于不同的領(lǐng)域，這個(gè)問題可能需要具體進(jìn)行分析。但總的來說，負(fù)采樣的作用有以下兩點(diǎn)：

• Efficient：

  • 提升了模型的計(jì)算效率。

  • 以推薦系統(tǒng)基于隱式反饋的協(xié)同過濾算法 (Implicit Collaborative Filtering) 為例，對于用戶交互的每個(gè)商品，如果我們不進(jìn)行負(fù)采樣，而是將該用戶未交互的所有商品都作為負(fù)例進(jìn)行優(yōu)化，這樣每個(gè)用戶的更新都會(huì)涉及所有 item embedding，效率低下。

  • 負(fù)采樣的目的之一是僅對求代價(jià)過程中涉及的向量進(jìn)行優(yōu)化，減少訓(xùn)練的負(fù)荷。

• Effective：

  • 保證了模型的訓(xùn)練效果。

  • 即使我們有充足的計(jì)算資源可以每次優(yōu)化所有負(fù)例，但使用一定的策略對負(fù)例進(jìn)行采樣選擇可以達(dá)到相同甚至更好的結(jié)果。

  • 通常來說，我們能夠使用的正例相對于隨機(jī)構(gòu)造的負(fù)例來說是非常有限的，即使對正例進(jìn)行數(shù)據(jù)增廣，正例與候選負(fù)例的數(shù)量往往也不在一個(gè)量級。

  • 訓(xùn)練時(shí)我們會(huì)優(yōu)化正例對的得分高于負(fù)例對，經(jīng)過幾輪訓(xùn)練后，正例 pair 的分?jǐn)?shù)相對隨機(jī)負(fù)例而言已經(jīng)比較高了。盡管負(fù)例候選集十分龐大，但能帶來信息增益的負(fù)例才是訓(xùn)練的關(guān)鍵，盲目地同等看待所有候選樣例很有可能事倍功半。

  • 負(fù)采樣的另一目的是有針對性地提供高質(zhì)量的負(fù)例，既加快收斂速度，又可以讓模型朝著我們希望的方向進(jìn)行優(yōu)化。

1.3 為什么需要高質(zhì)量的負(fù)采樣？

前面的描述可能比較抽象，讓我們從《三國演義》的一個(gè)例子來具體地體會(huì)負(fù)例選擇的重要性（對《三國演義》不太熟悉的讀者可以依次代入四郎、甄嬛、靜白、浣碧和純元，或者賈寶玉、晴雯、劉姥姥、多姑娘和林黛玉）。

正所謂“得人才者得天下”，已知?jiǎng)溆嘘P(guān)羽和張飛兩位大將，那么張飛就可以作為劉備的一個(gè)正例 (positive example)。由于人才永遠(yuǎn)是最稀缺的資源，如果我們隨機(jī)從三國時(shí)期的千萬人群中選一個(gè)作為負(fù)例，那么隨機(jī)負(fù)例 (random negative) 能被劉備賞識并重用的概率微乎其微。換句話說，劉備張飛劉備無名小兵 很難讓模型學(xué)到有用的信息。因此，模型可能無法進(jìn)行良好的參數(shù)更新，也不能將略微相關(guān)的樣例與非常相關(guān)的樣例區(qū)分開來。

我們希望采樣得到的是 informative negative，在文獻(xiàn)中常被稱作 hard negative，即強(qiáng)負(fù)例。

在《三國演義》的設(shè)定中，張飛和呂布都是勇猛過人的將領(lǐng)，有萬夫之勇，也都有各自的缺點(diǎn)。張飛鞭笞士卒、嗜酒無度；呂布驕奢淫逸、好色貪利。劉備視張飛為手足，卻在白門樓說出“公不見丁建陽、董卓之事乎？”，精準(zhǔn)為呂布補(bǔ)刀。

正是因?yàn)閯湟匀柿x聞名天下，最不喜的就是呂布此等忘恩負(fù)義、背信棄義的小人。將呂布這種具有一定競爭力的強(qiáng)負(fù)例作為訓(xùn)練樣本，模型便能更好地挖掘劉備重情重義的特點(diǎn)。

強(qiáng)負(fù)例可能增進(jìn)模型的訓(xùn)練效果，但至堅(jiān)易斷，過強(qiáng)易折，強(qiáng)負(fù)例超過一定界限后可能會(huì)采到未來的正例。對于當(dāng)前的訓(xùn)練而言，這種樣例在學(xué)術(shù)中被稱作偽負(fù)例 (false negative)。也就是說，如果將劉備很有可能感興趣的趙云作為與張飛配對的負(fù)例，劉備張飛劉備趙云 非但不能帶來正向激勵(lì)，有時(shí)甚至?xí)δＰ驮斐韶?fù)面影響。

針對負(fù)例的質(zhì)量和重要性，Facebook 進(jìn)行了一項(xiàng)很有意思的研究工作，定量分析了 CV 領(lǐng)域?qū)Ρ葘W(xué)習(xí)里的負(fù)例對模型性能的影響。

▲Are all negatives created equal in contrastive instance discrimination? [93]

文章研究發(fā)現(xiàn)：

• 絕大多數(shù) (約95%) 負(fù)例是 easy negatives，它們與查詢在語義上并不相似，僅用 easy negatives 不足以訓(xùn)練出一個(gè)好的模型。

• 其次，約 5% 的負(fù)例是 hard negatives，它們與查詢在語義上相似但不同，這些強(qiáng)負(fù)例幾乎決定了模型的結(jié)果，在訓(xùn)練中發(fā)揮了關(guān)鍵作用。

• 還有近 0.1% 的負(fù)例是 same class negatives，也就是我們之前提到的偽負(fù)例。這些負(fù)例表面上看與查詢并不相似，但本質(zhì)上語義是相同的（都是狗），把它們作為負(fù)例反而會(huì)影響模型的結(jié)果。

2. 負(fù)采樣方法分類梳理

本文聚焦于負(fù)采樣方法，將 NLP、CV、RS、GRL、CL 等領(lǐng)域的相關(guān)工作分為五類進(jìn)行介紹：靜態(tài)負(fù)采樣 (Static Negative Sampling)、強(qiáng)負(fù)例采樣 (Hard Negative Sampling)、對抗式負(fù)采樣 (Adversarial Sampling)、基于圖的負(fù)采樣 (Graph-based Sampling) 和引入額外信息的負(fù)采樣 (Additional Data Enhanced Sampling)。

參考文獻(xiàn)末尾給出了該篇工作的所屬領(lǐng)域和 PDF 鏈接，讀者可以根據(jù)自己的研究領(lǐng)域和興趣方向選擇性地閱讀原文。

2.1 靜態(tài)負(fù)采樣 (Static Negative Sampling)

如果我們限定從未交互集中選擇已知的樣例作為負(fù)例，那么，通過給不同的樣例設(shè)置不同的權(quán)重，我們便能根據(jù)負(fù)例分布進(jìn)行采樣。

在不考慮合成新負(fù)例的前提下，負(fù)采樣本質(zhì)上是學(xué)習(xí)負(fù)例分布的問題。當(dāng)每個(gè)樣例被采樣為負(fù)例的概率不隨訓(xùn)練發(fā)生變化時(shí)，我們就稱這種采樣策略為靜態(tài)負(fù)采樣 (Static Negative Sampling)。

在靜態(tài)負(fù)采樣方法中，最簡單也是應(yīng)用最廣泛的方法是隨機(jī)負(fù)采樣 (RNS, viz. Random Negative Sampling)，也被稱為均勻負(fù)采樣 (Uniform Negative Sampling)。RNS [1, 2, 11] 隨機(jī)從負(fù)例候選集中選擇一個(gè)作為負(fù)例，在不考慮負(fù)采樣的研究中，研究者們一般使用 RNS 作為基礎(chǔ)的采樣方法，以便公平地和 baseline 進(jìn)行比較。

顯然，對于每個(gè)正例而言，不同的負(fù)例帶來的影響并不相同，一種啟發(fā)式的負(fù)例分布的策略是基于流行度的負(fù)采樣 (PNS, viz. Popularity-biased Negative Sampling)。流行度可以通過頻次 (frequency) 或度 (degree) 來反映， ，即樣本 被選為負(fù)例的概率和 的流行度的 次方具有比例關(guān)系。

當(dāng) 時(shí)，PNS 就退化成了 RNS。

402 Payment Required

PNS 首先在 word2vec [3] 中被提出。在 word2vec 詞嵌入的表示中，實(shí)驗(yàn)發(fā)現(xiàn) 的結(jié)果較好，[4] 從理論角度對這種負(fù)采樣策略進(jìn)行了一定的解釋，大多數(shù)嵌入表示算法 [5, 6, 7, 8] 也沿用了該方法和超參數(shù)。

然而， 并不是適用于所有領(lǐng)域， 甚至不一定需要為正數(shù)。[10] 將 word2vec 的負(fù)采樣方式應(yīng)用到推薦系統(tǒng)中發(fā)現(xiàn)，PNS 超參數(shù) 的選擇依賴于數(shù)據(jù)集和任務(wù)。

[10] 在音樂推薦任務(wù)上研究了 對推薦結(jié)果的影響，結(jié)果發(fā)現(xiàn) 時(shí)的結(jié)果最佳。為負(fù)數(shù)意味著更多地選擇不受歡迎的音樂作為負(fù)樣本，這種情況下的 PNS 旨在更好地區(qū)分不同受歡迎程度的歌曲，文中也強(qiáng)調(diào)了超參數(shù)在不同任務(wù)場景下的關(guān)鍵作用。

▲Word2vec applied to Recommendation: Hyperparameters Matter [10]

在推薦系統(tǒng)領(lǐng)域，更常見的基于流行度的采樣方法 [9, 12, 17] 是直接將商品在訓(xùn)練集中的流行程度作為候選負(fù)例的權(quán)重，即傾向于選擇更流行的商品作為負(fù)例。

這種策略可以用流行度偏差來解釋，借用 @Zilize 的描述：在高流行度（高曝光度）的情況下用戶沒有給予商品正反饋，說明用戶大概率（比如 90%）不喜歡這件物品；在低流行度時(shí)則是完全不確定的狀態(tài)（比如 50%）。當(dāng)我們采樣高流行度的負(fù)例時(shí)，可能只會(huì)帶來 10% 的偏差，而隨機(jī)采樣會(huì)帶來 50% 的偏差，從而后者對推薦系統(tǒng)的訓(xùn)練不利。

盡管具有一定的解釋性，但從學(xué)術(shù)界的相關(guān)實(shí)驗(yàn)結(jié)果來看，PNS 在推薦系統(tǒng)中并不是穩(wěn)定地優(yōu)于 RNS，有時(shí)還會(huì)顯著降低模型結(jié)果。如何合理利用商品流行度仍然是推薦系統(tǒng)中未被充分探索的問題。

▲Reinforced Negative Sampling over Knowledge Graph for Recommendation [73]

• [1]. BPR: Bayesian Personalized Ranking from Implicit Feedback. UAI(2009) [RS] [PDF]

• [2]. Real-Time Top-N Recommendation in Social Streams. RecSys(2012) [RS] [PDF]

• [3]. Distributed Representations of Words and Phrases and their Compositionality. NIPS(2013) [NLP] [PDF]

• [4]. word2vec Explained: Deriving Mikolov et al.'s Negative-Sampling Word-Embedding Method. arXiv(2014) [NLP] [PDF]

• [5]. Deepwalk: Online learning of social representations. KDD(2014) [GRL] [PDF]

• [6]. LINE: Large-scale Information Network Embedding. WWW(2015) [GRL] [PDF]

• [7]. Context- and Content-aware Embeddings for Query Rewriting in Sponsored Search. SIGIR(2015) [NLP] [PDF]

• [8]. node2vec: Scalable Feature Learning for Networks. KDD(2016) [NLP] [PDF]

• [9]. Fast Matrix Factorization for Online Recommendation with Implicit Feedback. SIGIR(2016) [RS] [PDF]

• [10]. Word2vec applied to Recommendation: Hyperparameters Matter. RecSys(2018) [RS] [PDF]

• [11]. General Knowledge Embedded Image Representation Learning. TMM(2018) [CV] [PDF]

• [12]. Alleviating Cold-Start Problems in Recommendation through Pseudo-Labelling over Knowledge Graph. WSDM(2021) [RS] [PDF]

2.2 強(qiáng)負(fù)例采樣 (Hard Negative Sampling)

靜態(tài)負(fù)采樣方法不隨訓(xùn)練發(fā)生變化，無法動(dòng)態(tài)地適應(yīng)并調(diào)整候選負(fù)例的分布，也就難以挖掘更有利的負(fù)樣本。盡管我們沒有顯式的負(fù)例標(biāo)簽，但在訓(xùn)練過程中，模型對每個(gè)候選負(fù)例的分?jǐn)?shù)是可以被利用的。

所謂強(qiáng)負(fù)例 (hard negative) 的 hard 取決于模型，那些被錯(cuò)誤分類的樣例，或是預(yù)測得分更高的負(fù)例，與改進(jìn)模型結(jié)果更為相關(guān)。我們可以把這種思路類比到小明做題，得分低的負(fù)例是小明已經(jīng)掌握的簡單題，得分高的負(fù)例是小明不太會(huì)做的提高題或是錯(cuò)題，這些對于小明來說相對 hard 的題更能幫助他掌握所學(xué)知識。

Hard Negative Sampling，又稱 Hard Example Mining，早在 1998 年 CV 領(lǐng)域的人臉識別 [13] 中，研究者們就開始將分類器識別錯(cuò)誤的圖片加入到負(fù)例集來提升訓(xùn)練質(zhì)量。

▲Example-based learning for view-based human face detection [13]

在近十年的深度學(xué)習(xí)中，無論是 CV 領(lǐng)域的圖片分類 [16, 28]、目標(biāo)檢測 [21, 23, 26, 29]、跨模態(tài)學(xué)習(xí) [37]，還是 NLP 領(lǐng)域的語言模型 [14]、問答系統(tǒng) [19]、結(jié)點(diǎn)表示 [30]，或是推薦系統(tǒng) [15, 17, 18, 20, 24, 31, 33, 35]，或是知識圖譜的表示學(xué)習(xí) [25, 27, 36]，都可以通過強(qiáng)負(fù)例采樣提升模型的訓(xùn)練結(jié)果。

▲Graph Convolutional Neural Networks for Web-Scale Recommender Systems [70]

無論哪個(gè)領(lǐng)域，挖掘強(qiáng)負(fù)例的最常見方法都是選擇離 anchor/user/query 最近的樣本（即在 embedding 空間中最相似的樣本）。

既然錨點(diǎn)樣本對負(fù)例選擇有幫助，那么自然而然可以想到正例也能為配對的負(fù)例提供相似度的信息。[19] 在問答系統(tǒng)中選擇與正例最相似的樣本作為負(fù)例，[25, 27, 36] 中為知識圖譜三元組選取負(fù)例時(shí)也是選擇離正例最接近的實(shí)體。KGPolicy [73] 既考慮了與 anchor 的相似度，又考慮了與 positive example 的相似度，將兩者相加作為選擇強(qiáng)負(fù)例的標(biāo)準(zhǔn)。

不過，上述方法仍然是選擇已有的樣例作為強(qiáng)負(fù)例，那么我們能不能根據(jù)需要生成 (synthesize) 所需強(qiáng)負(fù)例呢？

▲Hard Negative Mixing for Contrastive Learning [32]

答案是可以的，MoCHi [32] 在對比學(xué)習(xí)的任務(wù)中直接合成強(qiáng)負(fù)例，通過 Hard Negative Mixing 的方式融合了現(xiàn)有強(qiáng)負(fù)例與 query 的表示，從 embedding 空間得到了更能為訓(xùn)練帶來增益的負(fù)例。

也就是說，我們不一定要執(zhí)著于學(xué)習(xí)已知負(fù)例的分布，還可以從 synthetic sampling 的角度出發(fā)合成我們需要的負(fù)樣本表示。

• [13]. Example-based learning for view-based human face detection. TPAMI(1998) [CV] [PDF]

• [14]. Adaptive Importance Sampling to Accelerate Training of a Neural Probabilistic Language Model. T-NN(2008) [NLP] [PDF]

• [15]. Optimizing Top-N Collaborative Filtering via Dynamic Negative Item Sampling. SIGIR(2013) [RS] [PDF]

• [16]. Bootstrapping Visual Categorization With Relevant Negatives. TMM(2013) [CV] [PDF]

• [17]. Improving Pairwise Learning for Item Recommendation from Implicit Feedback. WSDM(2014) [RS] [PDF]

• [18]. Improving Latent Factor Models via Personalized Feature Projection for One Class Recommendation. CIKM(2015) [RS] [PDF]

• [19]. Noise-Contrastive Estimation for Answer Selection with Deep Neural Networks. CIKM(2016) [NLP] [PDF]

• [20]. RankMBPR: Rank-aware Mutual Bayesian Personalized Ranking for Item Recommendation. WAIM(2016) [RS] [PDF]

• [21]. Training Region-Based Object Detectors With Online Hard Example Mining. CVPR(2016) [CV] [PDF]

• [22]. Hard Negative Mining for Metric Learning Based Zero-Shot Classification. ECCV(2016) [ML] [PDF]

• [23]. Vehicle detection in aerial images based on region convolutional neural networks and hard negative example mining. Sensors(2017) [CV] [PDF]

• [24]. WalkRanker: A Unified Pairwise Ranking Model with Multiple Relations for Item Recommendation. AAAI(2018) [RS] [PDF]

• [25]. Bootstrapping Entity Alignment with Knowledge Graph Embedding. IJCAI(2018) [KGE] [PDF]

• [26]. Improving Occlusion and Hard Negative Handling for Single-Stage Pedestrian Detectors. CVPR(2018) [CV] [PDF]

• [27]. NSCaching: Simple and Efficient Negative Sampling for Knowledge Graph Embedding. ICDE(2019) [KGE] [PDF]

• [28]. Meta-Transfer Learning for Few-Shot Learning. CVPR(2019) [CV] [PDF]

• [29]. ULDor: A Universal Lesion Detector for CT Scans with Pseudo Masks and Hard Negative Example Mining. ISBI(2019) [CV] [PDF]

• [30]. Distributed representation learning via node2vec for implicit feedback recommendation. NCA(2020) [NLP] [PDF]

• [31]. Simplify and Robustify Negative Sampling for Implicit Collaborative Filtering. arXiv(2020) ?[RS] [PDF]

• [32]. Hard Negative Mixing for Contrastive Learning. arXiv(2020) [CL] [PDF]

• [33]. Bundle Recommendation with Graph Convolutional Networks. SIGIR(2020) [RS] [PDF]

• [34]. Supervised Contrastive Learning. NIPS(2020) [CL] [PDF]

• [35]. Curriculum Meta-Learning for Next POI Recommendation. KDD(2021) [RS] [PDF]

• [36]. Boosting the Speed of Entity Alignment 10×: Dual Attention Matching Network with Normalized Hard Sample Mining. WWW(2021) [KGE] [PDF]

• [37]. Hard-Negatives or Non-Negatives? A Hard-Negative Selection Strategy for Cross-Modal Retrieval Using the Improved Marginal Ranking Loss. ICCV(2021) [CV] [PDF]

2.3 對抗式負(fù)采樣 (Adversarial Sampling)

生成對抗網(wǎng)絡(luò) (GAN, viz. Generative Adversarial Network) 是近幾年熱門的一種無監(jiān)督算法，多次出現(xiàn)在各類頂會(huì)論文中。對抗式負(fù)采樣方法通常基于 GAN 來選擇負(fù)例，為負(fù)采樣方法注入了新的活力。

與 GAN 類似，對抗式負(fù)采樣方法往往也有一個(gè)生成器 (generator) 和一個(gè)判別器 (discriminator)，其中生成器充當(dāng)采樣器生成樣例以混淆判別器，而判別器需要判斷給定的樣例是正例還是生成的樣例。理想的均衡狀態(tài)是判別器生成非常近似于正例的樣例，而判別器無法區(qū)分正例與生成器產(chǎn)生的樣例。

對抗式負(fù)采樣的關(guān)鍵在于對抗式的采樣器，它在 generator 和 discriminator 之間進(jìn)行 minimax 博弈，從而更好地挖掘強(qiáng)數(shù)據(jù)中的負(fù)例信息。從本質(zhì)上來說，對抗式負(fù)采樣的目的仍然是為了學(xué)習(xí)到更好的負(fù)例分布。

▲IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models [39]

然而，對抗式負(fù)采樣方法的缺點(diǎn)也很突出，復(fù)雜的框架、不穩(wěn)定的訓(xùn)練結(jié)果和較長的訓(xùn)練時(shí)間都極大地限制了該方法的應(yīng)用場景，生成器與對抗器之間的博弈也不一定能收斂到理想的納什均衡狀態(tài)，對抗式負(fù)采樣方法仍有探索和改進(jìn)的空間。

• [38]. Deep Generative Image Models using a Laplacian Pyramid of Adversarial Networks. NIPS(2015) [CV] [PDF]

• [39]. IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models. SIGIR(2017) [IR] [PDF]

• [40]. SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient. AAAI(2017) [NLP] [PDF]

• [41]. KBGAN: Adversarial Learning for Knowledge Graph Embeddings. NAACL(2018) [KGE] [PDF]

• [42]. Neural Memory Streaming Recommender Networks with Adversarial Training. KDD(2018) [RS] [PDF]

• [43]. GraphGAN: Graph Representation Learning with Generative Adversarial Nets. AAAI(2018) [GRL] [PDF]

• [44]. CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks. CIKM(2018) [RS] [PDF]

• [45]. Adversarial Contrastive Estimation. ACL(2018) [NLP] [PDF]

• [46]. Incorporating GAN for Negative Sampling in Knowledge Representation Learning. AAAI(2018) [KGE] [PDF]

• [47]. Exploring the potential of conditional adversarial networks for optical and SAR image matching. IEEE J-STARS(2018) [CV] [PDF]

• [48]. Deep Adversarial Metric Learning. CVPR(2018) [CV] [PDF]

• [49]. Adversarial Detection with Model Interpretation. KDD(2018) [ML] [PDF]

• [50]. Adversarial Sampling and Training for Semi-Supervised Information Retrieval. WWW(2019) [IR] [PDF]

• [51]. Deep Adversarial Social Recommendation. IJCAI(2019) [RS] [PDF]

• [52]. Adversarial Learning on Heterogeneous Information Networks. KDD(2019) [HIN] [PDF]

• [53]. Regularized Adversarial Sampling and Deep Time-aware Attention for Click-Through Rate Prediction. CIKM(2019) [RS] [PDF]

• [54]. Adversarial Knowledge Representation Learning Without External Model. IEEE Access(2019) [KGE] [PDF]

• [55]. Adversarial Binary Collaborative Filtering for Implicit Feedback. AAAI(2019) [RS] [PDF]

• [56]. ProGAN: Network Embedding via Proximity Generative Adversarial Network. KDD(2019) [GRL] [PDF]

• [57]. Generating Fluent Adversarial Examples for Natural Languages. ACL(2019) [NLP] [PDF]

• [58]. IPGAN: Generating Informative Item Pairs by Adversarial Sampling. TNLLS(2020) ?[RS] [PDF]

• [59]. Contrastive Learning with Adversarial Examples. arXiv(2020) [CL] [PDF]

• [60]. PURE: Positive-Unlabeled Recommendation with Generative Adversarial Network. KDD(2021) [RS] [PDF]

• [61]. Negative Sampling for Knowledge Graph Completion Based on Generative Adversarial Network. ICCCI(2021) [KGE] [PDF]

• [62]. Synthesizing Adversarial Negative Responses for Robust Response Ranking and Evaluation. arXiv(2021) [NLP] [PDF]

• [63]. Adversarial Feature Translation for Multi-domain Recommendation. KDD(2021) [RS] [PDF]

• [64]. Adversarial training regularization for negative sampling based network embedding. Information Sciences(2021) [GRL] [PDF]

• [65]. Adversarial Caching Training: Unsupervised Inductive Network Representation Learning on Large-Scale Graphs. TNNLS(2021) [GRL] [PDF]

• [66]. A Robust and Generalized Framework for Adversarial Graph Embedding. arxiv(2021) [GRL] [PDF]

• [67]. Instance-wise Hard Negative Example Generation for Contrastive Learning in Unpaired Image-to-Image Translation. ICCV(2021) [CV] [PDF]

2.4 基于圖的負(fù)采樣 (Graph-based Sampling)

如果說前面介紹的 Hard Negative Sampling 和 Adversarial Sampling 充分利用的是樣例在 embedding 空間的語義 (semantic) 信息，那么基于圖的負(fù)采樣方法則是進(jìn)一步結(jié)合樣例在圖上的結(jié)構(gòu) (structural) 信息。

GNEG [69] 是 word2vec 負(fù)采樣方法的改進(jìn)，先根據(jù)語料庫中詞語的共現(xiàn)關(guān)系構(gòu)造共現(xiàn) (co-occurrence) 網(wǎng)絡(luò)，再在通過目標(biāo)結(jié)點(diǎn)上的隨機(jī)游走獲得更強(qiáng)的負(fù)例。RWS [68]、SamWalker [71] 和 SamWalker++ [75] 也是類似的隨機(jī)游走 (Random Walking) 策略，只是應(yīng)用的領(lǐng)域?yàn)橥扑]系統(tǒng)。

KGPolicy [73] 利用知識圖譜的輔助信息和強(qiáng)化學(xué)習(xí)的方法尋找高質(zhì)量的負(fù)例，DSKReG [76] 則是在知識圖譜上根據(jù)相連的關(guān)系和結(jié)點(diǎn)嵌入計(jì)算鄰居結(jié)點(diǎn)的相關(guān)性分?jǐn)?shù)。

▲Reinforced Negative Sampling over Knowledge Graph for Recommendation [73]

作為 GNN 的歸納變體，PinSage [70] 提出基于 PageRank 分?jǐn)?shù)對強(qiáng)負(fù)例進(jìn)行采樣，相比隨機(jī)游走進(jìn)一步利用了圖上的結(jié)構(gòu)信息。

馬爾可夫鏈蒙特卡羅負(fù)采樣（MCNS）[72] 是從理論上分析負(fù)采樣在鏈路預(yù)測中的影響的先驅(qū)。基于推導(dǎo)出的理論，MCNS 提出通過近似正分布來對負(fù)樣本進(jìn)行采樣，根據(jù)圖上的結(jié)構(gòu)相關(guān)性重新設(shè)計(jì)正負(fù)例的樣本分布，并通過 Metropolis-Hastings 算法加速該過程。

▲Understanding Negative Sampling in Graph Representation Learning [72]

類似 MoCHi [32] 的合成機(jī)制，MixGCF [74] 設(shè)計(jì)了兩種策略：正例混合 (positive mixing) 和鄰域混合 (hop mixing)。positive mixing 通過注入正例的嵌入使得原始負(fù)樣本獲得正例的表示信息，而 hop mixing 通過 GNN 聚合鄰域生成信息增強(qiáng)的負(fù)例，在基于圖神經(jīng)網(wǎng)絡(luò)推薦系統(tǒng)的采樣方法中取得了 SOTA 的結(jié)果。

▲MixGCF: An Improved Training Method for Graph Neural Network-based Recommender Systems [74]

• [68]. ACRec: a co-authorship based random walk model for academic collaboration recommendation. WWW(2014) [RS] [PDF]

• [69]. GNEG: Graph-Based Negative Sampling for word2vec. ACL(2018) [NLP] [PDF]

• [70]. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD(2018) [RS] [PDF]

• [71]. SamWalker: Social Recommendation with Informative Sampling Strategy. WWW(2019) [RS] [PDF]

• [72]. Understanding Negative Sampling in Graph Representation Learning. KDD(2020) [GRL] [PDF]

• [73]. Reinforced Negative Sampling over Knowledge Graph for Recommendation. WWW(2020) [RS] [PDF]

• [74]. MixGCF: An Improved Training Method for Graph Neural Network-based Recommender Systems. KDD(2021) [RS] [PDF]

• [75]. SamWalker++: recommendation with informative sampling strategy. TKDE(2021) [RS] [PDF]

• [76]. DSKReG: Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN. CIKM(2021) [RS] [PDF]

2.5 引入額外信息的負(fù)采樣 (Additional Data Enhanced Sampling)

本小節(jié)主要針對推薦系統(tǒng)中引入額外信息的負(fù)采樣，一些工作利用社交網(wǎng)絡(luò)中的聯(lián)系 [77, 78, 85, 86]、用戶的地理位置 [80, 81, 84]、商品的類別信息 [87] 以及額外的交互數(shù)據(jù)，例如用戶瀏覽但沒有被點(diǎn)擊的商品 (viewed but non-clicked) [82, 83]，以及用戶點(diǎn)擊了卻沒有購買的商品 (clicked but non-purchased) [79] 來增強(qiáng)負(fù)例的選取。

▲Efficient Heterogeneous Collaborative Filtering without Negative Sampling for Recommendation [99]

在工業(yè)的推薦場景中，不同的行為 (比如瀏覽、點(diǎn)擊、添加購物車、購買) 是建模用戶偏好的關(guān)鍵。

• [77]. Leveraging Social Connections to Improve Personalized Ranking for Collaborative Filtering. CIKM(2014) [RS] [PDF]

• [78]. Social Recommendation with Strong and Weak Ties. CIKM(2016) [RS] [PDF]

• [79]. Bayesian Personalized Ranking with Multi-Channel User Feedback. RecSys(2016) [RS] [PDF]

• [80]. Joint Geo-Spatial Preference and Pairwise Ranking for Point-of-Interest Recommendation. ICTAI(2017) [RS] [PDF]

• [81]. A Personalised Ranking Framework with Multiple Sampling Criteria for Venue Recommendation. CIKM(2017) [RS] [PDF]

• [82]. An Improved Sampling for Bayesian Personalized Ranking by Leveraging View Data. WWW(2018) [RS] [PDF]

• [83]. Reinforced Negative Sampling for Recommendation with Exposure Data. IJCAI(2019) [RS] [PDF]

• [84]. Geo-ALM: POI Recommendation by Fusing Geographical Information and Adversarial Learning Mechanism. IJCAI(2019) [RS] [PDF]

• [85]. Bayesian Deep Learning with Trust and Distrust in Recommendation Systems. WI(2019) [RS] [PDF]

• [86]. Socially-Aware Self-Supervised Tri-Training for Recommendation. arXiv(2021) [RS] [PDF]

• [87]. DGCN: Diversified Recommendation with Graph Convolutional Networks. WWW(2021) [RS] [PDF]

3. 未來展望

3.1 偽負(fù)例問題 (False Negative Problem)

現(xiàn)有基于負(fù)采樣方法的研究集中在如何挖掘強(qiáng)負(fù)例，較少地關(guān)注偽負(fù)例 (False Negative) 問題。

一方面，我們希望模型能從一定的強(qiáng)負(fù)例中挖掘信息；另一方面，我們不希望模型總是將未來可能感興趣的樣例視作負(fù)例。兩者的平衡不應(yīng)人為去調(diào)整設(shè)定，而應(yīng)該讓模型具有一定的鑒別能力。

▲Graph Debiased Contrastive Learning with Joint Representation Clustering [89]

SRNS [31] 從統(tǒng)計(jì)學(xué)的角度觀測到數(shù)據(jù)集中的偽負(fù)例在訓(xùn)練過程中方差較小，而強(qiáng)負(fù)例具有較高的方差。根據(jù)這一現(xiàn)象，文章結(jié)合評分函數(shù)和樣例多輪得分的標(biāo)準(zhǔn)差，在新的得分上進(jìn)行采樣得到強(qiáng)負(fù)例。然而，SRNS 文中提到的負(fù)例現(xiàn)象只體現(xiàn)在某些數(shù)據(jù)集上，該啟發(fā)式的統(tǒng)計(jì)學(xué)思路也缺少理論的支撐。

ASA [90] 在強(qiáng)負(fù)例采樣中不是選擇得分最高的負(fù)例，而是考慮對應(yīng)的正樣本分?jǐn)?shù)，選擇得分不超過正樣本的難度適中的負(fù)例來緩解偽負(fù)例問題。在對比學(xué)習(xí)中，[88] 提出一種自監(jiān)督對比學(xué)習(xí)框架逐步檢測并刪除偽負(fù)例，而 [89] 通過圖表示學(xué)習(xí)中的聚類結(jié)果有效地減少偽負(fù)例樣本。

• [88]. Incremental False Negative Detection for Contrastive Learning. arXiv(2021) [CL] [PDF]

• [89]. Graph Debiased Contrastive Learning with Joint Representation Clustering. IJCAI(2021) [GRL & CL] [PDF]

• [90]. Relation-aware Graph Attention Model With Adaptive Self-adversarial Training. AAAI(2021) [KGE] [PDF]

3.2 融入課程學(xué)習(xí) (Curriculum Learning)

仍然是小明做題的例子，如果小明只練習(xí)簡單的加減乘除，即使平時(shí)練習(xí)次次滿分，也無法在高中的數(shù)學(xué)考試中取得佳績。但如果小明天天做高考壓軸題而不鞏固基礎(chǔ)，一樣無法拿到高分。換句話說，模型訓(xùn)練需要強(qiáng)負(fù)例，但是不能只有最強(qiáng)的負(fù)例。

為了均衡較強(qiáng)與較弱的負(fù)例，融入課程學(xué)習(xí) (Curriculum Learning) 是個(gè)不錯(cuò)的選擇。[91, 92] 的研究都是讓模型先從簡單的負(fù)例學(xué)起，逐漸增大負(fù)例的強(qiáng)度，而其他領(lǐng)域、其他任務(wù)中融入課程學(xué)習(xí)進(jìn)行負(fù)例選取的結(jié)果值得我們?nèi)ヌ剿鳌?/p>

• [91]. On The Power of Curriculum Learning in Training Deep Networks. ICML(2016) [CV] [PDF]

• [92]. Graph Representation with Curriculum Contrastive Learning. IJCAI(2021) [GRL & CL] [PDF]

3.3 負(fù)采樣比例 (Negative Sampling Ratio)

負(fù)采樣方法主要是為了提升負(fù)例質(zhì)量，而負(fù)采樣比例則是決定了負(fù)例的數(shù)量。

[93] 在圖像分類的對比學(xué)習(xí)中定量分析了各種負(fù)例的重要性；SimpleX [94] 表明，即使是最基礎(chǔ)的協(xié)同過濾方法，在合適的負(fù)采樣比例與損失函數(shù)的加持下，也能優(yōu)于目前最優(yōu)的推薦算法；[95] 對基于 InfoNCE 模型訓(xùn)練中的負(fù)例數(shù)量進(jìn)行了分析，提出了一種動(dòng)態(tài)適應(yīng)采樣比例的負(fù)采樣方法。就目前的研究來看，負(fù)采樣比例也是一個(gè)尚待深挖的方向。

• [93]. Are all negatives created equal in contrastive instance discrimination. arXiv(2020) [CL] [PDF]

• [94]. SimpleX: A Simple and Strong Baseline for Collaborative Filtering. CIKM(2021) [RS] [PDF]

• [95]. Rethinking InfoNCE: How Many Negative Samples Do You Need. arXiv(2021) [CL] [PDF]

3.4 去偏采樣 (Debiased Sampling)

在只能訪問正例和未標(biāo)記數(shù)據(jù) (Positive-Unlabeled) 的場景下，采樣不可避免會(huì)有一定的偏差，比如前面提到的 false negative 問題就是負(fù)采樣中一種典型的采樣偏差 (sample bias)。

[96] 首先對比了 Biased 和 Unbiased 方法的結(jié)果差異，并提出了一個(gè)去偏差的對比學(xué)習(xí)目標(biāo)，一定程度上糾正了負(fù)例的采樣偏差，在 CV、NLP 和強(qiáng)化學(xué)習(xí)任務(wù)上驗(yàn)證了方法的有效性。針對推薦系統(tǒng)曝光偏差對采樣的影響，CLRec [97] 從理論上證明了對比損失的流行度選擇相當(dāng)于通過逆傾向加權(quán)減少曝光偏差，為理解對比學(xué)習(xí)的有效性提供了新的視角。

▲Debiased Contrastive Learning [96]

• [96]. Debiased Contrastive Learning. NIPS(2020) [CL] [PDF]

• [97]. Contrastive Learning for Debiased Candidate Generation in Large-Scale Recommender Systems. KDD(2021) [RS] [PDF]

3.5 無采樣 (Non-Sampling)

前面都是考慮負(fù)采樣方法的應(yīng)用和展望，但負(fù)采樣真的是必須的嗎？[98, 99, 100] 分別在 CV、RS 和 KGE 領(lǐng)域提出了無需采樣 (Non-Sampling) 的訓(xùn)練方法。

• [98] 基于傅立葉變換推導(dǎo)出一種對 Gram 矩陣進(jìn)行塊對角化的變換，同時(shí)消除冗余并劃分學(xué)習(xí)問題。重點(diǎn)在于，它允許使用數(shù)千張圖像集中的所有潛在樣本進(jìn)行訓(xùn)練，通過考慮全集，在一輪迭代中就可以生成最優(yōu)解，而強(qiáng)負(fù)采樣方法需要好幾輪才能達(dá)到相同的結(jié)果。

• EHCF [99] 認(rèn)為采樣不適合學(xué)習(xí)推薦系統(tǒng)中的異構(gòu)行為數(shù)據(jù) (heterogeneous scenarios)，并推導(dǎo)出一種有效的優(yōu)化方法，以可控的時(shí)間復(fù)雜度解決了從整個(gè)數(shù)據(jù)中學(xué)習(xí)神經(jīng)模型的挑戰(zhàn)性問題。

• NS-KGE [100] 認(rèn)為在知識圖譜的嵌入學(xué)習(xí)中，以前基于負(fù)采樣的學(xué)習(xí)方法僅考慮負(fù)實(shí)例的子集，雖然有助于降低模型學(xué)習(xí)的時(shí)間復(fù)雜度，但由于采樣過程的不確定性，這可能無法提供穩(wěn)定的模型性能。NS-KGE 在模型學(xué)習(xí)中考慮 KG 中的所有負(fù)實(shí)例，從而避免負(fù)采樣，并利用數(shù)學(xué)推導(dǎo)來降低無采樣損失函數(shù)的復(fù)雜性。實(shí)驗(yàn)結(jié)果表明 NS-KGE 框架可以在效率和準(zhǔn)確性方面取得更好的性能。

負(fù)采樣方法是輔助模型訓(xùn)練的手段而不是目的，更不是必需品。倘若我們能在可承受的計(jì)算負(fù)荷下自適應(yīng)地考慮所有候選負(fù)例，那么不進(jìn)行負(fù)采樣的無采樣 (Non-Sampling) 方法也未嘗不可。

• [98]. Beyond Hard Negative Mining: Efficient Detector Learning via Block-Circulant Decomposition. ICCV(2013) [CV] [PDF]

• [99]. Efficient Heterogeneous Collaborative Filtering without Negative Sampling for Recommendation. AAAI(2020) [RS] [PDF]

• [100]. Efficient Non-Sampling Knowledge Graph Embedding. WWW(2021) [KGE] [PDF]

4. 小結(jié)

負(fù)采樣 (Negative Sampling) 方法最初是被用于加速 Skip-Gram 模型的訓(xùn)練，后來被廣泛應(yīng)用于自然語言處理 (NLP)、計(jì)算機(jī)視覺 (CV) 和推薦系統(tǒng) (RS) 等領(lǐng)域，在近兩年的對比學(xué)習(xí) (Contrastive Learning) 研究中也發(fā)揮了重要作用。本文聚焦于負(fù)采樣方法，將各領(lǐng)域的相關(guān)工作分為五類進(jìn)行介紹，并展望了未來的研究方向。

筆者將文中涉及的 100 篇論文整理在了 RUC AI Box 小組的 GitHub 中，讀者也可以在論文列表中快捷地找到論文的 PDF 鏈接。本倉庫將繼續(xù)關(guān)注負(fù)采樣方法 (Negative Sampling) 的研究進(jìn)展并持續(xù)更新，歡迎 Star ~

https://github.com/RUCAIBox/Negative-Sampling-Paper

后臺(tái)回復(fù)關(guān)鍵詞【入群】

加入賣萌屋NLP/IR/Rec與求職討論群

后臺(tái)回復(fù)關(guān)鍵詞【頂會(huì)】

獲取ACL、CIKM等各大頂會(huì)論文集！

總結(jié)

以上是生活随笔為你收集整理的负采样，yyds！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。