4.1-交叉结构

FTRL是如何保证“在线学习”的稳定性的？

FTRL的前身是FTL（Follow The Leader）。FTL其实不单指某一个算法，而是Online Learning的一种思路，即：为了减少单个样本的随机扰动，第t步的最优参数，不是单单最小化第t步的损失，而是让之前所有步骤的损失之和最小。

FTRL是如何保证解的稀疏性的？

FTRL是在FTL的基础上添加了正则项，如下所示：

• 表示被第条样本优化之后的模型权重。
• 表示第条样本在权重下计算得到的损失。
• 表示对权重的正则项。

但是，公式中的不容易求解。因此，我们需要引入代理损失函数。 FTRL采用的代理损
失函数如公式所示:

• 其中表示由第个样本回代得到的梯度向量，所以表示第个样本的梯度向量之和。由于Online Learning的随机性较大，使用累计梯度可以避免使用单样本梯度带来的较大抖动，这也是FTL思想的体现。
• 主要是为了推导公式方便而设立的。其中，ng代表第s步的步长。
• 代表前代第s个样本时，模型所使用的权重。同时也表示被前s-1个样本优化过后的权重。
• 代表模型被前t个样本优化后的权重，是我们的求解目标。其优化结果就是，将被用于前代第个样本。
• 一项， 相当于一个正则项，要求当前正在被优化的权重w， 与它的每个历史版本不能相距过远。这是为了防止模型只一味迎合新样本，而损害对前边老样本的拟合能力。
• 是传统的L1正则，代表传统的L2正则。

省去推导过程，最终可以给出解：

z_{t,i}=g_{1:t,i}-\sum_{s=1}^t \sigma_s w_{s,i} \\ \\ \\ w_{t+1,i} = \begin{cases} 0 ,|z_{t,i}|≤ \lambda_1\\ -\frac{1}{\lambda_2+\sum_{s+1}^i \sigma _s}(z_{t,i}-sgn(z_{t,i})\times\lambda _1),|z_{t,i}＞\lambda_1|\end{cases}

• 下标t表示第t步，也就是模型针对第t个样本的训练过程。下标i表示一个向量的第个元素。所以，表示第个特征在第步时的权重。
• 是为了推导方便而引入的中间变量。其中的定义参考上一个公式。
• 特别当时，第个特征的新权重会被直接设置成0，这就是FTRL算法能够产生稀疏解的原因。
• sgn代表符号函数。

FTRL是如何解决高维稀疏特征受训机会不均匀的问题的？

因为推荐系统中特征超级稀疏，不同特征在训练数据中的分布不均，导致不同特征受训的机会严重不均等。为此，FTRL放弃使用统一的步长，而是为每个特征独立设置步长(Per-oordinate LearningRate)，如公式所示：

• 代表由第s个样本计算出来的、针对第个特征的梯度。
• 频繁出现的特征，很多样本都贡献了对它的梯度，累积得比较大，因此步长会小一些。不会导致已经学得很好的剧烈变化；
• 较少出现的特征，之前积累的还比较少，步长会大一些。因为对超级稀疏的特征，每个样本都非常珍贵，大步长有利于对这些样本的应用。
• 和是两个超参数。

FM相对LR的优势在哪里？

FM的前身就是LR，担心只包含一阶特征表达能力弱，而加入了二阶特征交叉，

• 代表输入样本中第i个特征对应的特征值。
• 代表要学习的偏置(bias) 项。
• 代表一阶特征的权重。
• 代表二阶特征交叉的权重。

但是，引入二阶特征交叉后，也增加了训练难度：

• 假设一共有n个特征，所有特征之间两两交叉，只一项就引入了个要训练的参数。而要将这么多的参数训练好，就需要更多的数据，否则就容易过拟合（overfitting）。
• 看公式可知，只有遇到和都不为0的样本，才得到一次训练机会。但是前面我们说了，推荐系统的一大特点就是类别特征高维稀疏，符合条件的样本少之又少，导致得不到充分训练。

为了解决以上难题，业界提出了FM算法，见公式：

• 模型对每个特征，除了要学习它的一阶权重，还要再多学习一个Embedding，也就是公式x中的。
• 而和共现特征之前的权重 等于对应特征的Embedding的点积，即。

FM的想法虽然简单，但作用巨大

• 要学习的参数由变成了，是每个特征Embedding的长度，大大减少了学习的参数量。
• 只要的样本都能训练，的样本都能训练，也就都间接训练了。 数据利用率更高，训练更加充分。

除了使训练变得更容易，FM还提升了模型的“扩展性"：

• 如果还使用"手动二阶交叉的LR" ， 对于不曾在训练样本中出现过特征组合，对这一特征对前面的权重无从学起，只能赋成0，也就是剥夺了小众模式发挥作用的机会。
• 如果用FM模型，虽然这种组合从来没有在训练样本中共现过，但是和在训练样本中都单独出现，因此模型训练好了和。因此在预测时，FM能够预估出；从而给小众模式提供了一个发挥作用的机会。

FM对所有特征两两交叉，岂不是的复杂度？

观察公式，我们发现二阶交叉的部分仍然是的复杂度，并不实用。而且实际场景中以稀疏类别特征为主，不是0就是1。因此，公式x可以等价变换成更加实用的公式:

• 公式中的代表两个向量按位相乘。
• reducesum表示将一个向量所有位置上的元素相加。
• I是某个样本中所有非零特征的集合。

相比平方级的复杂度，上述公式拥有线性复杂度，而且只需要遍历样本中的非零特征。得益于推荐系统中的特征超级稀疏，一个样本包含的非零特征非常有限，因此根据公式训练与预测FM的速度都非常快。

请简要说一下记忆能力和扩展能力以及他们的缺陷。

记忆能力（Memorization）可以被理解模型直接学习并利用历史数据中物品或者特征的“共现频率”的能力。像逻辑回归、协同过滤等简单模型的结构较为简单,原始数据往往可以直接影响推荐结果,产生类似于“如果点击过A,就推荐B”这类规则式的推荐,相当于模型直接记住了历史数据的分布特点,并利用这些记忆进行推荐。即一旦发现了“强特征”,相应的权重会在模型(例如逻辑回归)训练过程中被调整的非常大,就实现了对这个特征的记忆。

通过一系列人工的特征叉乘（cross-product）来构造这些非线性特征，捕捉sparse特征之间的高阶相关性，即“记忆” 历史数据中曾共同出现过的特征对。

典型代表是LR模型，使用大量的原始sparse特征和叉乘特征作为输入，很多原始的dense特征通常也会被分桶离散化构造为sparse特征。这种做法的优点是模型可解释高，实现快速高效，特征重要度易于分析，在工业界已被证明是很有效的。

Memorization存在一些缺点：

• 需要更多的人工设计
• 可能出现过拟合。可以这样理解：如果将所有特征叉乘起来，那么几乎相当于纯粹记住每个训练样本，这个极端情况是最细粒度的叉乘，我们可以通过构造更粗粒度的特征叉乘来增强泛化性；
• 无法捕捉训练数据中未曾出现过的特征对。泛化能力较差，若两个特征共同出现的频次是0，模型训练后的对应权重也将是0；

Generalization扩展能力
sparse特征学习低维的dense embeddings 来捕获特征相关性，学习到的embeddings 本身带有一定的语义信息。可以联想到NLP中的词向量，不同词的词向量有相关性，因此文中也称Generalization是基于相关性之间的传递。这类模型的代表是DNN和FM。他的优点是需要更少的人工参与，对历史上没有出现的特征组合有更好的泛化性

Generalization也存在一些缺点：

在推荐系统中，当user-item matrix非常稀疏时，例如有和独特爱好的users以及很小众的items，NN很难为users和items学习到有效的embedding。这种情况下，大部分user-item应该是没有关联的，但dense embedding 的方法还是可以得到对所有 user-item pair 的非零预测，因此导致 over-generalize并推荐不怎么相关的物品。此时Memorization就展示了优势，它可以“记住”这些特殊的特征组合。
Memorization根据历史行为数据，产生的推荐通常和用户已有行为的物品直接相关的物品。而Generalization会学习新的特征组合，提高推荐物品的多样性。

什么样的特征进Deep侧？什么样的特征进Wide侧？

Deep侧对类别特征使用了Embedding以扩展它们的内涵，再加上DNN对特征进行高阶隐式交叉，大大增强了模型的"扩展性"和推荐系统的"多样性"，有利于满足低频、小众、个性化的用户需求。
Wide侧的LR不必像单独使用时那样大而全，喂入其中的都是一些被先验知识认定非常重要的精华特征。主要是一些人工设计的交叉、共现特征，比如"用户喜欢军事类，而当前视频的标签是坦克"。另外，影响推荐系统的bias特征，比如position bias,只能喂入Wide侧，避免与其他真实特征交叉。

Wide侧側发挥LR"强于记忆"的优势，把那些在训练数据中高频、大众的模式牢牢记住。此外, Wide侧的另一个作用是防止Deep侧过分扩展而影响预测精度，起到一个类似"正则化的作用。

Wide&Deep在训练的时候采用了Joint Training，有什么好处？

联合训练（Joint Training）和集成（Ensemble）是不同的，集成是每个模型单独训练，再将模型的结果汇合。相比联合训练，集成的每个独立模型都得学得足够好才有利于随后的汇合，因此每个模型的model size也相对更大。而联合训练的wide部分只需要作一小部分的特征叉乘来弥补deep部分的不足，不需要 一个full-size 的wide 模型。
在论文中，作者通过梯度的反向传播，使用 mini-batch stochastic optimization 训练参数，并对wide部分使用带L1正则的Follow- the-regularized-leader (FTRL) 算法，对deep部分使用 AdaGrad算法。

论文里作者是如何应用wide&deep来做推荐的？

Google Play商店的app推荐中，当一个user访问Google Play，会生成一个包含user和contextual信息的query，推荐系统的精排模型会对于候选池中召回的一系列apps（即item，文中也称 impression）进行打分，按打分生成app的排序列表返回给用户。Deep&Wide对应这里的精排模型，输入包括<user，contextual，impression>的信息，表示用户下载了impression app，打分即 。
实验的Deep&Wide模型结构如下：

实验细节

• 训练样本约5000亿
• Categorical 特征（sparse）会有一个过滤阈值，即至少在训练集中出现m次才会被加入
• Continuous 特征（dense）通过CDF被归一化到 [0,1] 之间
• Categorical 特征映射到32维embeddings，和原始Continuous特征共1200维作为NN输入
• Wide部分只用了一组特征叉乘，即被推荐的app ☓ 用户下载的app
• 线上模型更新时，通过“热启动”重训练，即使用上次的embeddings和模型参数初始化

Wide部分设置很有意思，作者为什么这么做呢？结合业务思考，在Google Play商店的app下载中，不断有新的app推出，并且有很多“非常冷门、小众”的app，而现在的智能手机user几乎全部会安装一系列必要的app。联想前面对Memorization和Generalization的介绍，此时的Deep部分无法很好的为这些app学到有效的embeddding，而这时Wide可以发挥了它“记忆”的优势，作者在这里选择了“记忆”user下载的app与被推荐的app之间的相关性，有点类似“装个这个app后还可能会装什么”。对于Wide来说，它现在的任务是弥补Deep的缺陷，其他大部分的活就交给Deep了，所以这时的Wide相比单独Wide也显得非常“轻量级”，这也是Joint training相对于Ensemble的优势。

Wide & Deep论文原文中说，训练Wide & Deep侧分别使用了两种优化器，你觉得有哪些道理

wide部分是用ftrl做的优化，wide部分可以看做传统的lr，用ftrl优化可以得到稀疏权重，精度也不错，大大压缩了模型的权重，也压缩了特征向量的维度，可以减少特征数量，降低计算复杂度。从而降低serving的复杂度。wide&deep采用L1 FTRL是想让Wide部分变得更加稀疏。

deep部分是神经网络，输入要么是Age，#App Installs这些数值类特征，要么是已经降维并稠密化的Embedding向量，不需要考虑特征稀疏问题，稀疏也降低不了复杂度，可以通过正则化或者dropout，降低过拟合。所以Deep部分不存在严重的特征稀疏问题，自然可以使用精度更好，更适用于深度学习训练的AdaGrad去训练

DeepFM提出的动机是什么？

目前大部分的CTR预估模型“are biased to low- or high- order feature interaction”，例如FNN、PNN等NN模型专注于隐式的高阶特征相关性，而LR、FM等则专注于显式对得到低阶特征相关性，Google在2016年提出的Wide&Deep模型同时考虑了两者，但Wide部分需要人工参与特征工程。
DeepFM的动机非常直观，既希望考虑高/低阶的feature interaction，又想省去额外的特征工程。使用FM取代Wide的LR部分是一个可行的做法，当然这里LR可以基于先验构造更高阶的组合特征，而FM只考虑二阶。

DeepFM中FM层与NN层是共享特征Embedding的好处是什么？

• 1）降低模型复杂度，提升模型性能；
• 2）在embedding的学习中同时接收与来自“low & high order interaction”部分的反馈，从而学到更好的特征表示。

DeepFM相较于Wide&Deep有什么改进？为什么这么改进？

1. DeepFM对Wide&Deep模型的改进之处在于用FM替换了原来的Wide部分,加强了浅层网络部分特征组合的能力。
2. DeepFM中的FM层和隐藏层共享输入。这种共享输入使得DeepFM可以同时从原始特征中学习低阶特征交互和高阶特征交互,完全不需要执行特征工程。

Deep&Cross相比Wide&Deep作了哪些改进？Deep&Cross模型的Cross网络是怎么操作的？

Deep&Cross的主要思路是使用 Cross网络替代原来的Wide部分,从而增加特征之间的交互力度。模型结构如下,

DCN模型以一个嵌入和堆叠层(embedding and stacking layer)开始，接着并列连一个cross network和一个deep network，接着通过一个combination layer将两个network的输出进行组合。

位于模型结构图左侧的Cross网络使用多层交叉层对输入向量进行特征交叉。假设第层交叉层的输出向量为,那么第层的输出向量如下：

在每一层的都保留了输入向量,且增加了一个n维的权重向量,在Wide&Deep模型中Wide部分的基础上进行特征的自动化交叉,避免了更多基于业务理解的人工特征组合。

请说明一下Deep&Cross Network中的交叉网络部分的结构。

交叉网络的核心思想是以有效的方式应用显式特征交叉。交叉网络由交叉层组成，每个层具有以下公式：

其中:

• 是列向量（column vectors），分别表示来自第层和第()层cross layers的输出；
• 是第层layer的weight和bias参数。

在完成一个特征交叉f后，每个cross layer会将它的输入加回去，对应的mapping function ，刚好等于残差 ，这里借鉴了残差网络的思想。

Cross Layer 设计的巧妙之处全部体现在上面的计算公式中：

1. 每层的神经元个数都相同，都等于输入的维度 d，也即每层的输入输出维度都是相等的；
2. 受残差网络（Residual Network）结构启发，每层的函数拟合的是的残差，残差网络有很多优点，其中一点是处理梯度消失的问题，使网络可以“更深”。

我们看一个具体的例子：
假设 Cross 有 2 层，令X_{ 0 }=\begin{bmatrix} x_{ 0,1 } & \\ x_{ 0,2 }\end{bmatrix}，那么为便于讨论令各层，则

当cross layer叠加层时，交叉最高阶可以达到阶，并且包含了所有的交叉组合，这是DCN的精妙之处。
复杂度分析：假设表示cross layers的数目，表示输入的维度。那么，在该cross network中涉及的参数数目为： 。
一个cross network的时间和空间复杂度对于输入维度是线性关系。因而，比起它的deep部分，一个cross network引入的复杂度微不足道，DCN的整体复杂度与传统的DNN在同一水平线上。

DCN主要有哪些优点？

• 提出一种新型的交叉网络结构，可以用来提取交叉组合特征，并不需要人为设计的特征工程；
• 这种网络结构足够简单同时也很有效，可以获得随网络层数增加而增加的多项式阶（polynomial degree）交叉特征；
• 十分节约内存（依赖于正确地实现），并且易于使用；
• 实验结果表明，DCN相比于其他模型有更出色的效果，与DNN模型相比，较少的参数却取得了较好的效果。