Contracted Events for Micro Frontend Communication​

A non-formal approach to non-breaking events for displaying information in distributed Frontend Fragments​

Schema Versioning and Consumer-driven contracts play critical roles in the world of distributed systems, where data structures often evolve across releases. These concepts can be applied to Micro Frontends, where messages need to be exchanged across system boundaries: Release-agnostic systems, which can dynamically enter and exit the system of concern, must be able to properly respond to event messages: Updated message structures must not introduce breaking changes.

In a frontend, provide contracts for data structures consumed by conceptually related modules and process the data according to the individual requirements of the consuming context.

Motivation​

Using a Micro Frontend architecture does not require to plan a specific tech stack ahead. Quite the contrary, developers and architects can agree on different approaches that allow for embedding complete parts of applications, or components provided by these applications, into a web frontend.

What matters is that each of the Micro Frontends strives for low coupling and strong cohesion, just as any building block of a modularized software system does. Low coupling doesn’t necessarily mean that a µFrontend is lashed and stowed within its domain, as it often needs to take part in sending and consuming messages within a frontend application: The big picture shows itself when conceptually related modules process broadcasted messages and offer the data in an informational context, updating visual elements with it. Here, the emphasis is clearly on “visual”, since triggering business or domain logic would mean a higher degree of coupling between the sender and the receiver. We want to avoid this.

The attempt to process data from events often results in inconsistent visual representation throughout the application, or even worse, runtime errors when the consuming API does not understand the format or the structure of the data the API is expected to process, sometimes due to unintentionally and accidentally changes made to the sender’s API.

Providing contracts for consumers with the help of shared source, versioned events and a must ignore policy lowers the risk of breaking functionality during runtime when messages of arbitrary source are processed by autonomously developed and independently deployed frontends, while keeping integrity and consistency high and coupling and lockstep release cycles low.

...continue reading

Die Standardnummerierung ist festgelegt als:

• $\mathbb{N}_0$: Die Menge aller Turingmaschinen (ein $i \in \mathbb{N}_0$ repräsentiert die Gödelnummer einer Turingmaschine), wobei $\mathcal{T}$ die Menge aller normierten Turingmaschinen ist. Die Abbildung $h: \mathbb{N}_0 \rightarrow \mathcal{T}$ ist definiert durch $h(i) = \begin{cases} T, & \text{falls } p(\tau(T)) = i\\ T_{\omega}, & \text{sonst} \end{cases}$ bildet also auf eine natürliche Zahl eine Turingmaschine ab.
• $\mathcal{P}$: Die Menge aller berechenbaren Funktionen.
• $\varphi: \mathbb{N}_0 \rightarrow \mathcal{P}$ ist eine Abzählung aller berechenbaren Funktionen. $\varphi$ ist festgelegt durch $\varphi(i) = f \Leftrightarrow f_{h(i)} = f$ Die berechenbare Funktion $\varphi(i)$ wird also durch die $i$-te Turingmaschine berechnet.

Die Standardnummerierung ist im Folgenden die Grundlage für die Formulierung von Entscheidbarkeitsproblemen bei Mengen.

Das spezielle Halteproblem​

Zunächst wird das spezielle Halteproblem (auch Selbstanwendbarkeitsproblem) betrachtet.
Vossen und Witt definieren es über folgende Menge:

$K$ enthält alle Nummern von Turingmaschinen, die, angewendet auf sich selbst, anhalten:

• $i$ ist die Codierung einer Turingmaschine.
• $\varphi_i$ ist die berechenbare Funktion, die von der Turingmaschine $p(\tau(T)) = i$ berechnet wird.
• $\text{Def}(\varphi_i)$ ist der Definitionsbereich der Funktion $\varphi_i$, also alle erlaubten Eingaben.
• $i \in \text{Def}(\varphi_i)$ bedeutet: Die Codierung $i$ der Turingmaschine $p(\tau(T)) = i$, die $\varphi_i$ berechnet, ist eine erlaubte Eingabe.

Vossen und Witt definieren $K$ als die "Menge aller Turingmaschinen, die, [...] anhalten."
Das bedeutet, dass von einer entscheidbaren Menge ausgegangen wird:
Es wird angenommen, dass sowohl $K$ als auch $\overline{K}$ semi-entscheidbar sind und die charakteristische Funktion $\chi_K$ von $K$ berechenbar ist.

Mit Satz 10.7 formulieren Vossen und Witt den Kern des Selbstanwendbarkeitsproblems, nämlich, dass $K$ zwar semi-entscheidbar, aber nicht entscheidbar ist:

Damit wird behauptet:

• $K$ ist semi-entscheidbar, da rekursiv-aufzählbar.
  Wenn $K$ semi-entscheidbar ist, ist auch die semi-charakteristische Funktion von $K$, $\chi'_K$, berechenbar.
  Wenn $K$ semi-entscheidbar und damit rekursiv aufzählbar ist, dann gilt äquivalent dazu: $K$ ist der Definitionsbereich einer berechenbaren Funktion $g: \mathbb{N}_{0} \rightarrow \mathbb{N}_0$ (s. Folgerung 10.2 [📖VW16, p. 356]). Es reicht also aus, eine solche Funktion anzugeben, um die Semi-Entscheidbarkeit und damit auch die rekursive Aufzählbarkeit nachzuweisen.
• Wenn $K$ entscheidbar ist, dann ist auch die charakteristische Funktion $\chi_K$ berechenbar: $\chi_K$ gibt $1$ aus, wenn die Turingmaschine $T$ angewendet auf $i = p(\tau(T))$ anhält (also wenn $\varphi_i(i)$ berechnet wird); und ansonsten ist $\chi_K(i) = 0$, wenn $T$ nicht anhält².

Beweisführung​

Der Beweis wird wie folgt geführt:

a) Vossen und Witt definieren die Funktion $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ durch

Bei $u_{\varphi}$ handelt es sich um die universelle Funktion von $(\mathbb{N}_0, \mathcal{P}, \varphi)$:

$u_{\varphi}(i, j)$ berechnet die $i$-te berechenbare Funktion für die Eingabe $j$.

Mit $f$ als berechenbare Funktion kann gezeigt werden:

womit $K = \text{Def}(f)$ ist und damit $K$ rekursiv-aufzählbar und semi-entscheidbar ist.

b) Angenommen, $K$ ist entscheidbar. Dann ist $\chi_K$ berechenbar.
Vossen und Witt definieren eine berechenbare (Hilfs-)Funktion

$g: \mathbb{N}_0 \rightarrow \mathbb{N}_0$

durch

$g$ ist total berechenbar: Wenn $\chi_K(x) = 1$, dann ist $x \in \text{Def}(\varphi_x)$, und damit ist $u_\varphi(x, x) + 1 = \varphi_x(x) + 1$.

Da $g$ total berechenbar ist ($g \in \mathcal{R} \subset \mathcal{P}$), muss es ein $p \in \mathbb{N}_0$ geben mit $g = \varphi_p$. Es folgt

Für $g(p)$ werden nun zwei Fälle untersucht:

• Fall 1: $g(p) = 0$

  $$\begin{align} g(p) = 0 &\Leftrightarrow \chi_K(p) = 0 \quad \text{(Entscheidbarkeit $K$)}\\ & \Leftrightarrow p \notin K \\ & \Leftrightarrow p \notin \text{Def}(\varphi_p) \quad \text{($g = \varphi_p$)}\\ & \Leftrightarrow p \notin \text{Def}(g) \\ & \Leftrightarrow g(p) = \bot \quad \text{(Widerspruch zu $g$ total berechenbar)} \end{align}$$

  womit insgesamt die widersprüchliche Aussage folgt:

  $$g(p) = 0 \Leftrightarrow g(p) = \bot$$

• Fall 2: $g(p) = u_{\varphi}(p,p) + 1$

  $$\begin{align} g(p) &= u_{\varphi}(p, p) + 1 \quad \text{(Definition $g$)}\\ &= \varphi_p(p) + 1 \quad \text{($u_{\varphi}(p, p) = \varphi_p(p)$)}\\ &= g(p) + 1 \quad \text{($\varphi_p = g$)} \end{align}$$

  womit insgesamt die widersprüchliche Aussage folgt:

  $$g(p) = g(p) + 1$$

Insgesamt wird durch den Beweis gezeigt: Die Anwendung von $g$ auf $p$ - also von $g$ auf sich selbst (wegen $g = \varphi_p = f_{h(p)}, \varphi_p(p) = u_{\varphi}(p, p)$) - führt in jedem Fall zu einem Widerspruch.
Damit ist gezeigt, dass $\chi_K$ nicht berechenbar und folglich $K$ nicht entscheidbar ist.

Für das Modul prog¹ im Wintersemester 2023/2024 des Fernstudiengangs Informatik (M.C.Sc.) der Hochschule Trier habe ich hier Lösungshinweise zu ausgewählten Tests zusammengefasst. Diese stehen als PDF zum Download zur Verfügung.

Repetitorium und Lösungshinweise Musterklausur (22.03.2024)​

• Das Repetitorium zu dem Modul PROG im WS 23/24 kann hier heruntergeladen werden
• Lösungsvorschläge, Anmerkungen und Ergänzungen zu der Musterklausur können hier heruntergeladen werden.

Lösungshinweise Test 5 - Such-undSortieralgorithmen (23.01.2024)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Lösungshinweise Test 4 - Dynamische Datenstrukturen und spezifische Algorithmen (09.01.2024)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Lösungshinweise Test 3 - Objektorientierung (05.12.2023)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Die Lösungshinweise beinhalten nicht die Testaufgaben, bei denen eine bestimmte Programmausgabe nachvollzogen werden musste.

Um Konzepte des Lehrmaterials deutlicher von weiterführenden, für den Kurs weniger relevante Themen abzugrenzen, sind diese nun unter Exkurs in den jeweiligen Abschnitten zusammengefasst.

Lösungshinweise Test 1 - Klassenbasierte Programmierung (31.10.2023)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Donald Shell stellt 1959 in [📖She59] einen Sortieralgorithmus vor, der später nach ihm benannt wird: Shellsort.
Die in dem Algorithmus verwendete Sortiermethode ist auch bekannt als Sortieren mit abnehmenden Inkrementen [📖OW17b, p. 88], das Verfahren ist eine Variation von Insertion Sort:

[Shellsort] uses insertion sort on periodic subarrays of the input to produce a faster sorting algorithm. [📖CL22, p. 48]

In der vorliegenden Implementierung (siehe Listing 1) werden $t = log_2(n)$ Inkremente¹ $h_t$² der Form $\lfloor {\frac{n}{2^i}} \rfloor$ verwendet, um $lg(n)$ $h$-sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in $h_1$ die Schlüssel mit Abstand=$1$.

Die Effizienz des Sortierverfahrens ist stark abhängig von $h$: So zeigt Knuth, dass $O(n^{\frac{3}{2}})$ gilt, wenn für $h$ gilt: $h_s = 2^{s+1} - 1$ mit $0 \leq s < t = \lfloor{lg(n)} \rfloor$ (vgl. [📖Knu97c, p. 91]³. In unserem Fall können wir von $O(n^2)$ ausgehen.

Anzahl der Aufrufe für Feldvergleiche​

Gesucht ist die Anzahl der zwischen zwei Feldelementen gemachte Vergleiche für große randomisierte Felder. Wir vermuten hierfür einen Wert zwischen $O(n\ lg\ n)$ und $O(n^2)$,

Um die Aufrufe der Feldvergleiche zu zählen, kann wie in Listing 1 eine Zählvariable $c3$ eingesetzt wird, die jeden Aufruf über ein increment protokolliert.

while (distanz > 0) {
    c1++;
    for (i = distanz; i < feld.length; i++) {
        j = i - distanz;
        c2++;
        while (j >= 0) {
            c3++;
            if (feld[j] > feld[j + distanz]) {
                c4++;
                swap(feld, j, j+distanz);
                j = j - distanz;
            } else {
                j =-1;
            }
        }
    }
    distanz = distanz / 2;
}

Zur Bestimmung von $c3$ können randomisierte Felder erzeugt werden, wie es der Test-Code in Listing 2 demonstriert. Dann wird überprüft, in welchen Bereichen sich $c3$ bewegt. Da jeder auf Vergleichsoperationen basierende Sortieralgorithmus zu der Laufzeitklasse $\Omega(n\ log\ n)$ gehört, kann im Mittel $c3 \geq n\ log\ n$ angenommen werden:

Jedes allgemeine Sortierverfahren benötigt zum Sortieren von N verschiedenen Schlüsseln sowohl im schlechtesten Fall als auch im Mittel wenigstens $\Omega(N\ log\ N)$ Schlüsselvergleiche.

[📖OW17b, p. 154]

Allerdings wird $n^{1.3}$ ab $n=982$ schneller wachsen als $n\ log\ n$ (siehe Abbildung 1), was in der Auswertung berücksichtigt werden muss. Sonst könnte man fälschlicherweise folgern, das in dem geg. Fall die Laufzeit im Durchschnitt $n\ log\ n$ beträgt.

int epochs = 2000;
while(epochs-- >= 0) {
    int[] tests = new int[]{10, 100, 1000, 100_000, 1_000_000};
    java.util.Random r = new java.util.Random();
    for (int i = 0; i < tests.length; i++) {
        int l = tests[i];
        int[] arr = new int[l];

        for (int j = l; j > 0; j--) {
            arr[l - j] = r.nextInt(l + 1);
        }

        ShellSort.sort(Arrays.copyOfRange(arr, 0, arr.length));
    }
}

^{Figure 1 Ab n=982 wächst n(4/3) schneller al n log n.}

Wegen $\Omega(n\ log\ n)$ interessieren wir uns für die Intervalle:

• $n\ log\ n \leq c3 \leq n^{1.3}$

• $n\ log\ n \leq n^{1.3} \leq c3 \leq n^2$

Die Ausführung des Tests zeigt, dass die Aufrufanzahl von $c3$ bei großen $n$ unterhalb $n^{1.3}$ oder zwischen $n^{1.3}$ und $n^2$ liegt:

It appears that the time required to sort $n$ elements is proportional to $n^{1.226}$.⁴ [📖She59, p. 31]

Laufzeitanalyse​

Für die nachfolgenden Betrachtungen sei eine Eingabegröße $n = 2^p$ gegeben. Die Inkremente $h$ entsprechen der über die Implementierung vorgegebenen Folge $h$ mit

Für die Analyse ist die Shellsort-Implementierung in Listing 3 gegeben.

public static int[] sort(int[] arr) {

    int n = arr.length;
    int delta = n/2;
    int min;
    int j;

    while (delta > 0) { // c1

        for (int i = delta; i < arr.length; i++) {

            // c2

            min = arr[i];
            j = i;

            while (j - delta >= 0 && min < arr[j - delta]) {

                // c3;

                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = min;
        }

        delta = delta / 2;

    }
    return arr;
}

Im Folgenden betrachten wir die Anzahl für die im Code durch Kommentare markierten Stellen $c1$ in Zeile 8, $c2$ in Zeile 12 und $c3$ in Zeile 19.

Für eine erste worst-case-Analyse ist ein Feld der Länge $16$ gegeben, in absteigender Reihenfolge sortiert (s. Abbildung 2):

^{Figure 2 Die für die Laufzeitabschätzung verwendete Eingabefolge 16..1.}

Ganz offensichtlich gilt für c3, dass es $lg(n)$-mal aufgerufen wird⁵. c2 befindet sich im Block der durch die in Zeile 11 definierten Zählschleife.

Der Startwert für i ist in jedem Durchgang des Blocks $c1$ der aktuelle Wert von delta ⁶, und läuft jeweils bis $n - 1$.

In einem kompletten Durchlauf der Schleife entspricht die Anzahl der Aufrufe von $c2$ also

Für die Gesamtzahl der Aufrufe von $c2$ ergibt sich somit unter Berücksichtigung von $c1$

entspricht, und für unser Beispiel

ist.

In der while-Schleife in Zeile 17 findet die eigentliche Arbeit des Algorithmus statt: Es wird überprüft, ob $delta$-entfernte Elemente in aufsteigender Reihenfolge sortiert angeordnet sind.

Ist das nicht der Fall, werden die Elemente an den Stellen $j$ und $j - delta$ ausgetauscht, bis die $h$-Folge sortiert ist.
Für den ersten Durchgang des Algorithmus an dieser Stelle mit $h_4 = 8$ ergibt sich somit die in Abbildung 3 dargestellte Reihenfolge der Schlüssel:

^{Figure 3 Nach dem ersten Durchgang sind die Schlüssel in den Abständen h₄ = 8 sortiert, es ergeben sich zwei sortierte Teilfolgen der Länge 8.}

Die weiteren Durchgänge des Algorithmus sortieren das Feld entsprechend der Größe $h$: Es sind danach jeweils Schlüssel mit den Abständen $4$ (Abbildung 4 und $2$ (Abbildung 5) sortiert; im letzten Schritt dann vollständig (Abbildung 6):

^{Figure 4 Die Sortierung für h₃ = 4, es sind 4 Folgen deren Schlüssel jeweils den Abstand 4 zueinander haben.}

^{Figure 5 Im vorletzten Sortierschritt sind 8 Folgen der Länge 2 sortiert.}

^{Figure 6 Der letzte Durchgang des Algorithmus vergleicht Schlüssel mit Distanzfolgen der Länge 1, also direkt benachbarte Schlüssel.}

Für die Berechnung der Anzahl der Aufrufe von $c3$ stellt man fest, das in diesem Fall in jedem Schritt immer 2 Elemente, die eine Distanz von $h_s$ aufweisen, falsch sortiert sind.

Der Algorithmus tauscht daraufhin in jedem Durchgang alle Schlüssel untereinander aus, die er über min < arr[j-delta] miteinander vergleicht, was folglich die maximale Anzahl von Schlüsselvertauschungen in dieser vergleichsbasierten Implementierung für ein Feld der Größe $n$ ergibt, nämlich $\frac{n}{2}$. Insgesamt finden dadurch für $c3$

Aufrufe statt.

Mit der Anzahl der berechneten Aufrufe $c1, c2, c3$ ergibt sich somit für die Laufzeit $T(n)$ für diesen Fall

und zusammengefasst

was nach Einsetzen zu

Aufrufen für unser Beispiel führt.

Nachweis der Komplexitätsklasse​

Um $O$ zu ermitteln, werden nun alle Konstanten der Funktion

eliminiert, und der "dominante" Summand in Abhängigkeit von $n$ betrachtet, der in diesem Fall $lg(n) * n$ ist.

Wir vermuten ein $N-log-N$-Wachstum⁷ (vgl. [📖OW17a, p. 5]), und wollen nun zeigen, dass $T(n)$ in $O(n\ log\ n)$ liegt.
Hierfür müssen wir ein geeignetes $c$ und ein $n_0$ finden, so dass gilt:

(vgl. [📖GD18a, p. 11]).

Zu zeigen ist

Wir wählen für $n_0 = 1$ und $c = \frac{3}{2}$, denn es gilt sicher

Ausserdem gilt stets $\forall n \in \mathbb{N}: lg(n) < n$, woraus $lg(n) - n < 0$ folgt, und damit auch $lg(n) - n + 1 \leq 0$.

Insgesamt gilt also

womit $f = O(n * log(n))$ gezeigt ist. ◻

Worst-Case-Analyse​

Unter der Annahme, dass ein in umgekehrter Reihenfolge sortiertes Feld zu einer Laufzeit von $O(n^2)$ bei dem Shellsort-Algorithmus führt, konnten wir mit dem in dem vorherigen Abschnitt gewählten Parametern nur eine Laufzeit von $O(n\ log\ n)$ nachweisen.
Tatsächlich stellt der Anwendungsfall nicht den worst-case für den Algorithmus dar, da ja gerade diese Form von Sortierreihenfolge dem Algorithmus die Vorsortierung der $h$-Folgen ermöglicht:

The idea underlying Shellsort is that moving elements of A long distances at each swap in the early stages, then shorter distances later, may reduce this $O(n^2)$ bound. [📖Pra72, p. 3]

Es gilt also, die Vorsortierung auszuhebeln.
Für Insertion-Sort ist die Laufzeit im worst-case $O(n^2)$ (vgl. [📖OW17b, p. 87]). Da Shellsort mindestens im letzten Schritt diese Sortiermethode auf Distanzfolgen der Länge $1$ anwendet, muss der Algorithmus eine Folge als Eingabe erhalten, die durch die ersten $lg(n) - 1$-Durchgänge (mit $h_s = 2^{s - 1}, 1 \leq s < lg(n)$) keine Änderungen erfährt, um dann im allerletzten Schritt auf einen Schlag sortiert wird, was maximal $\frac{n}{2}$ Inversionen⁸ bedeutet, und damit ebenso viele Vertauschungen (zuzüglich der benötigten Verschiebe-Operationen).
Hierzu kann wie im vorherigen Beispiel für $n=16$ ein Feld mit folgender Schlüsselanordnung verwendet werden: Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index. Hier gilt für alle Elemente aus dem Feld $A$:

Abbildung 7 veranschaulicht die Anordnung.

^{Figure 7 Eine worst-case Schlüsselfolge für Shellsort. Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index.}

Markiert sind die direkt benachbarten Felder, die eine Inversion aufweisen, die im letzten Schritt des Algorithmus eine bzw. mehrere Verschiebungen bedingen.
In den vorherigen Schritten - also bei den Durchgängen mit Distanzfolgen $h_s > 1$ - findet der Algorithmus jeweils Schlüssel in korrekter Sortierreihenfolge vor.

Mit $h_4 = 8$ werden die Felder $A[0..7]$ mit den Feldern $A[8..15]$ verglichen - hier gilt in jedem Fall, dass die Schlüssel $A[i] < A[j] (\forall i < j, j - i = 8)$ sind.

Auch im darauffolgenden Durchgang ($h_3 = 4, j - i = 4$) finden keine Verschiebungen statt, da keine Inversion gefunden wird. Erst im letzten Schritt, in dem direkt benachbarte Elemente miteinander verglichen werden, werden die Inversionen ermittelt und die Verschiebung der Elemente findet statt (s. Abbildung 8.

^{Figure 8 Für die worst-case Schlüsselfolge werden im letzten Schritt 7 Inversionen festgestellt. Jede dieser Fehlstellung bedingt eine Verschiebung um die angegebene Anzahl von Positionen.}

In diesem Fall wird $c3$ insgesamt $32$ mal aufgerufen.

Da jeweils zwei Schlüssel bereits korrekt sortiert sind ($A[0]$ und $A[n-1]$) existieren noch $\frac{n}{2} - 1$ Inversionen. Jede Inversion erzwingt eine Verschiebung des größten Elements um $\frac{i}{2}$ Positionen nach links.

Für die Berechnung der Laufzeitkomplexität ergibt sich somit der Term

und unter Berücksichtigung der Terme für $c1$, $c2$, $c3$ die Funktion

was zu einer Laufzeitabschätzung von $O(n^2)$ führt.

Thema​

Für 2023 stand die Zulassungsarbeit zum Master-Fernstudiengang Informatik an der Hoschschule Trier unter dem Thema Funktionsprinzipien und Anwendung künstlicher Intelligenz (KI) in der Medizin.

Das Thema wurde Ende Mai 2023 bekannt gegeben, als Bearbeitungszeitraum wurde der 01.07. - 02.10.2023 vorgegeben.

Vorbereitung​

Zur Einarbeitung in das Thema hat mir Grundkurs Künstliche Intelligenz [📖Ert21] von Prof. Dr. Wolfgang Ertel (Hochschule Ravensburg-Weingarten) geholfen. Das Buch hat mich auf die (formalen) Grundlagen der Aussagenlogik und Prädikatenlogik vorbereitet sowie einführend maschinelles Lernen und Neuronale Netze erklärt, was mir die anschliessende Arbeit mit Russel & Norvig's [📖RN12] erleichterte. Das Standardwerk zum Thema Künstliche Intelligenz geht detailliert (in Teilen auch sehr formal) auf Agentenmodelle, Problemlösungen, Logik, Entscheiden und Lernen ein.

Da nicht nur Künstliche Intelligenz als Thema vorgeben gewesen ist, sondern auch Medizin, habe ich darüber hinaus [📖Pfa22] (quer)gelesen, um mir einen Überblick über die verschiedenen Anwendungsgebiete von KI im Gesundheitswesen zu verschaffen. Ergänzend dazu habe ich mit großem Interesse den Podcast Dr. med. KI von Prof. Dr. Kerstin Ritter (Charité Berlin) und Mike Bernd (Stifterverband für die Deutsche Wissenschaft e.V.) verfolgt, in dem Themen aus den Bereichen Medizin, Informatik und Ethik zusammengefasst und Hintergründe, Problematiken und Ausblicke in Zusammenhang mit KI diskutiert werden.

Eingrenzung des Themas und Ausarbeitung​

Im Juli des gleichen Jahres habe ich dann mit der Ausarbeitung begonnen, das Thema hatte ich - noch etwas unscharf - auf den Einsatz von KI bei bildgebenden Verfahren in der Medizin eingegrenzt. Da hier KI überwiegend in Form neuronaler Netze stattfindet, musste ich mich also noch in dieses Thema einarbeiten: Während die Vorbereitung im Juni also das Verständnis um Künstliche Intelligenz geschärft hatte, wurde mir schnell klar, dass das ein bloßes Kratzen an der Oberfläche gewesen ist. Um Modelle neuronaler Netze nachvollziehen zu können, musste ich zunächst das biologische Vorbild verstehen, was mich zu den Neurowissenschaften führte.

Die Literatur, die ich bis zu diesem Zeitpunkt durchgearbeitet habe, hatte meinem Empfinden nach die tierische Nervenzelle als Mittel zum Zweck gesehen: Signalweiterleitung und verrechnende Einheiten in einem neuronalen Netze wurde zwar als Abstraktion biochemischer Vorgänge im Gehirn verstanden, aber das Warum und Wie wurde wenig ausführlich erklärt.

Es war mir also ein großes Anliegen,die komplexen biochemischen Vorgänge im Nervensystem zu verstehen und als fachlichen Hintergrund der Arbeit voranzustellen, um die großen Erfolge, die der Einsatz Künstlicher Intelligenz in den letzten Jahren in der Medizin vorweisen konnte, dem Leser besser verständlich zu machen.

Folglich legte ich das Thema meiner Arbeit fest:

Eine Einführung in mathematische Modelle der biologischen Nervenzelle als Bausteine künstlicher neuronaler Netze und deren Anwendung im Gesundheitswesen.

Es sollte die Signalweiterleitung im biologischen Neuron erklären, erste, frühe Modelle künstlicher Neuronen vorstellen, den Bogen zu künstlichen neuronalen Netzen spannen und dann Anwendungsbeispiele aus dem Gesundheitswesen aufführen.

Abgabe und Bewertung​

Ich hatte damit begonnen, erste Entwürfe in Markdown zu schreiben, damit mir eine spätere Überführung der Arbeit in eine lesbare Form auf meine Webseite erleichtert wird. Die Hochschule stellt Word- und Latex-Vorlagen zur Verfügung - die ich im Anschluss für eine Portierung nutzen wollte.

Als ich mit dem ersten Entwurf meiner Arbeit - ca. Mitte September - fertig war, hatte ich nach Korrektur und meiner (bescheidenen) Zählweise nach gut und gerne 20 - 30 DIN A4 Seiten Text (ohne Illustrationen und Tabellen) - an der Stelle war mir aber schon klar, dass ich den ein oder anderen Abschnitt eher ausführlich als kompakt beschrieben habe, weshalb ich noch eine Woche Lektorat eingeplant hatte.

Nach der Überführung in Latex, die ca. eine Woche gedauert hat, zählte ich - unter Verwendung der Vorlage, die Trier zur Verfügung gestellt hat, ca. 80 Seiten - ohne Inhalts-, Literatur- und Abbildungsverzeichnis. Das Lektorat umfasste also nicht nur inhaltliche und formale Korrekturen, sondern teilweise auch das komplette Umschreiben des ein oder anderen Kapitels, weil viel Stoff in den Anhang wechseln musste: Vor allem Biografien von Persönlichkeiten, die sich in Forschung und Wissenschaft um das Thema verdient gemacht haben, sowie Begriffe und Ergänzungen rund um das Thema Neurobiologie.

Die korrigierte Fassung, die als Vorlage der finalen Abgabeversion diente, umfasste dann knapp 45 Seiten, mit ungefähr 50 Seiten Anhang.

Für die Abgabeversion wurde also noch einmal inhaltlich soweit gekürzt, dass die Intention einer "Einführung" weitestgehend erhalten blieb - mir war aber auch klar, dass eine Arbeit, die Neurobiologie, Neurowissenschaften, Informatik, Mathematik und Medizin unter dem Thema "Künstliche Intelligenz" auf 20 (Vorgabe Prüfungsausschuss) Seiten zusammenfasst, keine Einführung mehr sein kann. Die Abgabeversion wurde kurzum umbenannt in

Mathematische Modelle der biologischen Nervenzelle als Bausteine künstlicher neuronale Netze und deren Anwendung im Gesundheitswesen

und umfasst 30 Seiten, inkl. Tabellen und Illustrationen. Der Anhang ist komplett entfallen, Fußnoten, die in der Ursprungsversion zahlreich vorhanden sind und viele Ergänzungen bieten, rausgekürzt.

Die Abgabeversion entsprach somit den formalen Vorgaben, was sich auch in der Bewertung der Arbeit widerspiegelte.

Download​

Die Arbeit liegt in zwei Versionen vor: Eine ausführliche Ausarbeitung der wichtigen Themen, die einen einführenden Charakter besitzt, sowie die gekürzte Fassung, die den formalen Vorgaben entspricht.

In beide Versionen wurden bereits Anmerkungen und Korrekturen aus dem Errata übernommen. Glücklicherweise beschränkten sich diese weitestgehend auf wenige Fehler in der Orthographie und einen Fehler in der formalen Herleitung des McCulloch-Pitts-Netzes als Graph in Abschnitt 3.1.4 (ungekürzte Version, entfallen in der Abgabeversion).

• Download ungekürzte Version (pdf)
• Download gekürzte Abgabeversion (pdf)

I have updated my Perceptron-implementation with a plotting function that allows for visualizing the adjustments of the Perceptron's weight-vector through the epochs.

The source-code can be found at https://github.com/ThorstenSuckow/pylabs.

Usage​

Create input data and the associated output values. As an example, the following represents the logical AND-function:

import numpy as np
from Perceptron import Perceptron

# input
X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

# output
y = np.array([0, 0, 0, 1])

In the next step, the Perceptron is created.

p = Perceptron(50, 0.3)

Once a Perceptron-instance is available, you can pass the input- and output-values to learn():

p.learn(X, y)

and test data with

result = p.test([0, 0])

result holds the computed weight vector if the training data could be separated within the epochs. If that failed, None is returned.

Note: The bias is available with p.bias

A log is available for all steps processed by learn():

for step in p.log:
    print(step)

You can pass the log to the PerceptronPlotter which will recreate the computation visually.

Examples​

and​

The and-function with a Perceptron.

X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

title= "\"AND\""
y = np.array([0, 0, 0, 1])

p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)
anim = plotter.animate(500)

or​

The or-function with a Perceptron.

X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

title= "\"OR\""
y = np.array([0, 1, 1, 1])

p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)
anim = plotter.animate(500)

xor​

The xor-function with a Perceptron.

X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

title= "\"OR\""
y = np.array([0, 1, 1, 0])

p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)
anim = plotter.animate(500)

With the Perceptron as a linear discriminant function, the algorithm can not properly create a separator for XOR [📖MIN69]. The Plotter shows the Epoch-label marked as red, which tells that the algorithm was not able to find a separator in 50 epochs.

Cluster Example​

The following uses isotropic Gaussian blobs generated by sklearn.datasets.make_blobs. The animate-method is called with an interval of 100 to speed up epoch-runs. The interplay of a larger set of data and the re-adjusting of the separator if accuracy does not reach 1 for a full epoch can be observed nicely.

title = "Clusters"
X, y = make_blobs(n_samples=50, n_features=2, centers=2, cluster_std=2.5)


p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)

anim = plotter.animate(100)

Resources

• https://github.com/ThorstenSuckow/pylabs

Errata für Beweisen lernen (Springer Verlag 2020) von Junk und Treude. Ich hoffe, dass meine Notizen dem Autorenteam zur Überprüfung und ggf. Korrektur nützlich sind.

Zum Hintergrund dieses Blog-Posts gibt es weiter unten mehr Informationen.

Errata​

Vergleichslösungen​

Ideen: Metrische Räume​

Ideen: Äquivalenzklassen​