本文作者：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 时，该方法就退化成离散化后接入嵌入层。
閱讀更多 騰訊技術工程 的文章
