Uma rede neural pode ser usada para prever o próximo número pseudo-aleatório?

17

É possível alimentar uma rede neural com a saída de um gerador de números aleatórios e esperar que ela aprenda a função de hash (ou gerador), para que possa prever qual será o próximo número pseudo-aleatório gerado ?

Algo assim já existe? Se já foi feita uma pesquisa sobre isso ou algo relacionado (à previsão de números pseudo-aleatórios), alguém pode me indicar os recursos certos?

Atualmente, estou vendo esta biblioteca e seus links relacionados. https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent

AshTyson
fonte

Respostas:

13

Se estamos falando de um RNG perfeito, a resposta é um não claro . É impossível prever um número verdadeiramente aleatório, caso contrário, não seria verdadeiramente aleatório.

Quando falamos de pseudo RNG, as coisas mudam um pouco. Dependendo da qualidade do PRNG, o problema varia de fácil a quase impossível. É claro que um PRNG muito fraco como o publicado pelo XKCD poderia ser facilmente previsto por uma rede neural com pouco treinamento. Mas no mundo real as coisas parecem diferentes.

A rede neural poderia ser treinada para encontrar certos padrões no histórico de números aleatórios gerados por um PRNG para prever o próximo bit. Quanto mais forte o PRNG fica, mais neurônios de entrada são necessários, supondo que você esteja usando um neurônio para cada bit de aleatoriedade anterior gerado pelo PRNG. Quanto menos previsível o PRNG for, mais dados serão necessários para encontrar algum tipo de padrão. Para PRNGs fortes, isso não é viável.

Em uma nota positiva, é útil que você possa gerar uma quantidade arbitrária de padrões de treinamento para a rede neural, supondo que você tenha controle sobre o PRNG e possa produzir quantos números aleatórios desejar.

Como os PRNGs modernos são um componente essencial para a criptografia, uma extensa pesquisa foi realizada para verificar se eles são "aleatórios o suficiente" para suportar tais ataques de previsão. Portanto, tenho certeza de que não é possível, com os recursos computacionais disponíveis no momento, construir uma rede neural para atacar com êxito um PRNG considerado seguro para criptografia.

Também é importante notar que não é necessário prever exatamente a saída de um PRNG para quebrar a criptografia - pode ser suficiente prever o próximo bit com uma certeza de pouco mais de 50% para enfraquecer significativamente uma implementação. Portanto, se você for capaz de construir uma rede neural que preveja o próximo bit de um PRNG (considerado seguro para criptografia) com uma taxa de sucesso de 55%, provavelmente será a manchete das notícias de segurança por um bom tempo.

Demento
fonte
2
Uau, obrigado pela explicação por trás disso. Estou tentando analisar o padrão e prever o próximo bit, e não é um RNG perfeito, mas um PRNG um tanto sólido. Mas também não é o estado da arte. Eu acho que com um pouco de poder computacional e implementação adequada eu poderia prever com 60-70%, se não mais. Se possível, você pode apontar quaisquer recursos onde eu possa ler mais sobre isso. Eu não sou de um fundo de pesquisa e mais de um desenvolvedor.
precisa saber é o seguinte
3

Sendo um novato em aprendizado de máquina, fiz esse experimento (usando o Scikit-learn):

  • Gerou um grande número (N) de extrações pseudo-aleatórias, usando a função python random.choices para selecionar N números de 90.

  • Treinou um classificador MLP com dados de treinamento compostos da seguinte maneira:

    • i-ésima amostra: X <- resultados da loteria [i: i + 100], Y <- resultados da loteria [i]

    Na prática, eu visava uma função que, dada a N números, poderia prever a próxima.

  • Pediu ao classificador treinado para prever os números restantes.

Resultados:

  • é claro, o classificador obteve uma pontuação vencedora comparável à de adivinhação aleatória ou de outras técnicas não baseadas em redes neurais (comparei os resultados com vários classificadores disponíveis nas bibliotecas do scikit-learn)

  • no entanto, se eu gerar extrações pseudo-aleatórias da loteria com uma função de distribuição específica, os números previstos pela rede neural serão gerados aproximadamente com a mesma curva de distribuição (se você plotar as ocorrências dos números aleatórios e das previsões da rede neural, você pode ver que os dois têm a mesma tendência, mesmo que na curva de predições haja muitos picos.Talvez a rede neural seja capaz de aprender sobre distribuições de números pseudo-aleatórios?

  • Se eu reduzir o tamanho do conjunto de treinamento sob um determinado limite, vejo que o classificador começa a prever sempre os mesmos poucos números, que estão entre os mais frequentes na geração pseudo-aleatória. Estranhamente (ou talvez não) esse comportamento parece aumentar levemente a pontuação vencedora.

Francesco Bochicchio
fonte
3

Pergunta antiga, mas achei que valeria uma resposta prática. Por acaso, deparei com ele logo depois de olhar para um guia de como construir essa rede neural, demonstrando o eco da randint de python como exemplo . Aqui está o código final sem explicação detalhada, ainda bastante simples e útil, caso o link fique offline:

from random import randint
from numpy import array
from numpy import argmax
from pandas import concat
from pandas import DataFrame
from keras.models import Sequential
from keras.layers import LSTM
from keras.layers import Dense

# generate a sequence of random numbers in [0, 99]
def generate_sequence(length=25):
    return [randint(0, 99) for _ in range(length)]

# one hot encode sequence
def one_hot_encode(sequence, n_unique=100):
    encoding = list()
    for value in sequence:
        vector = [0 for _ in range(n_unique)]
        vector[value] = 1
        encoding.append(vector)
    return array(encoding)

# decode a one hot encoded string
def one_hot_decode(encoded_seq):
    return [argmax(vector) for vector in encoded_seq]

# generate data for the lstm
def generate_data():
    # generate sequence
    sequence = generate_sequence()
    # one hot encode
    encoded = one_hot_encode(sequence)
    # create lag inputs
    df = DataFrame(encoded)
    df = concat([df.shift(4), df.shift(3), df.shift(2), df.shift(1), df], axis=1)
    # remove non-viable rows
    values = df.values
    values = values[5:,:]
    # convert to 3d for input
    X = values.reshape(len(values), 5, 100)
    # drop last value from y
    y = encoded[4:-1,:]
    return X, y

# define model
model = Sequential()
model.add(LSTM(50, batch_input_shape=(5, 5, 100), stateful=True))
model.add(Dense(100, activation='softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['acc'])
# fit model
for i in range(2000):
    X, y = generate_data()
    model.fit(X, y, epochs=1, batch_size=5, verbose=2, shuffle=False)
    model.reset_states()
# evaluate model on new data
X, y = generate_data()
yhat = model.predict(X, batch_size=5)
print('Expected:  %s' % one_hot_decode(y))
print('Predicted: %s' % one_hot_decode(yhat))

Eu apenas tentei e realmente funciona muito bem! Levei apenas alguns minutos no meu velho netbook lento. Aqui está minha própria saída, diferente do link acima e você pode ver que a correspondência não é perfeita, então suponho que os critérios de saída sejam um pouco permissivos:

...
 - 0s - loss: 0.2545 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.1845 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.3113 - acc: 0.9500
Expected:  [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 79, 45, 95, 92, 32, 33]
Predicted: [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 95, 45, 95, 92, 32, 33]
isp-zax
fonte
Isso não está aprendendo a prever a sequência aleatória - está aprendendo a repeti-la. Concretamente, as amostras de treinamento, X, consistem em 5 números inteiros aleatórios e a saída, y, é o quarto número inteiro de 5. Por exemplo, se X = [15, 33, 44, 30, 3], y = 30. O LSTM está aprendendo a ecoar a 4ª amostra.
thinkski
Sim, bom argumento. Ainda acho que é um exemplo prático muito interessante do uso de LSTM. Se você souber como aprender algo como Mersenne Twister a partir de sementes fornecidas apenas como entrada, por favor, publique aqui como eu estaria realmente interessado em ver. Parece possível com amostras suficientes, mas posso estar completamente errado.
Isp-zax 17/03/19
2

Se um gerador de números aleatórios psuedo estiver jogando números fora, na análise desses números, você poderá determinar o algoritmo que os produziu, porque os números não são aleatórios, eles são determinados pelo algoritmo e não são por acaso. Se o mundo é composto de leis físicas que podem ser entendidas e replicadas, a aparente aleatoriedade que observamos nos eventos se deve a essas leis físicas. e o gerador de psuedo não é mais, e é a aleatoriedade real que, a partir de sua definição, é indeterminável e apresenta um paradoxo. Como as regras podem criar aleatoriedade por definição, certamente nossa percepção aparente da aleatoriedade dos eventos que observamos é uma alusão e é realmente uma certeza que não somos incapazes de prever.

Bobs
fonte
1
Verdade. Bastante filosófico. Esperava uma resposta técnica. Obrigado de qualquer maneira :)
AshTyson
2

Além do que Demento disse, a extensão da aleatoriedade no algoritmo de geração de número aleatório é a questão principal. A seguir, alguns desenhos que podem tornar o RNG fraco:
Seqüências ocultas
Suponha que sejam as poucas seqüências anteriores de caracteres geradas: (Apenas um exemplo, para o uso prático, é usado um intervalo maior)

lwjVJA
Ls3Ajg
xpKr+A
XleXYg
9hyCzA
jeFuNg
JaZZoA

Inicialmente, você não pode observar nenhum padrão nas gerações, mas alterando-os para a codificação Base64 e depois para hexadecimal, obtemos o seguinte:

9708D524
2ECDC08E
C692ABF8
5E579762
F61C82CC
8DE16E36
25A659A0

Agora, se subtrairmos cada número do anterior, obtemos o seguinte:

FF97C4EB6A
97C4EB6A
FF97C4EB6A
97C4EB6A
FF97C4EB6A
FF97C4EB6A

Isso indica que o algoritmo apenas adiciona 0x97C4EB6A ao valor anterior, trunca o resultado em um número de 32 bits e o Base64 codifica os dados.
O acima é um exemplo básico. Os algoritmos e sistemas de ML de hoje são capazes o suficiente para aprender e prever padrões mais complexos.

Dependência de tempo
Alguns algoritmos RNG usam o tempo como a principal entrada para gerar números aleatórios, especialmente aqueles criados pelos próprios desenvolvedores para serem usados ​​em seu aplicativo.

Sempre que são implementados algoritmos RNG fracos que parecem ser estocásticos, eles podem ser extrapolados para frente ou para trás com precisão perfeita , caso um conjunto de dados suficiente esteja disponível.

Ugnes
fonte
Você acabou de me demonstrou uma concepção em minha própria mente entre quantidade e sua comunicação ser um método de determinar um padrão eu sabia que was'nt distante do de minha intuição :)
Bobs
Mas ainda implora uma questão inseparável de a aleatoriedade ser um "produto" desconectado da racionalidade quando tentamos descrevê-la a partir de uma função da linguagem que usamos, derivada de uma humildade em reter o processo evolutivo e buscou o método de manter a sanidade humana. ri muito.
Bobs 29/09
A aleatoriedade ou sua percepção é uma disjunção entre a realidade e a percepção humana e, por causa de sua disjunção, apenas um resíduo da percepção sensível decide a imagem de todos e de todos nós todos observamos e se soma à aleatoriedade comunicável por causa da disjunção intelectual nos fatores concêntricos humanos na distribuição conceitual.
Bobs
Como você pode sempre analisar algo sem uma base para começar a sua análise de se o seu tentando analisar aleatoriedade então certamente é a partir de uma base de certeza ego entérico lol
Bobs
A pseudo-aleatoriedade é uma propriedade das pessoas de plástico que se disfarçam de qualidades reais e reais, pelas quais elas têm um desprezo supérfluo e uma preocupação profana ou humana. A determinação leva à fé, a uma certeza da ocupação e a uma comunicação saudável do produto de uma vida boa, não obstante os problemas de um equilíbrio de dificuldades.
Bobs