Warum kann maschinelles Lernen Primzahlen nicht erkennen?

13

Angenommen, wir haben eine Vektordarstellung einer beliebigen ganzen Zahl der Größe n, V_n

Dieser Vektor ist die Eingabe für einen maschinellen Lernalgorithmus.

Erste Frage: Für welche Art von Darstellungen ist es möglich, die Primalität / Zusammensetzung von n unter Verwendung eines neuronalen Netzwerks oder einer anderen Vektor-zu-Bit-ML-Abbildung zu lernen. Dies ist rein theoretisch - das neuronale Netz könnte möglicherweise unbegrenzt groß sein.

Lassen Sie uns Darstellungen ignorieren, die sich bereits auf Primärtests beziehen, wie z. B .: die durch Null getrennte Liste der Faktoren von n oder die Existenz eines zusammengesetzten Zeugen wie in Miller Rabin. Konzentrieren wir uns stattdessen auf Darstellungen in verschiedenen Radices oder Darstellungen als Koeffizientenvektoren von (möglicherweise multivariaten) Polynomen. Oder andere exotische wie gesetzt.

Zweite Frage: Für welche Arten von ML-Algorithmen wird dies, wenn überhaupt, unmöglich sein, unabhängig von den Besonderheiten des Darstellungsvektors? Lassen wir noch einmal die Darstellungen "Verboten durch Trivialität" weg, für die oben Beispiele angeführt sind.

Die Ausgabe des Algorithmus für maschinelles Lernen ist ein einzelnes Bit, 0 für Primzahl, 1 für Composite.

Der Titel dieser Frage spiegelt meine Einschätzung wider, dass der Konsens für Frage 1 "unbekannt" und der Konsens für Frage 2 "wahrscheinlich die meisten ML-Algorithmen" ist. Ich frage dies, da ich nicht mehr als das weiß und ich hoffe, dass jemand den Weg weisen kann.

Wenn es eine gibt, lautet die Hauptmotivation für diese Frage: Gibt es eine informationstheoretische Grenze für die Struktur der Primzahlen, die in einem neuronalen Netzwerk einer bestimmten Größe erfasst werden können? Da ich kein Experte in dieser Art von Terminologie bin, lassen Sie mich diese Idee ein paar Mal umformulieren und sehen, ob ich eine Monte-Carlo-Annäherung an das Konzept erhalte: Wie komplex ist die algorithmische Komplexität der Menge von Primzahlen? Kann die Tatsache, dass die Primzahlen rekursiv diophantinisch sind (und eine bestimmte große diophantinische Gleichung erfüllen ), verwendet werden, um dieselbe Struktur in einem neuronalen Netzwerk mit den oben beschriebenen Ein- und Ausgängen einzufangen?

Cris Stringfellow
quelle
12
Aus theoretischer Sicht ist Ihr Problem nicht genau definiert. Was sind die Eingaben für den maschinellen Lernalgorithmus? Wie entstehen sie? Was weiß der Algorithmus vor seiner Lernaufgabe?
Lev Reyzin
3
Ich denke nicht, dass dies eine gute Frage in der aktuellen Form für diese Site ist.
Kaveh
4
Es kann. Beim maschinellen Lernen möchten wir jedoch Fehler beim Testen des Datensatzes minimieren. Wenn Sie nun mit trainieren , lernen Sie möglicherweise f ( n ) = n 2 - n + 41 und das funktioniert perfekt für Zahlen unter 41 . Aber danach ist seine Leistung nicht gut. Die Leute haben dies versucht (manuell :-)) und bisher ohne großen Erfolg . In ML versuchen wir, Muster zu finden, aber was ist, wenn es kein Muster gibt? [1,20]f(n)=n2n+4141
Pratik Deoghare
1
Sie scheinen zu fragen, ob es einen Algorithmus gibt, der eine Funktion von endlichen Folgen natürlicher Zahlen bis hin zu Prädikaten auf natürlichen Zahlen korrekt ausgeben kann, wenn eine Folge von Primzahlen angegeben wird, was zusätzlichen Einschränkungen des Algorithmus unterliegt. Die weitere Formulierung Ihrer Einschränkung ist, wenn überhaupt möglich, nicht trivial. Wenn Sie versuchen, es genau zu machen, werden Sie vielleicht sehen.
Vijay D
1
Eine einfache Antwort, da es schwierig ist, den Suchraum der gesuchten Primzahlfunktion f zu approximieren (das heißt, f ( n ) gibt 1 zurück, wenn n eine Primzahl ist, und ansonsten 0 für jedes n ). In Bezug auf @PratikDeoghare Kommentar ist es schwierig, ein Muster in S zu finden . Sff(n)nnS
AJed

Antworten:

-8

Dies ist eine alte Frage / ein altes Problem mit vielen, vielen Zusammenhängen, die tief in die Zahlentheorie, Mathematik, TCS und insbesondere in die Prüfung automatisierter Theoreme eingehen. [5]

Die alte, altertümliche Frage lautet: "Gibt es eine Formel für die Berechnung von Primzahlen?"

Die Antwort ist, ja, in gewissem Sinne gibt es verschiedene Algorithmen , um es zu berechnen.

Die Riemannsche Zetafunktion kann als "Algorithmus" neu ausgerichtet werden, um Primzahlen zu finden.

Ich halte es für möglich, dass ein GA-Ansatz mit genetischem Algorithmus eines Tages mit einem ausgeklügelten Setup erfolgreich sein könnte, dh GAs sind die am nächsten bekannte Technologie mit den größten Erfolgschancen. [6] [7] Es ist das Problem, einen Algorithmus aus einer endlichen Menge von Beispielen zu finden, dh maschinelles Lernen, das der mathematischen Induktion sehr ähnlich ist. Es scheint jedoch noch nicht viel Forschung zur Anwendung von GAs in der Zahlentheorie zu geben.

das nächstliegende in der vorhandenen Literatur scheint zB [8] zu sein, das die automatisierte Entwicklung der Twin-Prime-Vermutung, dh die "automatisierte Vermutung", diskutiert.

Ein anderer Ansatz ist ein Programm, das eine große Anzahl von Tabellen mit Standardfunktionen sowie eine ausgeklügelte Konvertierungslogik zum Erkennen von ganzzahligen Standardsequenzen enthält. Dies ist eine neue in Mathematica eingebaute Funktion namens findsequence[3].

Es ist auch mit einem relativ neuen Gebiet verbunden, das als "experimentelle Mathematik" [9, 10] oder als "empirische" Forschung in der TCS bezeichnet wird.

Ein weiterer wichtiger Punkt ist, dass die Sequenz der Primzahlen nicht "glatt", sehr unregelmäßig, chaotisch, fraktal ist und Standardalgorithmen für maschinelles Lernen historisch auf numerischer Optimierung und Minimierung von Fehlern (z. B. Gradientenabstieg) basieren und dies nicht tun gut auf genaue Antworten auf diskrete Probleme zu finden. Aber auch hier können GAs erfolgreich sein und es wurde gezeigt, dass sie in diesem Bereich / Regime erfolgreich sind.

[1] gibt es eine mathematische Gleichung für die n-te Primzahl math.se

[2] Formel für Primzahlen , Wikipedia

[3] Wolfram-Findsequenzfunktion

[4] Riemann-Zeta-Funktion

[5] Top-Erfolge der automatisierten Theoremprüfung

[6] Anwendungen genetischer Algorithmen in der realen Welt

[7] Anwendung genetischer Algorithmen auf automatisierte Thm-Prüfungen von Wang

[8] Automatisierte Vermutung in der Zahlentheorie mit HR, Otter und Maple Colton

[9] Gibt es Anwendungen der experimentellen Mathematik in TCS?

[10] Eine Leseliste zur experimentellen Algorithmik

vzn
quelle
1
Das ist eine großartige Antwort. Ich bin mir nicht sicher, ob die Seite zustimmt, aber es war genau das, wonach ich gesucht habe. Eine Reihe neuer Wege, um alte Verbindungen zu erkunden und zu altern. Danke, weiß das wirklich zu schätzen. Besonders GAs. Außerdem lesen Sie zwischen den Zeilen und verallgemeinern sie vom maschinellen Lernen bis zur Formel für Primzahlen. Das ist sehr hilfreich, danke.
Cris Stringfellow
11
@Cris, in dieser Antwort steht fast nichts über maschinelles Lernen. Aus Ihrem Kommentar zu Aryehs Antwort geht hervor, dass Sie mit maschinellem Lernen nicht vertraut sind (darf ich fragen, wo Sie gesehen haben, wie eine Maschine aus einer Liste von Beispielen einen Algorithmus wie Primalitätstests lernt?)
Kaveh,
6
GA kann einen Primalitätstest-Algorithmus in demselben Sinne "lernen", in dem der sprichwörtliche unendliche Affe eines Tages die gesamten Werke von Shakespeare
Sasho Nikolov vom
@sasho, es wurde noch nicht demonstriert, aber (ja, imho) es ist wahrscheinlich nicht auf technologische Einschränkungen zurückzuführen, sondern auf mangelnde Versuche. koza demonstrierte GAs komplexe Algorithmen zum "Lösen / Lernen" von Videospielen, z. B. Pacman (über lisp trees of primitives), und konstruierte auch Schaltkreise unter Verwendung von Unterkomponenten. ist das nicht mindestens so schwer wie das Finden von Primzahlen? Die eigentliche Frage ist, welche Arten von Primitiven das System haben würde und wie primitiv sie sein und dennoch die Lösung finden können.
vzn
19

Die Frage ist meiner Meinung nach ziemlich vage und beinhaltet einige Missverständnisse, daher versucht diese Antwort nur, das richtige Vokabular bereitzustellen und Sie in die richtige Richtung zu weisen.

Es gibt zwei Bereiche der Informatik, die solche Probleme direkt untersuchen. Induktive Inferenz und rechnergestützte Lerntheorie . Die beiden Bereiche sind sehr eng miteinander verbunden und die Unterscheidung ist eher eine soziale und eine ästhetische als eine formale.

AP(A)AAFP(A) . Sie können sich das als die Konzepte vorstellen, an denen Sie interessiert sind. Sie müssen häufig die Familie der Konzepte festlegen, die Sie interessieren, da, wie andere darauf hingewiesen haben, die Darstellung des Konzepts und die Darstellung der Daten äußerst wichtig sind.

f:NA

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

Eine Präsentation positiver Daten ist also eine Aufzählung des Zielkonzepts, häufig mit einigen zusätzlichen Fairness-Bedingungen. Sie können auch eine Präsentation anfordern, die Wörter abhängig davon beschriftet, ob sie in der Sprache sind oder nicht. Auch hier können Sie zusätzliche Bedingungen hinzufügen, um Fairness und Abdeckung aller Wörter zu gewährleisten.

RepMRepL(M)

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

Lassen Sie mich betonen, dass dies nur eine bestimmte Formalisierung eines bestimmten Lernmodells ist. Dies ist jedoch Schritt Null, bevor Sie anfangen können, Fragen zu stellen und zu studieren, an denen Sie interessiert sind. Das Lernmodell kann durch die Ermöglichung einer Interaktion zwischen dem Lernenden und dem Lehrer erweitert werden. Anstatt willkürlicher Sprachfamilien können wir sehr spezifische Sprachen oder sogar spezifische Darstellungen (wie monotone Boolesche Funktionen) berücksichtigen. Es gibt einen Unterschied zwischen dem, was Sie in jedem Modell lernen können, und der Komplexität des Lernens. Hier ist ein Beispiel für ein grundlegendes Unmöglichkeitsergebnis.

Gold [1967] Keine Sprachfamilie, die alle endlichen Sprachen und mindestens eine superendliche Sprache enthält, kann passiv nur aus positiven Daten gelernt werden.

Bei der Interpretation dieses Ergebnisses sollte man sehr vorsichtig sein. Zum Beispiel hat Dana Angluin in den 80ern gezeigt, dass

k

k

Angluin [1987] Normale Sprachen können von einem Lehrer gelernt werden, der Äquivalenzfragen beantwortet und Gegenbeispiele liefert. Der Algorithmus ist in der Menge der Zustände des minimalen DFA und der Länge des maximalen Gegenbeispiels polynomisch.

Dies ist ein ziemlich starkes und positives Ergebnis und hat in letzter Zeit mehrere Anwendungen gefunden. Die Details sind jedoch wie immer wichtig, wie der Titel des folgenden Papiers bereits andeutet.

Das minimale konsistente DFA-Problem kann innerhalb von und polynomial , Pitt und Warmuth, 1989, nicht angenähert werden .

Nun fragen Sie sich vielleicht, inwiefern dies für Ihre Frage relevant ist? Meine Antwort lautet, dass der Entwurfsraum für eine mathematische Definition Ihres Problems sehr groß ist und der spezifische Punkt, den Sie in diesem Raum auswählen, sich auf die Art der Antworten auswirkt, die Sie erhalten. Das oben Gesagte ist nicht als umfassende Übersicht über die Formalisierung des Lernproblems gedacht. Es soll nur die Richtung zeigen, die Sie untersuchen möchten. Alle Referenzen und Ergebnisse, die ich zitiere, sind extrem veraltet, und das Feld hat seitdem viel getan. Es gibt grundlegende Lehrbücher, die Sie konsultieren können, um den ausreichenden Hintergrund zu erhalten, um Ihre Frage präzise zu formulieren und festzustellen, ob die von Ihnen gesuchte Antwort bereits vorhanden ist.

Vijay D
quelle
Das ist großartig @Vijay D, danke dafür.
Cris Stringfellow
Es ist eine schlecht formulierte Frage. Meine Antwort (und Kommentare) unten zeigen, warum. ML kann Primzahlen erkennen, aber praktisch nicht, es würde zu lange dauern. So ist die Natur dieses besonderen Tieres.
Birkensocks
12

Der Erfolg eines Lernalgorithmus hängt entscheidend von der Darstellung ab. Wie präsentieren Sie die Eingabe für den Algorithmus? Nehmen wir im Extremfall an, Sie präsentieren die Zahlen als Folgen von Primfaktoren - in diesem Fall ist das Lernen ziemlich trivial. In einem anderen Extremfall sollten Sie die Zahlen als binäre Zeichenfolgen darstellen. Alle Standardlernalgorithmen, die ich kenne, würden hier versagen. Hier ist eine, die funktionieren würde: Finde die kleinste Turing-Maschine, die alle positiven Beispiele akzeptiert und alle negativen ablehnt. [Übung: Beweisen Sie, dass dies ein universeller Lerner ist.] Ein Problem dabei ist, dass die Aufgabe nicht nach Turing berechenbar ist. Können Sie, um die Dinge in die richtige Perspektive zu rücken, lernen, die Ursprünglichkeit nur anhand der Binärdarstellung zu erkennen?

Aryeh
quelle
Ich kann lernen, die Primalität anhand der binären Wiederholung zu erkennen, wenn ich beispielsweise den Miller-Rabin-Algorithmus lerne. Aber ich möchte über solche Dinge hinausgehen und nachsehen, ob es noch etwas anderes gibt. Warum ist die von Ihnen erwähnte Aufgabe nicht für Turing berechenbar?
Cris Stringfellow
6
Ich verstehe nicht, wie man hier über ein Lernproblem sprechen kann, ohne zum Beispiel auf die Zielklasse der Funktionen Bezug zu nehmen.
Lev Reyzin
1
Lev hat natürlich recht - aber ich dachte, eine Diskussion über Funktionsklassen würde den Rahmen der Frage sprengen ... :)
Aryeh
-1

Dieses Problem ist Teil der modernen Forschung: Finden Sie bei gegebenen Eingabe- und Ausgabedaten den einfachsten Algorithmus, der die Ausgabe aus der Eingabe erzeugt. RNN-Netzwerke sind vollständig, so dass Sie theoretisch durch endlose SGD in RNN enden können, das diesem Code entspricht:

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

in diesem Datensatz: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... usw

Das Problem ist, dass wir keine praktisch verlässliche Theorie zur SGD-Konvergenz und keine Schätzungen der für die Konvergenz oder die Tiefe des neuronalen Netzwerks erforderlichen Zeit haben. Neueste Untersuchungen zeigen jedoch, dass ähnliche Probleme gelöst werden können:

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

Verwenden Sie Google Scholar, um nach Stichwörtern zu suchen ...

Stepan Yakovenko
quelle
-3

Maschinelles Lernen unterliegt den Gesetzen der Rechenkomplexität.

Das Hauptfaktorisierungsproblem liegt in der NP-Komplexitätsklasse, möglicherweise sogar NP-hart (nicht bewiesen).

Aus diesem Grund gehört das Erkennen von Primzahlen zu den schwierigsten Problemen beim maschinellen Lernen und ist mit diesem Ansatz möglicherweise überhaupt nicht möglich.

Quantencomputer (QC) können dies in polynomialer Zeit tun, aber Shors ist Brute-Force-Determinismus, kein maschinelles Lernen.

Möglicherweise ist ein auf Shors basierender QC-Lernalgorithmus ein Ansatz. Ich schlage wirklich nur die Felsen zusammen, indem ich das vorschlage.

Birkensocken
quelle
1
PRIMES ist in P, also würde ich nicht sagen, dass das Erkennen von Primzahlen zu den schwierigsten Problemen in ML - oder einem anderen Bereich der Informatik - gehört. "Es geht nur um Repräsentation" kommt meiner Heimat viel näher - wie in meiner Antwort und den Kommentaren darunter erläutert.
Aryeh
Entschuldigung, P ≠ NP! PRIMES ist co-NP, und um es in P zu lösen, wäre derzeit ein galaktischer Algorithmus erforderlich, der in keinem Computerparadigma geeignet ist - insbesondere beim maschinellen Lernen, unabhängig davon, wie Sie es darstellen. In praktischer Hinsicht ist es NP und möglicherweise NP-schwer, danke.
Birkensocks
1
@Birkensocks Sie scheinen Primality-Tests mit Factoring in Konflikt gebracht zu haben. "PRIMES is in P" ist eigentlich der Name des Papiers, das als erstes einen Polynom-Zeit-Algorithmus zur Überprüfung der Primalität lieferte, en.wikipedia.org/wiki/AKS_primality_test . Beachten Sie auch, dass Factoring in NP und Co-NP erfolgt, was sehr unwahrscheinlich ist, dass es NP-schwer ist. Siehe z. B. blog.computationalcomplexity.org/2002/09/…
Rahul Savani,
Ja, ich glaube, das habe ich schon gesagt ...
Birkensocks