Data Dimensionality Reduction Series: Random Forest

Hello lovely individuals, I hope everyone is doing well, is fantastic, and is smiling more than usual. In this blog we shall discuss a very interesting term used to build many models in the Data science industry as well as the cyber security industry.

SUPER BASIC DEFINITION OF RANDOM FOREST:

Random forest is a form of Supervised Machine Learning Algorithm that operates on the majority rule. For example, if we have a number of different algorithms working on the same issue but producing different answers, the majority of the findings are taken into account. Random forests, also known as random selection forests, are an ensemble learning approach for classification, regression, and other problems that works by generating a jumble of decision trees during training.

When it comes to regression and classification, random forest can handle both categorical and continuous variable data sets. It typically helps us outperform other algorithms and overcome challenges like overfitting and the curse of dimensionality.

QUICK ANALOGY TO UNDERSTAND THINGS BETTER:

Uncle John wants to see a doctor for his acute abdominal discomfort, so he goes to his pals for recommendations on the top doctors in town. After consulting with a number of friends and family members, Atlas chooses to visit the doctor who received the highest recommendations.

So, what does this mean? The same is true for random forests. It builds decision trees from several samples and utilises their majority vote for classification and average for regression.

HOW BIAS AND VARIANCE AFFECTS THE ALGORITHM?

  1. BIAS
  • The algorithm’s accuracy or quality is measured.
  • High bias means a poor match
  1. VARIANCE
  • The accuracy or specificity of the match is measured.
  • A high variance means a weak match

We would like to minimise each of these. But, unfortunately we can’t do this independently, since there is a trade-off

EXPECTED PREDICTION ERROR = VARIANCE + BIAS^2 + NOISE^2

Bias vs Variance Tradeoff

HOW IS IT DIFFERENT FROM OTHER TWO ALGORITHMS?

Every other data dimensionality reduction method, such as missing value ratio and principal component analysis, must be built from the scratch, but the best thing about random forest is that it comes with built-in features and is a tree-based model that uses a combination of decision trees for non-linear data classification and regression.

Without wasting much time, let’s move to the main part where we’ll discuss the working of RANDOM FOREST:

WORKING WITH RANDOM FOREST:

As we saw in the analogy, RANDOM FOREST operates on the basis of ensemble technique; however, what precisely does ensemble technique mean? It’s actually rather straightforward. Ensemble simply refers to the combination of numerous models. As a result, rather than a single model, a group of models is utilised to create predictions.

ENSEMBLE TECHNIQUE HAS 2 METHODS:

Ensemble Learning: Bagging and Boosting

1] BAGGING

2] BOOSTING

Let’s dive deep to understand things better:

1] BAGGING:

LET’S UNDERSTAND IT THROUGH A BETTER VIEW:

Bagging simply helps us to reduce the variance in a loud datasets. It works on an ensemble technique.

  1. Algorithm independent : general purpose technique
  2. Well suited for high variance algorithms
  3. Variance reduction is achieved by averaging a group of data.
  4. Choose # of classifiers to build (B)

DIFFERENT TRAINING DATA:

  1. Sample Training Data with Replacement
  2. Same algorithm on different subsets of training data

APPLICATION :

  1. Use with high variance algorithms (DT, NN)
  2. Easy to parallelize
  3. Limitation: Loss of Interpretability
  4. Limitation: What if one of the features dominates?

SUMMING IT ALL UP:

  1. Ensemble approach = Bootstrap Aggregation.
  2. In bagging a random dataset is selected as shown in the above figure and then a model is built using those random data samples which is termed as bootstrapping.
  3. Now, when we train this random sample data it is not mendidate to select data points only once, while training the sample data we can select the individual data point more then once.
  4. Now each of these models is built and trained and results are obtained.
  5. Lastly the majority results are being considered.

We can even calculate  the error from this thing know as random forest OOB error:

RANDOM FORESTS: OOB ERROR  (Out-of-Bag Error) :

▪ From each bootstrapped sample, 1/3rd of it is kept aside as “Test”

▪ Tree built on remaining 2/3rd

▪ Average error from each of the “Test” samples is called “Out-of-Bag Error”

▪ OOB error provides a good estimate of model error

▪ No need for separate cross validation

2] BOOSTING:

Boosting in short helps us to improve our prediction by reducing error in predictive data analysis.

Weak Learner: only needs to generate a hypothesis with a training accuracy greater than 0.5, i.e., < 50% error over any distribution.

KEY INTUITION:

  1. Strong learners are very difficult to construct
  2. Constructing weaker Learners is relatively easy influence with the empirical squared improvement when assigned to the model

APPROACH OUTLINE:

  1. Start with a ML algorithm for finding the rough rules of thumb (a.k.a. “weak” or “base” algorithm)
  2. Call the base algorithm repeatedly, each time feeding it a different subset of the training examples
  3. The basic learning algorithm creates a new weak prediction rule each time it is invoked.
  4. After several rounds, the boosting algorithm must merge these weak rules into a single prediction rule that, hopefully, is considerably more accurate than any of the weak rules alone.

TWO KEY DETAILS :

  1. In each round, how is the distribution selected ?
  2. What is the best way to merge the weak rules into a single rule?

BOOSTING is classified into two types:

1] ADA BOOST

2] XG BOOST

As far as the Random forest is concerned it is said that it follows the bagging method, not a boosting method. As the name implies, boosting involves learning from others, which in turn increases learning. Random forests have trees that run in parallel. While creating the trees, there is no interaction between them.

Boosting helps us reduce the error by decreasing the bias whereas, on other hand, Bagging is a manner to decrease the variance within the prediction with the aid of generating additional information for schooling from the dataset using mixtures with repetitions to provide multi-sets of the original information.

How Bagging helps with variance – A Simple Example

BAGGED TREES

  1. Decision Trees have high variance
  2. The resultant tree (model) is determined by the training data.
  3. (Unpruned) Decision Trees tend to overfit
  4. One option: Cost Complexity Pruning

BAG TREES

  1. Sample with replacement (1 Training set → Multiple training sets)
  2. Train model on each bootstrapped training set
  3. Multiple trees; each different : A garden ☺
  4. Each DT predicts; Mean / Majority vote prediction
  5. Choose # of trees to build (B)

ADVANTAGES

Reduce model variance / instability.

RANDOM FOREST : VARIABLE IMPORTANCE

VARIABLE IMPORTANCE :

▪ Each time a tree is split due to a variable m, Gini impurity index of the parent node is higher than that of the child nodes

▪ Adding up all Gini index decreases due to variable m over all trees in the forest, gives a measure of variable importance

IMPORTANT FEATURES AND HYPERPARAMETERS:

  1. Diversity :
  2. Immunity to the curse of dimensionality :
  3. Parallelization :
  4. Train-Test split :
  5. Stability :
  6. Gini significance (or mean reduction impurity) :
  7. Mean Decrease Accuracy :

FEATURES THAT IMPROVE THE MODEL’S PREDICTIONS and SPEED :

  1. maximum_features :

Increasing max features often increases model performance since each node now has a greater number of alternatives to examine.

  1. n_estimators :

The number of trees you wish to create before calculating the maximum voting or prediction averages. A greater number of trees improves speed but slows down your code.

  1. min_sample_leaf :

If you’ve ever designed a decision tree, you’ll understand the significance of the minimal sample leaf size. A leaf is the decision tree’s last node. A smaller leaf increases the likelihood of the model collecting noise in train data.

  1. n_jobs :

This option instructs the engine on how many processors it is permitted to utilise.

  1. random_state :

This argument makes it simple to duplicate a solution. If given the same parameters and training data, a definite value of random state will always provide the same results.

  1. oob_score:

A random forest cross validation approach is used here. It is similar to the leave one out validation procedure, except it is significantly faster.

LET’S SEE THE STEPS INVOLVED IN IMPLEMENTATION OF RANDOM FOREST ALGORITHM:

Step1: Choose T- number of trees to grow

Step2: Choose m<p (p is the number of total features) —number of features used to calculate the best split at each node (typically 30% for regression, sqrt(p) for classification)

Step3: For each tree, choose a training set by choosing N times (N is the number of training examples) with replacement from the training set

Step4: For each node, calculate the best split, Fully grown and not pruned.

Step5: Use majority voting among all the trees

Following is a full case study and implementation of all the principles we just covered, in the form of a jupyter notebook including every concept and all you ever wanted to know about RANDOM FOREST.

GITHUB Repository for this blog article: https://gist.github.com/Vidhi1290/c9a6046f079fd5abafb7583d3689a410

Haufe Akademie Data Science Buzzword Bingo

Buzzword Bingo: Data Science – Teil III

Im ersten Teil unserer Serie „Buzzword Bingo: Data Science“ widmeten wir uns den Begriffen Künstliche Intelligenz, Algorithmen und Maschinelles Lernen, im zweiten Teil den Begriffen Big Data, Predictive Analytics und Internet of Things. Nun geht es hier im dritten und letzten Teil weiter mit der Begriffsklärung dreier weiterer Begriffe aus dem Data Science-Umfeld.

Buzzword Bingo: Data Science – Teil III: Künstliche neuronale Netze & Deep Learning

Im dritten Teil unserer dreiteiligen Reihe „Buzzword Bingo Data Science“ beschäftigen wir uns mit den Begriffen „künstliche neuronale Netze“ und „Deep Learning“.

Künstliche neuronale Netze

Künstliche neuronale Netze beschreiben eine besondere Form des überwachten maschinellen Lernens. Das Besondere hier ist, dass mit künstlichen neuronalen Netzen versucht wird, die Funktionsweise des menschlichen Gehirns nachzuahmen. Dort können biologische Nervenzellen durch elektrische Impulse von benachbarten Neuronen erregt werden. Nach bestimmten Regeln leiten Neuronen diese elektrischen Impulse dann wiederum an benachbarte Neuronen weiter. Häufig benutzte Signalwege werden dabei verstärkt, wenig benutzte Verbindungen werden gleichzeitig im Laufe der Zeit abgeschwächt. Dies wird beim Menschen üblicherweise dann als Lernen bezeichnet.

Dasselbe geschieht auch bei künstlichen neuronalen Netzen: Künstliche Neuronen werden hier hinter- und nebeneinander geschaltet. Diese Neuronen nehmen dann Informationen auf, modifizieren und verarbeiten diese nach bestimmten Regeln und geben dann Informationen wiederum an andere Neuronen ab. Üblicherweise werden bei künstlichen neuronalen Netzen mindestens drei Schichten von Neuronen unterschieden.

  • Die Eingabeschicht nimmt Informationen aus der Umwelt auf und speist diese in das neuronale Netz ein.
  • Die verborgene(n) Schichte(n) liegen zwischen der Eingabe- und der Ausgabeschicht. Hier werden wie beschrieben die eingegebenen Informationen von den einzelnen Neuronen verarbeitet und anschließend weitergegeben. Der Name „verborgene“ Schicht betont dabei, dass für Anwender meist nicht erkennbar ist, in welcher Form ein neuronales Netz die Eingabeinformationen in den verborgenen Schichten verarbeitet.
  • Die letzte Schicht eines neuronalen Netzes ist die Ausgabeschicht. Diese beinhaltet die Ausgabeneuronen, welche die eigentliche Entscheidung, auf die das neuronale Netz trainiert wurde, als Information ausgeben.

Das besondere an neuronalen Netzen: Wie die Neuronen die Informationen zwischen den verborgenen Schichten verarbeiten und an die nächste Schicht weitergeben, erlernt ein künstliches neuronales Netz selbstständig. Hierfür werden – einfach ausgedrückt – die verschiedenen Pfade durch ein neuronales Netz, die verschiedene Entscheidungen beinhalten, häufig hintereinander ausprobiert. Führt ein bestimmter Pfad während des Trainings des neuronalen Netzes nicht zu dem vordefinierten korrekten Ergebnis, wird dieser Pfad verändert und in dieser Form zukünftig eher nicht mehr verwendet. Führt ein Pfad stattdessen erfolgreich zu dem vordefinierten Ergebnis, dann wird dieser Pfad bestärkt. Schlussendlich kann, wie bei jedem überwachten Lernprozess, ein erfolgreich trainiertes künstliches neuronales Netz auf unbekannte Eingangsdaten angewandt werden.

Auch wenn diese Funktionsweise auf den ersten Blick nicht sehr leicht verständlich ist: Am Ende handelt es sich auch hier bloß um einen Algorithmus, dessen Ziel es ist, Muster in Daten zu erkennen. Zwei Eigenschaften teilen sich künstliche neuronale Netze aber tatsächlich mit den natürlichen Vorbildern: Sie können sich besonders gut an viele verschiedene Aufgaben anpassen, benötigen dafür aber auch meistens mehr Beispiele (Daten) und Zeit als die klassischen maschinellen Lernverfahren.

Sonderform: Deep Learning

Deep Learning ist eine besondere Form von künstlichen neuronalen Netzen. Hierbei werden viele verdeckte Schichten hintereinander verwendet, wodurch ein tiefes (also „deep“) neuronales Netz entsteht.

Je tiefer ein neuronales Netz ist, umso komplexere Zusammenhänge kann es abbilden. Aber es benötigt auch deutlich mehr Rechenleistung als ein flaches neuronales Netz. Seit einigen Jahren steht diese Leistung günstig zur Verfügung, weshalb diese Form des maschinellen Lernens an Bedeutung gewonnen hat.

Die 6 Schritte des Process Mining – Infografik

Viele Process Mining Projekte drehen sich vor allem um die Auswahl und die Einführung der richtigen Process Mining Tools. Egal ob mit Celonis, Signavio, UiPath oder einem anderem Software-Anbieten, Process Mining ist nicht irgendein Tool, sondern eine Methodik der Aufbereitung und Analyse der Daten. Im Kern von Process Mining steckt eigentlich eine Graphenanalyse, die Prozessschritte als Knoten (Event) und Kanten (Zeiten) darstellt. Hinzu kommen weitere Darstellungen mit einem fließenden Übergang in die Business Intelligence, so bieten andere Tool-Anbieter auch Plugins für Power BI, Tableau, Qlik Sense und andere BI-Tools, um Process Mining zu visualisieren.

Unternehmen können Event Logs selbst herstellen und in ein Data Warehouse speisen, die dann alle Process Mining Tools mit Prozessdaten versorgen können. Die investierten Aufwände in Process Mining würden somit nachhaltiger (weil länger nutzbar) werden und die Abhängigkeit von bestimmter Software würde sich auf ein Minimum reduzieren, wir riskieren keinen neuen Aufwand für Migration von einem Anbieter zum nächsten. Übrigens können die Event Logs dann auch in andere Tools z. B. für Business Intelligence (BI) geladen und anderweitig analysiert werden.

Jedoch ganz unabhängig von den Tools, gibt es eine ganz generelle Vorgehensweise in dieser datengetriebenen Prozessanalyse, die wir mit der folgenden Infografik beschreiben möchten.

DATANOMIQ Process Mining - 6 Steps of Doing Process Mining Analysis

6 Steps of Process Mining – Infographic PDF Download.

DATANOMIQ ist der herstellerunabhängige Beratungs- und Service-Partner für Business Intelligence, Process Mining und Data Science. Wir erschließen die vielfältigen Möglichkeiten durch Big Data und künstliche Intelligenz erstmalig in allen Bereichen der Wertschöpfungskette. Dabei setzen wir auf die besten Köpfe und das umfassendste Methoden- und Technologieportfolio für die Nutzung von Daten zur Geschäftsoptimierung.

Data Science & Big Data

Buzzword Bingo: Data Science – Teil II

Im ersten Teil unserer Serie „Buzzword Bingo: Data Science“ widmeten wir uns den Begriffen Künstliche Intelligenz, Algorithmen und Maschinelles Lernen. Nun geht es hier im zweiten Teil weiter mit der Begriffsklärung dreier weiterer Begriffe aus dem Data Science-Umfeld.

Buzzword Bingo: Data Science – Teil II: Big Data, Predictive Analytics & Internet of Things

Im zweiten Teil unserer dreiteiligen Reihe „Buzzword Bingo Data Science“ beschäftigen wir uns mit den Begriffen „Big Data“, „Predictive Analytics“ und „Internet of Things“.

Big Data

Interaktionen auf Internetseiten und in Webshops, Likes, Shares und Kommentare in Social Media, Nutzungsdaten aus Streamingdiensten wie Netflix und Spotify, von mobilen Endgeräten wie Smartphones oder Fitnesstrackern aufgezeichnete Bewegungsdate oder Zahlungsaktivitäten mit der Kreditkarte: Wir alle produzieren in unserem Leben alltäglich immense Datenmengen.

Im Zusammenhang mit künstlicher Intelligenz wird dabei häufig von „Big Data“ gesprochen. Und weil es in der öffentlichen Diskussion um Daten häufig um personenbezogene Daten geht, ist der Begriff Big Data oft eher negativ konnotiert. Dabei ist Big Data eigentlich ein völlig wertfreier Begriff. Im Wesentlichen müssen drei Faktoren erfüllt werden, damit Daten als „big“ gelten. Da die drei Fachbegriffe im Englischen alle mit einem „V“ beginnen, wird häufig auch von den drei V der Big Data gesprochen.

Doch welche Eigenschaften sind dies?

  • Volume (Datenmenge): Unter Big Data werden Daten(-mengen) verstanden, die zu groß sind, um sie mit klassischen Methoden zu bearbeiten, weil beispielsweise ein einzelner Computer nicht in der Läge wäre, diese Datenmenge zu verarbeiten.
  • Velocity (Geschwindigkeit der Datenerfassung und -verarbeitung): Unter Big Data werden Daten(-mengen) verstanden, die in einer sehr hohen Geschwindigkeit generiert werden und dementsprechend auch in einer hohen Geschwindigkeit ausgewertet und weiterverarbeitet werden müssen, um Aktualität zu gewährleisten.
  • Variety (Datenkomplexität oder Datenvielfalt): Unter Big Data werden Daten(-mengen) verstanden, die so komplex sind, dass auf den ersten Blick keine Zusammenhänge erkennbar sind. Diese Zusammenhänge können erst mit speziellen maschinellen Lernverfahren aufgedeckt werden. Dazu gehört auch, dass ein Großteil aller Daten in unstrukturierten Formaten wie Texten, Bildern oder Videos abgespeichert ist.

Häufig werden neben diesen drei V auch weitere Faktoren aufgezählt, welche Big Data definieren. Dazu gehören Variability (Schwankungen, d.h. die Bedeutung von Daten kann sich verändern), Veracity (Wahrhaftigkeit, d.h. Big Data muss gründlich auf die Korrektheit der Daten geprüft werden), Visualization (Visualisierungen helfen, um komplexe Zusammenhänge in großen Datensets aufzudecken) und Value (Wert, d.h. die Auswertung von Big Data sollte immer mit einem unternehmerischen Vorteil einhergehen).

Predictive Analytics

  • Heute schon die Verkaufszahlen von morgen kennen, sodass eine rechtzeitige Nachbestellung knapper Produkte möglich ist?
  • Bereits am Donnerstagabend die Regenwahrscheinlichkeit für das kommende Wochenende kennen, sodass passende Kleidung für den Kurztrip gepackt werden kann?
  • Frühzeitig vor bevorstehenden Maschinenausfällen gewarnt werden, sodass die passenden Ersatzteile bestellt und das benötigte technische Personal angefragt werden kann?

Als Königsdisziplin der Data Science gilt für viele die genaue Vorhersage zukünftiger Zustände oder Ereignisse. Im Englischen wird dann von „Predictive Analytics“ gesprochen. Diese Methoden werden in vielen verschiedenen Branchen und Anwendungsfeldern genutzt. Die Prognose von Absatzzahlen, die Wettervorhersage oder Predictive Maintenance (engl. für vorausschauende Wartung) von Maschinen und Anlagen sind nur drei mögliche Beispiele.

Zu beachten ist allerdings, dass Predictive-Analytics-Modelle keine Wahrsagerei sind. Die Vorhersage zukünftiger Ereignisse beruht immer auf historischen Daten. Das bedeutet, dass maschinelle Modelle mit Methoden des überwachten maschinellen Lernens darauf trainiert werden, Zusammenhänge zwischen vielen verschiedenen Eingangseigenschaften und einer vorherzusagenden Ausgangseigenschaft zu erkennen. Im Falle der Predicitve Maintenance könnten solche Eingangseigenschaften beispielsweise das Alter einer Produktionsmaschine, der Zeitraum seit der letzten Wartung, die Umgebungstemperatur, die Produktionsgeschwindigkeit und viele weitere sein. In den historischen Daten könnte ein Algorithmus nun untersuchen, ob diese Eingangseigenschaften einen Zusammenhang damit aufweisen, ob die Maschine innerhalb der kommenden 7 Tage ausfallen wird. Hierfür muss zunächst eine ausreichend große Menge an Daten zur Verfügung stehen. Wenn ein vorherzusagendes Ereignis in der Vergangenheit nur sehr selten aufgetreten ist, dann stehen auch nur wenige Daten zur Verfügung, um dasselbe Ereignis für die Zukunft vorherzusagen. Sobald der Algorithmus einen entsprechenden Zusammenhang identifiziert hat, kann dieses trainierte maschinelle Modell nun verwendet werden, um zukünftige Maschinenausfälle rechtzeitig vorherzusagen.

Natürlich müssen solche Modelle dauerhaft darauf geprüft werden, ob sie die Realität immer noch so gut abbilden, wie zu dem Zeitpunkt, zu dem sie trainiert worden sind. Wenn sich nämlich die Umweltparameter ändern, das heißt, wenn Faktoren auftreten, die zum Trainingszeitpunkt noch nicht bekannt waren, dann muss auch das maschinelle Modell neu trainiert werden. Für unser Beispiel könnte dies bedeuten, dass wenn die Maschine für die Produktion eines neuen Produktes eingesetzt wird, auch für dieses neue Produkt zunächst geprüft werden müsste, ob die in der Vergangenheit gefundenen Zusammenhänge immer noch Bestand haben.

Internet of Things

Selbstfahrende Autos, smarte Kühlschränke, Heizungssysteme und Glühbirnen, Fitnesstracker und vieles mehr: das Buzzword „Internet of Things“ (häufig als IoT abgekürzt) beschreibt den Trend, nicht nur Computer über Netzwerke miteinander zu verbinden, sondern auch verschiedene alltägliche Objekte mit in diese Netzwerke aufzunehmen. Seinen Anfang genommen hat dieser Trend in erster Linie im Bereich der Unterhaltungselektronik. In vielen Haushalten sind schon seit Jahren Fernseher, Computer, Spielekonsole und Drucker über das Heimnetzwerk miteinander verbunden und lassen sich per Smartphone bedienen.

Damit ist das IoT natürlich eng verbunden mit Big Data, denn all diese Geräte produzieren nicht nur ständig Daten, sondern sie sind auch auf Informationen sowie auf Daten von anderen Geräten angewiesen, um zu funktionieren.

Buzzword Bingo: Data Science – Teil I

Rund um das Thema Data Science gibt es unglaublich viele verschiedene Buzzwords, die Ihnen sicherlich auch schon vielfach begegnet sind. Sei es der Begriff Künstliche Intelligenz, Big Data oder auch Deep Learning. Die Bedeutung dieser Begriffe ist jedoch nicht immer ganz klar und häufig werden Begriffe auch vertauscht oder in missverständlichen Zusammenhängen benutzt. Höchste Zeit also, sich einmal mit den genauen Definitionen dieser Begriffe zu beschäftigen!

Buzzword Bingo: Data Science – Teil 1: Künstliche Intelligenz, Algorithmen & Maschinelles Lernen

Im ersten Teil unserer dreiteiligen Reihe „Buzzword Bingo Data Science“ beschäftigen wir uns zunächst mit den drei Begriffen „Künstliche Intelligenz“, „Algorithmus“ und „Maschinelles Lernen“.

Künstliche Intelligenz

Der im Bereich der Data Science u. a. am häufigsten genutzte Begriff ist derjenige der „Künstlichen Intelligenz“. Viele Menschen denken bei dem Begriff sofort an hochspezialisierte Maschinen à la „The Matrix“ oder „I, Robot“. Dabei ist der Begriff deutlich älter als viele denken. Bereits 1956 wurde der englische Begriff “artificial intelligence” zum ersten Mal in einem Workshop-Titel am US-amerikanischen Dartmouth College genutzt.

Heutzutage besitzt der Begriff der künstlichen Intelligenz keine allgemeingültige Definition. Es handelt sich bei künstlicher Intelligenz grundsätzlich um ein Teilgebiet der Informatik, das sich mit der Automatisierung von intelligentem Verhalten befasst. Es geht also darum, dass ein Computerprogramm auf eine Eingabe eine intelligente Reaktion zeigt. Zu beachten ist hierbei, dass eine künstliche Intelligenz nur ein scheinbar intelligentes Verhalten zeigen kann. Künstliche Intelligenz wird heutzutage sehr weit gefasst und kann vieles umfassen: von klassischen, regelbasierten Algorithmen bis hin zu selbstlernenden künstlichen neuronalen Netzen.

Das zentrale Forschungsziel ist die Entwicklung einer sogenannten Allgemeinen Künstlichen Intelligenz, also einer Maschine, die in der Lage sein wird, autonom beliebige Probleme zu lösen. Es gibt eine fortlaufende Debatte darüber, ob dieses Ziel jemals erreicht werden kann bzw. ob es erreicht werden sollte.

In den vergangenen Jahren ist auch die sogenannte xAI (engl. Explainable AI; erklärbare künstliche Intelligenz) in den Mittelpunkt der Forschungsinteressen gerückt. Dabei geht es um die Problematik, dass künstliche Intelligenzen sogenannte Black Boxen sind. Das bedeutet, dass ein menschlicher User die Entscheidung einer künstlichen Intelligenz üblicherweise nicht nachvollziehen kann. Eine xAI wäre im Vergleich jedoch eine Glass Box, die Entscheidungen einer solchen künstlichen Intelligenz wären für Menschen also nachvollziehbar.

Algorithmen

Algorithmen sind klar definierte, vorgegebene Prozeduren, mit denen klar definierte Aufgaben gelöst werden können. Dabei kann der Lösungsweg des Algorithmus entweder durch Menschen vorgegeben, also programmiert werden oder Algorithmen lernen durch Methoden des maschinellen Lernens selbstständig den Lösungsweg für eine Prozedur.

Im Bereich der Data Science bezeichnen wir mit Algorithmen kleine Programme, die scheinbar intelligent handeln. Dementsprechend stecken auch hinter künstlichen Intelligenzen Algorithmen. Werden Algorithmen mit klar definierten Eingaben versorgt, führen sie somit zu einem eindeutigen, konstanten Ergebnis. Dabei gilt aber leider auch der Grundsatz der Informatik „Mist rein, Mist raus“. Ein Algorithmus kann immer nur auf sinnvolle Eingaben sinnvolle Ausgaben erzeugen. Die Komplexität von Algorithmen kann sehr vielfältig sein und je komplexer ein solcher Algorithmus ist, desto „intelligenter“ erscheint er oftmals.

Maschinelles Lernen

Maschinelles Lernen ist ein Überbegriff für eine Vielzahl von Verfahren, mit denen ein Computer oder eine künstliche Intelligenz automatisch Muster in Daten erkennt. Beim maschinellen Lernen wird grundsätzlich zwischen dem überwachten und unüberwachten Lernen unterschieden.

Beim überwachten Lernen lernt ein Algorithmus den Zusammenhang zwischen bekannten Eingabe- und Ausgabewerten. Nachdem dieser Zusammenhang vom Algorithmus erlernt wurde, kann dieses maschinelle Modell dann auf neue Eingabewerte angewandt und somit unbekannte Ausgabewerte vorhergesagt werden. Beispielsweise könnte mithilfe einer Regression zunächst der Zusammenhang zwischen Lufttemperatur und dem Wochentag (jeweils bekannte Eingabewerte) sowie der Anzahl der verkauften Eiskugeln (für die Vergangenheit bekannte Ausgabewerte) in einem Freibad untersucht werden. Sobald dieser Zusammenhang einmal ausreichend genau bestimmt worden ist, kann er auch für die Zukunft fortgeschrieben werden. Das bedeutet, es wäre dann möglich, anhand des nächsten Wochentages sowie der vorhergesagten Lufttemperatur (bekannte Eingabewerte für die Zukunft) die Anzahl der verkauften Eiskugeln (unbekannte Ausgabewerte für die Zukunft) zu prognostizieren und somit die Absatzmenge genauer planen zu können.

Beim unüberwachten Lernen auf der anderen Seite sind nur Eingabedaten vorhanden, es gibt keine den Eingabedaten zugehörigen Ausgabedaten. Hier wird dann mit Methoden wie beispielsweise dem Clustering versucht, verschiedene Datenpunkte anhand ihrer Eigenschaften in verschiedene Gruppen aufzuteilen. Beispielsweise könnte ein Clustering-Algorithmus verschiedene Besucher:innen eines Webshops in verschiedene Gruppen einteilen: Es könnte beispielsweise eine Gruppe von Besucher:innen geben, die sehr zielstrebig ein einzelnes Produkt in den Warenkorb legen und ihren Kauf direkt abschließen. Andere Besucher:innen könnten allerdings viele verschiedene Produkte ansehen, in den Warenkorb legen und am Ende nur wenige oder vielleicht sogar gar keine Käufe tätigen. Wieder andere Kund:innen könnten unter Umständen lediglich auf der Suche nach Artikeln im Sale sein und keine anderen Produkte ansehen.

Aufgrund ihres Nutzungsverhaltens auf der Website könnte ein Clustering-Algorithmus mit ausreichend aufbereiteten Daten nun all diese Kund:innen in verschiedene Gruppen oder Cluster einteilen. Was der Algorithmus jedoch nicht leisten kann ist zu erklären, was die erkannten Cluster genau bedeuten. Hierfür braucht es nach wie vor menschliche Intelligenz gepaart mit Fachwissen.

Wie Maschinen uns verstehen: Natural Language Understanding

Foto von Sebastian Bill auf Unsplash.

Natural Language Understanding (NLU) ist ein Teilbereich von Computer Science, der sich damit beschäftigt natürliche Sprache, also beispielsweise Texte oder Sprachaufnahmen, verstehen und verarbeiten zu können. Das Ziel ist es, dass eine Maschine in der gleichen Weise mit Menschen kommunizieren kann, wie es Menschen untereinander bereits seit Jahrhunderten tun.

Was sind die Bereiche von NLU?

Eine neue Sprache zu erlernen ist auch für uns Menschen nicht einfach und erfordert viel Zeit und Durchhaltevermögen. Wenn eine Maschine natürliche Sprache erlernen will, ist es nicht anders. Deshalb haben sich einige Teilbereiche innerhalb des Natural Language Understandings herausgebildet, die notwendig sind, damit Sprache komplett verstanden werden kann.

Diese Unterteilungen können auch unabhängig voneinander genutzt werden, um einzelne Aufgaben zu lösen:

  • Speech Recognition versucht aufgezeichnete Sprache zu verstehen und in textuelle Informationen umzuwandeln. Das macht es für nachgeschaltete Algorithmen einfacher die Sprache zu verarbeiten. Speech Recognition kann jedoch auch alleinstehend genutzt werden, beispielsweise um Diktate oder Vorlesungen in Text zu verwandeln.
  • Part of Speech Tagging wird genutzt, um die grammatikalische Zusammensetzung eines Satzes zu erkennen und die einzelnen Satzbestandteile zu markieren.
  • Named Entity Recognition versucht innerhalb eines Textes Wörter und Satzbausteine zu finden, die einer vordefinierten Klasse zugeordnet werden können. So können dann zum Beispiel alle Phrasen in einem Textabschnitt markiert werden, die einen Personennamen enthalten oder eine Zeit ausdrücken.
  • Sentiment Analysis klassifiziert das Sentiment, also die Gefühlslage, eines Textes in verschiedene Stufen. Dadurch kann beispielsweise automatisiert erkannt werden, ob eine Produktbewertung eher positiv oder eher negativ ist.
  • Natural Language Generation ist eine allgemeine Gruppe von Anwendungen mithilfe derer automatisiert neue Texte generiert werden sollen, die möglichst natürlich klingen. Zum Beispiel können mithilfe von kurzen Produkttexten ganze Marketingbeschreibungen dieses Produkts erstellt werden.

Welche Algorithmen nutzt man für NLP?

Die meisten, grundlegenden Anwendungen von NLP können mit den Python Modulen spaCy und NLTK umgesetzt werden. Diese Bibliotheken bieten weitreichende Modelle zur direkten Anwendung auf einen Text, ohne vorheriges Trainieren eines eigenen Algorithmus. Mit diesen Modulen ist ohne weiteres ein Part of Speech Tagging oder Named Entity Recognition in verschiedenen Sprachen möglich.

Der Hauptunterschied zwischen diesen beiden Bibliotheken ist die Ausrichtung. NLTK ist vor allem für Entwickler gedacht, die eine funktionierende Applikation mit Natural Language Processing Modulen erstellen wollen und dabei auf Performance und Interkompatibilität angewiesen sind. SpaCy hingegen versucht immer Funktionen bereitzustellen, die auf dem neuesten Stand der Literatur sind und macht dabei möglicherweise Einbußen bei der Performance.

Für umfangreichere und komplexere Anwendungen reichen jedoch diese Optionen nicht mehr aus, beispielsweise wenn man eine eigene Sentiment Analyse erstellen will. Je nach Anwendungsfall sind dafür noch allgemeine Machine Learning Modelle ausreichend, wie beispielsweise ein Convolutional Neural Network (CNN). Mithilfe von Tokenizern von spaCy oder NLTK können die einzelnen in Wörter in Zahlen umgewandelt werden, mit denen wiederum das CNN als Input arbeiten kann. Auf heutigen Computern sind solche Modelle mit kleinen Neuronalen Netzwerken noch schnell trainierbar und deren Einsatz sollte deshalb immer erst geprüft und möglicherweise auch getestet werden.

Jedoch gibt es auch Fälle in denen sogenannte Transformer Modelle benötigt werden, die im Bereich des Natural Language Processing aktuell state-of-the-art sind. Sie können inhaltliche Zusammenhänge in Texten besonders gut mit in die Aufgabe einbeziehen und liefern daher bessere Ergebnisse beispielsweise bei der Machine Translation oder bei Natural Language Generation. Jedoch sind diese Modelle sehr rechenintensiv und führen zu einer sehr langen Rechenzeit auf normalen Computern.

Was sind Transformer Modelle?

In der heutigen Machine Learning Literatur führt kein Weg mehr an Transformer Modellen aus dem Paper „Attention is all you need“ (Vaswani et al. (2017)) vorbei. Speziell im Bereich des Natural Language Processing sind die darin erstmals beschriebenen Transformer Modelle nicht mehr wegzudenken.

Transformer werden aktuell vor allem für Übersetzungsaufgaben genutzt, wie beispielsweise auch bei www.deepl.com. Darüber hinaus sind diese Modelle auch für weitere Anwendungsfälle innerhalb des Natural Language Understandings geeignet, wie bspw. das Beantworten von Fragen, Textzusammenfassung oder das Klassifizieren von Texten. Das GPT-2 Modell ist eine Implementierung von Transformern, dessen Anwendungen und die Ergebnisse man hier ausprobieren kann.

Was macht den Transformer so viel besser?

Soweit wir wissen, ist der Transformer jedoch das erste Transduktionsmodell, das sich ausschließlich auf die Selbstaufmerksamkeit (im Englischen: Self-Attention) stützt, um Repräsentationen seiner Eingabe und Ausgabe zu berechnen, ohne sequenzorientierte RNNs oder Faltung (im Englischen Convolution) zu verwenden.

Übersetzt aus dem englischen Originaltext: Attention is all you need (Vaswani et al. (2017)).

In verständlichem Deutsch bedeutet dies, dass das Transformer Modell die sogenannte Self-Attention nutzt, um für jedes Wort innerhalb eines Satzes die Beziehung zu den anderen Wörtern im gleichen Satz herauszufinden. Dafür müssen nicht, wie bisher, Recurrent Neural Networks oder Convolutional Neural Networks zum Einsatz kommen.

Was dieser Mechanismus konkret bewirkt und warum er so viel besser ist, als die vorherigen Ansätze wird im folgenden Beispiel deutlich. Dazu soll der folgende deutsche Satz mithilfe von Machine Learning ins Englische übersetzt werden:

„Das Mädchen hat das Auto nicht gesehen, weil es zu müde war.“

Für einen Computer ist diese Aufgabe leider nicht so einfach, wie für uns Menschen. Die Schwierigkeit an diesem Satz ist das kleine Wort „es“, dass theoretisch für das Mädchen oder das Auto stehen könnte. Aus dem Kontext wird jedoch deutlich, dass das Mädchen gemeint ist. Und hier ist der Knackpunkt: der Kontext. Wie programmieren wir einen Algorithmus, der den Kontext einer Sequenz versteht?

Vor Veröffentlichung des Papers „Attention is all you need“ waren sogenannte Recurrent Neural Networks die state-of-the-art Technologie für solche Fragestellungen. Diese Netzwerke verarbeiten Wort für Wort eines Satzes. Bis man also bei dem Wort „es“ angekommen ist, müssen erst alle vorherigen Wörter verarbeitet worden sein. Dies führt dazu, dass nur noch wenig Information des Wortes „Mädchen“ im Netzwerk vorhanden sind bis den Algorithmus überhaupt bei dem Wort „es“ angekommen ist. Die vorhergegangenen Worte „weil“ und „gesehen“ sind zu diesem Zeitpunkt noch deutlich stärker im Bewusstsein des Algorithmus. Es besteht also das Problem, dass Abhängigkeiten innerhalb eines Satzes verloren gehen, wenn sie sehr weit auseinander liegen.

Was machen Transformer Modelle anders? Diese Algorithmen prozessieren den kompletten Satz gleichzeitig und gehen nicht Wort für Wort vor. Sobald der Algorithmus das Wort „es“ in unserem Beispiel übersetzen will, wird zuerst die sogenannte Self-Attention Layer durchlaufen. Diese hilft dem Programm andere Wörter innerhalb des Satzes zu erkennen, die helfen könnten das Wort „es“ zu übersetzen. In unserem Beispiel werden die meisten Wörter innerhalb des Satzes einen niedrigen Wert für die Attention haben und das Wort Mädchen einen hohen Wert. Dadurch ist der Kontext des Satzes bei der Übersetzung erhalten geblieben.

Generative Adversarial Networks GANs

Generative Adversarial Networks

After Deep Autoregressive Models, Deep Generative Modelling and Variational Autoencoders we now continue the discussion with Generative Adversarial Networks (GANs).

Introduction

So far, in the series of deep generative modellings (DGMs [Yad22a]), we have covered autoregressive modelling, which estimates the exact log likelihood defined by the model and variational autoencoders, which was variational approximations for lower bound optimization. Both of these modelling techniques were explicitly defining density functions and optimizing the likelihood of the training data. However, in this blog, we are going to discuss generative adversarial networks (GANs), which are likelihood-free models and do not define density functions explicitly. GANs follow a game-theoretic approach and learn to generate from the training distribution through a set up of a two-player game.

A two player model of GAN along with the generator and discriminators.

A two player model of GAN along with the generator and discriminators.

GAN tries to learn the distribution of high dimensional training data and generates high-quality synthetic data which has a similar distribution to training data. However, learning the training distribution is a highly complex task therefore GAN utilizes a two-player game approach to overcome the high dimensional complexity problem. GAN has two different neural networks (as shown in Figure ??) the generator and the discriminator. The generator takes a random input z\sim p(z) and produces a sample that has a similar distribution as p_d. To train this network efficiently, there is the other network that is utilized as the second player and known as the discriminator. The generator network (player one) tries to fool the discriminator by generating real looking images. Moreover, the discriminator network tries to distinguish between real (training data x\sim p_d(x)) and fake images effectively. Our main aim is to have an efficiently trained discriminator to be able to distinguish between real and fake images (the generator’s output) and on the other hand, we would like to have a generator, which can easily fool the discriminator by generating real-looking images.

Objective function and training

Objective function

Simultaneous training of these two networks is one of the main challenges in GANs and a minimax loss function is defined for this purpose. To understand this minimax function, firstly, we would like to discuss the concept of two sample testing by Aditya grover [Gro20]. Two sample testing is a method to compute the discrepancy between the training data distribution and the generated data distribution:

(1)   \begin{equation*} \min_{p_{\theta_g}}\: \max_{D_{\theta_d}\in F} \: \mathbb{E}_{x\sim p_d}[D_{\theta_d}(x)] - \mathbb{E}_{x\sim p_{\theta_g}} [D_{\theta_d}(G_{\theta_g}(x))], \end{equation*}


where p_{\theta_g} and p_d are the distribution functions of generated and training data respectively. The term F is a set of functions. The \textit{max} part is computing the discrepancies between two distribution using a function D_{\theta_d} \in F and this part is very similar to the term d (discrepancy measure) from our first article (Deep Generative Modelling) and KL-divergence is applied to compute this measure in second article (Deep Autoregressive Models) and third articles (Variational Autoencoders). However, in GANs, for a given set of functions F, we would like compute the distribution p_{\theta_g}, which minimizes the overall discrepancy even for a worse function D_{\theta_d}\in F. The above mentioned objective function does not use any likelihood function and utilizing two different data samples from training and generated data respectively.

By combining Figure ?? and Equation 1, the first term \mathbb{E}_{x\sim p_d}[D_{\theta_d}(x)] corresponds to the discriminator, which has direct access to the training data and the second term \mathbb{E}_{x\sim p_{\theta_g}}[D_{\theta_d}(G_{\theta_g}(x))] represents the generator part as it relies only on the latent space and produces synthetic data. Therefore, Equation 1 can be rewritten in the form of GAN’s two players as:

(2)   \begin{equation*} \min_{p_{\theta_g}}\: \max_{D_{\theta_d}\in F} \: \mathbb{E}_{x\sim p_d}[D_{\theta_d}(x)] - \mathbb{E}_{z\sim p_z}[D_{\theta_d}(G_{\theta_g}(z))], \end{equation*}


The above equation can be rearranged in the form of log loss:

(3)   \begin{equation*} \min_{\theta_g}\: \max_{\theta_d} \: (\mathbb{E}_{x\sim p_d} [log \: D_{\theta_d} (x)] + \mathbb{E}_{z\sim p_z}[log(1 - D_{\theta_d}(G_{\theta_g}(z))]), \end{equation*}

In the above equation, the arguments are modified from p_{\theta_g} and D_{\theta_d} in F to \theta_g and  \theta_d respectively as we would like to approximate the network parameters, which are represented by \theta_g and \theta_d for the both generator and discriminator respectively. The discriminator wants to maximize the above objective for \theta_d such that D_{\theta_d}(x) \approx 1, which indicates that the outcome is close to the real data. Furthermore, D_{\theta_d}(G_{\theta_g}(z)) should be close to zero as it is fake data, therefore, the maximization of the above objective function for \theta_d will ensure that the discriminator is performing efficiently in terms of separating real and fake data. From the generator point of view, we would like to minimize this objective function for \theta_g such that D_{\theta_d}(G_{\theta_g}(z)) \approx 1. If the minimization of the objective function happens effectively for \theta_g then the discriminator will classify a fake data into a real data that means that the generator is producing almost real-looking samples.

Training

The training procedure of GAN can be explained by using the following visualization from Goodfellow et al. [GPAM+14]. In Figure 2(a), z is a random input vector to the generator to produce a synthetic outcome x\sim p_{\theta_g} (green curve). The generated data distribution is not close to the original data distribution p_d (dotted black curve). Therefore, the discriminator classifies this image as a fake image and forces generator to learn the training data distribution (Figure 2(b) and (c)). Finally, the generator produces the image which could not detected as a fake data by discriminator(Figure 2(d)).

GAN’s training visualization: the dotted black, solid green lines represents pd and pθ respectively. The discriminator distribution is shown in dotted blue. This image taken from Goodfellow et al.

GAN’s training visualization: the dotted black, solid green lines represents pd and pθ
respectively. The discriminator distribution is shown in dotted blue. This image taken from Goodfellow
et al. [GPAM+14].

The optimization of the objective function mentioned in Equation 3 is performed in th following two steps repeatedly:
\begin{enumerate}
\item Firstly, the gradient ascent is utilized to maximize the objective function for \theta_d for discriminator.

(4)   \begin{equation*} \max_{\theta_d} \: (\mathbb{E}_{x\sim p_d} [log \: D_{\theta_d}(x)] + \mathbb{E}_{z\sim p_z}[log(1 - D_{\theta_d}(G_{\theta_g}(z))]) \end{equation*}


\item In the second step, the following function is minimized for the generator using gradient descent.

(5)   \begin{equation*} \min_{\theta_g} \: ( \mathbb{E}_{z\sim p_z}[log(1 - D_{\theta_d}(G_{\theta_g}(z))]) \end{equation*}


\end{enumerate}

However, in practice the minimization for the generator does now work well because when D_{\theta_d}(G_{\theta_g}(z) \approx 1 then the term log \: (1-D_{\theta_d}(G_{\theta_g}(z))) has the dominant gradient and vice versa.

However, we would like to have the gradient behaviour completely opposite because D_{\theta_d}(G_{\theta_g}(z) \approx 1 means the generator is well trained and does not require dominant gradient values. However, in case of D_{\theta_d}(G_{\theta_g}(z) \approx 0, the generator is not well trained and producing low quality outputs therefore, it requires a dominant gradient for an efficient training. To fix this problem, the gradient ascent method is applied to maximize the modified generator’s objective:
In the second step, the following function is minimized for the generator using gradient descent alternatively.

(6)   \begin{equation*} \max_{\theta_g} \: \mathbb{E}_{z\sim p_z}[log \: (D_{\theta_d}(G_{\theta_g}(z))] \end{equation*}


therefore, during the training, Equation 4 and 6 will be maximized using the gradient ascent algorithm until the convergence.

Results

The quality of the generated images using GANs depends on several factors. Firstly, the joint training of GANs is not a stable procedure and that could severely decrease the quality of the outcome. Furthermore, the different neural network architecture will modify the quality of images based on the sophistication of the used network. For example, the vanilla GAN [GPAM+14] uses a fully connected deep neural network and generates a quite decent result. Furthermore, DCGAN [RMC15] utilized deep convolutional networks and enhanced the quality of outcome significantly. Furthermore, different types of loss functions are applied to stabilize the training procedure of GAN and to produce high-quality outcomes. As shown in Figure 3, StyleGAN [KLA19] utilized Wasserstein metric [Yad22b] to generate high-resolution face images. As it can be seen from Figure 3, the quality of the generated images are enhancing with time by applying more sophisticated training techniques and network architectures.

GAN timeline with different variations in terms of network architecture and loss functions.

GAN timeline with different variations in terms of network architecture and loss functions.

Summary

This article covered the basics and mathematical concepts of GANs. However, the training of two different networks simultaneously could be complex and unstable. Therefore, researchers are continuously working to create a better and more stable version of GANs, for example, WGAN. Furthermore, different types of network architectures are introduced to improve the quality of outcomes. We will discuss this further in the upcoming blog about these variations.

References

[GPAM+14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, DavidWarde-Farley, Sherjil
Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in
neural information processing systems, 27, 2014.

[Gro20] Aditya Grover. Generative adversarial networks.
https://deepgenerativemodels.github.io/notes/gan/, 2020.

[KLA19] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for
generative adversarial networks. In Proceedings of the IEEE/CVF conference on computer
vision and pattern recognition, pages 4401–4410, 2019.

[RMC15] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation
learning with deep convolutional generative adversarial networks. arXiv preprint
arXiv:1511.06434, 2015.

[Yad22a] Sunil Yadav. Deep generative modelling. https://data-scienceblog.
com/blog/2022/02/19/deep-generative-modelling/, 2022.

[Yad22b] Sunil Yadav. Necessary probability concepts for deep learning: Part 2.
https://medium.com/@sunil7545/kl-divergence-js-divergence-and-wasserstein-metricin-
deep-learning-995560752a53, 2022.

Big Data mit Hadoop und Map Reduce!

Foto von delfi de la Rua auf Unsplash.

Hadoop ist ein Softwareframework, mit dem sich große Datenmengen auf verteilten Systemen schnell verarbeiten lassen. Es verfügt über Mechanismen, welche eine stabile und fehlertolerante Funktionalität sicherstellen, sodass das Tool für die Datenverarbeitung im Big Data Umfeld bestens geeignet ist. In diesen Fällen ist eine normale relationale Datenbank oft nicht ausreichend, um die unstrukturierten Datenmengen kostengünstig und effizient abzuspeichern.

Unterschiede zwischen Hadoop und einer relationalen Datenbank

Hadoop unterscheidet sich in einigen grundlegenden Eigenschaften von einer vergleichbaren relationalen Datenbank.

Eigenschaft Relationale Datenbank Hadoop
Datentypen ausschließlich strukturierte Daten alle Datentypen (strukturiert, semi-strukturiert und unstrukturiert)
Datenmenge wenig bis mittel (im Bereich von einigen GB) große Datenmengen (im Bereich von Terrabyte oder Petabyte)
Abfragesprache SQL HQL (Hive Query Language)
Schema Statisches Schema (Schema on Write) Dynamisches Schema (Schema on Read)
Kosten Lizenzkosten je nach Datenbank Kostenlos
Datenobjekte Relationale Tabellen Key-Value Pair
Skalierungstyp Vertikale Skalierung (Computer muss hardwaretechnisch besser werden) Horizontale Skalierung (mehr Computer können dazugeschaltet werden, um Last abzufangen)

Vergleich Hadoop und Relationale Datenbank

Bestandteile von Hadoop

Das Softwareframework selbst ist eine Zusammenstellung aus insgesamt vier Komponenten.

Hadoop Common ist eine Sammlung aus verschiedenen Modulen und Bibliotheken, welche die anderen Bestandteile unterstützt und deren Zusammenarbeit ermöglicht. Unter anderem sind hier die Java Archive Dateien (JAR Files) abgelegt, die zum Starten von Hadoop benötigt werden. Darüber hinaus ermöglicht die Sammlung die Bereitstellung von grundlegenden Services, wie beispielsweise das File System.

Der Map-Reduce Algorithmus geht in seinen Ursprüngen auf Google zurück und hilft komplexe Rechenaufgaben in überschaubarere Teilprozesse aufzuteilen und diese dann über mehrere Systeme zu verteilen, also horizontal zu skalieren. Dadurch verringert sich die Rechenzeit deutlich. Am Ende müssen die Ergebnisse der Teilaufgaben wieder zu seinem Gesamtresultat zusammengefügt werden.

Der Yet Another Resource Negotiator (YARN) unterstützt den Map-Reduce Algorithmus, indem er die Ressourcen innerhalb eines Computer Clusters im Auge behält und die Teilaufgaben auf die einzelnen Rechner verteilt. Darüber hinaus ordnet er den einzelnen Prozessen die Kapazitäten dafür zu.

Das Hadoop Distributed File System (HDFS) ist ein skalierbares Dateisystem zur Speicherung von Zwischen- oder Endergebnissen. Innerhalb des Clusters ist es über mehrere Rechner verteilt, um große Datenmengen schnell und effizient verarbeiten zu können. Die Idee dahinter war, dass Big Data Projekte und Datenanalysen auf großen Datenmengen beruhen. Somit sollte es ein System geben, welches die Daten auch stapelweise speichert und dadurch schnell verarbeitet. Das HDFS sorgt auch dafür, dass Duplikate von Datensätzen abgelegt werden, um den Ausfall eines Rechners verkraften zu können.

Map Reduce am Beispiel

Angenommen wir haben alle Teile der Harry Potter Romane in Hadoop PDF abgelegt und möchten nun die einzelnen Wörter zählen, die in den Büchern vorkommen. Dies ist eine klassische Aufgabe bei der uns die Aufteilung in eine Map-Funktion und eine Reduce Funktion helfen kann.

Bevor es die Möglichkeit gab, solche aufwendigen Abfragen auf ein ganzes Computer-Cluster aufzuteilen und parallel berechnen zu können, war man gezwungen, den kompletten Datensatz nacheinander zu durchlaufen. Dadurch wurde die Abfragezeit auch umso länger, umso größer der Datensatz wurde. Der einzige Weg, um die Ausführung der Funktion zu beschleunigen ist es, einen Computer mit einem leistungsfähigeren Prozessor (CPU) auszustatten, also dessen Hardware zu verbessern. Wenn man versucht, die Ausführung eines Algorithmus zu beschleunigen, indem man die Hardware des Gerätes verbessert, nennt man das vertikale Skalieren.

Mithilfe von MapReduce ist es möglich eine solche Abfrage deutlich zu beschleunigen, indem man die Aufgabe in kleinere Teilaufgaben aufsplittet. Das hat dann wiederum den Vorteil, dass die Teilaufgaben auf viele verschiedene Computer aufgeteilt und von ihnen ausgeführt werden kann. Dadurch müssen wir nicht die Hardware eines einzigen Gerätes verbessern, sondern können viele, vergleichsweise leistungsschwächere, Computer nutzen und trotzdem die Abfragezeit verringern. Ein solches Vorgehen nennt man horizontales Skalieren.

Kommen wir zurück zu unserem Beispiel: Bisher waren wir bildlich so vorgegangen, dass wir alle Harry Potter Teile gelesen haben und nach jedem gelesenen Wort die Strichliste mit den einzelnen Wörtern einfach um einen Strich erweitert haben. Das Problem daran ist, dass wir diese Vorgehensweise nicht parallelisieren können. Angenommen eine zweite Person will uns unterstützen, dann kann sie das nicht tun, weil sie die Strichliste, mit der wir gerade arbeiten, benötigt, um weiterzumachen. Solange sie diese nicht hat, kann sie nicht unterstützen.

Sie kann uns aber unterstützen, indem sie bereits mit dem zweiten Teil der Harry Potter Reihe beginnt und eine eigene Strichliste nur für das zweite Buch erstellt. Zum Schluss können wir dann alle einzelnen Strichlisten zusammenführen und beispielsweise die Häufigkeit des Wortes “Harry” auf allen Strichlisten zusammenaddieren.

MapReduce am Beispiel von Wortzählungen in Harry Potter Büchern

MapReduce am Beispiel von Wortzählungen in Harry Potter Büchern | Source: Data Basecamp

Dadurch lässt sich die Aufgabe auch relativ einfach horizontal skalieren, indem jeweils eine Person pro Harry Potter Buch arbeitet. Wenn wir noch schneller arbeiten wollen, können wir auch mehrere Personen mit einbeziehen und jede Person ein einziges Kapitel bearbeiten lassen. Am Schluss müssen wir dann nur alle Ergebnisse der einzelnen Personen zusammennehmen, um so zu einem Gesamtergebnis zu gelangen.

Das ausführliche Beispiel und die Umsetzung in Python findest Du hier.

Aufbau eines Hadoop Distributed File Systems

Der Kern des Hadoop Distributed File Systems besteht darin die Daten auf verschiedene Dateien und Computer zu verteilen, sodass Abfragen schnell bearbeitet werden können und der Nutzer keine langen Wartezeiten hat. Damit der Ausfall einer einzelnen Maschine im Cluster nicht zum Verlust der Daten führt, gibt es gezielte Replikationen auf verschiedenen Computern, um eine Ausfallsicherheit zu gewährleisten.

Hadoop arbeitet im Allgemeinen nach dem sogenannten Master-Slave-Prinzip. Innerhalb des Computerclusters haben wir einen Knoten, der die Rolle des sogenannten Masters übernimmt. Dieser führt in unserem Beispiel keine direkte Berechnung durch, sondern verteilt lediglich die Aufgaben auf die sogenannten Slave Knoten und koordiniert den ganzen Prozess. Die Slave Knoten wiederum lesen die Bücher aus und speichern die Worthäufigkeit und die Wortverteilung.

Dieses Prinzip wird auch bei der Datenspeicherung genutzt. Der Master verteilt Informationen aus dem Datensatz auf verschiedenen Slave Nodes und merkt sich, auf welchen Computern er welche Partitionen abgespeichert hat. Dabei legt er die Daten auch redundant ab, um Ausfälle kompensieren zu können. Bei einer Abfrage der Daten durch den Nutzer entscheidet der Masterknoten dann, welche Slaveknoten er anfragen muss, um die gewünschten Informationen zu erhalten.

Air Quality Forecasting Python Project

You will find the full python code and all visuals for this article here in this gitlab repository. The repository contains a series of analysis, transforms and forecasting models frequently used when dealing with time series. The aim of this repository is to showcase how to model time series from the scratch, for this we are using a real usecase dataset

This project forecast the Carbon Dioxide (Co2) emission levels yearly. Most of the organizations have to follow government norms with respect to Co2 emissions and they have to pay charges accordingly, so this project will forecast the Co2 levels so that organizations can follow the norms and pay in advance based on the forecasted values. In any data science project the main component is data, for this project the data was provided by the company, from here time series concept comes into the picture. The dataset for this project contains 215 entries and two components which are Year and Co2 emissions which is univariate time series as there is only one dependent variable Co2 which depends on time. from year 1800 to year 2014 Co2 levels were present in the dataset.

The dataset used: The dataset contains yearly Co2 emmisions levels. data from 1800 to 2014 sampled every 1 year. The dataset is non stationary so we have to use differenced time series for forecasting.

After getting data the next step is to analyze the time series data. This process is done by using Python. The data was present in excel file so first we need to read that excel file. This task is done by using Pandas which is python libraries to creates Pandas Data Frame. After that preprocessing like changing data types of time from object to DateTime performed for the coding purpose. Time series contain 4 main components Level, Trend, Seasonality and Noise. To study this component, we need to decompose our time series so that we can batter understand our time series and we can choose the forecasting model accordingly because each component behave different on the model. also by decomposing we can identify that the time series is multiplicative or additive.

CO2 emissions – plotted via python pandas / matplotlib

Decomposing time series using python statesmodels libraries we get to know trend, seasonality and residual component separately. the components multiply together to make the time series multiplicative and in additive time series components added together. Taking the deep dive to understand the trend component, moving average of 10 steps were applied which shows nonlinear upward trend, fit the linear regression model to check the trend which shows upward trend. talking about seasonality there were combination of multiple patterns over time period which is common in real world time series data. capturing the white noise is difficult in this type of data. the time series contains values from 1800 where the Co2 values are less then 1 because of no human activities so levels were decreasing. By the time numbers of industries and human activities are rapidly increasing which causes Co2 levels rapidly increasing. In time series the highest Co2 emission level was 18.7 in 1979. It was challenging to decide whether to consider this values which are less then 0.5 as white noise or not because 30% of the Co2 values were less then 1, in real world looking at current scenario the chances of Co2 emission level being 0 is near to impossible still there are chances that Co2 levels can be 0.0005. So considering each data point as a valuable information we refused to remove that entries.

Next step is to create Lag plot so we can see the correlation between the current year Co2 level and previous year Co2 level. the plot was linear which shows high correlation so we can say that the current Co2 levels and previous levels have strong relationship. the randomness of the data were measured by plotting autocorrelation graph. the autocorrelation graph shows smooth curves which indicates the time series is nonstationary thus next step is to make time series stationary. in nonstationary time series, summary statistics like mean and variance change over time.

To make time series stationary we have to remove trend and seasonality from it. Before that we use dickey fuller test to make sure our time series is nonstationary. the test was done by using python, and the test gives pvalue as output. here the null hypothesis is that the data is nonstationary while alternate hypothesis is that the data is stationary, in this case the significance values is 0.05 and the pvalues which is given by dickey fuller test is greater than 0.05 hence we failed to reject null hypothesis so we can say the time series is nonstationery. Differencing is one of the techniques to make time series stationary. On this time series, first order differencing technique applied to make the time series stationary. In first order differencing we have to subtract previous value from current value for all the data points. also different transformations like log, sqrt and reciprocal were applied in the context of making the time series stationary. Smoothing techniques like simple moving average, exponential weighted moving average, simple exponential smoothing and double exponential smoothing techniques can be applied to remove the variation between time stamps and to see the smooth curves.

Smoothing techniques also used to observe trend in time series as well as to predict the future values. But performance of other models was good compared to smoothing techniques. First 200 entries taken to train the model and remaining last for testing the performance of the model. performance of different models measured by Root Mean Squared Error (RMSE) and Mean Absolute Error (MAE) as we are predicting future Co2 emissions so basically it is regression problem. RMSE is calculated by root of the average of squared difference between actual values and predicted values by the model on testing data. Here RMSE values were calculated using python sklearn library. For model building two approaches are there, one is datadriven and another one is model based. models from both the approaches were applied to find the best fitted model. ARIMA model gives the best results for this kind of dataset as the model were trained on differenced time series. The ARIMA model predicts a given time series based on its own past values. It can be used for any nonseasonal series of numbers that exhibits patterns and is not a series of random events. ARIMA takes 3 parameters which are AR, MA and the order of difference. Hyper parameter tuning technique gives best parameters for the model by trying different sets of parameters. Although The autocorrelation and partial autocorrelation plots can be use to decide AR and MA parameter because partial autocorrelation function shows the partial correlation of a stationary time series with its own lagged values so using PACF we can decide the value of AR and from ACF we can decide the value of MA parameter as ACF shows how data points in a time series are related.

Yearly difference of CO2 emissions – ARIMA Prediction

Apart from ARIMA, few other model were trained which are AR, ARMA, Simple Linear Regression, Quadratic method, Holts winter exponential smoothing, Ridge and Lasso Regression, LGBM and XGboost methods, Recurrent neural network (RNN) Long Short Term Memory (LSTM) and Fbprophet. I would like to mention my experience with LSTM here because it is another model which gives good result as ARIMA. the reason for not choosing LSTM as final model is its complexity. As ARIMA is giving appropriate results and it is simple to understand and requires less dependencies. while using lstm, lot of data preprocessing and other dependencies required, the dataset was small thus we used to train the model on CPU, otherwise gpu is required to train the LSTM model. we face one more challenge in deployment part. the challenge is to get the data into original form because the model was trained on differenced time series, so it will predict the future values in differenced format. After lot of research on the internet and by deeply understanding mathematical concepts finally we got the solution for it. solution for this issue is we have to add previous value from the original data from into first order differencing and then we have to add the last value of this time series into predicted values. To create the user interface streamlit was used, it is commonly used python library. the pickle file of the ARIMA model were used to predict the future values based on user input. The limit for forecasting is the year 2050. The project was uploaded on google cloud platform. so the flow is, first the starting year from which user want to forecast was taken and the end year till which year user want to forecast was taken and then according to the range of this inputs the prediction takes place. so by taking the inputs the pickle file will produce the future Co2 emissions in differenced format, then the values will be converted to original format and then the original values will be displayed on the user interface as well as the interactive line graph were displayed on the interface.

You will find the full python code and all visuals for this article here in this gitlab repository.

Deep Autoregressive Models

Deep Autoregressive Models

In this blog article, we will discuss about deep autoregressive generative models (AGM). Autoregressive models were originated from economics and social science literature on time-series data where obser- vations from the previous steps are used to predict the value at the current and at future time steps [SS05]. Autoregression models can be expressed as:

    \begin{equation*} x_{t+1}= \sum_i^t \alpha_i x_{t-i} + c_i, \end{equation*}

where the terms \alpha and c are constants to define the contributions of previous samples x_i for the future value prediction. In the other words, autoregressive deep generative models are directed and fully observed models where outcome of the data completely depends on the previous data points as shown in Figure 1.

Autoregressive directed graph.

Figure 1: Autoregressive directed graph.

Let’s consider x \sim X, where X is a set of images and each images is n-dimensional (n pixels). Then the prediction of new data pixel will be depending all the previously predicted pixels (Figure ?? shows the one row of pixels from an image). Referring to our last blog, deep generative models (DGMs) aim to learn the data distribution p_\theta(x) of the given training data and by following the chain rule of the probability, we can express it as:

(1)   \begin{equation*} p_\theta(x) = \prod_{i=1}^n p_\theta(x_i | x_1, x_2, \dots , x_{i-1}) \end{equation*}

The above equation modeling the data distribution explicitly based on the pixel conditionals, which are tractable (exact likelihood estimation). The right hand side of the above equation is a complex distribution and can be represented by any possible distribution of n random variables. On the other hand, these kind of representation can have exponential space complexity. Therefore, in autoregressive generative models (AGM), these conditionals are approximated/parameterized by neural networks.

Training

As AGMs are based on tractable likelihood estimation, during the training process these methods maximize the likelihood of images over the given training data X and it can be expressed as:

(2)   \begin{equation*} \max_{\theta} \sum_{x\sim X} log \: p_\theta (x) = \max_{\theta} \sum_{x\sim X} \sum_{i=1}^n log \: p_\theta (x_i | x_1, x_2, \dots, x_{i-1}) \end{equation*}

The above expression is appearing because of the fact that DGMs try to minimize the distance between the distribution of the training data and the distribution of the generated data (please refer to our last blog). The distance between two distribution can be computed using KL-divergence:

(3)   \begin{equation*} \min_{\theta} d_{KL}(p_d (x),p_\theta (x)) = log\: p_d(x) - log \: p_\theta(x) \end{equation*}

In the above equation the term p_d(x) does not depend on \theta, therefore, whole equation can be shortened to Equation 2, which represents the MLE (maximum likelihood estimation) objective to learn the model parameter \theta by maximizing the log likelihood of the training images X. From implementation point of view, the MLE objective can be optimized using the variations of stochastic gradient (ADAM, RMSProp, etc.) on mini-batches.

Network Architectures

As we are discussing deep generative models, here, we would like to discuss the deep aspect of AGMs. The parameterization of the conditionals mentioned in Equation 1 can be realized by different kind of network architectures. In the literature, several network architectures are proposed to increase their receptive fields and memory, allowing more complex distributions to be learned. Here, we are mentioning a couple of well known architectures, which are widely used in deep AGMs:

  1. Fully-visible sigmoid belief network (FVSBN): FVSBN is the simplest network without any hidden units and it is a linear combination of the input elements followed by a sigmoid function to keep output between 0 and 1. The positive aspects of this network is simple design and the total number of parameters in the model is quadratic which is much smaller compared to exponential [GHCC15].
  2. Neural autoregressive density estimator (NADE): To increase the effectiveness of FVSBN, the simplest idea would be to use one hidden layer neural network instead of logistic regression. NADE is an alternate MLP-based parameterization and more effective compared to FVSBN [LM11].
  3. Masked autoencoder density distribution (MADE): Here, the standard autoencoder neural networks are modified such that it works as an efficient generative models. MADE masks the parameters to follow the autoregressive property, where the current sample is reconstructed using previous samples in a given ordering [GGML15].
  4. PixelRNN/PixelCNN: These architecture are introducced by Google Deepmind in 2016 and utilizing the sequential property of the AGMs with recurrent and convolutional neural networks.
Different autoregressive architectures

Figure 2: Different autoregressive architectures (image source from [LM11]).

Results using different architectures

Results using different architectures (images source https://deepgenerativemodels.github.io).

It uses two different RNN architectures (Unidirectional LSTM and Bidirectional LSTM) to generate pixels horizontally and horizontally-vertically respectively. Furthermore, it ulizes residual connection to speed up the convergence and masked convolution to condition the different channels of images. PixelCNN applies several convolutional layers to preserve spatial resolution and increase the receptive fields. Furthermore, masking is applied to use only the previous pixels. PixelCNN is faster in training compared to PixelRNN. However, the outcome quality is better with PixelRNN [vdOKK16].

Summary

In this blog article, we discussed about deep autoregressive models in details with the mathematical foundation. Furthermore, we discussed about the training procedure including the summary of different network architectures. We did not discuss network architectures in details, we would continue the discussion of PixelCNN and its variations in upcoming blogs.

References

[GGML15] Mathieu Germain, Karol Gregor, Iain Murray, and Hugo Larochelle. MADE: masked autoencoder for distribution estimation. CoRR, abs/1502.03509, 2015.

[GHCC15] Zhe Gan, Ricardo Henao, David Carlson, and Lawrence Carin. Learning Deep Sigmoid Belief Networks with Data Augmentation. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence
and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 268–276, San Diego, California, USA, 09–12 May 2015. PMLR.

[LM11] Hugo Larochelle and Iain Murray. The neural autoregressive distribution estimator. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 29–37, Fort Lauderdale, FL, USA, 11–13 Apr 2011.
PMLR.

[SS05] Robert H. Shumway and David S. Stoffer. Time Series Analysis and Its Applications (Springer Texts in Statistics). Springer-Verlag, Berlin, Heidelberg, 2005.

[vdOKK16] A ̈aron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural
networks. CoRR, abs/1601.06759, 2016