Entscheidungsbaum

Was ist ein Entscheidungsbaum?

Ein Entscheidungsbaum stellt eine Vorgehensweise zur Klassifizierung von Objekten dar, auf Basis welcher Entscheidungen getroffen werden können. Anwendung finden Entscheidungsbäume vorwiegend auf dem Gebiet der Stochastik zur Darstellung von bedingten Wahrscheinlichkeiten, aber auch im Bereich des maschinellen Lernens sowie in der Entscheidungstheorie.

Die grafische Veranschaulichung von Entscheidungsbäumen kann mit sogenannten Baumdiagrammen umgesetzt werden, welche sich ausgehend vom Wurzelknoten bis zum Blatt alle Entscheidungsmöglichkeiten übersichtlich darstellen lässt.

Die übersichtliche Interpretierbarkeit und die Transparenz in der Darstellungsmöglichkeit sind mitunter als Vorteile von Entscheidungsbäumen zu nennen. Zudem sind sie relativ flexibel erweiterbar. Die gute Übersichtlichkeit bei kleinen Bäumen kann sich bei großen und komplexen Bäumen jedoch für die menschliche Betrachtung auch in das Gegenteil verkehren. Große Bäume, vor allem mit einer großen Tiefe, können relativ schnell unübersichtlich werden und den Rechenaufwand zur Analyse erhöhen. Des Weiteren ist es oftmals schwierig, alle Attribute bzw. Entscheidungsmöglichkeiten jedes einzelnen Knotens darzustellen und zu bewerten.

Methodik

Seinen Ursprung hat jeder Entscheidungsbaum immer im erwähnten Wurzelknoten. Ausgehend vom Wurzelknoten verzweigt sich der Baum zu weiteren Knoten, welche schlussendlich in einem Blatt bzw. der endgültigen Klassifikation endet. Bei den einzelnen Knoten wird zwischen Entscheidungsknoten und Zufallsknoten unterschieden. Entscheidungsknoten werden in der grafischen Veranschaulichung als Rechteck dargestellt und stellen eine Abfrage über ein Attribut dar, welches über den weiteren Verlauf entlang des Baumes und des Folgeknotens entscheidet.
Zufallsknoten werden als Kreis dargestellt und beschreiben den weiteren Verlauf des Baumes mit einer bestimmten Wahrscheinlichkeit. Das Ende des Entscheidungsbaumes wird als Blatt bezeichnet, oftmals als Dreieck dargestellt und stellt das Ergebnis der jeweiligen Klassifikationsaufgabe dar. Hat jeder Knoten des Baumes exakt zwei Attribute bzw. zwei mögliche Verzweigungen, spricht man von einem binären Entscheidungsbaum. Jeder Entscheidungsbaum kann auch als binärer Baum dargestellt werden.

Im Rahmen der Analyse bzw. Klassifikation von Datenobjekten wird stets im Wurzelknoten gestartet. Anschließend wird zu jedem Entscheidungsknoten ein Eingabevektor abgefragt und mit den Attributen des Entscheidungsknotens verglichen. Stimmt der Vektor mit einem Attribut überein, stellt dies den Pfad bis zum nächsten Folgeknoten im Entscheidungsbaum dar.
Bei Zufallsknoten wird auf Basis der vorliegenden bzw. angenommenen Wahrscheinlichkeiten der weitere Pfad und somit der nächste Folgeknoten ermittelt. Gemäß dieser Methodik wird fortgefahren, bis das Ende des Entscheidungsbaumes bzw. das letzte Blatt erreicht wird. Dies stellt sogleich das Ergebnis des Baumes oder die jeweilige Klassifizierung des Datenobjektes dar. Dabei kann es sich um einen monetären, numerischen, kardinalen oder nominalen Wert handeln, welcher zuvor gegebenenfalls zur besseren mathematischen Verarbeitungsmöglichkeit umcodiert werden kann.

Beispiel für einen Entscheidungsbaum im Machine Learning

Ein konkretes Beispiel für die Anwendung von Entscheidungsbäumen im Bereich des Machine Learnings stellt die Methodik des Random Forest dar. Bei diesem vom Statistiker Leo Breiman begründeten Algorithmus werden Entscheidungsbäume zur Lösung von Klassifikations- und Regressionsaufgaben angewendet.

Wie der Name Random Forest (engl. für Zufallswald) verrät, kommt nicht lediglich ein einziger Entscheidungsbaum zur Anwendung, sondern eine Vielzahl. Hierdurch entsteht ein „Wald“ an Entscheidungsbäumen. Die Bäume werden bei Random Forest zufällig und unkorreliert generiert. Bei der Erstellung der Bäume wird durch sogenanntes Bagging darauf geachtet, dass die einzelnen Bäume nicht zueinander korrelieren und somit die Qualität des Ergebnisses negativ beeinflussen.

Die Eingangsdaten werden bei der Anwendung des Algorithmus für die Vorhersage durch die sogenannte Ensemble-Methode oder das Ensemble Learning auf mehrere Entscheidungsbäume angewandt, um so ein qualitativ hochwertiges Ergebnis zu erzielen. Dieses Vorgehen hat gegenüber der Betrachtung von lediglich einem einzigen Entscheidungsbaum den Vorteil, dass Ausreißern in den einzelnen Bäumen entgegengesteuert wird und das Ergebnis somit dem Durchschnitt der einzelnen Bäume entspricht.

Effizienz eines Algorithmus

Was ist die Effizienz eines Algorithmus?

Ein Algorithmus ist dann besonders effizient, wenn er möglichst wenig Ressourcen benötigt, also kaum Rechenzeit und Speicherplatz, um ein festgelegtes Problem zu lösen. Die Effizienz eines Algorithmus lässt sich auf verschiedene Arten messen: so wird in aller Regel die Laufzeiteffizienz und die Speichereffizienz als wesentliche Kennzahl herangezogen. Diese ist besonders gut in absoluter und relativer Darstellung mess- und damit auch interpretier- beziehungsweise auswertbar.

In einer konkreten Implementierung einer bestimmten Programmiersprache kann die Effizienz als Abhängigkeit von Hardware und den Eingabedaten ermittelt werden. Es ist aber auch möglich, eine Effizienzbewertung unabhängig von der Bewertungsgröße und der Implementierung zu erstellen. Mit der Landau Notation kann die Effizienz eines Algorithmus ermittelt werden.

Auf welchem Konzept beruht diese Effizienz?

Für präzise mathematische Effizienzanalysen werden die zugrunde liegenden Daten und ein Rechenmodell benötigt. Es wird geklärt, welche Datentypen existieren, wie die Daten abgelegt werden und welche Operationen zulässig sind. Dann wird ermittelt, welche Zeit eine gewisse Operation auf einem definierten Datentyp benötigt. Es wird dazu eine Random Access Maschine mit einfachem aber „unbegrenzten“ Speicher genutzt. Die Effizienz stellt sich als Speicher-Effizienz (Speicheraufwand), Subjective-Effizienz (Erfassungsaufwand) und Laufzeit-Effizienz (Zeitaufwand) dar.

Algorithmen können vollständig hinsichtlich Korrektheit und Effizienz analysiert werden. So kann auch das Sortieren, Suchen und Optimieren betrachtet werden. Datenstrukturen weisen unterschiedliche Effizienz in der Ablage und dem Zugriff auf. Entscheidend für die Güte eines Algorithmus ist vor allem die Betrachtung von großen Eingaben. Für praktischen Nutzen muss immer berücksichtigt werden, ob die Eingabe groß oder eher doch klein ist. In der Theorie ist aber ein asymptotische Verhalten wichtig.

Die Effizienz wird maschinenunabhängig in der Anzahl von Rechenschritten angegeben. Man kann diese nach Anzahl der Vergleiche und Additionen oder anderer Rechenoperationen aufschlüsseln. Auch die Anzahl an Speicherplätzen kann angegeben werden. So kann das Konzept der Effizienz eines Algorithmus maschinenunabhängig betrachtet werden. In der Theorie wird häufig eine Turingmaschine eingesetzt, die ein Band besitzt, auf dem sich Ein- und Ausgabe aufzeichnen lässt. Das Band ist unendlich lang und es werden die einzelnen Rechenschritte betrachtet.

Edge Case

Was ist ein Edge Case?

Ein Edge Case wird auch Grenzfall oder Randfall genannt. Er beschreibt ein Szenario, in der sich ein Parameter in einer Extremsituation befindet. Diese Extreme können entweder im minimalen oder maximalen Bereich liegen.

In den meisten Fällen resultieren daraus Probleme und Fehlfunktionen, deshalb sollte ein Edge Case gefunden, getestet und behoben werden. Dafür werden in der Softwareentwicklung üblicherweise Unit-Tests genutzt. Diese prüfen die Randbedingungen einer Methode, einer Funktion oder von Algorithmen.

Durch die Kontrolle der korrekten Funktionsweise innerhalb der Extremen (den Rändern oder „Edges“), kann davon ausgegangen werden, dass auch die dazwischen liegenden Zustände funktionieren wird. Dadurch muss nicht jeder möglicherweise eintretende Fall kontrolliert werden. Wenn zum Beispiel eine Funktion 2 Zahlen addieren soll, reicht es aus, sie mit möglichst kleinen und großen Zahlen zu testen. Funktioniert alles dabei fehlerfrei, ist anzunehmen, dass die Funktion auch für alle Zahlen dazwischen ohne Probleme funktionieren wird. Durch diese Herangehensweise wird der Prozess des Testens möglichst effizient gehalten.

Was ist der Unterschied zwischen einem Edge Case und einem Corner Case?

Im Gegensatz zum Edge Case, bei dem eine Extremsituation nur bei einem Parameter auftritt, definiert der Corner Case eine Situation, in der sich mehrere Bedingungen in extremen Bereichen (minimal oder maximal) befinden.

Der Unterschied liegt also in der Anzahl der Betriebsparameter, welche sich in den Extremen bewegen und dadurch Probleme verursachen.

Ein Beispiel für einen Edge Case: Ein Drucker hat einen niedrigen Tintenstand und druckt den Text nicht mehr sauber. Die Eigenschaft „Tintenstand“ befindet sich im Minimum und der Drucker kann seine Aufgabe nicht richtig ausführen.

Beim Corner Case hingegen befinden sich mehrere Bedingungen im Extremfall: Der Drucker hat einen niedrigen Tintenstand, die Helligkeit ist auf Maximum gestellt und der Drucker steht auf einem wackeligen Untergrund. Erst das Zusammenspiel dieser 3 Parameter führt dazu, dass der Drucker nicht richtig funktioniert. Würde jede Bedingung einzeln auftreten, hätte der Drucker kein Problem. Die Ausgangssituationen bei beiden Fällen sind also unterschiedlich, doch führen sie meist zu demselben Ergebnis, nämlich einer Fehlfunktion. Da auch öfters gar nicht klar ist, ob ein Parameter allein oder mehrere im Zusammenspiel ein Problem verursachen, werden Edge Case und Corner Case oft als Synonym für einen auftretenden Fehler verwendet.

Entropie (Informationstheorie)

Was ist eine Entropie?

Eine Entropie stellt in der Informationstheorie ein Maß dar, welches für eine gewisse Nachrichtenquelle einen mittleren Informationsgehalt der ausgegebenen Nachrichten angibt. Das informationstheoretische Verständnis vom Begriff Entropie geht auf Claude Shannon zurück. Im Allgemeinen ist es so, dass, je mehr Zeichen von einer bestimmten Quelle empfangen werden, desto mehr Informationen werden gesammelt. Die Entropie sollte nach Shannon’s ursprünglicher Absicht, als das Maß einer benötigten Bandbreite von einem Übertragungskanal genutzt werden. Jedoch verallgemeinerte er die Erkenntnisse und entwarf einen Entropiezustand, der generell als das Maß des Informationsgehaltes anerkannt ist. Ist diese klein, dann enthält der Informationstext viele Redundanzen oder auch statistische Regelmäßigkeiten.

Die wichtigsten Zweige von Shannon’s Informationstheorie umfassen die Kodierung von Informationen, das quantitative Maß, das für die Redundanz eines Textes gilt, die Datenkompression und die Kryptografie. Die Informationstheorie ist eine Theorie, welche darauf abzielt, dass der Informationsgehalt eines Datensatzes quantifiziert und qualifiziert wird.

Welche Aspekte ergeben sich in der Informatik?

Shannon verstand die Entropie in der Informatik als ein Maß für Information und damit konnte er Thermodynamik mit Informationstheorie verbinden. Daraus ergaben sich neue Aspekte und Methoden:

  • Die Kreuzentropie ist ein Maß für Modellqualität. Sie berechnet die Gesamtentropie zwischen den Verteilungen. Die Kreuzentropie wird üblicherweise beim maschinellen Lernen als eine Verlustfunktion genutzt. Die Kreuzentropie kann als ein Maß aufgefasst werden, welches aus dem Bereich der Informationstheorie stammt und das auf Entropiezuständen aufbaut.
  • Die Kullback-Leibler-Divergenz ist ein gewisses Distanzmaß zwischen zwei verschiedenen Modellen. Angewandt wird das intrinsische Maß für Schwierigkeit und Qualität beim maschinellen Lernen.
  • Die Entropieveränderung (Information gain) wird als Kriterium im Feature Engineering eingesetzt.
  • Die Cross-Entropy-Minimization wird als Methode der Modelloptimierung verwendet.
  • Eine weitere Rolle spielt der bedingte Entropiezustand (conditional entropy), bei dem geklärt wird, wie viel Entropiezustand in einer Zufallsvariablen übrig bleibt, bei Kenntnis von einer anderen Zufallsvariablen.
  • Die Verbundsentropie (Joint entropy) macht Aussagen darüber, wie viel Bits benötigt werden, um beide Zufallsvariablen richtig zu enkodieren.
  • Letztlich gibt es eine ganze Entropie-Algebra, bei der zwischen marginalen, bedingten und gemeinsamen Entropiezuständen hin- und herumgerechnet werden kann.

Wie wird die Entropie beim maschinellen Lernen genutzt?

Die Entropie im maschinellen Lernen ist das häufigste eingesetzte Maß für die Unreinheit (Impurity) in der ganzen Informatik. Er liegt bei Wahrscheinlichkeiten größer 0 und gleichzeitig kleiner 1. Der Entropiezustand ist maximal, wenn zwei Klassen 1.00 erreichen und diese Klassen innerhalb einer Obermenge mit identischer Häufigkeit vorkommen. Sollte eine Klasse dabei eine quantitative Dominanz gewinnen, dann steigt die Wahrscheinlichkeit, für solch eine Klasse gleichermaßen an und daraufhin sinkt der Entropiezustand. Beim maschinellen Lernen macht die Entropie Aussagen darüber, wie schwierig das Vorhersagen eines Ereignisses ist.

Evolutionärer Algorithmus

Was ist ein Evolutionärer Algorithmus?

Ein Evolutionärer Algorithmus orientiert sich an den Vorstellungen aus der biologischen Evolution und an deren Entwicklungsmuster. Es handelt es sich um ein Optimierungsverfahren, das neue Ansätze und Lösungen zu bestimmten Problemen finden kann. Evolutionärer Algorithmen werden auch als genetische Algorithmen bezeichnet.

Solch ein Verfahren eignet sich hervorragend für komplexere Probleme. So können in einer Simulation ganze Individuen geschaffen werden und diese erhalten eine sogenannte Fitnessfunktion mit Tauglichkeitswerten. Über diesen Tauglichkeitswert wird Aufschluss darüber gegeben, wie gut ein solches Individuum das entsprechende Problem lösen kann. Danach wird selektiert, wobei die am besten angepassten Individuen „überleben“.

Bei dem ganzen Prozess gelten zwei wichtige Elemente als Voraussetzung für eine Verbesserung, nämlich eine Rekombination und eine Mutation. Die stärksten Eigenschaften werden durch den Prozess gesichert und die KI nähert sich der optimalen Lösung an. Veränderungen werden immer kleiner und können sich sogar einstellen, sobald das Maximum erreicht ist. Dieser Prozess kann vorher manuell unterbrochen werden, um so das Problem einer Überanpassung zu umgehen.

Was ist der Unterschied zwischen Evolutionären Algorithmen und Backpropagation?

Evolutionäre Algorithmen sind eine Alternative zur Backpropagation. Bei der Backpropagation wird ein Gradientenverfahren eingesetzt, um die Ergebnisse stetig zu verbessern. Zum Einsatz kommen dabei eine Fehleranalyse und eine Ursachenforschung. Danach wird immer weiter justiert. Evolutionäre Algorithmen verhalten sich wesentlich „zufälliger“ bei einer Änderung der Gewichtungsparameter.

Backpropagation wird im Rahmen von überwachtem Lernen eingesetzt. Evolutionäre Algorithmen können hingegen auch im unüberwachten Lernen, bei der Mustererkennung und beim Reinforcement Learning genutzt werden.

Wo kommen Evolutionären Algorithmen zur Anwendung?

Evolutionäre Algorithmen können über Optimierung und Suche hinaus eingesetzt werden. So kommen sie in der Kunst, der Modellierung und in der Simulation zur Anwendung. Weitere Anwendungsfelder sind die Entwicklung von Sensornetzen, die Aktienmarktanalyse und das Vorhersagen von RNA-Strukturen.

In der Kombinatorik ist aufgrund des hohen Rechenaufwandes nicht immer eine optimale Lösung herzuleiten. Für solche Optimierungen werden häufig Heuristiken eingesetzt. Wichtig für den Einsatz von Evolutionären Algorithmen sind die Fitnessfunktion, die Mutation und die Variation, mit denen Generationen neuer Elemente berechnet werden können.