Die folgenden Seiten beschäftigen sich mit dem in den letzten Jahren zunehmenden Bereich des Case-based reasoning (CBR) (dt. Fallbasiertes Schliessen). Case-based reasoning ist eine Technik, die aus der Psychologie abgeleitet ist und in verschiedenen Anwendungsberei-chen zum Tragen kommt, vornehmlich in der Künstlichen Intelligenz (KI). Im weiteren Verlauf wird, ausgehend von dem Hintergrund und der Motivation dieses The-mengebiets, die Begrifflichkeit erklärt sowie ein einführendes Beispiel aufgeführt, um die späteren Konzepte leichter nachvollziehbar zu machen. Im Hauptteil werden die wichtigsten Grundlagen von CBR erklärt und anhand des Phasenmodells von Aamodt und Plaza [AaPl94] durchlaufen. Ferner wird auf den Aufbau von CBR-Anwendungen hingewiesen und kommerzielle Werkzeuge vorgestellt. Im Schlussteil erfolgt dann abschliessend eine Zusam-menfassung des Themenkomplexes, und ein Blick auf die zukünftige Entwicklung soll helfen zu verstehen, warum dieses Gebiet in den letzten Jahren so grosse Fortschritte gemacht hat und in neuen Bereichen wie self-service und e-commerce im WWW anzutreffen sein wird.
Inhaltsverzeichnis
1. Einleitung
1.1. Motivation und Hintergrund
1.2. Kognitionswissenschaftliche Basis
1.3. Problemlösungen mit Case-Based-Reasoning
2. Grundbegriffe und Fallrepräsentation
2.1. Repräsentationsformalismen
2.2. Ähnlichkeitsbestimmung(similarity)
2.3. Fallbasis und Lösungstransformation
2.4. Grundtypen von CBR-Methoden
3. Prozessmodell
Bild 1 Der CBR-Kreis Quelle: [AaPl94]
3.1. Retrieve
3.2. Reuse
3.3. Revise
3.4. Retain
4. Aufbau von CBR-Systemen und kommerzielle Werkzeuge
5. Zusammenfassung
1. Einleitung
Die folgenden Seiten beschäftigen sich mit dem in den letzten Jahren zunehmenden Bereich des Case-based reasoning (CBR) (dt. Fallbasiertes Schliessen). Case-based reasoning ist eine Technik, die aus der Psychologie abgeleitet ist und in verschiedenen Anwendungsbereichen zum Tragen kommt, vornehmlich in der Künstlichen Intelligenz (KI).
Im weiteren Verlauf wird, ausgehend von dem Hintergrund und der Motivation dieses Themengebiets, die Begrifflichkeit erklärt sowie ein einführendes Beispiel aufgeführt, um die späteren Konzepte leichter nachvollziehbar zu machen. Im Hauptteil werden die wichtigsten Grundlagen von CBR erklärt und anhand des Phasenmodells von Aamodt und Plaza [AaPl94] durchlaufen. Ferner wird auf den Aufbau von CBR-Anwendungen hingewiesen und kommerzielle Werkzeuge vorgestellt. Im Schlussteil erfolgt dann abschliessend eine Zusammenfassung des Themenkomplexes, und ein Blick auf die zukünftige Entwicklung soll helfen zu verstehen, warum dieses Gebiet in den letzten Jahren so grosse Fortschritte gemacht hat und in neuen Bereichen wie self-service und e-commerce im WWW anzutreffen sein wird.
1.1. Motivation und Hintergrund
Autowerkstatt "Car&Bike": es ist kurz vor Feierabend. Automechaniker Stefan H. will gerade abschliessen als noch ein letzter Kunde kommt. Das Problem mit seinem Wagen liegt darin, dass der Motor nicht mehr anspringt. Nach einer ersten oberflächlichen Überprüfung stellt er fest, dass sowohl genug Benzin im Tank ist, als auch Öl und Wasser stimmen und keine, auf den ersten Blick wahrnehmbaren, Schäden an Keilriemen oder Lichtmaschine zu erkennen sind. Stefan H. überlegt woran es liegen könnte. Da fällt ihm der Kunde von letztem Monat ein: da hatte der Wagen die gleichen Symptome und nach langer Suche wurde das Übel in Form der kaputtgegangenen Einspritzpumpe identifiziert. Diesmal wird Stefan H. sofort mal nach der Einspritzpumpe sehen...
Was Stefan H. gerade durchdacht hat stellt eins von vielen alltäglichen Beispielen für kognitive Leistung dar. Man steht vor einem Problem und versucht es zu lösen, indem man auf Lösungen von früheren ähnlichen Problemen zurückgreift. So eine Vorgehensweise ist nicht selten anzutreffen: in der Rechtssprechung geht der Vergleich zwischen einem aktuellen Strafdelikt und einem früheren Präzedenzfall dieselben Wege; ebenso eine Grundschullehrerin, die den Streit zweier Schüler um einen Fussball schlichtet und dabei die gleiche Vorgehensweise an den Tag legt wie einige Stunden zuvor auch.
All diese alltäglichen Probleme haben eines gemeinsam: den Prozess der Lösungsfindung, Verstehen und Lernen mit bereits Gelöstem, Verstandenem, Gelerntem oder Bewährtem.
Was ist Case-based reasoning?
" Case-based reasoning is [...] reasoning by remembering." zitiert nach [Berg99]
" A case-based reasoner solves new problems by adapting solutions that were used to solve old problems. " zitiert nach [Berg99]
" Case-based reasoning is a recent approach to problem solving and learning [...]"
[AaPl94]
" Case-based reasoning is both [...] the ways people use cases to solve problems and the ways we can make machines use them." zitiert nach [Berg99]
Beim CBR wird bereits vorhandenes, spezifisches Problemlösungswissen zur Lösung eines neuen Problems herangezogen und ggf. wiederverwendet. Dieses Wissen beruht auf früheren "Fällen" (case), die in einer sog. Fallsammlung (General Knowledge) zusammengefasst sind. Ein Fall besteht dabei immer aus der Beschreibung einer bereits aufgetretener Problemsituation und deren Lösung. Es können darüber hinaus auch in abgewandelter Form Beschreibung des Problemlösungswegs oder die Bewertung der jeweiligen Problemlösung zu dem Fall aufgenommen werden.
Beim Case-based reasoning geht man implizit von der Annahme aus, dass ähnliche Problemsituationen auch ähnliche Problemlösungen erfordern. Daher wird, um ein neues Problem zu lösen, ein ähnlicher Fall in der vorhandenen Fallsammlung ermittelt und anschliessend die vorhandene Problemlösung auf das neue Problem komplett oder in adaptierter Form übertragen. Dadurch ist ein neuer Fall entstanden, der nun in der Fallsammlung aufgenommen werden kann, um bei zukünftigen Problemen ebenfalls herangezogen werden zu können.
1.2. Kognitionswissenschaftliche Basis
Der Name Case-based reasoning ist zwar oben in einem ersten oberflächlichen Versuch erklärt worden, jedoch ist er für sich genommen wenig informativ und bedarf neben weiteren Erklärungen auch noch einigen Vorüberlegungen.
Der oben schon eingeführte Begriff "Fall" (engl. case) ist also eine " irgendwie geartete Erfahrung beim Lösen eines Problems " [Rich00], wobei die Beschreibung dieser Erfahrung meist erst einmal umgangssprachlich und informal vorliegt. Oft ist es auch nützlich, Erklärungen, wichtige Teile des Lösungsweges und andere zusätzliche Informationen mitzuliefern. Die Nutzung einer solchen Erfahrung oder Falles besteht im Weiteren nun darin, die Lösung auf ein neues, aktuelles oder hinreichend ähnliches Problem anzuwenden. Solche Erfahrungen spielen auch in anderen wissensbasierten Systemen eine Rolle, jedoch ist es wichtig, den Unterschied zwischen case-based Systemen und wissensbasierten Systemen zu sehen. Man kann case-based Systeme als spezielle Fortentwicklung wissensbasierter Systeme verstehen.
Der Leser kann sich nun zwei Arten von Fällen denken: gut gelöste und schlecht gelöste. Die ersteren möchte man erzielen und später wiederverwenden und die letzteren umgehen. Im weiteren Verlauf wird nur die erste Klassifizierung betrachtet. Die Menge aller Erfahrungen in Form der Fälle wird in der schon erwähnten Fallsammlung oder Fallbasis verwaltet. Sind die zwei zu betrachtenden Probleme, also frühere Erfahrung ↔ aktuelles Problem, aus unterschiedlichen Domänen (z.B. Sonnensystem und Atommodell) spricht man von "Analogie". Case-based reasoning wird aber so verstanden, dass beide Probleme aus demselben Bereich stammen. Ferner ist die Unterscheidung zu treffen, ob man die gefundene Lösung unverändert übernimmt oder sie geeignet adaptiert (im Beispiel: tauscht Stefan H. jetzt nur die Einspritzpumpe oder ist nicht auch ein Wechsel des Keilriemens nötig?). Hier ist somit ein Unterschied von eigentlichem case-based reasoning zu case-based retrieval zu sehen, da im zweiten Fall die Lösung nur kopiert, nicht aber generiert wurde. Diese Unterscheidung wird dann natürlich noch interessanter, wenn die Fallbasis eine derartige Menge an Erfahrungen beinhaltet, dass es zusätzlich noch zu dem Problem kommt, sich in einer aktuellen Situation einen geeigneten Fall aus der Basis suchen zu müssen.
Diese Vorgehensweise, Probleme zu lösen ist dem Menschen von jeher vertraut. Ihre Nutzbarmachung für die Unterstützung beim Problemlösen geht auf den Ansatz des "Dynamischen Gedächtnisses" (dynamic memory) [Berg99] zurück. Dieses psychologische Modell über menschliches Problemlösen und Lernen wird mit dem Wunsch verbunden, menschliche Intelligenz im Rahmen der KI auf einem Rechner zu verwirklichen.
Hierzu werden einige grundlegende Annahmen gemacht:
1. "Erinnern und Anpassen (Adaptieren) sind zentrale mentale Prozesse beim Verstehen" [Rich00]
Beim Verstehen ist sowohl allgemeines Wissen (scripts) als auch spezifisches Wissen (Fälle) erforderlich. Scripts speichern nur allgemeines Wissen (z.B. über Kinos). Ein script ist dabei eine Gedächtnisstruktur, die dieses allgemeine Wissen über eine typische Situation speichert.
Beispiel: Kinoscript
betreten → Karte kaufen → Platz aufsuchen → Film anschauen → gehen
2. "Indexierung ist für das Erinnern wichtig." [Rich00]
Je nach Bedarf wird allgemeines Wissen in Form von scripts oder spezifisches Wissen in Form von Fällen erinnert. Dabei ist es wichtig, dass
Indizes für die Situation (z.B. Kinobesuch) und die Unterschiede zu ähnlichen Situationen (z.B. Einlass bei anderen Kino) vorhanden sind.
3. "Verstehen führt zur Reorganisation des Gedächtnisses, weshalb dieses dynamisch ist." [Rich00]
Verstehen bedeutet, dass der Speichereintrag, welcher der aktuellen Situation am nächsten kommt aufgefunden und das Verständnis auf die neue Situation angepasst wird. Somit werden Erfahrungen erinnert und liefern Erwartungen, die das Verstehen erst ermöglichen.
4. "Die Gedächtnisstrukturen für die Wissensverarbeitung sind dieselben wie für die Wissensspeicherung." [Rich00]
Das dynamische Gedächtnis ändert sich durch Erfahrungen: es werden neue Fälle gespeichert, neue Indizes eingefügt oder bestehende geändert, neue Generalisierungen aus den Fällen erzeugt.
Die Fallbasis ist somit auch solch ein dynamisches Gedächtnis, welches sich ständig erweitert. Es ist daher offensichtlich, dass bei so einer Vorgehensweise und der Annahme der dynamischen Fallbasis, keine korrekten Lösungen garantiert werden können.. Deshalb wird auf die Exaktheit der Lösung zugunsten einer annährenden Lösung verzichtet. Da diese annährende Lösung nicht wahllos bestimmt werden darf, wird dies durch den Begriff der "Ähnlichkeitsbestimmung" (similarity), welcher eine zentrale Rolle in case-based Systemen einnimmt, kontrolliert (siehe 2.2 Ähnlichkeitsbestimmung (similarity)). Der Verzicht auf Exaktheit spiegelt sich auch darin wider, dass nicht mehr auf den Wahrheitsbegriff, sondern vielmehr auf den Nützlichkeitsbegriff Wert gelegt wird. Lösungen sind somit nicht mehr wahr oder falsch, sondern mehr oder weniger nützlich. Es handelt sich auch später nicht mehr um eine logisch richtige, sondern um eine Optimierungsfrage. Während der Wahrheitsbegriff universell ist, muss der Nutzen einer Lösung bei jedem aktuellen Problem individuell festgelegt werden.
1.3. Problemlösungen mit Case-Based-Reasoning
Um eine sinnvolle Nutzung durch CBR zu gewährleisten sind vorab folgende Überlegungen nötig:
1. "Es müssen hinreichend viele Erfahrungen vorliegen." [Rich00]
2. "Es muss einfacher sein, diese Erfahrungen zu nutzen, als die Probleme direkt zu lösen." [Rich00]
3. "Die Verwendung der Lösungen der Fallbasis darf sicherheitskritischen Anforderungen nicht widersprechen ." [Rich00]
4. "Die zur Verfügung stehenden Informationen sind unvollständig oder unsicher und ungenau." [Rich00]
5. "Eine Modellierung im Sinne traditioneller wissensbasierter Systeme ist nicht oder nicht einfach erhältlich ." [Rich00]
[...]
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.