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 comienza con la arquitectura general y explica claramente los detalles de optimización de la capa de recuperación, la capa de reglas y la capa de diversidad. En las partes de los algoritmos MMR y DPP, se analizan tanto los principios como las prácticas. Finalmente, se muestra la comparación de efectos con imágenes y textos, y se realiza un diseño de distancia objetivo en función de sus propias características comerciales.

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 existen algunas contradicciones entre diversidad y correlación. Este artículo explora las ideas y métodos sobre cómo sopesar la diversidad y la correlación desde la perspectiva de los indicadores comerciales, presenta el plan de implementación práctica de los algoritmos de diversidad y, en última instancia, logra el objetivo de mejorar los negocios. a través de la diversidad El propósito del indicador.

1. La importancia y 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, y ​​la mayor parte del trabajo se dedica a estudiar cómo mejorar la precisión. Sin embargo, la calidad de los resultados de las recomendaciones se mide mediante múltiples dimensiones. Cada vez más estudios han demostrado que las recomendaciones que se basan únicamente en la precisión ya no pueden mejorar la experiencia y la satisfacción del usuario, pero pueden promover fácilmente la formación de capullos de información. Por lo tanto, cómo compensar y optimizar conjuntamente entre precisión y diversidad para mejorar los indicadores de datos generales del negocio se ha convertido en otra dirección de optimización del sistema de recomendación actual.

En la práctica, hemos resumido varias dificultades al implementar algoritmos de diversidad:

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

Como todos sabemos, varios Los comportamientos del usuario (hacer clic, convertir, permanecer, compartir, etc.) se pueden utilizar como objetivos de optimización de precisión. Podemos recopilar claramente el comportamiento del usuario como la etiqueta objetivo del modelo para llevar a cabo el diseño y la optimización del modelo. Dado 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 negocio (tasa de conversión, tiempo de permanencia, etc.) y los indicadores de diversidad no son una simple relación positiva o negativa. Si realiza un trabajo de diversidad solo para mejorar las métricas de diversidad, esto hará que el resultado final se desvíe de los objetivos comerciales y reduzca la calidad de las recomendaciones.

En resumen, en la práctica de diversidad del sistema de recomendación de 58 Tribe, excluimos la práctica de simplemente usar indicadores de diversidad para evaluar la calidad del algoritmo. Combinado con las características comerciales de la tribu, establecemos el siguiente objetivo: utilizar la diversidad como un medio para mejorar los indicadores comerciales, evaluar integralmente la efectividad del algoritmo a través de múltiples indicadores comerciales e indicadores de diversidad, y finalmente lograr dos indicadores ****. la misma mejora, mejorando así el propósito de la experiencia del usuario.

Práctica del algoritmo de diversidad de 58 tribus

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

Diversidad basada en un solo género de usuario, con el objetivo de evitar recomendar artículos similares a un solo usuario, mejorando así la experiencia y la satisfacción del usuario;

Basado en la diversidad de todos los usuarios, con el objetivo de optimizar la distribución de artículos en la cola larga

Dado que nuestro objetivo principal en esta etapa es apuntar a la experiencia de un solo usuario, hemos elegido la diversidad basada en un solo usuario como dirección práctica.

1. Diagrama de arquitectura del sistema de recomendación

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

Para garantizar la diversidad de datos recomendados, lo hemos optimizado en tres lugares :

1) Capa de recuperación: proporcione datos diversos de los candidatos a partir de fuentes de datos y garantice la diversidad de las fuentes de datos mejorando la cobertura de temas, categorías y autores en el grupo de candidatos de clasificación aproximada;

2) Capa de reglas: garantice la diversidad de los datos que ingresan a la clasificación fina mejorando la cobertura de temas y categorías en el grupo de candidatos de clasificación fina, con poca pérdida de relevancia;

3) Capa de diversidad sexual: realizar un procesamiento de diversidad unificado en los datos para garantizar la diversidad de la salida de datos.

Los datos determinan el límite superior del efecto y el algoritmo solo se acerca a este límite superior. En la capa de diversidad, simplemente intente garantizar la diversidad de los datos después de la clasificación fina tanto como sea posible, porque el efecto se ve afectado por la diversidad de datos en el grupo de candidatos de clasificación fina, por lo que si la diversidad del candidato establecido en el retiro La fuente de datos de la capa se puede mantener y el efecto será mejor.

2. Diversidad de fuentes de datos

2.1 Implementación de la diversidad de capas de recuperación

Diagrama de arquitectura de capas de recuperación

En la fase de recuperación, utilizamos recuperación multidireccional. Para garantizar la diversidad de datos, enriquecemos la fuente de datos agregando algunas estrategias de recuperación de diversidad, tales como:

A través del algoritmo de diversidad, obtenemos temas, categorías y autores diversos y personalizados para el usuario para recordar. , Para garantizar que se tengan en cuenta la diversidad y la relevancia al recordar;

Aumentar la novedad y diversidad de los datos dividiendo algunos retiros de cola larga, retiros de tiempo y retiros sorpresa;

Aumentar la diversidad de datos a través de algún recuerdo colaborativo basado en relaciones y atributos.

Al aumentar la diversidad y el recuerdo de novedades, la cobertura de datos basada en temas en el grupo de candidatos con clasificación aproximada aumenta en aproximadamente un 120 %, y la cobertura basada en categorías aumenta en aproximadamente un 100 %.

2.2 Lograr diversidad en la capa de reglas

Diagrama de arquitectura de la capa de reglas

Los datos que recomendamos son una variedad de tipos de entidades heterogéneas, por lo que al ingresar a la clasificación fina ( Capa de reglas) Estos tipos se agruparon previamente. Desde la clasificación gruesa hasta la clasificación fina, cada tipo pasa por una etapa de interceptación de datos y el principal indicador de interceptación suele ser la puntuación de relevancia de la clasificación gruesa. Para evitar que la operación de truncamiento destruya la optimización de diversidad de la fuente de datos por parte de la capa de recuperación, al realizar el control de diversidad, primero agrupamos los resultados de clasificación aproximados de los tipos según categorías y luego realizamos el control de diversidad. Finalmente, se realiza el escalado, la suplementación de datos y algunos filtrados necesarios en los distintos tipos. La diversidad de los datos de filas refinados mejora cuando los efectos de correlación son pequeños.

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

Después de agregar la intervención del algoritmo de diversidad de capa de reglas, la cobertura de datos basada en temas en el grupo de candidatos de segmentación aumentó aproximadamente un 80 % y la cobertura de datos basada en categorías aumentó aproximadamente un 70 %.

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

Comparación del efecto del algoritmo de la capa de reglas

Como se puede ver en la figura anterior, en lo que respecta a este caso, la diferencia entre los distintos algoritmos no es grande y el rendimiento es ligeramente mejor. En este sentido, el rendimiento de cada algoritmo es ligeramente mejor. La capa de reglas reemplaza principalmente las reglas heurísticas anteriores mediante algoritmos de diversidad para realizar la automatización de la diversidad de fuentes de datos.

3. Capa de diversidad basada en el método de reordenamiento

Para el ajuste del algoritmo, nos referimos principalmente a tres indicadores comerciales:

pvctr se refiere a la tasa de clics pv se refiere a uvctr; a tasa de clics uv; avgpv se refiere al número de impresiones per cápita.

Con respecto a los escenarios de aplicación de los algoritmos de diversidad, los algoritmos de diversidad comunes, binomales, EE, DPP, XQUAD, PM2, Bayes y MMR, se utilizan en un solo tipo de capa de reglas. no es adecuado para múltiples tipos heterogéneos de entidades en la capa de diversidad porque los tipos de los 58 elementos tribales son diversos y heterogéneos, y es difícil para un único método de generación de vectores colocar los 58 elementos tribales en una base de datos densa. Los elementos heterogéneos son difíciles de colocar en una métrica espacial densa utilizando un método de generación de un solo vector, y la superposición de distribuciones de interés de diferentes tipos de entidades no es muy alta, por lo que utilizamos los algoritmos MMR y DPP basados ​​en distancias personalizadas y el algoritmo EE. no basado en la distancia.

3.1 Diagrama de arquitectura de diversificación

Diagrama de arquitectura de capa de diversificación

Debido al espacio limitado y a la importancia y oportunidad de la integración empresarial, lo siguiente se centra en MMR y DPP Aplicación de dos algoritmos en la práctica de la ingeniería.

3.2 Principio de MMR

El principio de MMR se llama "Relevancia marginal máxima", que es un algoritmo de clasificación codicioso que reduce la redundancia y garantiza la relevancia. En el escenario de recomendación, se materializa en recomendar productos relevantes a los usuarios y al mismo tiempo garantizar la diversidad de resultados recomendados.

Fórmula de cálculo:

S es un conjunto ordenado de documentos seleccionados, generalmente el resultado de la clasificación por relevancia;

R es el siguiente documento candidato

Di es el siguiente documento candidato;

Dj es el documento en S

función sim: es una función de medición de similitud, como la similitud

representa la relevancia del documento candidato; al documento de consulta;

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

Coeficiente de peso, utilizado para ajustar la relevancia y diversidad del sexo de los resultados recomendados.

Como algoritmo codicioso, también calcula el valor máximo en la fórmula cada vez y lo coloca en el conjunto de resultados ordenado. Al mismo tiempo, elimina los elementos seleccionados del conjunto candidato y luego actualiza el. parámetros y continúa en la siguiente ronda hasta que la cantidad de datos en el conjunto de resultados satisfaga sus necesidades o hasta que no haya datos disponibles.

Proceso de implementación

Diagrama de flujo del algoritmo MMR

Resultados experimentales

Cuadro comparativo del efecto de los parámetros MMR

Nuestro Para unificar el flujo del algoritmo, la implementación de ingeniería cambió las posiciones de la suma en la fórmula del artículo original. Para garantizar la comparación de varios indicadores en la misma figura, la cifra de la suma se amplió y se redujo hasta cierto punto. Alejar. Se puede ver en la figura que el parámetro de diversidad se ajusta gradualmente, se reduce gradualmente y alcanza el punto más alto en ese momento, porque cuanto más pequeño es, más sesgado está el resultado hacia la correlación. El aumento constante de las páginas vistas y de las páginas vistas per cápita sugiere que una mayor diversidad atraerá a algunas personas a hacer clic y hará que vean más contenido, logrando los mejores resultados en el punto más alto.

?Problemas de implementación de ingeniería

Al calcular la distancia, usamos la distancia promedio entre el documento actual y el documento seleccionado para evitar usar la distancia máxima, lo que conducirá a la adición de The La similitud entre documentos posteriores es demasiado alta.

La definición de la función de similitud entre elementos puede basarse en la similitud mencionada en el artículo. Sin embargo, esto requiere un vector uniforme de elementos en las listas de candidatos para garantizar que el vector sea de cualquier cosa. Dado que los resultados de las recomendaciones son de muchos tipos y heterogéneos, la interpretabilidad de la similitud no es sólida en este caso. Nuestro enfoque es utilizar una distancia personalizada integrada con el negocio, que se detalla a continuación.

3.3 Principio de DPP

El nombre completo de DPP es proceso de puntos determinantes, que es una distribución de probabilidad definida en el conjunto de potencias de conjuntos de puntos discretos. Es un subconjunto obtenido mediante muestreo aleatorio. Para cualquiera, existen

El significado de las variables en la fórmula:

Y?El proceso de punto determinante es un subconjunto aleatorio obtenido mediante muestreo aleatorio. ;

es cualquier subconjunto de Y;

representa la probabilidad de que todos los elementos sean impactados en la muestra

?k es una matriz cuadrada simétrica real de a; , También llamada matriz del núcleo, ¿cada elemento puede verse como la relevancia del elemento para el usuario y es proporcional a la probabilidad de muestreo?

Ka? es la fórmula maestra de K.

El proceso de punto de línea se puede mostrar visualmente a través de la siguiente figura:

Diagrama de proceso de punto de línea

Representa la probabilidad de que se muestreen los elementos i y j al mismo tiempo. De la fórmula se puede ver que cuanto más similares sean los elementos, menor será la probabilidad de que se extraigan 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 un subconjunto diverso pero de alta calidad del conjunto de datos original y mantener la alta calidad y diversidad. a través del DPP. DPP es un modelo probabilístico de alto rendimiento que simplifica los cálculos de probabilidad complejos mediante determinantes. DPP también se puede explicar como un proceso de muestreo en el que dibujar dos elementos como subconjuntos está relacionado con la probabilidad de que se extraiga un solo elemento y la similitud de los dos elementos.

Plan de implementación de DDP

? El primero es el plan de reordenamiento basado en ventanas propuesto por Google. El plan 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, ? es una variable libre. Cuando a = 1, es equivalente al kernel RBF estándar. Cuando se reducen las diagonales fuera de la matriz, esencialmente equivale a hacer que todos los elementos sean más diversos.

Cuando a>1, la diagonal de la matriz aumenta, lo que tiene el efecto contrario, es decir, todos los elementos se vuelven más similares.

A medida que aumenta el número de conjuntos, la probabilidad de conjuntos pequeños aumentará, mientras que la probabilidad de conjuntos grandes disminuirá. Dado que a>1 puede hacer que L no sea semipositivo, para garantizar que la matriz del núcleo calculada cada vez sea semipositiva, este artículo mapea la matriz del núcleo, calcula la descomposición propia de L y reemplaza cualquier valor propio negativo. ​con cero.

También 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 es la solución proporcionada por la Universidad de Pensilvania. Esta es una solución de inferencia máxima a posteriori de DDP generalizada, pero dado que la matriz del núcleo se reconstruye calculando cada término de adquisición, el retraso no es demasiado. optimista.

El tercero es el esquema de inferencia máxima a posteriori propuesto por Hu Hu Video. Propone un algoritmo codicioso mejorado que se puede resolver rápidamente y resuelve el problema de la alta complejidad temporal del MAP tradicional:

Construyendo ?

Resuelva el problema NP-difícil construyendo la función submodular de ? y maximizando la función submodular mediante un algoritmo codicioso.

Cada vez que se selecciona un producto para agregarlo al conjunto de resultados Yg, Yg se inicializa en un conjunto vacío Hasta que se cumplan las condiciones, el producto debe satisfacer la siguiente fórmula:

Debido a la alta complejidad del cálculo del determinante, este artículo descompone Cholesky, lo inicializa a vacío y lo obtiene mediante la transformación de varias columnas:

El autor también propone una actualización incremental y obtiene el incremental final actualice la fórmula mediante derivación (para el proceso de derivación específico, consulte el documento original):

Hemos implementado tres soluciones. La solución 2 tiene un gran retraso y no se puede aplicar a la línea. En la primera opción, implementamos un modelo simple, que consiste en calcular directamente el determinante, y el retraso es mayor que en la tercera opción. La solución 3 no repara la matriz del núcleo de filas y el resultado de la clasificación será menor que la cantidad de datos esperada. En la operación real, combinado con las necesidades de volumen de datos y eficiencia, finalmente elegimos el medicamento vendido en las tres calabazas del plan.

Proceso de implementación de DPP

Diagrama de flujo del algoritmo DPP

Resultados experimentales

Diagrama de efectos correspondiente a los cambios de parámetros de DPP

Para garantizar que se puedan comparar varios indicadores entre sí en la misma imagen, pvctr y avgpv en la imagen se ampliarán y reducirán hasta cierto punto. Como se puede ver en la figura anterior, a medida que los parámetros de diversidad se ajustan gradualmente, el pvctr se vuelve cada vez más grande, alcanzando un máximo de alrededor de 0,7, y las vistas uvctr y per cápita aumentan de manera constante, lo que indica que a medida que aumenta la diversidad, los que no hacen clic se sentirán atraídos. para hacer clic en el comportamiento Para que las personas exploren más contenido, uvctr alcanza su punto más alto en 0,7 y tiene el mejor efecto en 0,7. El último valor del parámetro de cada curva DDP es muy bajo, porque en 0,999, el valor de a se vuelve muy grande al construir la matriz kernel y luego cambia exponencialmente, lo que hace que el valor de muchas matrices kernel sea el valor máximo y el rango de la matriz no está completo, solo se devuelven unos pocos datos, que es una distribución no normal, y varios indicadores están disminuyendo. Esto también es algo que debe evitarse 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, para la implementación. Esta biblioteca actualmente está tratando de procesar bibliotecas más eficientes.

En términos de implementación de ingeniería, la principal referencia mencionada es el uso de

exp(αr_u )

en lugar de Ru, ajustando diversidad y correlación,

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

La garantía mencionada en el artículo se puede corregir asegurando una semidefinición positiva

S_ij =(1+? f_ i,f_j ? i,f_j ?) /2

El impacto no es muy grande en nuestra aplicación, principalmente porque nuestra matriz de similitud está personalizada.

El principal punto de optimización de DPP es la eficiencia. Adoptamos el plan de optimización de Hupu Video y reemplazamos el método determinante transversal con una solución incremental. En promedio, todo el proceso de reordenamiento de 100 entradas tiene una latencia de solo 4 ms.

En la construcción de la matriz del núcleo, debido a que necesitamos una distancia personalizada, que sea más interpretable y pueda integrarse más estrechamente con el negocio, la matriz de similitud y la matriz del núcleo también se personalizan.

Utiliza ventanas para ordenar la lista completa en lotes. Debido a la naturaleza de la función submodular, las ventanas son más adecuadas para conjuntos de datos pequeños que son más exclusivos que para conjuntos de datos grandes.

Para los parámetros de ajuste de DPP, primero corrija el parámetro de distancia personalizado, busque el parámetro adecuado y luego corríjalo, luego ajuste el parámetro de distancia cíclicamente y optimice el parámetro mediante la búsqueda de cuadrícula.

?Dado que la matriz del núcleo no está en el nivel completo, la cantidad de datos devueltos puede ser menor que la cantidad de datos esperada. Sin embargo, se puede utilizar normalmente si tiene poco impacto en el negocio. . Si existen requisitos estrictos sobre la cantidad de datos devueltos, debe considerar la corrección de la matriz del núcleo. Puede consultar la corrección de la matriz del núcleo similar a la propuesta por Google. Al mismo tiempo, tendrá un ligero impacto en el retraso. que es aproximadamente el doble del original.

3.4 Comparación de los efectos del algoritmo de la capa de diversidad

Comparación de los efectos del algoritmo original, MMR y DPP

La capa de diversidad considera principalmente la estabilidad y puntualidad Somos El tráfico se compone principalmente de 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, encontramos que DDP es mejor que MMR en efecto general y mejora enormemente en comparación con el algoritmo original. La siguiente tabla muestra los cambios de los dos algoritmos en comparación con el algoritmo original.

Indicador/Algoritmo MMR

DDP

pvctr+3.4%+5.8%

vvctr

+5.4 %+7.9%

avgpv

+4.2%+6.0%

¿Cuál es el gráfico de cambios de indicadores comerciales del algoritmo?

Distancia personalizada

Para que sea más interpretable y esté más estrechamente integrado con el negocio, utilizamos la distancia personalizada. Los beneficios de la distancia personalizada son los siguientes: