Os pesquisadores estão um passo mais perto de adicionar processos probabilísticos a máquinas determinísticas
Um problema de computação de longo prazo - Simulando o lançamento de dados
Aqui está um exercício aparentemente simples: crie um número de telefone aleatório. Sete números em uma linha, escolhidos de forma que cada um deles seja igualmente provável e para que a escolha do próximo dígito não afete a escolha do próximo. Provavelmente, isso não funcionará para você. Não se pode acreditar na minha palavra - pesquisas realizadas desde a década de 1950 mostram como não somos aleatórios do ponto de vista matemático, mesmo sem perceber.
Não fique chateado. Os computadores também não geram números aleatórios. Eles não deveriam - os programas e hardware dos computadores são executados na lógica booleana , não em probabilidades. “A cultura da computação é baseada no determinismo”, disse Vikash Mansinhkaque dirige um projeto de computação probabilística no MIT - e isso aparece em quase todos os níveis. "
No entanto, os programadores desejam criar programas que rodam aleatoriamente - às vezes as tarefas exigem isso. Ao longo dos anos, algoritmos engenhosos foram desenvolvidos que, embora não gerem números aleatórios, oferecem maneiras inteligentes e eficientes de usar e manipular a aleatoriedade. Uma das tentativas mais recentes foi feita pelo grupo de Mansinkhee no MIT, que está prestes a revelar seu Fast Loaded Dice Roller , ou FLDR, em uma conferência internacional de IA e estatísticas em agosto.
Para simplificar, o FLDR usa uma sequência aleatória para simular perfeitamente um dado de trapaça (ou uma moeda mal ponderada ou cartas marcadas). “Ele mostra como transformar uma moeda perfeitamente aleatória em uma distorcida”, disse o matemáticoPeter Bierhorst, da New Orleans University. Birhorst não esteve envolvido neste estudo, mas considera as premissas subjacentes ao FLDR “convincentes”.
O FLDR não lhe dará vantagem ao jogar Monopólio ou nas mesas de dados de Las Vegas. No entanto, seus criadores dizem que ele permite que números aleatórios sejam integrados em software ou hardware nativamente determinístico. Incorporar essas incertezas ajudará as máquinas a fazer previsões mais humanas e a simular melhor os eventos com base no acaso, como o clima ou os mercados financeiros.
A aleatoriedade é um conceito mais complexo do que parece. Cada dígito em uma sequência de dígitos aleatórios onde não há um padrão discernível, a probabilidade de ocorrência é a mesma. Por exemplo, o número π não é aleatório, mas acredita-se que por esta definição seus números sejam aleatórios (os matemáticos o chamam de "normal"): cada dígito de 0 a 9 aparece aproximadamente o mesmo número de vezes.
E embora você possa encontrar "geradores de números aleatórios" no Google, não haverá puro acaso. Os processadores, mecanismos de pesquisa e geradores de senha de hoje usam um método “pseudo-aleatório” que é “bom o suficiente” para a maioria das tarefas. Os números são gerados usando fórmulas complexas - no entanto, em teoria, saber a fórmula pode prever a sequência.
Os cientistas vêm tentando construir uma aleatoriedade real nas máquinas há pelo menos 80 anos. Até então, números aleatórios eram obtidos de assistentes antigos e confiáveis - eles jogavam ossos, tiravam bolas com números de um saco bem misturado ou usavam outros dispositivos mecânicos. Em 1927, um estatístico obteve uma amostra de dados de um censo, compilando uma tabela de 40.000 números aleatórios.
Vikash Mansinkhka, gerente de projeto de computação probabilística do MIT
As primeiras fontes de números aleatórios foram máquinas físicas. O primeiro gerador de números aleatórios foi inventado pelos estatísticos britânicos Maurice George Kendall e Bernard Babington Smith, que o descreveram em 1938. O carro foi colocado em uma sala escura, e lá girou um disco, dividido em 10 setores, numerados de 0 a 9. Quando alguém pressionava o botão em intervalos irregulares, breves flashes de neon ou faíscas iluminavam o disco, arrancando-o da escuridão, parecia uma imagem congelada onde apenas um número era visível. Uma máquina posterior, Ernie, usava ruído em tubos de néon. Desde 1957, ela tem escolhido números vencedores na loteria britânica.
Mais tarde, em busca de sequências verdadeiramente aleatórias, os cientistas da computação, de acordo com Birhorst, tiveram que recorrer a fenômenos naturais como radiação relíquia ou sistemas quânticos imprevisíveis. “Existem processos aleatórios realmente imprevisíveis na natureza que podem ser explorados”, disse ele. "Um elétron refletindo para a esquerda ou para a direita não pode dizer com antecedência o que fará."
No entanto, o acaso por si só não o levará muito longe. No final da década de 1940, os físicos começaram a gerar números aleatórios que se encaixam em uma determinada distribuição de probabilidade. Essas ferramentas - versões teóricas dos cubos NOS - funcionavam de forma mais precisa em situações reais, como congestionamentos de trânsito ou reações químicas. Em 1976, os pioneiros da ciência da computação Donald Knuth e Andrew Yaoapresentou um algoritmo capaz de produzir amostras aleatórias de qualquer matriz de resultados ponderados com base em uma sequência de números aleatórios. “Este é o algoritmo mais eficiente em termos de tempo que você pode imaginar”, disse Fera Saad, uma estudante de graduação no laboratório de Mansinkhke que liderou o FLDR.
Infelizmente, diz Saad, o algoritmo faz um compromisso conhecido entre os cientistas da computação: muitos aplicativos de execução rápida usam muita memória, e os aplicativos que usam pouca memória podem ser executados por muito tempo. O algoritmo de Knuth e Yao se enquadra na primeira categoria, o que o torna elegante, mas exige muita memória para uso prático.
No entanto, Saad veio com uma jogada inteligente na primavera passada. Ele percebeu que se a soma dos pesos dos dígitos do cubo for igual a alguma potência de 2, o algoritmo acaba sendo eficiente tanto na memória quanto no tempo. Imagine que, para um cubo de seis lados, os pesos 1, 2, 3, 4, 5 e 1 são adicionados às probabilidades de rolar números de 1 a 6. Ou seja, a probabilidade de rolar 1 é 1/16 e 2 é 2/16. Como resultado, a soma dos pesos é 16 - ou 2 4 - e o algoritmo acaba sendo eficiente tanto na memória quanto no tempo.
Fera Saad, estudante de doutorado no MIT
Mas digamos que os pesos sejam 1, 2, 3, 2, 4, 2, o que totaliza 14. Como 14 não é uma potência de 2, o algoritmo de Knut-Yao exigirá muito mais memória. Saad percebeu que seria possível adicionar peso extra para que os pesos sempre totalizassem uma potência de 2. Nesse caso, você pode adicionar uma face fictícia com um peso de 2 e, em seguida, os pesos somam 16. Se o algoritmo escolher uma face real, esse valor será registrado. Se for fictício, o valor é descartado e o algoritmo é reiniciado.
Esta é a chave para a eficácia do FLDR, tornando-o uma ferramenta de simulação poderosa. A quantidade de memória extra para lances extras é insignificante em comparação com as grandes quantidades exigidas na versão original do algoritmo.
FLDR torna o algoritmo Knuth-Yao eficiente e oferece uma oportunidade para expandir seu escopo. Simulações de mudanças climáticas, previsões de safras, simulações de partículas, modelos de mercado financeiro e explosões nucleares subterrâneas são todos dependentes de números aleatórios distribuídos com probabilidade ponderada. Além disso, os números aleatórios estão no centro dos esquemas criptográficos que protegem os dados transmitidos pela Internet.
Mansinkhka diz que o FLDR pode ajudar os pesquisadores a encontrar maneiras de integrar a probabilidade aos processadores de computador, seu laboratório no MIT está fazendo isso. O algoritmo pode ajudar a melhorar as bibliotecas de software e novas arquiteturas de processador que podem gerar números aleatórios e usá-los com eficiência. Esta seria uma mudança significativa em relação às máquinas booleanas determinísticas a que estamos acostumados.
“Podemos ter uma boa chance de integrar a aleatoriedade aos blocos de construção de software e hardware”, disse ele.
Veja também: