Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

Autor/Titel Begriff Zusammenfassung Metadaten

Peter Norvig über Entscheidungsbaum – Lexikon der Argumente

Norvig I 698
Def Entscheidungsbaum/Norvig/Russell: Ein Entscheidungsbaum repräsentiert eine Funktion DECISION TREE, die als Input einen Vektor von Attributwerten verwendet und eine "Entscheidung" - einen einzelnen Output-Wert - ausgibt. Die Ein- und Ausgabewerte können diskret oder kontinuierlich sein. Ein Entscheidungsbaum fällt seine Entscheidung mittels einer Reihe von Tests. Jeder interne Knoten im Baum entspricht einem Test des Wertes eines der Input-Attribute Ai, und die Zweige des Knotens werden mit den möglichen Werten des Attributs Ai =vik gekennzeichnet. Jeder Blattknoten im Baum gibt einen Wert an, welcher von der Funktion zurückgegeben werden muss.
Ein Boolescher Entscheidungsbaum ist logisch äquivalent zu der Behauptung, dass das Zielattribut wahr ist, und zwar nur dann, wenn die Eingabeattribute einen der Pfade erfüllen, die zu einem Blatt mit dem Wert wahr führen.
Wenn wir dies in der Aussagenlogik ausschreiben, haben wir
Ziel ⇔ (Pfad1 V Pfad2 ∨ · · ·) ,
wobei jeder Pfad eine Kombination von Tests des Attributwerts ist, die erforderlich sind, um diesem Pfad zu folgen. Der gesamte Ausdruck entspricht also der disjunkten Normalform. >Normalform/Logik.
Leider ist es, egal wie wir die Größe messen, ein unlösbares Problem, den kleinsten konsistenten Baum zu finden; es gibt keine Möglichkeit, die 22n Bäume effizient zu durchsuchen. Mit einigen einfachen Heuristiken können wir jedoch eine gute ungefähre Lösung finden: einen kleinen (aber nicht kleinsten) konsistenten Baum. Der Lernalgorithmus für Entscheidungsbäume verfolgt eine gierige Strategie des Teilen und Herrschens: immer das wichtigste Attribut zuerst testen. Dieser Test teilt das Problem in kleinere Teilprobleme auf, die dann rekursiv gelöst werden können.
"Wichtigstes Attribut": dasjenige, das für die Klassifizierung eines Beispiels den größten Unterschied macht.
Lernalgorithmus für Entscheidungsbäume: siehe Norvig I 702.
Norvig I 705
Probleme: Der Lernalgorithmus für Entscheidungsbäume erzeugt einen großen Baum, wenn eigentlich kein Muster zu finden ist.
Überanpassung (overfitting): Der Algorithmus greift jedes Muster auf, das er in der Eingabe finden kann. Wenn sich herausstellt, dass ein blauer, 7 Gramm schwerer Würfels zweimal mit gekreuzten Fingern gewürfelt wird und beide Würfe 6 ergeben, dann kann der Algorithmus einen Pfad konstruieren, der in diesem Fall 6 vorhersagt.
Lösung: Das Pruning des Entscheidungsbaums verhindert Überanpassung. Das Pruning funktioniert durch Eliminierung von Knoten, die nicht eindeutig relevant sind.
Norvig I 706
Fehlende Daten: In vielen Bereichen sind nicht alle Attributwerte für jedes Beispiel bekannt.
Norvig I 707
Multivariate Attribute: Wenn ein Attribut viele mögliche Werte hat, gibt das Maß für den Informationszuwachs einen unangemessenen Hinweis auf die Nützlichkeit des Attributs. Im Extremfall hat ein Attribut (z.B. die genaue Zeit) für jedes Beispiel einen anderen Wert, was bedeutet, dass jede Untermenge von Beispielen einzigartig ist und eine eindeutigen Klassifikation hat und das Maß für den Informationszuwachs für dieses Attribut seinen höchsten Wert hätte.
Kontinuierlich und ganzzahlig bewertete Input-Attribute: Kontinuierlich oder ganzzahlig bewertete Attribute wie Größe und Gewicht haben eine unendliche Menge möglicher Werte. Anstatt unendlich viele Äste zu erzeugen, finden Lernalgorithmen für Entscheidungsbäume normalerweise den Teilungspunkt, der den höchsten Informationszuwachs ergibt.
Kontinuierlich bewertete Output-Attribute: Wenn wir versuchen, einen numerischen Output-Wert vorherzusagen, wie z.B. den Preis einer Wohnung, dann brauchen wir einen Regressionsbaum statt eines Klassifikationsbaums. Ein Regressionsbaum hat an jedem Blatt eine lineare Funktion einer Teilmenge numerischer Attribute und nicht nur einen einzelnen Wert.
>Lernen/Norvig.
Norvig I 758
Geschichte: Die erste nennenswerte Verwendung von Entscheidungsbäumen war in EPAM, dem "Elementary Perceiver And Memorizer" (Feigenbaum, 1961)(1), der eine Simulation des menschlichen Konzeptlernens war. ID3 (Quinlan, 1979)(2) fügte die entscheidende Idee hinzu, das Attribut mit maximaler Entropie zu wählen; sie ist die Grundlage für den Algorithmus für Entscheidungsbäume in diesem Kapitel. Die Informationstheorie wurde von Claude Shannon entwickelt, um daie Erforschung der Kommunikation zu unterstützen (Shannon und Weaver, 1949)(3). (Shannon hat außerdem eines der frühesten Beispiele für maschinelles Lernen beigesteuert, eine mechanische Maus namens Theseus, die durch Versuch und Irrtum lernte, durch ein Labyrinth zu navigieren). Die χ2 Methode des Tree Pruning wurde von Quinlan (1986)(4) beschrieben. C4.5, ein industrielles Entscheidungsbaum-Paket, ist in Quinlan (1993)(5) zu finden. In der statistischen Literatur gibt es eine unabhängige Tradition des Lernens mit Entscheidungsbäumen. Classification and Regression Trees (Breiman et al., 1984)(6), bekannt als das "CART-Buch", ist die wichtigste Referenz.


1. Feigenbaum, E. A. (1961). The simulation of verbal learning behavior. Proc. Western Joint Computer
Conference, 19, 121-131.
2. Quinlan, J. R. (1979). Discovering rules from large collections of examples: A case study. In Michie,
D. (Ed.), Expert Systems in the Microelectronic Age. Edinburgh University Press.
3. Shannon, C. E. and Weaver, W. (1949). The Mathematical Theory of Communication. University of
Illinois Press.
4. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81-106.
5. Quinlan, J. R. (1993). C4.5: Programs for machine learning. Morgan Kaufmann.
6. Breiman, L., Friedman, J., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth International Group.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] ist eine Hinzufügung des Lexikons der Argumente.

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link
> Gegenargumente gegen Norvig

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z