Fach:KI Stundenlogs

Aus StudyWiki

Inhaltsverzeichnis

1 Woche 8 (Präsenz 20.02.08)
2 Woche 9
3 Woche 10
4 Woche 11
5 Woche 12
- 5.1 Natural Language
6 Woche 14
- 6.1 Thesis von G.Reif - Problemlösen durch Suchen

[bearbeiten] Woche 8 (Präsenz 20.02.08)

[bearbeiten] Unterlagen

[bearbeiten] Prädikatenlogik Beispiel Aufgaben

 ist_grossvater(G,E):- hat_kind(K,E), ist_vater(G,K)
 sind_cousins(C1,C2):- sind_geschwister(E1,E2), hat_kind(E1,C1), hat_kind(E2,C2), not(C1=C2)

[bearbeiten] Anwendungsbeispiele der KI

Unterhaltung
OCR, Voice Recognition
Problem Extraktion
Games
Autonome Systeme (Robotik)
Automatisierte code erstellung / Validierung
Semantik erkennung
Datenauswertung

[bearbeiten] Prädikatenlogik

[bearbeiten] Quantoren

$\exists X$	Es Existiert mindestens ein X für das gilt ...
$\forall X$	Für alle X gilt ...

[bearbeiten] Junktoren

$\neg$	nicht
$\land$	und
$\lor$	oder
$\Rightarrow$	implikation - aus A folgt B
$\Leftrightarrow$	äquivalenz - A ist gleichwertig B

[bearbeiten] Aufgaben

Folgende Aufgabe ist bis Dienstag, 26.2. im Lernjournal einzutragen:

Formulieren Sie folgendes Rätsel mit der Prädikatenlogik (aus Kapitel 3.3, aus den Unterlagen)

Portia wollte sich vermählen und unterzog jeden der zahlreichen Verehrer einer Prüfung. Sie nahm einen goldenen, einen silbernen und einen bronzenen Kasten und legte in einem davon ein Bild von sich. Die Kästen trugen folgende Aufschriften:

 Gold: Das Bild ist nicht im silbernen Kasten
 Silber: Das Bild ist nicht in diesem Kasten
 Bronze: Das Bild ist in diesem Kasten

Portia erklärte einem Bewerber noch, dass von den drei Aufschriften mindestens eine wahr und mindestens eine falsch sei. Danach sollte er einen Kasten öffnen. Wenn der geöffnete Kasten das Bild enthielt, kam er in die engere Wahl. Welchen Kasten sollte der Bewerber öffnen (vorausgesetzt, er ist wirklich an einer Heirat interessiert? ;)

[bearbeiten] Lösungen

[bearbeiten] vom Lehrer

Mögliche Fakten: 1. Das Bild ist in genau einem Kasten:

Die Farbe des Kastens ist das Atom (gold, silber, bronze). Das Prädikat ist "enthält Bild".

$\forall {X,Y,Z}(enthaelt\_Bild(X) \Leftrightarrow ( \neg (enthaelt\_Bild(Y) \land \neg (enthaelt\_Bild(Z)))))$

(Die Folgerung stimmt in beide Richtungen. Es sind weitere Schlussfolgerungen möglich)

2. Untersuchung der Aussagen auf den Kästen:

Prädikat: aussage stimmt:

$aussage\_stimmt(bronze)\Leftrightarrow enthaelt\_Bild(bronze)$

$aussage\_stimmt(gold)\Leftrightarrow \neg(enthaelt\_Bild(silber))$

$aussage\_stimmt(silber)\Leftrightarrow \neg(enthaelt\_Bild(silber))$

Da die Schlussfolgerung der 2. und 3. Aussage (Gold und Silber) identisch ist, lasse ich die 3. Zeile weg.

Auch hier gilt wieder Äquivalenz, d.h. man kann in beide Richtungen folgern (muss nicht immer der Fall sein).

3. Mindestens eine Aussage wahr, eine Falsch

Mit der 2. und 3. Bedingung identisch bedeutet dies:

Genau eine Bedingung ist wahr, eine Falsch.

$aussage\_stimmt(bronze)\Leftrightarrow \neg(aussage\_stimmt(gold))$

$\neg(aussage\_stimmt(bronze))\Leftrightarrow aussage\_stimmt(gold)$

4. Umformen der Bedingungen so, dass ich die Prädikatenlogik aus 1. einsetzen kann:

$enthaelt\_Bild(bronze)\Leftrightarrow enthaelt\_Bild(silber)$

$\neg(enthaelt\_Bild(bronze))\Leftrightarrow \neg(enthaelt\_Bild(silber))$

Aus der Bedingung 1 erhalte ich keine Lösung für die Prädikatenlogik aus 1.

Mit der Bedingung 2 kann ich diese auflösen indem ich X=Gold einsetze.

Das Bild ist also im goldenen Kasten.

[bearbeiten] Lösung rac

 gt:= "text auf gold ist wahr"
 st:= "text auf silber ist wahr"
 bt:= "text auf bronze ist wahr"
 gb:= "Bild ist in gold"
 sb:= "Bild ist in silber"
 bb:= "Bild ist in bronze"
 ---
 gt->not(sb)
 st->not(sb)
 gt=st
 bt->bb
 ---
 gt=st
 gt->not(sb)
 gt->not(bt)->not(bb)
 ---
 not(bb) AND not(sb) -> gb
  
 Andere formulierung:
 (gt OR st) -> [not(sb) AND not(bb)] -> gb

Was bei dieser Lösung fehlt, ist die Nutzung von All- oder Existenzquantoren gemäss Prädikatenlogik

[bearbeiten] Woche 9

https://ssl.hsz-t.ch/moodle/file.php/45/Prolog_Einfuehrung.pdf

[bearbeiten] Prolog Grundelemente

Behauptung (weil Kleinbuchstaben): likes(calvin, hobbes).; tiger(hobbes).
Frage (weil Grossbuchstaben): likes(X, hobbes).; tiger(T).
logisch UND: likes(susie, X), likes(calvin, X).
"falls" (alle Personen mögen Hobbes): likes(X, hobbes) :- person(X).

[bearbeiten] Getting Started

http://www.amzi.com/AdventureInProlog/index.htm

[bearbeiten] Facts

pred(arg1, arg2, ... argN).
pred
- The name of the predicate
arg1, ...
- The arguments
N
- The arity
.
- The syntactic end of all Prolog clauses

[bearbeiten] Simple Queries

[bearbeiten] Compound Querries

Goals können kombiniert werden

[bearbeiten] Rules

head :- body.
head
- a predicate definition (just like a fact)
:-
- the neck symbol, sometimes read as "if"
body
- one or more goals (a query)

[bearbeiten] Arithmetic

X is <arithmetic expression>
- X is 2+2.
- X is 5*(2/4).
5<6.

 X > Y
 X < Y
 X >= Y
 X =< Y

[bearbeiten] Woche 10

[bearbeiten] Managing Data

asserta(X)
- Adds the clause X as the first clause for its predicate. Like the other I/O predicates, it always fails on backtracking and does not undo its work.
assertz(X)
- Same as asserta/1, only it adds the clause X as the last clause for its predicate.
retract(X)
- Removes the clause X from the logicbase, again with a permanent effect that is not undone on backtracking.
not(X)
- Invertiert das resultat von X

[bearbeiten] Recursion

Sample for recursion:

 is_contained_in(T1,T2):-location(T1,T2).
 is_contained_in(T1,T2):-location(X,T2),is_contained_in(T1,X).

[bearbeiten] Data Structures

anonymous variable: _
verschachteltes wissen
- location_s(object(table, blue, big, 50), kitchen).

[bearbeiten] Unification

variable & any term
- The variable will unify with and is bound to any term, including another variable.
primitive & primitive
- Two primitive terms (atoms or integers) unify only if they are identical.
structure & structure
- Two structures unify if they have the same functor and arity and if each pair of corresponding arguments unify.

 "arg1 = arg2" ist das selbe wie =(arg1,arg2)

 X=a oder 4=Y sind beides zuweisungen da ein primitiver typ und eine variable vorhanden sind
 andere art der zuweisung: location(X,Y) = location(apple, kitchen)

 X=Y verbundet X und Y sodass bei einer zuweisung von X oder Y bei beiden dieser wert dan angenommen wird (verweist intern auf den gleichen speicherbereich)

[bearbeiten] Woche 11

[bearbeiten] Lists

Listen werden in [ und ] eingeschlossen und können überall anstelle von normalen konstanten eingesetzt werden

 [apple, broccoli, refrigerator]

empty list beschreibt das nichtvorhanden sein von elementen

[]

Erstes element der liste in erste Variable und zweite Variable enthält den rest der Liste

 [X | Y]

Wird mit "," getrennt können mehrere elemente abgefragt werden

 ?- [One, Two | T] = [apple, sprouts, fridge, milk].
 One = apple
 Two = sprouts
 T = [fridge, milk]

wenn display(x) anstelle von write(x) benutzt wird, kann man die reale struktur sehen

[bearbeiten] Operators

3 Typen von Operatoren
- infix
  - Example: 3 + 4
  - op(precedence,xfx,name).
- prefix
  - Example: -7
  - op(precedence,fx,name).
- postfix
  - Example: 8 factorial
  - op(precedence,xf,name).
precedence ist zwischen 1 und 1200 und representiert das Gewicht des operators, je leichter je höher je früher kommt er zum zug

 Die wie oben definierten operatoren können nu folgendermassen in prolog geschrieben werden als facts oder fragen
 :-op(35,xfx,is_in).
 :-op(33,fx,room).
 banana is_in room kitchen.

After compile

 ? X is_in room kitchen.
 X = banana;

Operatoren sind links- oder rechts assoziativ, können aber wie in der mathe mit klammern manipuliert werden
- Infix
  - xfx non-associative
  - xfy right to left
  - yfx left to right
- Prefix
  - fx non-associative
  - fy left to right
- Postfix:
  - xf non-associative
  - yf right to left

 Wie immer kann man das ganze gut sehen wenn man mit display() herumspielt
 Bsp:
 ?- op(35,xfy,is_in).
 yes
 ?- display(key is_in desk is_in office).
 is_in(key, is_in(desk, office))

[bearbeiten] Cut

Command: !
Wird benützt um backtracking ab diesem punkt zu verhindern

[bearbeiten] Control Structures

repeat
- Wird dazu benutzt eine wiederholung einzuleiten, es wird beim backtracking wiederholt wen ein fail zurückkommt
- repeat,fail erzeugt einen endless loop

[bearbeiten] Additional info

Prolog hat eine date und eine time funktion built-in, die kann für den game timecounter verwendet werden

 datetime:-date( Dy, Mt, Yr ),time( Hr, Mn, Sc, Fr ),X = [Dy,Mt,Yr,Hr,Mn,Sc,Fr].

[bearbeiten] Woche 12

[bearbeiten] Natural Language

The DCG vocabulary is represented by simple lists.

 noun --> [dog].
 verb --> [chases].

These are translated into Prolog as difference lists.

 noun([dog|X], X).
 verb([chases|X], X).

[bearbeiten] Woche 14

[bearbeiten] Thesis von G.Reif - Problemlösen durch Suchen

Abstrakter Ablauf:

Formulierung des Problems
Suche
Ausführung

[bearbeiten] Such Algorithmen

[bearbeiten] Blinde Suche

[bearbeiten] Tiefensuche (depth-first search)

http://de.wikipedia.org/wiki/Tiefensuche

Bestimme den Knoten an dem die Suche beginnen soll
Expandiere den Knoten und speichere alle Nachfolger in einem Stack
Rufe rekursiv für jeden der Knoten in dem Stack DFS (depth first search oder Tiefensuche) auf
1. Falls der Stack leer sein sollte, tue nichts
2. Falls das gesuchte Element gefunden worden sein sollte, brich die Suche ab und liefere ein Ergebnis

[bearbeiten] Breitensuche (breadth-first search)

http://de.wikipedia.org/wiki/Breitensuche

Bestimme den Knoten, an dem die Suche beginnen soll, und speichere ihn in einer Warteschlange ab.
Entnimm einen Knoten vom Beginn der Warteschlange und markiere ihn.
1. Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere "gefunden" zurück.
2. Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens, die sich noch nicht in der Warteschlange befinden, ans Ende der Warteschlange an.
Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere "nicht gefunden" zurück.
Wiederhole ab Schritt 2.

[bearbeiten] Nichtdeterministische Suche

Erzeuge einen Pfad, der nur aus dem Start-Node besteht und schreibe ihn in die Queue
Solange, bis der erste Pfad in der Queue zum Ziel-Node führt oder die Queue leer ist
1. Lösche den ersten Pfad aus der Queue. Ermittle den Endpunkt des Pfades und erzeuge je einen neuen Pfad zu allen Nachbarn dieses Endpunktes.
2. Entferne alle neuen Pfade, die Schleifen enthalten.
3. Füge die verbleibenden Pfade an zufälliger Stelle in die Queue ein.
Wenn der Zielknoten erreicht wurde, gib den Pfad aus.

[bearbeiten] Heuristisch informierte Suche

[bearbeiten] Hill-Climbing

http://en.wikipedia.org/wiki/Hill_climbing
Verhält sich wie die Tiefensuche mit einbeziehung von weiteren Daten (z.B. Luftlinie zwischen start- und zielnode)

Erzeuge einen Pfad, der nur aus dem Start-Node besteht und schreibe ihn in die Queue
Solange, bis der erste Pfad in der Queue zum Ziel-Node führt oder die Queue leer ist
1. Lösche den ersten Pfad aus der Queue. Ermittle den Endpunkt des Pfaades und erzeuge je einen neuen Pfad zu allen Nachbarn dieses Endpunktes.
2. Entferne alle neuen Pfade, die Schleifen enthalten.
3. Sortiere die verbleibenden neuen Pfade aufsteigend, nach der Distanz zum Ziel.
4. Füge die verbleibenden Pfade am Beginn der Queue ein.
Wenn der Zielknoten erreicht wurde, gib den Pfad aus.

[bearbeiten] Beam Search

Verhält sich wie die Breitensuche, es wird jedoch nur immer eine gewisse anzahl von Pfaden untersucht damit der Baum nicht Explodiert.

[bearbeiten] Best-First Search

http://en.wikipedia.org/wiki/Best-first_search

[bearbeiten] Optimale Netzsuche

[bearbeiten] British Museum Procedure

http://en.wikipedia.org/wiki/British_Museum_procedure

[bearbeiten] Branch-and-Bound Search

Erzeuge einen Pfad, der nur aus dem Start-Node besteht und schreibe ihn in die Queue
Solange, bis der erste Pfad in der Queue zum Ziel-Node führt oder die Queue leer ist
1. Lösche den ersten Pfad aus der Queue. Ermittle den Endpunkt des Pfades und erzeuge je einen neuen Pfad zu allen Nachbarn dieses Endpunktes
2. Entferne alle neuen Pfade, die Schleifen enthalten
3. Füge die verbleibenden Pfade in die Queue ein
4. Sortiere die Queue aufsteigend, nach den Pfadkosten
Wenn der Zielknoten erreicht wurde, gib den Pfad aus

[bearbeiten] Branch-and-Bound Search mit Abschätzung der Restkosten

Erzeuge einen Pfad, der nur aus dem Start-Node besteht und schreibe ihn in die Queue
Solange, bis der erste Pfad in der Queue zum Ziel-Node führt oder die Queue leer ist
1. Lösche den ersten Pfad aus der Queue. Ermittle den Endpunkt des Pfades und erzeuge je einen neuen Pfad zu allen Nachbarn dieses Endpunktes
2. Entferne alle neuen Pfade, die Schleifen enthalten
3. Füge die verbleibenden Pfade in die Queue ein
4. Sortiere die Queue aufsteigend, nach den Pfadkosten und der geschätzten Kosten zum Ziel
Wenn der Zielknoten erreicht wurde, gib den Pfad aus

[bearbeiten] Branch-and-Bound Search mit Eliminierung längerer Doppelwege

Erzeuge einen Pfad, der nur aus dem Start-Node besteht und schreibe ihn in die Queue
Solange, bis der erste Pfad in der Queue zum Ziel-Node führt oder die Queue leer ist
1. Lösche den ersten Pfad aus der Queue. Ermittle den Endpunkt des Pfades und erzeuge je einen neuen Pfad zu allen Nachbarn dieses Endpunktes
2. Entferne alle neuen Pfade, die Schleifen enthalten
3. Füge die verbleibenden Pfade in die Queue ein
4. Wenn zwei oder mehrere Pfade zu einem gleichen Node führen, lösche diese Pfade mit Ausnahme des Pfades, der den Node mit den minimalen Kosten erreicht
5. Sortiere die Queue aufsteigend, nach den Pfadkosten
Wenn der Zielknoten erreicht wurde, gib den Pfad aus

[bearbeiten] A* Algorithmus

Stellt ein Branch-and-Bound Search mit Abschätzung der Restkosten und Eliminierung längerer Doppelwege dar
http://de.wikipedia.org/wiki/A%2A

Erzeuge einen Pfad, der nur aus dem Start-Node besteht und schreibe ihn in die Queue
Solange, bis der erste Pfad in der Queue zum Ziel-Node führt oder die Queue leer ist
1. Lösche den ersten Pfad aus der Queue. Ermittle den Endpunkt des Pfades und erzeuge je einen neuen Pfad zu allen Nachbarn dieses Endpunktes
2. Entferne alle neuen Pfade, die Schleifen enthalten
3. Füge die verbleibenden Pfade in die Queue ein
4. Wenn zwei oder mehrere Pfade zu einem gleichen Node führen, lösche diese Pfade mit Ausnahme des Pfades, der den Node mit den minimalen Kosten erreicht
5. Sortiere die Queue aufsteigend, nach der Summe der Pfadkosten und der geschätzten Kosten zum Ziel
Wenn der Zielknoten erreicht wurde, gib den Pfad aus

Von „http://study.2030.tk/wiki/Fach:KI_Stundenlogs“

Kategorie: KI