Práctica y pensamiento del algoritmo de diversidad en 58 tribus

Después de aclarar el tema "Optimización de la diversidad individual de los sistemas de recomendación", este artículo explica claramente los detalles de optimización en la capa de recuperación, la capa de reglas y la capa de diversidad de la arquitectura general. En los algoritmos MMR y DPP, hay tanto principio como práctica. Finalmente, la comparación de efectos se muestra mediante gráficos y el diseño de la distancia objetivo se lleva a cabo de acuerdo con las características del propio negocio.

Antecedentes

En los sistemas de recomendación, además de la relevancia, la diversidad también es uno de los indicadores importantes para medir la calidad del sistema. Sin embargo, a menudo existe cierta tensión entre diversidad y relevancia. Desde la perspectiva de los indicadores comerciales, analiza el método de pensamiento sobre cómo sopesar la diversidad y la correlación, presenta soluciones prácticas para algoritmos de diversidad y, en última instancia, logra el propósito de mejorar los indicadores comerciales a través de medios de diversidad.

1. La importancia y la dificultad de los algoritmos de diversidad

En los sistemas de recomendación, la precisión siempre ha sido el indicador más importante para medir la calidad del sistema. La mayor parte del trabajo se centra en cómo mejorar. precisión. Sin embargo, la calidad de los resultados de las recomendaciones se mide mediante múltiples dimensiones. Cada vez más investigaciones muestran que las recomendaciones basadas en la precisión no pueden mejorar la experiencia y la satisfacción del usuario, pero pueden promover fácilmente la aparición de capullos de información. Por lo tanto, cómo equilibrar y optimizar la precisión y la diversidad, mejorando así los indicadores generales de datos del negocio, se ha convertido en otra dirección de optimización del sistema de recomendación.

En la práctica, hemos resumido varias dificultades en los algoritmos de diversidad:

1) El objetivo de optimización del modelo es vago.

Como todos sabemos, diversos comportamientos de los usuarios (clics, conversiones, estancias, acciones, etc.) se pueden utilizar como objetivos para lograr una optimización precisa. Podemos recopilar claramente el comportamiento del usuario como la etiqueta objetivo del modelo para diseñar y optimizar el modelo. Debido a que la diversidad en sí misma es una estadística establecida, es difícil encontrar el comportamiento directo del usuario como objetivo para la optimización del modelo.

2) Conflicto entre indicadores de negocio e indicadores de diversidad

Los indicadores de enfoque empresarial (tasa de conversión, tiempo de permanencia, etc.) y los indicadores de diversidad no son simplemente positivos o negativos. Si la diversidad se hace simplemente para mejorar el índice de diversidad, los resultados finales se desviarán de los objetivos comerciales y reducirán la calidad de las recomendaciones.

En resumen, en la práctica de diversidad del sistema de recomendación de 58 Tribe, hemos descartado el simple uso de indicadores de diversidad como método para evaluar algoritmos. Combinado con las características comerciales de la tribu, el objetivo que nos fijamos es utilizar la diversidad como un medio para mejorar los indicadores comerciales, evaluar integralmente el efecto del algoritmo a través de múltiples indicadores comerciales e indicadores de diversidad y, en última instancia, lograr el objetivo de mejorar los dos conjuntamente. indicadores, mejorando así la experiencia del Usuario.

Práctica del algoritmo de diversidad de 58 tribus

En la investigación del algoritmo de diversidad, la diversidad generalmente se divide en dos tipos:

Basado en la diversidad de usuarios individuales, Su objetivo es evitar recomendar productos similares a un solo usuario, mejorando así la experiencia del usuario y aumentando su satisfacción;

Basado en la diversidad de todos los usuarios, su objetivo es optimizar el efecto de distribución de los productos de cola larga;

Debido a que nuestro objetivo principal en esta etapa es la experiencia personal del usuario, elegimos la diversidad de usuarios individuales como la dirección práctica.

1. Diagrama de arquitectura del sistema recomendado

Diagrama de estructura jerárquica en línea del sistema de recomendación

Para garantizar la diversidad de datos recomendados, lo realizamos en tres Optimización de lugares:

1) Capa de recuperación: proporcione diversos conjuntos de candidatos de fuentes de datos y garantice la diversidad de fuentes de datos mejorando la cobertura de temas, categorías y autores en el grupo de candidatos aproximado;

2) Capa de reglas: en el caso de una pequeña pérdida de correlación, al mejorar la cobertura de temas y categorías en el grupo de candidatos de clasificación fina, se garantiza la diversidad de datos que ingresan al grupo de clasificación fina;

3) Capa de diversidad: unificar y diversificar los datos para garantizar la diversificación de la producción de datos.

Los datos determinan el límite superior del efecto y el algoritmo sólo se acerca a este límite superior. En la capa de diversidad, intente garantizar solo la diversidad de datos después de una clasificación fina. Dado que los resultados se ven afectados por la diversidad de datos del grupo de candidatos de fila refinado, sería mejor si la diversidad del conjunto de candidatos pudiera mantenerse en las fuentes de datos de la capa de recuperación.

2. Diversificación de las fuentes de datos

2.1 Implementación de la diversificación de la capa de recuperación

Diagrama de arquitectura de la capa de recuperación

En la fase de recuperación, Se adoptó un retiro multicanal.

Para garantizar la diversidad de datos, enriquezca la fuente de datos agregando algunas estrategias de recuperación diferentes, como:

Utilice el algoritmo de diversidad para obtener temas, categorías y autores diversos y personalizados para el usuario para recordar, asegurando la recuperación. tiene en cuenta tanto la diversidad como la relevancia;

Aumentar la novedad y la diversidad de los datos a través de algunos retiros de cola larga, temporales y sorpresa;

A través de algunos retiros colaborativos basados ​​en relaciones y atributos La ramificación mejora la diversidad de datos.

Al aumentar la diversidad y el recuerdo de novedades, la cobertura de datos en el grupo aproximado de candidatos aumenta en aproximadamente un 120 % y la cobertura basada en categorías aumenta en aproximadamente un 100 %.

2.2 Lograr la diversificación de la capa de reglas

Diagrama de arquitectura de la capa de reglas

Los datos que recomendamos son varias entidades heterogéneas, por lo que antes de ingresar los detalles (Antes de la regla capa), los tipos están agrupados. Cada tipo debe pasar por una etapa de interceptación de datos desde la clasificación aproximada hasta la clasificación fina. El principal indicador de interceptación es generalmente la puntuación relevante de la clasificación aproximada. Para evitar que el truncamiento destruya la optimización de la diversidad de la fuente de datos por parte de la capa de recuperación, primero dividimos los resultados de dicha clasificación aproximada en depósitos por categoría y luego controlamos la diversidad. Finalmente, ajuste las proporciones de varios tipos, complemente los datos y realice algunas evaluaciones necesarias. Mejore la diversidad de datos de filas detallados cuando la correlación es baja.

Dado que el algoritmo de diversidad de la capa de reglas está agrupado por tipo, no se ve afectado por la disposición mixta de varios tipos heterogéneos de entidades y es adecuado para varios algoritmos de diversidad.

Después de agregar la intervención del algoritmo de diversidad a la capa de reglas, la cobertura de datos en el grupo de candidatos de clasificación fina aumentó aproximadamente un 80 % según los temas y aproximadamente un 70 % según las categorías. ?

El efecto de transformación de ctr en línea y uvctr después de agregar diversidad a la capa regular se muestra en la siguiente figura:

Comparación de los efectos del algoritmo de capa regular

Se puede ver en la figura anterior que, en términos de diferencias, cada algoritmo no es muy grande y su rendimiento es ligeramente mejor. En general, el algoritmo funciona ligeramente mejor. La capa de reglas utiliza principalmente algoritmos de diversidad para reemplazar las reglas heurísticas anteriores para automatizar la diversidad de fuentes de datos.

3. Capas diversificadas según el método de reordenamiento

Para el ajuste de parámetros del algoritmo, nos referimos principalmente a tres indicadores comerciales:

Pvctr representa la tasa de clics pv; tasa de clics uv; Avgpv representa el número de visitas a la exposición per cápita.

Para escenarios donde se aplican algoritmos de diversidad, se utilizan algoritmos de diversidad comunes en un solo tipo de capa de reglas, como binomales, EE, DPP, XQUAD, PM2, Bayes y MMR, pero los algoritmos comunes no. adecuado para varios tipos heterogéneos de entidades en la capa de diversidad, debido a que 58 tribus son diversas y heterogéneas, es difícil utilizar un método de generación de un solo vector para medir elementos heterogéneos en un espacio denso y diferentes tipos de entidades El grado de superposición de intereses Las distribuciones no son muy altas.

3.1 Diagrama de arquitectura de diversidad

Diagrama de arquitectura de capa de diversidad

Debido al espacio limitado, la importancia de la cartera de negocios, la puntualidad y otras razones, lo siguiente se centra en MMR y Aplicación del DPP en la práctica de la ingeniería.

¿3,2MMR? Principio

El nombre completo del principio MMR es MaximalMarginal Relevance, que es un algoritmo de clasificación codicioso que reduce la redundancia y garantiza la relevancia. En el escenario de recomendación, podemos recomendar productos relevantes a los usuarios y al mismo tiempo garantizar la diversidad de resultados de recomendación. Fórmula:

s es un conjunto ordenado de documentos seleccionados, generalmente el resultado de una clasificación relacionada;

r representa el siguiente documento candidato

Di representa el siguiente; Un documento candidato;

Dj representa el documento en s;

Función Sim: es una función de medición de similitud, como similitud;

Representa el documento candidato y Consultar la correlación entre documentos;

Indica la similitud máxima entre el documento y los documentos existentes;

? El coeficiente de ponderación ajusta la relevancia y diversidad de los resultados recomendados.

Como algoritmo codicioso, también calcula el valor máximo en la fórmula cada vez, lo coloca en el conjunto de resultados ordenados, mientras elimina los elementos seleccionados del conjunto candidato, luego actualiza los parámetros y luego continúa. en la siguiente ronda Seleccione hasta que los datos del conjunto de resultados satisfagan sus necesidades o no haya datos para seleccionar.

Proceso de implementación

Diagrama de flujo del algoritmo Mmmr

Resultados experimentales

Cuadro comparativo de efectos de parámetros MMR

Para unificación Para el flujo del algoritmo, transpusimos la suma en la fórmula del artículo original. Para garantizar que se puedan comparar varios indicadores en la misma imagen, la suma de la imagen se amplía y se reduce hasta cierto punto. Como se puede ver en la figura, el parámetro de diversidad se ajusta gradualmente y disminuye gradualmente, alcanzando el punto más alto en ese momento, porque cuanto más pequeño es, más relevantes tienden a ser los resultados. Y el número de vistas per cápita ha aumentado constantemente, lo que indica que a medida que aumenta la diversidad, algunas personas se sentirán atraídas por hacer clic y explorarán más contenido. El efecto es mejor cuando está en casa y alcanza el punto más alto cuando está en casa.

? Problemas de implementación de ingeniería

Al calcular la distancia, implementamos la distancia promedio entre el documento actual y el documento seleccionado para evitar que el uso de la distancia máxima cause una alta similitud entre documentos posteriores en los resultados de la recomendación.

La definición de la función de similitud entre artículos puede basarse en la similitud mencionada en el artículo. Pero esto requiere que haya un vector de elementos unificado entre las listas de candidatos para garantizar que el vector sea de cualquiera a cualquiera. Debido a que existen muchos tipos de resultados de recomendación y son heterogéneos, la similitud no se explica bien en este caso. Nuestro enfoque es utilizar una distancia personalizada para combinar servicios, que se presentará en detalle a continuación.

3.3 Principios de DPP

El nombre completo del proceso de puntos determinantes es la distribución de probabilidad definida en el conjunto de potencias de conjuntos de puntos discretos. es un subconjunto del muestreo aleatorio, para cualquiera, existe

El significado de las variables en la fórmula:

y? Un subconjunto aleatorio obtenido mediante muestreo aleatorio utilizando un proceso de punto determinante;

es cualquier subconjunto de y;

representa la probabilidad de acertar todos los elementos de la muestra;

? k es una matriz cuadrada simétrica real, también llamada matriz kernel, ¿cada elemento? Puede considerarse como la similitud entre los primeros elementos del conjunto, que es inversamente proporcional a la probabilidad de muestreo. Puede verse como la correlación entre el elemento y el usuario, que es proporcional a la probabilidad de muestreo.

¿Ka? es la fórmula principal de k, y el orden es el número de elementos.

La siguiente figura puede describir vívidamente el proceso del punto de decisión:

Diagrama esquemático del proceso del punto de decisión

Indica la probabilidad de que los proyectos I y J se muestreen en al mismo tiempo. De la fórmula se puede ver que cuanto más elementos similares, menor será la probabilidad de que se muestreen al mismo tiempo.

La idea de este algoritmo es tratar el problema de reordenamiento como un problema de selección de subconjuntos. El objetivo es seleccionar subconjuntos diversos pero de alta calidad del conjunto de datos original y mantener el equilibrio entre la alta calidad. y diversidad a través del equilibrio DPP. DPP es un modelo de probabilidad de alto rendimiento que simplifica los cálculos de probabilidad complejos mediante determinantes. DPP también puede entenderse como un proceso de muestreo. La probabilidad de que dos elementos se extraigan como un subconjunto está relacionada con la probabilidad de que se extraiga un solo elemento y la similitud entre los dos elementos.

Plan de implementación del DDP

? El primero es el esquema de reordenamiento basado en ventanas propuesto por Google. El esquema de construcción de la matriz del núcleo mencionado en el artículo es:

Dij representa la distancia entre los elementos I y j, que es una variable libre. Cuando a = 1, es equivalente al kernel RBF estándar. Cuando...

Las diagonales fuera de la matriz se reducen, lo que básicamente corresponde a diversificar todos los elementos. Cuando a & gt1, la diagonal de la matriz aumenta, lo que tiene el efecto opuesto de hacer que todos los elementos sean más similares.

A medida que el conjunto crece, la probabilidad de conjuntos pequeños aumenta y la probabilidad de conjuntos grandes disminuye. Dado que a > está en 1, L puede ser semidefinido no positivo. Para garantizar que la matriz del núcleo sea semidefinida positiva en todo momento, este artículo mapea la matriz del núcleo, calcula la descomposición propia de L y reemplaza cualquier valor propio negativo con 0.

Al mismo tiempo, se propone un método de optimización del modelo de aprendizaje profundo basado en una matriz profunda del núcleo de Gram para reducir la complejidad de los parámetros de búsqueda de la cuadrícula.

La segunda solución es proporcionada por la Universidad de Pensilvania, que es una solución general para la inferencia máxima a posteriori de DDP. Sin embargo, cada vez que se obtiene un elemento, se debe reconstruir la matriz del núcleo mediante cálculo y la misma. El retraso no es optimista.

La tercera es la solución de inferencia posterior máxima propuesta por Tribe Tiger Video. Para resolver el problema de la alta complejidad temporal de los mapas tradicionales, se propone un algoritmo codicioso mejorado para una solución rápida:

¿Confiar en la construcción?

La función submodular mapeada se transforma en un problema de maximización de función submodular. Y se utiliza un algoritmo codicioso para resolver el problema NP-difícil causado por la maximización de la función submodular.

Cada vez que se selecciona un producto y se agrega al conjunto de resultados Yg, Yg se inicializa en un conjunto vacío hasta que se cumpla la condición. El producto debe satisfacer la siguiente ecuación:

Debido al cálculo del determinante La complejidad del proceso de derivación, consulte el artículo original):

Hemos implementado tres soluciones. La segunda solución tiene un gran retraso y no se puede aplicar en línea. El modo simple que implementamos en la primera solución es calcular directamente el determinante, que tiene un retraso mayor que la tercera solución. La opción 3 se puede reparar sin la matriz del núcleo y el resultado de la clasificación será menor que el volumen de datos esperado. En aplicaciones prácticas, combinadas con los requisitos de volumen de datos y eficiencia, finalmente elegimos la tercera solución de implementación propuesta por Hulu.

Proceso de implementación de DPP

Diagrama de flujo del algoritmo DPP

Resultados experimentales

Representaciones correspondientes a cambios en los parámetros de DPP

Para garantizar que se comparen varios indicadores entre sí en la misma imagen, tanto pvctr como avgpv se acercan y alejan hasta cierto punto. Como se puede ver en la figura anterior, al ajustar gradualmente los parámetros de diversidad, pvctr se vuelve cada vez más grande, alcanzando el máximo alrededor de 0,7. Uvtr y vistas per cápita aumentan constantemente, lo que indica que a medida que aumenta la diversidad, las personas que no hacen clic se sentirán atraídas a hacer clic y verán más contenido. Y Uvtr alcanza su máximo en 0,7, y 0,7 tiene el mejor efecto. El último valor del parámetro de cada curva de DDP es muy bajo porque en 0,999, el valor de A se vuelve muy grande al construir la matriz kernel. Después del cambio exponencial, muchas matrices del núcleo tienen valores máximos y la matriz no satisface el rango. Solo se devuelve una pequeña cantidad de datos, lo cual es una situación anormal y todos los indicadores están disminuyendo. Esto también es algo que se debe evitar durante la depuración del algoritmo.

Problemas de implementación de ingeniería

En términos de implementación, utilizamos principalmente EJML, una biblioteca de operación matricial Java eficiente de código abierto, que es una biblioteca relativamente eficiente en los intentos actuales.

En implementación de ingeniería, consulte principalmente los usos mencionados en el texto.

exp(αr_u)

En lugar de Ru, ajustando la diversidad y la correlación,

α=θ/((2(1-θ)) )

La garantía de certeza semipositiva mencionada en el artículo puede modificarse.

S_ij=(1+?f_i, f_j?)/2

En nuestra aplicación, el impacto no es grande, principalmente porque nuestra matriz de similitud está definida por el usuario.

El principal punto de optimización de DPP es la eficiencia. Adoptamos la solución de optimización de Huhu Video sin atravesar el determinante, y el retraso promedio de todo el proceso de reordenamiento de 100 elementos es de solo 4 ms.

Para la construcción de la matriz central, debido a que necesitamos una distancia definida por el usuario que sea más interpretable y pueda integrarse estrechamente con el negocio, la matriz de similitud y la matriz central también están definidas por el usuario.

Ordena toda la lista por lotes por ventana. Según la naturaleza de la función submodular, los conjuntos de datos pequeños son más exclusivos y tienen mejores efectos de ventana que los conjuntos de datos grandes.

Para el ajuste de parámetros DPP, primero corrija el parámetro de distancia definido por el usuario para encontrar uno adecuado, luego corrija y ajuste el parámetro de distancia cíclicamente y optimice los parámetros mediante la búsqueda de cuadrícula.

? Dado que la matriz del núcleo no está satisfecha con la clasificación, la cantidad de datos devueltos puede ser menor que la cantidad de datos esperada, que se puede utilizar normalmente sin mucho impacto en el negocio. Si existen requisitos estrictos sobre la cantidad de datos devueltos, debemos considerar modificar la matriz del núcleo. Puede consultar el método de modificación de la matriz del núcleo propuesto por Google, que tendrá un ligero impacto en el retraso, y el retraso probablemente se duplicará.

3.4 Cuadro comparativo de los efectos del algoritmo de la capa de diferencia

Comparación del algoritmo original, MMR y DPP

La capa de diversidad considera principalmente la estabilidad y la puntualidad. Nuestro tráfico principal se realiza en dos algoritmos de diversidad implícitos, MMR y DDP, mientras que nuestro algoritmo original está controlado por reglas heurísticas. Al comparar los algoritmos bajo parámetros óptimos, se encuentra que el efecto general de DDP es mejor que el de MMR, que mejora enormemente en comparación con el algoritmo original. La siguiente tabla muestra los cambios en los dos algoritmos en comparación con el algoritmo original.

Indicador\Registro de Algoritmo

Procesador de Datos Digital

pvctr+3.4%+5.8%

vvctr

+5,4%+7,9%

promedio

+4,2%+6,0%

? Cambiar gráfico de indicadores de negocio para cada algoritmo

Distancia personalizada

Para explicar mejor e integrar más estrechamente el negocio, utilizamos distancias definidas por el usuario. Los beneficios de la distancia definida por el usuario son los siguientes:

? Fuerte interpretabilidad, la distancia personalizada está sesgada hacia el propósito que las personas pueden entender, lo que hace que la distancia sea más interpretable;

Y la integración empresarial es más cercana, la distancia personalizada utiliza información relacionada con el negocio para integrar estrechamente el negocio;

p>

Es universal y se puede utilizar entre diferentes entidades heterogéneas, lo que no es posible con otras distancias.

Las distancias personalizadas que practicamos son las siguientes:

1. Distancia Jacquard/distancia Hamming

Esta distancia personalizada se calcula mediante el cuadrado de distancia Hamming-Jakad Implementado. mediante el método de aproximación de pavimentación.

Distancia personalizada - Distancia Jacquard/Hamming

Consiste en combinar servicios para construir el vector de Hamming, primero calcular la distancia de Hamming y luego normalizarla mediante similitud jacobiana.

2.? Distancia personalizada - distancia del modelo de árbol

La distancia del modelo de árbol definido por el usuario se logra mediante una atenuación jerárquica similar a un árbol y una combinación de negocios de arriba hacia abajo.

Modelo de árbol de distancias personalizado

Los nodos de hoja del árbol son los valores dispersos de distancia.

Hemos probado los tres métodos anteriores para personalizar la distancia. Desde la perspectiva de la interpretabilidad, la combinación de negocios y los resultados experimentales en línea, el modelo de árbol es actualmente el más adecuado.

Resumen y perspectivas

Hay muchos aspectos para evaluar la diversidad de sistemas de recomendación. Este artículo no solo utiliza el índice de diversidad para medir la calidad del algoritmo, sino que también considera de manera integral los resultados de diversidad basados ​​​​en indicadores comerciales, sopesa los indicadores de diversidad y preocupaciones comerciales y, en última instancia, logra el propósito de mejorar los indicadores comerciales a través de algoritmos de diversidad. En términos de implementación de ingeniería, este artículo presenta el intento del algoritmo de lograr diversidad en términos de recuperación, reglas y reordenamiento, especialmente en la etapa de reordenamiento más importante. Con base en los algoritmos MMR y DDP, se optimiza la eficiencia del cálculo y se personaliza la distancia de acuerdo con las características de los datos comerciales para satisfacer las necesidades comerciales de medir la similitud de proyectos desde múltiples dimensiones.

Actualmente, en términos de efectividad en la literatura, los algoritmos de diversidad de aprendizaje son más efectivos que los algoritmos de no aprendizaje, y lo explícito es más efectivo que lo implícito. Sin embargo, la relación entre entidades heterogéneas de múltiples categorías no es tan intuitiva. Lo intentaremos en función de las características comerciales en el futuro. Además, los algoritmos de diversidad basados ​​en el aprendizaje por refuerzo también son una dirección de investigación sobre la diversidad, y actualmente lo estamos intentando nuevamente.

Referencias:

1. C.-N Ziegler, S.M. Mejore las listas de recomendaciones mediante la diversificación de temas. WWW2005

2.? J. Carbonell y J. Goldstein. Vuelva a clasificar documentos y genere resúmenes utilizando métodos de reclasificación basados ​​en la diversidad. SIGIR 1998

3.? Jennifer Gillenwater Alex Kulesa Ben Taska. Inferencia de mapeo óptima aproximada para determinar procesos puntuales. ? ¿Pezones? 2012

4. Mark William, Ajit Kumar Ramanathan, Alexander Bonomo, Sagar Jain, Ed H. Chi, Jennifer Gillen Watt. Recomendaciones prácticas de diversidad en YouTube sobre el proceso del punto decisivo. CIKM'18 2018

5.? Chen Laming, Zhou Hanning. Inferencia de mapeo rápida y codiciosa para procesos de puntos de decisión para mejorar la diversidad de recomendaciones. NeurIPS 2018

6. Cao Yongsheng, bloguero de CSDN. Una introducción al procedimiento del vértice determinante. csdn, 2019.

Acerca del autor:

Liu Fashuai, 58 Ganji Group, ingeniero senior de algoritmos.

Zhou Jianbin, 58 Ganji Group, arquitecto de algoritmos, miembro del comité técnico.

Lectura recomendada:

Inteligente y sin cargas * * *Disfrute del proxy en la nube

La práctica de aplicación del aprendizaje profundo en 58 rankings empresariales

58 Salón de Tecnología|El número 15 ingresa al micro front-end

¡Inesperadamente! ¿Es así como es trabajar en 58.com?