Bagging

Was ist Bagging?

Bagging bezeichnet eine Abkürzung des Begriffs „Bootstrap Aggregating“ und stellt ein Verfahren zur Varianzreduktion bei Verwendung von verschiedenen Klassifikations- und Regressionsbäumen im Rahmen des maschinellen Lernens dar.

Neben dieser Erhöhung der Genauigkeit von Klassifikations- und Regressionsproblemen, wird Bagging auch genutzt, um das bekannte Problem des Overfitting zu lösen. Die Ergebnisse des Algorithmus sind besonders gut, wenn die einzelnen Lerner der Klassifikations- und Regressionsbäume instabil sind und eine hohe Varianz aufweisen.

Gemäß der Wortbestandteile wird bei dieser Methode das Bootstrap Aggregating in zwei Prozessschritten durchlaufen. Bootstrapping beschreibt grundsätzlich ein Verfahren in der Statistik, bei welcher wiederholt Zufallsstichproben aus einem definierten Datensatz gezogen werden, um eine unbekannte Verteilungsfunktion des Datensatzes zu identifizieren. Somit ist dieses Bootstrapping-Verfahren dem Resampling zuzuordnen, da auf Basis einer Stichprobe (Datensatz) wiederholt Unterstichproben gezogen werden. Diese einzelnen Stichproben werden anschließend mit dem Vorhersagemodell bzw. schwachen Klassifizierern trainiert und anschließend zu einem Vorhersagewert aggregiert.

Daraus leitet sich auch der Name Bootstrap Aggregating ab, indem Daten anfangs durch wiederholte Stichproben gezogen werden (mittels des Bootstrapping-Verfahrens) und anschließend die Vorhersagemodelle vereinigt (aggregiert) werden. Somit ist es möglich, dass diese Methodik zu einer Informationsfusion führt und sich dadurch die Klassifikations- bzw. Regressionsleistung erhöht.

Wie funktioniert die Ensemblemethode?

Bei einer Ensemblemethode bzw. dem Ensemble Learning spricht man grundsätzlich davon, wenn mehrere (schwache) Lerner bzw. Klassifizierer zusammengeschaltet und durchlaufen werden und dadurch ein sogenanntes Ensemble entsteht. Dahin gehend spricht man bei den Ensemblemethoden auch von einem Meta-Ansatz des maschinellen Lernens, da mehrere Modelle zu einem Vorhersagewert zusammengefasst werden.

Wie eingangs beschrieben, werden beim Bagging (Bootstrap Aggregating) mehrfach Stichproben eines Datensatzes gezogen und anschließend derselbe Algorithmus mit den Stichprobendaten parallel trainiert und getestet. Dabei werden im Regelfall Zufallsstichproben des Datensatzes gezogen, jedoch wäre es auch möglich, den gesamten Datensatz zu verteilen und daraus die Aufteilung der Daten zu generieren. Bei der Auswahl der Daten durch eine Zufallsstichprobe entspricht es dem Modell „Ziehen mit Zurücklegen“. Dies bedeutet, dass bestimmte Datenpunkte mehrfach (über mehrmalige zufällige Selektion) in das Modell einfließen können, andere hingegen gar nicht.

Nach der Generierung der Stichprobe erfolgt die Anwendung des Lernalgorithmus für jedes Ensemblemitglied. Dabei geschieht dies parallel zueinander. Abschließend werden die einzelnen Vorhersagemodelle aggregiert, wodurch ein endgültiger Ensemble-Klassifizierer entsteht. Die einzelnen Modelle bzw. Algorithmen können entweder mit gleich großen Gewichten in den Klassifizierer einfließen oder aber auch unterschiedlich hohe Gewichte besitzen.

Was unterscheidet Bagging von Boosting?

Neben dem Bagging stellt auch das sogenannte Boosting eine Ensemblemethode im maschinellen Lernen dar.

Dabei werden im Gegensatz zum Bagging die (schwachen) Klassifizierer nicht parallel durchlaufen, sondern sequenziell. Bei beiden dargestellten Methoden wird zu Beginn eine Basisstichprobe gezogen. Aufgrund der iterativen und sequenziellen Vorgehensweise der Ensemblemethode ist es möglich, dass die Erkenntnisse aus den vorherigen Schritten auf nachfolgende Schritte angewandt wird. Dies wird erreicht, indem falsch klassifizierte Iterationen anders gewichtet werden als richtig klassifizierte Iterationen.

Ziel von Boosting ist es, dass aus einer Vielzahl von schwachen Klassifizierern schlussendlich ein starker Klassifizierer entsteht. Während beim Bagging grundsätzlich auch Gewichte zur Anwendung kommen können, unterscheiden sich diese beim Boosting dahin gehend, dass ihre Größe vom bisherigen sequenziellen Fortschritt abhängen, während die Gewichte beim Bagging bereits im Vorhinein definiert werden, da der Prozess parallel abläuft.

Ein weiterer Unterschied zwischen den beiden Methoden besteht in der Zielsetzung. Das Ziel von Bagging besteht darin, durch Kombination die Varianz der einzelnen Klassifizierer zu reduzieren, während Boosting darauf abzielt, den systematischen Fehler bzw. die Verzerrung der Verteilung (=Bias) zu verringern. Dahin gehend kann Bagging dabei helfen, das Overfitting-Problem zu lösen, während dies beim Boosting keine Zielsetzung darstellt.

Beide Verfahren lassen sich mit Python umsetzen, wobei die scikit-learn-Bibliothek eine Implementierung für Ensemblemethoden bereitstellt und somit relativ einfach umgesetzt werden kann.

BERT

Was ist BERT?

BERT steht für „Bidirectional Encoder Representations from Transformers“ und beschreibt einen Algorithmus, welchen Google für Suchanfragen verwendet. Google entwickelt in ihren sogenannten Core-Updates den Algorithmus für Suchanfragen weiter, um immer bessere Suchergebnisse auf Suchanfragen der Nutzer zu erzielen.

BERT wurde Ende 2019 eingeführt und hat den Zweck, den Kontext der Suchanfrage besser zu verstehen. Dabei wurde ein besonderes Augenmerk auf Präpositionen und Füllwörter in der Suchanfrage gelegt, welche Google früher in Suchanfragen oftmals ignorierte. Neben dem Einsatz des Algorithmus wurden mit BERT auch sogenannte „Featured Snippets“ eingeführt. Dabei handelt es sich um hervorgehobene Suchergebnisse, welche dem Nutzer in Kurzform die Antwort auf die Suchanfrage liefern soll.

Da BERT auf die Sprach- und Texterkennung (Natural Language Understanding) sowie deren Verarbeitung abzielt, basiert der Algorithmus auf Natural Language Processing (NLP) im Gebiet der neuronalen Netze. NLP hat sich zum Ziel gesetzt, die natürliche menschliche Sprache für Computer verarbeitbar zu machen, sodass sie den Sinn der Sprache verstehen.

BERT nutzt ein Spezialgebiet im Bereich des maschinellen Lernens, das sogenannte Transfer Learning. Grundsätzlich fundieren Konzepte des maschinellen Lernens darauf, dass Trainings- und Testdaten aus demselben Merkmalsraum und derselben Verteilung stammen. Dies hat jedoch die Einschränkung, dass bei einer Änderung der Verteilung die ursprünglichen Trainingsdaten nicht weiter verwendet werden können. Beim Transfer Learning ist es jedoch möglich, dass Trainingsdaten aus einem „fachfremden“ Datensatz herangezogen und zur Lösungsfindung genutzt werden können. Dies reduziert die Anzahl der benötigten Trainingsdaten sowie gegebenenfalls auch die Trainingszeit. Während Transfer Learning ihren Ursprung in der Bilderkennung hat, nutzt BERT diese Methodik für die Textverarbeitung, da Suchanfragen sehr individuell gestellt werden und nicht immer spezifische Trainingsdaten vorhanden sind.

Wie ist das Sprachmodell aufgebaut und welche Funktionen umfasst es?

Das Sprachmodell BERT beruht auf Rechenmodellen, sogenannten Transformers, welche ein Wort jeweils in Beziehung zu allen anderen Wörtern eines Satzes stellt und so die Bedeutung besser zu verstehen versucht. Die Transformer funktionieren derart, indem Eingangssignale über sogenannte Encoder in eine verarbeitbare Form von Vektoren gebracht werden, mit welchen mathematische Operationen durchgeführt werden können. Im sogenannten „Self-Attention-Layer“ erfolgt die Gewichtung jedes Wortes der Eingabe anhand einer Werteskala. Diese Werteskala bewertet jedes Wort in Beziehung zu den anderen Worten der Eingabe. Die Werte werden anschließend normalisiert und mittels sogenannter Softmax-Funktion derart gewichtet, dass sich die Summe aller Werte auf 1 summiert. Anschließend werden diese an den nächsten Layer weitergeleitet.

Sowohl die Encoder als auch die Decoder sind als Feed-Forward-Neural-Network aufgebaut. Das bedeutet, dass es innerhalb der neuronalen Netze zu keiner Rückkoppelung zu vorherigen Schichten/Layern kommt, wie es bei rekurrenten Netzen der Fall ist. Im Decoder kommt es wieder zur Anwendung eines „Self-Attention-Layers“, zur Normalisierung der Werte sowie zur Zusammenführung mit den verarbeiteten Inputdaten im sogenannten „Encoder-Decoder-Attention-Layer“. Anschließend kommt es wiederum zur Implementierung eines neuronalen Feed-Forward-Netzes sowie zur Anwendung einer Linearisierung der Werte und der Softmax-Funktion, um schlussendlich die wahrscheinlichste Lösung auszugeben.

Auch BERT funktioniert wie die meisten Algorithmen auf Basis von Wahrscheinlichkeiten, auf welchen für die Lösungsfindung aufgesetzt wird.

Black Box

Was ist eine Black Box?

Als Black Box wird jedes System der eingesetzten künstlichen Intelligenz bezeichnet, dessen Eingaben und Operationen nicht sichtbar für den Benutzer sind. Allgemein handelt es sich bei einer Black Box um ein undurchdringliches System.

Bei Deep Learning wird in der Regel eine Black-Box-Entwicklung durchgeführt. So nimmt der Algorithmus Millionen von Datenpunkten entgegen, verarbeitet diese Eingabe und korreliert bestimmte Datenmerkmale, damit er eine Ausgabe erzeugen kann. Im Data Mining dagegen ist es ein Algorithmus oder auch eine Technologie, die keinerlei Erklärung für ihre Funktionsweise geben kann.

Ein Black-Box-Modell zur Entwicklung von Software mit künstlicher Intelligenz ist ein adäquates Entwicklungsmodell, um Software Bausteine zu testen. Dagegen spricht man bei Suchalgorithmen, Entscheidungsbäume und wissensbasierte Systeme, die von KI-Experten entwickelt wurden, transparent sind und nachvollziehbare Lösungswege bieten, von White-Box-Verfahren.

Eine Black Box im maschinellen Lernen ist ein Modell rein statistischer Art. White-Box-Modelle bezeichnen hingegen analytische und physikalische Beschreibungen, bei denen eine Modellierung häufig sehr aufwändig ist. Die Grey-Box-Modelle kombinieren schließlich beide Ansätze und können die jeweiligen Vorteile in sich vereinen.

Was sind typische Methoden?

Ein Black-Box-Test wird immer dann eingesetzt, wenn keine Kenntnisse der inneren Funktionsweise und Implementierung der Software vorhanden sind. Nur das nach außen sichtbare Verhalten fließt in den Test mit ein.

Ein erfolgreicher Test stellt dabei keinen ausreichenden Hinweis auf ein erfolgreiches und fehlerfreies System dar. So können eine nicht-geforderte Funktionalität oder eine massive Sicherheitslücke unerkannt bleiben. Ein Testverfahren genügt deshalb in aller Regel nicht aus, da Strukturtests keine fehlende Funktionalität erkennen können und Funktionstests nur unzureichend die vorliegende Implementierung berücksichtigen. Am besten ist ein kombiniertes Vorgehen von Funktionstests mit Grenzwertanalyse beziehungsweise Zufallstest, Strukturtests der Abschnitte welche nicht abgedeckt wurden und Regressionstests nach Fehlerkorrektur.

Funktionstests können die vorliegende Implementierung nur unzureichend berücksichtigen. Als Testmethoden gib es funktionale Tests (Black-Box-Test) mit einer Testfallauswahl, die auf einer Spezifikation beruht. So werden Äquivalenzklassentests durchgeführt, Grenzwerte berechnet und der Test über spezielle Werte eingegrenzt. Zustandstests können auf dieser Spezifikationsbasis umgesetzt werden.

Bag-of-Words-Modell

Was ist ein Bag-of-Words-Modell?

Ein Bag-of-Words-Modell ist eine vereinfachende Repräsentation, die in der Verarbeitung natürlicher Sprache und in der Informationsgewinnung verwendet wird. In diesem Modell wird ein Text als eine Tasche (bag) von seinen Worten repräsentiert, ohne die Grammatik und sogar ohne die Wortreihenfolge zu berücksichtigen, aber bei Beibehaltung der Vielzahl (multiplicity).

Eine Anwendung dieser Künstlichen Intelligenz ist die E-Mail-Filterung. Die Anzahl von gleichen Wörtern wird gespeichert. Es müssen die Wörter mit der höchsten Anzahl an Vorkommen, nicht die wichtigsten Wörter sein, denn häufig kommen „der“, „die“, „das“ und „ein“, „eine“ vor, ohne dass diese Wörter eine große Relevanz haben. Zum Zwecke einer Klassifizierung werden überwachte Alternativen entwickelt, um eine Klassenbezeichnung eines Dokumentes zu ergeben.

Es gibt ein Bigramm-Modell, in das der Text in Einheiten geparst wird. Es kann auch Hashing eingesetzt werden, um Speicher zu sparen. Weiter gibt es ein Bayes-Spam-Filter, bei dem die E-Mail-Nachricht in eine ungeordnete Sammlung von Wörtern aus zwei Wahrscheinlichkeitsverteilungen aufgeteilt wird. Die eine repräsentiert Spam und die andere legitimierte E-Mails, sogenannte „Ham“. So gibt es zwei Taschen voller Wörter. Die eine Tasche ist gefüllt mit Wörtern, die in Spam-Nachrichten enthalten sind und die andere mit Wörtern, die in legitimierten E-Mails vorhanden sind.

Was ist Bag-of-Words?

Bag-of-Words ist ein gewisser Weg, um Merkmale aus einem Text zu extrahieren, die dazu verwendet werden, diesen Text mit maschinellen Lernalgorithmen zu modellieren. Der Ansatz ist sehr einfach und flexibel. Er kann in vielfältigen Wegen genutzt werden, um Merkmale aus einem Dokument zu extrahieren.

Ein Bag-of-Words ist eine Repräsentation von Text, die die Häufigkeit von Wörtern innerhalb eines Dokuments beschreibt. Zum einen gibt es ein Vokabular von bekannten Wörtern, zum anderen gibt es eine Messung von vorhandenen bekannten Wörtern. Dieses Modell wird Tasche (bag) genannt, denn die Ordnung oder Struktur der Wörter wird weggelassen. Es wird lediglich betrachtet, ob ein Wort vorkommt, aber nicht wo es im Dokument steht.

Wie wird Text in Vektoren konvertiert?

Die Sprachmodellierung und Dokumentenklassifizierung kann ganz einfach mithilfe von Bag-of-Words Modellen geschehen. Maschinelles Lernen kann nicht direkt mit dem puren Text arbeiten, sondern es wird eine Konvertierung in Zahlen vorgenommen. Durch Zählen der Wortvorkommen und Hashing können die Sätze in Vektoren umgewandelt werden. Bag-of-Words ist eines der bekanntesten Verfahren, die zu einer Konstruktion von Feature-Räumen genutzt wird. Es werden im Zuge dieses Verfahrens Feature-Vektoren erzeugt.

Binärbaum

Was ist ein Binärbaum?

Ein Binärbaum ist ein spezieller Graph in Form eines sich verästelnden Baumes. Binärbäume haben die Besonderheit, dass ihre Knoten immer höchstens zwei Nachkommen aufweisen. Diese teilen sich systematisch in eine linken und einen rechten Teilbaum auf.

Mit dieser Methode werden Dateien in einer Datenbank platziert und aufgefunden. Der Algorithmus findet Daten, indem er die Anzahl der letztlich zugänglichen Datensätze wiederholt halbiert, bis nur noch einer übrig bleibt.

Wie funktioniert ein Binärbaum?

In einem Baum werden Datensätze an Orten gespeichert, die Blätter genannt werden. Dieser Name leitet sich von der Tatsache ab, dass Datensätze immer an den Endpunkten vorhanden sind; dahinter gibt es nichts. Die Verzweigungspunkte werden als Knoten bezeichnet. Die Ordnung eines Baumes ergibt sich aus der Anzahl der Zweige (Kinder genannt) pro Knoten. In einem binären Baum gibt es immer zwei Kinder pro Knoten, die Ordnung ist also 2. Die Anzahl der Blätter in einem binären Baum ist immer eine Potenz von 2. Die Anzahl der Zugriffsoperationen, die erforderlich sind, um den gewünschten Datensatz zu erreichen, wird als Tiefe des Baums bezeichnet.

In einem praktischen Baum kann es Tausende, Millionen oder Milliarden von Datensätzen geben. Nicht alle Blätter enthalten notwendigerweise einen Datensatz, aber mehr als die Hälfte schon. Ein Blatt, das keinen Datensatz enthält, wird als Null bezeichnet.

Eine der bekanntesten Programmiersprachen ist hierbei Java. In Java hat ein binärer Suchbaum eine knotenbasierte binäre Baumdatenstruktur, die die folgenden Eigenschaften aufweist: Der linke Teilbaum eines Knotens enthält nur Knoten, deren Schlüssel kleiner als der Schlüssel des Elternknotens ist und der rechte Teilbaum enthält dagegen nur Knoten mit größerem Schlüssel.

Welche Anwendungen haben Binärbäume?

Es gibt verschiedene Arten von Binärbäumen, mit einzigartigen Eigenschaften.:

  • Binäre Suchbäume stellen die relevantesten Vertreter der Binärbäume dar. Die Knoten in diesen Bäumen werden linear nach ihrem Schlüssel angeordnet. Mit ihrer Hilfe lassen sich in der Praxis effizientere Suchen umsetzen.
  • Volle Binärbäume sind eine spezielle Art von Binärbaum, der entweder keine oder zwei Kinder hat. Das bedeutet, dass alle Knoten in diesem Baum entweder zwei Kindknoten des Elternknotens haben oder der Elternknoten selbst der Blattknoten oder der externe Knoten ist. Mit anderen Worten: Bei einem vollen Binärbaum handelt es sich um einen eindeutigen Baum, in welchem jeglicher Knoten zwei Kinder hat, außer dem externen Knoten. Selbst wenn dieser lediglich ein einziges Kind besitzt, ist ein solcher binärer Baum kein vollständiger Binärbaum. Hier ist die Anzahl der Blattknoten gleich der Anzahl der inneren Knoten +1. Die Gleichung lautet: L=I+1, wobei L die Anzahl der Blattknoten und I die Anzahl der internen Knoten ist.
  • Ein vollständiger Binärbaum hat alle Ebenen des Baums vollständig mit Knoten gefüllt. Eine Ausnahme bildet hierbei die unterste Ebene des Baums. Auch in der letzten oder untersten Ebene dieses Baums sollte sich jeder Knoten möglichst auf der linken Seite befinden.
  • Partiell geordnete Binärbäume zeichnen sich durch die Tatsache aus, dass ihre Wurzel immer ein Minimum für den Knoten des Teilbaums darstellen. In Richtung ihrer Blätter nehmen die Werte der Knoten zu oder bleiben zumindest auf einem gleichen Niveau.
  • Ein Binärbaum wird als „perfekt“ bezeichnet, wenn alle internen Knoten genau zwei Kinder haben und jeder externe oder Blattknoten sich auf derselben Ebene oder Tiefe innerhalb eines Baumes befindet. Ein perfekter binärer Baum mit der Höhe ‚h‘ hat 2h – 1 Knoten.
  • Liegt Baumhöhe O(logN), wobei „N“ die Anzahl der Knoten ist, vor, wird von ausgewogenen Binärbäumen gesprochen. In diesen sollte die Höhe des linken und des rechten Teilbaums jedes Knotens höchstens um eins variieren. Ein AVL-Baum und ein Rot-Schwarz-Baum sind einige gängige Beispiele für Datenstrukturen, die einen ausgewogenen binären Suchbaum erzeugen können.
  • Bei degenerierten oder pathologischen Binärbäumen hat jeder interne Knoten nur ein einziges Kind. Solche Bäume ähneln in ihrer Leistung einer verketteten Liste.