¿Podría una red neuronal detectar primos?

21

No estoy buscando una forma eficiente de encontrar números primos (que por supuesto es un problema resuelto ). Esta es más una pregunta de "qué pasaría si".

Entonces, en teoría: ¿podría entrenar una red neuronal para predecir si un número dado n es compuesto o primo? ¿Cómo se establecería una red de este tipo?

Fullk33
fuente
1
Echa un vistazo a cs.indstate.edu/~legri/prime06.pdf
VividD
2
Si los números primos siguen un patrón y alguien simplemente entrena una red neuronal con suficientes nodos ocultos para definir el límite de clasificación, supongo que funcionaría. Sin embargo, no sabemos si esa clasificación existe e incluso si existiera, tendríamos que demostrar cuál es el límite para demostrar que la red neuronal sí encontró el patrón correcto.
quintumnia

Respuestas:

11

El éxito inicial en las pruebas de números primos a través de redes artificiales se presenta en Una solución de red neuronal compositiva para pruebas de números primos , László Egri, Thomas R. Shultz, 2006 . El enfoque de red de correlación en cascada basado en el conocimiento (KBCC) fue el más prometedor, aunque la practicidad de este enfoque se ve eclipsada por otros algoritmos de detección principales que generalmente comienzan verificando el bit menos significativo, reduciendo inmediatamente la búsqueda a la mitad y luego buscando basado en otros teoremas y heurísticas hasta . Sin embargo, el trabajo continuó conKnowledge Based Learning con KBCC, Shultz et. Alabama. 2006Floor(X)

En realidad, hay múltiples subpreguntas en esta pregunta. Primero, escribamos una versión más formal de la pregunta: "¿Puede una red artificial de algún tipo converger durante el entrenamiento a un comportamiento que pruebe con precisión si la entrada va de a 2 n - 1 , donde n es el número de bits en la representación entera, representa un número primo? "0 02norte-1norte

  1. ¿Puede simplemente memorizar los números primos en el rango de los enteros?
  2. ¿Puede aprender aprendiendo a factorizar y aplicar la definición de primo?
  3. ¿Puede aprender un algoritmo conocido?
  4. ¿Puede desarrollar un nuevo algoritmo propio durante el entrenamiento?

La respuesta directa es sí, y ya se ha hecho de acuerdo con el punto 1. anterior, pero se hizo ajustando en exceso, no aprendiendo un método de detección de números primos. Sabemos que el cerebro humano contiene una red neuronal que puede lograr 2., 3. y 4., por lo que si las redes artificiales se desarrollan en el grado que la mayoría cree que pueden ser, entonces la respuesta es sí para ellos. No existe una contra prueba para excluir a ninguno de ellos de la gama de posibilidades a partir de la redacción de esta respuesta.

No es sorprendente que se haya trabajado para entrenar redes artificiales en pruebas de números primos debido a la importancia de los números primos en matemáticas discretas, su aplicación a la criptografía y, más específicamente, al criptoanálisis. Podemos identificar la importancia de la detección de números primos en la red digital en la investigación y el desarrollo de la seguridad digital inteligente en trabajos como A First Study of the Neural Network Approach en el Criptosistema RSA , Gc Meletius et. al., 2002 . El vínculo de la criptografía con la seguridad de nuestras respectivas naciones es también la razón por la cual no toda la investigación actual en esta área será pública. Aquellos de nosotros que pueden tener autorización y exposición solo pueden hablar de lo que no está clasificado.

En el ámbito civil, el trabajo en curso en lo que se llama detección de novedades es una dirección importante de investigación. Aquellos como Markos Markou y Sameer Singh se están acercando a la detección de novedades desde el lado del procesamiento de señales , y es obvio para aquellos que entienden que las redes artificiales son esencialmente procesadores de señales digitales que tienen capacidades de autoajuste multipunto que pueden ver cómo su trabajo se aplica directamente a esto. pregunta. Markou y Singh escriben: "Hay una multitud de aplicaciones donde la detección de novedades es extremadamente importante, incluido el procesamiento de señales, la visión por computadora, el reconocimiento de patrones, la minería de datos y la robótica".

En el lado de las matemáticas cognitivas, el desarrollo de una matemática de sorpresa, como Aprender con sorpresa: teoría y aplicaciones (tesis), Mohammadjavad Faraji, 2016 puede profundizar lo que comenzaron Ergi y Shultz.

Douglas Daseeco
fuente
1

En teoría, una red neuronal puede mapear cualquier función dada ( fuente ).

Sin embargo, si entrena una red con los números 0paraN , no se puede garantizar que la red va a clasificar a los números fuera de ese rango correctamente ( n > N).

Dicha red sería una red de retroalimentación regular ( MLP ) ya que la recurrencia no agrega nada a la clasificación de la entrada dada. La cantidad de capas y nodos solo se puede encontrar a través de prueba y error.

Thomas W
fuente
1
Los teoremas universales se aplican a funciones continuas en subconjuntos compactos. Prime / not prime no es ese tipo de función.
pasaba por aqui
1
@pasabaporaqui: en este caso, la función de primidad se puede aproximar suficientemente bien mediante una función continua con picos en los valores de los números primos. Por lo tanto, el NN podría generar un 90% de posibilidades de ser primo para 6.93; eso es claramente una tontería, pero si discretiza las entradas y salidas, realmente no le importa lo que el NN predeciría para los no enteros. Creo que esta respuesta es básicamente correcta.
Neil Slater
1

Soy investigador universitario en la universidad Prairie View A&M. Pensé en comentar, porque solo pasé unas semanas ajustando un modelo MLPRegressor para predecir el enésimo número primo. Recientemente tropezó con un mínimo súper bajo, donde las primeras 1000 extrapolaciones fuera de los datos de entrenamiento produjeron un error inferior al 0,02 por ciento. Incluso a 300000 primos, tenía alrededor de .5 por ciento de descuento. Mi modelo era simple: 10 capas ocultas, entrenadas en un solo procesador por menos de 2 horas.

Para mí, surge la pregunta: "¿Existe una función razonable que produzca el enésimo número primo?" En este momento, los algoritmos se vuelven computacionalmente muy exigentes para el extremo n. Echa un vistazo a las brechas de tiempo entre los primos más grandes más recientes descubiertos. Algunos de ellos tienen años de diferencia. Sé que se ha demostrado que si existe tal función, no será polinómica.

Cody K
fuente
Bienvenido a AI.SE! Tenga en cuenta que solo permitimos respuestas (en lugar de comentarios) en la sección de respuestas, por lo que refiné un poco su publicación para centrarme en abordar la pregunta. Para una introducción a nuestro sitio, vea el recorrido .
Ben N
Hola Cody, esto no fue hace mucho tiempo. Pero me gustaría conversar contigo sobre la prueba que hiciste. ¿Estarías dispuesto a chatear en vivo sobre lo que hiciste y lo que percibiste? Me gustaría ver si existe la posibilidad de experimentar más con esto.
momomo
-1

sí, es factible, pero considere que el problema de factorización de enteros es un problema NP-algo y un problema BQP .

Debido a esto, es imposible que una red neuronal basada exclusivamente en la informática clásica encuentre el número primo con una precisión del 100%, a menos que P = NP.

ncomputadoras
fuente
Como explica la pregunta, verificar si un número es primo no es un problema de NP.
pasaba por aqui