Warum kann maschinelles Lernen Primzahlen nicht erkennen?

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?

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

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.

$A$$\mathcal{P}(A^*)$$A$$A$$\mathcal{F} \subseteq \mathcal{P}(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: \mathbb{N} \to A^*$

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.

$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))$

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.

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?

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 ...

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.