¿Por qué el aprendizaje automático no reconoce los números primos?

Digamos que tenemos una representación vectorial de cualquier número entero de magnitud n, V_n

Este vector es la entrada a un algoritmo de aprendizaje automático.

Primera pregunta: ¿Para qué tipo de representaciones es posible aprender la primalidad / composición de n usando una red neuronal o algún otro mapeo ML de vector a bit? Esto es puramente teórico: la red neuronal podría tener un tamaño ilimitado.

Ignoremos las representaciones que ya están relacionadas con las pruebas de primalidad como: la lista nula de factores separados de n, o la existencia de un testigo compuesto como en Miller Rabin. En cambio, centrémonos en representaciones en diferentes radios, o representaciones como vectores de coeficientes de polinomios (posiblemente multivariados). U otros exóticos como se postulan.

Segunda pregunta: ¿para qué tipos, si los hay, de algoritmo ML aprenderá esto será imposible independientemente de los detalles del vector de representación? Nuevamente, dejemos de lado las representaciones prohibidas por la trivialidad de los ejemplos que se dan arriba.

La salida del algoritmo de aprendizaje automático es un solo bit, 0 para primo, 1 para compuesto.

El título de esta pregunta refleja mi evaluación de que el consenso para la pregunta 1 es "desconocido" y el consenso para la pregunta 2 es "probablemente la mayoría de los algoritmos de ML". Estoy preguntando esto porque no sé más que esto y espero que alguien pueda señalar el camino.

La principal motivación, si hay una, de esta pregunta es: ¿existe un límite de 'información teórica' para la estructura del conjunto de números primos que pueden capturarse en una red neuronal de un tamaño particular? Como no soy experto en este tipo de terminología, permítanme reformular esta idea varias veces y ver si obtengo una aproximación de Montecarlo al concepto: ¿cuál es la complejidad algorítmica del conjunto de números primos? ¿Se puede utilizar el hecho de que los primos son diofantina enumerables recursivamente (y pueden satisfacer una ecuación de diofantina grande particular ) para capturar la misma estructura en una red neuronal con las entradas y salidas descritas anteriormente.

Esta es una vieja pregunta / problema con muchas, muchas conexiones profundas en la teoría de números, matemáticas, TCS y, en particular, la prueba de teorema automatizada. [5]

la vieja pregunta, casi antigua, es "¿existe una fórmula para calcular los números primos"

la respuesta es sí, en cierto sentido, hay varios algoritmos para calcularlo.

La función zeta de Riemann se puede reorientar como un "algoritmo" para encontrar números primos.

Me parece posible que un enfoque de algoritmo genético de GA pueda tener éxito en este problema algún día con una configuración ingeniosa, es decir, los GA son la tecnología conocida más cercana que tiene más posibilidades de éxito. [6] [7] es el problema de encontrar un algoritmo a partir de un conjunto finito de ejemplos, es decir, aprendizaje automático, que es muy similar a la inducción matemática. Sin embargo, hasta ahora no parece haber mucha investigación sobre la aplicación de GA en teoría de números.

el más cercano a esto en la literatura existente parece ser, por ejemplo, [8] que discute el desarrollo de la conjetura de primos gemelos de una manera automatizada, es decir, "elaboración de conjeturas automatizadas".

Otro enfoque es un programa que tiene un gran conjunto de tablas de funciones estándar, junto con una lógica de conversión sofisticada, para reconocer secuencias enteras estándar. Esta es una nueva función integrada en Mathematica llamada findsequence[3]

también está conectado a un campo relativamente nuevo llamado "matemática experimental" [9,10] o lo que también se llama investigación "empírica" ​​en TCS.

Otro punto básico a destacar aquí es que la secuencia de números primos no es "uniforme", los algoritmos de aprendizaje automático altamente irregulares, caóticos, fractales y estándar se basan históricamente en la optimización numérica y la minimización de errores (por ejemplo, el descenso de gradiente), y no lo hacen. bien en encontrar respuestas exactas a problemas discretos. pero nuevamente las AG pueden tener éxito y se ha demostrado que tienen éxito en esta área / régimen.

[1] ¿hay una ecuación matemática para la enésima prima, math.se

[2] fórmula para primos , wikipedia

[3] función de secuencia de búsqueda de wolfram

[4] función riemann zeta

[5] éxitos principales de la demostración automatizada de teoremas

[6] aplicaciones de algoritmos genéticos en el mundo real

[7] aplicando algoritmos genéticos a pruebas automáticas de THM por Wang

[8] Elaboración automatizada de conjeturas en teoría de números usando HR, Otter y Maple colton

[9] ¿Hay aplicaciones de matemáticas experimentales en TCS?

[10] Una lista de lectura sobre algoritmos experimentales

La pregunta es, en mi opinión, bastante vaga e implica algunos malentendidos, por lo que esta respuesta solo intenta proporcionar el vocabulario correcto y orientarlo en la dirección correcta.

Hay dos campos de la informática que estudian directamente tales problemas. Inferencia inductiva y teoría del aprendizaje computacional . Los dos campos están estrechamente relacionados y la distinción es social y estética, más que formal.

$A$$\mathcal{P}(A^*)$$A$$A$$\mathcal{F} \subseteq \mathcal{P}(A^*)$

$f: \mathbb{N} \to A^*$

Por lo tanto, una presentación de datos positivos es una enumeración del concepto de destino, a menudo con algunas condiciones adicionales de equidad. También puede solicitar una presentación que etiquete las palabras dependiendo de si están en el idioma o no. Nuevamente, puede agregar condiciones adicionales para garantizar la equidad y la cobertura de todas las palabras.

$Rep$$M$$Rep$$L(M)$

$p: \mathbb{N} \to Rep$$L(p(i))$$f(j)$$j \le i$$k$$j \ge k$$L(p(j)) = L(p(j+1))$

Permítanme enfatizar que esta es solo una formalización específica de un modelo de aprendizaje específico. Pero este es el paso cero antes de que pueda comenzar a hacer y estudiar preguntas que le interesen. El modelo de aprendizaje puede enriquecerse al permitir la interacción entre el alumno y el maestro. En lugar de familias arbitrarias de idiomas, podemos considerar lenguajes muy específicos, o incluso representaciones específicas (como funciones booleanas monótonas). Hay una diferencia entre lo que puede aprender en cada modelo y la complejidad del aprendizaje. Aquí hay un ejemplo de un resultado fundamental de imposibilidad.

Gold [1967] No hay una familia de idiomas que contenga todos los idiomas finitos y al menos un idioma superfinito se puede aprender pasivamente solo con datos positivos.

Uno debe ser muy muy cuidadoso al interpretar este resultado. Por ejemplo, Dana Angluin demostró en los años 80 que

$k$

$k$

Angluin [1987] Los idiomas regulares se pueden aprender de un maestro que responde preguntas de equivalencia y proporciona contraejemplos. El algoritmo es polinómico en el conjunto de estados del DFA mínimo y la longitud del contraejemplo máximo.

Este es un resultado bastante fuerte y positivo y recientemente ha encontrado varias aplicaciones. Sin embargo, como siempre, los detalles son importantes, como ya sugiere el título del artículo a continuación.

El problema mínimo de DFA constante no puede aproximarse dentro de polinomio , Pitt y Warmuth, 1989.

Ahora puede que se pregunte, ¿cómo es esto relevante para su pregunta? A lo que mi respuesta es que el espacio de diseño para una definición matemática de su problema es muy grande y el punto específico que elija en este espacio va a afectar el tipo de respuestas que obtendrá. Lo anterior no pretende ser una encuesta exhaustiva sobre cómo formalizar el problema de aprendizaje. Solo pretende demostrar la dirección que puede investigar. Todas las referencias y resultados que cito son extremadamente anticuados, y el campo ha hecho mucho desde entonces. Hay libros de texto básicos que puede consultar para obtener los antecedentes suficientes para formular su pregunta de manera precisa y determinar si la respuesta que busca ya existe.

El éxito de un algoritmo de aprendizaje depende críticamente de la representación. ¿Cómo presentas la entrada al algoritmo? En un caso extremo, suponga que presenta los números como secuencias de factores primos; en este caso, el aprendizaje es bastante trivial. En otro extremo, considere representar los números como cadenas binarias. Todos los algoritmos de aprendizaje estándar que conozco fallarían aquí. Aquí hay uno que funcionaría: encuentre la máquina de Turing más pequeña que acepte todos los ejemplos positivos y rechace todos los negativos. [Ejercicio: demuestre que se trata de un alumno universal.] Un problema con eso es que la tarea no es computable por Turing. Para poner las cosas en perspectiva, ¿ puedes aprender a reconocer la primalidad basada solo en la representación binaria?

Este problema es parte de la investigación moderna: dados los datos de entrada y salida, encuentra el algoritmo más simple que produce la salida de la entrada. Las redes RNN son completas de Turing, por lo que, teóricamente, con un SGD interminable puede terminar en RNN, que es equivalente a este código:

bool isPrime(int n, int d) {
    if(n<2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}

en este conjunto de datos: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... etc.

El problema es que no tenemos una teoría prácticamente confiable sobre la convergencia SGD ni ninguna estimación del tiempo requerido para la convergencia o la profundidad de la red neuronal. Pero las últimas investigaciones muestran que se pueden resolver problemas similares:

https://en.wikipedia.org/wiki/Neural_Turing_machine

https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf

use Google Scholar para buscar palabras clave ...

El aprendizaje automático está sujeto a las leyes de la complejidad informática.

El principal problema de factorización está en la clase de complejidad NP, posiblemente incluso NP-duro (no probado).

Es por eso que la detección de números primos es uno de los problemas más difíciles en el aprendizaje automático, y podría no ser posible con ese enfoque.

Las computadoras cuánticas (QC) pueden hacerlo en tiempo polinómico, pero Shor es determinismo de fuerza bruta, no aprendizaje automático.

Posiblemente un algoritmo de aprendizaje de CC basado en Shor's sea un enfoque. Realmente estoy golpeando las rocas juntas al sugerir eso.