Einführung — Definition

Die Definition von Intelligenz?

Die derzeitige Definition von KI

…kann aus dieser Meldung entnommen werden:

…Already, China has one of the biggest clusters of AI scientists. It has over 800m internet users, more than any other country, which means more data on which to hone its new AI.

(The Economist 17. 3. 2018, America vs. China)

KI als Mode-Erscheinung

Das ist nicht die erste KI-Modewelle

Sachliche Grundlagen der KI

Übersicht nach Kalenderwochen

Organisatorisches

Beispiele für Aufgaben der KI

Sudoku

Lunar Lockout

Nim

Go

Übung KW14

  1. Sokoban

    • ausprobieren: z.B. https://sokoban.info/

    • formale Spezifikation

    • Eine Startkonfiguration \(s\) enthält \(f\) Felder, darauf stehen \(k\) Kisten. Geben Sie eine möglichst gute obere Schranke für die Anzahl der von \(s\) aus erreichbaren Konfigurationen an (die keine weiteren Informationen wie Form des Feldes, Lage der Kisten benutzt)

  2. Gomoku

    • Ziel: 5 in einer Reihe (waagerecht, senkrecht, diagonal)

    • (Brett und Steine wie Go, aber sonst keine Beziehung)

    • Gewinnen Sie gegen M-x gomoku?

      (gesprochen: meta x, getippt: ESC dann x)

      in Emacs (vgl. https://xkcd.com/378/ )

    • Diese KI verwendet keine Spielbaumsuche, sonder nur eine einfache Heuristik zur Stellungsbewertung.

      Suchen Sie den Quelltext. In welcher Programmiersprache?

  3. unterhalten Sie sich mit Eliza (M-x doctor).

    (Wann, von wem, ) Warum wurde dieses Programm ursprünglich geschrieben?

    Falls Sie dazu Wikipedia benutzen: welche Information aus dem Anfang des englischen Textes ist im deutschen viel weiter hinten versteckt?

Aufgaben (Diskussion in KW 15)

  1. Wolkenkratzer https://www.janko.at/Raetsel/Wolkenkratzer/index.htm

    • Lösen Sie (auf dem Papier) eine der dort als schwer bezeichneten Instanzen, beschreiben Sie das Vorgehen.

    • Geben Sie eine formale Spezifikation an.

  2. Lunar Lockout (Teil A)

    • Lösen Sie Ihre autotool-Aufgabe, beschreiben Sie das Vorgehen

    • ergänzen Sie die Spezifikation aus dem Skript

  3. Lunar Lockout (Teil B). Wir betrachten den gerichteten Graph \(G\) aller Konfigurationen (jeder Zug ist eine Kante), die von einer Startkonfiguration mit \(k\) Robotern aus erreichbar sind.

    • Ist \(G\) kreisfrei?

    • Geben Sie eine Konfiguration mit \(k \ge 4\) an, die in \(G\) keinen Vorgänger hat.

  4. Go

    • Lösen und erklären Sie eine der Aufgaben von http://www.goproblems.com/ (für 30 …20 kyu)

    • Zeigen Sie eine Beispiel-Aufgabe mit einer Treppe (engl. ladder). Was bedeutet die Existenz von Treppen für die (automatisierte) Bewertung von Spielsituationen durch lokale Mustererkennung?

Such-Aufgaben und -Verfahren

Varianten

Unterschied zu bekannten Graph-Aufgaben

z.B. single-source-shortest-paths
(kürzeste Wege von einem Knoten zu allen anderen),

gelöst durch Dijkstra-Algorithmus

Eingaben für Such-Aufgabe

Beispiele für Such-Aufgaben

Aufgabenstellung in Such-Aufgabe

Graph- und Baumsuche

Informierte Suche

Eigenschaften von Schätzfunktionen

Übungen KW 15

Hausaufgaben (für KW 16)

vgl. Serie 1 von http://www.imn.htwk-leipzig.de/~schwarz/lehre/ss17/ki/

  1. Wegsuche (Aufgabe 1.2)

    1. Tiefen- und Breitensuche

    2. Greedy- und \(A^*\)-Suche mit Manhattan-Abstand als Heuristik

    3. geben Sie eine Landkarte (Gitter mit Wänden, wie in Aufgabenstellung) sowie Start- und Zielpunkt an, so daß die Suche nach dieser Heuristik deutlich länger dauert als blinde Breitensuche.

  2. Wegsuche (vgl. Aufgabe 1.2)

    1. (1.2.4.) modellieren Sie die Kosten des Abbiegens dadurch, daß Sie in jeder Konfiguration zusätzlich auch die Blickrichtung speichern. Ein Abbiegen besteht dann aus zwei Zügen: Drehen (am Ort) und Gehen.

    2. Geben Sie eine Landkarte mit Start- und Zielpunkt sowie darauf einen Weg an, der mit Abbiegekosten optimal ist, aber mit Standardkosten nicht.

  3. Schiebefax — aber mit Feldgröße \(2\times 3\).

    Die gelöste Konfiguration ist \(\displaystyle\begin{pmatrix}1&2&3\\4&5&-\end{pmatrix}\).

    1. Aufgabe 1.1.1 für 4 Züge (statt 7)

    2. Aufgabe 1.1.2 (für die Zugfolge aus voriger Teilaufgabe)

    3. für die Startkonfiguration aus voriger Teilaufgabe und für die Heuristik Summe der Abstände: zeigen Sie jeweils die ersten 4 Schritte der Greedy-Baumsuche, der \(A^*\)-Baumsuche.

  4. Über eine Such-Aufgabe ist bekannt:

    • es gibt \(N\) von \(s\) aus erreichbare Konfigurationen

      (Z.B. für Schiebefax auf \(3\times 3\) ist \(N= 181440\)).

    • in jeder Konfiguration sind höchstens \(B\) verschiedene Züge möglich (Schiebefax: \(B=?\))

    Bestimmen Sie daraus eine möglichst große Zahl \(K\), so daß gilt: es gibt eine Konfiguration \(t\), die von \(s\) aus nicht in \(<K\) Zügen erreichbar ist.

    Hinweis: bestimmen Sie eine obere Schranke für die Anzahl der in \(<K\) Schritten erreichbaren Konfigurationen.

BFS/DFS: Vollständigkeit

BFS/DFS: Optimalität

für Einheitskosten: jede Kante hat Gewicht 1

BFS/DFS: Kosten

Invariante der informierten Suche

Eigenschaften von Heuristiken

(Gegen)beispiele

(alle für \(s=x_0\to x_1\to x_2\to x_3=t\in T\) mit Einheitskosten)

Eigenschaften der perfekten Heuristik

Monoton und zielerkennend \(\Rightarrow\) nicht überschätzend

Invariante der \(A^*\)-Suche

Nicht überschätzend \(\Rightarrow\) \(A^*\)-Baum ist vollst.

Nicht überschätzend \(\Rightarrow\) \(A^*\)-Baum ist optimal

Monotonie

Schwere Such-Aufgaben

3 Türme von Hanoi

3 Türme von Hanoi (Beweis)

Grenzen einfacher Suchverfahren

Hausaufgaben (für KW17)

  1. Das Verfahren iterierte DFS führt nacheinander für \(k= 0, 1, \dots\) eine DFS mit Tiefenschranke \(k\) durch (d.h., wenn der Keller schon \(k\) Elemente enthält, ändert Push den Zustand nicht) und hält, sobald ein Ziel erreicht wird.

    Ist das Verfahren auf endlichen Graphen vollständig? optimal?

  2. (Gegen)beispiele für Schätzfunktionen für informierte Suche auf dann live gegebenem Graphen (vgl. Vorlesung, evtl. autotool)

  3. autotool: Türme von Hanoi (Pflicht: 3 Türme, Zusatz: 4 Türme)

  4. Geben Sie eine planare Zeichnung des Übergangs-Graphen aller Hanoi-Konfigurationen für 3 Türme und 2 Scheiben an.

    Verallgemeinern Sie auf 3, 4, …Scheiben.

    Wir suchen nun eine Zugfolge von \(A^n\) nach \(C^n\) ohne Züge \(A-C\).

    Tragen Sie eine kürzeste Lösung für \(n=2\) und evtl. \(n=3\) in Ihre Zeichnung ein.

    Geben Sie eine allgemeine Lösung der Aufgabe an.

  5. (Zusatz) Besorgen Sie 5 (oder mehr) Papp- oder Holzscheiben verschiedener Größen, die man gut sehen und anfassen kann (Durchmesser zw. 10 und 30 cm), und führen Sie das Hanoi-Umstapeln konkret vor, mit Stoppuhr (Ziel: ein Zug in 1/4 Sekunde)

    • Die Scheiben liegen einfach nur übereinander. Das Auffädeln auf einen senkrechten Mittelstab raubt zu viel Zeit.

    • Der Algorithmus in der rekursiven Form ist hier ungeeignet, da man sich den Stack (der gerade noch laufenden Unterprogramme) praktisch nicht merken kann. Man muß stattdessen beim Ansehen einer Konfiguration sofort den nächsten Zug zu erkennen (D.h., die Rekursion durch eine Iteration ersetzen.) Fällt Ihnen dazu ein Verfahren ein? Beweisen Sie dessen Korrektheit.

    • Läßt sich die Aufgabe zu zweit schneller lösen? Es muß trotzdem eine korrekte Zugfolge realisiert werden, aber die beiden können sich die Arbeit (das Bestimmen und Ausführen des jeweils nächsten Zuges) geeignet teilen.

  6. (Zusatz) Lösen Sie das Rätsel in Fig. 1 im zitierten Artikel von Hearn und Demain. Vorsicht!

  7. (Zusatz) Finden oder konstruieren Sie Lunar-Lockout-Instanzen mit langer kürzester Lösung. Kann es länger dauern als:

    . A . . . . . . . . . . . . .
. . . e . . . . . . . E F . B
. . . . . . . . . . .   . . .                
D . . . . . . . . . . . . . .                
. . . . . . . . . . . . . C .

    Sie können https://gitlab.imn.htwk-leipzig.de/waldmann/ki-ss18/blob/master/search/Lockout.hs verwenden, aber für ernsthaftes Arbeiten sollte man

    • Lösungsverfahren verbessern (unlösbare Konfigurationen schnell erkennen)

    • nicht alle Startkonfigurationen erzeugen

Finite-Domain Constraints

Beispiel, Einordnung

Definition FD-CS und Lösung

Beispiel: Sudoku

Graphkantenfärbung

Lösungssuche (Spezifikation)

Lösungssuche (Realisierung)

Konsistenz von Konfigurationen

Propagation

Beispiele für Propagatoren

SAT-Kodierungen

SAT-Kodierung für das Damen-Problem

Mini/Flat-Zinc als Standard für FD-CS

Hausaufgaben (für KW 18)

  1. (autotool) ein FD-CS lösen. Eine Folge von Schritten beschreibt eine Tiefensuche bis zu einer Lösung oder dem Beweis der Unlösbarkeit. Die Schritte sind:

    • Decide <var> <wert> einen Wert festlegen und diesen Teilbaum betreten, die restlichen Belegungen ergeben eine Konfiguration im Keller

    • Arc_Consistency_Deduction eine Variable einschränken (unsere Bezeichnung war: Propagation)

    • Backtrack der aktuelle Teilbaum \(c\) ist fehlgeschlagen, hole nächste Konfiguration vom Keller

    • Solved aktuelle Konfiguration ist Lösung

    • Inconsistent es gibt keine Lösung

  2. Hochhaus-Rätsel in Minizinc

    • Ergänzen Sie die Vorlage https://gitlab.imn.htwk-leipzig.de/waldmann/ki-ss18/blob/master/fd-cs/skyline.mzn (benutzen Sie minizinc-Dokumentation)

    • lösen Sie die zitierte Beispiel-Instanz.

      Aufruf z.B. so:

      BASE=/usr/local/waldmann/opt
export PATH=$BASE/gecode/latest/bin:$BASE/libminizinc/latest/bin:$PATH
export LD_LIBRARY_PATH=$BASE/gecode/latest/lib:$BASE/libminizinc/latest/lib

mzn-fzn -f fzn-gecode skyline.mzn

    • Modellieren Sie die Variante Hochhäuser mit Parks, lösen Sie eine Instanz.

  3. Graph-Kanten-Färbung in CNF-SAT

    • Geben Sie das FD-CS (wie in VL) für \(n=5,k=3\) im DIMACS-Format an.

    • Lösen Sie mit minisat (in $BASE/minisat/latest/bin)

    • Beweisen Sie (auf dem Papier), daß die Instanz \(n=6,k=3\) nicht lösbar ist (Jede 2-Färbung der Kanten eines \(K_6\) enhält einen einfarbigen \(K_3\)).

Modellierung von 2-Personen-Spielen

Modellierung von Spielzuständen

Wert eines Spielbaums

Subtraktions-Spiele

Abspeichern von Bewertungen

Verkürzte Spielbaum-Bewertung

vollst. Bewertung i.A. nicht möglich. Verkürzen durch:

Alpha-Beta-Suche (Motivation, Spezifikation)

Alpha-Beta-Suche (Implementierung)

Computer-Schach

Ü: Heuristik für Gomoku

Ü: Heuristik für Atari-Go

Hausaufgaben für KW20

  1. autotool-Aufgabe Alpha-Beta

  2. Heuristik Gomoku (autotool)

  3. Heuristik Atari-Go (live)

    im Pool Z430: GUI zum Go-Spielen: qgo,

    dort kann auch das Programm gnugo als Gegner eingestellt werden (alles unter /usr/local/waldmann/opt/{qgo,gnugo}/latest/bin)

    eine bestimmte Startsituation vorgeben: im SGF-Editor erzeugen, abspeichern, dann unter “go engine” laden.

    Spielen Sie auf diese Weise Atari-Go gegen gnugo. (Das weiß aber nicht, daß es Atari-Go ist, also wird es nicht jede einzelne Kette verteidigen. Deswegen können Sie leicht gewinnen.)

  4. Geben Sie ein Subtraktionsspiel (d.h., eine Menge \(S\)) mit großer Periode an. (evtl. autotool, noch in Arbeit)

  5. Geben Sie ein Programm an, das aus \(S\) die Folge der Spielwerte bestimmt.

    Kurze Lösung (kann man direkt in ghci ausprobieren)

    import Data.List (transpose)
shift xs d = replicate d True ++ xs
values s = let xs = map (not . and) $ transpose $ map (shift xs ) s in xs
take 10 $ values [2, 5] -- Beispiel von der Folie, ergibt:
[False,False,True,True,False,True,True,False,False,True]

  6. …die Periodenlänge bestimmt

Kombinatorische Spieltheorie

Motivation, Definition

Welche Spiele werden hier betrachtet?

Hackenbush

Spielklassen, Gegensätze

Die disjunkte Summe von Spielen

Äquivalenz von Spielen

Die (Halb)Ordnung auf Spielen

Vereinfachung von Spielen, Domination

Reversible Optionen, Normalformen

Beispiel: Zahlen und die Größe von \(\uparrow\)

Neutrale Spiele

Der Satz von Sprague und Grundy

Die Nim-Addition

Hausaufgaben für KW 20

  1. autotool-Aufgaben zu voriger Ü-Serie (Minimax, Alpha/Beta, evtl. Gomoku-Heuristik)

  2. Status und Gewinnzüge für eine Nim-Position berechnen (Bsp: \(\{3,7,8\}\), weitere live an der Tafel)

  3. Den Spielwert einer Hackenbush-Position angeben

  4. (Zusatz) Def: ein Spiel \(G\) heißt Zahl, wenn

    • jede Option eine Zahl ist

    • und \(\neg\exists x\in G_L, y\in G_R: x\ge y\).

    Bsp: \(0, 1, -1, 1/2, 2\) sind Zahlen. \(*=\{0\mid 0\}\) ist keine Zahl.

    • Beweise: die Summe von zwei Zahlen ist eine Zahl.

    • zwei Nicht-Zahlen angeben, deren Summe eine Zahl ist.

    • Konstruiere eine Zahl \(x\) mit \(1/2 < x < 1\).

    • Finde ein/das kleinste Intervall von Zahlen \(a,b\) mit \(a < \{1\mid -1\} < b\).

  5. (Zusatz - zur Diskussion in Übung) Beweisen Sie die Behauptung:

    Wenn \(w\) der (minimax-)Wert eines Spielbaumes \(B\) ist, und \(B'\) aus \(B\) dadurch entsteht, daß der Wert eines beliebigen Blattes in \(B\) auf \(w\) geändert wird, dann ist der Wert von \(B'\) immer noch \(w\).

Wissensrepräsentation und -Verarbeitung durch Logik

Inhalt, Motivation

Regelsysteme

Beispiel für Regelsystem: CSS

Einzelheiten zur CSS-Semantik

Übungsaufgaben CSS

Regeln in Tracking-Blockern

Übungsaufgaben Tracking-Blocker

Entscheidungstabellen

Bsp. Wahrheits/Entscheidungs-Tabelle

Formel \(x\leftrightarrow (y\vee\neg z)\)

links Wahrheitswerttabelle (Ergebnisse stehen unter \(\leftrightarrow\))

rechts äquivalente Entscheidungstabelle (Regelmenge)

\[\begin{array}{ccc|cccccc} x & y & z & x & \leftrightarrow & (y & \vee & \neg & z) \\ \hline 0 & 0 & 0 & & 0 & & 1 & 1 & \\ 0 & 0 & 1 & & 1 & & 0 & 0 & \\ 0 & 1 & 0 & & 0 & & 1 & 1 & \\ 0 & 1 & 1 & & 0 & & 1 & 0 & \\ 1 & 0 & 0 & & 1 & & 1 & 1 & \\ 1 & 0 & 1 & & 0 & & 0 & 0 & \\ 1 & 1 & 0 & & 1 & & 1 & 1 & \\ 1 & 1 & 1 & & 1 & & 1 & 0 & \end{array} \qquad \begin{array}{ccc|c} x & y & z & e \\ \hline 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & * & 1 \end{array}\]

Entscheidungsbäume

Entscheidungsdiagramme (Begriff)

BDDs (Geschichte, Eigenschaften)

BDDs (Anwendungen)

Hausaufgaben für KW 21

Wählen Sie eine der Aufgaben 1 und 2.

  1. CSS

    • den lexikografischen Vergleich der CSS-Spezifiken (6.4.3) an (vorbereiteten!) Beispielen vorführen

    • den dafür relevanten Quelltext in Firefox finden und erklären

  2. Blocking mit \(\mu\)Matrix:

    • die Farben der Anzeigematrix erklären und an (vorbereiteten!) Beispielen vorführen. (Der uMatix-Logger zeigt alle Requests.)

    • den Quelltext suchen, der Regelanwendung realisiert

  3. (autotool) eine aussagenlogische Formel umformen

  4. (autotool) ein BDD konstruieren

  5. Konstruieren Sie das BDD für die Funktion

    \((x_1,\ldots,x_n)\mapsto\) genau die Hälfte der \(x_i\) sind wahr,

    zu Variablenordnung \(x_1<\ldots<x_n\), wobei \(n\) eine gerade Zahl ist, z.B. \(n=6\).

    Beschriften Sie jeden Knoten \(v\) mit der Anzahl der Modelle des Teil-BDDs, das bei \(v\) beginnt.

    Vergleichen Sie das mit der Wahrheit, d.h., bestimmen Sie die Anzahl der Modelle dieser Formel (für beliebiges \(n\)) noch auf eine andere Weise.

Resolution

Beispiel, Motivation

Aussagenlogik: Syntax und Semantik

Disjunktive Klauseln

Spezialformen von Klauseln

Semantisches Folgern

Syntaktisches Schließen (Resolvieren)

Resolution als Inferenzsystem, Korrektheit

Beispiel Inferenz-Baum

Vollständigkeit der Resolution

Illustration für Induktionsschritt

Anwendungen der Resolution

Erfüllbarkeit von Hornklauselmengen

Bsp Erfüllbarkeit Hornklauselmenge

Hausaufgaben für KW 22

  1. (autotool) eine Resolutionsableitung für die leere Klausel

  2. eine aussagenlogische Modellierung einer Rätselaufgabe, das Ableiten einer Aussage durch Resolution: Serie 3 Aufgabe 3.4 von http://www.imn.htwk-leipzig.de/~schwarz/lehre/ss17/ki/

    (Die anderen Aufgaben dieser Serie dürfen Sie sich natürlich auch anschauen.)

  3. Die Widerlegungsvollständigkeit der Resolution ist nicht die Umkehrung der Korrektheit der Resolution, denn die Aussage \(\forall M:\forall C: M\models C\Rightarrow M\vdash C\) ist nicht wahr. Begründen Sie das durch ein Gegenbeispiel.

  4. (Zusatz) Die Erfüllbarkeit eine Menge \(M\) von Krom-Klauseln ist in Polynomialzeit entscheidbar.

    Realisieren Sie den folgenden Beweisplan und führen Sie ihn an einem Beispiel vor.

    • konstruiere gerichteten Graphen \(G\)

      • Knoten \(=\) alle Literale (\(x,\neg x\) für \(x\in\textsf{Var}(M)\))

      • Knoten \(=\) alle Implikationen, die man aus den Klauseln ablesen kann (welche genau?)

    • Hilfssatz: nach Konstruktion gilt: wenn \(x\to_G^*y\), dann auch \(\neg y\to_G^* \neg x\).

    • Hilfssatz: wenn \(x\to_G^*\neg x\to_G^* x\), dann \(M\) nicht erfüllbar.

    • Konstruiere Graphen \(G'\) der starken Zusammenhangskomponenten von \(G\).

      Dann gilt: wenn eine Komponente \(C\) sowohl \(x\) als auch \(\neg x\) enthält, dann \(M\) nicht erfüllbar.

    • Falls keine Komponente mit \(x\) und \(\neg x\), dann Belegung:

      • es gibt (wenigstens) eine (noch nicht belegte) Komponente \(S\) ohne Vorgänger, eine Komponente \(S'\) ohne Nachfolger,

      • belege (alle Literale in) \(S\) mit 0, belege \(S'\) mit 1.

      • wiederhole, bis alle Komponenten belegt sind

      Beweisen Sie, daß dieser Algorithmus durchgeführt werden kann (es gibt \(S\) und \(S'\)) und daß die resultierende Belegung ein Modell ist

Prädikatenlogische Resolution

Motivation, Definition

PL: Syntax (Wiederholung)

PL: Semantik (Wiederholung)

PL: Äquivalenzen (Wiedeholung)

Bereinigte Form

Pränex-Form

Skolem-Form

Herbrand-Strukturen

Klauselform

Hornklauselmengen und Logische Progr.

PL-Resolution (Motivation, Plan)

Grund-Instantiierung

Von PL zu AL durch Grund-Instantiierung

PL-Resolution (Beispiel)

PL-Resolution (Definition, Beispiel)

Hausaufgaben für KW 23

siehe http://www.imn.htwk-leipzig.de/~schwarz/lehre/ss17/ki/ und Kap 2.5 aus U. Schöning: Logik für Informatiker

  1. KI 17 Aufgabe 5.1 (2. und 3.: erfüllbarkeitsäquivalent) (oder eine ähnliche Aufgabeninstanz) live an der Tafel

  2. KI 17 Aufgabe 5.2

  3. (bis auf Umbenennungen) alle Resolventen von:

    \(C_1=\{\neg P(x,y),\neg P(f(a),g(u,b)),Q(x,u)\}\)

    \(C_2=\{P(f(x),g(a,b)),\neg Q(f(a),b),\neg Q(a,b)\}\)

  4. (autotool) Beispiel PL-Resolution

Logische Programmierung

Wiederholung, Motivation

Lineare Resolution

Die DFS-Strategie

Substitutionen

Produkt von Substitutionen

Vergleich von Substitutionen

Das Unifikationsproblem (Definition)

Ein Algorithmus zur Unifikation

Algorithmus zur Unifikation (Eigensch.)

Beispiel f. Prolog-Programm

Datalog (Definition, Beispiel)

Datalog (Semantik)

Beispiel: Affe, Stuhl, Banane (Version 1)

Beispiel: Affe, Stuhl, Banane (Version 2)

Hausaufgaben für KW 24

Hinweise:

  1. (autotool) Aufgabe zu Unifikation

  2. Zur Implementierung des Produktes von Substitutionen https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/Prolog/Substitution.hs#L55

    1. ist das korrekt?

    2. kann man das verkürzen?

  3. Vorführen (am Computer) und erklären (an der Tafel): für das Programm

    plus(zero,Y,Y).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
times(zero,Y,zero).
times(s(X),Y,Z) :- times(X,Y,W), plus(Y,W,Z).

    1. Wie kann man mit diesem Programm subtrahieren?

    2. was passiert bei Anfrage (und dann mehrfach ;) times(X,Y,s(s(s(s(s(s(zero)))))))?

  4. Aufgabe 7.2 von http://www.imn.htwk-leipzig.de/~schwarz/lehre/ss17/ki/, zu Teil 2 (Fixpunktsemantik) siehe Datalog

Bayes-Netze

Motivation, Definition

(Wdhlg) Wahrscheinlichkeiten

(Wdhlg) Bedingte Wahrscheinlichkeit

(Wdhlg) Satz von Bayes

(Whdlg) Unabhängige Ereignisse

(Wdhlg) Diskrete Zufallsgrößen

Definition Bayes-Netz

Beispiel Bayes-Netz

Bedingte Unabhängigkeit und BN

(automatisierbare) Aufgaben zu BN

Inferenz mit BN

Einfaches Sampling für BN

Lernen von BN

Hausaufgaben für KW 25

  1. Erklären Sie https://xkcd.com/552/

  2. \(X\) und \(Y\) spielen dieses Spiel:

    • \(X\) versteckt einen Schatz in Kiste \(A,B\) oder \(C\).

    • \(Y\) zeigt auf eine Kiste \(K\).

    • \(X\) öffnet eine leere Kiste \(L\neq K\)

    • \(Y\) zeigt auf eine Kiste \(K'\) (es könnte \(K'=K\) sein)

    • wenn \(K'\) den Schatz enthält, hat \(Y\) gewonnen.

    Bestimmen Sie die Erfolgsaussichten der Strategien

    • niemals umentscheiden (d.h., immer \(K'=K\))

    • immer umentscheiden (d.h., immer \(K'\neq K\) und \(K'\neq L\))

    Wer das Resultat nicht glaubt, programmiert eine Simulation.

  3. (autotool) Aufgabe zu Bayes-Netzen

  4. (live in der Übung oder für KW 26) aus aktuellem Anlaß (und nach Russel/Norvig Kap. 14)

    Drei Mannschaften \(A,B,C\) spielen jeder gegen jeden einmal. Mögliche Ergebnisse sind Gewonnen, Unentschieden, Verloren. Jede Mannschaft hat eine fixierte, aber unbekannte Spielstärke \(\in\{0,1,2\}\). Jedes Spielresultat hängt probabilistisch von der Differenz der Spielstärken ab.

    1. Modellieren Sie das als Bayes-Netz. Setzen Sie plausible numerische Werte ein.

    2. \(A\) gewinnt gegen \(B\), \(B\) spielt gegen \(C\) unentschieden. Wie geht das Spiel \(A\) gegen \(C\) aus? (Geben Sie die bedingte Wahrscheinlichkeitsverteilung an.)

Hinweis: Bayes-Netz-Beispiele im Autotool benutzen: siehe https://gitlab.imn.htwk-leipzig.de/autotool/all0/issues/541

Statistische Textanalyse

Definition, Motivation

Quellen

Wörter und Kontexte

Die Korrelationsmatrix

Faktorisierung der PMI-Matrix

Verbessern einer Faktorisierung

Skalierung

Vereinfachte Kontextmodelle

Kann man so Texte verstehen?

Erkennen von Analogien

Warum funktioniert das?

Hausaufgaben für KW 26

  1. (die einfache Übungsaufgabe zur Wsk-Rechnung) Bei Korrekturlesen Ihrer Bachelorarbeit finden Anton 8 Fehler und Berta 9. Zwei Fehler wurden von beiden gefunden. Wieviele Fehler enthält die Arbeit? (unter der Annahme, daß Fehler zufällig verteilt sind und die Fehlersuchen unabhängig voneinander)

  2. Wie behandeln Mikolov et al. phrases (Wortgruppen)?

  3. Wie funktioniert das Lernen (Verschieben der Vektoren) in https://github.com/dav/word2vec?

  4. (evtl. autotool) Aufgabe zur angenäherten Matrix-Faktorisierung

  5. https://gitlab.imn.htwk-leipzig.de/waldmann/ki-ss18/ word-vec benutzen und verbessern

Neuronale Netze

Zusammenfassung

Geschichte, Quellen

Definition

Spezielle Formen neuronaler Netze

Modellierung von NN

Konvolutions-Netze (CNN)

Parameterbestimmung für NN

Verfahren zur Gradientenbestimmung

Automatische Differentiation (AD)

AD vorwärts und rückwärts

Diskussion (Beispiel)

Diskussion (allgemein)

Gary Marcus: Deep Learning: A Critical Appraisal, 2018,

https://arxiv.org/abs/1801.00631

The real problem lies in misunderstanding what deep learning is, and is not, good for. The technique excels

Deviations from these assumptions can cause problems. Deep learning is just a statistical technique. All statistical techniques suffer from deviation from their assumptions.

Hausaufgaben für KW 27 (optional)

  1. zu https://gitlab.imn.htwk-leipzig.de/waldmann/ki-ss18/tree/master/tiefl

    • experimentieren Sie mit verschiedenen Lernraten in learn_gradient

    • approximieren Sie durch das gegebene n0 die Funktion

      \(f:I^2\to I: (x,y)\mapsto\) wenn \(x^2+y^2\le 1\), dann 1, sonst 0;

      a) für \(I=[0,1]\) b) für \(I=[-1,1]\) (Intervalle reeler Zahlen)

Monte-Carlo-Baumsuche

Inhalt, Motivation

UCB: Exploration und Exploitation

Monte-Carlo-Baumsuche (MCTS) für Go

MCTS Beispiel-Implementierung

Alpha(Go)Zero: MCTS und CNN

Einzelheiten zu AlphaGoZero

Aktuelle Entwicklungen im Computer-Go

Zusammenfassung, Ausblick

Themen

Themen für Projekte und Abschlußarbeiten