Black Box Algorithmen

Hartmut KlauckUniversität FrankfurtSS 05

1.6.

Randomisierte Entscheidungsbäume Definition:

Ein randomisierter Entscheidungsbaum hat zusätzliche Knoten, an denen eine Münze geworfen wird

Ein randomisierter Entscheidungsbaum berechnet eine Funktion korrekt, wenn auf jeder Eingabe mit Wahrscheinlichkeit 2/3 das richtige Ergebnis produziert wird

Tiefe ist wie zuvor definiert, wobei Zufallsknoten nicht mitgerechnet werden

Komplexitätsmass R(f) ist Minimum der Tiefe, über alle korrekten randomisierten Entscheidungsbäume für f

Randomisierte Entscheidungsbäume Beispiel: f(x,y,z)=xÇyÇ z Randomisierter Algorithmus:

ziehe Zufallsvariable r aus {1,2,3} x,y, x,z oder y,z x,z, oder y=1: Akz. Sonst verwerfe

Tiefe 2 Fehler: 1/3

für alle Eingaben

Randomisierte Entscheidungsbäume f(x,y,z)=xÇyÇ z Randomisierter Algorithmus:

ziehe Zufallsvariable r aus {1,2,3} x,z, oder y=1: Akz. Sonst verwerfe

Randomisierung

Gibt es ein Beispiel mit einem besseren Unterschied zwischen D(f) und R(f) ?

Versuchen, iterativ die obige Idee zu nutzen

Maximale Beschleunigung

Vorher jedoch: Wieviel kann R(f) kleiner sein als D(f)? Wir zeigen: R(f)¸ bs(f)/3 Dann gilt mit D(f)· bs4(f): Theorem 11.

R(f)=(D1/4(f)) für allen totalen Booleschen Funktionen

Sogar R(f)=(D1/3(f))

Beweis:

Betrachte eine Eingabe x, mit maximaler Blocksensitivität k und Blöcken B1,…,Bk

Für jeden Block Bi muß mit Wahrscheinlichkeit 1/3 mind. eine Variable gelesen werden, sonst ist der Fehler zu gross: Fehler >2/3 ¢ ½ ist sonst unvermeidlich

Damit müssen insgesamt k/3 Fraagen gestellt werden: Erwartet für jeden Block 1/3 Frage,

Erwartungswert der Fragen insgesamt alsoi k/3

Eine effizient randomisiert berechenbare Funktion

f(x1,…,xn) sei durch eine alternierende UND-ODER Formel mit Ingrad 2 gegeben

Tiefe log n Wir wissen schon: D(f)=n

Auswertungsalgorithmus

Durchlaufe Formel von der Spitze: UND Gatter:

Wähle ein Kind zufälligWerte den Teilbaum rekursiv ausWenn 0 berechnet, setze die AusgabeSonst Werte anderen Teilbaum re. aus

ODER Gatter:analog, aber 1 statt 0

Idee: Für viele Gatter muss mit Wahrsch. ½ nur 1 Kind ausgewertet werden

Wir zeigen : n mit ¼ 0.754 Zeit reicht erwartet aus

Vereinfachung der Analyse

Machen Analyse „symmetrischer“ Betrachten Baum von NANDs Ersetze (xÆ y)Ç(aÆ b)

durch (x NAND y) NAND (a NAND b)

Vereinfachung

Ersetze so alle Gatter ausser evtl. der Wurzel durch NAND Gatter

Wurzel OR: Dann Anzahl der Level gerade, Wurzel auch NAND

Wurzel AND: Negiere Funktion, keine Auswirkung auf Komplexität

Algorithmus

Durchlaufe Formel von der Wurzel her Wähle ein zufälliges Kind Werte rekursiv das Kind aus 0 Gefunden: Akzeptiere 1 Gefunden: Werte auch anderes

Kind aus

Analyse

Klar: Algorithmus macht keinen Fehler Worst Case Anzahl Fragen ist n

Untersuchen erwartete Anzahl Fragen Wenn t<< n: Breche nach 100 n ab und rate

Ausgabe zufällig, wenn noch kein Ergebnis vorlag

Damit ist Fehlerwahrscheinlichkeit 1/100¢ 1/2

Erwartete Zeit:

ak: Erwartete Zeit für Eingaben mit f(x)=0 bei Formeltiefe k

bk: Erwartete Zeit für Eingaben mit f(x)=1 bei Formeltiefe k

ak: Beide Kinder werden ausgewertet und sind 1, alsoak=2bk-1

Erwartete Zeit:

bk: f(x)=1, also folgende Fälle Beide Kinder sind 0: eines wird ausgewertet Ein Kind ist 0: Mit Wahrscheinlichkeit ½ wird

eines, mit ½ werden beide ausgewertet bk· max[ ak-1, ½ bk-1+ ½ (ak-1+ bk-1)]

=bk-1+ ½ ak-1

Ausserdem:a0,b0=1

Lösung der Rekursion

Schreiben als Matrix:

Lösung der Rekursion

Betrachte Matrix M Norm von M: || M || =

max v: ||M v||/||v|| Maximale Streckung von Vektoren ||Mk||· ||M||k

||M||: Wurzel maximaler Eigenwert von M Mt

Oder betragsgrösster EW von M, wenn alle EW reell

Lösung der Rekursion

Behauptung : Ew sind

Damit :

Ergebnis

Theorem 12. :Es gibt eine Funktion, die mit O(n )

Fragen randomisiert, aber nur mit mind. n Fragen det. berechenbar ist

Untere Schranken

Haben bereits: R(f)¸ bs(f)/3

Systematisch?

Adversary Methoden?

Das Yao Prinzip

Betrachte Verteilung auf Eingaben in {0,1}n

Es gelte:

Betrachte randomisierten Algo Worst Case Komplexität sei c, Fehler sei

1/3 Betrachte randomisierten

Entscheidungsbaum als Verteilung auf deterministischen Bäumen Ziehe jeweils nach einem globalen

Zufallsstring

Das Yao Prinzip

r sei der Zufallsstring Dann gilt:

8 x Er [Fehler auf x mit r]· 1/3

Aber auch Ex Er [Fehler auf x mit r]· 1/3

Und: Er Ex [Fehler auf x mit r]· 1/3

Es gibt ein r mit Ex [Fehler auf x mit r]· 1/3

Das Yao Prinzip

Distributionale Komplexität:Für eine Verteilung auf den

Eingaben sei D() (f) die minimale Tiefe eines det. E-Baumes für f mit Fehler 1/3 unter

Theorem: R(f)¸ max D1/3() (f)

Das Yao Prinzip

Beweis:Obige Beobachtungen gelten für alle

und Frage: sind solche unteren Schranken

immer gut?

Das Yao Prinzip

Theorem: R(f) = max D1/3() (f)

Beweis: Gegeben sei für alle ein E-Baum mit Tiefe k und

Fehler 1/3 Zu konstruieren ist ein randomisierter E-Baum mit

Tiefe k Betrachte als Spiel:

• Spieler A wählt eine Eingabe, Spieler B einen Baum der Tiefe k

• Spieler A gewinnt 1 Euro, wenn Baum falsch auf der Eingabe, sonst gewinnt Spieler B 1 Euro

Das Yao Prinzip

Angenommen A zieht Eingabe nach ist eine Strategie von A Dann kann B mit einem festem Baum einen erwarteten

Gewinn von 2/3 machen Wie haben: Für alle (bekannten) Strategien von A gibt es

eine Strategie von B, die 2/3 gewinnt Wir wollen: Strategie von B (Verteilung auf E-Bäumen

Tiefe k), die gut ist für alle Strategien von A Haben: min über Strat. von A von max über Strat. von B

von [Payoff für Bob]¸ 2/3 Wollen: max über Strat. von Bob von min über Strat. von

A von [Payoff für Bob] ¸ 2/3

Das Yao Prinzip

Jetzt wende an:

Theorem [von Neumann]:In Nullsummenspielen ist

minmax=maxmin

Beispiel

OR:Finde eine schwierige Verteilung (0n)=1/2 (000010000)=1/2nDann ist D()(OR)¸ n/3Und R(OR)=(n)