华为在《AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction》提出了AutoFIS
摘要
学习特征交叉对于CTR预估来说非常重要。在大多数已经存在的深度学习模型中，特征交叉是人工设计或者简单枚举的。然而，枚举所有的特征交叉会带来很大的内容和计算开销。更糟的是，无用的交叉会在训练过程中引入噪声和复杂度[28]。在本工作中，我们提出了一个two-stage算法称为Automiaitc Feature Interaction Selection（AutoFIS）。AutoFIS可以为FM自动标识出重要的特征交叉，有一定计算开销。在search stage中，通过替代搜索候选特征交叉的离散集合，我们会通过引入结构参数将从离线变成连续进行选择。通过在结构参数上实现一个regularized optimizer，模型可以在训练过程中自动标识并移除冗余的特征交叉。在retrain stage，我们会保存结构参数，将它们作为一个attention unit来进一步增强效果。在三个大规模数据集上的离线实验表明，AutoFIS可以极大提升多个FM-based模型。AutoFIS被成功部署在Huawei APP store推荐服务中，10天数据看，可以在CTR/CVR上分别提升20.3%和20.1%。
3.方法
在本节中，我们描述了提出的AutoFIS，它可以自动选择在FM中重要的特征交叉。
3.1 FM（Base Model）
首先，我们定义FM：
定义3.1: FM是这样的模型：来自不同features的多个embeddings的交叉会通过一些内积/neural network的操作来建模成一个实数（real number）。
图1
我们采用FM、DeepFM、IPNN作为实例来公式化我们的算法，并探索在多个数据集上的效果。图1表示了：FM、DeepFM和IPNN模型的结构。FM包含了一个feature embedding layer和一个feature interaction layer。除了这两个layers外，DeepFM和IPNN模型会包含一个额外的layer：MLP layer。在DeepFM和IPNN间的不同之处是：feature interaction layer和MLP layer会在DeepFM中并列工作，而在IPNN中则是顺序的。
在后续章节上，我们将简要描述FM中的feature embedding layer和feature interaction layer。为了与DeepFM和IPNN模型一起工作，MLP layer和output layer也会被公式化。接着，我们提出的AutoFIS是如何在feature interaction layers上工作的会被详述，例如：基于结构参数选择重要的特征交叉。
Feature Embedding Layer。在大多数CTR预估任务中，数据会以multi-field categorical的形式采集。一个典型的数据预处理，会通过one-hot或multi-hot encoding会将每个数据样本转化成一个高维稀疏向量。当一个field是多变量时，会被表示成一个multi-hot encoding vector。一个数据样本可以表示成：
\[x = [x_1, x_2, \cdots, x_m]\]其中，m是fields数目，\(x_i\)是第i个field的one-hot或multi-hot encoding vector。一个feature embedding layer被用于将一个encoding vector转换成一个低维向量：
\[e_i = V_i x_i\]…(1)
其中：\(V_i \in R^{d \times n}\)是一个matrix，\(n_i\)是在第i个field中的。
- 如果\(x_i\)是一个具有第j个元素\(x_i[j]=1\)的one-hot vector，那么\(x_i\)的representation是\(V_i^j\)
- 如果\(x_i\)是一个multi-hot vector，对于\(j=i_1, i_2, \cdots, i_k\)，具有\(x_i[j]=1\)，那么这些元素的embeddings是\(\lbrace V_i^{i1}, V_i^{i2}, \cdots, V_i^{ik}\rbrace\)，接着\(x_i\)的representation是这些embeddings的sum或average。
feature embedding layer的output是多个embedding vectors的concatenation：
\[E= [e_1, e_2, \cdots, e_m]\]Feature Interction Layer
在将features转换成低维空间之后，feature interactions可以使用feature interaction layer被建模到这样的一个空间。首先，pairwise feature interactions的inner product会被计算如下：
\[[\langle e_1, e_2 \rangle, \langlee_1, e_3 \rangle, \cdots, \langle e_{m-1}, e_m \rangle]\]…(2)
其中：
- \(e_i\)是第i个field的feature embedding，
- \(\langle \cdot, \cdot \langle\)是两个vectors的inner product
在该layer中的pair-wise feature interactions的数目是\(C_m^2\)：
\[l_{fm} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \langle e_i, e_j \rangle\]…(3)
这里，所有的feature interactions会等贡献地被传给下一layer。如第1节和第4节，不是所有的特征交叉都有相等的预见性，无效交叉可能会影响效果退化。因此，我们提出了AutoFIS算法来有效选择重要的特征交叉。
为了研究我们的方法是否可以被用来识别重要的高阶交叉，我们将具有3rd-order交叉（例如：三个fields的组合）的feature interaction layer定义为：
\[l_{rm}^{3rd} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \langlee_i, e_j \rangle + \sum\limits_{i=1}^m \sum\limits_{j<i}^m \sum\limits_{t>j}^m \langle e_i, e_j, e_t \rangle\]…(4)
MLP Layer。MLP Layer会包含许多具有activation functions的FC layers，它会学到features的关系和组合。一个这样的layer的output是：
\[a^{(l+1)} = relu(W^{(l)} a^{(l)} + b^{(l)})\]…(5)
其中：
- \(a^{(l)}, W^{(l)}, b^{(l)}\)分别是第l层的input、model weight、bias。
- \(relu(z) =max(0, z)\)：为Activation
- \(a^{(0)}\)是input layer
- \(MLP(a^{(0)}) = a^{(h)}\)：其中h是MLP layer MLP的depth
Output Layer
FM模型没有MLP layer，并直接将feature interaction layer与prediction layer连接：
\[\hat{y}_{FM} = sigmoid(l_{fm}) = \frac{1}{1 + exp(-l_{fm})}\]…(6)
其中，\(\hat{y}_{FM}\)是predicted CTR。
DeepFM会将feature interaction layer与MLP layers并行进行组合：
\[\hat{y}_{DeepFM} = sigmoid(l_{fm} + MLP(E))\]…(7)
当在IPNN中时，MLP layer会跟在feature interaction layer之后：
\[\hat{y}_{IPNN} = sigmoid(MLP([E, l_{fm}]))\]…(8)
注意，IPNN的MLP layer可以对不同feature interactions进行reweighting，来捕获它们的相对重要性。这也是为啥IPNN要比FM和DeepFM具有更高能力的原因。然而，有了IPNN的公式，我们不能检索对应于每个feature interaction的相对贡献的准确值。因此，在IPNN中的feature interactions会带来噪声和计算开销。下面，我们展示了AutoFIS是如何改进IPNN的。
Objective Function
FM、DeepFM、IPNN会共享相同的objective function，例如：最小化predicted values和labels间的cross-entropy：
\[L(y, \hat{y}_M) = - y log\hat{y}_M - (1-y) log(1 - \hat{y}_M)\]…(9)
其中：
- \(y \in \lbrace 0, 1 \rbrace\)是label
- \(\hat{y}_M \in [0, 1]\)是y=1的预估概率。
3.2 AutoFIS
AutoFIS会自动选择有用的特征交叉，它可以补用于任意FM模型的feature interaction layer。在本节中，我们会详述它是如何工作的。AutoFIS可以分成两个阶段：search stage和re-train stage。在search stage中，AutoFIS会检测有用的特征交叉；而在re-train stage中，具有选中的feature interactions的模型会被重新训练。
Search Stage
为了让该算法更好地呈现，我们引入gate操作来控制是否选择一个feature interaction：一个open gate对应于选中一个feature interaction，而一个closed gate会导致一个dropped interaction。对应于所有二阶特征交叉的gates的总数是：\(C_m^2\)。以brute-force方式寻找open gates的最优集合非常挑战，因为我们会面对一个非常大的搜索空间（\(2^{C_m^2}\)）。在本工作中，我们会从一个不同的视角去处理该问题：作为在open gates的一个离散集合上进行搜索的替代，我们会通过引入结构参数\(\alpha\)可以选择连续方式，以便每个feature interaction的相对重要性可以通过梯度下降进行学习。提出的AutoFIS的总览如图2所示。
图2 AutoFIS总览
这种通过梯度学习的结构选择scheme受DARTS【20】的启发，在DARTS中，目标是从在CNN结构中的候选操作集合中选择一个操作（operation）。
特别说明的是，我们会将在FM中的interaction layer重新公式化为：
\[l_{AutoFIS} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \alpha_{(i,j)} \langle e_i, e_j \rangle\]…(10)
其中：
\(\alpha = \lbrace \alpha_{(1,2)}, \cdots, \alpha_{(m-1,m)} \rbrace\)是结构参数。在AutoFIS的search stage，\(\alpha_{(i,j)}\)值会以这样的方式学习：\(\alpha_{(i,j)}\)可以表示每个feature interaction到final prediction的相对贡献。接着，我们可以通过设置那些不重要的gates关闭决定每个feature interaction的gate状态。
Batch Normalization
从整体neural network的角度看，一个feature interaction的贡献可以通过\(\alpha_{(i,j)} \cdot \langle e_i, e_j \rangle\)来进行测算。相同的贡献可以通过对该项rescaling成\((\frac{\alpha_{(i,j)}}{\eta}) \cdot (\eta \cdot \langle e_i, e_j\rangle )\)，其中\(\eta\)是一个真实值。
由于\(\langle e_i, e_j \rangle\)的值可以与\(\alpha_{(i,j)}\)联合学习，它们的scale组合会导致对\(\alpha_{(i,j)}\)的不稳定估计，比如：\(\alpha_{(i,j)}\)不再表示\(<e_i, e_j>\)相对重要性。为了解决该问题，我们在\(\langle e_i, e_j \rangle\)上使用Batch Normalization来取除它的scale问题。BN已经作为一个标准方法被用来训练DNN来达成快速收敛和更好的效果。
原始的BN会使用一个mini-batch的统计信息来对activated output进行归一化。特别的，
\[\hat{z} = \frac{z_{in} - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} \\ z_{out} = \theta \cdot \hat{z} + \beta\]…(11)
其中：
- \(z_{in}, \hat{z}, \hat{z_{out}}\)是input、BN的归一化值、BN的output值
- \(\mu_B, \sigma_B\)是\(z_{in}\)在一个mini-batch B上的均值和标准差；
- \(\theta, \beta\)分别是BN的trainable scale和shift参数
- \(\epsilon\)是数值稳定性的一个常数
为了得到\(\alpha_{(i,j)}\)的稳定估计，我们分别将scale和shift参数设置为1和0. 在每个feature interaction \(<e_i, e_j>\)上的BN操作可以被计算成：
\[\langle e_i, e_j\rangle_{BN} = \frac{\langle e_i, e_j\rangle - \mu_B(\langle e_i, e_j \rangle)}{\sqrt{\sigma^2_B(\langle e_i, e_j\rangle)} + \epsilon}\]…(12)
其中：
- \(\mu_B\)和\(\sigma_B\)是在mini-batch B中的\(\langle e_i, e_j \rangle\)的均值和标准差。
GRDA Optimizer
GRDA optimizer的目标是：获得一个sparse DNN。为了在每个gradident step t上使用数据\(Z_t\)来更新\(\alpha\)，我们使用以下的等式：
\[\alpha_{t+1} = \underset{argmin}{\alpha} \lbrace \alpha^T(-\alpha_0 + \gamma \sum\limits_{i=0}^t \nabla L(\alpha_t; Z_{i+1}) + g(t, \gamma) \| \alpha \|_1 + 1/2\| \alpha \|_2^2 \rbrace\]其中：
- \(g(t,\gamma) = c\gamma^{1/2} (t\gamma)^u\),
- \(\gamma\)是learning rate
- c和\(\mu\)是可调超参数，用于对accuracy和sparsity做tradeoff
在搜索阶段，我们使用GRDA optimizer来学习结构参数\(\alpha\)，并获得一个sparse解。这些不重要的特征交叉（例如：具有零值的\(\alpha_{i,j}\)值）会被自动丢弃。其它参数可以通过Adam optimzier进行学习。
One-level优化
为了在AutoFIS的search stage上学习结构参数\(\alpha_{i,j}\)，我们提出\(\alpha\)与其它所有network权重v进行联合最优化（比如：等式3中的w，和等式5中的\(W^{(l)}\)和\(b^{(l)}\)）。这与DARTS不同。DARTS会将\(\alpha\)看成是更高lebel的决策变量，将network weights看成是更低level的变量，接着使用一个bi-level最优化算法来对它们进行最优化。在DARTS中，假设：当只有network weights被合理学习时，以使\(\alpha\)可以“做出合适决策”，模型可以选择operation。在AutoFIS公式的上下文中，这意味着，我们可以决定：在network weights被合理训练时，一个gate是否会是open或closed，这会导致我们会回到对\(2^{C_m^2}\)个模型完全训练的问题。为了避免这个问题，DARTS提出，只在一个gradient descent step上对network weights的最优值进行逼近，并迭代训练\(\alpha\)和\(v\)。
我们会讨论这种近似的不准确性可能对效果有损。因此，通过对bi-level optimization进行替代，我们提出使用one-level optimization对\(\alpha\)和\(v\)进行联合优化。特别的，参数\(\alpha\)和\(v\)会与gradient descent一起更新：
\[\partial_v L_{train}(v_{t-1}, \alpha_{t-1}) = \partial_{\alpha} L_{train}(v_{t-1}, \alpha_{t-1})\]…(14)
在该setting中，\(\alpha\)和\(v\)可以探索它们的设计空间直到收敛，\(\alpha\)可以被学习用来作为独立feature interactions的贡献。在第4节中，我们展示了one-level optimization要优于two-level optimization。
Re-train Stage
在search stage的训练之后，一些不重要的交叉会根据架构参数\(\alpha^*\)被自动抛弃。我们使用\(G_{(i,j)}\)来表示特征交叉\(\langle e_i, e_j \rangle\)的gate status，当\(\alpha_{(i,j)}^*=0\)时会\(G_{(i,j)}\)将并设置为0；否则，我们设置为1. 在retrain阶段，这些不重要的feature interactions的gate status被确定永久关闭。
在移除这些不重要的交叉后，我们会使用在模型中保存的\(\alpha\)来对新模型进行retrain。特别的，我们会将等式(3)的feature interaction layer进行替换：
\[l_{rm}^{re} = \langle w,x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>1}^m \alpha_{(i,j)} G_{(i,j)} \langle e_i, e_j \rangle\]…(15)
注意，这里\(\alpha_{(i,j)}\)不再作为一个indicator来决定是否一个交叉该包含在模型内（比如：在search stage）。作为替代，它会当成是结构的一个attention unit来学习保持特征交叉的相对重要性。在该stage中，我们不必选择feature interactions。因此，所有参数会通过Adam optimizaer来学习。
4.实验
略