Vorlesungsskript: Grundlagen des Entscheidens I |
| Inhalt |
Dieses Teilkapitel ist als Exkurs gedacht. Wem es für den Anfang zu schwierig ist, der kann diesen Exkurs (und die dazu gehörigen Übungsaufgaben) ruhig überspringen. Im Folgenden wird darauf nicht mehr zurück gegriffen.
Um Entscheidungsbäume in Tabellen umzuwandeln, können wir uns den Umstand zu Nutze machen, dass Entscheidungsbäume, so kompliziert sie auch sein mögen, aus der Kombination von nur zwei Elementen bestehen, Entscheidungsknoten und Zufallsknoten. Um einen Entscheidungsbaum in eine Tabelle zu überführen müssen wir also nur wissen, wie man 1) Entscheidungsknoten in eine Tabelle überträgt, wie man 2) Zufallsknoten in eine Tabelle überträgt und 3) wie man einen komplizierten zusammengesetzten Baum schrittweise mit Hilfe der beiden vorherigen Übertragungsregeln reduziert.
1) Ein Entscheidungsbaum, der nur aus einem einzigen Entscheidungsknoten mit zwei Alternativen besteht, ergibt eine Tabelle mit zwei Zeilen und einer Spalte:
![[image: Beispiel1b_1.png]](Beispiel1b_1.png)
2) Ein Baum, der nur aus einem Zufallsknoten besteht, liefert demgegenüber eine Tabelle mit nur einer Zeile und genau soviel Spalten wie Ereignisse an dem entsprechenden Ereignisknoten eintreten können.
![[image: Beispiel1b_2.png]](Beispiel1b_2.png)
3) Wie kann man nun aber einen Entscheidungsbaum, der aus einer Vielzahl von Entscheidungs- und Zufallsknoten besteht, in eine Tabelle überführen? Dazu wird der Baum schrittweise von hinten „aufgerollt“. Die jeweils „letzten“ Entscheidungs- bzw. Zufallsknoten von rechts entsprechen genau den vorher beschriebenen Fällen und können auf die beschriebende Weise umgewandelt werden. Kompliziert wird es erst bei den weiter in der Mitte und am Anfang liegenden Knoten. Wenn wir an einem solchen Knoten ankommen, haben wir den Baum aber schon soweit aufgerollt, dass wir zu den sich an den Knoten anschließenden Teilbäumen bereits über Tabellen verfügen. Das Problem stellt sich also folgendermaßen dar: Wie kann ein Entscheidungsknoten bzw. ein Zufallsknoten in eine Tabelle überführt werden, an dessen Enden sich wiederum ganze Entscheidungsbäume anschließen, für die wir aber immerhin schon über eine Repräsentation in Tabellenform verfügen?
Um dieses Problem zu lösen, müssen wir wiederum Entscheidungs- und Zufallsknoten getrennt betrachten:
3 a) Angenommen, wir haben es mit einem Entscheidungsknoten zu tun. Dann endet der Entscheidungsknoten in zwei Teilbäumen, die bereits als Tabellen dargestellt sind. Jede dieser Tabellen enthält wiederum eine Menge von Handlungsalternativen und eine Menge von Zufallsereignissen.
![[image: Beispiel1b_3.png]](Beispiel1b_3.png)
Die beiden Ereignismengen und des ersten und des zweiten Teilbaums sowie die entsprechenden Mengen von Handlungsalternativen und müssen nun in geeigneter Form kobminiert werden, um die Tabelle des gesamten Entscheidungsknotens aufzubauen. Das geschieht folgendermaßen: In den Spalten der zusammengefassten Tabelle muss jede mögliche Kombination der Zufallsereignisse aus beiden Mengen eingetragen werden. In den Zeilen wird als erstes der Block von Handlungen eingetragen, worauf als zweites ein Block von Handlungen folgt (d.h. jede der Handlungen der ersten Tabelle wird mit der Handlung kombiniert, jede alternative Handlung der zweiten Tabelle mit ).[4] Daraus ergibt sich folgende kombinierte Tabelle:
Man beachte: Jedes mögliche Resultat aus der ersten Tabelle kommt genau -mal vor, d.h. genauso viel mal, wie es Zufallsereignisse in der zweiten Tabelle gibt. Umgekehrt kommt jedes mögliche Resultat aus der zweiten Tabelle genau -mal vor, wobei die Anzahl der Zufallsereignisse in der ersten Tabelle ist. (Die entsprechende Tabellendarstellung ist also in der Regel hochgradig redundant und könnte, wenn dies der Fall ist, nachträglich noch vereinfacht werden.)
3 b) Geht es statt dessen um die Umwandlung eines Zufallsknotens, dann stehen wir vor der spiegelbildlichen Situation, so dass wir diesmal zwei Spaltenblöcke bilden und in den Zeilen jede Kombination möglicher Handlungen zu berücksichtigen haben.
![[image: Beispiel1b_4.png]](Beispiel1b_4.png)
Um die kombinierte Tabelle zu konstruieren, müssen wir also zwei Spaltenblöcke bilden, wobei der erste Block alle Zufallsereignisse der ersten Tabelle umfasst (und-verknüpft mit dem Ereignis versteht sich!) und der zweite Block die der zweiten Tabelle: In den Zeilen treten alle Kombinationen möglicher Handlungen auf, und zwar, da die Möglichkeit, eine bestimmte Handlung zu wählen oder nicht zu wählen erst durch das Eintreten von oder überhaupt eröffnet wird, in einer „wenn dann“-Form. In einer abgekürzten Schreibweise, bei der das Zeichen „“ für die wenn-dann-Beziehung stehen soll, schreiben wir also z.B. .[5]
Mit diesen beiden „Übersetzungsregeln“ kann man jeden Entscheidungsbaum systematisch schrittweise in eine Tabelle überführen. Man ahnt, dass die Tabelle ziemlich groß werden kann. Dies hängt auch damit zusammen, dass wir an dieser Stelle auf Sonderfallbetrachtungen verzichtet haben, die die Tabelle vereinfachen könnten. Z.B. ist es sehr wohl möglich, dass unterschiedliche Zufallsknoten in einem Baum in Wirklichkeit ein- und dasselbe Ereignis ausdrücken, nur dass es je nach den zuvor getroffenen Entscheidungen möglicherweise zu anderen Resultaten führt. Am Beispiel von vorhin lässt sich dies erläutern:
![[image: Beispiel1_1.png]](Beispiel1_1.png)
Würde man diesen Entscheidungsbaum nach unserem „mechanischen“ Verfahren in eine Tabelle überführen, dann würden in den Spaltenüberschriften die Ereignisse „schwere Klausur & schwere Klausur“, „schwere Klausur & leichte Klausur“, „leichte Klausur & schwere Klausur“ und „leichte Klausur & leichte Klausur“ stehen. Das hängt damit zusammen, dass der Algorithmus zunächst keine Informationen darüber hat, ob unterschiedliche Zufallsknoten möglicherweise identische Zufallsereignisse repräsentieren. Man müsste den Entscheidungsbaum um entsprechende Informationen ergänzen (z.B. indem man eine Verbindungslinie zwischen identischen Ereignissen zieht) und den Algorithmus so anpassen, dass er unmögliche Ereigniskombinationen („schwere & leichte Klausur“) streicht.
Weiterhin haben wir den Algorithmus zur Übersetzung von Bäumen in Tabellen zunächst nur für Binär-bäume (d.h. Bäume, die an jeder Verzweigung nur zwei Äste haben) beschrieben. Das ist aber unproblematisch, da man jeden Entscheidungsbaum in einen binären Entscheidungsbaum umwandeln kann. Z.B. kann der Entscheidungsbaum
![[image: Beispiel1b_5.png]](Beispiel1b_5.png)
einfach in den Baum
![[image: Beispiel1b_6.png]](Beispiel1b_6.png)
umgewandelt werden. Eine andere Alternative bestünde darin, den Algorithmus so anzupassen, dass er sich auch für nicht binäre Entscheidungsbäume eignet (siehe Übungsaufgabe 2.1.5 auf Seite 2.1.5).
|
[4] Das aus der Logik bekannte Zeichen bedeutet „und“, so dass der Ausdruck so zu verstehen ist, dass die Handlung und die (möglicherweise wiederum aus mehreren Einzelhandlungen zusammengesetzte) Handlung ausgeführt werden.
[5] Angesichts der Symmetrie zwischen dem Problem der Umwandlung eines Entscheidungsknotens in eine Tabelle und dem der Umwandlung eines Zufallsknotens in eine Tabelle, könnte es verwundern, dass wir im zweiten Fall in den Zeilen der generierten Tabelle „wenn dann“-Audrücke vorfinden, während wir uns im ersteren Fall mit simpleren und-Verknüpfungen begnügen. Dies ist dadurch motiviert, dass wir davon ausgehen, dass die Ereignisse der Serien bzw. unabhängig von den getroffenen Entscheidungen auch dann eintreten, wenn sie angesichts des gewählten Zweiges für das erzielbare Ergebnis nicht mehr relevant sind. Diese Annahme ist zwar harmlos aber keinesfalls zwingend. Wollte man ganz präzise sein, dann müsste man die Spaltenüberschriften der aus einem Entscheidungsknoten gewonnen Tabelle ebenfalls als „wenn dann“-Aussagen ausformulieren.
|