Los investigadores están un paso más cerca de agregar procesos probabilísticos a máquinas deterministas
Un problema de computación a largo plazo: simulación de la tirada de dados
Aquí hay un ejercicio engañosamente simple: inventa un número de teléfono al azar. Siete números seguidos, elegidos para que cada uno de ellos sea igualmente probable y para que su elección del siguiente dígito no afecte la elección del siguiente. Lo más probable es que esto no funcione para usted. No puede confiar en mi palabra: la investigación realizada desde la década de 1950 muestra que no somos aleatorios desde un punto de vista matemático, sin siquiera darnos cuenta.
No te enfades. Las computadoras tampoco generan números aleatorios. No deberían: los programas y el hardware de las computadoras se ejecutan en lógica booleana , no en probabilidades. "La cultura informática se basa en el determinismo", dijo Vikash Mansinhka.que dirige un proyecto de computación probabilística en el MIT, y aparece en casi todos los niveles ".
Sin embargo, los programadores quieren crear programas que se ejecuten con aleatoriedad, a veces las tareas lo requieren. A lo largo de los años, se han desarrollado algoritmos ingeniosos que, si bien no generan números aleatorios, ofrecen formas inteligentes y eficientes de utilizar y manipular la aleatoriedad. Uno de los intentos más recientes lo ha realizado el grupo de Mansinkhee en el MIT, que está a punto de presentar su rodillo de dados Fast Loaded , o FLDR, en una conferencia internacional de inteligencia artificial y estadísticas en agosto.
En pocas palabras, FLDR utiliza una secuencia aleatoria para simular perfectamente un dado de trampa (o una moneda mal ponderada o cartas marcadas). "Él muestra cómo convertir un lanzamiento de moneda perfectamente aleatorio en uno distorsionado", dijo el matemáticoPeter Birhorst de la Universidad de Nueva Orleans. Birhorst no participó en este estudio, pero considera que las premisas subyacentes a FLDR son "convincentes".
FLDR no le dará una ventaja cuando juegue Monopoly o en las mesas de dados de Las Vegas. Sin embargo, sus creadores dicen que permite integrar números aleatorios en software o hardware determinista de forma nativa. La incorporación de tales incertidumbres ayudará a las máquinas a hacer predicciones más parecidas a las humanas y simular mejor los eventos basados en el azar: el clima o los mercados financieros.
La aleatoriedad es un concepto más complejo de lo que parece. Cada dígito en una secuencia de dígitos aleatorios, donde no hay un patrón discernible, la probabilidad de ocurrencia es la misma. Por ejemplo, el número π no es aleatorio, pero se cree que según esta definición sus números son aleatorios (los matemáticos lo llaman "normal"): cada dígito del 0 al 9 aparece aproximadamente el mismo número de veces.
Y aunque puede encontrar "generadores de números aleatorios" en Google, no habrá pura casualidad. Los procesadores, motores de búsqueda y generadores de contraseñas actuales utilizan un método "pseudoaleatorio" que es "suficientemente bueno" para la mayoría de las tareas. Los números se generan utilizando fórmulas complejas; sin embargo, en teoría, conocer la fórmula puede predecir la secuencia.
Los científicos han intentado crear una verdadera aleatoriedad en las máquinas durante al menos 80 años. Hasta entonces, se tomaron números aleatorios de asistentes viejos y confiables: lanzaron huesos, sacaron bolas con números de una bolsa bien mezclada o usaron otros dispositivos mecánicos. En 1927, un estadístico tomó una muestra de los datos del censo, compilando una tabla de 40.000 números aleatorios.
Vikash Mansinkhka, gerente de proyectos de computación probabilística en MIT
Las primeras fuentes de números aleatorios fueron las máquinas físicas. El primer generador de números aleatorios fue inventado por los estadísticos británicos Maurice George Kendall y Bernard Babington Smith, quienes lo describieron en 1938. El auto fue colocado en un cuarto oscuro, y allí giraba un disco, dividido en 10 sectores, numerados del 0 al 9. Cuando alguien presionaba el botón a intervalos irregulares, breves destellos de neón o chispas iluminaban el disco, arrebatándolo de la oscuridad, parecía una imagen congelada donde solo se veía un número. Una máquina posterior, Ernie, usó ruido en tubos de neón. Desde 1957, ha estado eligiendo números ganadores en la lotería británica.
Más tarde, en busca de secuencias verdaderamente aleatorias, los informáticos, según Birhorst, tuvieron que recurrir a fenómenos naturales como la radiación reliquia o los sistemas cuánticos impredecibles. “Hay procesos aleatorios verdaderamente impredecibles en la naturaleza que pueden explotarse”, dijo. "Un electrón que se refleja hacia la izquierda o hacia la derecha no puede decir de antemano lo que hará".
Sin embargo, el azar por sí solo no te llevará muy lejos. A fines de la década de 1940, los físicos comenzaron a generar números aleatorios que encajaban en una distribución de probabilidad dada. Estas herramientas, versiones teóricas de los cubos NOS, funcionaron con mayor precisión en situaciones reales, como la congestión del tráfico o las reacciones químicas. En 1976, los pioneros de la informática Donald Knuth y Andrew Yaopresentó un algoritmo capaz de producir muestras aleatorias de cualquier matriz de resultados ponderados basados en una secuencia de números aleatorios. "Este es el algoritmo más eficiente en el tiempo que se pueda imaginar", dijo Fera Saad, una estudiante de posgrado en el laboratorio de Mansinkhke que dirigió el FLDR.
Desafortunadamente, dice Saad, el algoritmo hace un compromiso conocido entre los científicos de la computación: muchas aplicaciones de ejecución rápida usan mucha memoria, y las aplicaciones que usan poca memoria pueden llevar mucho tiempo. El algoritmo de Knuth y Yao cae en la primera categoría, lo que lo hace elegante, pero requiere demasiada memoria para su uso práctico.
Sin embargo, a Saad se le ocurrió un movimiento inteligente la primavera pasada. Se dio cuenta de que si la suma de los pesos de los dígitos del cubo es igual a alguna potencia de 2, el algoritmo resulta ser eficiente tanto en memoria como en tiempo. Imagina que para un cubo de seis lados, los pesos 1, 2, 3, 4, 5 y 1 se suman a las probabilidades de desplegar números del 1 al 6. Es decir, la probabilidad de desplegar 1 es 1/16 y 2 es 2/16. Como resultado, la suma de los pesos es 16 - o 2 4 - y el algoritmo resulta ser eficiente tanto en memoria como en tiempo.
Fera Saad, estudiante de doctorado en MIT
Pero digamos que los pesos son 1, 2, 3, 2, 4, 2, lo que suma 14. Dado que 14 no es una potencia de 2, el algoritmo de Knut-Yao requerirá mucha más memoria. Saad se dio cuenta de que se podía agregar peso adicional para que los pesos siempre sumen una potencia de 2. En este caso, puede agregar una cara ficticia con un peso de 2, y luego los pesos suman 16. Si el algoritmo elige una cara real, este valor se registra. Si es ficticio, el valor se descarta y el algoritmo comienza de nuevo.
Esta es la clave de la eficacia de FLDR, lo que la convierte en una poderosa herramienta de simulación. La cantidad de memoria adicional para lanzamientos adicionales es insignificante en comparación con las grandes cantidades requeridas por la versión original del algoritmo.
FLDR hace que el algoritmo Knuth-Yao sea eficiente y brinda la oportunidad de expandir su alcance. Las simulaciones del cambio climático, las predicciones de cultivos, las simulaciones de partículas, los modelos del mercado financiero y las explosiones nucleares subterráneas dependen de números aleatorios distribuidos con probabilidad ponderada. Además, los números aleatorios son el núcleo de los esquemas criptográficos que protegen los datos transmitidos a través de Internet.
Mansinkhka dice que FLDR puede ayudar a los investigadores a encontrar formas de integrar la probabilidad en los procesadores de computadora, su laboratorio en el MIT está haciendo esto. El algoritmo puede ayudar a mejorar las bibliotecas de software y las nuevas arquitecturas de procesadores que pueden generar números aleatorios y utilizarlos de manera eficiente. Este sería un cambio significativo de las máquinas booleanas deterministas a las que estamos acostumbrados.
“Podríamos tener una buena oportunidad de integrar la aleatoriedad en los componentes básicos del software y el hardware”, dijo.
Ver también: