El remarketing dinámico (dynrem) en myTarget es una tecnología publicitaria dirigida que utiliza información sobre las acciones de los usuarios en sitios web y en aplicaciones móviles de anunciantes. Por ejemplo, en una tienda en línea, un usuario miraba las páginas de productos o los agregaba a la cesta, y myTarget usa estos eventos para mostrar anuncios de aquellos productos y servicios en los que una persona ha mostrado interés anteriormente. Hoy hablaré con más detalle sobre el mecanismo para generar recomendaciones no personales, es decir, item2item, que nos permiten diversificar y complementar la producción publicitaria.

Los clientes de dynrem myTarget son principalmente tiendas en línea, que pueden tener una o más listas de productos. Al elaborar recomendaciones, el par "tienda - lista de productos" debe considerarse como una unidad separada. Pero por simplicidad, simplemente usaremos la "tienda" a continuación. Si hablamos de la dimensión de la tarea de entrada, entonces las recomendaciones deben ser construidas para aproximadamente mil tiendas, y la cantidad de bienes puede variar de varios miles a millones.

El sistema de recomendaciones para dynrem debe cumplir los siguientes requisitos:

1. El banner contiene productos que maximizan su CTR.
2. Las recomendaciones se crean sin conexión durante un tiempo determinado.
3. La arquitectura del sistema debe ser flexible, escalable, estable y funcionar en un entorno de arranque en frío.

Tenga en cuenta que a partir del requisito de elaborar recomendaciones por un tiempo fijo y las condiciones iniciales descritas (asumiremos de manera optimista que el número de tiendas está aumentando), naturalmente surge un requisito para el uso económico de los recursos de la máquina.

La sección 2 contiene los fundamentos teóricos para construir sistemas de recomendación, las secciones 3 y 4 discuten el lado práctico del problema, y ​​la sección 5 resume el resultado general.

Conceptos basicos

Considere la tarea de construir un sistema de recomendación para una tienda y enumere los enfoques matemáticos básicos.

Descomposición de valor singular (SVD)

Un enfoque popular para construir sistemas de recomendación es el enfoque de descomposición singular (SVD). Matriz de calificación $$$R = (r_ {ui})$ representar como producto de dos matrices $$$P$ y $$$Q$ para que $$$R \ aprox. P Q ^ T$ luego califica la calificación del usuario $$$u$ para bienes $$$i$ representado como $$$\ hat {r} _ {ui} = <p_u, q_i>$ [1], donde los elementos del producto escalar son vectores de dimensión $$$k$ (parámetro principal del modelo). Esta fórmula sirve como base para otros modelos SVD. La tarea de encontrar $$$P$ y $$$Q$ Todo se reduce a la optimización de la funcionalidad:

(2.1)

$$

$$J (P, Q) = \ sum _ {(u, i)} \ mathcal {L} (r_ {ui}, \ hat {r} _ {ui}) + \ Lambda (P, Q) \ rightarrow \ min_ {P, Q},$$

donde $$$L$ - función de error (por ejemplo, RMSE como en la competencia de Netflix ), $$$Λ$ - regularización, y la suma es por pares para los que se conoce la calificación. Reescribimos la expresión (2.1) de forma explícita:

(2.2)

$$

$$J (P, Q) = \ sum _ {(u, i)} (r_ {ui} - <p_u, q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 \ rightarrow \ min_ {P, Q},$$

Aqui $$$λ1$ , $$$λ2$ - Coeficientes de regularización L2 para representaciones de usuarios $$$p_ {u}$ y bienes $$$q_ {i}$ en consecuencia El modelo básico para la competencia de Netflix fue:

(2.3)

$$

$$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u, q_i>,$$

(2.4)

$$

$$J (P, Q) = \ sum _ {(u, i)} (r_ {ui} - \ mu - b_u - b_i - <p_u, q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 + \ lambda_3 b_u ^ 2 + \ lambda_4 b_i ^ 2 \ rightarrow \ min_ {P, Q},$$

donde $$$µ$ , $$$b_ {u}$ y $$$b_ {i}$ - sesgos de calificación, usuario y producto, respectivamente. El modelo (2.3) - (2.4) se puede mejorar añadiéndole una preferencia implícita de usuario. En el ejemplo de la competencia de Netflix, la respuesta explícita es la puntuación establecida por el usuario para la película "a petición nuestra", y otra información sobre la "interacción del usuario con el producto" (ver la película, su descripción, comentarios sobre ella; es decir, la respuesta implícita no da una respuesta implícita) información directa sobre la calificación de la película, pero al mismo tiempo indica interés). La contabilidad de respuesta implícita se implementa en el modelo SVD ++:

(2.5)

$$

$$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u + \ frac {1} {\ sqrt {\ sigma_u}} \ sum_ {j \ en S (u)} y_j, \, \ , q_i>,$$

donde $$$S (u)$ - un conjunto de objetos con los que el usuario interactúa implícitamente, $$$σ_ {u} = | S (u) |, y_ {j}$ - representación de dimensión $$$k$ para un objeto de $$$S (u)$ .

Máquinas de factorización (FM)

Como se puede ver en los ejemplos con diferentes modelos SVD, un modelo difiere del otro en el conjunto de términos incluidos en la fórmula de evaluación. Además, la expansión del modelo cada vez representa una nueva tarea. Queremos que dichos cambios (por ejemplo, agregar un nuevo tipo de respuesta implícita, teniendo en cuenta los parámetros de tiempo) se implementen fácilmente sin cambiar el código de implementación del modelo. Los modelos (2.1) - (2.5) se pueden representar en una forma universal conveniente utilizando la siguiente parametrización. Representamos al usuario y al producto como un conjunto de características:

(2.6)

$$

$$\ overline {x} ^ U = (x_1 ^ U, x_2 ^ U, \ dots, x_l ^ U) \ in \ mathbb {R} ^ l,$$

(2.7)

$$

$$\ overline {x} ^ I = (x_1 ^ I, x_2 ^ I, \ dots, x_m ^ I) \ in \ mathbb {R} ^ m.$$

Fig. 1: Un ejemplo de una matriz de características en el caso de CF.

Por ejemplo, en el caso del filtrado colaborativo (CF), cuando solo se utilizan datos sobre la interacción de usuarios y productos, los vectores de características se ven como un código de acceso directo (Fig. 1). Introducir vector $$$\ overline {x} = (\ overline {x} ^ U, \ overline {x} ^ I)$ , la tarea de recomendación se reduce a problemas de regresión con la variable objetivo $$$r_ {ui}$ :

1. Modelo lineal:
   (2.8)
   

   $$

   $$h_ {lin} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j$$
2. Poly2:
   (2.9)
   

   $$

   $$h_ {poly2} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} w_ {ij} x_i x_j$$
3. FM:
   (2.10)
   

   $$

   $$h_ {FM} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} x_i x_j <\ overline {v} _i, \ overline {v} _j>$$

donde $$$w_ {j}$ - parámetros del modelo, $$$v_ {i}$ Son vectores de dimensión $$$k$ representando el signo $$$i$ en espacio latente $$$l$ y $$$m$ - el número de signos del usuario y producto, respectivamente. Además de los códigos de acceso directo, las características basadas en contenido (basadas en contenido, CB) pueden servir como signos (Fig. 2), por ejemplo, descripciones vectorizadas de productos y perfiles de usuario.


Fig. 2: Un ejemplo de una matriz de características expandida.

El modelo FM introducido en [2] es una generalización para (2.1) - (2.5), (2.8), (2.10). La esencia de FM es que tiene en cuenta la interacción por pares de características que utilizan un producto escalar $$$<\ overline {v} _i, \ overline {v} _j>$ , sin usar el parámetro $$$w_ {ij}$ . La ventaja de FM sobre Poly2 es una reducción significativa en el número de parámetros: para vectores $$$v_ {i}$ necesitaremos $$$(l + m) · k$ parámetros y para $$$w_ {ij}$ será requerido $$$lm m$ parámetros En $$$l$ y $$$m$ de pedidos grandes, el primer enfoque utiliza significativamente menos parámetros.

Tenga en cuenta: si no hay un par específico en el conjunto de entrenamiento $$$(i, j)$ , entonces el término correspondiente con $$$w_ {ij}$ en Poly2 no afecta el entrenamiento del modelo, y el puntaje de calificación se forma solo en la parte lineal. Sin embargo, el enfoque (2.10) nos permite establecer relaciones a través de otras características. En otras palabras, los datos de una interacción ayudan a evaluar los parámetros de los atributos que no se incluyen en este ejemplo.

Sobre la base de FM, se implementa un denominado modelo híbrido en el que los atributos CB se agregan a los atributos CF. Le permite resolver el problema de un arranque en frío, y también tiene en cuenta las preferencias del usuario y le permite hacer recomendaciones personalizadas.

Lightfm

En la implementación popular de FM , el énfasis está en la separación entre las características del usuario y el producto. Las matrices actúan como parámetros del modelo. $$$E ^ U$ y $$$E ^ I$ Presentación de características personalizadas y de producto:

(2.11)

$$

$$E ^ U = \ begin {pmatrix} \ overline {e} _1 ^ U \\ \ vdots \\ \ overline {e} _l ^ U \ end {pmatrix}, \, \, E ^ I = \ begin {pmatrix } \ overline {e} _1 ^ I \\ \ vdots \\ \ overline {e} _m ^ I \ end {pmatrix}, \ overline {e} _i ^ U \ in \ mathbb {R} ^ k, \ overline { e} _i ^ I \ in \ mathbb {R} ^ k$$

así como las compensaciones $$$\ overline {b} ^ U, \ overline {b} ^ I \ in \ mathbb {R} ^ k$ . Uso de vistas de usuario y producto:

(2.12)

$$

$$\ overline {p} ^ U = \ overline {x} ^ U \ cdot E ^ U = \ sum_ {j = 1} ^ l x_j ^ U \ cdot \ overline {e} _j ^ U,$$

(2.13)

$$

$$\ overline {q} ^ I = \ overline {x} ^ I \ cdot E ^ I = \ sum_ {j = 1} ^ m x_j ^ I \ cdot \ overline {e} _j ^ I,$$

obtener la calificación de pareja $$$(u, i)$ :

(2.14)

$$

$$\ hat {r} _ {ui} = <\ overline {p} ^ U, \ overline {q} ^ I> + <\ overline {x} ^ U, \ overline {b} ^ U> + <\ overline {x} ^ I, \ overline {b} ^ I>. $$$

Funciones de pérdida

En nuestro caso, es necesario clasificar los productos para un usuario específico para que un producto más relevante tenga una calificación más alta que uno menos relevante. LightFM tiene varias funciones de pérdida:

1. La logística es una implementación que requiere un negativo que no se presenta explícitamente en la mayoría de las tareas.
2. BPR [3] es maximizar la diferencia en las calificaciones entre ejemplos positivos y negativos para un usuario en particular. Negativo se obtiene mediante muestreo bootstrap. La calidad funcional utilizada en el algoritmo es similar a ROC-AUC.
3. WARP [4] difiere de BPR en el método de muestreo de ejemplos negativos y la función de pérdida, que también es de clasificación, pero al mismo tiempo optimiza las principales recomendaciones para el usuario.

Implementación práctica

Para crear recomendaciones para un momento dado, se utiliza una implementación paralela en Spark. Se inicia una tarea independiente para cada tienda, cuya ejecución está controlada por luigi.

Preprocesamiento de datos

El preprocesamiento de datos se realiza mediante herramientas Spark SQL escalables automáticamente. Las características seleccionadas en el modelo final son descripciones textuales de productos y catálogos con conversiones estándar.

Lo que nos ayudó al interactuar con Spark:

1. Particionamiento de datos preparados (matriz de interacciones de usuario y producto, signos para ellos) por tiendas. Esto le permite ahorrar tiempo durante la fase de capacitación en la lectura de datos de HDFS. De lo contrario, cada tarea debe leer los datos en la memoria de Spark y filtrarlos por ID de tienda.
2. Guardar / recibir datos a / desde Spark se realiza en partes. Esto se debe al hecho de que durante cualquiera de estas acciones los datos se cargan en la memoria JVM. ¿Por qué no solo aumentar la memoria para la JVM? En primer lugar, la memoria disponible para entrenar el modelo disminuye y, en segundo lugar, no es necesario almacenar nada en la JVM; en este caso, actúa como un almacenamiento temporal.

Entrenamiento modelo

El modelo para cada tienda está entrenado en su propio contenedor Spark, para que pueda ejecutar simultáneamente un número arbitrario de tareas para tiendas, limitado solo por los recursos del clúster.

LightFM carece de mecanismos de parada temprana, por lo tanto, gastamos recursos adicionales en iteraciones adicionales de capacitación cuando no hay un aumento en la métrica objetivo. Elegimos AUC como métrica, cuya relación con CTR se confirma experimentalmente.

Denotar:

$$$S$ - todas las interacciones conocidas entre usuarios y productos, es decir, pares $$$(u, i)$ ,
$$$I$ - muchos de todos los bienes $$$i$ ,
$$$U$ - muchos de todos los usuarios $$$u$ .
Para un usuario específico $$$u$ también presentar $$$I_ {u} = {i ∈ I: (u, i) ∈ S}$ - Muchos productos con los que el usuario interactúa. El AUC se puede calcular de la siguiente manera [ref]:

(3.1)

$$

$$AUC (u) = \ frac {1} {| \ mathcal {I} _u || \ mathcal {I} \ setminus \ mathcal {I} _u |} \ sum_ {i \ in \ mathcal {I} _u} \ sum_ {j \ in \ mathcal {I} \ setminus \ mathcal {I} _u} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}),$$

(3.2)

$$

$$AUC = \ frac {1} {| \ mathcal {U} |} \ sum_ {u \ in \ mathcal {U}} AUC (u).$$

En la fórmula (3.1) necesitamos calcular la calificación para todos los pares posibles $$$(u, i)$ ( $$$u$ fijo), así como comparar clasificaciones para artículos de $$$\ mathcal {I} _u$ con valoraciones de $$$\ mathcal {I} \ setminus \ mathcal {I} _u$ . Dado que el usuario interactúa con la escasa parte del surtido, la complejidad del cálculo es $$$O (| \ mathcal {U} || \ mathcal {I} |)$ . Al mismo tiempo, una era de entrenamiento FM nos cuesta $$$O (| \ mathcal {U} |)$ .

Por lo tanto, modificamos el cálculo de AUC. Primero, debes dividir la muestra en un entrenamiento $$$\ mathcal {S} ^ {train} \ subset \ mathcal {S}$ y validación $$$\ mathcal {S} ^ {val} \ subset \ mathcal {S}$ y $$$\ mathcal {S} ^ {val} = \ mathcal {S} \ setminus \ mathcal {S} ^ {train}$ . A continuación, usamos el muestreo para crear muchos usuarios para la validación. $$$\ mathcal {U} ^ {val} \ subset \ {u \ in \ mathcal {U}: (u, i) \ in \ mathcal {S} ^ {val} \}$ . Para el usuario $$$u$ de $$$\ mathcal {U} ^ {val}$ los elementos de la clase positiva se considerarán muchos $$$\ mathcal {I} _u ^ {+} = \ {i \ in \ mathcal {I}: (u, i) \ in \ mathcal {S} ^ {val} \}$ similar $$$\ mathcal {I} _u$ . Como elementos de una clase negativa, tomamos una submuestra $$$\ mathcal {I} _u ^ {-} \ subset \ mathcal {I}$ para que no haya elementos de $$$\ mathcal {I} _u$ . El tamaño de la submuestra puede tomarse proporcionalmente al tamaño. $$$\ mathcal {I} _u ^ {+}$ eso es $$$| \ mathcal {I} _u ^ {-} | = c \ cdot | \ mathcal {I} _u ^ {+} |$ . Entonces las fórmulas (3.1), (3.2) para calcular AUC cambiarán:

(3.3)

$$

$$AUC (u) = \ frac {1} {| \ mathcal {I} _u ^ {+} || \ mathcal {I} _u ^ {-} |} \ sum_ {i \ in \ mathcal {I} _u ^ {+}} \ sum_ {j \ in \ mathcal {I} _u ^ {-}} \ delta (\ sombrero {r} _ {ui}> \ hat {r} _ {uj}),$$

(3.4)

$$

$$AUC = \ frac {1} {| \ mathcal {U} ^ {val} |} \ sum_ {u \ in \ mathcal {U} ^ {val}} AUC (u).$$

Como resultado, obtenemos un tiempo constante para calcular AUC, ya que solo tomamos una parte fija de los usuarios y los conjuntos $$$\ mathcal {I} _u ^ {+}$ y $$$\ mathcal {I} _u ^ {-}$ Tiene un tamaño pequeño. El proceso de aprendizaje para la tienda se detiene después de que el AUC (3.4) deja de mejorar.

Buscar objetos similares

Como parte de la tarea item2item, debe seleccionar para cada elemento $$$n$ (o productos lo más similares posible) a aquellos que maximizan la posibilidad de hacer clic en el banner. Nuestra suposición: los candidatos para el banner deben considerarse desde arriba $$$k$ más cercano en incrustaciones espaciales. Probamos los siguientes métodos para calcular "vecinos más cercanos": Scala + Spark, ANNOY, SCANNs, HNSW.


Para Scala + Spark para una tienda con 500 mil objetos, calcular una métrica de coseno honesta tomó 15 minutos y una cantidad significativa de recursos de clúster, en relación con lo cual probamos métodos aproximados para encontrar vecinos más cercanos. Al estudiar el método SCANN, los siguientes parámetros variaron: bucketLimit , shouldSampleBuckets , NumHashes y setSignatureLength , pero los resultados resultaron insatisfactorios en comparación con otros métodos (objetos muy diferentes cayeron en el cubo). Los algoritmos ANNOY y HNSW mostraron resultados comparables a un coseno honesto, pero funcionaron mucho más rápido.

	200k productos		500 mil bienes		2,2 millones de productos
Algoritmo	Molestar	Hnsw	Molestar	Hnsw	Molestar	Hnsw
tiempo de construcción índice (seg)	59,45	8.64	258,02	25,44	1190.81	90,45
tiempo total (seg)	141,23	14/01	527,76	43,38	2081.57	150,92

Debido al hecho de que HNSW funcionó más rápido que todos los algoritmos, decidimos detenerlo.
También buscamos los vecinos más cercanos en el contenedor de Spark y escribimos el resultado en Hive con la partición adecuada.

Conclusión

Recordemos: utilizamos WARP para entrenar el modelo, AUC para la parada temprana, y la evaluación de calidad final se lleva a cabo utilizando la prueba A / B en tráfico en vivo.

Creemos que en este lugar, al organizar el experimento y seleccionar la composición óptima del banner, los datos terminan y comienza la ciencia. Aquí aprendemos a determinar si tiene sentido mostrar recomendaciones para productos para los que funcionó la reorientación; exactamente cuántas recomendaciones mostrar; cuántos productos viste, etc. Hablaremos de esto en los siguientes artículos.

Las mejoras adicionales al algoritmo, la búsqueda de incrustaciones universales que permitirán colocar los productos de todas las tiendas en un solo espacio, se llevan a cabo dentro del marco del paradigma descrito al comienzo del artículo.

Gracias por su atencion!

Literatura

[1] Ricci F., Rokach L., Shapira B. Introducción al manual de sistemas de recomendación
// Manual de sistemas de recomendación. - Springer, Boston, MA, 2011 .-- S. 147160.

[2] Rendle S. Máquinas de factorización // 2010 IEEE International Conference on Data Mining. - IEEE, 2010 .-- S. 995-1000.

[3] Rendle S. y col. BPR: clasificación personalizada bayesiana a partir de comentarios implícitos
// Actas de la vigésima quinta conferencia sobre incertidumbre en inteligencia artificial.
- AUAI Press, 2009 .-- S. 452-461.

[4] Weston J., Bengio S., Usunier N. Wsabie: Ampliación a la anotación de imágenes de vocabulario grande // Vigésima Segunda Conferencia Internacional Conjunta sobre Inteligencia Artificial. - 2011.