ÜbersichtI Künstliche Intelligenz

1. Einführung2. Intelligente Agenten

II Problem lösen

III Wissen und Schlußfolgern

IV Logisch Handeln

V Unsicheres Wissen und Schließen

VI Lernen

VII Kommunizieren, Wahrnehmen und Handeln

Übersicht über Definitionen der Künstlichen Intelligenz

Menschliches Verhalten: Der Turing Test

Def.: Intelligentes Verhalten ist die Fähigkeit, menschliche Performanzin allen kognitiven Bereichen zu erreichen, so daß ein Interviewergetäuscht wird.

Turing Test (1950): Ein Mensch kann (nach 30 Minuten freiem Dialog)nicht entscheiden, ob sein Gegenüber ein Mensch oder eine Maschine ist(Kommunikation nur über Terminal).

Erforderliche Fähigkeiten eines Computers:

- Sprachverarbeitung- Wissensrepräsentation- Schlußfolgerungsfähigkeit- Lernfähigkeit

Erweiterung zu totalem Turing Test für Umgang mit physikalischenObjekten:

- Bildverarbeitung- Robotik

Loebner-Preis für Turing-Test

• Seit 1990 (gestiftet von Loebner, vergeben in Cambridge/USA)http://www.loebner.net/Prizef/loebner-prize.html

• Ablauf: Eine Jury kommuniziert mit 8 Programmen sowie 2Menschen und soll beides auseinanderhalten.

• Preise:– Gold: 100000 $ für natürlichsprachlichen Dialog,

– Silber: 25000 $ für schriftlichen Dialog,

– Bronze: 2000 $ für bestes Programm

• Bronze-Preisträger 2001 (wie 2000): Alice: http://alicebot.org/

Menschliches Denken: Kognitionswissenschaft

Voraussetzung für den Turing Test ist, daß Programme ähnlich wieMenschen denken. Menschliches Denken wird von derKognitionswissenschaft untersucht. Zugangsmethoden:

IntrospektionPsychologische Experimente

Falls eine hinreichend präzise Theorie aufgestellt wurde, kann man sieals Computerprogramm ausdrücken und vergleichen, ob dessen Ein-/Ausgabeverhalten dem von Menschen entspricht.

Rationales Denken: "Gesetze des Denkens“

Logisches Schließen: Gesetze, die richtige Schlußfolgerungen ausrichtigen Prämissen ableiten.

Beispiel: Syllogismus von Aristoteles:

Prämisse 1: Alle Menschen sind sterblich.Prämisse 2: Sokrates ist ein Mensch.Konklusion: Sokrates ist sterblich.

Im Gegensatz etwa zur Arithmetik können mit der Logik alle möglichenAussagen über die Welt und ihre Relationen gemacht werden.

Seit 1965 existieren Programme, die unter der Annahme von genügendZeit und Speicherkapazität für beliebige in logischer Sprache formuliertenProbleme eine Lösung finden, sofern eine Lösung existiert.

Probleme dieses Ansatzes:

– Formulierung eines informellen Problems in logischer Sprache.– Großer Unterschied, etwas prinzipiell oder tatsächlich tun zu können.

Rationales Handeln: Rationale Agenten

Agent: Etwas, das wahrnimmt und handelt.

Rationales Handeln: So zu handeln, daß man gemäß seinem Wissenseine Ziele erreicht.

Während die Gesetze des Denkens korrekte Inferenzen betonen, gehtrationales Handeln darüber hinaus, da es Zeitbegrenzungen, Un-sicherheiten usw. miteinbezieht.

Grundlagen der KI

Philosophie

Mathematik/Informatik

Psychologie

Computer

Linguistik

Philosophie (Plato (428 v.C) - jetzt) (1)

Sokrates fragt Euthyphro: Woran kann ich Frömmigkeit erkennen?

Aristoteles entwickelt informelles System zum korrekten Schlußfolgern(z.B. Syllogismus). Er glaubt aber auch an Intuition.

---- Problem des freien Willens

Rene Descartes (1596-1650): Dualismus (Seele ↔ Verstand)

Wilhelm Leibnitz (1646-1716): Materialismus

John Locke (1561-1626): Empirismus. "Nichts ist im Verstand,was nicht vorher in den Sinnen war."

David Hume (1711-1776): Induktion

Bertrand Russell (1872-1970): Logischer Positivismus

Newell & Simon (1972): Implementierung eines Programms zurMittel-Zweck-Analyse (means-ends analysis)

John Stuart Mill (1806-1873): Nützlichkeit (Utilitarismus)

Mathematik/Informatik (800 - jetzt) (1)

Formalisierungsbedarf in: Berechenbarkeit, Logik, Wahrscheinlichkeit

al-Khowarazmi (9. Jahrhundert): Algorithmus

--- Entwicklung der Logik

George Boole (1815-64; 1847): Formale Sprache für logische Inferenzen

Gottlob Frege (1848-1925; 1879): Prädikatenlogik 1. Stufe

Alfred Tarski (1902-83): Theorie über die Beziehung zwischen Objektender Welt und der Logik

--- Grenzen von Logik und Berechenbarkeit

David Hilbert (1862-1943; 1900): Frage nach Entscheidungsproblem

Kurt Gödel (1906-78; 1931): Unvollständigkeitstheorem.

Alan Turing (1912-54): T.-Maschine, Church-T. These; Halteproblem.

Mathematik/Informatik (800 - jetzt) (2)

--- praktische Grenzen der Berechenbarkeit

Intractability (Widerspenstigkeit): Mindestens exponentieller Zeitbedarf

NP-Vollständigkeit (Cook 1971 & Carp 1972)

--- Wahrscheinlichkeit

Geralamo Cardano (1501-76): Idee der Wahrscheinlichkeit

Thomas Bayes (1702-61): Theorem von Bayes

Entscheidungstheorie (John v. Neumann & Oskar Morgenstern, 1944)

Psychologie (1879 - jetzt)

Experimente und Introspektion (Wundt 1879: 1. Labor fürexperimentelle Psychologie an der Univ. Leipzig).

Behaviourismus (ca. 1920–60). Rebellion gegen Introspektion:Beschränkung der Untersuchung auf Reiz-Reaktion ohne mentaleKonstrukte wie Wissen, Glauben, Ziele.

Kognitive Psychologie (Kenneth Craik 1943):1. Reize werden in eine interne Repräsentation überführt.2. Die interne Repräsentation wird durch kognitive Prozesse verarbeitet.3. Daraus ergeben sich Aktionen. (Anderson, 1980): "Eine kognitive

Theorie sollte wie ein Computer-Programm sein".

Computer (1940 - jetzt)

Heath Robinson: (1940, Alan Turing). Erster funktionsfähigerSpezialcomputer zur Dekodierung von deutschen Funksprüchen im 2.Weltkrieg

Z3 (1941, Konrad Zuse). Erster programmierbarer Computer

IBM 701 (1952, Nathaniel Rochester): Erster profitabler Computer.

Die rasante Steigerung der absoluten Leistungsfähigkeit und desPreis/Leistungsverhältnisses von Computern (Verdopplung bisher etwaalle 18 Monate) war und ist eine entscheidende Voraussetzung für dieKünstliche Intelligenz.

Linguistik (1957 - jetzt)

Noam Chomsky (1957): Mit einer Kritik des Buches "Verbal Behaviour"des Behavioristen Skinner demonstiert er die Notwendigkeitweitergehender Modelle zum Verständnis kreativer Aspekte beim Lernenvon Sprache (wie z.B. in seinem gleichzeitg erschienenen Buch"Syntactic Strucures").

Jedoch reichen syntaktische Strukturen nicht aus, Mehrdeutigkeiten derSprache aufzulösen, daher schon früh ein starkes Interesse anWissensrepräsentation.

Geschichte der Künstlichen Intelligenz

1942 - 1956: Vorlaufphase

1952 - 1969: Früher Enthusiasmus, große Erwartungen

1966 - 1974: Relativierung durch Realitätsbezug

1969 - 1979: Wissensbasierte Systeme

1980 - 1988: Beginn der wissensbasierten Industrie

1986 - jetzt: Rückkehr der Neuronalen Netze

Gegenwart: Uneinheitlich

Vorlaufphase der KI (1943 - 1956)

Cullach & Pitt 1943: Integration dreier Quellen zum Vorschlag einesNetzes künstlicher Neuronen:

Physiologie der Neuronen

Aussagenlogik

Theorie der Berechenbarkeit

Dartmouth-Workshop 1956 (Newell, Simon, Minsky, Mc Carthy et al.):Prägung des Begriffes "Künstliche Intelligenz".

Früher Enthusiasmus, große Erwartungen 1952 - 1969 (1)

Anfangs wurden die (relativ primitiven) Computer nur alsRechenmaschinen betrachtet ("eine Maschine kann niemals X tun). KI-Forscher erregten viel Aufmerksamkeit, indem sie für ein X nach demanderen Programme entwickelten.

Logic Theorist (Newell &Simon, CMU): Beweisenmathematischer Theoreme

General Problem Solver (Newell & Simon, CMU): AllgemeineProblemlöse-Architektur

Geometry Theorem Prover (Gelernter, IBM): Benutzung einernumerischen Repräsentation von Diagrammen beim Beweisen.

Checker-Program (Samuel, IBM): Lernfähiges SpielprogrammLISP (Mc Carthy, MIT, 1958).Time-Sharing (Mc Carthy, MIT, 1958).Advice Taker (Mc Carthy, MIT, 1958).

Früher Enthusiasmus, große Erwartungen 1952 - 1969 (2)

Explizite WissensrepräsentationMikrowelten (Minsky, MIT)- SAINT (Slage, 1963): Integral-Rechnung- ANALOGY (Evans, 1968): Geometrische Analogie aus

IQ-Tests- SIR (Raphael, 1969): Beantworten natürlichsprachlicherAnfragen

- STUDENT (Bobrow, 1967): Lösen natürlichsprachlicherschul-mathematischer Textaufgaben

Früher Enthusiasmus, große Erwartungen 1952 - 1969 (3)

Klötzchen-Welt (MIT):- Bildverarbeitung (Huffman, 1971)- Bildverarbeitung und Constraint-Propagierung (Waltz, 1975)- Lerntheorie (Winston, 1970)- Sprachverarbeitung (SHRDLU, Winograd, 1972)- Planung (Fahlman, 1974)

Neuronale Netze- Perceptron-Konvergenz-Theorem (Rosenblatt, 1962).

Relativierung durch Realitätsbezug (1966 - 1974)

- 1966 Abbruch der US-Forschungsförderung für Sprachübersetzung(gefördert seit Sputnik-Schock 1957)

- Nichterfüllen der Prophezeiung von Simon von 1958, daß in 10Jahren ein Computer Schachweltmeister und daß ein wichtigesneues mathematisches Theorem maschinell bewiesen worden sei.

- Entdecken der Skalierungsprobleme:"Die Tatsache, daß ein Programm ein Problem im Prinzip lösenkann, heißt nicht, daß es irgendwelche der Mechanismen enthält,die für einen praktischen Erfolg erforderlich sind."

- Fehlschlag bei Experimenten zur Maschinen-Evolution (heute:Genetische Algorithmen) trotz tausender CPU-Stunden.

- Lighthill-Bericht (1973): Abbruch der KI-Forschungsförderung inGroßbritannien (mit Ausnahme von 2 Unis)

- Die von Minsky & Papert (1969) gezeigten theoretischen Grenzenvon Perceptrons führen zu einem weitgehenden Ende derForschungsförderung im Bereich neuronaler Netze

Wissensbasierte Systeme (1969-1979) (1)

"In the knowledge lies the power" (Feigenbaum) - und nicht inuniversellen ("schwachen") Problemlösungsmethoden.

- DENDRAL (Buchanan, Feigenbaum und Lederberg, Stanford,1969): erstes bekanntes wissensbasiertes System zur Interpretationvon Massenspektrogrammen zur Aufklärung der Strukturformel vonMolekülen.

- MYCIN (Shortliffe, Stanford, 1976): Evaluiertes Expertensystemzur Antibiotika-Therapie von Infektionskrankheiten des Blutes mitsauberer Trennung zwischen Wissen und Inferenzmechanismen.

- PROSPECTOR (Duda et al, SRI, 1979): ProbabilistischesDiagnosesystem zur Vorhersage von Lagen für Bodenschätze, dasein großes Molybdän-Vorkommen richtig prognostiziert.

Wissensbasierte Systeme (1969-1979) (2)

Minsky (1975) faßt viele Ideen der Zeit in dem Konzept der "Frames"zusammen.

Auch bei der Sprachverarbeitung wird die Bedeutung von Weltwissen(stereotype Situationen, Skripts) - im Gegensatz zu den bishersyntaktisch orientierten Programmen wie SHRDLU betont (RogerSchank, Yale)

- LUNAR (Woods, 1973): Erstes extern genutztesnatürlichsprachliches Anfragesystem für eine Datenbank überMondgestein.

Beginn der wissensbasierten Industrie (1980 - 1988)

R1/XCON (Mc Dermott/DEC 1982): Erstes kommerziell erfolgreichesExpertensystem zur Konfiguration von Computern bei DEC(Einsparungen von ca. 40.000.000 $ pro Jahr)

Entstehen zahlreicher KI-Firmen mit meist hybriden Expertensystem-Werkzeugen und Beratung (Teknowledge, Carnegie Group, Inference,Intellicorp) sowie Entwicklung und Verkauf dezidierter KI-Hardware(LISP-Maschinen).

Fifth Generation Project (Japan, 1981). 10-Jahres-Projekt zurEntwicklung von intelligenten Maschinen.

Nachziehen der USA (MCC-Konsortium) und Europa (Alvey-Berichtwiederbelebt die KI-Forschung in Großbritannien, BMFT startetVerbundprojekte in Deutschland).

Der KI-Umsatz stieg 1980-88 von einigen Millionen auf ≈ 2 Milliarden $.

Danach Rückschlag wegen zu hoher Erwartungen ("KI-Winter").

Rückkehr der Neuronalen Netze (seit 1986)

Das Buch von Rummelhard & McClelland "Parallel DistributedProcessing" 1986 verbreitet neue Erfolge mit dem wiederentdecktenBackpropagation-Algorithmus (der bereits 1969, im gleichen Jahr in demdas kritische Buch von Minsky und Papert erschienen ist, von Bryson &Ho publiziert wurde).

Gegenwärtige Trends

Die KI ist etabliert. An fast jeder Informatik-Abteilung gibt es dazu eineProfessur, wissensbasierte Techniken werden in Industrie breit genutzt.

Relative Selbständigkeit anwendungsorientierter Teilbereiche:

- Wissenssysteme (Diagnose, Konfigurierung; Scheduling, Planung)- Sprachverarbeitung (Verstehen gesprochener und geschriebener

Sprache; Dolmetscher, Übersetzer, Natürlichsprachliche Anfrage-und Auskunftssysteme, Sprechschreibmaschinen).

- Bildverarbeitung (Erkennen von Gegenständen in begrenztenSzenen)

- Robotik (autonome Roboter, z.B. Robocup, Raumfahrt, Gefahren)

Betonung logischer Grundlagen (z.B. Hidden Markov Models,Probabilistische Netze, logik-basierte Wissensrepräsentationen):"Normative versus empirische Expertensysteme".

Versuche zur Integration, Agentenbasierte Ansätze, Internet

Aktuelle Erfolge

- Schachprogramme haben Weltmeisterniveau erreicht.

- Natürlichsprachliche Auskunftssysteme (z.B. Reisebuchung)

- Erfolgreiche Expertensysteme in vielen Bereichen

- Automatischer Autofahrer

- Automatische Verkehrsüberwachung

- Autonome Roboter auf dem Mars.