This page is a translated version of the page Deep & Cross Network for Ad Click Predictions/paper and the translation is 100% complete.

Other languages:

SummarySource

Deep & Cross Network for Ad Click Predictions

Research Paper
Authors	Ruoxi Wang; Bin Fu; Gang Fu; Mingliang Wang
Year	2017
Topic area	Machine Learning
Difficulty	Research
arXiv	1708.05123
PDF	Download PDF

Ruoxi Wang Stanford UniversityStanfordCA ruoxi@stanford.edu , Bin Fu Google Inc.New YorkNY binfu@google.com , Gang Fu Google Inc.New YorkNY thomasfu@google.com 与 Mingliang Wang Google Inc.New YorkNY mlwang@google.com

摘要。

特征工程一直是许多预测模型取得成功的关键。然而，这一过程并不简单，往往需要人工的特征工程或穷举搜索。DNN 能够自动学习特征交互，但其生成的所有交互都是隐式的，在学习所有类型的交叉特征时并不一定高效。本文提出 Deep & Cross Network（DCN），它保留了 DNN 模型的优点，并在此之上引入一个新颖的 cross network，能够更高效地学习某些有界阶数的特征交互。特别地，DCN 在每一层显式地进行特征交叉，无需人工特征工程，并且只在 DNN 模型之上增加可忽略的额外复杂度。我们的实验结果在模型精度与内存占用两方面，都展示了其在 CTR 预测数据集与稠密分类数据集上相对于最新算法的优越性。

1. 引言

点击率（CTR）预测是一个大规模问题，对数十亿美元规模的在线广告业至关重要。在广告业中，广告主向发布者付费以在发布者的网站上展示广告。一种流行的付费模式是按点击付费（CPC）模式，即只有在发生点击时广告主才被收费。因此，发布者的收入在很大程度上取决于其准确预测 CTR 的能力。

识别经常具有预测能力的特征，同时探索未见过或罕见的交叉特征，是做出良好预测的关键。然而，Web 规模推荐系统中的数据大多是离散的、类别型的，从而形成一个庞大且稀疏的特征空间，给特征探索带来挑战。这迫使大多数大规模系统只能使用诸如逻辑回归之类的线性模型。

线性模型（Chapelle 等，2015）简单、可解释且易于扩展；但其表达能力有限。另一方面，已有研究表明交叉特征对提升模型表达力有重要作用。遗憾的是，识别这些特征往往需要人工特征工程或穷举搜索；而且，向未见过的特征交互泛化也很困难。

在本文中，我们的目标是通过引入一种新颖的神经网络结构——cross network——来避免针对具体任务的特征工程，该网络以自动方式显式地进行特征交叉。cross network 由多层组成，其表示交互的最高阶数可被证明由层深决定。每一层都在已有交互的基础上产生更高阶的交互，并保留前面各层的交互。我们将 cross network 与一个深度神经网络（DNN）联合训练（LeCun 等，2015；Schmidhuber，2015）。DNN 有望捕捉非常复杂的特征交互；但与我们的 cross network 相比，它需要的参数几乎多一个数量级，无法显式构造交叉特征，而且可能难以高效地学习某些类型的特征交互。然而，将 cross 与 DNN 组件联合训练能够高效地捕捉具有预测力的特征交互，并在 Criteo CTR 数据集上取得最新的最佳性能。

1.1. 相关工作

由于数据集在规模和维度上的急剧增长，已有大量方法被提出以避免针对具体任务的特征工程，这些方法大多基于嵌入技术和神经网络。

Factorization machines（FMs）（Rendle，2010，2012）将稀疏特征投影到低维稠密向量上，并通过向量内积学习特征交互。Field-aware factorization machines（FFMs）（Juan 等，2016，2017）进一步让每个特征学习多个向量，每个向量与一个 field 相关联。遗憾的是，FMs 与 FFMs 的浅层结构限制了它们的表达能力。也有工作将 FM 扩展到更高阶（Blondel 等，2016；Yang 与 Gittens，2015），但其参数量过大，带来了不理想的计算开销。深度神经网络（DNN）借助嵌入向量与非线性激活函数，能够学习非平凡的高阶特征交互。Residual Network（He 等，2015）的近期成功使得训练非常深的网络成为可能。Deep Crossing（Shan 等，2016）扩展了 residual network，通过堆叠各种类型的输入实现自动特征学习。

深度学习的显著成功激发了有关其表示能力的理论分析。有研究（Valiant，2014；Veit 等，2016）表明，在一定的光滑性假设下，只要隐藏单元或隐藏层足够多，DNN 能以任意精度逼近任意函数。此外，在实践中也发现，DNN 在可行的参数规模下就能表现良好。一个关键原因是，大多数实际感兴趣的函数并非任意函数。

然而，仍有一个问题：DNN 是否真的是表示这类实际感兴趣函数的最高效方式。在 Kaggle¹¹1https://www.kaggle.com/ 比赛中，许多获胜方案中人工设计的特征都是低阶、显式且有效的。而 DNN 学到的特征则是隐式且高度非线性的。这启发了人们去设计一种模型，使其能够比通用 DNN 更高效、更显式地学习有界阶数的特征交互。

wide-and-deep（Cheng 等，2016）正是这一思路下的一种模型。它将交叉特征作为线性模型的输入，并将该线性模型与 DNN 模型联合训练。然而，wide-and-deep 的成功依赖于对交叉特征的合理选择，而这是一个指数级的问题，目前尚无明显高效的方法。

1.2. 主要贡献

在本文中，我们提出 Deep & Cross Network（DCN）模型，它在同时具有稀疏与稠密输入的情况下实现 Web 规模的自动特征学习。DCN 能高效地捕获有界阶数的有效特征交互、学习高度非线性的交互、无需人工特征工程或穷举搜索，且计算开销低。

本文的主要贡献包括：

•

我们提出了一种新颖的 cross network，在每一层显式地进行特征交叉，能够高效地学习有界阶数的、具有预测力的交叉特征，并且无需人工特征工程或穷举搜索。
•

cross network 简单而有效。从设计上，每一层的最高多项式阶数都会增加，并由层深决定。网络包含所有不超过最高阶的交叉项，且各项系数均不相同。
•

cross network 在内存上高效，且易于实现。
•

实验结果表明，借助一个 cross network，DCN 在参数量比 DNN 少近一个数量级的情况下取得了更低的 log loss。

本文的组织如下：第 2 节描述 Deep & Cross Network 的架构。第 3 节详细分析 cross network。第 4 节展示实验结果。

2. Deep & Cross Network（DCN）

在本节中，我们描述 Deep & Cross Network（DCN）模型的架构。DCN 模型从一个 embedding and stacking layer 开始，紧接着是并行的 cross network 与 deep network。之后是最终的 combination layer，它将两条网络的输出组合在一起。完整的 DCN 模型如图 1 所示。

2.1. 嵌入与堆叠层

我们考虑同时包含稀疏与稠密特征的输入数据。在 CTR 预测等 Web 规模推荐系统中，输入大多是类别型特征，例如 "country=usa"。这类特征通常被编码为 one-hot 向量，例如 "[0,1,0]"；但对于大词表，这往往会导致维度过高的特征空间。

为了降低维度，我们采用嵌入过程，将这些二值特征转换为实数稠密向量（通常称为嵌入向量）：

(1)		${\mathbf{x}_{\text{embed},i} = {W_{\text{embed},i}\hspace{0pt}\mathbf{x}_{i}}},$

其中 ${\textstyle \mathbf{x}_{\text{embed},i}}$ 是嵌入向量， ${\textstyle \mathbf{x}_{i}}$ 是第 ${\textstyle i}$ 个类别的二值输入， ${\textstyle W_{\text{embed},i} \in {\mathbb{R}}^{n_{e} \times n_{v}}}$ 是对应的嵌入矩阵，将与网络中的其他参数共同被优化， ${\textstyle n_{e},n_{v}}$ 分别为嵌入维度与词表大小。

最后，我们将嵌入向量与归一化的稠密特征 ${\textstyle \mathbf{x}_{\text{dense}}}$ 堆叠成单个向量：

(2)		${\mathbf{x}_{0} = \left\lbrack \mathbf{x}_{\text{embed},1}^{T},\ldots,\mathbf{x}_{\text{embed},k}^{T},\mathbf{x}_{\text{dense}}^{T} \right\rbrack},$

并将 ${\textstyle \mathbf{x}_{0}}$ 输入到网络中。

2.2. Cross Network

我们提出的新颖 cross network 的关键思想是以一种高效的方式进行显式的特征交叉。cross network 由若干个 cross layer 组成，每一层具有如下公式：

(3)		${\mathbf{x}_{l + 1} = {{\mathbf{x}_{0}\hspace{0pt}\mathbf{x}_{l}^{T}\hspace{0pt}\mathbf{w}_{l}} + \mathbf{b}_{l} + \mathbf{x}_{l}} = {{f\hspace{0pt}{(\mathbf{x}_{l},\mathbf{w}_{l},\mathbf{b}_{l})}} + \mathbf{x}_{l}}},$

其中 ${\textstyle {\mathbf{x}_{l},\mathbf{x}_{l + 1}} \in {\mathbb{R}}^{d}}$ 为列向量，分别表示第 ${\textstyle l}$ 和第 ${\textstyle ({l + 1})}$ 个 cross layer 的输出； ${\textstyle {\mathbf{w}_{l},\mathbf{b}_{l}} \in {\mathbb{R}}^{d}}$ 为第 ${\textstyle l}$ 层的权重与偏置参数。每个 cross layer 在进行特征交叉 ${\textstyle f}$ 之后再把输入加回来，而映射函数 ${\textstyle f:{{\mathbb{R}}^{d}\mapsto{\mathbb{R}}^{d}}}$ 拟合的是 ${\textstyle \mathbf{x}_{l + 1} - \mathbf{x}_{l}}$ 这一残差。一个 cross layer 的可视化见图 2。

跨特征的高阶交互。cross network 的特殊结构使得交叉特征的阶数随层深增长。一个 ${\textstyle l}$ 层 cross network 的最高多项式阶数（关于输入 ${\textstyle \mathbf{x}_{0}}$ ）为 ${\textstyle l + 1}$ 。实际上，cross network 包含所有阶数从 1 到 ${\textstyle l + 1}$ 的交叉项 ${\textstyle x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\ldots\hspace{0pt}x_{d}^{\alpha_{d}}}$ 。详细分析见第 3 节。

复杂度分析。设 ${\textstyle L_{c}}$ 为 cross layer 的数量， ${\textstyle d}$ 为输入维度。则 cross network 涉及的参数数量为

	${\textstyle {d \times L_{c} \times 2}.}$

cross network 的时间与空间复杂度对输入维度均为线性。因此，相比其深层对应部分，cross network 引入的复杂度可以忽略不计，使得 DCN 的整体复杂度与传统 DNN 处于同一水平。这种效率得益于 ${\textstyle \mathbf{x}_{0}\hspace{0pt}\mathbf{x}_{l}^{T}}$ 的秩一性质，使我们无需计算或存储完整矩阵即可生成所有交叉项。

cross network 的参数量较小，会限制模型容量。为了捕获高度非线性的交互，我们并行引入了一个 deep network。

2.3. Deep Network

deep network 是一个全连接的前馈神经网络，每一个 deep layer 具有如下公式：

(4)		${\mathbf{h}_{l + 1} = {f\hspace{0pt}{({{W_{l}\hspace{0pt}\mathbf{h}_{l}} + \mathbf{b}_{l}})}}},$

其中 ${\textstyle {\mathbf{h}_{l} \in {\mathbb{R}}^{n_{l}}},{\mathbf{h}_{l + 1} \in {\mathbb{R}}^{n_{l + 1}}}}$ 分别为第 ${\textstyle l}$ 和第 ${\textstyle ({l + 1})}$ 个隐藏层； ${\textstyle {W_{l} \in {\mathbb{R}}^{n_{l + 1} \times n_{l}}},{\mathbf{b}_{l} \in {\mathbb{R}}^{n_{l + 1}}}}$ 是第 ${\textstyle l}$ 个 deep layer 的参数； ${\textstyle f\hspace{0pt}{( \cdot )}}$ 为 ReLU 函数。

复杂度分析。为简化起见，我们假设所有 deep layer 大小相同。设 ${\textstyle L_{d}}$ 为 deep layer 的数量， ${\textstyle m}$ 为 deep layer 的大小。则 deep network 中的参数数量为

	${\textstyle {{d \times m} + m + {{({m^{2} + m})} \times {({L_{d} - 1})}}}.}$

2.4. 组合层

组合层将两条网络的输出拼接，并将拼接后的向量输入到一个标准的 logits 层。

以下是二分类问题的公式：

(5)		${p = {\sigma\hspace{0pt}\left( {{\lbrack\mathbf{x}_{L_{1}}^{T},\mathbf{h}_{L_{2}}^{T}\rbrack}\hspace{0pt}\mathbf{w}_{\text{logits}}} \right)}},$

其中 ${\textstyle {\mathbf{x}_{L_{1}} \in {\mathbb{R}}^{d}},{\mathbf{h}_{L_{2}} \in {\mathbb{R}}^{m}}}$ 分别为 cross network 与 deep network 的输出， ${\textstyle \mathbf{w}_{\text{logits}} \in {\mathbb{R}}^{({d + m})}}$ 为组合层的权重向量， ${\textstyle {\sigma\hspace{0pt}{(x)}} = {1/{({1 + {\exp{({- x})}}})}}}$ 。

损失函数为 log loss 加上一个正则化项，

(6)		$\begin{aligned} {\text{loss} =} & {{{- {\frac{1}{N}\hspace{0pt}{\sum\limits_{i = 1}^{N}{y_{i}\hspace{0pt}{\log{(p_{i})}}}}}} + {{({1 - y_{i}})}\hspace{0pt}{\log{({1 - p_{i}})}}} + {\lambda\hspace{0pt}{\sum\limits_{l}{\\|\mathbf{w}_{l}\\|}^{2}}}},} \end{aligned}$

其中 ${\textstyle p_{i}}$ 是由公式 5 计算得到的概率， ${\textstyle y_{i}}$ 为真实标签， ${\textstyle N}$ 为输入总数， ${\textstyle \lambda}$ 为 ${\textstyle L_{2}}$ 正则化参数。

我们对两条网络进行联合训练，这样每一条网络在训练过程中都能感知到其他网络。

3. Cross Network 分析

在本节中，我们对 DCN 的 cross network 进行分析，以便理解其有效性。我们从三个角度展开：多项式逼近、对 FMs 的推广，以及高效投影。为简化起见，我们假设 ${\textstyle \mathbf{b}_{i} = 0}$ 。

记号。记 ${\textstyle \mathbf{w}_{j}}$ 的第 ${\textstyle i}$ 个分量为 ${\textstyle w_{j}^{(i)}}$ 。对于多重指标 ${\textstyle {\mathbf{α}} = {\lbrack\alpha_{1},\cdots,\alpha_{d}\rbrack} \in {\mathbb{N}}^{d}}$ 和 ${\textstyle \mathbf{x} = {\lbrack x_{1},\cdots,x_{d}\rbrack} \in {\mathbb{R}}^{d}}$ ，定义 ${\textstyle {|{\mathbf{α}}|} = {\sum_{i = 1}^{d}\alpha_{i}}}$ 。

术语。交叉项（单项式） ${\textstyle x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\cdots\hspace{0pt}x_{d}^{\alpha_{d}}}$ 的阶数定义为 ${\textstyle |{\mathbf{α}}|}$ 。多项式的阶数定义为其中各项的最高阶数。

3.1. 多项式逼近

根据 Weierstrass 逼近定理（Rudin 等，1964），在一定的光滑性假设下，任何函数都可以由多项式以任意精度逼近。因此，我们从多项式逼近的角度分析 cross network。具体而言，cross network 以一种高效、富表达力且在真实数据上泛化更好的方式逼近同阶多项式类。

我们详细研究 cross network 对同阶多项式类的逼近。用 ${\textstyle P_{n}\hspace{0pt}{(\mathbf{x})}}$ 表示阶数为 ${\textstyle n}$ 的多元多项式类：

(7)		$P_{n}{(\mathbf{x})} = \left\{ \sum\limits_{\mathbf{α}}w_{\mathbf{α}}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\ldots x_{d}^{\alpha_{d}} \middle\| 0 \leq \|{\mathbf{α}}\| \leq n,{\mathbf{α}} \in {\mathbb{N}}^{d} \right\}.$

该类中的每个多项式有 ${\textstyle O\hspace{0pt}{(d^{n})}}$ 个系数。我们证明，只用 ${\textstyle O\hspace{0pt}{(d)}}$ 个参数，cross network 就能包含同阶多项式中出现的所有交叉项，且每一项的系数都各不相同。

定理 3.1。

考虑一个 ${\textstyle l}$ 层的 cross network，其第 ${\textstyle i + 1}$ 层定义为 ${\textstyle \mathbf{x}_{i + 1} = {{\mathbf{x}_{0}\hspace{0pt}\mathbf{x}_{i}^{T}\hspace{0pt}\mathbf{w}_{i}} + \mathbf{x}_{i}}}$ 。设网络的输入为 ${\textstyle \mathbf{x}_{0} = {\lbrack x_{1},x_{2},\ldots,x_{d}\rbrack}^{T}}$ ，输出为 ${\textstyle {g_{l}\hspace{0pt}{(\mathbf{x}_{0})}} = {\mathbf{x}_{l}^{T}\hspace{0pt}\mathbf{w}_{l}}}$ ，参数为 ${\textstyle {\mathbf{w}_{i},\mathbf{b}_{i}} \in {\mathbb{R}}^{d}}$ 。则多元多项式 ${\textstyle g_{l}\hspace{0pt}{(\mathbf{x}_{0})}}$ 复现下面这一类多项式：

	$\left\{ {\left. {\sum\limits_{\mathbf{α}}{c_{\mathbf{α}}\hspace{0pt}{(\mathbf{w}_{0},\ldots,\mathbf{w}_{l})}\hspace{0pt}x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\ldots\hspace{0pt}x_{d}^{\alpha_{d}}}} \middle\| 0 \leq {\|{\mathbf{α}}\|} \leq {l + 1} \right.,{{\mathbf{α}} \in {\mathbb{N}}^{d}}} \right\},$

其中 ${\textstyle c_{\mathbf{α}} = {M_{\mathbf{α}}\hspace{0pt}{\sum_{\mathbf{i} \in B_{\mathbf{α}}}{\sum_{\mathbf{j} \in P_{\mathbf{α}}}{\prod_{k = 1}^{|{\mathbf{α}}|}w_{i_{k}}^{(j_{k})}}}}}}$ ， ${\textstyle M_{\mathbf{α}}}$ 是与 ${\textstyle \mathbf{w}_{i}}$ 无关的常数， ${\textstyle \mathbf{i} = {\lbrack i_{1},\ldots,i_{|{\mathbf{α}}|}\rbrack}}$ 与 ${\textstyle \mathbf{j} = {\lbrack j_{1},\ldots,j_{|{\mathbf{α}}|}\rbrack}}$ 都是多重指标， ${\textstyle B_{\mathbf{α}} = \left\{ \mathbf{y} \in {\{ 0,1,\cdots,l\}}^{|{\mathbf{α}}|} \middle| y_{i} < {y_{j} \land y_{|{\mathbf{α}}|}} = l \right\}}$ ，而 ${\textstyle P_{\mathbf{α}}}$ 是指标 ${\textstyle ({\underset{\alpha_{1}\hspace{0pt}\text{times}}{\underbrace{1,\cdots,1}}\hspace{0pt}\cdots\hspace{0pt}\underset{\alpha_{d}\hspace{0pt}\text{times}}{\underbrace{d,\cdots,d}}})}$ 的所有排列构成的集合。

定理 3.1 的证明在附录中。我们举一个例子。考虑 ${\textstyle x_{1}\hspace{0pt}x_{2}\hspace{0pt}x_{3}}$ 在 ${\textstyle {\mathbf{α}} = {(1,1,1,0,\ldots,0)}}$ 下的系数 ${\textstyle c_{\mathbf{α}}}$ 。在差一个常数的意义下，当 ${\textstyle l = 2}$ 时， ${\textstyle c_{\mathbf{α}} = {\sum_{{i,j,k} \in P_{\mathbf{α}}}{w_{0}^{(i)}\hspace{0pt}w_{1}^{(j)}\hspace{0pt}w_{2}^{(k)}}}}$ ；当 ${\textstyle l = 3}$ 时， ${\textstyle c_{\mathbf{α}} = {{\sum_{{i,j,k} \in P_{\mathbf{α}}}{w_{0}^{(i)}\hspace{0pt}w_{1}^{(j)}\hspace{0pt}w_{3}^{(k)}}} + {w_{0}^{(i)}\hspace{0pt}w_{2}^{(j)}\hspace{0pt}w_{3}^{(k)}} + {w_{1}^{(i)}\hspace{0pt}w_{2}^{(j)}\hspace{0pt}w_{3}^{(k)}}}}$ 。

3.2. 对 FMs 的推广

cross network 继承了 FM 模型参数共享的思想，并将其进一步推广到更深的结构。

在 FM 模型中，特征 ${\textstyle x_{i}}$ 与权重向量 ${\textstyle \mathbf{v}_{i}}$ 关联，交叉项 ${\textstyle x_{i}\hspace{0pt}x_{j}}$ 的权重由 ${\textstyle \langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle}$ 计算得到。在 DCN 中， ${\textstyle x_{i}}$ 与一组标量 ${\textstyle {\{ w_{k}^{(i)}\}}_{k = 1}^{l}}$ 关联， ${\textstyle x_{i}\hspace{0pt}x_{j}}$ 的权重则是来自 ${\textstyle {\{ w_{k}^{(i)}\}}_{k = 0}^{l}}$ 与 ${\textstyle {\{ w_{k}^{(j)}\}}_{k = 0}^{l}}$ 这两组参数的乘积。两种模型都为每个特征学到一些与其他特征相互独立的参数，而某一交叉项的权重则是相应参数的某种组合。

参数共享不仅使模型更高效，也使模型能够泛化到未见过的特征交互，并对噪声更鲁棒。例如，考虑具有稀疏特征的数据集。如果两个二值特征 ${\textstyle x_{i}}$ 与 ${\textstyle x_{j}}$ 在训练数据中很少甚至从不共现，即 ${\textstyle x_{i} \neq {0 \land x_{j}} \neq 0}$ ，那么学到的 ${\textstyle x_{i}\hspace{0pt}x_{j}}$ 的权重对预测不会带来有意义的信息。

FM 是一种浅层结构，仅能表示二阶交叉项。相比之下，DCN 能够构造所有阶数 ${\textstyle |{\mathbf{α}}|}$ 不超过由层深决定的某个常数的交叉项 ${\textstyle x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\ldots\hspace{0pt}x_{d}^{\alpha_{d}}}$ ，正如定理 3.1 所述。因此，cross network 将参数共享的思想从单层推广到多层与高阶交叉项。注意，与高阶 FMs 不同，cross network 的参数数量仅随输入维度线性增长。

3.3. 高效投影

每个 cross layer 都以一种高效的方式，将 ${\textstyle \mathbf{x}_{0}}$ 与 ${\textstyle \mathbf{x}_{l}}$ 之间所有的成对交互投影回输入维度。

将 ${\textstyle \overset{\sim}{\mathbf{x}} \in {\mathbb{R}}^{d}}$ 视为某个 cross layer 的输入。该 cross layer 隐式地构造 ${\textstyle d^{2}}$ 个成对交互 ${\textstyle x_{i}\hspace{0pt}{\overset{\sim}{x}}_{j}}$ ，然后以一种内存高效的方式将它们隐式投影回维度 ${\textstyle d}$ 。然而，直接的做法会带来立方级的开销。

我们的 cross layer 给出一种高效解决方案，将开销降至维度 ${\textstyle d}$ 上的线性。考虑 ${\textstyle \mathbf{x}_{p} = {\mathbf{x}_{0}\hspace{0pt}{\overset{\sim}{\mathbf{x}}}^{T}\hspace{0pt}\mathbf{w}}}$ 。这事实上等价于

(8)		$\begin{array}{r} {\mathbf{x}_{p}^{T} = {\begin{bmatrix} {x_{1}\hspace{0pt}{\overset{\sim}{x}}_{1}\hspace{0pt}\ldots\hspace{0pt}x_{1}\hspace{0pt}{\overset{\sim}{x}}_{d}} & \ldots & {x_{d}\hspace{0pt}{\overset{\sim}{x}}_{1}\hspace{0pt}\ldots\hspace{0pt}x_{d}\hspace{0pt}{\overset{\sim}{x}}_{d}} \end{bmatrix}\hspace{0pt}\begin{bmatrix} \begin{matrix} \mid \\ \mathbf{w} \\ \mid \end{matrix} & \mathbf{0} & \ldots & \mathbf{0} \\ \mathbf{0} & \begin{matrix} \mid \\ \mathbf{w} \\ \mid \end{matrix} & \ldots & \mathbf{0} \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{0} & \mathbf{0} & \ldots & \begin{matrix} \mid \\ \mathbf{w} \\ \mid \end{matrix} \end{bmatrix}}} \end{array}$

其中行向量包含所有 ${\textstyle d^{2}}$ 个成对交互 ${\textstyle x_{i}\hspace{0pt}{\overset{\sim}{x}}_{j}}$ ，投影矩阵则具有以 ${\textstyle \mathbf{w} \in {\mathbb{R}}^{d}}$ 为列向量的分块对角结构。

4. 实验结果

在本节中，我们在若干常用的分类数据集上评估 DCN 的性能。

4.1. Criteo Display Ads 数据

Criteo Display Ads²²2https://www.kaggle.com/c/criteo-display-ad-challenge 数据集用于预测广告点击率。它包含 13 个整型特征和 26 个类别型特征，每个类别都具有较高的基数。对该数据集而言，log loss 提升 0.001 即被视为具有实际意义。考虑到庞大的用户基数，预测精度的微小提升可能为公司带来显著的收入增长。该数据包含 11 GB 的 7 天用户日志（ ${\textstyle \sim}$ 4100 万条记录）。我们将前 6 天的数据用于训练，并将第 7 天的数据随机划分为大小相同的验证集和测试集。

4.2. 实现细节

DCN 基于 TensorFlow 实现，下面简要介绍一些训练 DCN 的实现细节。

数据处理与嵌入。实值特征通过对数变换进行归一化。对于类别型特征，我们将其嵌入到维度为 ${\textstyle {6 \times {(\text{category cardinality})}^{1/4}}.}$ 的稠密向量中。将所有嵌入拼接后得到一个 1026 维的向量。
优化。我们采用 Adam 优化器（Kingma 与 Ba，2014）进行小批量随机优化。batch 大小设为 512。在 deep network 上使用 batch normalization（Ioffe 与 Szegedy，2015），并将梯度裁剪范数设为 100。
正则化。我们使用 early stopping，因为我们发现 ${\textstyle L_{2}}$ 正则化和 dropout 均不奏效。
超参数。我们在隐藏层数量、隐藏层大小、初始学习率和 cross layer 数量上进行网格搜索，并报告相应结果。隐藏层数量从 2 到 5，隐藏层大小从 32 到 1024。对于 DCN，cross layer 的数量³³3更多的 cross layer 并未带来显著提升，因此我们将其限定在较小范围以便更精细地调参。从 1 到 6。初始学习率⁴⁴4实验中我们观察到，对于 Criteo 数据集，学习率高于 0.001 通常会使性能下降。在 0.0001 到 0.001 之间以 0.0001 的步长进行调节。所有实验都在训练步数 150,000 处使用 early stopping，超过该点便开始出现过拟合。

4.3. 对比模型

我们将 DCN 与五种模型进行比较：去除 cross network 的 DCN（DNN）、逻辑回归（LR）、Factorization Machines（FMs）、Wide and Deep 模型（W&D），以及 Deep Crossing（DC）。

DNN。嵌入层、输出层和超参数调优流程与 DCN 相同。与 DCN 模型的唯一区别在于没有 cross layer。
LR。我们使用 Sibyl（Canini，2012），一个用于分布式逻辑回归的大规模机器学习系统。整型特征按对数刻度离散化。交叉特征通过一个复杂的特征选择工具选出。所有的单个特征都被使用。
FM。我们使用一个基于 FM 的模型，具体细节为内部专有。
W&D。与 DCN 不同，其 wide 部分以原始稀疏特征为输入，并依赖穷举搜索和领域知识来挑选具有预测力的交叉特征。由于目前没有公认的良好方法来选择交叉特征，我们略去了这一对比。
DC。与 DCN 相比，DC 不显式构造交叉特征。它主要依赖堆叠和 residual unit 来生成隐式交叉。我们采用与 DCN 相同的嵌入（堆叠）层，再接一层 ReLU 作为一系列 residual unit 的输入。residual unit 的数量在 1 到 5 之间调节，其输入维度和 cross 维度在 100 到 1026 之间调节。

4.4. 模型性能

在本节中，我们先列出不同模型在 log loss 上的最佳性能，然后详细比较 DCN 与 DNN，即深入考察 cross network 所带来的影响。

不同模型的性能。各模型的最佳测试 log loss 列于表 1。最优超参数设置为：DCN 模型为 2 个大小为 1024 的 deep layer 与 6 个 cross layer；DNN 为 5 个大小为 1024 的 deep layer；DC 为 5 个 residual unit，输入维度 424、cross 维度 537；LR 模型为 42 个交叉特征。最佳性能出现在最深的 cross 架构上，表明 cross network 提供的高阶特征交互是有价值的。可以看到，DCN 大幅领先于其他所有模型。特别地，它超越了最先进的 DNN 模型，但只使用了 DNN 内存消耗的 40%。

模型	DCN	DC	DNN	FM	LR
Log loss	0.4419	0.4425	0.4428	0.4464	0.4474

对于每个模型的最优超参数设置，我们还报告了 10 次独立运行的测试 log loss 的均值与标准差：DCN： ${\textstyle 0.4422 \pm {\mathbf{9} \times \mathbf{1}\mathbf{0}^{- \mathbf{5}}}}$ ，DNN： ${\textstyle 0.4430 \pm {3.7 \times 10^{- 4}}}$ ，DC： ${\textstyle 0.4430 \pm {4.3 \times 10^{- 4}}}$ 。可以看出，DCN 始终以较大幅度优于其他模型。

DCN 与 DNN 的比较。考虑到 cross network 只引入 ${\textstyle O\hspace{0pt}{(d)}}$ 个额外参数，我们将 DCN 与其 deep network——即传统的 DNN——进行比较，并在不同的内存预算和损失容差下给出实验结果。

下文中，对应于某一参数量的损失，是在所有学习率和模型结构中得到的最佳验证损失。我们在计算时忽略了嵌入层中的参数量，因为两种模型在这一点上完全相同。

表 2 报告了达到给定 log loss 阈值所需的最少参数量。从表 2 中可以看到，得益于 cross network 能更高效地学习有界阶数的特征交互，DCN 在内存使用上比单一 DNN 高效近一个数量级。

Log loss	0.4430	0.4460	0.4470	0.4480
DNN	${\textstyle 3.2 \times 10^{6}}$	${\textstyle 1.5 \times 10^{5}}$	${\textstyle 1.5 \times 10^{5}}$	${\textstyle 7.8 \times 10^{4}}$
DCN	${\textstyle 7.9 \times \mathbf{1}\mathbf{0}^{\mathbf{5}}}$	${\textstyle 7.3 \times \mathbf{1}\mathbf{0}^{\mathbf{4}}}$	${\textstyle 3.7 \times \mathbf{1}\mathbf{0}^{\mathbf{4}}}$	${\textstyle 3.7 \times \mathbf{1}\mathbf{0}^{\mathbf{4}}}$

表 3 在固定内存预算下比较了神经网络模型的性能。可以看到，DCN 在所有规模上都稳定优于 DNN。在小参数量区间，cross network 的参数量与 deep network 相当，而显著的提升表明 cross network 在学习有效特征交互方面更高效。在大参数量区间，DNN 缩小了部分差距；然而 DCN 仍然以较大幅度领先 DNN，这表明它能够高效地学习一些即便庞大 DNN 也无法捕获的有意义的特征交互。

参数量	${\textstyle 5 \times 10^{4}}$	${\textstyle 1 \times 10^{5}}$	${\textstyle 4 \times 10^{5}}$	${\textstyle 1.1 \times 10^{6}}$	${\textstyle 2.5 \times 10^{6}}$
DNN	0.4480	0.4471	0.4439	0.4433	0.4431
DCN	0.4465	0.4453	0.4432	0.4426	0.4423

我们通过展示在给定 DNN 模型上引入 cross network 所带来的影响，对 DCN 进行更细致的分析。首先在相同的层数和层大小下比较 DNN 与 DCN 的最佳性能，然后对每种设置展示随着 cross layer 数量增加，验证集 log loss 的变化情况。表 4 给出了 DCN 与 DNN 模型在 log loss 上的差异。在相同实验设置下，相同结构的 DCN 模型最佳 log loss 始终优于单独 DNN 模型。这一提升在所有超参数下都保持一致，抵消了来自初始化和随机优化的随机性影响。

[[File:data:image/svg+xml;base64,PHN2ZyBoZWlnaHQ9IjI0LjYiIG92ZXJmbG93PSJ2aXNpYmxlIiB2ZXJzaW9uPSIxLjEiIHdpZHRoPSI4OS45NCI+PGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMCwyNC42KSBzY2FsZSgxLC0xKSI+PHBhdGggZD0iTSAwLDI0LjYgODkuOTQsMCIgc3Ryb2tlPSIjMDAwMDAwIiBzdHJva2Utd2lkdGg9IjAuNCIgLz48ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgwLDApIj48ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgwLDEyLjMpIHNjYWxlKDEsIC0xKSI+PGZvcmVpZ25vYmplY3QgaGVpZ2h0PSIxMi4zIiBvdmVyZmxvdz0idmlzaWJsZSIgd2lkdGg9IjUwLjY2Ij4KCgojTGF5ZXJzCgo8L2ZvcmVpZ25vYmplY3Q+PC9nPjwvZz48ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSg0MS40MywxMi4zKSI+PGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMCwxMi4zKSBzY2FsZSgxLCAtMSkiPjxmb3JlaWdub2JqZWN0IGhlaWdodD0iMTIuMyIgb3ZlcmZsb3c9InZpc2libGUiIHdpZHRoPSI0OC41MSI+CgoKI05vZGVzCgo8L2ZvcmVpZ25vYmplY3Q+PC9nPjwvZz48L2c+PC9zdmc+]]	32	64	128	256	512	1024
2	-0.28	-0.10	-0.16	-0.06	-0.05	-0.08
3	-0.19	-0.10	-0.13	-0.18	-0.07	-0.05
4	-0.12	-0.10	-0.06	-0.09	-0.09	-0.21
5	-0.21	-0.11	-0.13	-0.00	-0.06	-0.02

图 3 展示了在若干随机选择的设置上，随着 cross layer 数量增加所带来的提升。对于图 3 中的 deep network，向模型中加入 1 个 cross layer 即可带来明显的提升。随着引入更多 cross layer，在某些设置下 log loss 持续下降，说明所引入的交叉项对预测有效；而在另一些设置下，log loss 开始波动甚至略有上升，表明所引入的更高阶特征交互并无帮助。

4.5. 非 CTR 数据集

我们展示了 DCN 在非 CTR 预测问题上同样表现良好。我们使用 UCI 仓库中的 forest covertype（581012 个样本，54 个特征）和 Higgs（1100 万个样本，28 个特征）数据集。数据集被随机划分为训练集（90%）和测试集（10%）。我们在超参数上进行网格搜索。deep layer 的数量在 1 到 10 之间，大小在 50 到 300 之间。cross layer 的数量在 4 到 10 之间。residual unit 的数量在 1 到 5 之间，其输入维度和 cross 维度在 50 到 300 之间。对于 DCN，输入向量直接送入 cross network。

在 forest covertype 数据上，DCN 以最少的内存消耗取得了 0.9740 的最佳测试准确率。DNN 和 DC 均为 0.9737。最优超参数设置为：DCN 为 8 个大小为 54 的 cross layer 与 6 个大小为 292 的 deep layer；DNN 为 7 个大小为 292 的 deep layer；DC 为 4 个 residual unit，输入维度 271、cross 维度 287。

在 Higgs 数据上，DCN 取得了 0.4494 的最佳测试 log loss，而 DNN 为 0.4506。最优超参数设置为：DCN 为 4 个大小为 28 的 cross layer 与 4 个大小为 209 的 deep layer；DNN 为 10 个大小为 196 的 deep layer。DCN 在使用 DNN 一半内存的情况下仍然优于 DNN。

5. 结论与未来方向

识别有效的特征交互一直是许多预测模型取得成功的关键。遗憾的是，这一过程往往需要人工特征构造和穷举搜索。DNN 在自动特征学习方面很受欢迎；然而，所学到的特征是隐式且高度非线性的，网络可能不必要地庞大，并在学习某些特征时效率低下。本文提出的 Deep & Cross Network 能够处理大规模的稀疏与稠密特征，并与传统深度表示一同显式地学习有界阶数的交叉特征。交叉特征的阶数在每个 cross layer 上增加一阶。实验结果在稀疏数据集和稠密数据集上的模型精度与内存使用两方面，均展示了其相对于最新算法的优越性。

我们希望进一步探索将 cross layer 作为其他模型的构建模块、为更深的 cross network 实现有效的训练、研究 cross network 在多项式逼近中的效率，并更好地理解其与 deep network 在优化过程中的相互作用。

参考文献

(1)
Blondel et al. (2016) Mathieu Blondel, Akinori Fujino, Naonori Ueda, 与 Masakazu Ishihata. 2016. Higher-Order Factorization Machines. 见 Advances in Neural Information Processing Systems. 3351–3359.
Canini (2012) K. Canini. 2012. Sibyl: A system for large scale supervised machine learning. Technical Talk (2012).
Chapelle et al. (2015) Olivier Chapelle, Eren Manavoglu, 与 Romer Rosales. 2015. Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology (TIST) 5, 4 (2015), 61.
Cheng et al. (2016) Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, 等. 2016. Wide & Deep Learning for Recommender Systems. arXiv preprint arXiv:1606.07792 (2016).
He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, 与 Jian Sun. 2015. Deep residual learning for image recognition. arXiv preprint arXiv:1512.03385 (2015).
Ioffe 与 Szegedy (2015) Sergey Ioffe 与 Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167 (2015).
Juan et al. (2017) Yuchin Juan, Damien Lefortier, 与 Olivier Chapelle. 2017. Field-aware factorization machines in a real-world online advertising system. 见 Proceedings of the 26th International Conference on World Wide Web Companion. International World Wide Web Conferences Steering Committee, 680–688.
Juan et al. (2016) Yuchin Juan, Yong Zhuang, Wei-Sheng Chin, 与 Chih-Jen Lin. 2016. Field-aware factorization machines for CTR prediction. 见 Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 43–50.
Kingma 与 Ba (2014) Diederik Kingma 与 Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).
LeCun et al. (2015) Yann LeCun, Yoshua Bengio, 与 Geoffrey Hinton. 2015. Deep learning. Nature 521, 7553 (2015), 436–444.
Rendle (2010) Steffen Rendle. 2010. Factorization machines. 见 2010 IEEE International Conference on Data Mining. IEEE, 995–1000.
Rendle (2012) Steffen Rendle. 2012. Factorization Machines with libFM. ACM Trans. Intell. Syst. Technol. 3, 3, 第 57 篇文章 (2012 年 5 月), 22 页.
Rudin et al. (1964) Walter Rudin 等. 1964. Principles of mathematical analysis. Vol. 3. McGraw-Hill New York.
Schmidhuber (2015) Jürgen Schmidhuber. 2015. Deep learning in neural networks: An overview. Neural networks 61 (2015), 85–117.
Shan et al. (2016) Ying Shan, T Ryan Hoens, Jian Jiao, Haijing Wang, Dong Yu, 与 JC Mao. 2016. Deep Crossing: Web-Scale Modeling without Manually Crafted Combinatorial Features. 见 Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 255–262.
Valiant (2014) Gregory Valiant. 2014. Learning polynomials with neural networks. (2014).
Veit et al. (2016) Andreas Veit, Michael J Wilber, 与 Serge Belongie. 2016. Residual Networks Behave Like Ensembles of Relatively Shallow Networks. 见 Advances in Neural Information Processing Systems 29, D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, 与 R. Garnett (编). Curran Associates, Inc., 550–558.
Yang 与 Gittens (2015) Jiyan Yang 与 Alex Gittens. 2015. Tensor machines for learning target-specific polynomial features. arXiv preprint arXiv:1504.01697 (2015).

附录：定理 3.1 的证明

证明。

记号。设 ${\textstyle \mathbf{i}}$ 为由 0 与 1 组成的多重指标向量，其最后一项固定为 1。对于多重指标 ${\textstyle {\mathbf{α}} = {\lbrack\alpha_{1},\cdots,\alpha_{d}\rbrack} \in {\mathbb{N}}^{d}}$ 与 ${\textstyle \mathbf{x} = {\lbrack x_{1},\cdots,x_{d}\rbrack}^{T}}$ ，定义 ${\textstyle {|{\mathbf{α}}|} = {\sum_{i = 1}^{d}\alpha_{i}}}$ ，以及 ${\textstyle \mathbf{x}^{\mathbf{α}} = {x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\cdots\hspace{0pt}x_{d}^{\alpha_{d}}}}$ 。

我们首先用数学归纳法证明

(9)		${{g_{l}\hspace{0pt}{(\mathbf{x}_{0})}} = {\mathbf{x}_{l}^{T}\hspace{0pt}\mathbf{w}_{l}} = {\sum\limits_{p = 1}^{l + 1}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p}}{\prod\limits_{j = 0}^{l}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}}},$

然后将上式改写以得到所需的结论。

基础情形。当 ${\textstyle l = 0}$ 时， ${\textstyle {g_{0}\hspace{0pt}{(\mathbf{x}_{0})}} = {\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{0}}}$ 。显然公式 9 成立。

归纳步骤。假设当 ${\textstyle l = k}$ 时，

	${{g_{k}\hspace{0pt}{(\mathbf{x}_{0})}} = {\mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k}} = {\sum\limits_{p = 1}^{k + 1}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p}}{\prod\limits_{j = 0}^{k}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}}}.$

当 ${\textstyle l = {k + 1}}$ 时，

(10)		$\begin{array}{r} {{\mathbf{x}_{k + 1}^{T}\hspace{0pt}\mathbf{w}_{k + 1}} = {{{({\mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k}})}\hspace{0pt}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{k + 1}})}} + {\mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k + 1}}}} \end{array}$

由于 ${\textstyle \mathbf{x}_{k}}$ 只包含 ${\textstyle \mathbf{w}_{0},\ldots,\mathbf{w}_{k - 1}}$ ，因此 ${\textstyle \mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k + 1}}$ 的表达式可以由 ${\textstyle \mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k}}$ 的表达式中将所有出现的 ${\textstyle \mathbf{w}_{k}}$ 替换为 ${\textstyle \mathbf{w}_{k + 1}}$ 得到。于是

(11)		$\begin{array}{cl} & {{\mathbf{x}_{k + 1}^{T}\hspace{0pt}\mathbf{w}_{k + 1}} =} \\ & {{\sum\limits_{p = 1}^{k + 1}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p}}{{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{k + 1}})}\hspace{0pt}{\prod\limits_{j = 0}^{k}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}}} + {\sum\limits_{p = 1}^{k + 1}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p}}{{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{k + 1}})}^{i_{k}}\hspace{0pt}{\prod\limits_{j = 0}^{k - 1}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}}}} \\ = & {{\sum\limits_{p = 2}^{k + 2}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p \\ i_{k} = 1}}{\prod\limits_{j = 0}^{k + 1}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}} + {\sum\limits_{p = 1}^{k + 1}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p \\ i_{k} = 0}}{\prod\limits_{j = 0}^{k + 1}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}}} \\ = & {{\sum\limits_{p = 2}^{k + 1}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p}}{\prod\limits_{j = 0}^{k + 1}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}} + {({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{k + 1}})} + {\prod\limits_{j = 0}^{k + 1}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}}} \\ = & {{\sum\limits_{p = 1}^{k + 2}{\sum\limits_{\substack{{\|\mathbf{i}\|} = p}}{\prod\limits_{j = 0}^{k + 1}{({\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{j}})}^{i_{j}}}}}.} \end{array}$

第一个等号是把 ${\textstyle \mathbf{i}}$ 的长度由 ${\textstyle k + 1}$ 扩大到 ${\textstyle k + 2}$ 的结果。第二个等号利用了 ${\textstyle \mathbf{i}}$ 的最后一项按定义恒为 1 这一事实，最后一个等号同理。根据归纳假设，公式 9 对所有 ${\textstyle l \in {\mathbb{Z}}}$ 成立。

接下来，我们通过对公式 9 中的项重新排列来计算 ${\textstyle \mathbf{x}^{\mathbf{α}}}$ 的系数 ${\textstyle c_{\mathbf{α}}\hspace{0pt}{(\mathbf{w}_{0},\cdots,\mathbf{w}_{l})}}$ 。注意 ${\textstyle \underset{\alpha_{1}}{\underbrace{x_{1}\hspace{0pt}\cdots\hspace{0pt}x_{1}}}\hspace{0pt}\cdots\hspace{0pt}\underset{\alpha_{d}}{\underbrace{x_{d}\hspace{0pt}\cdots\hspace{0pt}x_{d}}}}$ 的所有不同排列都具有 ${\textstyle \mathbf{x}^{\mathbf{α}}}$ 的形式。因此， ${\textstyle c_{\mathbf{α}}}$ 等于公式 9 中各排列对应权重之和。排列 ${\textstyle x_{j_{1}}\hspace{0pt}x_{j_{2}}\hspace{0pt}\cdots\hspace{0pt}x_{j_{p}}}$ 对应的权重为

	${\sum\limits_{i_{1},\cdots,i_{p}}{w_{i_{1}}^{(j_{1})}\hspace{0pt}w_{i_{2}}^{(j_{2})}\hspace{0pt}\cdots\hspace{0pt}w_{i_{p}}^{(j_{p})}}},$

其中 ${\textstyle (i_{1},\cdots,i_{p})}$ 属于满足 ${\textstyle {|\mathbf{i}|} = p}$ 的所有相应活动指标的集合，具体地，

	${(i_{1},\cdots,i_{p})} \in B_{p} = :\left\{ \mathbf{y} \in {\{ 0,1,\cdots,l\}}^{p} \middle\| y_{i} < y_{j} \land y_{p} = l \right\}.$

因此，若用 ${\textstyle P_{\mathbf{α}}}$ 表示 ${\textstyle ({\underset{\alpha_{1}}{\underbrace{1\hspace{0pt}\cdots\hspace{0pt}1}}\hspace{0pt}\cdots\hspace{0pt}\underset{\alpha_{d}}{\underbrace{d\hspace{0pt}\cdots\hspace{0pt}d}}})}$ 的所有排列构成的集合，则得到所要的结论

(12)		${c_{\mathbf{α}} = {\sum\limits_{{j_{1},\cdots,j_{p}} \in P_{p}}{\sum\limits_{{i_{1},\cdots,i_{p}} \in B_{p}}{\prod\limits_{k = 1}^{p}w_{i_{k}}^{(j_{k})}}}}}.$

∎