本文作者：branxu，騰訊 CDG 應用研究員
2018 年和 2019 年騰訊算法廣告大賽都可以看做推薦系統問題。這類問題最重要的特徵是點擊率，最大的難點是冷啟動。文本結合 2018 年比賽亞軍方案和 2019 年比賽冠軍方案中的一部分技巧，提出了一種新的點擊率建模方案，試圖解決一部分冷啟動問題。該方案複雜度很低，實現簡單，效果好。
問題介紹
推薦系統和廣告算法中，對於新用戶或者新內容，記錄很少，如果我們直接將歷史點擊率作為特徵，會存在問題。比如
1，新用戶 A 有 2 條瀏覽記錄，1 次點擊，轉化率 50%,
2，老用戶 B 有 2 條瀏覽記錄，0 次點擊，轉化率 0%。
A 和 B，只因為 1 次點擊，點擊率就相差 50%，這不合理。顯然，問題出現在 A,B 用戶都是新用戶，他們的歷史數據太少了，歷史點擊率自然不準。
這就像我告訴同事小明：我王者榮耀賊溜，后羿 100%勝率。實際上，我只打了兩盤后羿，其中一盤還是新手教學。同事小明可能會多嘴問一句：你打了幾盤后羿啊？但是模型不會，沒有專門調整過的模型只會默默接受我后羿 100%勝率的設定，然後給我匹配一堆王者選手。這就是冷啟動問題。
解決思路
已經 9102 年了，我們人類星球上的人工智能模型的計算能力還可以，但還是太“老實”，太“傻”。所以，解決上述問題的方法就是：直接把預測結果告訴模型，別讓模型自己去算，去猜。這顯然是句廢話，不過翻譯成學術語言就不是了：給模型輸入概率，而不是頻率。
所以最好的辦法是，利用用戶的歷史點擊率，去計算用戶之後點擊的概率，再將這個概率輸入模型。通過用戶 A 的歷史點擊頻率去計算用戶 A 之後點擊的概率，聽起來不錯，但又不太可行，因為這裡的信息太少了。好在我們有所有數據，用所有用戶的歷史點擊頻率去預測用戶 A 之後點擊的概率，似乎有點希望。
貝葉斯平滑
新用戶 A 只有兩條瀏覽記錄，模型還不夠認識用戶 A，如何辦？如果 A 用戶能多幾次瀏覽記錄就好了。可是去哪裡找那不存在的瀏覽記錄呢？我們可以假定用戶 A 和其他所有用戶是差不多，用其他用戶的歷史數據“構造”一些瀏覽記錄，作為新用戶 A 的瀏覽記錄。這裡“構造”出來的記錄，可以理解成先驗知識。當我們見過了很多用戶之後，即使不認識新用戶 A，也會對 A 有個大概的“預期值”。貝葉斯平滑就是這樣工作的，它通過“觀測”所有用戶數據，為新用戶確定一個初始預期值，這個預期值就是“先驗”。而用戶 A 自己真實的行為所產生的“預期值”，被稱之為後驗。最後我們將先驗和後驗綜合起來，計算一個貝葉斯平滑修正過的點擊率。
貝葉斯平滑的推導比較繁雜，也不是本文的重點，有興趣的話，可以查看：
https://www.jianshu.com/p/c98f3bb48b97
有了貝葉斯平滑，我們可以對點擊率進行修正，讓歷史轉化率這個頻率值，更加接近用戶真實點擊的概率。
連續值與深度學習
通過上文，我們可以得到一個貝葉斯平滑後的點擊率，那麼直接把點擊率特徵輸入深度神經網絡，問題不就解決了嗎？
只能說，對於大多數普通特徵也許可以這樣，但是轉化率這種強特徵，這樣做太浪費了。原因如下：
近年來，推薦系統相關的深度網絡模型層出不窮：
DeepFM，Wide & Deep，Deep & Cross Network，Attentional Factorization Machine，xDeepFM，Deep Interest Network，AutoInt…
這些模型都有個共同特點：擁有 FM 層或者 Attention 層（Wide & Deep 除外）。FM 層和 Attention 層都能有效進行特徵交叉，從而提高了模型精度。FM 層和 Attention 層的輸入都是向量，所以這些模型基本都需要讓特徵先進入嵌入層，變成一個向量，再參與後面的特徵自動交叉。
這時候，連續值特徵就會很尷尬，他們無法像離散值特徵一樣進入嵌入層，從而無法參與後面的特徵交叉，效果大打折扣。
目前將連續值轉化成向量的解決方案主要有以下幾種：
第一種方式是對連續值特徵做離散化分桶，之後將分桶後的離散值輸入到嵌入層到的嵌入向量。分桶本質上就是做四捨五入近似，等距分桶是直接四捨五入，等頻分桶是排序後對序做四捨五入，這兩種方法會影響精度。因為近似必然會損失信息。
第二種方式也是離散化，不過是有監督的離散化。它借鑑了決策樹的思路，枚舉所有分割點，找到一組分割點，使分割後的數據組的信息熵增益最大。這裡有個比較 trick 的做法：直接用一部分數據訓練一個 lightGBM 模型，然後解析模型文件，裡面記錄了 lightGBM 模型選出來的最優分割點，直接可以用。需要注意的是，有監督的離散化用到了數據的標籤，所以可能會帶來數據穿越。為了避免這個問題，建議訓練 lightGBM 模型的數據和深度學習的數據不要重合。
第三種方法來自 AutoInt 論文，非常有趣。它先用前面兩種方法對連續值特徵 Z 做離散化，得到 Z'，之後將 Z'輸入嵌入層得到嵌入向量 emd(Z')，最後用嵌入層的輸出 emd(Z')再乘以 Z。想法很巧妙：既然離散化後的特徵會損失精度，那麼就將原始特徵再一次輸入模型。
最後一種方法來自 2019 年比賽冠軍成員郭大，下文重點介紹。
鍵值儲存網絡
該方法靈感來自 NLP 頂會 ACL2016 的論文《Key-Value Memory Networks for Directly Reading Documents》。
文章為深度網絡引入了記憶模塊，原本是用來解決 QA 問答問題的，不過簡單改進後，可以用來將構造續值特徵的專屬嵌入層。（目前推薦系統很多好的 idea，都來自 NLP 和 CV 領域。所以，學習推薦系統或者廣告算法，瞭解 NLP 和 CV 領域的前沿研究成果也很重要）
不多說，鍵值儲存網絡(Key-Value Memory Networks)結構如下：
圖一:Key-Value Memory Networks
鍵值儲存網絡與普通網絡最大的區別是可以方便的引入先驗知識，即圖中的 Knowledge Source 模塊。該模塊相當於一個內嵌在神經網絡中的“搜索引擎”，對於輸入的任何一個 Question，先在 Knowledge Source 中做一次搜索，然後將搜索結果也作為神經網絡的輸入。為什麼說它是內嵌在神經網絡中呢？因為搜索結果與 Question 之間存在一個相似度，這個相似度的計算是依賴神經網絡的，它可以享受梯度下降帶來的優化。
模型主要分為三個部分：Key hashing,Key addressing 和 Value reading。
Key hashing
圖二:Key hashing
Key hashing 是離線計算好的。它的輸入是 Question 和 Knowlege
Source。Question 是 QA 問答問題中的提問，比如“如何打開企業微信”。Knowlege
Source 是一個類似維基百科的數據庫，裡面記錄了各種詞彙，實體和知識。
Key
hashing 就是把所有 Question 裡面的常用詞（出現次數大於某個閾值）挑出來，然後給這些詞一個編號，組成一個字典。字典的 key 是這些常用詞，value 是常用詞編號。
Key addressing
圖三:Key addressing
Key addressing 就是去 Knowlege Source 裡面尋找 Question 中的詞彙和短語。比如找到了："企業","微信","企業微信","如何"等詞。Question“如何打開企業微信”會有一個訓練出的 Question embedding 值，同時，"企業","微信","企業微信","如何"等詞也都有各自的 embedding 值，被稱為 Key embeddings。用 Question embedding 分別乘以每一個 Key embeddings，再經過一次 Softmax，就可以得到 Question 與各個 Key 的相似度權重 P。具體公式如下：
Key hashing 和 Key addressing 用上述模型解決了一個問題：Question 與 Knowlege Source 中相近詞彙的相關性。比如對於 Question"如何打開企業微信"，可以得到一個相似度權重 P 字典{"企業":0.4,"微信":0.2,"企業微信":0.3,"如何":0.1}。
Value reading
圖四:value reading
value reading 是鍵值儲存網絡的核心部分。還記得我們上文有個 key embedding，對應的，Key-Value Memories 還有個 value embedding，它的輸入是 Knowlege Source 裡面每個詞的 id。對 value embedding 以上文的 p 為權重加權求和，便得到我們需要的向量 o。
優勢
和傳統的深度神經網絡比，鍵值儲存網絡可以方便的讓先驗知識以鍵值對的方式輸入模型(圖中的 Key-Value Memories)。這意味著，神經網絡的輸入值可以直接是多個鍵值對組成的字典。
舉個例子，傳統神經網絡只能將數字作為特徵，比如:身高(173),體重(90)或者年齡(25)。而鍵值儲存網絡可以將興趣 ({‘籃球’:0.5,'足球':0.2,'檯球':0.1}) 作為特徵，直接輸入給模型。字典特徵的 key 是實體，使用 LabelEncoding 後可以進入嵌入層，value 是其權重。鍵值儲存網絡可以方便的將輸入的字典特徵轉化成上文的向量 o。
連續值鍵值儲存網絡
回到最開始的問題，我們想找到一個將連續值轉成向量的方法，但上文卻一直在講鍵值儲存網絡，為什麼？
因為鍵值儲存網絡實現了字典特徵->向量的轉換，我們希望的是連續值->向量的轉換。所以，藉助鍵值儲存網絡，只需要再實現連續值->字典特徵的轉化就大功告成了。連續值->向量很難，但是連續值->字典特徵方式很多，易於實現。
假定有了連續值->字典特徵的轉化，那麼總體架構和鍵值記憶網絡基本一致，如下圖所示：
圖五:連續值鍵值儲存網絡
連續值->字典特徵的轉化即圖中的 Key-Value Memory,如何實現這部分應當結合具體的業務場景，數據分佈。這裡先介紹下郭大的做法吧：
- 將連續值特徵縮放至[0,1]區間
- 在[0,1]區間找 n 等分點，比如 n=6 時，就是(0, 0.2, 0.4, 0.6, 0.8, 1)
- 依次計算連續值 x 與 n 等分點的距離，比如 x=0.3，n=6，就是(0.3, 0.1, 0.1, 0.3, 0.5,0.7)，之後構造字典特徵{0:0.3, 1:0.1, 2:0.1, 3:0.3, 4:0.5, 5:0.7}
- 對字典特徵的 value 取倒數後 softmax，具體相似度公式如下：
python 偽代碼: {i: softmax(1/(q-i/n+1e-15)) for i in range(n+1)},其中 q 為浮點數特徵，n 為等分點個數。這裡加上 1e-15 是為了防止 q 正好等於某個等分點時，分母為 0。
郭大的方法將字典特徵的 key 定義為[0,1]區間的等分點，之後對浮點數與各等分點的距離做取倒和 softmax 變換。取倒是為了保證浮點數越接近等分點，權重越大。softmax 變換是為了保證所有權重之和為 1。
實踐中發現，當 q 與某個等分點較接近時，value 中除該等分點對應的值外，都非常接近 0。這主要是因為 softmax 函數會指數級加大距離間差異。
為了緩解這種情況，我在最近的代碼裡使用如下相似度公式：
該公式取距離平方反比為權值，之後將權值縮放至總和為 1。用該公式得到的權值比較"分散",可以讓模型更好的學習那些冷門分位數的嵌入表示。
概率分佈特徵
截至目前，文章講了點擊率特徵的貝葉斯平滑，以及如何在不損失精度的情況下把浮點數特徵（比如點擊率特徵）輸入神經網絡。
如果把點擊率看成一個普通浮點數，問題已經解決。但是點擊率並不普通，點擊率可以被認為是用戶是否點擊廣告這個隨機變量的期望值。
用戶是否點擊廣告實際上是一個隨機變量，點擊率就是用這個隨機變量的期望值作為特徵，去描述它。這樣做實際上是用一個值去代表一個複雜的分佈，必然會帶來信息損失。舉個例子，A 用戶瀏覽 20 次，點擊 10 次。B 用戶瀏覽 100 次，點擊 50 次。A 和 B 的點擊率都是 50%，但是他們是否點擊廣告的概率分佈卻大不一樣：
圖六:用戶A和用戶B否點擊廣告的概率分佈
雖然 AB 兩用戶點擊率都是 50%，但是 B 用戶點擊次數更多，所以 B 用戶的點擊率更置信，B 用戶的概率分佈也更集中。這就體現出點擊率特徵的弊端，它只能描述概率分佈的期望，無法完整描述概率分佈。
我們希望完整描述概率分佈給模型，我們希望精確區分出點擊率很相似但總瀏覽數差異很大的那群人。這個問題可以被定義為如何向模型描述一個概率分佈。
用戶是否點擊廣告的概率分佈是連續的，用概率密度函數可以表示。可以對概率密度函數函數進行分段近似，分別統計它在[0,0.1),[0.1,0.2),[0.2,0.3),[0.3,0.4)…區間的平均值，用這些平均值來表示這個分佈。形式如下：
{[0,0.1):0.1,[0.1,0.2):0.2,[0.2,0.3):0.4,[0.3,0.4):0.4,…}
該形式其實也是字典特徵，它的 key 是區間，value 是點擊率這個隨機變量落在各區間的概率。如此一來，可以直接將這個字典特徵輸入鍵值儲存網絡。這種方式利用隨機變量的概率分佈，跳過了連續值->字典特徵這一步，直接做隨機變量->字典特徵，避免了上文中的人工設計相似度公式。
如果構造的特徵可以被看做是隨機變量，那麼就可以利用數學工具得到他的概率分佈，概率分佈分段近似得到字典特徵，最後將字典特徵輸入鍵值儲存網絡。
代碼實現與複雜度分析
上文的方法在代碼實現上很容易，用途廣泛（任何使用了嵌入層的網絡都可以用）。
代碼主要有四部分：貝葉斯平滑，隨機變量->字典特徵的轉換，浮點數>字典特徵的轉換和鍵值儲存網絡。
相關第三方庫
<code>import numpy as npimport randomimport pandas as pdimport scipy.special as specialfrom sklearn.model_selection import StratifiedKFold,KFoldfrom scipy import statsfrom collections import OrderedDict, namedtuplefrom itertools import chainfrom tensorflow.python.keras.initializers import RandomNormalfrom tensorflow.python.keras.layers import Embedding, Input, Flattenfrom tensorflow.python.keras.regularizers import l2/<code>
貝葉斯平滑
<code>class BayesianSmoothing(object): def __init__(self, alpha, beta): self.alpha = alpha self.beta = beta def sample(self, alpha, beta, num, imp_upperbound): sample = np.random.beta(alpha, beta, num) I = [] C = [] for clk_rt in sample: imp = random.random() * imp_upperbound clk = imp * clk_rt I.append(int(imp)) C.append(int(clk)) return I, C def update(self, imps, clks, iter_num, epsilon): for i in range(iter_num): new_alpha, new_beta = self.__fixed_point_iteration(imps, clks, self.alpha, self.beta) if abs(new_alpha-self.alpha)<epsilon>/<code>
隨機變量（beta 分佈）->字典特徵
<code>def beta_ppf(alpha, beta, dim): return stats.beta(alpha, beta).ppf([x/(dim+1) for x in range(0,dim+2)])def beta_prior_feat_2_vec(data, key_col, count_col, sum_col, dim): data_simple = data.drop_duplicates([key_col],keep='last') bs = BayesianSmoothing(1, 1) bs.update(data_simple[count_col].values, data_simple[sum_col].values, 1000, 0.0000000001) if np.isnan(bs.alpha) or np.isnan(bs.beta): bs.alpha, bs.beta = 0, 0 data[key_col+'_beta_cdf_value'] = list( map(lambda x,y:beta_cdf(x,y,dim), data[sum_col]+bs.alpha, data[count_col]-data[sum_col]+bs.beta)) data[key_col + '_beta_ppf_value'] = list( map(lambda x,y:beta_ppf(x,y,dim), data[sum_col] + bs.alpha, data[count_col] - data[sum_col] + bs.beta)) data[key_col + '_beta_key'] = [np.array([i for i in range(dim)]) for _ in range(data.shape[0])] return data[key_col+'_beta_cdf_value'].values, data[key_col + '_beta_ppf_value'].values, data[key_col + '_beta_key'].values/<code>
浮點數->字典特徵
<code>def numpy_softmax(x): orig_shape = x.shape if len(x.shape) > 1: exp_minmax = lambda x: np.exp(x - np.max(x)) denom = lambda x: 1.0 / np.sum(x) x = np.apply_along_axis(exp_minmax,1,x) denominator = np.apply_along_axis(denom,1,x) if len(denominator.shape) == 1: denominator = denominator.reshape((denominator.shape[0],1)) x = x * denominator else: x_max = np.max(x) x = x - x_max numerator = np.exp(x) denominator = 1.0 / np.sum(numerator) x = numerator.dot(denominator) assert x.shape == orig_shape return xdef float2vec(float_feat, bar_num = 20, method = 'gravitation'): float_feat = (float_feat-np.min(float_feat))*1.0 / np.max(float_feat-np.min(float_feat)) key_array = np.array([[i*1.0/(bar_num + 1) for i in range(bar_num + 1)]] * len(float_feat)) value_array = None if method == 'gravitation': value_array = 1/(np.abs(key_array - float_feat[:,None] + 0.00001))**2 value_array = value_array/np.sum(value_array,axis=1, keepdims=True) if method == 'sofmax': value_array = 1 / np.abs(key_array - float_feat[:, None] + 0.00001) value_array = numpy_softmax(value_array) return key_array,value_array/<code>
網絡結構
<code>def get_varlen_multiply_list(embedding_dict, features, varlen_sparse_feature_columns_name_dict): multiply_vec_list = [] print(embedding_dict) for key_feature in varlen_sparse_feature_columns_name_dict: for value_feature in varlen_sparse_feature_columns_name_dict[key_feature]: key_feature_length_name = key_feature.name + '_seq_length' if isinstance(value_feature, VarLenSparseFeat): value_input = embedding_dict[value_feature.name] elif isinstance(value_feature, DenseFeat): value_input = features[value_feature.name] else: raise TypeError("Invalid feature column type,got",type(value_feature)) if key_feature_length_name in features: varlen_vec = SequenceMultiplyLayer(supports_masking=False)( [embedding_dict[key_feature.name], features[key_feature_length_name], value_input]) vec = SequencePoolingLayer('sum', supports_masking=False)( [varlen_vec, features[key_feature_length_name]]) else: varlen_vec = SequenceMultiplyLayer(supports_masking=True)( [embedding_dict[key_feature.name], value_input]) vec = SequencePoolingLayer('sum', supports_masking=True)( varlen_vec) multiply_vec_list.append(vec) return multiply_vec_listclass SequenceMultiplyLayer(Layer): def __init__(self, supports_masking, **kwargs): super(SequenceMultiplyLayer, self).__init__(**kwargs) self.supports_masking = supports_masking def build(self, input_shape): if not self.supports_masking: self.seq_len_max = int(input_shape[0][1]) super(SequenceMultiplyLayer, self).build( input_shape) # Be sure to call this somewhere! def call(self, input_list, mask=None, **kwargs): if self.supports_masking: if mask is None: raise ValueError( "When supports_masking=True,input must support masking") key_input, value_input = input_list mask = tf.cast(mask[0], tf.float32) mask = tf.expand_dims(mask, axis=2) else: key_input, key_length_input, value_input = input_list mask = tf.sequence_mask(key_length_input, self.seq_len_max, dtype=tf.float32) mask = tf.transpose(mask, (0, 2, 1)) embedding_size = key_input.shape[-1] mask = tf.tile(mask, [1, 1, embedding_size]) key_input *= mask if len(tf.shape(value_input)) == 2: value_input = tf.expand_dims(value_input, axis=2) value_input = tf.tile(value_input, [1, 1, embedding_size]) return tf.multiply(key_input,value_input) def compute_output_shape(self, input_shape): return input_shape[0] def compute_mask(self, inputs, mask): if self.supports_masking: return mask[0] else: return None def get_config(self, ): config = {'supports_masking': self.supports_masking} base_config = super(SequenceMultiplyLayer, self).get_config() return dict(list(base_config.items()) + list(config.items()))/<code>改進後的鍵值網絡與連續值離散化後接入嵌入層的方法相比，沒有增加訓練參數，只是多做了一次向量加權求和，多增加了一些權重的輸入。另一方面，改進後的鍵值網絡中，分位數或者概率區間個數是可以人工調整的，當分位數或者概率區間個數為 1 時，該方法就退化成離散化後接入嵌入層。
閱讀更多 騰訊技術工程 的文章
