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$

---

pod gesucht: RANSAC

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

     *Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): trials= frac{log\left(1-p\right)}{(1-\left(1-\Epsilon\right)^k\right)}
  mit k=Anzahl der Datenpunkte und p=Erfolgswahrscheinlichkeit, $\Epsilon$=Outlier-Anteil