Uma rede neural poderia detectar números primos?

21

Não estou procurando uma maneira eficiente de encontrar números primos (o que obviamente é um problema resolvido ). Esta é mais uma pergunta "e se".

Então, em teoria: você poderia treinar uma rede neural para prever se um determinado número n é ou não composto ou primo? Como essa rede seria estabelecida?

Fullk33
fonte
1
Dê uma olhada em cs.indstate.edu/~legri/prime06.pdf
VividD
2
Se os primos seguem um padrão e alguém treina uma rede neural com nós ocultos suficientes para definir o limite de classificação, suponho que funcione. No entanto, não sabemos se essa classificação existe e, mesmo que existisse, teríamos que provar qual é o limite para provar que a rede neural realmente encontrou o padrão correto.
quintumnia

Respostas:

11

O sucesso inicial no teste de números primos via redes artificiais é apresentado em Uma solução de rede neural composicional para testes de números primos , László Egri, Thomas R. Shultz, 2006 . A abordagem de rede de correlação em cascata (KBCC) baseada no conhecimento mostrou a maior promessa, embora a praticidade dessa abordagem seja ofuscada por outros algoritmos de detecção primária que geralmente começam verificando o bit menos significativo, reduzindo imediatamente a pesquisa pela metade e depois pesquisando com base em outros teoremas e heurísticas até o . No entanto, o trabalho foi continuado com a Aprendizagem Baseada em Conhecimento com a KBCC , Shultz et. al. 2006feuoor(x)

Na verdade, existem várias sub-perguntas nesta pergunta. Primeiro, vamos escrever uma versão mais formal da pergunta: "Uma rede artificial de algum tipo pode convergir durante o treinamento para um comportamento que testa com precisão se a entrada varia de a , onde é o número de bits na representação inteira, representa um número primo? "0 02n-1n

  1. Pode simplesmente memorizar os números primos no intervalo de números inteiros?
  2. Pode aprender a fatorar e aplicar a definição de primo?
  3. Pode aprender um algoritmo conhecido?
  4. Ele pode desenvolver um novo algoritmo próprio durante o treinamento?

A resposta direta é sim, e ela já foi feita de acordo com o item 1. acima, mas foi feita por excesso de ajuste, não aprendendo um método de detecção de número primo. Sabemos que o cérebro humano contém uma rede neural que pode realizar 2., 3. e 4., portanto, se as redes artificiais são desenvolvidas na medida em que elas pensam que podem ser, então a resposta é sim para elas. Não existe contraprova para excluir qualquer um deles do leque de possibilidades até a redação desta resposta.

Não é de surpreender que tenha sido feito um trabalho para treinar redes artificiais em testes de números primos, devido à importância dos números primos na matemática discreta, sua aplicação na criptografia e, mais especificamente, na análise criptográfica. Podemos identificar a importância da detecção de números primos em redes digitais na pesquisa e desenvolvimento de segurança digital inteligente em trabalhos como Um Primeiro Estudo da Abordagem de Redes Neurais no RSA Cryptosystem , Gc Meletius et. al., 2002 . O vínculo da criptografia com a segurança de nossas respectivas nações também é a razão pela qual nem toda a pesquisa atual nesta área será pública. Aqueles de nós que podem ter a autorização e a exposição só podem falar do que não está classificado.

Do lado civil, o trabalho em andamento no que é chamado de detecção de novidade é uma direção importante da pesquisa. Pessoas como Markos Markou e Sameer Singh estão se aproximando da detecção de novidades do lado do processamento de sinais , e é óbvio para aqueles que entendem que as redes artificiais são essencialmente processadores de sinais digitais com recursos de autoajuste multiponto e podem ver como o trabalho deles se aplica diretamente a isso. questão. Markou e Singh escrevem: "Existem inúmeras aplicações em que a detecção de novidades é extremamente importante, incluindo processamento de sinais, visão computacional, reconhecimento de padrões, mineração de dados e robótica".

No lado da matemática cognitiva, o desenvolvimento de uma matemática de surpresa, como Aprendendo com Surpresa: Teoria e Aplicações (tese), Mohammadjavad Faraji, 2016 pode ajudar ainda mais o que Ergi e Shultz começaram.

Douglas Daseeco
fonte
1

Em teoria, uma rede neural pode mapear qualquer função ( fonte ).

No entanto, se você treinar uma rede com os números 0para N, você não pode garantir que a rede irá classificar números fora dessa faixa corretamente ( n > N).

Essa rede seria uma rede de alimentação direta ( MLP ) regular, pois a recorrência não adiciona nada à classificação da entrada fornecida. A quantidade de camadas e nós só pode ser encontrada por tentativa e erro.

Thomas W
fonte
1
Teoremas universais se aplicam a funções contínuas em subconjuntos compactos. Prime / not prime não é esse tipo de função.
pasaba por aqui 17/08/18
1
@pasabaporaqui: Nesse caso, a função de primidez pode ser aproximada o suficiente por uma função contínua com picos nos valores dos primos. Portanto, o NN pode gerar 90% de chance de ser o principal para 6,93 - isso é claramente um absurdo, mas se você discretizou as entradas e saídas, não se importa com o que o NN preveria para não-inteiros. Eu acho que essa resposta está basicamente correta.
Neil Slater
1

Sou pesquisador de graduação na Prairie View A&M university. Pensei em comentar, porque passei algumas semanas aprimorando um modelo MLPRegressor para prever o enésimo número primo. Recentemente, tropeçou em mínimos super baixos, onde as primeiras 1000 extrapolações fora dos dados de treinamento produziram erros inferiores a 0,02%. Mesmo com 300000 números primos, houve cerca de 0,5% de desconto. Meu modelo era simples: 10 camadas ocultas, treinadas em um único processador por menos de 2 horas.

Para mim, ele levanta a pergunta: "Existe uma função razoável que produz o enésimo número primo?" No momento, os algoritmos tornam-se computacionalmente muito exigentes para n extremo. Confira os intervalos de tempo entre os maiores primos descobertos mais recentes. Alguns deles têm anos de diferença. Eu sei que ficou provado que, se essa função existir, não será polinomial.

Cody K
fonte
Bem-vindo ao AI.SE! Observe que permitimos apenas respostas (em oposição a comentários) na seção de respostas, então refinei um pouco sua postagem para focar em abordar a questão. Para uma introdução ao nosso site, consulte o tour .
Ben N
Oi Cody, isso não foi há muito tempo. Mas eu gostaria de conversar com você sobre o teste que você fez. Você gostaria de conversar ao vivo sobre o que fez e o que percebeu? Eu gostaria de ver se existe a possibilidade de experimentar ainda mais isso.
momomo 22/07
-1

sim, é viável, mas considere que o problema da fatoração de número inteiro é um problema NP-something e BQP .

por isso, é impossível que uma rede neural puramente baseada na computação clássica encontre um número primo com 100% de precisão, a menos que P = NP.

ncomputadores
fonte
Como a pergunta explica, verifique se um número é primo não é um problema de NP.
pasaba por aqui 17/08/18