Una Solución Rentable y Escalable: Sistema de Recomendación basado en Filtros Colaborativos

Ivan Fernández, César Silgo y Juan Arévalo

d&a blog

El pasado jueves (26 de septiembre) tuvimos la oportunidad de presentar una colaboración entre BBVA Data & Analytics y BEEVA en el Theatre of Partners durante la AWS Summit Madrid 2017.

En la conferencia, presentamos un enfoque rentable para los sistemas de recomendación basados ​​en el filtro colaborativo (RS), que escalan a millones de usuarios y un millón de productos. Nuestra implementación hizo uso de AWS EMR con Spark, para producir un modelo de factorización de matriz implícita de la matriz de calificación original. Al principio del proyecto descubrimos que la implementación basada en la CPU resultó ser demasiado costosa y poco práctica para el cálculo de la propia recomendación -i.e. la multiplicación de vectores de característica de producto de usuario, que implica entre 1012 a 1014 operaciones. Como la multiplicación matricial es una operación embarazosa paralela, decidimos que la tarea podría hacerse en GPUs.

La charla fue bien recibida, por lo que pensamos en explicarlo en mayor detalle en un blog. Aquí, empezamos a motivar la necesidad de RS muy grande cuando atacamos la larga cola del catálogo de productos. A continuación, revisaremos brevemente algunas técnicas de RS y daremos los detalles de cómo las implementamos en los clústeres EMR de Spark y AWS. Después de mostrar por qué Spark falló en nuestro caso de uso, volvemos al origen del problema, es decir, la escala del número de recomendaciones que se deben hacer. Esta enorme escala nos obligó a pasar a las GPU, y por lo tanto, explicamos a continuación por qué las GPUs son más adecuadas para esta tarea, y el detalle de su implementación utilizando TensorFlow en las instancias AWS p2.8xlarge- lanzado para uso de producción sólo una semana antes empezamos a usarlos-. Posteriormente, ofrecemos algunos de los aspectos clave para entrar en producción en la nube AWS con este tipo de tecnologías. Finalmente, sacamos algunas conclusiones y líneas de trabajo futuro.

Sistemas de Recomendación y Larga-Cola

Los sistemas de recomendación (RS) se están convirtiendo en ubicuos a las aplicaciones en línea más comunes: de sugerencias personalizadas de la siguiente canción para escuchar, la película que ver, o el próximo producto financiero que adquirir, pasando por el descubrimiento de un comercio cercano para la próxima compra. Este tipo de RS presentan a los clientes con sugerencias personalizadas, lo que permite a las empresas hacer conocer los productos menos populares, pero rentables en la larga cola de su catálogo.

El fenómeno de la larga cola es una propiedad estadística presente en las distribuciones después de un decaimiento de la ley de potencia (pero no limitado a): hay pocos elementos que ocurren con una frecuencia muy alta y un número enorme que aparece en un número relativamente pequeño de casos. Cuando se traza la frecuencia (aka, popularidad) de cada elemento ocurrencia, se ve una cola que parece no tener fin, de ahí el nombre de larga cola. Esto se representa esquemáticamente en la figura anterior. Hay muchos ejemplos de distribuciones que exhiben una larga cola. El número de seguidores que cada usuario tiene en Twitter podría ser un ejemplo, con Barack Obama siendo ciertamente considerado como un elemento de cola corta en dicha distribución (muy popular), y los autores de este post como elementos en la cola larga (mucho menos popular que Obama, calculamos). Otros ejemplos clásicos incluyen la distribución de ventas por producto en un minorista web, como Amazon, o la distribución de popularidad de canciones y películas en plataformas como Spotify o Netflix.

Entonces, ¿por qué la cola larga es absolutamente relevante? Resulta ser muy importante para las economías de escala, como señaló Chris Anderson en su famoso libro The Long Tail: Why the Future of Business Is Selling Less of More. La idea básica es que si usted tiene un catálogo de productos muy grande, el volumen de ventas acumuladas de productos raros puede compensar o superar el volumen de ventas de los pocos productos bien conocidos. De hecho, este modelo de negocio es la esencia de varias empresas exitosas como Amazon, Spotify o Netflix. El problema es, ¿cómo mostrar el catálogo completo a los usuarios? Aquí es donde entran en la escena los sistemas de recomendación: Los sistemas de recomendación son herramientas diseñadas para filtrar información no relevante al mismo tiempo que ofrecen sugerencias personalizadas. Además, si desea proporcionar a los usuarios una experiencia verdaderamente personalizada, debe tener un catálogo de productos grande que satisfaga la variedad de gustos de cada posible usuario.

Métodos de Filtrado Colaborativo

La siguiente pregunta es cómo construir un sistema de recomendación para productos de nicho, de una manera asequible y escalable. En el caso de tener la historia de las adopciones de los usuarios (es decir, escuchas, relojes, clicks, compras, etc.), una técnica bien establecida es el llamado Filtrado Colaborativo (CF) para la retroalimentación implícita. Los métodos implícitos de los CF intentan predecir la preferencia que un usuario tendrá para los productos no vistos en el catálogo, basado en las preferencias observadas que todos los usuarios han tenido para todos los productos. Un ejemplo bastante famoso es el de Amazon de “usuario que compró este producto también compró estos otros productos”.

Un déficit de este tipo de métodos CF (usualmente conocido como K-Nearest Neighbors, o KNN), es que no proporciona a los usuarios una recomendación para todos los productos posibles (no a bajo coste, al menos), sino más bien para el K más similar a un usuario / producto dado. Sin embargo, nuestro modelo de negocio requiere tener una recomendación para cada producto posible, ya que sólo un subconjunto del catálogo de productos estará disponible a la vez. Esta restricción no es tan rara en el mundo de los negocios: considere, por ejemplo, productos descontinuados, que podrían contener valiosa información sobre las preferencias del usuario y, sin embargo, no pueden ofrecerse.

Tal requisito puede ser satisfecho por otro, muy popular, método de filtrado colaborativo: factorización de la matriz. Para esta técnica, las interacciones entre usuarios y productos se apilan formando una matriz grande (la matriz de calificación), que tiene tantas filas como usuarios, y tantas columnas como productos hay. Ver la matriz R en la siguiente figura. Observe por favor que tal matriz de la calificación estará llena de ceros, pues la mayoría de las interacciones del artículo del usuario son desconocidas, y tendrá pocos elementos con un 1 (que indica una interacción observada del artículo del usuario). La tarea de los modelos de Factorizaciones de Matriz Implícita es completar la matriz de clasificación R, y así proporcionar una predicción para la preferencia de un usuario por cada producto. Estas predicciones numéricas se pueden ordenar, produciendo una lista de recomendaciones.

Sin entrar en demasiados detalles técnicos, la factorización de matrices consiste en descomponer la matriz de clasificación original en dos matrices más pequeñas, U y P en la figura anterior. La recomendación se obtiene después de multiplicar los dos. Como estas matrices son forzadas a ser mucho más pequeñas que la original, su producto producirá una matriz de clasificación sin ceros (matemáticamente, las matrices de descomposición U y P tienen un rango k, con k típicamente alrededor de varias decenas o centenas, eso es mucho menor que el número de usuarios o elementos).

En este punto, es importante darse cuenta de la escala de la matriz de calificación: en nuestro caso, constaba de decenas de millones de usuarios y más de un millón de productos. Por lo tanto, necesitábamos tomar una solución escalable, probablemente asequible a este problema.

Entramos en profundidad en el Sistema de Recomendación de Spark

Hay varias implementaciones eficaces y escalables de Factorización de Matrices Implícita en la industria. Entre ellos, uno destacado es el proporcionado por Apache Spark, un motor de procesamiento de datos distribuido que se puede ejecutar fácilmente en Amazon Web Services con un cluster de Mapreduce Elastic.

Apache Spark implementa una versión distribuida del método Alternating Least Square (ALS) method with Weight Regularization. En nuestro caso, utilizamos la API Scala, así como la versión implícita del modelo, diseñada para modelar preferencias en lugar de clasificaciones. Normalmente ejecutamos nuestros experimentos en instancias AWS r3 / r4, ya que están optimizadas para motores que consumen mucha memoria, como Spark. Los tamaños de los grupos variaban de unas pocas decenas a más de un centenar de ejecutores, dependiendo de cada caso.

Como buena práctica de código limpio, implementamos una definición personalizada para cada clase, forzando una clara separación entre las fases de modelado y recomendación. Estas clases cubren el mapeo inicial de los archivos de origen, el cálculo de un modelo de factorización de matriz y la generación de recomendaciones. Nos gustaría destacar que una definición adecuada de campos y tipos de derechos era fundamental para mejorar el rendimiento general. Además, optimizamos todos los hiperparámetros de Spark, como el nivel de paralelismo, la memoria y la fracción de almacenamiento, el montón JVM, etc.

Después de todos estos esfuerzos, pudimos calcular el modelo de factorización de la matriz con recursos razonables (tanto en tiempo como en coste). Sin embargo, la generación de todas las recomendaciones requeridas falló sistemáticamente, no importa cuántos ejecutores se usaron. Curiosamente, el uso de la CPU durante la fase de recomendación siempre se mantuvo por debajo del 30%.

Este uso relativamente bajo de la CPU, nos permitió darnos cuenta de que el rendimiento de ALS está fuertemente afectado por su tamaño de bloque. El tamaño de bloque determina cómo se dividen las matrices de usuario y de producto (U y P en la descripción anterior), de modo que la multiplicación matricial se puede realizar en bloques usando bibliotecas de álgebra estándar. Dado que Spark es un sistema distribuido, el tamaño de los bloques determina tanto el uso de la CPU como la cantidad de datos que debe transferirse entre los ejecutores. Desafortunadamente, el parámetro de tamaño de bloque fue codificado en el método de bloqueo dentro de la implementación de Spark que usamos (y permanece como tal, como en la versión 2.2.0 de Spark), vea la siguiente figura. Después de realizar varias pruebas de esfuerzo, un valor diferente para el tamaño de bloque predeterminado demostró un mejor rendimiento. En consecuencia, implementamos una versión personalizada del método bloquify, que nos permitió parametrizar el tamaño del bloque.

Gracias a esta parametrización, hemos logrado incrementar el uso de la CPU del 30% al 70%, ¡nada mal! Y sin embargo, no pudimos terminar la fase de recomendación con un clúster de 80 nodos funcionando durante 6 horas. ¿Qué podría estar saliendo mal?

Repensando el problema: CPU vs GPU

Dado los esfuerzos que hicimos tratando de optimizar varios clusters de Spark -grandes y optimizados-, pensamos que sería oportuno detenernos y pensar en el problema que estábamos enfrentando. Estaba claro que estábamos cosechando todos los beneficios de Spark en la CPU, y sin embargo, no pudimos completar la tarea.

¿Sería posible que el número de operaciones requeridas para la recomendación fuera simplemente demasiado? Bueno, podría ser. Teníamos entre 2 y 20 millones de usuarios, dependiendo del país al que se aplica la RS, y más de un millón de artículos por país. Por lo tanto, el número de recomendaciones era algo entre 2 y más de 20 trillones. Eso es sin duda mucho, pero era difícil entender el tamaño de la misma.

Para visualizar cuánto era un trillón de operaciones, empezamos a buscar ejemplos en la naturaleza que pudieran servir como comparación. Por ejemplo, encontramos en la web que el número de dólares en efectivo en todo el mundo era de alrededor de 100 mil millones. Pero eso no es ni siquiera cerca de un billón! Así que pensamos en pasar a otro campo, donde casi todo se cuenta con grandes números (o muy pequeños, pero nada intermedio): la astrofísica. Allí, tenemos varios ejemplos que nos pueden ayudar a visualizar el tamaño de nuestro problema -ver la figura anterior, donde la superficie de cada bola es proporcional al número de operaciones-. Por ejemplo, el número de estrellas que constituyen la Vía Láctea -nuestra galaxia, que no es tan grande- se calcula en 400.000 millones a lo sumo; no lo suficientemente cerca. Pero el número de galaxias en el Universo observable se cree que es de alrededor de dos billones. ¡Bingo! Por lo tanto, para un país de tamaño mediano, tuvimos que hacer tantas recomendaciones como galaxias; y para el país más grande, teníamos diez veces eso!

Por lo tanto, dada la asombrosa cantidad de recomendaciones que teníamos que calcular, necesitábamos paralelizar aún más el cálculo. Y esto es lo que se hacen las Unidades Gráficas de Computación (GPU). Tal vez, habías oído hablar de ellas en el contexto de los videojuegos, donde se utilizan para el procesamiento de fotogramas de vídeo lo más rápido posible. La cosa es que una imagen no es nada más que una matriz, por lo que fue el hardware que necesitábamos. De hecho, las GPU de propósito general se utilizan hoy en día para la optimización Deep Learning precisamente por la misma razón: Deep Learning consiste en un montón de multiplicaciones matriciales.

En cuanto al nivel de paralelismo alcanzado por los dos hardwares, Ricardo Guerrero, uno de los Científicos de Datos en BEEVA Labs, dio como una brillante imagen de dibujos animados que ejemplifica las diferencias entre CPU y GPU. Las CPU están optimizadas para realizar tareas complicadas una tras otra con baja latencia. Es como un coche de Fórmula Uno: puede correr muy rápido, pero transporta una sola persona cada vez. Por el contrario, las GPU están optimizadas para tareas paralelas y simples (aka, multiplicaciones matriciales). Así que usted podría pensar en ellos como camiones, que no son tan rápidos, pero pueden transportar muchas cosas a la vez, por lo tanto, proporcionar más ancho de banda dependiendo de la naturaleza de la carga de trabajo. El número típico de núcleos para una CPU varía de 2 a 64, mientras que un Nvidia Tesla K80 GPU proporciona 2,496. Para fines de referencia, el precio actual de una instancia de gran demanda de m4.16xlarge con 64 núcleos que ejecutan Linux es de 3.55 USD por hora, mientras que el precio de una instancia de gran demanda de p2.8xlarge con 19.968 núcleos que ejecutan Linux es de 7.78 USD por hora.

Por lo tanto, lo único que quedaba era aprender a programar tales dispositivos GPU. En el nivel muy bajo, esto se hace en marcos como Nvidia CUDA y cuDNN. Pero queríamos un API de nivel superior más productivo, de código abierto, estable y con una gran comunidad detrás de él. Ingrese TensorFlow.

En noviembre de 2015 Google lanzó TensorFlow como una biblioteca de software de código abierto para realizar cálculos numéricos, con especial atención a las GPU. Desde entonces, se ha convertido en una herramienta popular para desarrollar e implementar cualquier modelo de aprendizaje automático. Así que decidimos aprovechar nuestras oportunidades con TensorFlow.

Con el fin de integrar en la memoria las matrices resultantes de la factorización, desarrollamos una estrategia de partición simple para que la multiplicación matricial se realice en bloques. Además, hacemos uso de TF Queues, lo que resulta en un aumento del 33% en el rendimiento. Larga historia corta, nos las arreglamos para producir todas las recomendaciones (y ordenarlos) en menos de 2 horas! Compare este resultado con la ejecución de 6 horas en un clúster de 80 nodos usando Apache Spark, que de hecho, nunca terminó. Por ejemplo, la reducción del coste es superior a un factor de 20.

Entrando en producción

Para poder lanzar el sistema de recomendación definido en un entorno de producción, definimos una arquitectura escalable, confiable y flexible en Amazon Web Services. Esta solución se basa en los fundamentos de la arquitectura en nube, tanto la infraestructura como el código, la automatización, la escalabilidad y los servicios gestionados.

Hemos creado AWS Lambdas programados y activados para orquestar cada paso en el proceso de recomendación de una manera sin servidor, desde alimentar el proceso y generar el modelo a obtener acceso a los valores finales recomendados.

Esta solución sigue dos enfoques diferentes para el procesamiento de datos. Primero, utilizamos EMR ejecutando Apache Spark para hacer cálculos más generales, es decir, generar nuestros propios modelos personalizados. Para procesos de computación específicos con mayor consumo de recursos, creamos nuestros propios clusters de procesamiento en instancias de EC2 P2 basadas en GPU Nvidia para ejecutar fragmentos de código TensorFlow. Estos grupos crecen y se reducen en función del tamaño de la carga de trabajo.

Hacemos un uso intensivo de los servicios como CloudFormation y EC2 Container Registry, tanto desde una infraestructura como un punto de vista de administración de código para automatizar la creación y administración de recursos de la nube. Es importante notar que debido a las características de nuestro sistema de recomendación, la escalabilidad fue uno de los principales puntos de dolor que necesitábamos abordar. Ser capaz de configurar y proporcionar nuestra infraestructura, especialmente las instancias de GPU, ya que el código nos permite encajar las cargas de trabajo de procesamiento de producción en una cuestión de configuración de propiedades.

Lecciones aprendidas y próximos pasos

Consideramos que una de las estrategias clave para tener éxito con este caso de uso fue la participación de equipos de Ciencia de Datos e Ingeniería de Datos desde el principio. Con frecuencia encontramos proyectos en los que una de las dos partes es desestimada y tomada en consideración demasiado tarde en la cadena de distribución, lo que lleva a malas técnicas formales de verificación, algoritmos poco precisos, soluciones no escalables, infraestructura costosa, preocupaciones de seguridad o malos resultados. Teniendo en cuenta los aspectos matemáticos y de ingeniería al construir desde el principio es una garantía en el largo plazo.

Hablando de escalabilidad, la complejidad de Big Data se ha medido tradicionalmente en volumen; cuanto más grande sea tu fuente de datos, más elegante será tu sistema. Ese no es el caso aquí, ya que estábamos manejando un conjunto de datos relativamente pequeño (escala TByte), pero tuvimos que calcular miles de millones de operaciones vectoriales con ellos. Aquí es donde los frameworks basados ​​en CPU tradicionales fallan mal, ya que las GPUs pueden ejecutar miles de operaciones matemáticas en paralelo mientras que las CPUs actuales sólo pueden ejecutar menos de cien. Las GPU han interrumpido el panorama de Ciencia de Datos y Big Data. En nuestra opinión, los que brinden un mejor apoyo para ellos liderarán la carrera en los próximos años.

Esta tendencia se ha vuelto cada vez más evidente en los últimos meses con el aumento exponencial de la popularidad de los marcos de GPU como TensorFlow y MxNet. Pero no fue tan claro hace un año cuando empezamos esta colaboración. Por ejemplo, la familia de instancias de GPU AWS P2 fue anunciada para su uso en producción apenas una semana antes de que comenzáramos. Ser capaz de desarrollar utilizando tecnologías de vanguardia y probar rápidamente a bajo coste utilizando un proveedor de la nube fue una gran ventaja para la reducción de time-to-market. Sin embargo, nuestra arquitectura de contenedores enfrentó algunos desafíos; por ejemplo, no era fácil, y aún no lo es, desplegar instancias de GPU personalizadas utilizando contenedores de Docker. Además, desde la perspectiva de una solución de extremo a extremo, tuvimos que implementar soluciones ad-hoc de monitoreo y escalado.

En cuanto a nuestros próximos pasos, aunque la solución presentada es barata y escalable, los sistemas de recomendación de factorización de matriz estándar, tales como ALS-WR, son conocidos por proporcionar recomendaciones de calidad moderada para matrices de clasificación muy escasas. Por lo tanto, nuestro trabajo actual se centra en la implementación de métodos de filtrado colaborativo basados ​​en GPU, que aprovechan la infraestructura de AWS y proporcionan recomendaciones personalizadas de larga cola. De hecho, nuestra arquitectura ha sido construida para soportar un esquema multi-modelo, de modo que los desarrollos personalizados puedan ser incluidos en el registro de imágenes y ser desplegados en nuevas tuberías de procesamiento.

Agradecimientos

Queremos agradecer a todos los equipos que hacen realidad este proyecto: Payments Business Unit de BBVA, los equipos de ingeniería y soporte de BEEVA, Data and Open Innovation Platform y el equipo de pagos de BBVA Data & Analytics.

Jessica Olmos, Cristian Galán, Valentín Quintas, Pedro García,
Roberto Andradas, Iván Fernández and César Silgo from BEEVA

Juan Ramón Duque, Marco Creatura, Javier García Santamaría
and Juan Arévalo from BBVA Data & Analytics