一 背景
傳統的推薦系統通常由兩部分構成，分别是 Candidate Generation（候選生成）和 Ranking（排序），以下圖中經典的 YouTube 視訊推薦為例[1]，整個系統分為了兩層：第一層是 Candidate Generation（候選生成），負責從全量的視訊中快速篩選出幾百個候選視訊，這一步通常也被成為 Matching（召回）；第二層是 Ranking（排序），負責對幾百個視訊進行精準打分并重新排序，決定最終向使用者展示的結果順序。
本文主要研究 Matching（召回）部分，這部分通常面對的是整個推薦 item 集合，既要盡可能多的保留相關性高的結果，又要保證速度，召回結果的好壞對整個推薦結果有着至關重要的影響。最近的一系列實踐和研究表明，基于行為序列的深度學習推薦模型[2-4]搭配高性能的近似檢索算法[5]可以實作既準又快的召回性能（這套方案通常被稱為DeepMatch），和傳統的召回方法相比（比如 swing、etrec、SVD），DeepMatch 的優勢主要如下：
- 可以模組化 user-item 間更深層次的非線性關系
- 可以在模型中使用各種 user 和 item 的特征
- 基于行為序列的模型可以模組化使用者不斷變化的興趣，并且能夠融合使用者的長短期興趣
DeepMatch 已經廣泛應用于天貓精靈推薦場景中（APP 資訊流推薦、音樂推薦等）并取得了比傳統 i2i 方法更好的效果，但目前的模型仍存在着一些問題，有一些關鍵的資訊還未引入進來（以“我要聽歌”場景為例，在這個場景中天貓精靈會根據使用者的喜好來給使用者推薦音樂）：
負向回報信号（Play Rate）
初始訓練日志資料中僅包含正向回報，也即使用播放完成率高的歌曲序列訓練 DeepMatch 模型。而在天貓精靈的場景中，使用者有主動切歌的行為，如主動的“停止播放”、“下一首”，其中大部分這類型是使用者在出現不喜歡的歌曲時觸發，這些信号可以作為使用者的負回報加入到模型中。而且一些實踐已經表明了負向回報的作用[6-7]，如果能将這些信号有效的利用起來，模型有能力去捕捉使用者時刻變化興趣，在使用者進行切歌行為時，減少同類型的音樂推薦。在這個場景中，我們用每首歌曲的播放完成率來表示使用者回報，完播率較大即為正回報，完播率較小即為負回報。
歌曲點播 query 意圖信号（Intent Type）
天貓精靈歌曲的播放大部分由使用者的 query 點播而來，每一首歌曲背後都有使用者的點播意圖，天貓精靈背後有一套專門的歌曲 query 意圖解析，比如精确點播（歌名點播：“播放七裡香”、歌手點播：“我要聽劉德華的歌曲”）、推薦（風格流派推薦：“來點搖滾”、随便聽聽推薦：“放歌”）。通過對使用者行為的分析來看，不同意圖類型下的歌曲對于推薦模型貢獻的權重是不同的，在模型中融入歌曲對應的意圖 attention，能更準确把握使用者的興趣。是以本文提出了一種基于多任務學習和負回報的深度召回模型。
二 方法
總體來說，由于近似最近鄰檢索算法的限制，我們的召回模型需要獨立地對使用者曆史行為序列進行編碼以生成使用者的每一步的向量表示，然後再和 Target Item 向量做内積運算，得到打分，模型基于 Self-Attention 的架構來實作，總體結構如下：
1 Input Representations
如前所述，為了模組化負向回報信号和使用者意圖類型信号，我們的模型引入了對 Play Rate 和 Intent Type 的表示。但初始資料集不包含這兩種信号，是以我們用 Train Set 1 來表示初始資料集，Train Set 2 表示帶有負向回報信号和使用者意圖類型信号的資料集，我們對它們做了統一的表示。總的來說，使用者曆史行為序列中的每個 Item 的表示由如下四部分構成：
1）Item Embedding
我們首先把每個 Item 嵌入到固定大小的低維向量中，Train Set 1 和 Train Set 2 共用一套 Item Vocabulary，不需要做區分：
其中，
為 Item 的 One-Hot 表示，
是 Item Embedding 矩陣，另外需要注意的是輸出層和輸入層共用一套 Item Embedding，這樣做的目的主要是節省顯存占用空間，因為推薦場景的 Item 數量是巨大的，而且有很多工作已經證明了這樣的做法對于模型性能影響不會很大[2]。
2）Position Embedding
對于行為序列任務，我們需要使用位置嵌入來捕獲行為序列中的順序資訊。我們采用不同于 Transformer 原論文[8]中的 sin 和 cos 方法，直接使用 Max Sequence Length 個 Embedding 來表示不同的位置。
3）Play Rate Embedding
播放完成率是使用者對于 Item 接受程度的一個重要回報，在天貓精靈上，對于不喜歡的歌曲，使用者通常會直接使用“下一首”指令将其切掉，這些歌曲的播放完成率就會比較低。播放完成率是一個值域在 [0, 1] 間的連續值，為了實作後面将要提到的連續值特征和離散值特征的互動，我們參照了[9]中方案，将 Play Rate 映射到了與 Item Embedding 相同的低維向量空間，具體來說，我們将 Play Rate Embedding 表示為：
是 Play Rate，
是随機初始化的 Embedding，
是最終得到的 Play Rate Embedding，由于我們 Train Set 1 資料隻有播放時長較高的歌曲，并且沒有播放完成率的資訊，是以對于 Train Set 1，我們固定所有 Play Rate 為 0.99：
4）Intent Type Embedding
使用者意圖類型表示了使用者進入這個 Item 的方式，比如在天貓精靈端，點播（使用者明确點播出的歌曲）和推薦（天貓精靈為使用者推薦的歌曲）就是兩種不同的 Intent Type（天貓精靈的實際場景中類型會更多），類似 Item 本身的表示，我們把 Intent Type 也映射到了一個固定的低維向量空間：
我們不知道 Train Set 1 資料中的 Intent Type，在此我們假設所有的 Train Set 1 資料的 Intent Type 全部為點播：
2 Factorized Embedding Parameterization
在推薦的任務中，Vocabulary Size 通常是巨大的，這導緻了我們無法使用太大的 Embedding Size 來表示 Item，否則顯存放不下，但很多使用 Transformer 的工作證明，提高 Hidden Size 可以有效的提升模型效果[10]，參照 ALBERT[11] 壓縮模型的方式，我們首先把 Item 的 One-Hot 向量映射到一個低次元的空間，大小為 ，然後再映射回高次元的空間再輸入Transformer，進而把參數量從 降低到了 ，當 時參數量會明顯減少。
3 Feedback-Aware Multi-Head Self-Attention
在獲得使用者行為序列的特征表示後，我們就可以準備建構使用者向量了，我們采用了注意力機制來編碼使用者的行為序列。如 Transformer[8] 中所述，注意力機制可以被描述為一個将 Query 和一系列的 Key-Value Pairs 映射到 Output 的函數，其中 Query，Key，Value 和 Output 都是向量，Output 被計算為 Value 的權重和，其中配置設定給每個 Value 的權重由 Query 與對應 Key 的打分函數計算，由于召回模型的限制，我們無法使用 Target Item 提前和使用者行為序列中的 Item 做運算，是以采用 Self-Attention 的方式，直接把使用者行為序列作為 Query，Key，Value 來進行計算。具體來說，我們使用了 Multi-Head Self-Attention 的方式來提升模型對于複雜互動的模組化能力：
是線性投影矩陣，
是 head 的數量。在經典的 Transformer 結構中，
由 Item Embedding 和 Position Embedding 構成，在我們的模型中，我們将外部資訊（播放完成率和使用者意圖類型）引入到 Attention 中來，我們稱之為 Feedback-Aware Attention，通過對這些資訊的引入，我們的模型就有能力結合使用者的回報資訊感覺使用者對于各個歌曲的不同的偏好程度了：
除此之外我們還參照 ALBERT[11]，嘗試了 Cross-layer Parameter Sharing 的方案，這種方案讓每層 Transformer Layer 全部共享一組參數，同樣量級（層數相同）下的 Transformer 采用該方案後實際上的效果是會有所下降的，但是參數量減少了很多，訓練速度也會快很多，對于推薦這種資料規模比較龐大的場景，采用這種政策可以在盡量節約訓練時間的前提下提升模型性能。
4 Sampled Softmax Loss For Positive Feedback and Sigmoid CE Loss For Negative Feedback
在獲得使用者的向量表示後，就可以定義多任務學習的目标了，由于之前我們已經統一了 Train Set 1 和 Train Set 2 的資料表示，是以這兩個任務可以放在一起進行聯合多任務訓練。具體來說，我們的任務類似于語言模型：給定前 個已經聽過的音樂，預測第 步使用者想要聽什麼音樂，我們根據播放完成率的高低将信号分成兩種（實際實作時會使用一個門檻值來區分），一種是 Positive Feedback，這種的優化目标是使其打分排序盡量靠前，另一種是 Negative Feedback，這種的優化目标是使其打分排序盡量靠後。
如下圖的左圖所示，如果隻做傳統的 Positive Feedback Loss 的話，我們的模型可以拉近使用者向量和喜歡的 Item（正向樣本）的距離并拉大其和未觀測 Item 的距離，但是不喜歡的 Item（負向樣本）的距離可能并不會被拉開，我們希望我們的模型可以向右圖一樣，在做到上述特性的同時，拉大使用者向量與不喜歡的 Item 的距離：
是以我們使用了 Positive Feedback 和 Negative Feedback 結合的優化目标：
對于 Positive Feedback，我們使用 Sampled Softmax Loss 來優化。在之前的很多工作中[12-13]，Sampled Softmax Loss 已經被證明非常适用于大規模推薦召回模型，它的定義如下：
在使用 Tensorflow 實作的時候，sampled_softmax 預設使用的采樣器為 log_uniform_candidate_sampler（TF 版 Word2Vec 基于此實作），它基于 Zipfian 分布來采樣，每個 Item 被采樣的機率隻跟他詞頻的排序相關，采樣機率不是詞的頻率，但是推薦中的商品和 NLP 中的詞可能不同，是以我們嘗試了另外兩個采樣器：
- uniform_candidate_sampler：使用均勻分布來采樣
- learned_unigram_candidate_sampler：這個分布會動态統計訓練過程中的詞表，然後計算機率并進行采樣
在我們的實驗中，learned_unigram_candidate_sampler 可以實作最好的效果。除此之外，我們發現了類似[2]中的結論，負采樣的數量是一個比較重要的參數，在顯存允許的情況下，适當調高負采樣的數量可以有效的提升模型收斂效果。
對于 Negative Feedback，我們直接使用 Sigmoid Cross Entropy Loss 來優化，将播放完成率低的 Item 全部看成負例，使其打分盡量低：
最終的總 Loss 則為兩者的加和：
三 實驗
1 分布式訓練
推薦場景的詞表大小和資料量通常是巨大的，是以我們采用了 TensorFlow 中的 ParameterServer 政策來實作分布式訓練的代碼。調優過程中也積累了一些經驗：
1）需要注意 Embedding 分片的問題，一個是 tf.fixed_size_partitioner 中的 size，另外一個是embedding_lookup 中的 partition_strategy，需要保持他們在 Training 和 Inference 過程中的設定是相同的。
2）sample_softmax 中的代碼需要根據自己的場景來做優化，比如在我們的場景中，同一個 batch 中的重複 sample item 比例比較高，把裡面的 embedding_lookup 加上 unique，可以大幅提升訓練速度。
3）靈活使用 Mask 機制，可以有效的實作各種不同的 Attention 政策。
2 實驗結果
離線實驗的名額采用 R@N，即打分排序的前 N 項結果包含Target Item 的比例，對于正向樣本，名額稱為 POS@N，我們希望這個值越高越好，對于負向樣本，名額稱為 NEG@N，我們希望這個值越低越好。由于篇幅限制，我們隻列出一組主要的實驗結果，這組實驗驗證了 Multitask Learning 和 Negative Feedback 的效果，我們在其他政策都采用上述最優的情況下（比如優化器，采樣方法等），a 采用傳統 DM 方式訓練，隻保留完播率較高的正回報 Item 來建構行為序列，b 在 a 的基礎上加入 Play Rate、Play Type 特征，c 在 b 的基礎上再加入負向回報信号進行多任務訓練：
可以看出，加入回報信号（Play Rate）和歌曲點播 query 意圖信号（Intent Type）後，b 的效果要優于 a，再加入 Negative Feedback 目标進行 Multitask Learning 後，c 可以保證 POS@N 微小變化的情況下明顯降低 NEG@N。
我們在猜你喜歡的線上場景中也證明了新方法的有效性，和基于 DM 原方案的分桶相比，新模型（DM with Play Rate/Intent Type and NEG MTL）分桶的人均播放時長提高了 +9.2%；同時該方法已經應用于天貓精靈推薦的更多場景中并取得了不錯的收益。
參考文獻:
[1] Covington P, Adams J, Sargin E. Deep neural networks for youtube recommendations[C]//Proceedings of the 10th ACM conference on recommender systems. ACM, 2016: 191-198.
[2] Hidasi B, Karatzoglou A. Recurrent neural networks with top-k gains for session-based recommendations[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management. ACM, 2018: 843-852.
[3] Sun F, Liu J, Wu J, et al. BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer[J]. arXiv preprint arXiv:1904.06690, 2019.
[4] Li C, Liu Z, Wu M, et al. Multi-interest network with dynamic routing for recommendation at Tmall[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. ACM, 2019: 2615-2623.
[5] Johnson J, Douze M, Jégou H. Billion-scale similarity search with GPUs[J]. IEEE Transactions on Big Data, 2019.
[6] Paudel B, Luck S, Bernstein A. Loss Aversion in Recommender Systems: Utilizing Negative User Preference to Improve Recommendation Quality[J]. arXiv preprint arXiv:1812.11422, 2018.
[7] Zhao X, Zhang L, Ding Z, et al. Recommendations with negative feedback via pairwise deep reinforcement learning[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018: 1040-1048.
[8] Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need[C]//Advances in neural information processing systems. 2017: 5998-6008.
[9] Song W, Shi C, Xiao Z, et al. Autoint: Automatic feature interaction learning via self-attentive neural networks[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. ACM, 2019: 1161-1170.
[10] Devlin J, Chang M W, Lee K, et al. Bert: Pre-training of deep bidirectional transformers for language understanding[J]. arXiv preprint arXiv:1810.04805, 2018.
[11] Lan Z, Chen M, Goodman S, et al. Albert: A lite bert for self-supervised learning of language representations[J]. arXiv preprint arXiv:1909.11942, 2019.
算法學習 | 10+ 算法模拟題精解合輯
題目：給出一個長度為 n 的數組，和一個正整數 d，每次可以選擇其中任意一個元素 a[i] 将其變為 a[i] + d 或 a[i] - d，這算作一次操作。請将所有的元素全部變成相等元素，如果有解，請輸出最小操作次數，如果無解請輸出 -1。
解題： 首先判斷無解的情況，可以發現：a[i]，a[i]+d, a[i]-d 在模 d 情況下的餘數不會發生改變，是以如果原數組中存在任意兩個數字它們對 d 取餘結果不同，那麼此時無解。
識别下方二維碼檢視更多算法題及精解：