Konnte ein neuronales Netzwerk Primzahlen erkennen?

21

Ich bin nicht auf der Suche nach einer effizienten Möglichkeit, Primzahlen zu finden (was natürlich ein gelöstes Problem ist ). Dies ist eher eine "Was-wäre-wenn" -Frage.

Theoretisch: Könnten Sie ein neuronales Netzwerk trainieren, um vorherzusagen, ob eine bestimmte Zahl n zusammengesetzt oder eine Primzahl ist? Wie würde ein solches Netzwerk aufgebaut sein?

Fullk33
quelle
1
Werfen
VividD
2
Wenn die Primzahlen einem Muster folgen und jemand zufällig ein neuronales Netzwerk mit genügend versteckten Knoten trainiert, um die Klassifizierungsgrenze zu definieren, würde es wahrscheinlich funktionieren. Wir wissen jedoch nicht, ob diese Klassifikation existiert, und selbst wenn dies der Fall ist, müssten wir die Grenze nachweisen, um zu beweisen, dass das neuronale Netzwerk tatsächlich das richtige Muster gefunden hat.
Quintumnia

Antworten:

11

Frühe Erfolge beim Testen von Primzahlen über künstliche Netzwerke werden in A Compositional Neural-Network Solution für das Testen von Primzahlen , László Egri, Thomas R. Shultz, 2006, vorgestellt . Der wissensbasierte Kaskadenkorrelations (KBCC) -Netzwerkansatz erwies sich als vielversprechend, obwohl die Praktikabilität dieses Ansatzes durch andere Algorithmen zur Erkennung von Primzahlen übertroffen wird, die normalerweise damit beginnen, das niedrigstwertige Bit zu überprüfen, die Suche sofort um die Hälfte zu reduzieren und dann zu suchen basierte andere Theoreme und Heuristiken bis . Die Arbeit wurde jedoch mit Knowledge Based Learning mit KBCC , Shultz et. al. 2006flOOr(x)

02n-1n

  1. Kann man sich die Primzahlen einfach über den Bereich von ganzen Zahlen merken?
  2. Kann es, indem es lernt, die Definition einer Primzahl zu faktorisieren und anzuwenden?
  3. Kann es durch das Erlernen eines bekannten Algorithmus?
  4. Kann es durch die Entwicklung eines eigenen Algorithmus während des Trainings?

Die direkte Antwort lautet "Ja" und wurde bereits gemäß obiger Ziffer 1 durchgeführt, jedoch durch Überanpassung und nicht durch Erlernen einer Primzahlerkennungsmethode. Wir wissen, dass das menschliche Gehirn ein neuronales Netzwerk enthält, das 2., 3. und 4. erreichen kann. Wenn also künstliche Netzwerke so weit entwickelt sind, wie es die meisten glauben, lautet die Antwort Ja für diese. Es gibt keinen Gegenbeweis, um einen von ihnen aus dem Bereich der Möglichkeiten auszuschließen, der zum Zeitpunkt der Abfassung dieser Antwort besteht.

Es ist nicht überraschend, dass Arbeiten zum Trainieren künstlicher Netzwerke zum Testen von Primzahlen durchgeführt wurden, da Primzahlen in der diskreten Mathematik, deren Anwendung auf die Kryptographie und insbesondere auf die Kryptoanalyse von Bedeutung sind. Wir können die Bedeutung der digitalen Netzwerkerkennung von Primzahlen für die Erforschung und Entwicklung intelligenter digitaler Sicherheit in Werken wie identifizieren einer ersten Studie zum Ansatz des neuronalen Netzwerks im RSA-Kryptosystem , Gc Meletius et. al., 2002 . Die Bindung der Kryptographie an die Sicherheit unserer jeweiligen Nationen ist auch der Grund, warum nicht alle aktuellen Forschungen auf diesem Gebiet öffentlich sein werden. Diejenigen von uns, die die Freigabe und Exposition haben, können nur von dem sprechen, was nicht klassifiziert ist.

Auf ziviler Ebene ist die kontinuierliche Arbeit in der sogenannten Neuheitserkennung eine wichtige Forschungsrichtung. Markos Markou und Sameer Singh nähern sich der Neuheitserkennung von der Seite der Signalverarbeitung aus , und es ist für diejenigen, die verstehen, dass künstliche Netzwerke im Wesentlichen digitale Signalprozessoren sind, die über Mehrpunkt-Selbstoptimierungsfunktionen verfügen, offensichtlich, wie sich ihre Arbeit direkt darauf auswirkt Frage. Markou und Singh schreiben: "Es gibt eine Vielzahl von Anwendungen, bei denen die Erkennung von Neuheiten äußerst wichtig ist, einschließlich Signalverarbeitung, Computer Vision, Mustererkennung, Data Mining und Robotik."

Auf der Seite der kognitiven Mathematik könnte die Entwicklung einer Mathematik der Überraschung, wie Lernen mit Überraschung: Theorie und Anwendungen (Dissertation), Mohammadjavad Faraji, 2016, die Anfänge von Ergi und Shultz fördern .

Douglas Daseeco
quelle
1

Theoretisch kann ein neuronales Netzwerk jede gegebene Funktion ( Quelle) abbilden ) .

Wenn Sie jedoch ein Netzwerk mit den Nummern 0bis trainieren N, können Sie nicht garantieren, dass das Netzwerk Nummern außerhalb dieses Bereichs korrekt klassifiziert ( n > N).

Ein solches Netzwerk wäre ein reguläres Feed-Forward-Netzwerk ( MLP ), da die Wiederkehr der Klassifizierung der gegebenen Eingabe nichts hinzufügt. Die Anzahl der Ebenen und Knoten kann nur durch Ausprobieren ermittelt werden.

Thomas W
quelle
1
Universalsätze gelten für stetige Funktionen auf kompakten Teilmengen. Prime / nicht Prime ist keine solche Funktion.
Pasaba por aqui
1
@pasabaporaqui: In diesem Fall kann die Primzahlfunktion durch eine stetige Funktion mit Peaks bei den Werten der Primzahlen gut genug approximiert werden. Die Wahrscheinlichkeit, dass die NN eine Primzahl für 6,93 ist, liegt bei 90% - das ist eindeutig Unsinn. Wenn Sie jedoch die Ein- und Ausgaben diskretisieren, ist es Ihnen egal, was die NN für Nicht-Ganzzahlen vorhersagen würde. Ich denke, diese Antwort ist im Grunde richtig.
Neil Slater
1

Ich bin Student an der Prairie View A & M University. Ich dachte, ich würde einen Kommentar abgeben, weil ich nur ein paar Wochen damit verbracht habe, ein MLPRegressor-Modell zu optimieren, um die n-te Primzahl vorherzusagen. Vor kurzem stolperte es über ein extrem niedriges Minimum, bei dem die ersten 1000 Extrapolationen außerhalb der Trainingsdaten Fehler von weniger als 0,02 Prozent ergaben. Sogar bei 300000 Primes waren es ungefähr 0,5 Prozent. Mein Modell war einfach: 10 ausgeblendete Ebenen, die für weniger als 2 Stunden auf einem einzelnen Prozessor trainiert wurden.

Für mich stellt sich die Frage: "Gibt es eine vernünftige Funktion, die die n-te Primzahl erzeugt?" Im Moment werden die Algorithmen für extreme n rechenintensiv. Sehen Sie sich die Zeitlücken zwischen den zuletzt entdeckten größten Primzahlen an. Einige von ihnen sind Jahre auseinander. Ich weiß, es wurde bewiesen, dass eine solche Funktion nicht polynomisch ist, wenn sie existiert.

Cody K
quelle
Willkommen bei AI.SE! Bitte beachten Sie, dass wir im Antwortbereich nur Antworten (im Gegensatz zu Kommentaren) zulassen. Daher habe ich Ihren Beitrag etwas verfeinert, um mich auf die Beantwortung der Frage zu konzentrieren. Eine Einführung in unsere Website finden Sie in der Tour .
Ben N
Hallo Cody, das ist noch nicht lange her. Aber ich würde gerne mit Ihnen über den Test sprechen, den Sie gemacht haben. Würdest du gerne live darüber plaudern, was du getan hast und was du wahrgenommen hast? Ich würde gerne sehen, ob es eine Möglichkeit gibt, damit weiter zu experimentieren.
Momomo
-1

ja, es ist machbar, aber bedenken Sie, dass das Problem der Faktorisierung ganzer Zahlen ein NP-Problem und ein BQP-Problem ist .

Aus diesem Grund ist es unmöglich, dass ein rein auf klassischem Rechnen basierendes neuronales Netzwerk eine Primzahl mit 100% iger Genauigkeit findet, es sei denn, P = NP.

ncomputer
quelle
Wie in der Frage erläutert, ist es kein NP-Problem, zu überprüfen, ob eine Zahl eine Primzahl ist.
Pasaba por aqui