Resumen Técnico: Asignación Restringida de Usuario-Artículo para Campañas de Marketing en Comercio Electrónico

Definición del Problema: Auto-Targeting (Auto-Segmentación)

El artículo aborda un problema de asignación combinatoria en el comercio electrónico conocido como auto-targeting. A diferencia de los enfoques tradicionales que desacoplan la selección de artículos de la asignación de usuarios o asumen una estructura de campaña predefinida, este trabajo formaliza el problema como una tarea de optimización conjunta. El objetivo es particionar simultáneamente un conjunto de usuarios y un conjunto de artículos en $K$ campañas (grupos) disjuntas de tal manera que:

1. Cohesión: Cada campaña maximiza la afinidad total intra-grupo entre sus usuarios y artículos asignados.
2. Disjuntos: Cada usuario y artículo aparece en, como máximo, una campaña.
3. Restricciones: Cada campaña debe contener un número fijo de artículos ($I$) y un número de usuarios dentro de un rango específico ($\tau_{min} \le |U_k| \le \tau_{max}$).

La afinidad entre usuarios y artículos se deriva de un espacio de embeddings compartido (aprendido de interacciones históricas como clics o compras), donde la proximidad indica un interés mutuo. La función objetivo busca maximizar la suma de las afinidades a través de todas las campañas:
$$\max_{\{I_k, U_k\}_{k=1}^K} \sum_{k=1}^K \sum_{i \in I_k} \sum_{u \in U_k} \text{affinity}(i, u)$$

Esta formulación es computacionalmente desafiante debido al espacio de búsqueda exponencial y al acoplamiento de las restricciones, lo que hace que las soluciones exactas sean inviables para conjuntos de datos a gran escala.

Metodología

Los autores proponen tres estrategias heurísticas complementarias para resolver este problema, junto con el Recocido Simulado (Simulated Annealing - SA) como línea base:

1. Biclustering Espectral Restringido

Este enfoque adapta el biclustering espectral para identificar regiones densas en la matriz de afinidad usuario-artículo.

• Sobremuestreo (Oversampling): Inicialmente calcula $k' = \alpha k$ biclusters (donde $\alpha \ge 2$) para asegurar un conjunto diverso de candidatos.
• Poda (Pruning): Los candidatos se podan para satisfacer las restricciones de tamaño. Los artículos y usuarios se eliminan secuencialmente basándose en su afinidad promedio dentro del bicluster hasta alcanzar el tamaño máximo.
• Selección: Los candidatos restantes se clasifican por densidad (afinidad promedio), y se seleccionan los $k$ biclusters no superpuestos superiores como las campañas finales.

2. Optimización de Bandidos Multibrazo (Multi-Armed Bandit - MAB)

Este método trata las campañas como "brazos" en un marco de bandidos, equilibrando la explotación (asignar entidades a campañas de alta afinidad) y la exploración.

• Recompensas Acopladas: Las recompensas son endógenas; la afinidad de una entidad hacia una campaña depende de la composición actual de dicha campaña.
• Estrategias: Los autores implementan dos bonificaciones de exploración:
  • UCB1: Añade un límite de confianza a la puntuación de afinidad.
  • Thompson Sampling: Perturba las puntuaciones con ruido gaussiano que se reduce a medida que una campaña recibe más asignaciones.
• Mecanismo: El algoritmo alterna entre fases de asignación de usuarios y de artículos, utilizando estadísticas de ventana rodante con decaimiento exponencial para adaptarse a los cambios en la composición de las campañas.

3. Búsqueda Local Voraz (Greedy Local Search)

Esta estrategia emplea un procedimiento voraz con restricciones de capacidad seguido de un refinamiento.

• Asignación Voraz: Las entidades se asignan a las campañas basándose en la máxima mejora de la puntuación, procesadas en orden descendente de ganancia potencial.
• Intercambios de Pares (Pairwise Swaps): Un paso de búsqueda local evalúa el intercambio de entidades entre diferentes campañas para escapar de los óptimos locales. Si un intercambio mejora el objetivo manteniendo la viabilidad, se ejecuta.
• Iteración: El proceso alterna entre actualizaciones de usuarios e ítems durante un número fijo de iteraciones.

Línea Base: Recocido Simulado Secuencial

Los autores utilizan el Recocido Simulado (SA) como línea base. El problema global se descompone en $K$ subproblemas secuenciales. Para cada campaña, el SA realiza una búsqueda local estocástica (usando operaciones de añadir, eliminar y cambiar) con una probabilidad de aceptación controlada por temperatura para aproximar el bicluster óptimo.

Contribuciones Clave

1. Formalización del Auto-Targeting: El artículo define un nuevo problema de optimización conjunta que infiere tanto la estructura de la campaña como las asignaciones usuario-artículo simultáneamente, abordando una brecha donde los métodos existentes típicamente fijan uno de los lados de la asignación.
2. Adaptación Algorítmica: Los autores adaptan tres enfoques distintos (biclustering espectral restringido, búsqueda local voraz y bandidos multibrazo) para manejar las restricciones específicas de cobertura disjunta y límites de capacidad en un entorno acoplado.
3. Evaluación Exhaustiva: Los métodos se evalúan en tres fuentes de datos distintas:
   • Datos Sintéticos: Entornos controlados con estructuras de verdad fundamental conocidas.
   • Benchmarks Públicos: Conjuntos de datos de Amazon Reviews (Productos para Bebés, Instrumentos Musicales).
   • Datos Propietarios: Conjuntos de datos comerciales a gran escala (IKEA, Diseño de Interiores).

Resultados y Rendimiento

La evaluación utiliza métricas que incluyen Utilidad (afinidad total), Calidad (afinidad promedio), Lift (mejora sobre la asignación aleatoria) y el Coeficiente de Gini (distribución de la utilidad entre los usuarios).

• Calidad de la Solución: El Biclustering Espectral Restringido logra consistentemente los puntajes más altos en Lift, Calidad y equidad (coeficientes de Gini más bajos) en todos los conjuntos de datos. Es particularmente efectivo para recuperar regiones de alta afinidad coherentes, incluso cuando la estructura subyacente es ruidosa o superpuesta.
• Compromiso entre Escalabilidad y Calidad:
  • El Biclustering es altamente eficiente en conjuntos de datos más pequeños, pero se vuelve computacionalmente costoso a medida que la matriz de afinidad crece (por ejemplo, el tiempo de ejecución aumentó de 1.2 minutos en IKEA a 66.2 minutos en Diseño de Interiores).
  • Los métodos basados en Bandidos (UCB1 y Thompson Sampling) ofrecen una alternativa escalable para grandes conjuntos de datos, manteniendo un rendimiento competitivo con un tiempo de ejecución significativamente menor que los métodos voraces o SA en escalas muy grandes.
  • La Búsqueda Local Voraz es generalmente más lenta que los métodos de bandidos debido a los repetidos pasos de búsqueda local.
• Rendimiento de la Línea Base: El Recocido Simulado (SA) es sustancialmente inferior a los métodos propuestos en términos de calidad de la solución e incurre en el mayor costo computacional (a menudo requiriendo horas). Los autores atribuyen esto a la dificultad de realizar progresos significativos en espacios combinatorios de alta dimensión utilizando movimientos de una sola entidad.

Significado y Reivindicaciones

El artículo sostiene que modelar explícitamente la estructura conjunta usuario-artículo es crítico para un diseño de campaña efectivo. Los resultados sugieren que:

• La Optimización Conjunta es Superior: Desacoplar la selección de artículos de la asignación de usuarios pierde agrupaciones que solo emergen de la optimización conjunta.
• El Biclustering Captura la Intención Latente: El análisis cualitativo (por ejemplo, en el conjunto de datos de Instrumentos Musicales) muestra que el biclustering recupera campañas alineadas con la intención latente del usuario (por ejemplo, agrupando artículos de mantenimiento de saxofón) en lugar de taxonomías superficiales.
• Robustez al Ruido: El biclustering es robusto ante el aumento de la varianza y el ruido de los clusters, superando a los métodos que dependen de señales de entidades individuales cuando la señal de afinidad está concentrada globalmente en una pequeña fracción de pares pero es difusa por usuario.
• Compromisos Prácticos: Aunque el biclustering ofrece la mayor calidad, los métodos basados en bandidos proporcionan una alternativa viable y escalable para despliegues comerciales de gran escala donde el tiempo de ejecución es una restricción primaria.

Los autores concluyen que, si bien su marco de trabajo mejora la relevancia y la eficiencia del targeting, depende de embeddings aprendidos de datos de comportamiento, lo que requiere consideraciones de transparencia y equidad para evitar reforzar las disparidades existentes en la segmentación de usuarios.