Die Forscher sind der HinzufĂŒgung probabilistischer Prozesse zu deterministischen Maschinen einen Schritt nĂ€her gekommen
Ein langfristiges Computerproblem - Simulation eines BetrugswĂŒrfels
Hier ist eine tĂ€uschend einfache Ăbung: Ăberlegen Sie sich eine zufĂ€llige Telefonnummer. Sieben Zahlen in einer Reihe, so gewĂ€hlt, dass jede von ihnen gleich wahrscheinlich ist und Ihre Wahl der nĂ€chsten Zahl keinen Einfluss auf die Wahl der nĂ€chsten hat. Dies wird höchstwahrscheinlich bei Ihnen nicht funktionieren. Sie können mein Wort nicht dafĂŒr nehmen - Untersuchungen, die seit den 1950er Jahren durchgefĂŒhrt wurden, zeigen, dass wir aus mathematischer Sicht nicht zufĂ€llig sind, ohne es ĂŒberhaupt zu merken.
Sei nicht verÀrgert. Computer erzeugen auch keine Zufallszahlen. Sie sollten nicht - die Programme und Hardware von Computern laufen auf Boolescher Logik , nicht auf Wahrscheinlichkeiten. "Computerkultur basiert auf Determinismus", sagte Vikash MansinhkaWer betreibt ein probabilistisches Computerprojekt am MIT - und es zeigt sich auf fast jeder Ebene. "
Programmierer möchten jedoch Programme erstellen, die zufĂ€llig ausgefĂŒhrt werden - manchmal erfordern Aufgaben dies. Im Laufe der Jahre wurden ausgeklĂŒgelte Algorithmen entwickelt, die zwar keine Zufallszahlen erzeugen, aber clevere und effiziente Möglichkeiten zur Verwendung und Manipulation von ZufĂ€lligkeiten bieten. Einer der jĂŒngsten Versuche wurde von Mansinhees Gruppe am MIT unternommen, die im August auf einer internationalen KI- und Statistikkonferenz ihren FLDR- Algorithmus ( Fast Loaded Dice Roller) vorstellen wird.
In einfachen Worten, FLDR verwendet eine zufĂ€llige Sequenz, um einen BetrugswĂŒrfel (oder eine schlecht gewichtete MĂŒnze oder markierte Karten) perfekt zu simulieren. "Er zeigt, wie man einen perfekt zufĂ€lligen MĂŒnzwurf in einen verzerrten verwandelt", sagte der MathematikerPeter Birhorst von der New Orleans University. Birhorst war an dieser Studie nicht beteiligt, erachtet jedoch die dem FLDR zugrunde liegenden PrĂ€missen als âĂŒberzeugendâ.
FLDR bietet Ihnen keinen Vorteil, wenn Sie Monopoly oder an den Craps-Tischen in Las Vegas spielen. Die Entwickler sagen jedoch, dass Zufallszahlen in nativ deterministische Software oder Hardware integriert werden können. Das Einbeziehen solcher Unsicherheiten hilft Maschinen dabei, Vorhersagen eher wie menschliche Vorhersagen zu treffen und zufÀllige Ereignisse wie Klima- oder FinanzmÀrkte besser zu simulieren.
ZufĂ€lligkeit ist ein komplexeres Konzept als es sich anhört. FĂŒr jede Ziffer in einer Folge von Zufallsziffern, bei denen kein Muster erkennbar ist, ist die Wahrscheinlichkeit des Auftretens gleich. Zum Beispiel ist die Zahl Ï nicht zufĂ€llig, aber es wird angenommen, dass nach dieser Definition ihre Zahlen zufĂ€llig sind (Mathematiker nennen sie "normal"): Jede Ziffer von 0 bis 9 erscheint ungefĂ€hr gleich oft.
Und obwohl Sie bei Google "Zufallszahlengeneratoren" finden, gibt es keinen reinen Zufall. Heutige Prozessoren, Suchmaschinen und Passwortgeneratoren verwenden eine "Pseudozufalls" -Methode, die fĂŒr die meisten Aufgaben "gut genug" ist. Zahlen werden mit komplexen Formeln generiert - theoretisch kann die Kenntnis der Formel jedoch die Reihenfolge vorhersagen.
Seit mindestens 80 Jahren versuchen Wissenschaftler, echte ZufĂ€lligkeit in Maschinen einzubauen. Bis dahin wurden Zufallszahlen von alten und zuverlĂ€ssigen Assistenten genommen - sie warfen WĂŒrfel, nahmen BĂ€lle mit Zahlen aus einem gut gemischten Beutel heraus oder verwendeten andere mechanische GerĂ€te. Im Jahr 1927 untersuchte ein Statistiker die VolkszĂ€hlungsdaten und stellte eine Tabelle mit 40.000 Zufallszahlen zusammen.
Vikash Mansinkhka, Projektmanager fĂŒr probabilistisches Computing am MIT
Die frĂŒhesten Quellen fĂŒr Zufallszahlen waren physische Maschinen. Der erste Zufallszahlengenerator wurde von den britischen Statistikern Maurice George Kendall und Bernard Babington Smith erfunden, die ihn 1938 beschrieben haben. Das Auto wurde in einen dunklen Raum gestellt und dort drehte es eine Scheibe, die in 10 Sektoren unterteilt war und von 0 bis 9 nummeriert war. Wenn jemand den Knopf in unregelmĂ€Ăigen AbstĂ€nden drĂŒckte, beleuchteten kurze Neon- oder Funkenblitze die Scheibe und rissen sie aus der Dunkelheit heraus, wie es schien ein eingefrorenes Bild, in dem nur eine Zahl sichtbar war. Eine spĂ€tere Maschine, Ernie, verwendete LĂ€rm in Neonröhren. Seit 1957 wĂ€hlt sie Gewinnzahlen in der britischen Lotterie.
Auf der Suche nach wirklich zufĂ€lligen Sequenzen mussten sich Informatiker laut Birhorst spĂ€ter natĂŒrlichen PhĂ€nomenen wie Reliktstrahlung oder unvorhersehbaren Quantensystemen zuwenden. "Es gibt wirklich unvorhersehbare zufĂ€llige Prozesse in der Natur, die ausgenutzt werden können", sagte er. "Ein links oder rechts reflektierendes Elektron kann nicht im Voraus sagen, was es tun wird."
Der Zufall allein bringt Sie jedoch nicht weit. In den spÀten 1940er Jahren begannen Physiker, Zufallszahlen zu generieren, die in eine bestimmte Wahrscheinlichkeitsverteilung passen. Solche Tools - theoretische Versionen der NOS-Cubes - funktionierten in realen Situationen wie Verkehrsstaus oder chemischen Reaktionen genauer. Bis 1976 waren die Informatikpioniere Donald Knuth und Andrew Yaostellten einen Algorithmus vor, der in der Lage ist, Zufallsstichproben eines beliebigen Arrays gewichteter Ergebnisse basierend auf einer Folge von Zufallszahlen zu erstellen. "Dies ist der zeiteffizienteste Algorithmus, den Sie sich vorstellen können", sagte Fera Saad, ein Doktorand in Mansinkhkes Labor, der das FLDR leitete.
Leider, sagt Saad, macht der Algorithmus einen Kompromiss unter Informatikern bekannt: Viele schnell laufende Anwendungen verbrauchen viel Speicher, und Anwendungen, die wenig Speicher benötigen, können sehr lange dauern. Der Algorithmus von Knuth und Yao fĂ€llt in die erste Kategorie, was ihn elegant, aber fĂŒr den praktischen Gebrauch zu speicherintensiv macht.
Saad hatte jedoch im vergangenen FrĂŒhjahr einen cleveren Schachzug. Er erkannte, dass sich der Algorithmus sowohl im Speicher als auch in der Zeit als effizient herausstellt, wenn die Summe der Gewichte der WĂŒrfelziffern gleich einer Potenz von 2 ist. Stellen Sie sich vor, dass fĂŒr einen sechsseitigen WĂŒrfel die Gewichte 1, 2, 3, 4, 5 und 1 zu den Wahrscheinlichkeiten fĂŒr das Ausrollen von Zahlen von 1 bis 6 addiert werden. Das heiĂt, die Wahrscheinlichkeit fĂŒr das Ausrollen von 1 betrĂ€gt 1/16 und 2 betrĂ€gt 2/16. Infolgedessen betrĂ€gt die Summe der Gewichte 16 - oder 2 4 - und der Algorithmus erweist sich sowohl im Speicher als auch in der Zeit als effizient.
Fera Saad, Doktorandin am MIT
Angenommen, die Gewichte sind 1, 2, 3, 2, 4, 2, was 14 ergibt. Da 14 keine Potenz von 2 ist, benötigt der Knut-Yao-Algorithmus erheblich mehr Speicher. Saad erkannte, dass man zusĂ€tzliches Gewicht hinzufĂŒgen kann, so dass sich die Gewichte immer zu einer Potenz von 2 addieren. In diesem Fall können Sie ein fiktives Gesicht mit einem Gewicht von 2 und dann die Gewichte zu 16 addieren. Wenn der Algorithmus ein reales Gesicht auswĂ€hlt, wird dieser Wert aufgezeichnet. Wenn es fiktiv ist, wird der Wert verworfen und der Algorithmus startet erneut.
Dies ist der SchlĂŒssel zur EffektivitĂ€t von FLDR und macht es zu einem leistungsstarken Simulationswerkzeug. Die Menge an zusĂ€tzlichem Speicher fĂŒr zusĂ€tzliche WĂŒrfe ist im Vergleich zu den groĂen Mengen, die fĂŒr die ursprĂŒngliche Version des Algorithmus erforderlich sind, unbedeutend.
FLDR macht den Knuth-Yao-Algorithmus effizient und bietet die Möglichkeit, seinen Anwendungsbereich zu erweitern. Klimawandelsimulationen, Erntevorhersagen, Partikelsimulationen, Finanzmarktmodelle und unterirdische nukleare Explosionen hĂ€ngen alle von Zufallszahlen ab, die mit gewichteter Wahrscheinlichkeit verteilt werden. Zufallszahlen sind auch das HerzstĂŒck kryptografischer Schemata, die ĂŒber das Internet ĂŒbertragene Daten schĂŒtzen.
Laut Mansinkhka kann FLDR Forschern helfen, Wege zu finden, um Wahrscheinlichkeiten in Computerprozessoren zu integrieren. Sein Labor am MIT tut dies. Der Algorithmus kann dazu beitragen, Softwarebibliotheken und neue Prozessorarchitekturen zu verbessern, mit denen Zufallszahlen generiert und effizient verwendet werden können. Dies wĂ€re eine signifikante Ănderung gegenĂŒber den deterministischen Booleschen Maschinen, die wir gewohnt sind.
"Wir haben möglicherweise gute Chancen, ZufĂ€lligkeit in die Bausteine ââvon Software und Hardware zu integrieren", sagte er.
Siehe auch: