Randomisierte Algorithmen

Randomisierte Algorithmen

Definition

Randomisierte Algorithmen sind Algorithmen, die bei Entscheidungen über das weitere Vorgehen oder bei der Wahl der Parameter Zufallszahlen benutzen.

Anschaulich gesprochen, wersucht man bei randomisierten Algorithmen, einen Teil der Lösung zu raten. Auf den ersten Blick würde man vermuten, dass dabei nicht viel Sinnvolles herauskommen kann. Diese Kapitel wird jedoch zeigen, dass man durch geschicktes Raten tatsächlich zu sehr eleganten Algorithmen gelangen kann.

Grundsätzlich unterscheidet man zwei Arten von randomisierten Algorithmen:

Las Vegas - Algorithmen

Das Ergebnis des Algorithmus ist immer korrekt, und die Berechnung erfolgt mit hoher Wahrscheinlichkeit effizient.

Monte Carlo - Algorithmen

Die Berechnung ist immer effizient, und das Ergebnis ist mit hoher Wahrscheinlichkeit korrekt.

Las Vegas-Algorithmen verwendet man, wenn der Algorithmus im ungünstigen Fall eine schlechte Laufzeit hat, und der ungünstige Fall kann durch die Randomisierung sehr unwahrscheinlich gemacht werden. Wir haben in der Vorlesung schon mehrere Las Vegas-Algorithmen kennen gelernt:

• Quick Sort mit zufälliger Wahl des Pivot-Elements: Die Randomisierung verhindert, dass das Array immer wieder in Subarrays von sehr unterschiedlicher Größe aufgeteilt wird.
• Treap mit zufälligen Prioritäten: Die Randomisierung verhindert, dass der Baum schlecht balanciert ist.
• Universelles Hashing: Die zufällige Wahl der Hashfunktion verhindert, dass ein Angreifer eine Schlüsselmenge mit sehr vielen Kollisionen konstruieren kann.
• Erzeugung einer perfekten Hashfunktion: Durch die Randomisierung entsteht mit nach wenigen Versuchen ein zyklenfreier Graph, der zur Definition der Hashfunktion geeignet ist.

Monte Carlo-Algorithmen verwendet man dagegen, wenn kein effizienter deterministischer Algorithmus für ein Problem bekannt ist. Man gibt sich dann damit zufrieden, dass der randomisierte Algorithmus die korrekte Lösung nur mit hoher Wahrscheinlichkeit findet, wenn dies dafür sehr effizient geschieht. Bei manchen Problemen ist auch dies unerreichbar - man muss dann bereits zufrieden sein, wenn der Algorithmus mit hoher Wahrscheinlichkeit eine sehr gute Näherungslösung findet. Beliebte Anwendungsgebiete für Monte Carlo-Algorithmen sind beispielsweise

• Randomisierte Primzahl-Tests: Moderne Verschlüsselungsverfahren benötigen zahlreiche Primzahlen, aber exakte Primzahltests sind teuer. Der Miller-Rabin-Test findet effizient Zahlen, die mit sehr hoher Wahrscheinlichkeit tatsächlich Primzahlen sind.
• Randomisiertes Testen: Wie jeder Test kann auch eine randomisierter Test nicht die Abwesenheit von Programmierfehlern garantieren, aber man kann durch die Randomisierung viel mehr Testfälle generieren und erhöht so die Erfolgswarscheinlichkeit. Wir haben als Beispiel dafür den Algorithmus von Freivald behandelt.
• Lösung schwieriger Optimierungsprobleme: Wir zeigen unten, dass ein randomisierter Algorithmus effizient eine Lösung für das 2-SAT-Problem aus dem vorherigen Kapitel findet (für k-SAT mit <math>k \ge 3</math> liefert der Algorithmus immer noch mit einer gewissen Wahrscheinlichkeit das richtige Ergebnis, ist aber nicht mehr effizient). Einen effizienten Approximationsalgorithmus für des Problem des Handelsreisenden behandlen wir im Kapitel NP-Vollständigkeit. Weitere wichtige Beispiele für diesen Bereich sind simulated annealing und das Markov-Chain-Monte-Carlo-Verfahren.
• Robuste Statistik: Eine Grundaufgabe der Statistik ist das Anpassen (Fitten) von Modellen an gemessene Werte. Wenn die Messungen jedoch "Ausreißer" (einige völlig falsche Werte) enthalten, geht die Anpassung schief. Wir beschreiben unten den RANSAC-Algorithmus, der die Ausreißer identifizieren und beim Modellfitten ignorieren kann.

Anwendung: Lösen des K-SAT-Problems

   geg.: logischer Ausdruck in K-CNF (n Variablen, m Klauseln, k Variablen pro Klausel)

   <math>\underbrace {\underbrace {\left(x_1 \vee x_3 \vee...\right)}_{k\; Variablen} \wedge \left( x_2 \vee x_4 \vee...\right)}_{m\;Klauseln}</math>

   for i in range (trials):    #Anzahl der Versuche
        #Bestimme eine Zufallsbelegung des <math>\{ x_i \}</math>:
        for j in range (steps):
              if <math>\{ x_i \}</math> erfüllt alle Klauseln: return <math>\{ x_i \}</math>
              #wähle zufällig eine Klausel, die nicht erfüllt ist und negiere zufällig eine der Variablen in dieser Klausel 
              (die Klausel ist jetzt erfüllt)
   return None

Eigenschaft: falls <math>k>2</math> : steps *trials <math>\in O\left(\Alpha^n \right) \Alpha >1</math>

z.B. <math>k=3</math> steps=3*n, trials=<math>\left(\frac{4}3\right)^n</math>

aber: bei <math>k=2</math> sind im Mittel nur steps=<math>O\left(n^2\right)</math> nötig, trials=<math>O\left(1\right)</math>

---

-Zufallsbelegung hat <math>t\leq n</math> richtige Variablen (im Mittel <math>t\approx \frac {n} 2</math>)

Negieren einer Variable ändert t um 1, u.Z. <math>t\rightarrow t+1</math> mit Wahrscheinlichkeit <math>\frac 1 2</math> ::(für beliebiges k: <math>\frac 1 k</math>)

<math>t\rightarrow t-1</math> mit Wahrscheinlichkeit <math>\frac 1 2</math> ::(für beliebiges k: <math>\frac {k-1} k</math>)

-Wieviele Schritte braucht man im Mittel, um zu einer Lösung mit t Richtigen zu kommen?

      <math>S\left(t\right)=\frac 1 2 S\left(t-1\right) + \frac 1 2 S\left(t+1\right) +1</math>
      
      <math>S\left(n\right)=0</math>    #Abbruchbedingung der Schleife
      
      <math>S\left(0\right) = S\left( 1\right) + 1 \Rightarrow S\left(t\right) = n^2-t^2</math>

      Probe: 

      <math>
      \begin{align} 
            S\left(n\right) & = n^2-n^2=0 \\
                 
            S\left(0\right) &= n^2-0^2 \\
             
                  &= S\left(1\right)+1 \\
             
                  &= n^2-1^2+1 \\
             
                  &= n^2 \\
                
             S\left(t\right) &= \frac 1 2 \left(n^2-\left(t-1\right)^2\right) + \frac 1 2 \left(n^2-\left(t+1\right)^2\right)+1 \\
             
                  &= \frac 1 2 n^2-\frac 1 2 \left( t^2-2t+1\right) + \frac 1 2 n^2-\frac 1 2 \left(t^2+2t+1\right) + 1 \\
             
                  &= n^2-t^2
      \end{align}</math>

Das ist das Random Walk Problem

Im ungünstigsten Fall (t=0) werden im Mittel <math>n^2</math> Schritte benötigt, um durch random walk nach t=n zu gelangen.

2. RANSAC-ALGORITHMUS (Random Sample Consensus)

Aufgabe: gegeben: Datenpunkte

gesucht: Modell, das die Datenpunkte erklärt

Messpunkte:

     übliche Lösung: Methode der kleinsten Quadrate
     
     <math>\min_{a,b} 	\sum_{i} \left(a x_i + b + y_i\right)^2</math>
     
     Schulmathematik:      <math>Minimum\stackrel{\wedge}{=}Ableitung=0</math>

Lineares Gleichungssystem

<math>\frac{d}{da}\sum{i} \left(ax_i+b-y_i\right)^2=\sum{i} \frac{d}{da} \left[ax_i+b-y_i\right)^2</math>

<math>f\left(g\left(x\right)\right)</math>

<math>f\left(x\right)=x^2</math>

<math>y\left(a\right)=ax_i+b-y_i</math>

<math>=\sum_{i}2\left(ax_i+b-y_i\right)\frac{d}{da} \underbrace {ax_i+b-y_i}_{x_i}</math>

<math>\underline {=2\sum_{i}\left(ax_i+b-y_i\right)x_i\stackrel{!}{=}0}</math>

<math>a\sum_{i}{x_i}^2+b\sum_{i}x_i=\sum_{i}x_iy_i</math>

<math>a\sum_{i}x_i+b\sum_{i}1=\sum_{i}y_i</math>

<math>\frac{d}{db}\sum_{i}\left(ax_i+b-y_i\right)^2=2\sum_{i}\left(ax_i+b-y_i\right)*1</math>

---

Problem: <math>\epsilon  %</math> der Datenpunkte sind Outlier

<math>\Longrightarrow</math> Einfaches Anpassen des Modells an die Datenpunkte funktioniert nicht

Seien mindestens k Datenpunkte notwendig, um das Programm anpassen zu können

RANSAC-Algorithmus

     for  l in range (trials):
          wähle zufällig k Punkte aus
          passe das Modell an die k Punkte an
          zähle, wieviele Punkte in der Nähe des Modells liegen (d.h. <math>d_i < d_max</math> muss geschickt gewählt werden) 
                                          #Bsp. Geradenfinden:-wähle a,b aus zwei Punkten
                                                              -berechne: <math>|ax_i+b-y_i|=d_i</math>
                                                              -zähle Punkt i als Inlier, falls <math>d_i<d_ma</math>
     return: Modell mit höchster Zahl der Inlier

     <math>trials= \frac{log\left(1-p\right)}{log\left(1-\left(1-\epsilon\right)^k\right)}</math>  mit k=Anzahl der Datenpunkte und p=Erfolgswahrscheinlichkeit, <math>\epsilon</math>=Outlier-Anteil

Erfolgswahrscheinlichkeit: p=99%

<math>\begin{array}{|c||c|c|c|c|c|}

        Beispiel & k & \epsilon=10% & 20% & 50% & 70%\\
        \hline
        Linie\;in\;2D & 2 & 3 &5 & 17 & 49\\
        Kreis\;in\;2D & 3 & 4 & 7 & 35 & 169\\
        Ebene\;in\;3D & 8 & 9 & 26 & 1172 & 70188\\
      \end{array}</math>

Ein Spiel: Wie viel Schritte braucht man im Mittel zum Ziel?

  geg.: 5 Plätze, 2 Personen: eine Person rückt vom einem Platz zu dem enderen Platz;
        die zweite Person wirft die Münze.
        Wenn die Münze auf Kopf landet, rücke nach rechts und wenn die Münze auf Zahl landet, rücke nach links.
        <--- Zahl                                                         Kopf-->
        Kopf: /////
        Zahl: /// 

=> mit 8 Schritten bis zum Ziel

im Mittel: bei N Plätzen braucht man N² Schritte

all: mit N² Schritten um N Plätze rücken

Wie viel Schritte braucht man im Mittel zum Ziel?

        <math>S\left(N\right)=0</math>    #wenn wir uns im Stuhl Nr.1 befinden
          
        <math>S\left(i\right)=\frac 1 2 S\left(1 + S\left(i+1\right)\right) + \frac 1 2 S\left(1 + S\left(i-1\right)\right) = \frac 1 2 S\left(i+1\right) + \frac 1 2 S\left(i-1\right) +1 </math>

        <math>S\left(0\right)=1 + S\left(1\right)</math>    #bei 0.Platz

• Lösung:

        <math>S\left(i\right)= N^2 - i^2</math>

• speziell:

        <math>S\left(i\right)= N^2</math>           #wenn man am ungünstigsten Platz startet

---

Beziehung zu randomisiertem 2-SAT

     "Platz <math>i</math> ": <math>i</math> Variablen haben den richtigen Wert,  <math>\left(N-i\right)</math>  sind falsch gesetzt

     <math>S\left(\frac N 2\right)=N^2 - \left(\frac N 2\right)^2 = N^2 - \frac N 4 ^2 = \frac 3 4 N^2 </math>
     <math>S\left(\frac N 2\right)</math>     # Anfangszustand

---

Las Vegas vs. Monte Carlo

  * Las Vegas - Algorithmen
    - Ergebnis ist immer korrekt.
    - Berechnung ist mit hoher Wahrscheinlichkeit effizient (d.h. Randomisierung macht den ungünstigsten Fall unwahrscheinlich).

  * Monte Carlo - Algorithmen
    - Berechnung immer effizient.
    - Ergebnis mit hoher Wahrscheinlichkeit korrekt (falls kein effizienter Algorithmus bekannt, der immer die richtige Lösung liefert).

Las Vegas	Monte Carlo
- Erzeugen einer perfekten Hashfuktion	- Algorithmus von Freiwald(Matrizenmultiplikation)
- universelles Hashing	- RANSAC
- Quick Sort mit zufälliger Wahl des Pivot-Elements	- randomisierte K-SAT(k>=3)(Alg. von Schöning)
- Treep mit zufälligen Prioritäten	-

Zufallszahlen

- kann man nicht mit deterministischen Computern erzeugen

- aber man kann Pseudo-Zufallszahlen erzeugen, die viele Eigenschaften von echten Zufallszahlen haben

* sehr ähnlich zum Hash

    "linear Conguential Random number generator"
       <math>I_{i+1}= \left(a*I_i + c\right)\textrm{mod\ } m</math>
       <math>\begin{array}{ll}
       \mathrm{=> } & I_i \in [0, m-1]\\

       \end{array}</math>

-sorgfältige Wahl von a, c, m notwendig

Bsp. m = 2³²

a = 1664525, c = 1013904223

"quick and dirty generator"

Nachteile

• nicht zufällig genug für viele Anwendungen

Bsp. wähle Punkt in R³

<math>\begin{array}{ll}

     \mathrm{ } & p = (rand(), rand(), rand())\\

     \end{array}</math>

gibt Zahl u, v, w so, dass

<math>\begin{array}{ll}

       \mathrm{ } & u * p[0] + v * p[1] + w * p[3]\\

       \end{array}</math>

stark geclustert ist.

• Periodenlänge ist zu kurz:

spätestens nach m Schritten wiederholt sich die Folge

allgemein: falls der interne Zustand des Zufallsgenerators k bits hat, ist Periodenlänge:

<math>\begin{array}{ll}

       \mathrm{ } & Periode < 2^k\\

       \end{array}</math>

• lowbits sind weniger zufällig als die highbits

---

Mersenne Twister

bester zur Zeit bekannter Zufallszahlengenerator (ZZG)

• innere Zustand: <math>\begin{array}{ll}

       \mathrm{ } & 624*32 bit\ Integers  => 19968 bits\\
       \end{array}</math>

• Periodenlänge: <math>2^ {19937} \approx 4 * 10^{6000}</math>

• Punkte aus aufeinanderfolgende Zufallszahlen in <math>\mathbb{R}^n</math> sind gleich verteilt bis <math>\begin{array}{ll}

       \mathrm{ } & n = 623\\
       \end{array}</math>

• alle Bits sind unabhängig voneinander zufällig ("Twister")

• schnell

   class MersenneTwister:
       
       def __init__(self, seed):
           self.N = 624  # Größe des inneren Zustands festlegen
           self.i = 0    # zählt mit in welchem Zustand wir uns gerade aufhalten
           
           self.state = [0]*self.N  # Speicher für den inneren Zustand reservieren
           
           self.state[0] = seed     # initiale Zufallszahl vom Benutzer
           # den Rest des inneren Zustands mit einfachem Zufallszahlengenerator initialisieren
           for i in xrange(1, self.N):
               self.state[i] = (1812433253 * (self.state[i-1] ^ (self.state[i-1] >> 30)) + i) % 4294967296
    
       def __call__(self):
           """gibt die nächste Zufallszahl im Bereich [0, 232-1] aus"""
           N, M = self.N, 397
           
           # Zustand aktualisieren (neue Zufallszahl ausrechnen)
           i = self.i
           r = ((self.state[i] & 0x80000000) | (self.state[(i+1)%N] & 0x7FFFFFFF)) >> 1
           if self.state[(i+1)%N] & 1:
               r ^= 0x9908B0DF
           self.state[i] = self.state[(i+M)%N] ^ r
    
           # aktuelle Zufallszahl auslesen und ihre Zufälligkeit durch verwürfeln der Bits verbessern
           y = self.state[i]
           y ^=  (y >> 11)
           y ^= ((y <<  7) & 0x9D2C5680)
           y ^= ((y << 15) & 0xEFC60000)
           y ^=  (y >> 18)
           
           # Zustand weitersetzen und endgültige Zufallszahl ausgeben
           self.i = (self.i + 1) % N
           return y

geg.: Zufallszahl <math>\begin{array}{ll}

       \mathrm{ } & [0, \overbrace{2^{32}-1}^{m-1}]\\
       \end{array}</math>

ges.: Zufallszahl <math>\begin{array}{ll}

       \mathrm{ } & [0, k - 1]\\
       \end{array}</math>

naive Lösung: <math>\begin{array}{ll}

       \mathrm{ } & rand()%k\\
       \end{array}</math>  ist schlecht.

Bsp. <math>\begin{array}{ll}

       \mathrm{ } & \qquad m = 16\qquad k = 11\\
       \end{array}</math>

rand()	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
rand()%k	0	1	2	3	4	5	6	7	8	9	10	0	1	2	3	4

=> 0,...,4 kommt doppelt so häufig wie 5,...,10 "nicht zufällig"

Lösung: Zurückweisen des Rests der Zahlen (rejektion sampling)

<math>\begin{array}{ll}

       \mathrm{ } & remainder = (m - 1 - (k - 1))% k = (m - k)%k\\
       \mathrm{ } & last\ Good\ Value = m-1-remainder\\
       \end{array}</math>

 r = rand()
 while r > last.GoodValue:
       r = rand()
       return r%k

Nächstes Thema