论文《AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction》阅读
AutoFIS：点击率预测问题下因子分解机模型的自动特征交互选择模型
论文概况
这篇论文是华为诺亚实验室发表在KDD 2020上的一篇关于推荐系统方向的一篇论文，文章介绍了一种关于因子分解机（FM， Factorization Machines）模型的interaction选择方法，提出了AutoFIS模型。这也是本人第一次接触这个方向的论文，下面我将带领大家了解一下这篇文章提出的AutoFIS方法。
Introduction
Background Knowledge
我们先介绍一下特征交互（Feature Interaction）。在因子分解机（Factorization Machines，FM）模型中，是依据用户user与物体item的交互（interaction）进行点击率的预测的。 FM 直接将每个interaction作为一个向量进行处理，内容包含User ID/Item ID/Interaction(Context) Features等。参考FM经典示例图：
在这里，每一类特征被称为域（field），而每个域包含多个bit，这些特征或者是one-hot特征，或者是multi-hot特征（因为大多数特征是离散型的特征，对于连续性特征，使用分箱(bucket)操作处理为离散型特征）。这些原始的特征被称为low-order interaction，因为他们每一个只能代表一类特征，特征与特征之间是独立的。
特征之间相互影响形成higher-order interaction（高阶特征），从二阶、三阶一直到更高阶，越高阶的特征交互代表着更大维度的特征组合。
CTR预测中的Feature Interaction Selection问题
CTR（Click-Through Rate，点击率）预测经常基于MF方法。但是MF方法中关于特征交互问题是没有考虑的，就是把所有的特征都一股脑参与后续的预测任务中。这种方法带来的坏处是（1）浪费了计算时间和计算开销在没用的特征交互上；（2）更坏的是，这些没用的特征引入了噪声，反而降低了模型的表达能力。
高阶特征交互选择是比较困难的，具体的，如果数据包含 m m m 个域的特征，则二阶特征交互共 C m 2 C_m^2 Cm2 个（简单的排列组合问题，等价于“在m个不同的小球中不放回地取出2个，不考虑顺序，一共多少种取法？”），也可表示为 ( k 2 ) \binom{k}{2} (2k) 。在选择过程中，每个二阶特征交互都需要进行甄别，是落下还是剔除，因此一共需要 2 C m 2 2^{C_m^2} 2Cm2 次选择。
Inspired by DARTS 方法，作者提出了AutoFIS 方法。就是把这个离散型迭代搜索的问题转为连续型变量的求解。对于这 C m 2 C_m^2 Cm2 个二阶特征交互，不去考虑排列组合问题，而是在 C m 2 C_m^2 Cm2 个二阶交互前加一个系数，系数如果是0，就等于剔除；如果不是0，就保留。
作者将 AutoFIS 方法分为两个阶段：1. search阶段，利用GRDA 优化器选择合适的系数； 2. re-train阶段，剔除系数为 0 的特征交互， 将剩下的系数当做 attention 系数进行联合优化，二次训练。
Methodology
Factorization Model(Base Model)
这部分介绍了模型的整体设计。
作者先介绍了三种基于FM方法的SOTA模型FM、DeepFM、IPNN。由上图可以，FM组合了一阶特征和embedding之后的Interaction二阶特征；DeepFM组合了一阶特征、embedding之后的Interaction二阶特征、embedding之后的MLP特征，特征并行相加进行预测；IPNN组合了一阶特征、embedding之后的Interaction二阶特征，并将组合特征输入MLP进行更高阶特征的选择。
AutoFIS
search stage
作者在上述模型的基础上，在搜索阶段中，在每个高阶交互前加了一个系数 α ( i , j ) \alpha_{(i, j)} α(i,j) ，用于指示门开还是关。如下：
l A u t o F I S = < w , x > + ∑ i = 1 m ∑ j > i m α ( i , j ) < e i , e j > (10) l_{AutoFIS} = <w,x> + \sum\limits_{i=1}^{m} \sum\limits_{j>i}^{m} \alpha_{(i, j)}<e_i, e_j> \tag{10} lAutoFIS=<w,x>+i=1∑mj>i∑mα(i,j)<ei,ej>(10)
所有的 α ( i , j ) \alpha_{(i, j)} α(i,j) 构成向量 α = { α ( 1 , 2 ) , α ( 1 , 3 ) , ⋯ , α ( 1 , m ) , α ( 2 , 3 ) , α ( 2 , 4 ) , ⋯ , α ( 2 , m ) , ⋯ , α ( m − 1 , m ) } \bm{\alpha} = \{ {\alpha_{(1, 2)}}, {\alpha_{(1, 3)}}, \cdots, {\alpha_{(1, m)}}, \ \ \ {\alpha_{(2,3)}}, {\alpha_{(2, 4)}}, \cdots, {\alpha_{( 2, m)}}, \ \ \ \ \cdots, {\alpha_{(m-1, m)}} \} α={α(1,2),α(1,3),⋯,α(1,m), α(2,3),α(2,4),⋯,α(2,m), ⋯,α(m−1,m)}
Batch Normalization
但是，这里需要注意的是， < e i , e j > <e_i, e_j> <ei,ej> 并没有统一大小，如果 < e i , e j > <e_i, e_j> <ei,ej> 大小不一样，前面的 α \alpha α 也就没有意义了（并没有起到attention 缩放的效果）。
因此需要在这里进行Batch Normalization，具体的，把每个每个高阶交互集中在（0， 1）范围内。
GRDA Optimizer
这里，作者选用了参考文献[3]（A generalization of regularized dual averaging and its dynamics）提出的GRDA优化器，进行 α \alpha α 的学习。 （公式 (13) 没有更深入的具体研究，欢迎评论区探讨交流，共同进步）。
这里，需要指出的是，在Introduction部分中，作者指出了选用GRDA学习 α \alpha α 的原因： GRDA优化I容易产生稀疏解，也即容易产生0，这样就意味着在后续的操作中容易把0对应的高阶交互进行剔除。
One-level Optimization
这里作者主要与DARTS方法进行了比对。
在DARTS方法中，对于这种超参数的选择，作者将其放在更高层的位置，模型参数处于较低层的位置。本来的训练方法应该是：先训练好低层的模型参数，然后对高层的模型参数进行训练和选择，这样就可以剔除没用的特征交互。但是针对一共 C m 2 C_m^2 Cm2 的参数空间，这样的处理流程带来了较大的计算负担，因此DARTS的处理方式是交替训练高层和低层的参数，启发式地达到较优解。
这个方法的问题在于这种交替训练的方式只是进行近似，并不一定是最优解。
作者针对这个问题，使用了one-level 的训练方式，也就是把
α
\alpha
α 和 低层的模型本身的参数
v
v
v （
v
v
v 不特指，就是泛指模型参数）共同训练，只不过
α
\alpha
α 使用GRDA，而模型参数
v
v
v 使用Adam优化而已。但是这两个优化过程是一起进行的，对损失函数各自求梯度即可。如下：
∂
∂
v
L
(
v
t
−
1
,
α
t
−
1
)
∂
∂
α
L
(
v
t
−
1
,
α
t
−
1
)
(14)
\frac{\partial}{\partial v}{\mathcal{L}(v_{t-1}, \alpha_{t-1})} \\ \\ \frac{\partial}{\partial \alpha}{\mathcal{L}(v_{t-1}, \alpha_{t-1})} \tag{14}
∂v∂L(vt−1,αt−1)∂α∂L(vt−1,αt−1)(14)
Re-train Stage
在重训练的过程中，针对search阶段训练好的 α ∗ \alpha^* α∗ 结果，将 α ( i , j ) = 0 \alpha_{(i, j)} = 0 α(i,j)=0 的高阶特征交互直接剔除，将 α ( i ′ , j ′ ) ≠ 0 \alpha_{(i^{'}, j^{'})} \neq 0 α(i′,j′)=0 的高阶交互保留，将 α ( i ′ , j ′ ) \alpha_{(i^{'}, j^{'})} α(i′,j′) 视为注意力参数加入重新训练的过程，统一使用Adam进行训练。
论文总结
本文提出了高阶特征选择模型 AutoFIS ，模型将较大的特征选择空间转变为连续性的系数求解问题。文中针对共同训练的one-level方式，GRDA优化器的选择，search stage、retrain stage的设定都比较新颖！！！