Pourquoi l'apprentissage automatique ne reconnaît-il pas les nombres premiers?

13

Disons que nous avons une représentation vectorielle de tout entier de magnitude n, V_n

Ce vecteur est l'entrée d'un algorithme d'apprentissage automatique.

Première question: pour quel type de représentations est-il possible d'apprendre la primalité / composition de n en utilisant un réseau neuronal ou une autre cartographie ML de vecteur à bit. Ceci est purement théorique - le réseau de neurones pourrait avoir une taille illimitée.

Ignorons les représentations qui sont déjà liées aux tests de primalité telles que: la liste des facteurs n séparés de zéro, ou l'existence d'un témoin de compositivité comme dans Miller Rabin. Concentrons-nous plutôt sur les représentations dans différents radices, ou les représentations en tant que vecteurs de coefficient de polynômes (éventuellement multivariés). Ou d'autres exotiques comme cela est posé.

Deuxième question: pour quels types d'algorithmes ML, le cas échéant, l'apprentissage sera-t-il impossible quelles que soient les spécificités du vecteur de représentation? Encore une fois, laissons de côté les représentations «interdites par la trivialité» dont les exemples sont donnés ci-dessus.

La sortie de l'algorithme d'apprentissage automatique est un bit unique, 0 pour le premier, 1 pour le composite.

Le titre de cette question reflète mon évaluation selon laquelle le consensus pour la question 1 est «inconnu» et le consensus pour la question 2 est «probablement la plupart des algorithmes ML». Je pose la question car je n'en sais pas plus et j'espère que quelqu'un pourra montrer la voie.

S'il y en a une, la principale motivation de cette question est: existe-t-il une limite «théorique de l'information» à la structure de l'ensemble des nombres premiers qui peuvent être capturés dans un réseau neuronal d'une taille particulière? Comme je ne suis pas expert dans ce type de terminologie, permettez-moi de reformuler cette idée plusieurs fois et de voir si j'obtiens une approximation Monte-Carlo du concept: quelle est la complexité algorithmique de l'ensemble des nombres premiers? Le fait que les nombres premiers soient diophantiens récursivement énumérables (et peut satisfaire une grande équation diophantienne particulière ) peut-il être utilisé pour capturer la même structure dans un réseau neuronal avec les entrées et sorties décrites ci-dessus.

Cris Stringfellow
la source
12
Du point de vue théorique, votre problème n'est pas bien défini. Quelles sont les entrées de l'algorithme d'apprentissage automatique? Comment sont-ils générés? Que sait l'algorithme avant sa tâche d'apprentissage?
Lev Reyzin
3
Je ne pense pas que ce soit une bonne question dans sa forme actuelle pour ce site.
Kaveh
4
Ça peut. Mais dans l'apprentissage automatique, nous voulons minimiser les erreurs lors du test de l'ensemble de données. Maintenant, si vous vous entraînez sur vous pourriez finir par apprendre f ( n ) = n 2 - n + 41 et qui fonctionne parfaitement pour des nombres inférieurs à 41 . Mais après cela, ses performances ne sont pas bonnes. Les gens l'ont essayé (manuellement :-)) et jusqu'à présent sans grand succès . En ML, nous essayons de trouver des modèles, mais qu'en est-il s'il n'y en a pas? [1,20]f(n)=n2n+4141
Pratik Deoghare
1
Vous semblez vous demander s'il existe un algorithme qui, étant donné une fonction de séquences finies de nombres naturels aux prédicats sur les nombres naturels, peut correctement produire un prédicat de primalité donné une séquence de nombres premiers, sous réserve de contraintes supplémentaires sur l'algorithme. Articuler davantage votre restriction n'est pas anodin, si possible. Si vous essayez de le préciser, vous verrez peut-être.
Vijay D
1
Sff(n)nnS

Réponses:

-8

c'est une vieille question / problème avec de très nombreuses connexions en profondeur dans la théorie des nombres, les mathématiques, le TCS et en particulier la vérification automatisée des théorèmes. [5]

la vieille question, presque ancienne, est "existe-t-il une formule pour calculer les nombres premiers"

la réponse est, oui, dans un sens, il existe différents algorithmes pour le calculer.

la fonction zêta de Riemann peut être réorientée comme un "algorithme" pour trouver des nombres premiers.

Il me semble possible qu'une approche basée sur un algorithme génétique GA puisse réussir un jour sur ce problème avec une configuration ingénieuse, c'est-à-dire que les GA sont la technologie connue la plus proche qui a le plus de chances de réussir. [6] [7] C'est le problème de trouver un algorithme à partir d'un ensemble fini d'exemples, c'est-à-dire l'apprentissage automatique, qui est très similaire à l'induction mathématique. cependant, il ne semble pas y avoir beaucoup de recherches sur l'application des AG dans la théorie des nombres jusqu'à présent.

le plus proche de cela dans la littérature existante semble être par exemple [8] qui discute du développement de la conjecture principale jumelle d'une manière automatisée c'est-à-dire "la fabrication de conjectures automatisée".

une autre approche est un programme qui possède un grand ensemble de tableaux de fonctions standard, ainsi qu'une logique de conversion sophistiquée, pour reconnaître les séquences entières standard. il s'agit d'une nouvelle fonction intégrée à Mathematica appelée findsequence[3]

elle est également reliée à un domaine relativement nouveau appelé «mathématiques expérimentales» [9,10] ou à ce que l'on appelle également la recherche «empirique» dans le TCS.

un autre point fondamental à souligner ici est que la séquence des nombres premiers n'est pas "lisse", très irrégulière, chaotique, fractale et les algorithmes d'apprentissage machine standard sont historiquement basés sur l'optimisation numérique et la minimisation des erreurs (par exemple descente de gradient), et ne le font pas bien sur la recherche de réponses exactes à des problèmes discrets. mais encore une fois, les AG peuvent réussir et il a été prouvé qu'elles réussissent dans ce domaine / régime.

[1] est - il une équation mathématique pour le n - ième premier, math.se

[2] formule pour les nombres premiers , wikipedia

[3] fonction de recherche de wolfram

[4] fonction riemann zeta

[5] principaux succès de la preuve automatisée du théorème

[6] applications des algorithmes génétiques dans le monde réel

[7] application d'algorithmes génétiques à la preuve automatisée de thm par Wang

[8] Fabrication de conjectures automatisée en théorie des nombres en utilisant HR, Otter et Maple colton

[9] Existe-t-il des applications des mathématiques expérimentales au TCS?

[10] Une liste de lecture sur l'algorithmique expérimentale

vzn
la source
1
C'est une excellente réponse. Je ne sais pas si le site sera d'accord, mais c'était ce que je cherchais. Un tas de nouvelles directions pour explorer et vieillir les connexions anciennes. Merci, j'apprécie vraiment ça. En particulier les AG. En outre, vous lisez entre les lignes et généralisé de l'apprentissage automatique à la «formule pour les nombres premiers». C'est très utile merci.
Cris Stringfellow
11
@Cris, il n'y a presque rien dans cette réponse qui concerne l'apprentissage automatique. D'après votre commentaire sur la réponse d'Aryeh, il me semble que vous n'êtes pas familier avec l'apprentissage automatique (puis-je demander où avez-vous vu une machine apprendre un algorithme comme le test de primalité à partir d'une liste d'exemples?)
Kaveh
6
GA peut «apprendre» un algorithme de test de primalité dans le même sens où le singe infini proverbial tapera un jour les œuvres complètes de Shakespeare
Sasho Nikolov
@sasho, cela n'a pas encore été démontré mais (oui, à mon humble avis) ce n'est probablement pas dû à des limitations de la technologie mais plutôt à un manque de tentative. Koza a démontré les algorithmes complexes de «résolution / apprentissage» des GA pour les jeux vidéo, par exemple pacman (via des arbres lisp de primitives), ainsi que la construction de circuits utilisant des sous-composants. n'est-ce pas au moins aussi difficile que de trouver des nombres premiers? la vraie question est, quels types de primitives le système aurait-il, et comment peuvent-ils être primitifs et toujours trouver la solution?
vzn
19

La question est, à mon avis, assez vague et implique un malentendu, donc cette réponse tente uniquement de fournir le bon vocabulaire et de vous orienter dans la bonne direction.

Il existe deux domaines de l'informatique qui étudient directement ces problèmes. Inférence inductive et théorie de l'apprentissage informatique . Les deux domaines sont étroitement liés et la distinction est sociale et esthétique plutôt que formelle.

AP(A)AAFP(A)

f:NA

iNf(i)=T, for some T in F.

Ainsi, une présentation de données positives est une énumération du concept cible, souvent avec quelques conditions d'équité supplémentaires. Vous pouvez de même demander une présentation qui étiquette les mots selon qu'ils sont dans la langue ou non. Encore une fois, vous pouvez ajouter des conditions supplémentaires pour garantir l'équité et la couverture de tous les mots.

RepMRepL(M)

p:NRepL(p(i))f(j)jikjkL(p(j))=L(p(j+1))

Permettez-moi de souligner qu'il ne s'agit que d'une formalisation spécifique d'un modèle d'apprentissage spécifique. Mais c'est l'étape zéro avant de pouvoir commencer à poser et à étudier les questions qui vous intéressent. Le modèle d'apprentissage peut être enrichi en permettant l'interaction entre l'apprenant et l'enseignant. Plutôt que des familles arbitraires de langues, nous pouvons considérer des langues très spécifiques, voire des représentations spécifiques (comme les fonctions booléennes monotones). Il y a une différence entre ce que vous pouvez apprendre dans chaque modèle et la complexité de l'apprentissage. Voici un exemple d'un résultat d'impossibilité fondamental.

Gold [1967] Aucune famille de langues contenant toutes les langues finies et au moins une langue superfinie ne peut être apprise passivement à partir de données positives seules.

Il faut être très très prudent dans l'interprétation de ce résultat. Par exemple, Dana Angluin a montré dans les années 80 que

k

k

Angluin [1987] Les langues régulières peuvent être apprises par un enseignant qui répond aux requêtes d'équivalence et fournit des contre-exemples. L'algorithme est polynomial dans l'ensemble des états du DFA minimal et de la longueur du contre-exemple maximal.

C'est un résultat assez fort et positif et a récemment trouvé plusieurs applications. Cependant, comme toujours, les détails sont importants, comme le suggère déjà le titre de l'article ci-dessous.

Le problème de DFA cohérent minimum ne peut pas être approximé dans et polynôme , Pitt et Warmuth, 1989.

Maintenant, vous vous demandez peut-être en quoi cela est-il pertinent pour votre question? À quoi ma réponse est que l'espace de conception pour une définition mathématique de votre problème est très grand et le point spécifique que vous choisissez dans cet espace va affecter le type de réponses que vous obtiendrez. Ce qui précède n'est pas censé être une enquête complète sur la façon de formaliser le problème d'apprentissage. Il s'agit simplement de montrer la direction que vous voudrez peut-être étudier. Toutes les références et les résultats que je cite sont extrêmement datés, et le domaine a beaucoup fait depuis lors. Il existe des manuels de base que vous pouvez consulter pour obtenir le contexte suffisant pour formuler votre question de manière précise et déterminer si la réponse que vous recherchez existe déjà.

Vijay D
la source
C'est super @Vijay D, merci pour cela.
Cris Stringfellow
C'est une question mal formée. Ma réponse (et commentaires) ci-dessous montre pourquoi. ML peut reconnaître des nombres premiers, mais pas dans un sens pratique, cela prendrait trop de temps. Telle est la nature de cette bestiole particulière.
Dominic Cerisano
12

Le succès d'un algorithme d'apprentissage dépend essentiellement de la représentation. Comment présentez-vous l'entrée de l'algorithme? Dans un cas extrême, supposons que vous présentiez les nombres comme des séquences de facteurs premiers - dans ce cas, l'apprentissage est assez trivial. Dans un autre extrême, envisagez de représenter les nombres sous forme de chaînes binaires. Tous les algorithmes d'apprentissage standard que je connais échoueraient ici. En voici une qui fonctionnerait: trouver la plus petite machine de Turing qui accepte tous les exemples positifs et rejette tous les négatifs. [Exercice: prouver qu'il s'agit d'un apprenant universel.] Un problème avec cela est que la tâche n'est pas calculable par Turing. Pour mettre les choses en perspective, pouvez- vous apprendre à reconnaître la primauté basée uniquement sur la représentation binaire?

Aryeh
la source
Je peux apprendre à reconnaître la primalité basée sur la représentation binaire si j'apprends, disons, l'algorithme de Miller Rabin. Mais je veux aller au-delà de ce genre de choses et voir s'il y a autre chose. Pourquoi la tâche que vous mentionnez n'est-elle pas calculable?
Cris Stringfellow
6
Je ne comprends pas comment on peut parler d'un problème d'apprentissage ici sans se référer, par exemple, à la classe cible de fonctions.
Lev Reyzin
1
Lev a raison, bien sûr - mais je pensais qu'une discussion sur les classes de fonction dépasserait la portée de la question ... :)
Aryeh
-1

Ce problème fait partie de la recherche moderne: étant donné les données d'entrée et de sortie, trouvez l'algorithme le plus simple qui produit la sortie de l'entrée. Les réseaux RNN sont Turing-complet, donc théoriquement par SGD sans fin, vous pouvez vous retrouver dans RNN qui est équivalent à ce code:

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);
    }
}

sur cet ensemble de données: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... etc

Le problème est que nous n'avons aucune théorie pratiquement fiable sur la convergence SGD ni aucune estimation du temps requis pour la convergence ou la profondeur du réseau neuronal. Mais les dernières recherches montrent que des problèmes similaires peuvent être résolus:

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

utilisez google scholar pour rechercher des mots clés ...

Stepan Yakovenko
la source
-3

L'apprentissage automatique est soumis aux lois de la complexité informatique.

Le problème de factorisation principal se situe dans la classe de complexité NP, peut-être même NP-difficile (non prouvé).

C'est pourquoi la détection des nombres premiers est l'un des problèmes les plus difficiles de l'apprentissage automatique, et pourrait ne pas être possible du tout avec cette approche.

Les ordinateurs quantiques (QC) peuvent le faire en temps polynomial, mais Shor est un déterminisme de force brute, pas un apprentissage automatique.

Il est possible qu'un algorithme d'apprentissage QC basé sur Shor soit une approche. Je ne fais que cogner les rochers en suggérant cela.

Dominic Cerisano
la source
1
PRIMES est en P, donc je ne dirais pas que «détecter les nombres premiers» est parmi les problèmes les plus difficiles en ML - ou dans toute autre branche de l'informatique, d'ailleurs. «Il s'agit de représentation» frappe beaucoup plus près de chez nous, comme expliqué dans ma réponse et les commentaires ci-dessous.
Aryeh
Excusez-moi, P ≠ NP! PRIMES est co-NP, et pour le résoudre en P, il faudrait actuellement un algorithme galactique totalement inadapté à aucun paradigme informatique - en particulier l'apprentissage automatique, peu importe comment vous le représentez. Dans un sens pratique, c'est NP, et peut-être NP-dur, merci yoo.
Dominic Cerisano
1
@Birkensocks, vous semblez avoir confondu les tests de primauté avec l'affacturage. "PRIMES is in P" est en fait le nom de l'article qui a d'abord fourni un algorithme polynomial pour vérifier la primalité, en.wikipedia.org/wiki/AKS_primality_test . Notez également que l'affacturage est en NP et co-NP, donc très peu susceptible d'être NP-difficile, voir par exemple, blog.computationalcomplexity.org/2002/09/…
Rahul Savani
Oui, je pense que j'ai déjà dit ça ...
Dominic Cerisano