Supón que te piden construir un sitio web en el que los usuarios puedan escribir poemas y, a su vez, valorar los poemas que escriben otros usuarios.
Para incentivar que los usuarios lean y valoren los poemas de otros usuarios, la probabilidad de que un poema suyo sea seleccionado (para ser valorado por otro usuario) debe ser proporcional al número de votos que éste ha emitido. Así, aquellos que más se esfuerzan en leer y valorar a otros, serán también más leídos y valorados.
Teniendo en cuenta que hay millones de poetas, que cada poeta escribe un poema al día (en un año habrá 365 millones de poemas) y que cada poeta lee y valora 10 poemas al día (en un año habrá 3.650 millones de votos). ¿Cómo seleccionar aleatoriamente un poema?.
Solución inmediata, escaneando la lista de usuarios
Una solución tremendamente sencilla, consiste en tomar la lista del número de votos de los usuarios e ir acumulándola desde el primer elemento hasta el último:
| UsuarioId | VotosEmitidos | AcumuladoDeVotosEmitidos |
|---|---|---|
| 48517 | 85 | 85 |
| 13782 | 77 | 162 |
| 58184 | 79 | 241 |
| 47596 | 22 | 263 |
| 82126 | 89 | 352 |
| 21258 | 69 | 421 |
| 31316 | 58 | 479 |
| 64711 | 20 | 499 |
| 62975 | 68 | 567 |
| 84333 | 84 | 651 |
Con dicha lista, basta buscar un número aleatorio entre 0 y el total de votos y buscar el registro con el menor acumulado que lo contenga (ej. con una busqueda dicotómica).
El método es factible en la práctica, siempre que se permita calcular la tabla de acumulados cada "mucho" tiempo (por ejemplo, una vez al día), puesto que calcular la tabla de acumulados requiere un coste lineal respecto del número de filas (y vamos a tener millones con millones de peticiones cada día).
Por supuesto puede hacerse muy eficiente, por ejemplo podría mantenerse dicha tabla en memoria (aun con millones de usuarios no ocuparía más de unos pocos megabytes), actualizándose asíncronamente cada vez que un usuario emite un voto (requiere dos accesos indizados e incrementar la mitad de los acumulados de la tabla, lo cual llevará apenas algún milisegundo o menos). Así, el servicio estaría centralizado (con el consiguiente peligro de sobrecarga) pero las probabilidades resultantes se ajustarían enormemente a los requerimientos solicitados.
Para evitar una sobrecarga, la actualización puede hacerse en un buffer independiente de la tabla de lecturas (no bloqueantes) y mantener un pool de "entradas de votos" para hacer de forma simultánea la actualización de tramas de entradas de votos (las que han ido entrando mientras se recalculaba la actualización anterior).
Nota: el conteo de votos de cada poeta no es necesario recalcularlo si tenemos cuidado de incrementar un contador por usuario cada vez que alguien le emite un voto. Típicamente sería hacer un "update Usuario set TotalVotos = TotalVotos + Delta ..." cuando se inserta un voto ("Delta=1") o elimina un voto ("Delta=-1") posiblemente en sus respectivos triggers.
Escalable y distribuible
La solución anterior es práctica y muy sencilla de implementar. Parece razonable que se nos permita calcular offline una vez al día el "ranking" de los usuarios y usarlo sin modificar hasta el día siguiente. Si la precisión en las probabilidades es muy importante como para que esté actualizada constantemente (los poetas no parecen muy quisquillosos, pero nunca se sabe) o nuestro sistema siempre debe estar online (por lo que no podemos hacer un bloqueo global para calcular los acumulados), podemos implementar la versión complicada que requiere de un servicio específico (en línea y en memoria). Aun cuando cada habitante del planeta Tierra abriera cuenta en nuestro servicio, "sólo" necesitaríamos 260G RAM (7e9 humanos * 8 bytes * 5 números), 521G si usamos doble buffer.
Pero lo interesante es ¿podría hacerse sin mantener ninguna estructura o servicio adicional que no requiera considerar todos los usuarios?, ¿puede hacerse eficiente aunque el número de usuarios aumente indiscriminadamente? (en cuyo caso, la primera solución dejaría de valer), o, dicho de otra forma, ¿puede hacerse escalable y distribuible? (no deba estar centralizados ni los datos, ni las máquinas que resuelven las peticiones).
Si nos exigen una precisión total en la probabilidad de elegir un poeta u otro no parece posible, pero si nos permiten limitar el número de "rankings" diferentes, es decir, si nos permiten agrupar entre "poetas que no votan", "poetas que votan algo", "poetas que votan de vez en cuando", "poetas que votan con cierta frecuencia", ... entonces, podemos construir un método de selección (un algoritmo) que respete las probabilidades y sin tener que mantener ninguna estructura con coste proporcional al número de usuarios y, lo más interesante, tanto los datos como los servicios pueden estar distribuidos.
¿Como?
Bueno, si los poetas con más votos realizados los llamamos A, los siguientes B, ... entonces, está claro que deberán salir más veces los poemas de los A, luego de los B, ... basta entonces elegir uno cualquiera (todos con la misma probabilidad) si sale A entonces hemos terminado, si sale otro volvemos a tomar otro aleatoriamente, si sale A o B, entonces hemos terminado, si sale otro volvemos a tomar otro aleatoriamente, si sale A, B o C...
Por poner un ejemplo muy sencillo, supongamos que el 10% de los N usuarios están en el grupo A por tener el doble de votos que los del grupo B (el otro 90%). Entonces, cada usuario a € A debe tener el doble de probabilidad que cada usuario b € B de ser elegido para que le valoren un poema.
Como a un usuario lo eligen uniformemente de entre todos es P{u € A} = 0.1 y P{u € B} = 0.9.
Y según la estrategia anterior "en escalera" tenemos que hacer:
Donde se ve que la probabilidad final de P{Elegido A} = 0.1 + 0.9 * 0.1 = 0.19 y de P{Elegido B} = 0.9 * 0.9 = 0.81; es decir, si hay 100 usuarios (por poner las probabilidades de cada usuario individualmente) tenemos que P{Elegido cierto x con x € A} = 0.19 / 10 = 0.019 y por otro lado, P{Elegido cierto x con x € B} = 0.81 / 90 = 0.009.
Pues resulta que hemos tenido suerte y con dicho algoritmo para este caso concreto, se cumple que los poetas del grupo A tienen el doble de probabilidad de ser elegidos frente a los del grupo B (como debe ser, puesto que los primeros han realizado el doble de valoraciones que los segundos).
El tema ahora es, ¿qué grafo (autómata) debemos seguir si hay más grupos de usuarios?, ¿cómo podemos hacer que las probabilidades resultantes sean las buscadas?.
Cadenas de Markov
El grafo anterior que presenta un autómata y en el que cada arista posee una probabilidad de ser elegida, representa una Cadena de Markov, las cuales han sido profusamente estudiadas y de las que se conocen muchas propiedades interesantes.
Una cadena de Markov es un simple autómata, en el que no hay ninguna entrada de símbolos, lo que se hace para pasar de un estado al siguiente es elegir las alternativas aleatoriamente (con la distribución de probabilidad que sea).
Por ejemplo, la siguiente cadena de Markov:
(Fuente: Wikipedia)
Genera cadenas de la forma AAAEEAEAAAEAAAAEEAAAAAAEAAAA... sólo hay que seguir el autómata para verlo, es muy sencillo.
Lo que vamos a hacer para terminar de resolver nuestro problema, es crear un autómata generador de cadenas de Markov en el que dejaremos libres ciertas incógnitas, luego las despejaremos y ya tendremos nuestro seleccionador aleatorio de poemas escalable y distribuible.
El mejor autómata
A mí, no se me ocurre cual puede ser el autómata óptimo para cada conjunto de datos de entrada posible (número de grupos, probabilidades, etc...), pero está claro que debemos de poderlo generar según se deseen más o menos grupos de poetas, así, se me ha ocurrido hacer una estrella en el que hay un pétalo para cada grupo de poetas:
Es fácil demostrar que para ciertos conjuntos de datos no existe ningún autómata (ni de flor, ni de fruta ni de ningún tipo) óptimo (no hay solución), o que, también para cualquier autómata, serán necesarios muchos experimentos (obtener un usuario al azar) para obtener la probabilidad buscada (ej. si un usuario de entre un millón debe tener más de un millón de veces probabilidad que el resto ¡hacen falta un millón de lanzamientos en media!). Pero para datos "razonables", obtendremos soluciones "razonables" y, esta flor, permite encontrar siempre unos parámetros de ajuste.
La flor, desde inicio, obtiene un usuario al azar con coste O(1) y obtendrá un usuario de alguno de los grupos. Con cierta probabilidad h desconocida, se lo quedará o descartará, repitiendo el proceso un máximo prefijado de veces, con lo que el coste de la selección, sigue siendo O(1) independientemente del número de usuarios que existan y de cómo estén representados (ordenados, desordenados, en la misma máquina, varias, ...). El único requisito es poder elegirlos aleatoriamente de forma uniforme.
Despejando las H
Dado un conjunto de grupos A, B, C, ... y sus respectivas probabilidades conocidas a, b, c, ... (que no son más que el número de usuarios que contiene cada grupo dividido por el total de usuarios) tenemos una serie de incógnitas ha, hb, hc, ... que harán que, la probabilidad final de alcanzar cada grupo, sean las buscadas, llamemoslas Pa, Pb, Pc, ... (que no son más que la suma de votos de cada grupo partido por el total).
Por otro lado, hemos dicho que el autómata debe terminar en T iteraciones, para que nuestro algoritmo siga teniendo coste constante. Pero partiendo de inicio, T debe ser un número impar de saltos (para estar en un estado "Quizás X" o en un estado "Elige X").
¿Cual será entonces la probabilidad de haber elegido un usuario de cada grupo tras "ir saltando" T veces por nuestra cadena de Markov?.
Cualquier grafo, puede representarse mediante una matriz y las cadenas de Markov no son una excepción, denominándose en este caso matriz de transición. Que no es más que hacer lo mismo que en cualquier otro grafo:
| M = | I | Q.A | E.A | Q.B | E.B | Q.C | E.C | ... | |
|---|---|---|---|---|---|---|---|---|---|
| I | 0 | a | 0 | b | 0 | c | 0 | ... | |
| Q.A | 1-ha | 0 | ha | 0 | 0 | 0 | 0 | ... | |
| E.A | 0 | 0 | 1 | 0 | 0 | 0 | 0 | ... | |
| Q.B | 1-hb | 0 | 0 | 0 | hb | 0 | 0 | ... | |
| E.B | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ... | |
| ... | ............ | ||||||||
La matriz anterior indica la probabilidad de ir de un estado cualquiera a otro cualquiera, se ve por ejemplo que del nodo "Elige A" no se puede ir al nodo "Inicio" (probabilidad 0) y que del nodo "Quizás A" al nodo "Elige A" hay una probabilidad de ha.
Aunque si no estás acostumbrado a calcular probabilidades de sucesos dependientes te puede costar verlo, la potencia n-ésima de la matriz de transición nos da las probabilidades, de todos los caminos posibles, desde cada nodo a cada nodo. Realmente, ya lo hemos hecho (de forma muy sencilla) en el ejemplo de "Elige u" anterior.
Así, sólo tenemos que hacer MT + 1 (el más 1 es porque la primera transición ocurre en el primer producto M2) para obtener las probabilidades finales. Como sólo nos interesan las que salen del nodo inicial, resulta que las tenemos en la primera fila de la matriz resultante de la potencia.
Por último y como hemos limitado a T transiciones, podremos haber terminado en un estado "Quizás X" o bien "Elige X", por lo que las probabilidades buscadas hay que igualarlas a la suma de ambas, es decir:
| Pa = P{Quizás A} + P{Elige A} |
| Pb = P{Quizás B} + P{Elige B} |
| Pc = P{Quizás C} + P{Elige C} |
| ... |
Con este procedimiento, podemos elegir libremente el número de grupos en que clasificamos a los poetas participativos y los no participativos. Además, podemos graduar la precisión que queremos obtener en las probabilidades resultantes, a costa de aumentar (con T) el número máximo de consultas a la base de datos (para buscar un usuario cualquiera aleatoriamente). Más grupos y menos T implica peor precisión en las probabilidades obtenidas, menos grupos y más T implica un mejor ajuste.
¿Cómo resolver las incógnitas?
Hay muchas formas, en general, al elevar a la potencia la matriz M nos aparecerán polinomios de grado superior en muchas variables, por lo que aunque es fácil obtener la expresión simbólica, despejar las variables parece que sólo se podrá hacer numéricamente.
Por ejemplo en Python podría usarse SymPy para elevar la matriz a la potencia y luego despejar numéricamente las incógnitas.
En el siguiente apartado, que no añade nada más a la solución, utilizo una sencilla búsqueda por Montecarlo en el dominio de las h.
Uhm... vale ¿y qué hacemos con las incógnitas?
Con ellas, tenemos perfectamente determinado el autómata no determinista (en este caso la cadena de Markov) con todas las probabilidades conocidas, sólo se trata de evaluarlo y ver en que estado (usuario) termina. Podemos recalcular el autómata en cada petición o mantenerlo cacheado durante X tiempo, además, es independiente (se ha admitido no transaccionalidad en la precisión obtenida) de cualquier otro estado, por lo que diferentes máquinas pueden calcular sus autómatas de forma independiente asegurando la tan ansiada distribuibilidad, escalabilidad y por tanto tolerancia a fallos, siempre online, etc...
Un ejemplo en Haskell
Realmente, todo se reduce a construir la matriz de transición, elevar a la potencia, despejar las incógnitas y evaluar las veces requeridas el autómata no determinista obtenido. Yo me enrollo mucho, pero en unas pocas líneas lo tenemos resuelto.
El siguiente código sirve para obtener las soluciones (las h) para cualquier número de grupos:
(En un entorno real y dado que es un sistema de polinomios seguro que podemos usar un solver mucho mejor; ¡pero éste es cómodo!).
Con él y a modo de "ejemplo de uso", podemos ver cómo obtener con distribución uniforme números naturales que existen con distribución no uniforme (les damos más preferencia a unos números que a otros).
El siguiente código, genera un generador (sí, genera un generador que a su vez genera números con la distribución buscada) de números aleatorios pero de tal forma que la probabilidad de obtener un número divisible por dos, un número divisible por tres (pero no por dos) u otro (no divisible ni por dos ni tres) es la misma (cuando respectivamente las probabilidades son 1/2, 1/6 y 1/3) y eso, sobre "todos" los números naturales (que no admiten la primera estrategia comentada).
El siguiente código compara el generador anterior con el estandar (con el no ajustado), además, utiliza dos valores de T para comparar la bondad de ajuste (precisión) obtenida.
