Randomisierte Algorithmen: Difference between revisions

Revision as of 19:50, 12 July 2012

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)

   Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ x_i \}}
:
        for j in range (steps):
              if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ x_i \}}
 erfüllt alle Klauseln: return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>2} : steps *trials Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \in O\left(\Alpha^n \right) \Alpha >1}

z.B. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=3} steps=3*n, trials=Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{4}3\right)^n}

aber: bei Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=2} sind im Mittel nur steps=Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O\left(n^2\right)} nötig, trials=Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O\left(1\right)}

-Zufallsbelegung hat Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t\leq n} richtige Variablen (im Mittel Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t\approx \frac {n} 2} )

Negieren einer Variable ändert t um 1, u.Z. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t\rightarrow t+1} mit Wahrscheinlichkeit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac 1 2} ::(für beliebiges k: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac 1 k} )

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t\rightarrow t-1} mit Wahrscheinlichkeit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac 1 2} ::(für beliebiges k: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac {k-1} k} )

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

      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(t\right)=\frac 1 2 S\left(t-1\right) + \frac 1 2 S\left(t+1\right) +1}

      
      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(n\right)=0}
    #Abbruchbedingung der Schleife
      
      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(0\right) = S\left( 1\right) + 1 \Rightarrow S\left(t\right) = n^2-t^2}

      Probe: 

      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle         \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}}

Das ist das Random Walk Problem

Im ungünstigsten Fall (t=0) werden im Mittel Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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
     
     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min_{a,b} 	\sum_{i} \left(a x_i + b + y_i\right)^2}

     
     Schulmathematik:      Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Minimum\stackrel{\wedge}{=}Ableitung=0}

Lineares Gleichungssystem

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\left(g\left(x\right)\right)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\left(x\right)=x^2}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y\left(a\right)=ax_i+b-y_i}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle =\sum_{i}2\left(ax_i+b-y_i\right)\frac{d}{da} \underbrace {ax_i+b-y_i}_{x_i}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \underline {=2\sum_{i}\left(ax_i+b-y_i\right)x_i\stackrel{!}{=}0}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\sum_{i}{x_i}^2+b\sum_{i}x_i=\sum_{i}x_iy_i}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\sum_{i}x_i+b\sum_{i}1=\sum_{i}y_i}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon %} der Datenpunkte sind Outlier

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_i < d_max}
 muss geschickt gewählt werden) 
                                          #Bsp. Geradenfinden:-wähle a,b aus zwei Punkten
                                                              -berechne: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |ax_i+b-y_i|=d_i}

                                                              -zähle Punkt i als Inlier, falls Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_i<d_ma}

     return: Modell mit höchster Zahl der Inlier

     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle trials= \frac{log\left(1-p\right)}{log\left(1-\left(1-\epsilon\right)^k\right)}}
  mit k=Anzahl der Datenpunkte und p=Erfolgswahrscheinlichkeit, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon}
=Outlier-Anteil

Erfolgswahrscheinlichkeit: p=99%

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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?

        Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(N\right)=0}
    #wenn wir uns im Stuhl Nr.1 befinden
          
        Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 }

        Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(0\right)=1 + S\left(1\right)}
    #bei 0.Platz

Lösung:

        Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(i\right)= N^2 - i^2}

speziell:

        Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\left(i\right)= N^2}
           #wenn man am ungünstigsten Platz startet

Beziehung zu randomisiertem 2-SAT

     "Platz Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
 ": Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)modm$ 
        ${\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*32bit\ Integers=>19968bits\\\end{array}}$

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

Punkte aus aufeinanderfolgende Zufallszahlen in $\mathbb {R} ^{n}$ sind gleich verteilt bis ${\begin{array}{ll}\mathrm {} &n=623\\\end{array}}$

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
           
           # inneren Zustand mit einfachem Zufallszahlengenerator initialisieren
           self.state[0] = seed     # initiale Zufallszahl vom Benutzer
           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, 2**32-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 ${\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

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

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

${\begin{array}{ll}\mathrm {} &remainder=(m-1-(k-1))\%k=(m-k)\%k\\\mathrm {} &last\ Good\ Value=m-1-remainder\\\end{array}}$

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

Nächstes Thema

Randomisierte Algorithmen: Difference between revisions

Revision as of 19:50, 12 July 2012

Contents

1. Randomisierte Algorithmen

2. RANSAC-ALGORITHMUS (Random Sample Consensus)

Las Vegas vs. Monte Carlo

Zufallszahlen

Nachteile

Mersenne Twister

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools