Graphendatenbank Neo4j 5 Release veröffentlicht

Die neue Version der nativen Graphdatenbank bietet uneingeschränkte Skalierbarkeit, hohe Performance sowie diverse Verbesserungen in der Abfragesprache Cypher und im Index-Handling

München, 9. November 2022 – Neo4j, führender Anbieter von Graphtechnologie, stellt das Release Neo4j 5 vor. Mit der neuen Version setzt sich die native Graphdatenbank hinsichtlich ihrer Performance weiter von herkömmlichen, relationalen Datenbanksystemen ab.

Im Mittelpunkt von Neo4j 5 steht die Optimierung des Betriebs der Graphdatenbank. Dazu gehört eine uneingeschränkte Skalierbarkeit sowie eine hohe Performance für schnellere Abfragen – unabhängig von der Größe oder der Aufteilung des Datenbestands (Sharding). Diverse Verbesserungen in der Syntax der Abfragesprache Cypher, im Index-Handling, im Abfrage Planer und in der Implementierung ermöglichen es, Abfragen über mehrere Knoten hinweg deutlich einfacher auszudrücken und schneller Antworten zu erhalten.

Wie bereits frühere Versionen ist auch Neo4j 5 als Cloud Service verfügbar (Neo4j AuraDB und Neo4j AuraDS). Anwender können das neue Release ab sofort im Download-Center von Neo4j oder über die Cloud-Marktplätze von AWS, Azure und GCP beziehen.

Die wichtigsten Funktionen von Neo4j 5 im Überblick

  • Automatisches Clustering: Neo4j 5 bietet eine Cloud-fähige Architektur für globale Cluster, mit der sich Daten sowie Datenbanken skalieren lassen, ohne die Cluster selbst skalieren zu müssen. Die Platzierung von primären und sekundären Kopien auf dem Server im Cluster erfolgt dabei automatisch. Das reduziert nicht nur den manuellen Aufwand für Anwender, sondern stellt auch eine optimale Auslastung der Infrastruktur sicher.
  • Multi-Cluster Fabric: Mit Neo4j Fabric lassen sich individuelle Abfragen wieder zusammenführen und als Ganzes analysieren. In Neo4j 5 können Anwender nun via Cypher Kommandos Fabric Konfigurationen schneller erstellen und Abfragen sowohl innerhalb eines lokalen als auch entfernter Cluster durchführen. Separate Fabric-Proxys sind dafür nicht erforderlich.
  • Inkrementeller Import: Neo4j 5 ermöglicht es, große Datenmengen inkrementell in eine bestehende Datenbank einzubringen. Damit lässt sich die Datenladezeit drastisch reduzieren und eine höhere Flexibilität beim Laden großer Datensets erreichen.
  • Schnellere K-Hop-Abfragen. K-Hop ist eine Form von Deep Query, die eine große und variable Anzahl (K) von Hops beinhaltet, um alle eindeutigen Knoten im Umkreis des Startpunkts in einem Graphen zu finden. In der Regel wird diese Abfrage in Kombination mit Aggregationsfunktionen zum Zählen von Eigenschaften verwendet. In Neo4j 5 wurden K-Hop-Abfragen optimiert und die Antwortzeiten für 8-Hop-Abfragen um das 1000-fache verbessert.
  • Verbesserungen beim Graph Pattern Matching und optimierte Query Planung: Am Pfad gesetzte Filter für Beziehungen sowie differenzierte Label-Ausdrücke ermöglichen es Anwendern, MATCH-Klauseln einfacher zu schreiben und zu lesen. Darüber hinaus wurde die Query Planung für Cypher-Abfragen optimiert und ihre Ausführung damit beschleunigt.
  • Verbesserte Indizes: Indizes sind entscheidend, um möglichst schnell den besten Ausgangspunkt (z. B. Knoten, Kanten) für eine Abfrage zu finden. In Neo4j 5 wurde die Abgleichsmöglichkeiten von Indizes erweitert:
    FULLTEXT indiziert nun Listen und Arrays von Strings, um die Qualität der Textsuchergebnisse zu verbessern.
    RANGE ermöglicht die Angabe oder den Vergleich von Werten (z. B. Rezensionen 3-5 von Nutzern im PLZ-Bereich 8-9).
    Mit POINT, der häufig bei Routing- und Lieferkettenanalysen verwendet wird, lassen sich nun auch geospatiale Daten wie Längen- und Breitengrade finden und vergleichen.
  • Neo4j Ops Manager: Das Backend-Admin-Tool bietet ein intuitives Dashboard, mit dem Datenbankadministratoren Neo4j-Implementierungen (z. B. Datenbank, Instanz oder Cluster) monitoren und managen können.
  • Rolling Updates: Neo4j 5 beinhaltet kontinuierliche Updates für alle Implementierungen der Graphdatenbank ohne Ausfallzeiten – egal ob On-Premise, in der Cloud oder in hybriden Umgebungen. Zudem garantiert das neue Release eine durchgehende Kompatibilität zwischen selbst verwalteten und von Neo4j verwalteten Aura-Workloads.
  • Backup und Wiederherstellung: Optimierungen der Backup-Engine erlauben mehr Kontrolle und eine schnellere und einfachere Datensicherung. Dazu verfügt Neo4j 5 über ein differentielles Backup einschließlich eines einzelnen komprimierten Dateiarchivs, Point-in-Time-Wiederherstellung, APIs zur Überprüfung und Verwaltung von Sicherungsdateien sowie die Aktivierung einer Konsistenzprüfung.

„Der Einsatz von Graphdatenbanken ist in den letzten Jahren regelrecht explodiert. Unternehmen nutzen die Technologie, um ihre Daten sowie die Datenverbindungen im vollen Umfang zu analysieren und in der Praxis zu nutzen – sei es, um Prozesse weiter zu automatisieren, Risiken proaktiv zu bewerten oder datengestützte bzw. KI-basierte Entscheidungen zu treffen“, erklärt Emil Eifrem, CEO und Mitbegründer von Neo4j. „Neo4j 5 wurde mit diesen Zielen vor Augen weiter ausgebaut. Das neue Release bietet höhere Skalierbarkeit, Agilität und Performance, um Unternehmen in Sachen Datenmanagement und Data Analytics auf das nächste Level zu verhelfen.“

Mehr über das Neo4j 5 Release erfahren Sie auf der Neo4j Webseite sowie im Blog „Scale New Heights with Neo4j 5 Graph Database“. Melden Sie sich außerdem zur kostenlosen virtuellen Entwicklerkonferenz NODES 2022 (16. – 17. November) an, um an den Neo4j 5 Sessions „What’s New in Neo4j 5 and Aura 5 for Developers” und „Introducing Neo4j 5 for Administrators” teilzunehmen.

Bildmaterial zum Download (Quelle: Neo4j): Features in Neo4j 5

Google Cloud run with Infrastructure by Code using Terraform

Google Cloud Run – Tutorial

Es gibt Gelegenheiten, da ist eine oder mehrere serverlose Funktionen nicht ausreichend, um einen Service darzustellen. Für diese Fälle gibt es auf der Google Cloud Plattform Google Cloud Run. Cloud Run bietet zwei Möglichkeiten Container auszuführen. Services und Jobs. In diesem Beispiel wird ein Google Cloud Run Service mittels Terraform definiert, welcher auf Basis eines Scheduler Jobs regelmäßig aufgerufen wird. Cloud Build wird dazu genutzt den aktuellen Code auf den Service zu veröffentlichen.

Der nachfolgende Quellcode ist in GitHub verfügbar: https://github.com/fingineering/GCPCloudRunDemo

tl;dr

Mittels Terraform können alle notwendigen Komponenten erstellt werden, um einen Cloud Run Services aus einem Github Repository kontinuierlich zu aktualisieren. Als Beispiel wird ein stark vereinfachter Flask Webservice verwendet. Durch den Cloud Scheduler wird dieser Service regelmäßig aufgerufen.

Voraussetzungen

Bevor der Service aufgesetzt werden kann, müssen einige Voraussetzungen erfüllt sein. Es wird ein Google Cloud Project benötigt, sowie ein Github Account. Auf dem Computer, welcher zur Entwicklung verwendet werden soll, müssen Terraform, Google Cloud SDK, git, Docker und Python installiert sein. In diesem Beispiel wird Python verwendet, es ist aber mit jeder Sprache möglich, mit der ein WebServer erstellt werden kann.

  • Ein Google Cloud Projekt kann bei Google Cloud Plattform erstellt werden. Es wird nur ein Google Account benötigt, Neukunden erhalten ein kostenloses Guthaben von 300€ für 90 Tage.
  • Wenn noch nicht vorhanden sollte ein kostenloser Github Account auf Github erstellt werden. Das Beispiel kann auch mittels Google Cloud Source Repositories umgesetzt werden. Als Alternative zu Cloud Build kann Github Actions eingesetzt werden.
  • Terraform, Google Cloud SDK, Docker und Python müssen auf dem verwendeten Computer installiert werden, hierzu empfiehlt sich ein Paketmanager wie Homebrew oder Chocolatey. Linux Nutzer verwenden am besten den in ihrer Distribution mitgelieferten.
  • Soll nichts installiert werden, dann kann auch die Google Cloud Shell verwendet werden, diese findet sich im in der Cloud Console

APIs die in Google Cloud aktiviert werden müssen

Neben den Voraussetzungen zur Software müssen auf der Google Cloud Plattform einige APIs aktiviert werden:

  • Cloud Run API
  • Cloud Build API
  • Artifact Registry API
  • Cloud Scheduler API
  • Cloud Logging API
  • Identity and Access Management API

Die Cloud Run API wird benötigt um einen Cloud Run Service zu erstellen, die Artifact Registry wird benötigt, um die Container Abbilder zu speichern. Die Cloud Build API und die Identity and Access Management API werden benötigt, um eine CI/CD Pipeline zu implementieren. Cloud Scheduler wird in diesem Beispiel verwendet, um den Service regelmäßig aufzurufen. Da alle Services via Terraform erstellt und verwaltet werden, werden die APIs benötigt.

Infrastruktur

Das Erstellen der Infrastruktur läuft in mehreren Schritten ab, nur wenn App Code und Container bereits vorhanden sind, kann der gesamte Prozess automatisiert werden. Für die Definition der Infrastruktur wird ein Ordner “Infrastructure” erstellt und darin die Dateien main.tfvariables.tfund  terraform.tfvars.

Insgesamt werden vier Komponenten erstellt, das Artifact Registry Repository, ein Cloud Run Service, ein Cloud Build Trigger und ein Cloud Scheduler Job. Bevor die eigentliche Infrastruktur erzeugt werden kann, müssen einige Service Accounts definiert werden. Ziel ist es, das jedes Asset eine eigene Identität zugewiesen werden kann. Daher werden drei Service Accounts erstellt, für den Run Service, den Build Trigger und den Scheduler Job.

Da der erste Schritt die Einrichtung der Artifact Registry für den Cloud Run Service ist, wird dieser wie folgt hinzugefügt:

Nun kann der erste Schritt zum Aufsetzen der Infrastruktur mittels des Terraform Dreiklangs durchgeführt werden:

Die Beispiel Flask Anwendung

Als Beispielanwendung wird hier eine sehr simple Flask Webapp verwendet. Die Webapp beinhaltet eine einzige Route, es wird Hello World bei einem GET Request zurück gegeben und mittels POST kann die Nachricht personalisiert werden. Die Anwendung dient nur der Demonstration, es können fast beliebige Funktionalitäten umgesetzt werden.

Es ist auch nur zwingend notwendig flask oder Python zu verwenden, es kann jede Sprache und jedes Framework eingesetzt werden, welches einen Webserver implementieren kann und auf HTTP Anfragen reagieren kann. Flask selbst ist ein sogenanntes Micro Framework und kann flexibel eingesetzt werden, für mehr Informationen empfiehlt sich z.b. das Flask Mega Tutorial

Im Projektverzeichnis muss ein neuer Ordner App erzeugt werden, in diesem Ordner wird die Python Datei main.py, sowie die requirements.txt Datei erzeugt.

Dieser minimale Webservice kann local ausgeführt werden indem ein virtual environment erzeugt und die in requirements.txt spezifizierten Pakete installiert werden.

Die App kann nun local ausgeführt werden mittels:

Zum Testen kann im Browser die Adresse localhost:8080 aufgerufen werden oder mittels curl ein POST Request an den Service gesendet werden.

Der mit flask mitgelieferte Web Server sollte nur zu Entwicklungszwecken verwendet werden, in produktiven Umgebungen kann z.b. gunicorn eingesetzt werden. Gunicorn wird in diesem Beispiel später auch im Container verwendet werden.

Docker Container erstellen, ausführen und deployen

Um einen Service in Cloud Run auszuführen, muss dieser in einem Docker Container vorliegen. Dazu wird zunächst ein Dockerfile im App Ordner erstellt. Diese ist einfach gehalten, es basiert auf einem Python Container, kopiert die Dateien aus dem App Ordner und definiert das Start Kommando für Gunicorn.

In vielen Fällen sind im lokalen Entwicklungsordner Dateien vorhanden die nicht in den Container veröffentlicht werden sollten, damit Dateien explizit aus der Containererzeugung ausgeschlossen werden können kann eine .dockerignore Datei hinzugefügt werden. Diese funktioniert analog der .gitignore Dateien.

Um das Veröffentlichen auf die Artifact Registry zu vereinfachen, kann es eine gute Idee sein dem Namensschema der Registry zu folgen: location—docker.pkg.dev/your-project-id/registryname/containername:latest. Mittels docker build kann das Container Image erstellt werden:

Um das erstellt Image local zu testen, kann dieses mittels docker run auch lokal ausgeführt werden. Wichtig ist dabei zu beachten die notwendigen Umgebungsvariablen mit zugeben und den Port zu exponieren.

Werden im Webservice Google Identitäten verwendet, dann müssen Informationen über den zu verwendenden Google Account mitgegeben werden. Wie dies im Detail funktioniert findet sich unter Cloud Run lokal testen.

Den ersten Container manuell deployen

Bevor es möglich ist den Cloud Run Service zu erstellen muss das Container Abbild einmal manuell in die Artifact Registry veröffentlicht werden.

Erstellen und veröffentlichen des Container Abbilds kann auch in einem Kommando erfolgen:

Cloud Run Service aufsetzen

Da der initiale Container nun in der Aritfact Registry vorhanden ist, kann der Cloud Run Service daraus erstellt werden. Für den Cloud Run Service wird eine neue Resource im main.tf erstellt.

Dieser Service ist zunächst privat, alle Identitäten die diesen Service aufrufen wollen benötigen die Rolle roles/run.invoker. Da der Cloud Scheduler den Service regelmäßig aufrufen soll, muss die Identität des Schedulers Mitglied der Rolle sein.

Nun kann der Terraform Dreiklang verwendet werden den Service und den Scheduler Job zu erstellen.

Cloud Build Trigger erstellen

Der finale Schritt um ein kontinuierliches deployment des Services zu erreichen ist einen Cloud Build Trigger einzurichten. Der Cloud Build Trigger beobachtet Veränderungen am GitHub Repository und erstellt bei jedem neuen Commit auf dem main branch eine neue Version des Cloud Run Services. Die hier vorgestellte Pipeline beinhaltet nur das Erstellen und Veröffentlichen des Containers. Für eine produktive Implementation ist unbedingt zu empfehlen auch noch ein Testschritt mit einzufügen. Mit dem folgenden Code wird der Trigger mittels Terraform erstellt:

Der Cloud Build Trigger nutzt zur Definition des Deployment Processes die Datei cloudbuild.yaml, diese enthält die drei Schritte zum Erstellen des Container Abbilds, Veröffentlichen des Abbilds und Erzeugen einer neuen Version des Cloud Run Services.

  1. Erstellen des Container Abbilds mittels des Docker build Tools. Das erste Argument ist die Aktion build, das zweite und dritte beziehen sich auf den Tag des Images und das vierte gibt den Ort vor an dem nach dem Dockerfile gesucht wird
  2. Veröffentlichen des Container Images in die Artifact Registry mittels des Cloud Build Docker Tools. Als Argumente werden die Aktion push und das Ziel mitgegeben.
  3. Veröffentlichen der neuen Version des Images im Cloud Run Service mittels des Google Cloud SDK Tools gcloud

Alle drei Schritte nutzen Variablen, um Projektziel, Image Tag und Ort flexibel durch den Build Trigger zu steuern. Diese Variable werden bei der Erstellung des Triggers mit definiert, d.h. dieser finden sich in der Definition des Cloud Build Triggers in der Terraform Datei. Die Variablen werden substitutions genannt, es ist zu beachten, das nutzerdefinierte Variablen mit einem Unterstrich beginnen müssen, nur Systemvariablen, wie die PROJECT_ID.

Das Erstellen des Cloud Build Triggers kann versagen, in diesem Falle sollten die Einstellungen von Cloud Build in der Cloud Console geprüft werden. Die Service Account Berechtigungen für Cloud Run und Service Accounts müssen aktiviert sein, wie im Bild unten.

Service Account Berechtigungen für Cloud Run und Service Accounts

Service Account Berechtigungen für Cloud Run und Service Accounts

Zusammenfassung

Mit Hilfe von Terraform ist es möglich ein vollständig in Code definierten, kontinuierlich veröffentlichten Google Cloud Run Service zu erstellen. Dazu werden GCP Services verwendet, eine Flask Webapp in einem Container zu verpacken und diesen auf Cloud Run zu veröffentlichen.

Für Fragen erstellt gerne ein Issue oder ihr findet mich auf LinkedIn.

Der Quellcode ist in GitHub verfügbar: https://github.com/fingineering/GCPCloudRunDemo

Control the visibility of the PowerBI visuals based on condition

In PowerBI, there is no direct or functional mechanism to adjust the visibility (Show/Hide) of visualizations based on filter choices. There is, however, a workaround that enables us to show/hide visuals based on filter condition.

The fundamental concept behind this technique is to apply a mask to a visual and change its opacity based on a condition or filter selection.

Use Case:

I have detail table of orders. These orders are divided into Consumer, Home Office, and Corporation categories. I use segment as a filter. One of the requirements is to present a table of detail if the overall profit for the selected segment is less than $100,000. To do this, this task will be divided into two major parts. First, we will display the table if the filter is selected. Next, we will add a condition to the table.

Step 1: Show table only filter is selected

  • Place filter (Slicer) and visual on the Report Pane.

  • Create a measure that will determine if the filter is selected or not.

Filter_Selected = IF(ISFILTERED(Orders[Segment]),1,0)

  • Add this measure to the filter pane of the table visualization and select the show item when the value is 1 option. This will ensure that when no options are selected, only the header is displayed.

  • Set the mask down on the table. Make sure you only mask the table header with a border color that matches your background, or remove it entirely.

  • Create a measure to change the mask’s transparency. If two zeros are appended to the end of any HAX code, this represents complete transparency.

mask_transparency =IF([Filter_Selected],”#FFFFFF00″,”#FFFFFF”)

  • Keep this measure on the Fill of the mask and add conditional formatting to it.

If the mask transparency(measure) field is grayed out during the previous steps, you may need to modify the data type of mask transparency to text.

Step 2 : Add a condition to the solution

  • Create a new measure to determine if our condition is met.

condition_check = IF(CALCULATE(SUM(Orders[Profit]),filter(all(Orders), Orders[Segment] = SELECTEDVALUE(Orders[Segment]))) < 100000,1,0)

  • Now add this new measure to a table visual’s filter pane and pick the show item when the value is 1 option. This ensures that only if the condition meets the table will appear.

You can now display or hide visuals based on slicer selection and condition. If you know a better way to do this, please comment and let me know. For this article, I referred to this page.

 

5 Apache Spark Best Practices

Already familiar with the term big data, right? Despite the fact that we would all discuss Big Data, it takes a very long time before you confront it in your career. Apache Spark is a Big Data tool that aims to handle large datasets in a parallel and distributed manner. Apache Spark began as a research project at UC Berkeley’s AMPLab, a student, researcher, and faculty collaboration centered on data-intensive application domains, in 2009. 

Introduction

Spark’s aim is to create a new framework that was optimized for quick iterative processing, such as machine learning and interactive data analysis while retaining Hadoop MapReduce’s scalability and fault-tolerant. Spark outperforms Hadoop in many ways, reaching performance levels that are nearly 100 times higher in some cases. Spark has a number of components for various types of processing, all of which are based on Spark Core. Today we will be going to discuss in brief the Apache  Spark and 5 of its best practices to look forward to-

What is Apache Spark?

Apache Spark is an open-source distributed system for big data workforces. For fast analytic queries against another size of data, it uses in-memory caching and optimised query execution. It is a parallel processing framework for grouped computers to operate large-scale data analytics applications. This could handle packet and real-time data processing and predictive analysis workloads.

It claims to support code reuse all over multiple workloads—batch processing, interactive queries, real-time analytics, machine learning, and graph processing—and offers development APIs in Java, Scala, Python, and R. With 365,000 meetup members in 2017, Apache Spark is becoming one of the most renowned big data distributed processing frameworks. Explore for Apache Spark Tutorial for more information.

5 best practices of Apache Spark

1. Begin with a small sample of the data.

Because we want to make big data work, we need to start with a small sample of data to see if we’re on the right track. In my project, I sampled 10% of the data and verified that the pipelines were working properly. This allowed me to use the SQL section of the Spark UI to watch the numbers grow throughout the flow while not having to wait too long for it to complete.

In my experience, if you attain your preferred runtime with a small sample, scaling up is usually simple.

2. Spark troubleshooting

For transformations, Spark seems to have a lazy loading behaviour. That is, it will not initiate the transformation computation; instead, it will keep records of the transformation requested. This makes it difficult to determine where in our code there are bugs or areas that need to be optimised. Splitting the code into sections with df.cache() and then using df.count() to force Spark to calculate the df at every section was one practise that we found useful.

Spark actions seem to be keen in that they cause the underlying action to perform a computation. So, if you’ve had a Spark action which you only call when it’s required, pay attention. A Spark action, for instance, is count() on a dataset. You can now inspect the computation of each section using the spark UI and identify any issues. It’s important to note that if you don’t use the sampling we mentioned in (1), you’ll probably end up with a very long runtime that’s difficult to debug.

Check out Apache Spark Training & Certification Course to get yourself certified in Apache Spark with industry-level skills.

3. Finding and resolving Skewness is a difficult task.

Having to look at the stage specifics in the spark UI and looking for just a major difference between both the max and median can help you find the Skewness:

Let’s begin with a definition of Skewness. As previously stated, our data is divided into partitions, and the size of each partition will most likely change as the progress of transformation. This can result in a large difference in size between partitions, indicating that our data is skew. This implies that a few of the tasks were markedly slower than the rest.

Why is this even a bad thing? Because it may cause other stages to stand in line for these few tasks, leaving cores idle. If you understand where all the Skewness has been coming from, you can fix it right away by changing the partitioning.

4. Appropriately cache

Spark allows you to cache datasets in memory. There are a variety of options to choose from:

  • Since the same operation has been computed several times in the pipeline flow, cache it.
  • To allow the required cache setting, use the persist API to enable caching (persist to disc or not; serialized or not).
  • Be cognizant of lazy loading and, if necessary, prime cache up front. Some APIs are eager, while others aren’t.
  • To see information about the datasets you’ve cached, go to the Storage tab in the Spark UI.
  • It’s a good idea to unpersist your cached datasets after you’ve finished using them to free up resources, especially if other people are using the cluster.

5. Spark has issues with iterative code.

It was particularly difficult. Spark uses lazy evaluation so that when the code is run, it only creates a computational graph, a DAG. Once you have an iterative process, however, this method can be very problematic so because DAG finally opens the prior iteration and then becomes extremely large, we mean extremely large. This may be too large for the driver to remember. Because the application is stuck, this makes it appear in the spark UI as if no jobs are running (which is correct) for an extended period of time — until the driver crashes.

This seems to be presently an obvious issue with Spark, and the workaround that worked for me was to use df.checkpoint() / df.reset() / df.reset() / df.reset() / df.reset() / df. every 5–6 iterations, call localCheckpoint() (find your number by experimenting a bit). This works because, unlike cache(), checkpoint() breaks the lineage and the DAG, saves the results and starts from a new checkpoint. The disadvantage is that you don’t have the entire DAG to recreate the df if something goes wrong.

Conclusion

Spark is now one of the most popular projects inside the Hadoop ecosystem, with many companies using it in conjunction with Hadoop to process large amounts of data. In June 2013, Spark was acknowledged into the Apache Software Foundation’s (ASF) entrepreneurial context, and in February 2014, it was designated as an Apache Top-Level Project. Spark could indeed run by itself, on Apache Mesos, or on Apache Hadoop, which is the most common. Spark is used by large enterprises working with big data applications because of its speed and ability to connect multiple types of databases and run various types of analytics applications.

Learning how to make Spark work its magic takes time, but these 5 practices will help you move your project forward and sprinkle some spark charm on your code.

process.science presents a new release

Advertisement

Process Mining Tool provider process.science presents a new release

process.science, specialist in the development of process mining plugins for BI systems, presents its upgraded version of their product ps4pbi. Process.science has added the following improvements to their plug-in for Microsoft Power BI. Identcal upgrades will soon also be released for ps4qlk, the corresponding plug-in for Qlik Sense:

  • 3x faster performance: By improvement of the graph library the graph built got approx. 300% more performant. This is particularly noticeable in complex processes
  • Navigator window: For a better overview in complex graphs, an overview window has been added, in which the entire graph and the respective position of the viewed area within the overall process is displayed
  • Activities legend: This allows activities to be assigned to specific categories and highlighted in different colors, for example in which source system an activity was carried out
  • Activity drill-through: This makes it possible to take filters that have been set for selected activities into other dashboards
  • Value Color Scale: Activity values ​​can be color-coded and assigned to freely selectable groupings, which makes the overview easier at first sight
process.science Process Mining on Power BI

process.science Process Mining on Power BI

Process mining is a business data analysis technique. The software used for this extracts the data that is already available in the source systems and visualizes them in a process graph. The aim is to ensure continuous monitoring in real time in order to identify optimization measures for processes, to simulate them and to continuously evaluate them after implementation.

The process mining tools from process.science are integrated directly into Microsoft Power BI and Qlik Sense. A corresponding plug-in for Tableau is already in development. So it is not a complicated isolated solution requires a new set up in addition to existing systems. With process.science the existing know-how on the BI system already implemented and the existing infrastructure framework can be adapted.

The integration of process.science in the BI systems has no influence on day-to-day business and bears absolutely no risk of system failures, as process.science does not intervene in the the source system or any other program but extends the respective business intelligence tool by the process perspective including various functionalities.

Contact person for inquiries:

process.science GmbH & Co. KG
Gordon Arnemann
Tel .: + 49 (231) 5869 2868
Email: ga@process.science
https://de.process.science/

Process Mining mit Fluxicon Disco – Artikelserie

Dieser Artikel der Artikelserie Process Mining Tools beschäftigt sich mit dem Anbieter Fluxicon. Das im Jahr 2010 gegründete Unternehmen, bis heute geführt von den zwei Gründern Dr. Anne Rozinat und Dr. Christian W. Günther, die beide bei Prof. Wil van der Aalst in Eindhoven promovierten, sowie einem weiteren Mitarbeiter, ist eines der ersten Tool-Anbieter für Process Mining. Das Tool Disco ist das Kernprodukt des Fluxicon-Teams und bietet pures Process Mining.

Die beiden Gründer haben übrigens eine ganze Reihe an Artikeln zu Process Mining (ohne Sponsoring / ohne Entgelt) veröffentlicht.

Lösungspakete: Standard-Lizenz
Zielgruppe:  Lauf Fluxicon für Unternehmen aller Größen.
Datenquellen: Keine Standard-Konnektoren. Benötigt fertiges Event Log.
Datenvolumen: Unlimitierte Datenmengen, Beschränkung nur durch Hardware.
Architektur: On-Premise / Desktop-Anwendung

Diese Software für Process Mining ist für jeden, der in Process Mining reinschnuppern möchte, direkt als Download verfügbar. Die Demo-Lizenz reicht aus, um eigene Event-Logs auszuprobieren oder das mitgelieferte Event-Log (Sandbox) zu benutzen. Es gibt ferner mehrere Evaluierungslizenz-Modelle sowie akademische Lizenzen via Kooperationen mit Hochschulen.

Fluxicon Disco erfreut sich einer breiten Nutzerbasis, die seit 2012 über das jährliche ‘Process Mining Camp’ (https://fluxicon.com/camp/index und http://processminingcamp.com ) und seit 2020 auch über das monatliche ‘Process Mining Café’ (https://fluxicon.com/cafe/) vorangetrieben wird.

Bedienbarkeit und Anpassungsfähigkeit der Analysen

Fluxicon Disco bietet den Vorteil des schnellen Einstiegs in datengetriebene Prozessanalysen und ist überaus nutzerfreundlich für den Analysten. Die Oberflächen sind leicht zu bedienen und die Bedeutung schnell zu erfassen oder zumindest zu erahnen. Die Filter-Möglichkeiten sind überraschend umfangreich und äußerst intuitiv bedien- und kombinierbar.

Fluxicon Disco Process Mining

Fluxicon Disco Process Mining – Das Haupt-Dashboard zeigt den Process Flow aus der Rekonstruktion auf Basis des Event Logs. Hier wird die Frequenz-Ansicht gezeigt, die Häufigkeiten von Cases und Events darstellt.

Disco lässt den Analysten auf Process Mining im Kern fokussieren, es können keine Analyse-Diagramme strukturell hinzugefügt, geändert oder gelöscht werden, es bleibt ein statischer Report ohne weitere BI-Funktionalitäten.

Die Visualisierung des Prozess-Graphen im Bereich “Map” ist übersichtlich, stets gut lesbar und leicht in der Abdeckung zu steuern. Die Hauptmetrik kann zwischen der Frequenz- zur Zeit-Orientierung hin und her geschaltet werden. Neben der Hauptmetrik kann auch eine zweite Metrik (Secondary Metric) zur Ansicht hinzugefügt werden, was sehr sinnvoll ist, wenn z. B. neben der durchschnittlichen Zeit zwischen Prozessaktivitäten auch die Häufigkeit dieser Prozessfolgen in Relation gesetzt werden soll.

Die Ansicht “Statistics” zeigt die wesentlichen Einblicke nach allen Dimensionen aus statistischer Sicht: Welche Prozessaktivitäten, Ressourcen oder sonstigen Features treten gehäuft auf? Diese Fragen werden hier leicht beantwortet, ohne dass der Analyst selbst statistische Berechnungen anstellen muss – jedoch auch ohne es zu dürfen, würde er wollen.

Die weitere Ansicht “Cases” erlaubt einen Einblick in die Prozess-Varianten und alle Einzelfälle innerhalb einer Variante. Diese Ansicht ist wichtig für Prozessoptimierer, die Optimierungspotenziale vor allem in häufigen, sich oft wiederholenden Prozessverläufen suchen möchten. Für Compliance-Analysten sind hingegen eher die oft vielen verschiedenen Einzelfälle spezieller Prozessverläufe der Fokus.

Für Einsteiger in Process Mining als Methodik und Disco als Tool empfiehlt sich übrigens das Process Mining Online Book: https://processminingbook.com

Integrationsfähigkeit

Fluxicon Disco ist eine Desktop-Anwendung, die nicht als Cloud- oder Server-Version verfügbar ist. Es ist möglich, die Software auf einem Windows Application Server on Premise zu installieren und somit als virtuelle Umgebung via Microsoft Virtual Desktop oder via Citrix als virtuelle Anwendung für mehrere Anwender zugleich verfügbar zu machen. Allerdings ist dies keine hochgradige Integration in eine Enterprise-IT-Infrastruktur.

Auch wird von Disco vorausgesetzt, dass Event Logs als einzelne Tabellen bereits vorliegen müssen. Dieses Tool ist also rein für die Analyse vorgesehen und bietet keine Standardschnittstellen mit vorgefertigten Skripten zur automatischen Herstellung von Event Logs beispielsweise aus Salesforce CRM oder SAP ERP.

Grundsätzlich sollte Process Mining methodisch stets als Doppel-Disziplin betrachtet werden: Der erste Teil des Process Minings fällt in die Kategorie Data Engineering und umfasst die Betrachtung der IT-Systeme (ERP, CRM, SRM, PLM, DMS, ITS,….), die für einen bestimmten Prozess relevant sind, und die in diesen System hinterlegten Datentabellen als Datenquellen. Die in diesen enthaltenen Datenspuren über Prozessaktivitäten müssen dann in ein Prozessprotokoll überführt und in ein Format transformiert werden, das der Inputvoraussetzung als Event Log für das jeweilige Process Mining Tool gerecht wird. Minimalanforderung ist hierbei zumindest eine Vorgangsnummer (Case ID), ein Zeitstempel (Event Time) einer Aktivität und einer Beschreibung dieser Aktivität (Event).

Das Event Log kann dann in ein oder mehrere Process Mining Tools geladen werden und die eigentliche Prozessanalyse kann beginnen. Genau dieser Schritt der Kategorie Data Analytics kann in Fluxicon Disco erfolgen.

Zum Einspeisen eines Event Logs kann der klassische CSV-Import verwendet werden oder neuerdings auch die REST-basierte Airlift-Schnittstelle, so dass Event Logs direkt von Servern On-Premise oder aus der Cloud abgerufen werden können.

Prinzip des direkten Zugriffs auf Event Logs von Servern via Airlift.

Import von Event Logs als CSV (“Open file”) oder von Servern auch aus der Cloud.

Sind diese Limitierungen durch die Software für ein Unternehmen, bzw. für dessen Vorhaben, vertretbar und bestehen interne oder externe Ressourcen zum Data Engineering von Event Logs, begeistert die Einfachheit von Process Mining mit Fluxicon Disco, die den schnellsten Start in diese Analyse verspricht, sofern die Daten als Event Log vorbereitet vorliegen.

Skalierbarkeit

Die Skalierbarkeit im Sinne hochskalierender Datenmengen (Big Data Readiness) sowie auch im Sinne eines Ausrollens dieser Analyse-Software auf einer Konzern-Ebene ist nahezu nicht gegeben, da hierzu Benutzer-Berechtigungsmodelle fehlen. Ferner darf hierbei nicht unberücksichtigt bleiben, dass Disco, wie zuvor erläutert, ein reines Analyse-/Visualisierungstool ist und keine Event Logs generieren kann (der Teil der Arbeit, der viele Hardware Ressourcen benötigt).

Für die reine Analyse läuft Disco jedoch auch mit vielen Daten sehr zügig und ist rein auf Ebene der Hardware-Ressourcen limitiert. Vertikales Upscaling ist auf dieser Ebene möglich, dazu empfiehlt sich diese Leselektüre zum System-Benchmark.

Zukunftsfähigkeit

Fluxicon Disco ist eines der Process Mining Tools der ersten Stunde und wird auch heute noch stetig vom Fluxicon Team mit kleinen Updates versorgt, die Weiterentwicklung ist erkennbar, beschränkt sich jedoch auf Process Mining im Kern.

Preisgestaltung

Die Preisgestaltung wird, wie auch bei den meisten anderen Anbietern für Process Mining Tools, nicht transparent kommuniziert. Aus eigener Einsatzerfahrung als Berater können mit Preisen um 1.000 EUR pro Benutzer pro Monat gerechnet werden, für Endbenutzer in Anwenderunternehmen darf von anderen Tarifen ausgegangen werden.

Studierende von mehr als 700 Universitäten weltweit (siehe https://fluxicon.com/academic/) können Fluxicon Disco kostenlos nutzen und das sehr unkompliziert. Sie bekommen bereits automatisch akademische Lizenzen, sobald sie sich mit ihrer Uni-Email-Adresse in dem Tool registrieren. Forscher und Studierende, deren Uni noch kein Partner ist, können sehr leicht auch individuelle akademische Lizenzen anfragen.

Fazit

Fluxicon Disco ist ein Process Mining Tool der ersten Stunde und das bis heute. Das Tool beschränkt sich auf das Wesentliche, bietet keine Big Data Plattform mit Multi-User-Management oder anderen Möglichkeiten integrierter Data Governance, auch sind keine Standard-Schnittstellen zu anderen IT-Systemen vorhanden. Auch handelt es sich hierbei nicht um ein Tool, das mit anderen BI-Tools interagieren oder gar selbst zu einem werden möchte, es sind keine eigenen Report-Strukturen erstellbar. Fluxicon Disco ist dafür der denkbar schnellste Einstieg mit minimaler Rüstzeit in Process Mining für kleine bis mittelständische Unternehmen, für die Hochschullehre und nicht zuletzt auch für Unternehmensberatungen oder Wirtschaftsprüfungen, die ihren Kunden auf schlanke Art und Weise Ist-Prozessanalysen ergebnisorientiert anbieten möchten.

Dass Disco seitens Fluxicon nur für kleine und mittelgroße Unternehmen bestimmt ist, ist nicht ganz zutreffend. Die meisten Kunden sind grosse Unternehmen (Banken, Versicherungen, Telekommunikationsanabieter, Ministerien, Pharma-Konzerne und andere), denn diese haben komplexe Prozesse und somit den größten Optimierungsbedarf. Um Process Mining kommen die Unternehmen nicht herum und so sind oft auch mehrere Tools verschiedener Anbieter im Einsatz, die sich gegenseitig um ihre Stärken ergänzen, für Fluxicon Disco ist dies die flexible Nutzung, nicht jedoch das unternehmensweite Monitoring. Der flexible und schlanke Einsatz von Disco in vielen Unternehmen zeigt sich auch mit Blick auf die Sprecher und Teilnehmer der jährlichen Nutzerkonferenz, dem Process Mining Camp.

My elaborate study notes on reinforcement learning

I will not tell you why, but all of a sudden I was in need of writing an article series on Reinforcement Learning. Though I am also a beginner in reinforcement learning field. Everything I knew was what I learned from one online lecture conducted in a lazy tone in my college. However in the process of learning reinforcement learning, I found a line which could connect the two dots, one is reinforcement learning and the other is my studying field. That is why I made up my mind to make an article series on reinforcement learning seriously.

To be a bit more concrete, I imagine that technologies in our world could be enhanced by a combination of reinforcement learning and virtual reality. That means companies like Toyota or VW might come to invest on visual effect or video game companies more seriously in the future. And I have been actually struggling with how to train deep learning with cgi, which might bridge the virtual world and the real world.

As I am also a beginner in reinforcement learning, this article series would a kind of study note for me. But as I have been doing in my former articles, I prefer exhaustive but intuitive explanations on AI algorithms, thus I will do my best to make my series as instructive and effective as existing tutorial on reinforcement learning.

This article is going to be composed of the following contents.

In this article I would like to share what I have learned about RL, and I hope you could get some hints of learning this fascinating field. In case you have any comments or advice on my “study note,” leaving a comment or contacting me via email would be appreciated.

Coffee Shop Location Predictor

As part of this article, we will explore the main steps involved in predicting the best location for a coffee shop in Vancouver. We will also take into consideration that the coffee shop is near a transit station, and has no Starbucks near it. Well, while at it, let us also add an extra feature where we make sure the crime in the area is lower.

Introduction

In this article, we will highlight the main steps involved to predict a location for a coffee shop in Vancouver. We also want to make sure that the coffee shop is near a transit station, and has no Starbucks near it. As an added feature, we will make sure that the crime concentration in the area is low, and the entire program should be implemented in Python. So let’s walk through the steps.

Steps Required

  • Get crime history for the last two years
  • Get locations of all transit stations and Starbucks in Vancouver
  • Check all the transit stations that do not have any Starbucks near them
  • Get all the data regarding crimes near the filtered transit stations
  • Create a grid of all possible coordinates around the transit station
  • Check crime around each created coordinate and display the top 5 locations.

Gathering Data

This covers the first two steps required to get data from the internet, both manually and automatically.

Getting all Crime History

We can get crime history for the past 14 years in Vancouver from here. This data is in raw crime.csv format, so we have to process it and filter out useless data. We then write this processed information on the crime_processed.csv file.

Note: There are 530,653 records of crime in this file

In this program, we will just use the type and coordinate of the crime. There are many crime types, but we have classified them into three major categories namely;

Theft (red), Break and Enter (orange) and Mischief (green)

These all crimes can be plotted on Graph as displayed below.

This may seem very congested and full, so let’s see a closeup image for future references.

Getting Locations of all Rapid Transit Stations

We can get the coordinates of all Transit Stations in Vancouver from here. This dataset has all coordinates of rapid transit stations in three transit lines in Vancouver. There are a total of 23 of them in Vancouver, we can then use it for further processing.

Getting Locations of all Starbucks

The Starbucks data is present here, we can scrape it easily and get the locations of all the Starbucks in Vancouver. We just need the Starbucks that is near transit stations, so we’ll filter out the rest. There are a total 24 Starbucks in Vancouver, and 10 of them are near Transit Stations.

Note: Other than the coordinates of Transit Stations and Starbucks, we also need coordinates and type of the crime.

Transit Stations with no Starbucks

As we have all the data required, now moving to the next step. We need to get to the transit Station locations that have no Starbucks near them. For that we can create an area of particular radius around each Transit Station. Then check all Starbucks locations with respect to them, whether they are within that area or not.

If none of the Starbucks are within that particular Transit Station’s area, we can append it to a list. At the end, we have a list of all Transit locations with no Starbucks near them. There are a total of 6 Transit Stations with no Starbucks near them.

Crime near Transit Stations

Now lets filter out all crime records and get just what we are interested in, which means the crime near Transit stations. For that we will plot an area of specific radius around each of them to see the crimes. These are more than 110,000 crime records.

Crime near located Transit Stations

Now that we have all the Transit Stations that don’t have any Starbucks near them and also the crime near all Transit Stations. So, let’s use this information and get crime near the located Transit Stations. These are about 44,000 crime records.

This may seem correct at first glance, but the points are overlapping due to abundance, so we can create different lists of crimes based on their types.

Theft

Break and Enter

Mischief

Generating all possible coordinates

Now finally, we have all the prerequisites and let’s get to the main task at hand, predicting the best coordinate for the coffee shop.

There may be many approaches to solve this problem, but the one I used in this program is that I will create a grid of all possible locations (coordinates) in the area of 1 km radius around each located transit station.

Initially I generated 1 coordinate for every m, this resulted in 1000,000 coordinates in every km. This is a huge number, and for the 6 located Transit stations, it becomes 6 Million. It may not seem much at first glance because computers can handle such data in a few seconds.

But for location prediction we need to compare each coordinate with crime coordinates. As the algorithm has to check for ~7,000 Thefts, ~19,000 Break ins, and ~17,000 Mischiefs around each generated coordinate. Computing this would want the program to process an estimate of 432.4 Billion times. This sort of execution takes many hours on normal computers (sometimes days).

The solution to this is to create a coordinate for each 10 m area, this results about 10,000 coordinate per km. For the above mentioned number of crimes, the estimated processes will be several Billions. That would significantly reduce the time, but is still not less.

To control this, we can remove the duplicate values in crime coordinates and those which are too close to each other ~1m. Doing so, we are left with just 816 Thefts, 2,654 Break ins, and 8,234 Mischiefs around each generated coordinate.
The precision will not be affected much but the time and computational resources required will be reduced a lot.

 

Checking Crime near Generated coordinates

Now that we have all the locations, we will start some processing on it and check each coordinate against some constraints. That are respectively;

  1. Filter out Coordinates having Theft near 1 km
    We get 122,000 coordinates with no Thefts (Below merged 1000 to 1)
  2. Filter out Coordinates having Break Ins near 200m
    We get 8000 coordinates with no Thefts (Below merged 1000 to 1)
  3. Filter out Coordinates having Mischief near 200m
    We get 6000 coordinates with no Thefts (Below merged 1000 to 1)
    Now that we have 6 Coordinates of best locations that have passed through all the constraints, we will order them.To order them, we will check their distance from the nearest transit location. The nearest will be on top of the list as the best possible location, then the second and so on. The generated List is;

    1. -123.0419406741792, 49.24824259252004
    2. -123.05887151659479, 49.24327221040713
    3. -123.05287151659476, 49.24327221040713
    4. -123.04994067417924, 49.239242592520064
    5. -123.0419406741792, 49.239242592520064
    6. -123.0409406741792, 49.239242592520064

How can MindTrades help?

MindTrades Consulting Services, a leading marketing agency provides in-depth analysis and insights for the global IT sector including leading data integration brands such as Diyotta. From Cloud Migration, Big Data, Digital Transformation, Agile Deliver, Cyber Security, to Analytics- Mind trades provides published breakthrough ideas, and prompt content delivery. For more information, refer to mindtrades.com.

Code

https://github.com/Mindtrades-Consulting/Coffee-Shop-Location-Predictor

 

Rethinking linear algebra part two: ellipsoids in data science

*This is the fourth article of my article series “Illustrative introductions on dimension reduction.”

1 Our expedition of eigenvectors still continues

This article is still going to be about eigenvectors and PCA, and this article still will not cover LDA (linear discriminant analysis). Hereby I would like you to have more organic links of the data science ideas with eigenvectors.

In the second article, we have covered the following points:

  • You can visualize linear transformations with matrices by calculating displacement vectors, and they usually look like vectors swirling.
  • Diagonalization is finding a direction in which the displacement vectors do not swirl, and that is equal to finding new axis/basis where you can describe its linear transformations more straightforwardly. But we have to consider diagonalizability of the matrices.
  • In linear dimension reduction such as PCA or LDA, we mainly use types of matrices called positive definite or positive semidefinite matrices.

In the last article we have seen the following points:

  • PCA is an algorithm of calculating orthogonal axes along which data “swell” the most.
  • PCA is equivalent to calculating a new orthonormal basis for the data where the covariance between components is zero.
  • You can reduced the dimension of the data in the new coordinate system by ignoring the axes corresponding to small eigenvalues.
  • Covariance matrices enable linear transformation of rotation and expansion and contraction of vectors.

I emphasized that the axes are more important than the surface of the high dimensional ellipsoids, but in this article let’s focus more on the surface of ellipsoids, or I would rather say general quadratic curves. After also seeing how to draw ellipsoids on data, you would see the following points about PCA or eigenvectors.

  • Covariance matrices are real symmetric matrices, and also they are positive semidefinite. That means you can always diagonalize covariance matrices, and their eigenvalues are all equal or greater than 0.
  • PCA is equivalent to finding axes of quadratic curves in which gradients are biggest. The values of quadratic curves increases the most in those directions, and that means the directions describe great deal of information of data distribution.
  • Intuitively dimension reduction by PCA is equal to fitting a high dimensional ellipsoid on data and cutting off the axes corresponding to small eigenvalues.

Even if you already understand PCA to some extent, I hope this article provides you with deeper insight into PCA, and at least after reading this article, I think you would be more or less able to visually control eigenvectors and ellipsoids with the Numpy and Maplotlib libraries.

*Let me first introduce some mathematical facts and how I denote them throughout this article in advance. If you are allergic to mathematics, take it easy or please go back to my former articles.

  • Any quadratic curves can be denoted as \boldsymbol{x}^T A\boldsymbol{x} + 2\boldsymbol{b}^T\boldsymbol{x} + s = 0, where \boldsymbol{x}\in \mathbb{R}^D , A \in \mathbb{R}^{D\times D} \boldsymbol{b}\in \mathbb{R}^D s\in \mathbb{R}.
  • When I want to clarify dimensions of variables of quadratic curves, I denote parameters as A_D, b_D.
  • If a matrix A is a real symmetric matrix, there exist a rotation matrix U such that U^T A U = \Lambda, where \Lambda = diag(\lambda_1, \dots, \lambda_D) and U = (\boldsymbol{u}_1, \dots , \boldsymbol{u}_D). \boldsymbol{u}_1, \dots , \boldsymbol{u}_D are eigenvectors corresponding to \lambda_1, \dots, \lambda_D respectively.
  • PCA corresponds to a case of diagonalizing A where A is a covariance matrix of certain data. When I want to clarify that A is a covariance matrix, I denote it as A=\Sigma.
  • Importantly covariance matrices \Sigma are positive semidefinite and real symmetric, which means you can always diagonalize \Sigma and any of their engenvalues cannot be lower than 0.

*In the last article, I denoted the covariance of data as S, based on Pattern Recognition and Machine Learning by C. M. Bishop.

*Sooner or later you are going to see that I am explaining basically the same ideas from different points of view, using the topic of PCA. However I believe they are all important when you learn linear algebra for data science of machine learning. Even you have not learnt linear algebra or if you have to teach linear algebra, I recommend you to first take a review on the idea of diagonalization, like the second article. And you should be conscious that, in the context of machine learning or data science, only a very limited type of matrices are important, which I have been explaining throughout this article.

2 Rotation or projection?

In this section I am going to talk about basic stuff found in most textbooks on linear algebra. In the last article, I mentioned that if A is a real symmetric matrix, you can diagonalize A with a rotation matrix U = (\boldsymbol{u}_1 \: \cdots \: \boldsymbol{u}_D), such that U^{-1}AU = U^{T}AU =\Lambda, where \Lambda = diag(\lambda_{1}, \dots , \lambda_{D}). I also explained that PCA is a case where A=\Sigma, that is, A is the covariance matrix of certain data. \Sigma is known to be positive semidefinite and real symmetric. Thus you can always diagonalize \Sigma and any of their engenvalues cannot be lower than 0.

I think we first need to clarify the difference of rotation and projection. In order to visualize the ideas, let’s consider a case of D=3. Assume that you have got an orthonormal rotation matrix U = (\boldsymbol{u}_1 \: \boldsymbol{u}_2 \: \boldsymbol{u}_3) which diagonalizes A. In the last article I said diagonalization is equivalent to finding new orthogonal axes formed by eigenvectors, and in the case of this section you got new orthonoramal basis (\boldsymbol{u}_1, \boldsymbol{u}_2, \boldsymbol{u}_3) which are in red in the figure below. Projecting a point \boldsymbol{x} = (x, y, z) on the new orthonormal basis is simple: you just have to multiply \boldsymbol{x} with U^T. Let U^T \boldsymbol{x} be (x', y', z')^T, and then \left( \begin{array}{c} x' \\ y' \\ z' \end{array} \right) = U^T\boldsymbol{x} = \left( \begin{array}{c} \boldsymbol{u}_1^{T}\boldsymbol{x} \\ \boldsymbol{u}_2^{T}\boldsymbol{x} \\ \boldsymbol{u}_3^{T}\boldsymbol{x} \end{array} \right). You can see x', y', z' are \boldsymbol{x} projected on \boldsymbol{u}_1, \boldsymbol{u}_2, \boldsymbol{u}_3 respectively, and the left side of the figure below shows the idea. When you replace the orginal orthonormal basis (\boldsymbol{e}_1, \boldsymbol{e}_2, \boldsymbol{e}_3) with (\boldsymbol{u}_1, \boldsymbol{u}_2, \boldsymbol{u}_3) as in the right side of the figure below, you can comprehend the projection as a rotation from (x, y, z) to (x', y', z') by a rotation matrix U^T.

Next, let’s see what rotation is. In case of rotation, you should imagine that you rotate the point \boldsymbol{x} in the same coordinate system, rather than projecting to other coordinate system. You can rotate \boldsymbol{x} by multiplying it with U. This rotation looks like the figure below.

In the initial position, the edges of the cube are aligned with the three orthogonal black axes (\boldsymbol{e}_1,  \boldsymbol{e}_2 , \boldsymbol{e}_3), with one corner of the cube located at the origin point of those axes. The purple dot denotes the corner of the cube directly opposite the origin corner. The cube is rotated in three dimensions, with the origin corner staying fixed in place. After the rotation with a pivot at the origin, the edges of the cube are now aligned with a new set of orthogonal axes (\boldsymbol{u}_1,  \boldsymbol{u}_2 , \boldsymbol{u}_3), shown in red. You might understand that more clearly with an equation: U\boldsymbol{x} = (\boldsymbol{u}_1 \: \boldsymbol{u}_2 \: \boldsymbol{u}_3) \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = x\boldsymbol{u}_1 + y\boldsymbol{u}_2 + z\boldsymbol{u}_3. In short this rotation means you keep relative position of \boldsymbol{x}, I mean its coordinates (x, y, z), in the new orthonormal basis. In this article, let me call this a “cube rotation.”

The discussion above can be generalized to spaces with dimensions higher than 3. When U \in \mathbb{R}^{D \times D} is an orthonormal matrix and a vector \boldsymbol{x} \in \mathbb{R}^D, you can project \boldsymbol{x} to \boldsymbol{x}' = U^T \boldsymbol{x}or rotate it to \boldsymbol{x}'' = U \boldsymbol{x}, where \boldsymbol{x}' = (x_{1}', \dots, x_{D}')^T and \boldsymbol{x}'' = (x_{1}'', \dots, x_{D}'')^T. In other words \boldsymbol{x} = U \boldsymbol{x}', which means you can rotate back \boldsymbol{x}' to the original point \boldsymbol{x} with the rotation matrix U.

I think you at least saw that rotation and projection are basically the same, and that is only a matter of how you look at the coordinate systems. But I would say the idea of projection is more important through out this article.

Let’s consider a function f(\boldsymbol{x}; A) = \boldsymbol{x}^T A \boldsymbol{x} = (\boldsymbol{x}, A \boldsymbol{x}), where A\in \mathbb{R}^{D\times D} is a real symmetric matrix. The distribution of f(\boldsymbol{x}; A) is quadratic curves whose center point covers the origin, and it is known that you can express this distribution in a much simpler way using eigenvectors. When you project this function on eigenvectors of A, that is when you substitute U \boldsymbol{x}' for \boldsymbol{x}, you get f = (\boldsymbol{x}, A \boldsymbol{x}) =(U \boldsymbol{x}', AU \boldsymbol{x}') = (\boldsymbol{x}')^T U^TAU \boldsymbol{x}' = (\boldsymbol{x}')^T \Lambda \boldsymbol{x}' = \lambda_1 ({x'}_1)^2 + \cdots + \lambda_D ({x'}_D)^2. You can always diagonalize real symmetric matrices, so the formula implies that the shapes of quadratic curves largely depend on eigenvectors. We are going to see this in detail in the next section.

*(\boldsymbol{x}, \boldsymbol{y}) denotes an inner product of \boldsymbol{x} and \boldsymbol{y}.

*We are going to see details of the shapes of quadratic “curves” or “functions” in the next section.

To be exact, you cannot naively multiply U or U^T for rotation. Let’s take a part of data I showed in the last article as an example. In the figure below, I projected data on the basis (\boldsymbol{u}_1,  \boldsymbol{u}_2 , \boldsymbol{u}_3).

You might have noticed that you cannot do a “cube rotation” in this case. If you make the coordinate system (\boldsymbol{u}_1, \boldsymbol{u}_2, \boldsymbol{u}_3) with your left hand, like you might have done in science classes in school to learn Fleming’s rule, you would soon realize that the coordinate systems in the figure above do not match. You need to flip the direction of one axis to match them.

Mathematically, you have to consider the determinant of the rotation matrix U. You can do a “cube rotation” when det(U)=1, and in the case above det(U) was -1, and you needed to flip one axis to make the determinant 1. In the example in the figure below, you can match the basis. This also can be generalized to higher dimensions, but that is also beyond the scope of this article series. If you are really interested, you should prepare some coffee and snacks and textbooks on linear algebra, and some weekends.

When you want to make general ellipsoids in a 3d space on Matplotlib, you can take advantage of rotation matrices. You first make a simple ellipsoid symmetric about xyz axis using polar coordinates, and you can rotate the whole ellipsoid with rotation matrices. I made some simple modules for drawing ellipsoid. If you put in a rotation matrix which diagonalize the covariance matrix of data and a list of three radiuses \sqrt{\lambda_1}, \sqrt{\lambda_2}, \sqrt{\lambda_3}, you can rotate the original ellipsoid so that it fits the data well.

3 Types of quadratic curves.

*This article might look like a mathematical writing, but I would say this is more about computer science. Please tolerate some inaccuracy in terms of mathematics. I gave priority to visualizing necessary mathematical ideas in my article series. If you are not sure about details, please let me know.

In linear dimension reduction, or at least in this article series you mainly have to consider ellipsoids. However ellipsoids are just one type of quadratic curves. In the last article, I mentioned that when the center of a D dimensional ellipsoid is the origin point of a normal coordinate system, the formula of the surface of the ellipsoid is as follows: (\boldsymbol{x}, A\boldsymbol{x})=1, where A satisfies certain conditions. To be concrete, when (\boldsymbol{x}, A\boldsymbol{x})=1 is the surface of a ellipsoid, A has to be diagonalizable and positive definite.

*Real symmetric matrices are diagonalizable, and positive definite matrices have only positive eigenvalues. Covariance matrices \Sigma, whose displacement vectors I visualized in the last two articles, are known to be symmetric real matrices and positive semi-defintie. However, the surface of an ellipsoid which fit the data is \boldsymbol{x}^T \Sigma ^{-1} \boldsymbol{x} = const., not \boldsymbol{x}^T \Sigma \boldsymbol{x} = const..

*You have to keep it in mind that \boldsymbol{x} are all deviations.

*You do not have to think too much about what the “semi” of the term “positive semi-definite” means fow now.

As you could imagine, this is just one simple case of richer variety of graphs. Let’s consider a 3-dimensional space. Any quadratic curves in this space can be denoted as ax^2 + by^2 + cz^2 + dxy + eyz + fxz + px + qy + rz + s = 0, where at least one of a, b, c, d, e, f, p, q, r, s is not 0.  Let \boldsymbol{x} be (x, y, z)^T, then the quadratic curves can be simply denoted with a 3\times 3 matrix A and a 3-dimensional vector \boldsymbol{b} as follows: \boldsymbol{x}^T A\boldsymbol{x} + 2\boldsymbol{b}^T\boldsymbol{x} + s = 0, where A = \left( \begin{array}{ccc} a & \frac{d}{2} & \frac{f}{2} \\ \frac{d}{2} & b & \frac{e}{2} \\ \frac{f}{2} & \frac{e}{2} & c \end{array} \right), \boldsymbol{b} = \left( \begin{array}{c} \frac{p}{2} \\ \frac{q}{2} \\ \frac{r}{2} \end{array} \right). General quadratic curves are roughly classified into the 9 types below.

You can shift these quadratic curves so that their center points come to the origin, without rotation, and the resulting curves are as follows. The curves can be all denoted as \boldsymbol{x}^T A\boldsymbol{x}.

As you can see, A is a real symmetric matrix. As I have mentioned repeatedly, when all the elements of a D \times D symmetric matrix A are real values and its eigen values are \lambda_{i} (i=1, \dots , D), there exist orthogonal/orthonormal matrices U such that U^{-1}AU = \Lambda, where \Lambda = diag(\lambda_{1}, \dots , \lambda_{D}). Hence, you can diagonalize the A = \left( \begin{array}{ccc} a & \frac{d}{2} & \frac{f}{2} \\ \frac{d}{2} & b & \frac{e}{2} \\ \frac{f}{2} & \frac{e}{2} & c \end{array} \right) with an orthogonal matrix U. Let U be an orthogonal matrix such that U^T A U = \left( \begin{array}{ccc} \alpha  & 0 & 0 \\ 0 & \beta & 0 \\ 0 & 0 & \gamma \end{array} \right) =\left( \begin{array}{ccc} \lambda_1  & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \end{array} \right). After you apply rotation by U to the curves (a)” ~ (i)”, those curves are symmetrically placed about the xyz axes, and their center points still cross the origin. The resulting curves look like below. Or rather I should say you projected (a)’ ~ (i)’ on their eigenvectors.

In this article mainly (a)” , (g)”, (h)”, and (i)” are important. General equations for the curves is as follows

  • (a)”: \frac{x^2}{l^2} + \frac{y^2}{m^2} + \frac{z^2}{n^2} = 1
  • (g)”: z = \frac{x^2}{l^2} + \frac{y^2}{m^2}
  • (h)”: z = \frac{x^2}{l^2} - \frac{y^2}{m^2}
  • (i)”: z = \frac{x^2}{l^2}

, where l, m, n \in \mathbb{R}^+.

Even if this section has been puzzling to you, you just have to keep one point in your mind: we have been discussing general quadratic curves, but in PCA, you only need to consider a case where A is a covariance matrix, that is A=\Sigma. PCA corresponds to the case where you shift and rotate the curve (a) into (a)”. Subtracting the mean of data from each point of data corresponds to shifting quadratic curve (a) to (a)’. Calculating eigenvectors of A corresponds to calculating a rotation matrix U such that the curve (a)’ comes to (a)” after applying the rotation, or projecting curves on eigenvectors of \Sigma. Importantly we are only discussing the covariance of certain data, not the distribution of the data itself.

*Just in case you are interested in a little more mathematical sides: it is known that if you rotate all the points \boldsymbol{x} on the curve \boldsymbol{x}^T A\boldsymbol{x} + 2\boldsymbol{b}^T\boldsymbol{x} + s = 0 with the rotation matrix P, those points \boldsymbol{x} are mapped into a new quadratic curve \alpha x^2 + \beta y^2 + \gamma z^2 + \lambda x + \mu y + \nu z + \rho = 0. That means the rotation of the original quadratic curve with P (or rather rotating axes) enables getting rid of the terms xy, yz, zx. Also it is known that when \alpha ' \neq 0, with proper translations and rotations, the quadratic curve \alpha x^2 + \beta y^2 + \gamma z^2 + \lambda x + \mu y + \nu z + \rho = 0 can be mapped into one of the types of quadratic curves in the figure below, depending on coefficients of the original quadratic curve. And the discussion so far can be generalized to higher dimensional spaces, but that is beyond the scope of this article series. Please consult decent textbooks on linear algebra around you for further details.

4 Eigenvectors are gradients and sometimes variances.

In the second section I explained that you can express quadratic functions f(\boldsymbol{x}; A) = \boldsymbol{x}^T A \boldsymbol{x} in a very simple way by projecting \boldsymbol{x} on eigenvectors of A.

You can comprehend what I have explained in another way: eigenvectors, to be exact eigenvectors of real symmetric matrices A, are gradients. And in case of PCA, I mean when A=\Sigma eigenvalues are also variances. Before explaining what that means, let me explain a little of the totally common facts on mathematics. If you have variables \boldsymbol{x}\in \mathbb{R}^D, I think you can comprehend functions f(\boldysmbol{x}) in two ways. One is a normal “functions” f(\boldsymbol{x}), and the others are “curves” f(\boldsymbol{x}) = const.. “Functions” get an input \boldsymbol{x} and gives out an output f(\boldsymbol{x}), just as well as normal functions you would imagine. “Curves” are rather sets of \boldsymbol{x} \in \mathbb{R}^D such that f(\boldsymbol{x}) = const..

*Please assume that the terms “functions” and “curves” are my original words. I use them just in case I fail to use functions and curves properly.

The quadratic curves in the figure above are all “curves” in my term, which can be denoted as f(\boldsymbol{x}; A_3, \boldsymbol{b}_3)=const or f(\boldsymbol{x}; A_3)=const. However if you replace z of (g)”, (h)”, and (i)” with f, you can interpret the “curves” as “functions” which are denoted as f(\boldsymbol{x}; A_2). This might sounds too obvious to you, and my point is you can visualize how values of “functions” change only when the inputs are 2 dimensional.

When a symmetric 2\times 2 real matrices A_2 have two eigenvalues \lambda_1, \lambda_2, the distribution of quadratic curves can be roughly classified to the following three types.

  • (g): Both \lambda_1 and \lambda_2 are positive or negative.
  • (h): Either of \lambda_1 or \lambda_2 is positive and the other is negative.
  • (i): Either of \lambda_1 or \lambda_2 is 0 and the other is not.

The equations of (g)” , (h)”, and (i)” correspond to each type of f=(\boldsymbol{x}; A_2), and thier curves look like the three graphs below.

And in fact, when start from the origin and go in the direction of an eigenvector \boldsymbol{u}_i, \lambda_i is the gradient of the direction. You can see that more clearly when you restrict the distribution of f=(\boldsymbol{x}; A_2) to a unit circle. Like in the figure below, in case \lambda_1 = 7, \lambda_2 = 3, which is classified to (g), the distribution looks like the left side, and if you restrict the distribution in the unit circle, the distribution looks like a bowl like the middle and the right side. When you move in the direction of \boldsymbol{u}_1, you can climb the bowl as as high as \lambda_1, in \boldsymbol{u}_2 as high as \lambda_2.

Also in case of (h), the same facts hold. But in this case, you can also descend the curve.

*You might have seen the curve above in the context of optimization with stochastic gradient descent. The origin of the curve above is a notorious saddle point, where gradients are all 0 in any directions but not a local maximum or minimum. Points can be stuck in this point during optimization.

Especially in case of PCA, A is a covariance matrix, thus A=\Sigma. Eigenvalues of \Sigma are all equal to or greater than 0. And it is known that in this case \lambda_i is the variance of data projected on its corresponding eigenvector \boldsymbol{u}_i (i=0, \dots , D). Hence, if you project f(\boldsymbol{x}; \Sigma), quadratic curves formed by a covariance matrix \Sigma, on eigenvectors of \Sigma, you get f(\boldsymbol{x}; \Sigma) = ({x'}_1 \: \dots \: {x'}_D) (\lambda_1 {x'}_1 \: \dots \: \lambda_D {x'}_D)^t =\lambda_1 ({x'}_1)^2 + \cdots + \lambda_D ({x'}_D)^2.  This shows that you can re-weight ({x'}_1 \: \dots \: {x'}_D), the coordinates of data projected projected on eigenvectors of A, with \lambda_1, \dots, \lambda_D, which are variances ({x'}_1 \: \dots \: {x'}_D). As I mentioned in an example of data of exam scores in the last article, the bigger a variance \lambda_i is, the more the feature described by \boldsymbol{u}_i vary from sample to sample. In other words, you can ignore eigenvectors corresponding to small eigenvalues.

That is a great hint why principal components corresponding to large eigenvectors contain much information of the data distribution. And you can also interpret PCA as a “climbing” a bowl of f(\boldsymbol{x}; A_D), as I have visualized in the case of (g) type curve in the figure above.

*But as I have repeatedly mentioned, ellipsoid which fit data well isf(\boldsymbol{x}; \Sigma ^{-1}) =(\boldsymbol{x}')^T diag(\frac{1}{\lambda_1}, \dots, \frac{1}{\lambda_D})\boldsymbol{x}' = \frac{({x'}_{1})^2}{\lambda_1} + \cdots + \frac{({x'}_{D})^2}{\lambda_D} = const..

*You have to be careful that even if you slice a type (h) curve f(\boldsymbol{x}; A_D) with a place z=const. the resulting cross section does not fit the original data well because the equation of the cross section is \lambda_1 ({x'}_1)^2 + \cdots + \lambda_D ({x'}_D)^2 = const. The figure below is an example of slicing the same f(\boldsymbol{x}; A_2) as the one above with z=1, and the resulting cross section.

As we have seen, \lambda_i, the eigenvalues of the covariance matrix of data are variances or data when projected on it eigenvectors. At the same time, when you fit an ellipsoid on the data, \sqrt{\lambda_i} is the radius of the ellipsoid corresponding to \boldsymbol{u}_i. Thus ignoring data projected on eigenvectors corresponding to small eigenvalues is equivalent to cutting of the axes of the ellipsoid with small radiusses.

I have explained PCA in three different ways over three articles.

  • The second article: I focused on what kind of linear transformations convariance matrices \Sigma enable, by visualizing displacement vectors. And those vectors look like swirling and extending into directions of eigenvectors of \Sigma.
  • The third article: We directly found directions where certain data distribution “swell” the most, to find that data swell the most in directions of eigenvectors.
  • In this article, we have seen PCA corresponds to only one case of quadratic functions, where the matrix A is a covariance matrix. When you go in the directions of eigenvectors corresponding to big eigenvalues, the quadratic function increases the most. Also that means data samples have bigger variances when projected on the eigenvectors. Thus you can cut off eigenvectors corresponding to small eigenvectors because they retain little information about data, and that is equivalent to fitting an ellipsoid on data and cutting off axes with small radiuses.

*Let A be a covariance matrix, and you can diagonalize it with an orthogonal matrix U as follow: U^{T}AU = \Lambda, where \Lambda = diag(\lambda_1, \dots, \lambda_D). Thus A = U \Lambda U^{T}. U is a rotation, and multiplying a \boldsymbol{x} with \Lambda means you multiply each eigenvalue to each element of \boldsymbol{x}. At the end U^T enables the reverse rotation.

If you get data like the left side of the figure below, most explanation on PCA would just fit an oval on this data distribution. However after reading this articles series so far, you would have learned to see PCA from different viewpoints like at the right side of the figure below.

 

5 Ellipsoids in Gaussian distributions.

I have explained that if the covariance of a data distribution is \boldsymbol{\Sigma}, the ellipsoid which fits the distribution the best is \bigl((\boldsymbol{x} - \boldsymbol{\mu}), \boldsymbol{\Sigma}^{-1}(\boldsymbol{x} - \boldsymbol{\mu})\bigr) = 1. You might have seen the part \bigl((\boldsymbol{x} - \boldsymbol{\mu}), \boldsymbol{\Sigma}^{-1}(\boldsymbol{x} - \boldsymbol{\mu})\bigr) = (\boldsymbol{x} - \boldsymbol{\mu}) \boldsymbol{\Sigma}^{-1}(\boldsymbol{x} - \boldsymbol{\mu}) somewhere else. It is the exponent of general Gaussian distributions: \mathcal{N}(\boldsymbol{x} | \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \frac{1}{(2\pi)^{D/2}} \frac{1}{|\boldsymbol{\Sigma}|} exp\{ -\frac{1}{2}(\boldsymbol{x} - \boldsymbol{\mu}) \boldsymbol{\Sigma}^{-1}(\boldsymbol{x} - \boldsymbol{\mu}) \}.  It is known that the eigenvalues of \Sigma ^{-1} are \frac{1}{\lambda_1}, \dots, \frac{1}{\lambda_D}, and eigenvectors corresponding to each eigenvalue are also \boldsymbol{u}_1, \dots, \boldsymbol{u}_D respectively. Hence just as well as what we have seen, if you project (\boldsymbol{x} - \boldsymbol{\mu}) on each eigenvector of \Sigma ^{-1}, we can convert the exponent of the Gaussian distribution.

Let -\frac{1}{2}(\boldsymbol{x} - \boldsymbol{\mu}) \boldsymbol{\Sigma}^{-1}(\boldsymbol{x} - \boldsymbol{\mu}) be \boldsymbol{y} and U ^{-1} \boldsymbol{y}= U^{T} \boldsymbol{y} be \boldsymbol{y}', where U=(\boldsymbol{u}_1 \: \dots \: \boldsymbol{u}_D). Just as we have seen, (\boldsymbol{x} - \boldsymbol{\mu}) \boldsymbol{\Sigma}^{-1}(\boldsymbol{x} - \boldsymbol{\mu}) =\boldsymbol{y}^T\Sigma^{-1} \boldsymbol{y} =(U\boldsymbol{y}')^T \Sigma^{-1} U\boldsymbol{y}' =((\boldsymbol{y}')^T U^T \Sigma^{-1} U\boldsymbol{y}' = (\boldsymbol{y}')^T diag(\frac{1}{\lambda_1}, \dots, \frac{1}{\lambda_D}) \boldsymbol{y}' = \frac{({y'}_{1})^2}{\lambda_1} + \cdots + \frac{({y'}_{D})^2}{\lambda_D}. Hence \mathcal{N}(\boldsymbol{x} | \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \frac{1}{(2\pi)^{D/2}} \frac{1}{|\boldsymbol{\Sigma}|} exp\{ -\frac{1}{2}(\boldsymbol{y}) \boldsymbol{\Sigma}^{-1}(\boldsymbol{y}) \} =  \frac{1}{(2\pi)^{D/2}} \frac{1}{|\boldsymbol{\Sigma}|} exp\{ -\frac{1}{2}(\frac{({y'}_{1})^2}{\lambda_1} + \cdots + \frac{({y'}_{D})^2}{\lambda_D} ) \} =\frac{1}{(2\pi)^{1/2}} \frac{1}{|\boldsymbol{\Sigma}|} exp\biggl( -\frac{1}{2} \frac{({y'}_{1})^2}{\lambda_1} \biggl) \cdots \frac{1}{(2\pi)^{1/2}} \frac{1}{|\boldsymbol{\Sigma}|} exp\biggl( -\frac{1}{2}\frac{({y'}_{D})^2}{\lambda_D} \biggl).

*To be mathematically exact about changing variants of normal distributions, you have to consider for example Jacobian matrices.

This results above demonstrate that, by projecting data on the eigenvectors of its covariance matrix, you can factorize the original multi-dimensional Gaussian distribution into a product of Gaussian distributions which are irrelevant to each other. However, at the same time, that is the potential limit of approximating data with PCA. This idea is going to be more important when you think about more probabilistic ways to handle PCA, which is more robust to lack of data.

I have explained PCA over 3 articles from various viewpoints. If you have been patient enough to read my article series, I think you have gained some deeper insight into not only PCA, but also linear algebra, and that should be helpful when you learn or teach data science. I hope my codes also help you. In fact these are not the only topics about PCA. There are a lot of important PCA-like algorithms.

In fact our expedition of ellipsoids, or PCA still continues, just as Star Wars series still continues. Especially if I have to explain an algorithm named probabilistic PCA, I need to explain the “Bayesian world” of machine learning. Most machine learning algorithms covered by major introductory textbooks tend to be too deterministic and dependent on the size of data. Many of those algorithms have another “parallel world,” where you can handle inaccuracy in better ways. I hope I can also write about them, and I might prepare another trilogy for such PCA. But I will not disappoint you, like “The Phantom Menace.”

Appendix: making a model of a bunch of grape with ellipsoid berries.

If you can control quadratic curves, reshaping and rotating them, you can make a model of a grape of olive bunch on Matplotlib. I made a program of making a model of a bunch of berries on Matplotlib using the module to draw ellipsoids which I introduced earlier. You can check the codes in this page.

*I have no idea how many people on this earth are in need of making such models.

I made some modules so that you can see the grape bunch from several angles. This might look very simple to you, but the locations of berries are organized carefully so that it looks like they are placed around a stem and that the berries are not too close to each other.

 

The programming code I created for this article is completly available here.

[Refereces]

[1]C. M. Bishop, “Pattern Recognition and Machine Learning,” (2006), Springer, pp. 78-83, 559-577

[2]「理工系新課程 線形代数 基礎から応用まで」, 培風館、(2017)

[3]「これなら分かる 最適化数学 基礎原理から計算手法まで」, 金谷健一著、共立出版, (2019), pp. 17-49

[4]「これなら分かる 応用数学教室 最小二乗法からウェーブレットまで」, 金谷健一著、共立出版, (2019), pp.165-208

[5] 「サボテンパイソン 」
https://sabopy.com/

 

How to make a toy English-German translator with multi-head attention heat maps: the overall architecture of Transformer

If you have been patient enough to read the former articles of this article series Instructions on Transformer for people outside NLP field, but with examples of NLP, you should have already learned a great deal of Transformer model, and I hope you gained a solid foundation of learning theoretical sides on this algorithm.

This article is going to focus more on practical implementation of a transformer model. We use codes in the Tensorflow official tutorial. They are maintained well by Google, and I think it is the best practice to use widely known codes.

The figure below shows what I have explained in the articles so far. Depending on your level of understanding, you can go back to my former articles. If you are familiar with NLP with deep learning, you can start with the third article.

1 The datasets

I think this article series appears to be on NLP, and I do believe that learning Transformer through NLP examples is very effective. But I cannot delve into effective techniques of processing corpus in each language. Thus we are going to use a library named BPEmb. This library enables you to encode any sentences in various languages into lists of integers. And conversely you can decode lists of integers to the language. Thanks to this library, we do not have to do simplification of alphabets, such as getting rid of Umlaut.

*Actually, I am studying in computer vision field, so my codes would look elementary to those in NLP fields.

The official Tensorflow tutorial makes a Portuguese-English translator, but in article we are going to make an English-German translator. Basically, only the codes below are my original. As I said, this is not an article on NLP, so all you have to know is that at every iteration you get a batch of (64, 41) sized tensor as the source sentences, and a batch of (64, 42) tensor as corresponding target sentences. 41, 42 are respectively the maximum lengths of the input or target sentences, and when input sentences are shorter than them, the rest positions are zero padded, as you can see in the codes below.

*If you just replace datasets and modules for encoding, you can make translators of other pairs of languages.

We are going to train a seq2seq-like Transformer model of converting those list of integers, thus a mapping from a vector to another vector. But each word, or integer is encoded as an embedding vector, so virtually the Transformer model is going to learn a mapping from sequence data to another sequence data. Let’s formulate this into a bit more mathematics-like way: when we get a pair of sequence data \boldsymbol{X} = (\boldsymbol{x}^{(1)}, \dots, \boldsymbol{x}^{(\tau _x)}) and \boldsymbol{Y} = (\boldsymbol{y}^{(1)}, \dots, \boldsymbol{y}^{(\tau _y)}), where \boldsymbol{x}^{(t)} \in \mathbb{R}^{|\mathcal{V}_{\mathcal{X}}|}, \boldsymbol{x}^{(t)} \in \mathbb{R}^{|\mathcal{V}_{\mathcal{Y}}|}, respectively from English and German corpus, then we learn a mapping f: \boldsymbol{X} \to \boldsymbol{Y}.

*In this implementation the vocabulary sizes are both 10002. Thus |\mathcal{V}_{\mathcal{X}}|=|\mathcal{V}_{\mathcal{Y}}|=10002

2 The whole architecture

This article series has covered most of components of Transformer model, but you might not understand how seq2seq-like models can be constructed with them. It is very effective to understand how transformer is constructed by actually reading or writing codes, and in this article we are finally going to construct the whole architecture of a Transforme translator, following the Tensorflow official tutorial. At the end of this article, you would be able to make a toy English-German translator.

The implementation is mainly composed of 4 classes, EncoderLayer(), Encoder(), DecoderLayer(), and Decoder() class. The inclusion relations of the classes are displayed in the figure below.

To be more exact in a seq2seq-like model with Transformer, the encoder and the decoder are connected like in the figure below. The encoder part keeps converting input sentences in the original language through N layers. The decoder part also keeps converting the inputs in the target languages, also through N layers, but it receives the output of the final layer of the Encoder at every layer.

You can see how the Encoder() class and the Decoder() class are combined in Transformer in the codes below. If you have used Tensorflow or Pytorch to some extent, the codes below should not be that hard to read.

3 The encoder

*From now on “sentences” do not mean only the input tokens in natural language, but also the reweighted and concatenated “values,” which I repeatedly explained in explained in the former articles. By the end of this section, you will see that Transformer repeatedly converts sentences layer by layer, remaining the shape of the original sentence.

I have explained multi-head attention mechanism in the third article, precisely, and I explained positional encoding and masked multi-head attention in the last article. Thus if you have read them and have ever written some codes in Tensorflow or Pytorch, I think the codes of Transformer in the official Tensorflow tutorial is not so hard to read. What is more, you do not use CNNs or RNNs in this implementation. Basically all you need is linear transformations. First of all let’s see how the EncoderLayer() and the Encoder() classes are implemented in the codes below.

You might be confused what “Feed Forward” means in  this article or the original paper on Transformer. The original paper says this layer is calculated as FFN(x) = max(0, xW_1 + b_1)W_2 +b_2. In short you stack two fully connected layers and activate it with a ReLU function. Let’s see how point_wise_feed_forward_network() function works in the implementation with some simple codes. As you can see from the number of parameters in each layer of the position wise feed forward neural network, the network does not depend on the length of the sentences.

From the number of parameters of the position-wise feed forward neural networks, you can see that you share the same parameters over all the positions of the sentences. That means in the figure above, you use the same densely connected layers at all the positions, in single layer. But you also have to keep it in mind that parameters for position-wise feed-forward networks change from layer to layer. That is also true of “Layer” parts in Transformer model, including the output part of the decoder: there are no learnable parameters which cover over different positions of tokens. These facts lead to one very important feature of Transformer: the number of parameters does not depend on the length of input or target sentences. You can offset the influences of the length of sentences with multi-head attention mechanisms. Also in the decoder part, you can keep the shape of sentences, or reweighted values, layer by layer, which is expected to enhance calculation efficiency of Transformer models.

4, The decoder

The structures of DecoderLayer() and the Decoder() classes are quite similar to those of EncoderLayer() and the Encoder() classes, so if you understand the last section, you would not find it hard to understand the codes below. What you have to care additionally in this section is inter-language multi-head attention mechanism. In the third article I was repeatedly explaining multi-head self attention mechanism, taking the input sentence “Anthony Hopkins admired Michael Bay as a great director.” as an example. However, as I explained in the second article, usually in attention mechanism, you compare sentences with the same meaning in two languages. Thus the decoder part of Transformer model has not only self-attention multi-head attention mechanism of the target sentence, but also an inter-language multi-head attention mechanism. That means, In case of translating from English to German, you compare the sentence “Anthony Hopkins hat Michael Bay als einen großartigen Regisseur bewundert.” with the sentence itself in masked multi-head attention mechanism (, just as I repeatedly explained in the third article). On the other hand, you compare “Anthony Hopkins hat Michael Bay als einen großartigen Regisseur bewundert.” with “Anthony Hopkins admired Michael Bay as a great director.” in the inter-language multi-head attention mechanism (, just as you can see in the figure above).

*The “inter-language multi-head attention mechanism” is my original way to call it.

I briefly mentioned how you calculate the inter-language multi-head attention mechanism in the end of the third article, with some simple codes, but let’s see that again, with more straightforward figures. If you understand my explanation on multi-head attention mechanism in the third article, the inter-language multi-head attention mechanism is nothing difficult to understand. In the multi-head attention mechanism in encoder layers, “queries”, “keys”, and “values” come from the same sentence in English, but in case of inter-language one, only “keys” and “values” come from the original sentence, and “queries” come from the target sentence. You compare “queries” in German with the “keys” in the original sentence in English, and you re-weight the sentence in English. You use the re-weighted English sentence in the decoder part, and you do not need look-ahead mask in this inter-language multi-head attention mechanism.

Just as well as multi-head self-attention, you can calculate inter-language multi-head attention mechanism as follows: softmax(\frac{\boldsymbol{Q} \boldsymbol{K} ^T}{\sqrt{d}_k}). In the example above, the resulting multi-head attention map is a 10 \times 9 matrix like in the figure below.

Once you keep the points above in you mind, the implementation of the decoder part should not be that hard.

5 Masking tokens in practice

I explained masked-multi-head attention mechanism in the last article, and the ideas itself is not so difficult. However in practice this is implemented in a little tricky way. You might have realized that the size of input matrices is fixed so that it fits the longest sentence. That means, when the maximum length of the input sentences is 41, even if the sentences in a batch have less than 41 tokens, you sample (64, 41) sized tensor as a batch every time (The 64 is a batch size). Let “Anthony Hopkins admired Michael Bay as a great director.”, which has 9 tokens in total, be an input. We have been considering calculating (9, 9) sized attention maps or (10, 9) sized attention maps, but in practice you use (41, 41) or (42, 41) sized ones. When it comes to calculating self attentions in the encoder part, you zero pad self attention maps with encoder padding masks, like in the figure below. The black dots denote the zero valued elements.

As you can see in the codes below, encode padding masks are quite simple. You just multiply the padding masks with -1e9 and add them to attention maps and apply a softmax function. Thereby you can zero-pad the columns in the positions/columns where you added -1e9 to.

I explained look ahead mask in the last article, and in practice you combine normal padding masks and look ahead masks like in the figure below. You can see that you can compare each token with only its previous tokens. For example you can compare “als” only with “Anthony”, “Hopkins”, “hat”, “Michael”, “Bay”, “als”, not with “einen”, “großartigen”, “Regisseur” or “bewundert.”

Decoder padding masks are almost the same as encoder one. You have to keep it in mind that you zero pad positions which surpassed the length of the source input sentence.

6 Decoding process

In the last section we have seen that we can zero-pad columns, but still the rows are redundant. However I guess that is not a big problem because you decode the final output in the direction of the rows of attention maps. Once you decode <end> token, you stop decoding. The redundant rows would not affect the decoding anymore.

This decoding process is similar to that of seq2seq models with RNNs, and that is why you need to hide future tokens in the self-multi-head attention mechanism in the decoder. You share the same densely connected layers followed by a softmax function, at all the time steps of decoding. Transformer has to learn how to decode only based on the words which have appeared so far.

According to the original paper, “We also modify the self-attention sub-layer in the decoder stack to prevent positions from attending to subsequent positions. This masking, combined with fact that the output embeddings are offset by one position, ensures that the predictions for position i can depend only on the known outputs at positions less than i.” After these explanations, I think you understand the part more clearly.

The codes blow is for the decoding part. You can see that you first start decoding an output sentence with a sentence composed of only <start>, and you decide which word to decoded, step by step.

*It easy to imagine that this decoding procedure is not the best. In reality you have to consider some possibilities of decoding, and you can do that with beam search decoding.

After training this English-German translator for 30 epochs you can translate relatively simple English sentences into German. I displayed some results below, with heat maps of multi-head attention. Each colored attention maps corresponds to each head of multi-head attention. The examples below are all from the fourth (last) layer, but you can visualize maps in any layers. When it comes to look ahead attention, naturally only the lower triangular part of the maps is activated.

This article series has not covered some important topics machine translation, for example how to calculate translation errors. Actually there are many other fascinating topics related to machine translation. For example beam search decoding, which consider some decoding possibilities, or other topics like how to handle proper nouns such as “Anthony” or “Hopkins.” But this article series is not on NLP. I hope you could effectively learn the architecture of Transformer model with examples of languages so far. And also I have not explained some details of training the network, but I will not cover that because I think that depends on tasks. The next article is going to be the last one of this series, and I hope you can see how Transformer is applied in computer vision fields, in a more “linguistic” manner.

But anyway we have finally made it. In this article series we have seen that one of the earliest computers was invented to break Enigma. And today we can quickly make a more or less accurate translator on our desk. With Transformer models, you can even translate deadly funny jokes into German.

*You can train a translator with this code.

*After training a translator, you can translate English sentences into German with this code.

[References]

[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin, “Attention Is All You Need” (2017)

[2] “Transformer model for language understanding,” Tensorflow Core
https://www.tensorflow.org/overview

[3] Jay Alammar, “The Illustrated Transformer,”
http://jalammar.github.io/illustrated-transformer/

[4] “Stanford CS224N: NLP with Deep Learning | Winter 2019 | Lecture 14 – Transformers and Self-Attention,” stanfordonline, (2019)
https://www.youtube.com/watch?v=5vcj8kSwBCY

[5]Tsuboi Yuuta, Unno Yuuya, Suzuki Jun, “Machine Learning Professional Series: Natural Language Processing with Deep Learning,” (2017), pp. 91-94
坪井祐太、海野裕也、鈴木潤 著, 「機械学習プロフェッショナルシリーズ 深層学習による自然言語処理」, (2017), pp. 191-193

* I make study materials on machine learning, sponsored by DATANOMIQ. I do my best to make my content as straightforward but as precise as possible. I include all of my reference sources. If you notice any mistakes in my materials, including grammatical errors, please let me know (email: yasuto.tamura@datanomiq.de). And if you have any advice for making my materials more understandable to learners, I would appreciate hearing it.