Randomisierte Algorithmen

1. Randomisierte Algorithmen

Def.: Algorithmen, die bei Entscheidung oder bei der Wahl der Parameter Zufallszahlen benutzen

Bsp.: Lösen des K-SAT-Problems durch RA

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

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

   for i in range (trials):    #Anzahl der Versuche
        #Bestimme eine Zufallsbelegung des $\{ x_i \}$:
        for j in range (steps):
              if $\{ x_i \}$ erfüllt alle Klauseln: return $\{ x_i \}$
              #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 $k>2$ : steps *trials $\in O\left(\Alpha^n \right) \Alpha >1$

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

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

---

-Zufallsbelegung hat $t\leq n$ richtige Variablen (im Mittel $t\approx \frac {n} 2$)

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

$t\rightarrow t-1$ mit Wahrscheinlichkeit $\frac 1 2$ ::(für beliebiges k: $\frac {k-1} k$)

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

      $S\left(t\right)=\frac 1 2 S\left(t-1\right) + \frac 1 2 S\left(t+1\right) +1$
      
      $S\left(n\right)=0$    #Abbruchbedingung der Schleife
      
      $S\left(0\right) = S\left( 1\right) + 1 \Longrightarrow S\left(t\right) = n^2-t^2$

      Probe: $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)$              
             
                  $\;=n^2-t^2$

Das ist das Random Walk Problem

Im ungünstigsten Fall (t=0) werden im Mittel $n^2$ 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
     
     $\min_{a,b} 	\sum_{i} \left(a x_i + b + y_i\right)^2$
     
     Schulmathematik:      $Minimum\stackrel{\wedge}{=}Ableitung=0$

Lineares Gleichungssystem

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

$f\left(g\left(x\right)\right)$

$f\left(x\right)=x^2$

$y\left(a\right)=ax_i+b-y_i$

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

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

$a\sum_{i}{x_i}^2+b\sum_{i}x_i=\sum_{i}x_iy_i$

$a\sum_{i}x_i+b\sum_{i}1=\sum_{i}y_i$

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

---

Problem: $\epsilon %$ der Datenpunkte sind Outlier

$\Longrightarrow$ 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. $d_i < d_max$ muss geschickt gewählt werden) 
                                          #Bsp. Geradenfinden:-wähle a,b aus zwei Punkten
                                                              -berechne: $|ax_i+b-y_i|=d_i$
                                                              -zähle Punkt i als Inlier, falls $d_i<d_ma$
     return: Modell mit höchster Zahl der Inlier

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

Erfolgswahrscheinlichkeit: p=99%

$\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}$

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?

        $S\left(N\right)=0$    #wenn wir uns im Stuhl Nr.1 befinden
          
        $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$

        $S\left(0\right)=1 + S\left(1\right)$    #bei 0.Platz

• Lösung:

        $S\left(i\right)= N^2 - i^2$

• speziell:

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

---

Beziehung zu randomisiertem 2-SAT

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

     $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$
     $S\left(\frac N 2\right)$     # 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"
       $I_{i+1}= \left(a*I_i + c\right)mod m$
       $\begin{array}{ll}
        \mathrm{=> } & I_i \in [0, m-1]\\

        \end{array}$

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

$\begin{array}{ll} \mathrm{ } & p = (rand(), rand(), rand())\\ \end{array}$

gibt Zahl u, v, w so, dass

$\begin{array}{ll} \mathrm{ } & u * p[0] + v * p[1] + w * p[3]\\ \end{array}$

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:

$\begin{array}{ll} \mathrm{ } & Periode < 2^k\\ \end{array}$

• lowbits sind weniger zufällig als die highbits

---

Mersenne Twister

bester zur Zeit bekannter Zufallszahlengenerator (ZZG)

• innere Zustand: $\begin{array}{ll} \mathrm{ } & 624*32 bit\ Integers => 19968 bits\\ \end{array}$

• Periodenlänge: $2^ {19937} \approx 4 * 10^{6000}$

• Punkte aus aufeinanderfolgende Zufallszahlen in $\mathbb{R}^n$ sind gleich verteilt bis n = 623

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

• schnell

 class Random:
   def __init__(self, seed):
       self.N = 624
       self.state = [0]*624
       self.state = zufällig mit Hilfe des seeds initialisieren (einfacher ZZG)
       self.i = 0    # zählt mit in welchem Zustand wir gerade aufhalten

   def __call__(self):
       N,M = 624, 397
       i = self.i
       r = (self.state[i] & 0x80000000)|(self.state[(i+1)%N] & 0x7FFFFFFF)     # aktualisieren
       if self.state[(i+1)%N]&1:                                               # des Zustands
          r^= 0x9908B0DF
       self.state[i] = self.state[(i+1)%N]*^r

       y = self.state[i]
          self.i = (self.i + 1)%N
          # bits verwürfeln
          y ^= (y>>11)
          y ^= ((y>>7) & 0x9D2C5680)
          y ^= ((y>>15) & 0xEFC60000)
          y ^= (y>>18)
        return y

geg.: Zufallszahl $\begin{array}{ll} \mathrm{ } & [0, \overbrace{2^{32}-1}^{m-1}]\\ \end{array}$

ges.: Zufallszahl $\begin{array}{ll} \mathrm{ } & [0, k - 1]\\ \end{array}$

naive Lösung: $\begin{array}{ll} \mathrm{ } & rand()%k\\ \end{array}$ ist schlecht.

Bsp. $\begin{array}{ll} \mathrm{ } & \qquad m = 16\qquad k = 11\\ \end{array}$

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