Philosophie Lexikon der ArgumenteHome
| |||
|
| |||
| Entscheidungsbaum: Ein Entscheidungsbaum ist ein Modell des maschinellen Lernens, das einen baumartigen Graphen oder ein Modell von Entscheidungen und ihren möglichen Folgen verwendet, einschließlich zufälliger Ergebnisse, Ressourcenkosten und Nutzen. Er ist eine Möglichkeit, einen Algorithmus darzustellen, der nur bedingte Steueranweisungen enthält._____________Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente. | |||
| Autor | Begriff | Zusammenfassung/Zitate | Quellen |
|---|---|---|---|
|
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 ArgumenteDer Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" 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 |
||
> Gegenargumente gegen Norvig
> Gegenargumente zu Entscheidungsbaum ...
