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 y Mingliang Wang Google Inc.New YorkNY mlwang@google.com

Resumen.

La ingeniería de features ha sido la clave del éxito de muchos modelos de predicción. Sin embargo, el proceso no es trivial y a menudo requiere ingeniería manual de features o búsqueda exhaustiva. Las DNNs son capaces de aprender automáticamente interacciones de features; sin embargo, generan todas las interacciones de forma implícita y no son necesariamente eficientes a la hora de aprender todos los tipos de cross features. En este trabajo proponemos la Deep & Cross Network (DCN), que conserva las ventajas de un modelo DNN y, además, introduce una novedosa cross network que es más eficiente en el aprendizaje de ciertas interacciones de features de grado acotado. En particular, DCN aplica explícitamente el cruce de features en cada capa, no requiere ingeniería manual de features y añade una complejidad adicional despreciable al modelo DNN. Nuestros resultados experimentales han demostrado su superioridad sobre los algoritmos del estado del arte en el dataset de predicción de CTR y en el dataset de clasificación densa, tanto en precisión del modelo como en uso de memoria.

1. Introducción

La predicción de la tasa de clics (CTR) es un problema a gran escala esencial para la industria multimillonaria de la publicidad en línea. En la industria publicitaria, los anunciantes pagan a los publishers para mostrar sus anuncios en los sitios de los publishers. Un modelo de pago popular es el modelo de coste por clic (CPC), donde a los anunciantes sólo se les cobra cuando se produce un clic. Como consecuencia, los ingresos del publisher dependen en gran medida de la capacidad de predecir el CTR con precisión.

Identificar features predictivas frecuentes y, al mismo tiempo, explorar cross features no vistas o raras es la clave para hacer buenas predicciones. Sin embargo, los datos para sistemas de recomendación a escala web son, en su mayoría, discretos y categóricos, lo que conduce a un espacio de features grande y disperso, difícil de explorar. Esto ha limitado a la mayoría de los sistemas a gran escala a modelos lineales, como la regresión logística.

Los modelos lineales (Chapelle et al., 2015) son simples, interpretables y fáciles de escalar; sin embargo, su poder expresivo es limitado. Por otro lado, se ha demostrado que las cross features son significativas para mejorar la expresividad de los modelos. Lamentablemente, identificar tales features a menudo requiere ingeniería manual o búsqueda exhaustiva; además, generalizar a interacciones de features no vistas resulta difícil.

En este trabajo, nuestro objetivo es evitar la ingeniería de features específica para cada tarea introduciendo una novedosa estructura de red neuronal — una cross network — que aplica explícitamente el cruce de features de manera automática. La cross network consta de múltiples capas, donde el grado más alto de las interacciones está demostrablemente determinado por la profundidad de la capa. Cada capa produce interacciones de orden superior basadas en las existentes y conserva las interacciones de las capas previas. Entrenamos la cross network conjuntamente con una red neuronal profunda (DNN) (LeCun et al., 2015; Schmidhuber, 2015). Las DNNs prometen capturar interacciones muy complejas entre features; sin embargo, en comparación con nuestra cross network, requieren casi un orden de magnitud más de parámetros, no son capaces de formar cross features de manera explícita y pueden no aprender de forma eficiente algunos tipos de interacciones de features. Entrenar conjuntamente los componentes cross y DNN, en cambio, captura eficientemente interacciones de features predictivas y ofrece un rendimiento del estado del arte en el dataset Criteo CTR.

1.1. Trabajo relacionado

Debido al drástico aumento en tamaño y dimensionalidad de los conjuntos de datos, se han propuesto numerosos métodos para evitar la ingeniería de features específica de tarea, mayoritariamente basados en técnicas de embedding y redes neuronales.

Las factorization machines (FMs) (Rendle, 2010, 2012) proyectan features dispersas en vectores densos de baja dimensión y aprenden interacciones de features a partir de los productos internos de los vectores. Las field-aware factorization machines (FFMs) (Juan et al., 2016, 2017) permiten además que cada feature aprenda varios vectores, cada uno asociado a un campo. Lamentablemente, las estructuras superficiales de FMs y FFMs limitan su poder representativo. Existen trabajos que extienden las FMs a órdenes superiores (Blondel et al., 2016; Yang y Gittens, 2015), pero un inconveniente reside en su gran número de parámetros, que conlleva un coste computacional indeseable. Las redes neuronales profundas (DNN) son capaces de aprender interacciones de features de alto grado no triviales gracias a los vectores de embedding y a las funciones de activación no lineales. El reciente éxito de la Residual Network (He et al., 2015) ha permitido entrenar redes muy profundas. Deep Crossing (Shan et al., 2016) extiende las residual networks y logra el aprendizaje automático de features apilando todo tipo de entradas.

El extraordinario éxito del deep learning ha motivado análisis teóricos sobre su poder representativo. Existen investigaciones (Valiant, 2014; Veit et al., 2016) que muestran que las DNNs son capaces de aproximar una función arbitraria, bajo ciertos supuestos de suavidad, con precisión arbitraria, dado un número suficiente de unidades o capas ocultas. Además, en la práctica se ha observado que las DNNs funcionan bien con un número factible de parámetros. Una razón clave es que la mayoría de las funciones de interés práctico no son arbitrarias.

Sin embargo, una pregunta pendiente es si las DNNs son realmente las más eficientes para representar tales funciones de interés práctico. En la competición de Kaggle¹¹1https://www.kaggle.com/, las features creadas manualmente en muchas soluciones ganadoras son de bajo grado, en formato explícito y efectivas. En cambio, las features aprendidas por las DNNs son implícitas y altamente no lineales. Esto ha arrojado luz sobre el diseño de un modelo capaz de aprender interacciones de features de grado acotado de forma más eficiente y explícita que una DNN universal.

El modelo wide-and-deep (Cheng et al., 2016) es un modelo en este espíritu. Toma cross features como entradas a un modelo lineal y entrena conjuntamente el modelo lineal con un modelo DNN. Sin embargo, el éxito de wide-and-deep depende de una elección adecuada de cross features, un problema exponencial para el cual aún no existe un método claramente eficiente.

1.2. Contribuciones principales

En este trabajo proponemos el modelo Deep & Cross Network (DCN), que permite el aprendizaje automático de features a escala web con entradas tanto dispersas como densas. DCN captura eficientemente interacciones efectivas de features de grado acotado, aprende interacciones altamente no lineales, no requiere ingeniería manual de features ni búsqueda exhaustiva, y tiene un coste computacional bajo.

Las principales contribuciones del trabajo incluyen:

•

Proponemos una novedosa cross network que aplica explícitamente el cruce de features en cada capa, aprende eficientemente cross features predictivas de grado acotado y no requiere ingeniería manual de features ni búsqueda exhaustiva.
•

La cross network es simple pero efectiva. Por diseño, el grado polinómico más alto aumenta en cada capa y queda determinado por la profundidad. La red contiene todos los términos cruzados hasta el grado más alto, con coeficientes todos distintos.
•

La cross network es eficiente en memoria y fácil de implementar.
•

Nuestros resultados experimentales han demostrado que, gracias a una cross network, DCN obtiene un logloss menor que una DNN con casi un orden de magnitud menos de parámetros.

El trabajo está organizado de la siguiente manera: la Sección 2 describe la arquitectura de la Deep & Cross Network. La Sección 3 analiza la cross network en detalle. La Sección 4 muestra los resultados experimentales.

2. Deep & Cross Network (DCN)

En esta sección describimos la arquitectura de los modelos Deep & Cross Network (DCN). Un modelo DCN comienza con una embedding and stacking layer, seguida de una cross network y una deep network en paralelo. A continuación se encuentra una combination layer final que combina las salidas de las dos redes. El modelo DCN completo se muestra en la Figura 1.

2.1. Embedding and Stacking Layer

Consideramos datos de entrada con features dispersas y densas. En sistemas de recomendación a escala web como la predicción de CTR, las entradas son mayoritariamente features categóricas, e.g. "country=usa". Estas features suelen codificarse como vectores one-hot, e.g. "[0,1,0]"; sin embargo, esto a menudo conduce a espacios de features de dimensionalidad excesivamente alta para vocabularios grandes.

Para reducir la dimensionalidad, empleamos un procedimiento de embedding que transforma estas features binarias en vectores densos de valores reales (comúnmente llamados embedding vectors):

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

donde ${\textstyle \mathbf{x}_{\text{embed},i}}$ es el embedding vector, ${\textstyle \mathbf{x}_{i}}$ es la entrada binaria en la ${\textstyle i}$ -ésima categoría, y ${\textstyle W_{\text{embed},i} \in {\mathbb{R}}^{n_{e} \times n_{v}}}$ es la matriz de embedding correspondiente, que se optimiza junto con los demás parámetros de la red, y ${\textstyle n_{e},n_{v}}$ son el tamaño del embedding y el tamaño del vocabulario, respectivamente.

Finalmente, apilamos los embedding vectors junto con las features densas normalizadas ${\textstyle \mathbf{x}_{\text{dense}}}$ en un único vector:

(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},$

y alimentamos ${\textstyle \mathbf{x}_{0}}$ a la red.

2.2. Cross Network

La idea clave de nuestra novedosa cross network es aplicar el cruce explícito de features de manera eficiente. La cross network está compuesta por cross layers, donde cada capa tiene la siguiente fórmula:

(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}}},$

donde ${\textstyle {\mathbf{x}_{l},\mathbf{x}_{l + 1}} \in {\mathbb{R}}^{d}}$ son vectores columna que denotan las salidas de la ${\textstyle l}$ -ésima y ${\textstyle ({l + 1})}$ -ésima cross layers, respectivamente; ${\textstyle {\mathbf{w}_{l},\mathbf{b}_{l}} \in {\mathbb{R}}^{d}}$ son los parámetros de peso y sesgo de la ${\textstyle l}$ -ésima capa. Cada cross layer vuelve a sumar su entrada tras un cruce de features ${\textstyle f}$ , y la función de mapeo ${\textstyle f:{{\mathbb{R}}^{d}\mapsto{\mathbb{R}}^{d}}}$ ajusta el residual de ${\textstyle \mathbf{x}_{l + 1} - \mathbf{x}_{l}}$ . En la Figura 2 se muestra una visualización de una cross layer.

Interacciones de alto grado entre features. La estructura especial de la cross network hace que el grado de las cross features crezca con la profundidad de la capa. El grado polinómico más alto (en términos de la entrada ${\textstyle \mathbf{x}_{0}}$ ) para una cross network de ${\textstyle l}$ capas es ${\textstyle l + 1}$ . De hecho, la cross network contiene todos los términos cruzados ${\textstyle x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\ldots\hspace{0pt}x_{d}^{\alpha_{d}}}$ de grado entre 1 y ${\textstyle l + 1}$ . Un análisis detallado se encuentra en la Sección 3.

Análisis de complejidad. Sea ${\textstyle L_{c}}$ el número de cross layers y ${\textstyle d}$ la dimensión de entrada. Entonces, el número de parámetros que intervienen en la cross network es

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

La complejidad temporal y espacial de una cross network es lineal en la dimensión de entrada. Por tanto, una cross network introduce una complejidad despreciable en comparación con su contraparte profunda, manteniendo la complejidad global de DCN al mismo nivel que la de una DNN tradicional. Esta eficiencia se beneficia de la propiedad de rango uno de ${\textstyle \mathbf{x}_{0}\hspace{0pt}\mathbf{x}_{l}^{T}}$ , que nos permite generar todos los términos cruzados sin calcular ni almacenar la matriz completa.

El reducido número de parámetros de la cross network limita la capacidad del modelo. Para capturar interacciones altamente no lineales, introducimos en paralelo una deep network.

2.3. Deep Network

La deep network es una red neuronal feed-forward totalmente conectada, donde cada deep layer tiene la siguiente fórmula:

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

donde ${\textstyle {\mathbf{h}_{l} \in {\mathbb{R}}^{n_{l}}},{\mathbf{h}_{l + 1} \in {\mathbb{R}}^{n_{l + 1}}}}$ son las capas ocultas ${\textstyle l}$ -ésima y ${\textstyle ({l + 1})}$ -ésima, respectivamente; ${\textstyle {W_{l} \in {\mathbb{R}}^{n_{l + 1} \times n_{l}}},{\mathbf{b}_{l} \in {\mathbb{R}}^{n_{l + 1}}}}$ son los parámetros de la ${\textstyle l}$ -ésima deep layer; y ${\textstyle f\hspace{0pt}{( \cdot )}}$ es la función ReLU.

Análisis de complejidad. Por simplicidad, asumimos que todas las deep layers tienen el mismo tamaño. Sea ${\textstyle L_{d}}$ el número de deep layers y ${\textstyle m}$ el tamaño de las deep layers. Entonces, el número de parámetros en la deep network es

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

2.4. Capa de combinación

La capa de combinación concatena las salidas de las dos redes y alimenta el vector concatenado a una capa de logits estándar.

La siguiente es la fórmula para un problema de clasificación binaria:

(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)}},$

donde ${\textstyle {\mathbf{x}_{L_{1}} \in {\mathbb{R}}^{d}},{\mathbf{h}_{L_{2}} \in {\mathbb{R}}^{m}}}$ son las salidas de la cross network y de la deep network, respectivamente, ${\textstyle \mathbf{w}_{\text{logits}} \in {\mathbb{R}}^{({d + m})}}$ es el vector de pesos de la capa de combinación, y ${\textstyle {\sigma\hspace{0pt}{(x)}} = {1/{({1 + {\exp{({- x})}}})}}}$ .

La función de pérdida es la log loss junto con un término de regularización,

(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}$

donde los ${\textstyle p_{i}}$ 's son las probabilidades calculadas a partir de la Ecuación 5, los ${\textstyle y_{i}}$ 's son las etiquetas verdaderas, ${\textstyle N}$ es el número total de entradas y ${\textstyle \lambda}$ es el parámetro de regularización ${\textstyle L_{2}}$ .

Entrenamos ambas redes conjuntamente, ya que esto permite que cada red individual sea consciente de las demás durante el entrenamiento.

3. Análisis de la cross network

En esta sección analizamos la cross network de DCN con el objetivo de comprender su efectividad. Ofrecemos tres perspectivas: aproximación polinómica, generalización a las FMs y proyección eficiente. Por simplicidad, asumimos ${\textstyle \mathbf{b}_{i} = 0}$ .

Notaciones. Sea el ${\textstyle i}$ -ésimo elemento de ${\textstyle \mathbf{w}_{j}}$ denotado por ${\textstyle w_{j}^{(i)}}$ . Para multi-índice ${\textstyle {\mathbf{α}} = {\lbrack\alpha_{1},\cdots,\alpha_{d}\rbrack} \in {\mathbb{N}}^{d}}$ y ${\textstyle \mathbf{x} = {\lbrack x_{1},\cdots,x_{d}\rbrack} \in {\mathbb{R}}^{d}}$ , definimos ${\textstyle {|{\mathbf{α}}|} = {\sum_{i = 1}^{d}\alpha_{i}}}$ .

Terminología. El grado de un término cruzado (monomio) ${\textstyle x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\cdots\hspace{0pt}x_{d}^{\alpha_{d}}}$ se define como ${\textstyle |{\mathbf{α}}|}$ . El grado de un polinomio se define por el grado más alto de sus términos.

3.1. Aproximación polinómica

Por el teorema de aproximación de Weierstrass (Rudin et al., 1964), cualquier función bajo cierta hipótesis de suavidad puede aproximarse mediante un polinomio con precisión arbitraria. Por tanto, analizamos la cross network desde la perspectiva de la aproximación polinómica. En particular, la cross network aproxima la clase de polinomios del mismo grado de un modo eficiente, expresivo y que generaliza mejor en datasets del mundo real.

Estudiamos en detalle la aproximación de una cross network a la clase de polinomios del mismo grado. Denotemos por ${\textstyle P_{n}\hspace{0pt}{(\mathbf{x})}}$ la clase de polinomios multivariados de grado ${\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\}.$

Cada polinomio en esta clase tiene ${\textstyle O\hspace{0pt}{(d^{n})}}$ coeficientes. Mostramos que, con sólo ${\textstyle O\hspace{0pt}{(d)}}$ parámetros, la cross network contiene todos los términos cruzados que aparecen en el polinomio del mismo grado, con un coeficiente distinto para cada término.

Teorema 3.1.

Considérese una cross network de ${\textstyle l}$ capas con la ${\textstyle i + 1}$ -ésima capa definida como ${\textstyle \mathbf{x}_{i + 1} = {{\mathbf{x}_{0}\hspace{0pt}\mathbf{x}_{i}^{T}\hspace{0pt}\mathbf{w}_{i}} + \mathbf{x}_{i}}}$ . Sea la entrada de la red ${\textstyle \mathbf{x}_{0} = {\lbrack x_{1},x_{2},\ldots,x_{d}\rbrack}^{T}}$ , la salida ${\textstyle {g_{l}\hspace{0pt}{(\mathbf{x}_{0})}} = {\mathbf{x}_{l}^{T}\hspace{0pt}\mathbf{w}_{l}}}$ , y los parámetros ${\textstyle {\mathbf{w}_{i},\mathbf{b}_{i}} \in {\mathbb{R}}^{d}}$ . Entonces, el polinomio multivariado ${\textstyle g_{l}\hspace{0pt}{(\mathbf{x}_{0})}}$ reproduce los polinomios de la siguiente clase:

	$\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\},$

donde ${\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{α}}}$ es una constante independiente de los ${\textstyle \mathbf{w}_{i}}$ 's, ${\textstyle \mathbf{i} = {\lbrack i_{1},\ldots,i_{|{\mathbf{α}}|}\rbrack}}$ y ${\textstyle \mathbf{j} = {\lbrack j_{1},\ldots,j_{|{\mathbf{α}}|}\rbrack}}$ son multi-índices, ${\textstyle B_{\mathbf{α}} = \left\{ \mathbf{y} \in {\{ 0,1,\cdots,l\}}^{|{\mathbf{α}}|} \middle| y_{i} < {y_{j} \land y_{|{\mathbf{α}}|}} = l \right\}}$ , y ${\textstyle P_{\mathbf{α}}}$ es el conjunto de todas las permutaciones de los índices ${\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}}})}$ .

La demostración del Teorema 3.1 está en el Apéndice. Veamos un ejemplo. Considérese el coeficiente ${\textstyle c_{\mathbf{α}}}$ para ${\textstyle x_{1}\hspace{0pt}x_{2}\hspace{0pt}x_{3}}$ con ${\textstyle {\mathbf{α}} = {(1,1,1,0,\ldots,0)}}$ . Salvo una constante, cuando ${\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)}}}}$ ; cuando ${\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. Generalización de las FMs

La cross network comparte el espíritu del reparto de parámetros del modelo FM y lo extiende además a una estructura más profunda.

En un modelo FM, la feature ${\textstyle x_{i}}$ se asocia con un vector de pesos ${\textstyle \mathbf{v}_{i}}$ , y el peso del término cruzado ${\textstyle x_{i}\hspace{0pt}x_{j}}$ se calcula como ${\textstyle \langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle}$ . En DCN, ${\textstyle x_{i}}$ se asocia con escalares ${\textstyle {\{ w_{k}^{(i)}\}}_{k = 1}^{l}}$ , y el peso de ${\textstyle x_{i}\hspace{0pt}x_{j}}$ es la multiplicación de parámetros provenientes de los conjuntos ${\textstyle {\{ w_{k}^{(i)}\}}_{k = 0}^{l}}$ y ${\textstyle {\{ w_{k}^{(j)}\}}_{k = 0}^{l}}$ . Ambos modelos hacen que cada feature aprenda algunos parámetros independientes de las otras features, y el peso de un término cruzado es una determinada combinación de los parámetros correspondientes.

El reparto de parámetros no sólo hace al modelo más eficiente, sino que también le permite generalizar a interacciones de features no vistas y ser más robusto al ruido. Por ejemplo, considérense datasets con features dispersas. Si dos features binarias ${\textstyle x_{i}}$ y ${\textstyle x_{j}}$ co-ocurren raramente o nunca en los datos de entrenamiento, es decir, ${\textstyle x_{i} \neq {0 \land x_{j}} \neq 0}$ , entonces el peso aprendido de ${\textstyle x_{i}\hspace{0pt}x_{j}}$ no aportaría información significativa para la predicción.

La FM es una estructura superficial y está limitada a representar términos cruzados de grado 2. DCN, por el contrario, es capaz de construir todos los términos cruzados ${\textstyle x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\ldots\hspace{0pt}x_{d}^{\alpha_{d}}}$ con grado ${\textstyle |{\mathbf{α}}|}$ acotado por una constante determinada por la profundidad de la capa, como se afirma en el Teorema 3.1. Por tanto, la cross network extiende la idea del reparto de parámetros desde una sola capa a múltiples capas y términos cruzados de alto grado. Obsérvese que, a diferencia de las FMs de orden superior, el número de parámetros en una cross network sólo crece linealmente con la dimensión de entrada.

3.3. Proyección eficiente

Cada cross layer proyecta todas las interacciones por pares entre ${\textstyle \mathbf{x}_{0}}$ y ${\textstyle \mathbf{x}_{l}}$ , de manera eficiente, de vuelta a la dimensión de la entrada.

Considérese ${\textstyle \overset{\sim}{\mathbf{x}} \in {\mathbb{R}}^{d}}$ como entrada a una cross layer. La cross layer construye implícitamente ${\textstyle d^{2}}$ interacciones por pares ${\textstyle x_{i}\hspace{0pt}{\overset{\sim}{x}}_{j}}$ , y luego las proyecta implícitamente de vuelta a la dimensión ${\textstyle d}$ de manera eficiente en memoria. Un enfoque directo, sin embargo, conlleva un coste cúbico.

Nuestra cross layer ofrece una solución eficiente para reducir el coste a lineal en la dimensión ${\textstyle d}$ . Considérese ${\textstyle \mathbf{x}_{p} = {\mathbf{x}_{0}\hspace{0pt}{\overset{\sim}{\mathbf{x}}}^{T}\hspace{0pt}\mathbf{w}}}$ . Esto es, de hecho, equivalente a

(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}$

donde el vector fila contiene todas las ${\textstyle d^{2}}$ interacciones por pares ${\textstyle x_{i}\hspace{0pt}{\overset{\sim}{x}}_{j}}$ 's, y la matriz de proyección tiene una estructura diagonal por bloques con ${\textstyle \mathbf{w} \in {\mathbb{R}}^{d}}$ como vector columna.

4. Resultados experimentales

En esta sección evaluamos el rendimiento de DCN en algunos datasets de clasificación populares.

4.1. Datos de Criteo Display Ads

El dataset Criteo Display Ads²²2https://www.kaggle.com/c/criteo-display-ad-challenge tiene como objetivo predecir la tasa de clics en anuncios. Cuenta con 13 features enteras y 26 categóricas, donde cada categoría tiene una cardinalidad alta. Para este dataset, una mejora de 0,001 en logloss se considera prácticamente significativa. Considerando una gran base de usuarios, una pequeña mejora en la precisión de predicción puede traducirse en un gran aumento de los ingresos de una empresa. Los datos contienen 11 GB de logs de usuario de un periodo de 7 días ( ${\textstyle \sim}$ 41 millones de registros). Utilizamos los datos de los primeros 6 días para entrenamiento y dividimos aleatoriamente los datos del día 7 en conjuntos de validación y test del mismo tamaño.

4.2. Detalles de implementación

DCN se implementa en TensorFlow; comentamos brevemente algunos detalles de implementación para entrenar DCN.

Procesamiento de datos y embedding. Las features de valores reales se normalizan aplicando una transformación logarítmica. Para las features categóricas, las incrustamos en vectores densos de dimensión ${\textstyle {6 \times {(\text{category cardinality})}^{1/4}}.}$ Concatenando todos los embeddings se obtiene un vector de dimensión 1026.
Optimización. Aplicamos optimización estocástica por mini-lotes con el optimizador Adam (Kingma y Ba, 2014). El tamaño de batch se fija en 512. Se aplicó batch normalization (Ioffe y Szegedy, 2015) a la deep network y la norma de recorte de gradiente se fijó en 100.
Regularización. Usamos early stopping, ya que no encontramos eficaces la regularización ${\textstyle L_{2}}$ ni el dropout.
Hiperparámetros. Reportamos los resultados a partir de una búsqueda en cuadrícula sobre el número de capas ocultas, el tamaño de la capa oculta, el learning rate inicial y el número de cross layers. El número de capas ocultas varió de 2 a 5, con tamaños de capa oculta de 32 a 1024. Para DCN, el número de cross layers³³3Más cross layers no produjeron mejoras significativas, por lo que nos restringimos a un rango pequeño para un ajuste más fino. va de 1 a 6. El learning rate inicial⁴⁴4Experimentalmente observamos que para el dataset Criteo, un learning rate mayor que 0,001 suele degradar el rendimiento. se ajustó de 0,0001 a 0,001 con incrementos de 0,0001. Todos los experimentos aplicaron early stopping en el paso de entrenamiento 150.000, a partir del cual comenzaba el sobreajuste.

4.3. Modelos de comparación

Comparamos DCN con cinco modelos: el modelo DCN sin cross network (DNN), regresión logística (LR), Factorization Machines (FMs), el modelo Wide and Deep (W&D) y Deep Crossing (DC).

DNN. La capa de embedding, la capa de salida y el proceso de ajuste de hiperparámetros son los mismos que en DCN. El único cambio respecto al modelo DCN es que no tiene cross layers.
LR. Usamos Sibyl (Canini, 2012) — un sistema de aprendizaje automático a gran escala para regresión logística distribuida. Las features enteras se discretizaron en escala logarítmica. Las cross features se seleccionaron mediante una herramienta sofisticada de selección de features. Se utilizaron todas las features individuales.
FM. Usamos un modelo basado en FM con detalles propietarios.
W&D. A diferencia de DCN, su componente wide toma como entrada features dispersas en bruto y depende de búsqueda exhaustiva y conocimiento del dominio para seleccionar cross features predictivas. Omitimos la comparación, ya que no se conoce un buen método para seleccionar cross features.
DC. Comparado con DCN, DC no forma cross features explícitas. Se basa principalmente en el apilado y en residual units para crear cruces implícitos. Aplicamos la misma capa de embedding (apilado) que DCN, seguida de otra capa ReLU para generar la entrada a una secuencia de residual units. El número de residual units se ajustó de 1 a 5, con dimensión de entrada y dimensión cross de 100 a 1026.

4.4. Rendimiento del modelo

En esta sección, primero listamos el mejor rendimiento de los distintos modelos en logloss y luego comparamos DCN con DNN en detalle, es decir, profundizamos en los efectos introducidos por la cross network.

Rendimiento de los distintos modelos. El mejor logloss de test de los distintos modelos se lista en la Tabla 1. La configuración óptima de hiperparámetros fue de 2 deep layers de tamaño 1024 y 6 cross layers para el modelo DCN, 5 deep layers de tamaño 1024 para la DNN, 5 residual units con dimensión de entrada 424 y dimensión cross 537 para DC, y 42 cross features para el modelo LR. Que el mejor rendimiento se obtuviera con la arquitectura cross más profunda sugiere que las interacciones de features de orden superior provenientes de la cross network son valiosas. Como puede verse, DCN supera a todos los demás modelos por un amplio margen. En particular, supera al modelo DNN del estado del arte usando sólo el 40% de la memoria consumida por la DNN.

Modelo	DCN	DC	DNN	FM	LR
Logloss	0,4419	0,4425	0,4428	0,4464	0,4474

Para la configuración óptima de hiperparámetros de cada modelo, también reportamos la media y la desviación estándar del logloss de test sobre 10 ejecuciones independientes: 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}}}$ . Como puede verse, DCN supera consistentemente a los demás modelos por un amplio margen.

Comparaciones entre DCN y DNN. Considerando que la cross network sólo introduce ${\textstyle O\hspace{0pt}{(d)}}$ parámetros adicionales, comparamos DCN con su deep network — una DNN tradicional — y presentamos los resultados experimentales variando el presupuesto de memoria y la tolerancia de pérdida.

En lo que sigue, la pérdida para un cierto número de parámetros se reporta como la mejor pérdida de validación entre todos los learning rates y estructuras de modelo. El número de parámetros en la capa de embedding se omitió en nuestro cálculo, ya que es idéntico en ambos modelos.

La Tabla 2 reporta el número mínimo de parámetros necesario para alcanzar un umbral deseado de logloss. De la Tabla 2 vemos que DCN es casi un orden de magnitud más eficiente en memoria que una sola DNN, gracias a la cross network, capaz de aprender interacciones de features de grado acotado de manera más eficiente.

Logloss	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}}}$

La Tabla 3 compara el rendimiento de los modelos neuronales sujetos a presupuestos de memoria fijos. Como puede verse, DCN supera consistentemente a DNN. En el régimen de pocos parámetros, el número de parámetros en la cross network es comparable al de la deep network, y la mejora clara indica que la cross network es más eficiente aprendiendo interacciones de features efectivas. En el régimen de muchos parámetros, la DNN cierra parte de la brecha; sin embargo, DCN sigue superando a DNN por un amplio margen, lo que sugiere que puede aprender eficientemente algunos tipos de interacciones de features significativas que ni siquiera un modelo DNN enorme puede capturar.

#Parámetros	${\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

Analizamos DCN con mayor detalle ilustrando el efecto de introducir una cross network en un modelo DNN dado. Primero comparamos el mejor rendimiento de DNN con el de DCN bajo el mismo número de capas y tamaño de capa, y luego, para cada configuración, mostramos cómo cambia el logloss de validación a medida que se añaden más cross layers. La Tabla 4 muestra las diferencias en logloss entre el modelo DCN y el DNN. Bajo el mismo entorno experimental, el mejor logloss del modelo DCN supera consistentemente al del modelo DNN solo de la misma estructura. Que la mejora sea consistente en todos los hiperparámetros mitiga el efecto de aleatoriedad debido a la inicialización y a la optimización estocástica.

[[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

La Figura 3 muestra la mejora a medida que aumentamos el número de cross layers en configuraciones seleccionadas aleatoriamente. Para las deep networks de la Figura 3 se observa una mejora clara cuando se añade 1 cross layer al modelo. A medida que se introducen más cross layers, en algunas configuraciones el logloss continúa disminuyendo, lo que indica que los términos cruzados introducidos son efectivos en la predicción; en otras, en cambio, el logloss empieza a fluctuar e incluso a aumentar ligeramente, lo que indica que las interacciones de features de mayor grado introducidas no son útiles.

4.5. Datasets no-CTR

Mostramos que DCN funciona bien en problemas de predicción no-CTR. Usamos los datasets forest covertype (581012 muestras y 54 features) y Higgs (11M muestras y 28 features) del repositorio UCI. Los datasets se dividieron aleatoriamente en conjuntos de entrenamiento (90%) y test (10%). Se realizó una búsqueda en cuadrícula sobre los hiperparámetros. El número de deep layers varió de 1 a 10, con tamaño de capa de 50 a 300. El número de cross layers varió de 4 a 10. El número de residual units varió de 1 a 5, con dimensiones de entrada y dimensiones cross de 50 a 300. Para DCN, el vector de entrada se introdujo directamente en la cross network.

Para los datos de forest covertype, DCN logró la mejor precisión de test de 0,9740 con el menor consumo de memoria. Tanto DNN como DC alcanzaron 0,9737. La configuración óptima de hiperparámetros fue: 8 cross layers de tamaño 54 y 6 deep layers de tamaño 292 para DCN, 7 deep layers de tamaño 292 para DNN, y 4 residual units con dimensión de entrada 271 y dimensión cross 287 para DC.

Para los datos Higgs, DCN logró el mejor logloss de test 0,4494, mientras que DNN alcanzó 0,4506. La configuración óptima de hiperparámetros fue: 4 cross layers de tamaño 28 y 4 deep layers de tamaño 209 para DCN, y 10 deep layers de tamaño 196 para DNN. DCN supera a DNN utilizando la mitad de la memoria que usa DNN.

5. Conclusión y direcciones futuras

Identificar interacciones de features efectivas ha sido la clave del éxito de muchos modelos de predicción. Lamentablemente, el proceso a menudo requiere creación manual de features y búsqueda exhaustiva. Las DNNs son populares para el aprendizaje automático de features; sin embargo, las features aprendidas son implícitas y altamente no lineales, y la red puede ser innecesariamente grande e ineficiente al aprender ciertas features. La Deep & Cross Network propuesta en este trabajo puede manejar un gran conjunto de features dispersas y densas, y aprende cross features explícitas de grado acotado conjuntamente con representaciones profundas tradicionales. El grado de las cross features aumenta en uno por cada cross layer. Nuestros resultados experimentales han demostrado su superioridad sobre los algoritmos del estado del arte tanto en datasets dispersos como densos, en términos de precisión del modelo y de uso de memoria.

Nos gustaría explorar adicionalmente el uso de cross layers como bloques de construcción en otros modelos, habilitar un entrenamiento eficaz para cross networks más profundas, investigar la eficiencia de la cross network en aproximación polinómica y comprender mejor su interacción con las deep networks durante la optimización.

Referencias

(1)
Blondel et al. (2016) Mathieu Blondel, Akinori Fujino, Naonori Ueda, y Masakazu Ishihata. 2016. Higher-Order Factorization Machines. En 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, y 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, y otros. 2016. Wide & Deep Learning for Recommender Systems. arXiv preprint arXiv:1606.07792 (2016).
He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, y Jian Sun. 2015. Deep residual learning for image recognition. arXiv preprint arXiv:1512.03385 (2015).
Ioffe y Szegedy (2015) Sergey Ioffe y 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, y Olivier Chapelle. 2017. Field-aware factorization machines in a real-world online advertising system. En 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, y Chih-Jen Lin. 2016. Field-aware factorization machines for CTR prediction. En Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 43–50.
Kingma y Ba (2014) Diederik Kingma y Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).
LeCun et al. (2015) Yann LeCun, Yoshua Bengio, y Geoffrey Hinton. 2015. Deep learning. Nature 521, 7553 (2015), 436–444.
Rendle (2010) Steffen Rendle. 2010. Factorization machines. En 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, Artículo 57 (Mayo de 2012), 22 páginas.
Rudin et al. (1964) Walter Rudin y otros. 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, y JC Mao. 2016. Deep Crossing: Web-Scale Modeling without Manually Crafted Combinatorial Features. En 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, y Serge Belongie. 2016. Residual Networks Behave Like Ensembles of Relatively Shallow Networks. En Advances in Neural Information Processing Systems 29, D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, y R. Garnett (Eds.). Curran Associates, Inc., 550–558.
Yang y Gittens (2015) Jiyan Yang y Alex Gittens. 2015. Tensor machines for learning target-specific polynomial features. arXiv preprint arXiv:1504.01697 (2015).

Apéndice: Demostración del Teorema 3.1

Demostración.

Notaciones. Sea ${\textstyle \mathbf{i}}$ un vector de multi-índices de 0's y 1's, con su última entrada fijada en 1. Para multi-índice ${\textstyle {\mathbf{α}} = {\lbrack\alpha_{1},\cdots,\alpha_{d}\rbrack} \in {\mathbb{N}}^{d}}$ y ${\textstyle \mathbf{x} = {\lbrack x_{1},\cdots,x_{d}\rbrack}^{T}}$ , definimos ${\textstyle {|{\mathbf{α}}|} = {\sum_{i = 1}^{d}\alpha_{i}}}$ , y ${\textstyle \mathbf{x}^{\mathbf{α}} = {x_{1}^{\alpha_{1}}\hspace{0pt}x_{2}^{\alpha_{2}}\hspace{0pt}\cdots\hspace{0pt}x_{d}^{\alpha_{d}}}}$ .

Primero demostramos por inducción que

(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}}}}}},$

y luego reescribimos la forma anterior para obtener la afirmación deseada.

Caso base. Cuando ${\textstyle l = 0}$ , ${\textstyle {g_{0}\hspace{0pt}{(\mathbf{x}_{0})}} = {\mathbf{x}_{0}^{T}\hspace{0pt}\mathbf{w}_{0}}}$ . Claramente la Ecuación 9 se cumple.

Paso de inducción. Asumimos que cuando ${\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}}}}}}.$

Cuando ${\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}$

Como ${\textstyle \mathbf{x}_{k}}$ sólo contiene ${\textstyle \mathbf{w}_{0},\ldots,\mathbf{w}_{k - 1}}$ , se sigue que la fórmula de ${\textstyle \mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k + 1}}$ puede obtenerse a partir de la de ${\textstyle \mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k}}$ reemplazando todos los ${\textstyle \mathbf{w}_{k}}$ 's que aparecen en ${\textstyle \mathbf{x}_{k}^{T}\hspace{0pt}\mathbf{w}_{k}}$ por ${\textstyle \mathbf{w}_{k + 1}}$ . Entonces

(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}$

La primera igualdad es resultado de aumentar el tamaño de ${\textstyle \mathbf{i}}$ de ${\textstyle k + 1}$ a ${\textstyle k + 2}$ . La segunda igualdad usa el hecho de que la última entrada de ${\textstyle \mathbf{i}}$ es siempre 1 por definición, y lo mismo se aplicó a la última igualdad. Por hipótesis de inducción, la Ecuación 9 se cumple para todo ${\textstyle l \in {\mathbb{Z}}}$ .

A continuación, calculamos ${\textstyle c_{\mathbf{α}}\hspace{0pt}{(\mathbf{w}_{0},\cdots,\mathbf{w}_{l})}}$ , el coeficiente de ${\textstyle \mathbf{x}^{\mathbf{α}}}$ , reordenando los términos en la Ecuación 9. Obsérvese que todas las distintas permutaciones de ${\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}}}}$ tienen la forma ${\textstyle \mathbf{x}^{\mathbf{α}}}$ . Por tanto, ${\textstyle c_{\mathbf{α}}}$ es la suma de todos los pesos asociados con cada permutación que aparece en la Ecuación 9. El peso para la permutación ${\textstyle x_{j_{1}}\hspace{0pt}x_{j_{2}}\hspace{0pt}\cdots\hspace{0pt}x_{j_{p}}}$ es

	${\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})}}},$

donde ${\textstyle (i_{1},\cdots,i_{p})}$ pertenece al conjunto de todos los índices activos correspondientes para ${\textstyle {|\mathbf{i}|} = p}$ , específicamente,

	${(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\}.$

Por tanto, si denotamos por ${\textstyle P_{\mathbf{α}}}$ el conjunto de todas las permutaciones de ${\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}}})}$ , entonces llegamos a nuestra afirmación

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

∎