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})}}}}}.$

∎