ZsoltTest

Einführung in Computational Intelligence und AI

Die Idee hinter der künstlichen Intelligenz, KI (Artificial Intelligence - AI), bestand darin, die Prozesse der menschlichen Wahrnehmung wie Denken, Lernen oder Mustererkennung nachzubilden. Das Erscheinen der KI in der akademischen Welt begann mit der Simulation des Verhaltens neuronaler Netze bei IBM im Jahr 1955. Dies führte zu einer Konferenz zu diesem Thema, die heute als Dartmouth-Konferenz bekannt ist und als Geburtsstunde der künstlichen Intelligenz gilt.

Die Geschichte der KI als akademische Disziplin hat einen langen, weitreichenden und abenteuerlichen Weg zurückgelegt, der optimistische und zweifelhafte, verrufene Phasen durchquerte und durch viele wissenschaftliche Bereiche führte. Es begann mit dem Studium der ,,formalen“Argumentation, das unter anderem zu Alan Turings Berechnungstheorie oder zur Programmiersprache Lisp sowie zum kommerziellen Erfolg von Expertensystemen in den frühen 1980er Jahren führte. Es folgte eine eher zweifelhafte Zeitraum, während andere Ansätze wuchsen, wie z.B. Bewegen von technischen Maschinen.

Mit der rasanten Entwicklung der Rechengeschwindigkeit und -fähigkeiten der Computer entstanden spätestens in den 1990er Jahren rechenintensive Zweige der KI. Computational Intelligence umfasst die biologisch motivierten Bereiche der Informationsverarbeitung, wie z.B. evolutionäre Algorithmen. Maschinelles Lernen ist ein umfassender Zweig der KI, der viele rechenintensive Teilbereiche umfasst. Eine davon ist die auf statistischen Ansätzen basierende Mustererkennung, die Ende der 1990er Jahre zu einem großen kommerziellen Erfolg bei Befehls- und Kontrollsystemen (command&control systems), Spracherkennungssystemen mit großem Vokabular (Large Vocabulary Speech Recognition Systems - LVSRS) und ihren Anwendungen in Callcentern und in der Radiologie führte. Diese Ansätze haben sich in den 2000er Jahren abgeflacht, als sie die Sättigung des angewandten statistischen Ansatzes erreichten.

Mittlerweile führte die Entwicklung von Ideen zur Wissensdarstellung zu fortgeschritteneren Ansätzen wie Ontologie oder Wissensgraphen (Knowledge Graphs - KG).

Die wichtigste Entwicklung war jedoch die Wiederbelebung der neuronalen Netzwerkforschung, die zu vielen erfolgreichen Anwendungen führte, wie z.B. Erkennung handgeschriebener Ziffern. Der eigentliche Durchbruch bei der Verwendung neuronaler Netze kam mit Deep Learning, das erfolgreich auf die Klassifizierung großer Datenmengen angewendet werden kann, wie z.B. Bilder. Der Erfolg von Deep Learning führte zu einem enormen Anstieg des Interesses an und der Finanzierung von KI. Deep Reinforcement Learning ermöglicht die erfolgreiche Umsetzung automatischer Steuerungsaufgaben.

Die jüngste Entwicklung im Bereich der KI ist die Anwendung spezifischer großer Sprachmodelle (Large Language Model - LLM) und fortschrittlicher Darstellungstechniken in prädiktiven Transformatoren, die zu Produkten führen, wie z. B. ChatGPT 3.5.

Im Wesentlichen soll KI die unterschiedlichen Fähigkeiten der menschlichen Intelligenz umsetzen. Dazu gehören Lernen, Wahrnehmung, logisches Denken, Abstraktion sowie komplexere Fähigkeiten wie z.B. Zusammenfassung, Kontrolle, Aufgabenlösungsfähigkeiten und vieles mehr. Eines der langfristigen Ziele ist die Schaffung einer allgemeinen Intelligenz, der sogenannten Künstlichen Allgemeinen Intelligenz (Artificial General Intelligence - AGI), die eine Vielzahl von Problemen ähnlich der menschlichen Intelligenz lösen könnte.

Raymond Kurzweil, Pionier unter anderen der optischen Texterkennung (Optical Character Recognition - OCR), Sprachsynthese (speech synthesis), Spracherkennung, ein Visionär der künstlichen Intelligenz hat vorhergesagt, dass (einfach formuliert) spätestens im Jahr 2029 die KI klüger sein werden als das Mensch. Kritiker sagen, dass in der Richtung der Entwicklung zukünftiger Technologien er wahrscheinlich Recht hat, aber die prognostizierte Zeitspanne stimmt nicht, er ist zu optimistisch.

KI ist eine unvermeidliche zukünftige Entwicklungsrichtung und eine der Kernfachgebiete der Wissenschaftsfeld Data Science. Beachten Sie, dass Data Science in wirtschaftlichen Kontext auch als Business Analytics bekannt ist.

Grundlagen von Computational Intelligence und AI

Mathematische Grundlagen von KI

Es gibt keine Einheitliche Definition von KI. Eine mögliche ausdrucksvolle Definition kann wie folgt angegeben werden: KI ist the field of study in computer science that develops and studies intelligent machines. Allerdings unter KI ist auch die ,,intelligente Maschine“ selbst zu verstehen.

Die Ziele von KI sind Teilmenge möglicher Arten menschlicher intelligenter Aktivitäten zu implementieren. Dazu gehört Argumentation (reasoning), Wissensrepräsentation (knowledge representation), Planung (planning), Lernen (learning), Verarbeitung natürlicher Sprache (natural language processing), Wahrnehmung (perception) und Unterstützung für Robotik (support for robotics).

Im Folgenden geben wir eine kurze mathematische Beschreibung einiger ausgewählten grundlegender Konzepte der KI. Das beinhaltet

1. Regelbasierte Methoden,
2. Wissensrepräsentation,
3. Linear regression mit MSE-Framework
4. Klassifikation - Bayesian decision theory
5. Klassifikation - lineare Diskriminanzfunktionen
6. Lernen aus Beispiele
7. Learning durch Steuereung - MDP

Regelbasierte Methoden

Logische Argumentation zielt auf menschliche Fähigkeit ab, Schritt für Schritt zu argumentieren oder/und logische Schlussfolgerungen zu ziehen. Dies wird realisiert durch Regelbasierte Methoden (rule-based methods). Sie bieten eine deterministische Methode zur Klassifizierung in Problemen, in welchen Klassen aus Beziehungen von Entitäten bestimmt werden können, die Eigenschaften einiger Entitäten darstellen. Solche Entitätenbeziehungen werden üblicherweise durch die breite Klasse der if-then rules (Wenn-Dann-Regeln) dargestellt. Eine einfache if-then rule lautet:
IF EinerDerFünfGrößtenOrteÖsterreichs(x) THEN Stadt(x)
was natürlich bedeutet, dass wenn ein Objekt x der Eigenschaft hat, einer der fünf größten Orte von Österreichs zu sein, dann ist x eine Stadt.

If-then rules können auch logische Verknüpfungen einbeziehen, wie es im folgenden Beispiel gezeigt wird:
IF Fahrzeug(x) AND AufSchienenFahrendes(x) THEN Bahnfahrzeug(x)
Darüber hinaus sind in if-then rules auch Funktionen erlaubt, die numerische Werte zurückgeben. Dies wird wie folgt veranschaulicht:
IF Female(x) AND (Age(x) < 16) THEN Girl(x),
wobei der Age(x) ist eine Funktion, die das numerische Alter in Jahren zurückgibt, und der Ausdruck (Age(x) < 16) gibt entweder logisch ,,True“ oder ,,False“ zurück.

Eine predicate (Aussage), wie z.B. Vögel(x), HatFlügel(x) and HatKörperbedeckungAusFeder(x) and HatSchnabel(x), ist ein Test, der entweder logisch ,,True“ oder ,,False“ zurückgibt. Es gibt zwei Haupttypen von if-then rules, die propositional (variablenfrei Aussage) and first-order Regeln. Die bisherige Beispiele sind alle first-order Regel, da alle sich auf eine Variable x beziehen. Ein Beispiel für propositional if-then rules ist
IF EineDerFünfGrößtenOrteVonÖsterreich (Wien) THEN Stadt(Wien),
da diese Regel eine Aussage nur für die logische Konstante (=bestimmte atomare Instanz) Wien beschreibt.

Die first-order if-then rules sind leistungsstarke logische Regeln, was durch folgendes Beispiel verdeutlicht wird:
IF Parent(x,y) AND Parent(y,z) THEN Grandchild(z,x)

If-then rules können auf algorithmischem Wege erlernt werden. Der Sequential Covering Learning Algorithmus basiert auf dem Lernen aus Trainingsdaten, die aus einer Menge positiver und negativer Aussagen (Prädikate) bestehen. Der Algorithmus erstellt Regeln, die die Menge der positiven Prädikate abdecken, aber keines der negativen Prädikate. Das Grundprinzip des Algorithmus besteht darin, jeweils eine Regel zu lernen und diesen Vorgang zu wiederholen um schrittweise alle positiven Prädikate abzudecken. Daher heißt der "Sequential Covering". Entsprechend umfasst der Algorithmus drei Schritte: Lernen einer einzelnen Regel um am meisten positive Prädikate abzudecken (Learn-One-Rule), Löschen der dadurch abgedeckte Prädikate und Iterieren. Das Ergebnis ist ein disjunktes Regelwerk, das die gesamte Menge der positiven Prädikate abdeckt.

Beispiel .

Als Trainingsdaten werden die folgende Aussagen über Möbelwaren angegeben:

Trainingsdaten - Aussagen über Möbelwaren

Aussage-ID	Größe	Möbelhaus	Teuer
1	groß	Möbelix	False
2	klein	Möbelix	False
3	groß	Kika	True
4	klein	Kika	False
5	groß	XXXLutz	True
6	klein	XXXLutz	True

Die Aussagen 3,5 und 6 bilden die Menge der positiven Prädikaten, während die anderen (1,2 und 4) der Menge der negativen Prädikaten gehören. Zuerst werden mittels Learn-One-Rule die beste Hypothese bestimmt, d.h. die Regel die am meisten positive Prädikate abdeckt:
IF Möbelhaus(x,XXXLutz) THEN Teuer(x),
wobei x die Variable für Möbelwaren ist. Dann werden die Prädikaten 5,6 aus dem Trainingsdaten gelöscht. Wendet man Learn-One-Rule noch einmal an, bekommt man die Regel
IF Größe(x,groß) AND Möbelhaus(x,Kika) THEN Teuer(x)
Damit alle positiven Prädikate wurde abgedekt, also endet der Algorithmus hier. Beachten Sie, dass die beiden gefundenen Regeln disjunkt sind, was aus dem Verlauf des Algorithmus folgt.

Die endgültige Regel lautet wie folgt:
IF Möbelhaus(x,XXXLutz) (deckt die Beispiele 5,6)
OR (Größe(x,groß) AND Möbelhaus(x,Kika)) (deckt das Beispiel 3)
Then Teuer(x)

Die Visualisierung des Sequential Covering Learning Algorithmus wird in Abbildung 1.1 gezeigt.

Abbildung 1.1 Visualisierung des Sequential Covering Learning Algorithmus

Das vorige Beispiel zeigt den Aufbau eines Regels mittels Sequential Covering Learning Algorithmus für Binäre Klassifizierung, welche die mögliche Prädikate in eine von zwei Klassen eingeteilt werden: Teuer(x) = True oder Teuer(x) = False. Die Regelbasierte Methoden können für Klassifizierung nicht nur in zwei sondern in mehrere Klassen angewendet werden. Nachfolgend wird der Sequential Covering Learning Algorithmus für den allgemeinen Fall von Lernregeln für die Klassifizierung in eine endliche Anzahl von Klassen gezeigt.

—————————————————————————————
Algorithm  Sequential Covering Algorithm
—————————————————————————————
Eingabe:
- Die Menge T, Trainingsdaten, bestehend aus positiver und negativer Prädikaten
- Die geordnete Menge von Klassen, ${\textstyle C={c1,...,c_{k}}}$
Output: Individuelle Regel für jede Klasse
in Form eine mit AND verbundener Liste der gefundenen Regeln,
${\textstyle R_{i}}$ für die Klasse ${\textstyle c_{i},i=1,...,k}$,
die die Klassifikation durch Ausprobieren der Regellisten, ${\textstyle R_{i}}$,
in der Reihenfolge ${\textstyle i=1,...,k}$, realisieren.
—————————————————————————————
1 Initialize the rule lists, ${\textstyle R_{i}={}}$, ${\textstyle i=1,...,k}$
2 for i= 1:(k-1)
3   while not every positive predicate is covered in class ${\textstyle c_{i}}$
4     ${\textstyle r}$ <– Learn-One-Rule
5     Removing predicates from training data covered by ${\textstyle r}$
6     Add r to the end of the rule list ${\textstyle R_{i}}$
7   end
8 end
—————————————————————————————

Auf diese Weise werden mögliche komplexe if-then rules erlernt. Dieser Greedy-Algorithmus ist nicht unbedingt optimal, d. h. er liefert nicht unbedingt die kompaktesten Regeln. Daher können die resultierenden Regeln in einem Nachbearbeitungsschritt durch die Anwendung logischer Umformulierungsregeln weiter vereinfacht werden. Der Schritt Learn-One-Rule kann auf auf unterschiedliche Art und Weise realisiert werden. Eine effektiver Ansatz ist beam search. Man kann über Sequential Covering Algorithmenfamilie reden, da geänderte und erweiterte Varianten des ursprünglichen Algorithmus existieren. Typische Varianten sind Ripper Algorithmus, Foil Algorithmus oder CN2 Algorithmus. If-then rules können auch auf andere Weise, z. B. mittels Entscheidungsbäume auch gelernt werden.

Regeln haben den Vorteil, dass sie einfach zu interpretieren sind und in relationalen Datenbanken implementiert werden können. Allerdings hängt die Auswahl der Prädikate für die Trainingsdaten stark von der Aufgabe ab und ist in der Praxis eine schwierigere Aufgabe als das Erlernen der Regeln. Regelbasierte Methoden sind integraler Bestandteil von Expertensystemen in der KI.

Wissensrepräsentation

Representing knowledge on word level can be realized by probabilistic model of natural language, which is called Language Model (LM) Usually an LM is used to estimate the probability of a given word sequence ${\textstyle w_{1},w_{2},...,w_{n}}$, i.e. ${\textstyle P(w_{1},w_{2},...,w_{n})}$, which can be given as a product of the conditional probabilities as
${\textstyle P(w_{1},w_{2},...,w_{n})=P(w_{1})P(w_{2}|w_{1})...P(w_{n}|w_{n-1},...,w_{2},w_{1})}$.

In the N-gram LM, due to practical reasons, the word sequence probability, ${\textstyle P(w_{1},w_{2},...,w_{n})}$ is approximated as
${\textstyle P(w_{1},w_{2},...,w_{n})=\prod _{i=1}^{n}P(w_{i}|w_{i-1},w_{i-2},...,w_{i-N+1})}$,
where the words with negative index must be omitted from the probabilities. The conditional probabilities ${\textstyle P(w_{i}|w_{i-1},w_{i-2},...,w_{i-N+1})}$ can be estimated from the relative frequencies of the N-grams and (N-1)-gramms as
${\textstyle P(w_{i}|w_{i-1},w_{i-2},...,w_{i-N+1})={\frac {c(w_{i},w_{i-1},...,w_{i-N+1})}{c(w_{i-1},w_{i-2},...,w_{i-N+1})}}}$,
where ${\textstyle c(x)}$ stands for the number of occurrences of string x.

The probabilities ${\textstyle P(w_{i})forN=1,P(w_{i},w_{j})}$ for ${\textstyle N=2}$ and ${\textstyle P(w_{i},w_{j},w_{k})}$ for ${\textstyle N=3}$ are called unigram, bigram and trigram probabilities, respectively. The N-gram LM is purely Statistical LM (SLM), since it is trained on N-gram statistics of the training corpora. The estimates of the conditional probabilities ${\textstyle P(w_{i}|w_{i-1},w_{i-2},...,w_{i-N+1})}$ to be reliable requires that the corresponding N-grams and (N-1)-grams must be present in the training corpora. This implies that the training corpus must be large enough. The SLM can not assign any probability to N-grams, which does not appear in the training corpus. This problem is usually solved by applying smoothing techniques, in which a small part of the probability measure is shifted to the unseen grams.

The most effective method of smoothing is the Kneser–Ney smoothing, in which a fixed value is subtracted from the conditional probability’s of N-grams with lower frequencies and the so won probabilities are spread over the conditional probabilities of all non-appearing N-grams. The equation for the conditional bigram probabilities is given by
${\textstyle P_{KN}(w_{i}|w_{i_{1}})={\frac {max(c(w_{i-1},w_{i})-\delta ,0)}{\sum _{w_{j}}c(w_{i-1},w_{j})}}+\lambda _{w_{i-1}}P_{KN}(w_{i})}$
and
${\textstyle P_{KN}(w_{i})={\frac {|{w_{j}:0<c(w_{j},w_{i})}|}{|{(w_{j},w_{k}):0<c(w_{j},w_{k})}|}}}$.
Here ${\textstyle \delta }$ is the constant discount value to be subtracted and ${\textstyle \lambda _{w_{i-1}}}$ is a normalization constant, which is set to make the sum of ${\textstyle P_{KN}(w_{i}|w_{i_{1}})}$ over all ${\textstyle w_{i}}$ equal to one. The conditional probability’s of N-grams with lower frequencies will be determined by the unusual probability term ${\textstyle P_{KN}(w_{i})}$, which realizes an estimation for the conditional probability of the unseen bigram form other bigram counts related to ${\textstyle w_{i}}$.

Besides of LMs, another ways of knowledge representation are

• Semantic network - a graph representing semantic relations between concepts. The concepts are represented by the nodes and the edges specify the semantic relations. One reason to design semantic networks is to represent knowledge in machine readable form. Knowledge graphs are semantic networks with limited set of semantic relations.
• Ontology- hierarchical representation of concepts and their relationships, which can be managed by standard ontology language such as OWL or RDF.

Linear regression mit MSE-Framework

The task of linear regression is to give an linear prediction for the random scalar output ${\textstyle y\in \mathbb {R} }$ from the random input vector ${\textstyle {\bf {x}}}$. Let ${\textstyle {\hat {y}}}$ be the predicted value of ${\textstyle y}$. It is assumed that the ${\textstyle y}$ depends linearly from the vector ${\textstyle {\bf {x}}}$, hence the predicted value ${\textstyle {\hat {y}}}$ can be given as linear combination of ${\textstyle {\bf {x}}}$ as ${\textstyle {\hat {y}}=w_{1}*x_{1}+\ldots +w_{n}*x_{n}}$ or in vector form

$${\hat {y}}={\bf {w}}^{T}{\bf {x}},$$

where ${\textstyle {\bf {w}}=(w_{1},\ldots ,w_{n})^{T}}$ is a column vector of parameters. Here ${\textstyle ^{T}}$ stands for the transpose operation and the vectors are by default column vectors. The parameters ${\textstyle w_{i}}$ can be seen as weights. If input value ${\textstyle x_{i}}$ has positive weight, then increasing ${\textstyle x_{i}}$ also increases the predicted value ${\textstyle {\hat {y}}}$. Similarly if ${\textstyle x_{i}}$ has negative weight, then increasing ${\textstyle x_{i}}$ decreases the predicted value ${\textstyle {\hat {y}}}$. If ${\textstyle w_{i}}$ is a large value then ${\textstyle x_{i}}$ has a large impact on ${\textstyle {\hat {y}}}$. If ${\textstyle w_{i}=0}$ then ${\textstyle x_{i}}$ has no effect on ${\textstyle {\hat {y}}}$.

Suppose that ${\textstyle K}$ examples of the vector ${\textstyle {\bf {x}}}$ and the correct value of output ${\textstyle y}$ to each of them are given. We arrange the input vectors in a matrix ${\textstyle {\bf {X}}}$ on that way that vector ${\textstyle {\bf {x}}_{k}}$ is placed into the ${\textstyle k}$-th row of matrix ${\textstyle {\bf {X}}}$, ${\textstyle k=1,\ldots ,K}$. The output values and the predicted values are also arranged into a column vector ${\textstyle {\bf {y}}}$ and ${\textstyle {\bf {\hat {y}}}}$ so, that the correct value ${\textstyle y_{k}}$ and the predicted value ${\textstyle {\hat {y}}_{k}}$ belonging to the input vector ${\textstyle {\bf {x}}_{k}}$ comes to the ${\textstyle k}$-th position in the vector ${\textstyle {\bf {y}}}$ and ${\textstyle {\bf {\hat {y}}}}$, respectively.

The optimal parameter vector ${\textstyle {\bf {w}}}$ can be determined from an optimum task with respect to a performance measure quantifying the quality of prediction.

Linear regression with mean squared error

One possible choice for the performance measure is the Mean Squared Error (MSE) of the predictions, which is biven by

$$MSE={\frac {1}{K}}\sum _{k}({\bf {\hat {y}}}_{k}-{\bf {y}}_{k})^{2}={\frac {1}{K}}\lVert {\bf {\hat {y}}}-{\bf {y}}\rVert _{2}^{2},$$

where ${\textstyle \lVert z\rVert _{2}}$ stands for the ${\textstyle \mathbb {L} _{2}}$ norm of ${\textstyle z}$.

Then the optimal value of parameter vector ${\textstyle {\bf {w}}}$ is obtained by minimizing the MSE. The necessary condition of having a local minimum of MSE is to have a value of parameter vector ${\textstyle {\bf {w}}}$, for which the gradient of MSE is 0. It can be shown, that in our case, MSE as function of ${\textstyle {\bf {w}}}$ is a convex function, in which case there is only one such value of ${\textstyle {\bf {w}}}$, and hence it is also the global minimum point. Therefore the best value of parameter vector ${\textstyle {\bf {w}}}$ is obtained by solving the equation

$$\nabla _{\bf {w}}MSE=\nabla _{\bf {w}}\left({\frac {1}{K}}\lVert {\bf {\hat {y}}}-{\bf {y}}\rVert _{2}^{2}\right)=0,$$

where ${\textstyle \nabla _{\bf {w}}}$ stands for the gradient with respect to ${\textstyle {\bf {w}}}$. The set of predicted outputs can be given in vector-matrix form as ${\textstyle {\bf {\hat {y}}}={\bf {X}}{\bf {w}}}$. Applying it in the above relation gives the equation to be solved in terms of ${\textstyle {\bf {w}}}$ as

$$\nabla _{\bf {w}}MSE=\nabla _{\bf {w}}\left({\frac {1}{K}}\lVert {\bf {X}}{\bf {w}}-{\bf {y}}\rVert _{2}^{2}\right)=0.$$

Omitting the constant ${\textstyle {\frac {1}{K}}}$, evaluating the gradient and performing several rearrangements we get

Fehler beim Parsen (Unbekannte Funktion „\hspace“): {\displaystyle \begin{aligned} \nabla_{{\bf w}} \left( \lVert {\bf X}{\bf w} - {\bf y} \rVert_2^2 \right) &&\hspace{-5mm}= \nabla_{{\bf w}} \left({\bf X}{\bf w} - {\bf y} \right)^T \left({\bf X}{\bf w} - {\bf y} \right) = \nabla_{{\bf w}} \left( {\bf w}^T {\bf X}^T{\bf X}{\bf w} - 2 {\bf w}^T {\bf X}^T {\bf y} + {\bf y}^T {\bf y}\right) \nonumber \\ &&\hspace{-5mm}= 2 {\bf X}^T{\bf X}{\bf w} - 2 {\bf X}^T {\bf y} = 0, \nonumber \end{aligned}}

where we utilized in the second equality that ${\textstyle {\bf {y}}^{T}{\bf {X}}{\bf {w}}={\bf {w}}^{T}{\bf {X}}^{T}{\bf {y}}}$, since ${\textstyle {\bf {y}}^{T}{\bf {X}}{\bf {w}}}$ is a scalar and thus it equals to its transpose, and in the last equality that matrix ${\textstyle {\bf {X}}^{T}{\bf {X}}}$ is symmetric enabling the above form of ${\textstyle \nabla _{\bf {w}}\left({\bf {w}}^{T}{\bf {X}}^{T}{\bf {X}}{\bf {w}}\right)}$.

Finally the solution for the parameter vector ${\textstyle {\bf {w}}}$ can be expressed from the above equation as

$${\bf {w}}=\left({\bf {X}}^{T}{\bf {X}}\right)^{-1}{\bf {X}}^{T}{\bf {y}}.$$

Matrix ${\textstyle {\bf {X}}^{T}{\bf {X}}}$ is quadratic enabling taking the inverse of it. Nevertheless the inverse exists only if matrix ${\textstyle {\bf {X}}^{T}{\bf {X}}}$ is non-singular, which usually holds, since matrix ${\textstyle {\bf {X}}}$ is constructed from independent input examples.

The above equations in scalar form lead to system of equations, which are called as normal equations.

Linear regression is also used for a slightly extended prediction model, which is given as

$${\hat {y}}={\bf {w}}^{T}{\bf {x}}+b,$$

where the scalar ${\textstyle b}$ is called bias and results that the hyperplane described by the multivariate function ${\textstyle y({\bf {w}})}$ does not pass through the origin. This extended case can be led back to the base case by introducing the extended vectors ${\textstyle {\bf {x}}^{*}=({\bf {x}},1)^{T}}$ and ${\textstyle {\bf {w}}^{*}=({\bf {w}},b)^{T}}$ leading to the equivalent description

$${\hat {y}}={\bf {w}}^{*T}{\bf {x}}^{*}.$$

An illustrating example with one-dimensional input values is shown in Figure 1.

Connection of linear regression with MSE to maximum likelihood estimation

Let ${\textstyle {\bf {z}}=(z_{1},\ldots ,z_{M})}$ be a sequence of samples taken from the underlying population producing independent samples, each of them from the same random variable ${\textstyle Z}$ with a likelihood function Fehler beim Parsen (Syntaxfehler): {\textstyle p(z|{\mbox{\boldmath$\theta$}})} from a known distribution family with unknown parameter vector Fehler beim Parsen (Syntaxfehler): {\textstyle {\mbox{\boldmath$\theta$}}} . The likelihood function equals to the probability (mass) function and the probability density function (pdf) for discrete and continuous distribution, respectively. The Maximum Likelihood Estimation (ML estimation or MLE) of the parameter vector ${\textstyle {\bf {\theta }}}$ is the value, which maximizes the probability of the observed sequence of samples. In other words

Fehler beim Parsen (Syntaxfehler): {\displaystyle {\mbox{\boldmath$\theta$}}_{ML} = \arg \max_{{\mbox{\boldmath$\theta$}}} p({\bf z}|{\mbox{\boldmath$\theta$}}) = \arg \max_{{\mbox{\boldmath$\theta$}}} p(z_1,\ldots,z_M|{\mbox{\boldmath$\theta$}}) = \arg \max_{{\mbox{\boldmath$\theta$}}} \prod_{m=1}^{M} p(z_m|{\mbox{\boldmath$\theta$}}),}

where we utilized that the samples are taken independently from the same random variable ${\textstyle Z}$.

The product over more likelihoods can cause numerical issues, like e.g. numerical underflow. Therefore it is usual to use the logarithm of the likelihood instead of the likelihood. This modification does not cause any change in argmax and max, since the logarithm function is monotone. This gives the usual form of the ML estimate of the parameter vector ${\textstyle {\bf {\theta }}}$ as

Fehler beim Parsen (Syntaxfehler): {\displaystyle {\mbox{\boldmath$\theta$}}_{ML} = \arg \max_{{\mbox{\boldmath$\theta$}}} log \left( \prod_{m=1}^{M} log p(z_m|{\mbox{\boldmath$\theta$}})\right) = \arg \max_{{\mbox{\boldmath$\theta$}}}\sum_{m=1}^{M} log p(z_m|{\mbox{\boldmath$\theta$}}).}

Applying the principle of MLE to a conditional likelihood function ${\textstyle p(y|{\bf {x}})}$, the conditional likelihood function from a known distribution family with unknown parameter vector Fehler beim Parsen (Syntaxfehler): {\textstyle {\mbox{\boldmath$\theta$}}} becomes Fehler beim Parsen (Syntaxfehler): {\textstyle p(y|{\bf x}, {\mbox{\boldmath$\theta$}})} . Thus the ML estimate of the parameter vector ${\textstyle {\bf {\theta }}}$ in such case is given by

Fehler beim Parsen (Syntaxfehler): {\displaystyle {\mbox{\boldmath$\theta$}}_{ML} = \arg \max_{{\mbox{\boldmath$\theta$}}}\sum_{k=1}^{K} log~ p(y_k|{\bf x}_k, {\mbox{\boldmath$\theta$}}).}

Now we select the normal distribution as the known distribution family and set the mean of the distribution to be the predicted output value, ${\textstyle {\hat {y}}}$ and the variance of the distribution to a fixed value ${\textstyle \sigma ^{2}}$. Then the conditional likelihood function, which in this case a conditional pdf, becomes Fehler beim Parsen (Syntaxfehler): {\textstyle p(y|{\bf x},{\mbox{\boldmath$\theta$}}) = N(y| \hat{y}({\bf x},{\bf w}),\sigma^2)} , where ${\textstyle N(y|\mu ,\sigma ^{2})}$ stands for the pdf of the normal distribution with mean ${\textstyle \mu }$ and variance ${\textstyle \sigma ^{2}}$. Applying the expression of the pdf of the normal distribution ${\textstyle N(y|\mu ,\sigma ^{2})={\frac {1}{{\sqrt {(}}2\pi \sigma ^{2})}}exp\left(-{\frac {1}{2}}{\frac {(y-\mu )^{2}}{\sigma ^{2}}}\right)}$, we get for the ML estimate of the predicted output values, ${\textstyle {\bf {\hat {y}}}}$

Fehler beim Parsen (Unbekannte Funktion „\hspace“): {\displaystyle \begin{aligned} {\bf \hat{y}} &&\hspace{-5mm}= \arg \max_{\bf \hat{y}}\sum_{k=1}^{K} log N(y_k| \hat{y_k}({\bf x_k},{\bf w}),\sigma^2)\nonumber \\ &&\hspace{-5mm} = \arg \max_{\bf \hat{y}}\sum_{k=1}^{K} log \left(\frac{1}{\sqrt(2 \pi \sigma^2)}exp\left(-\frac{1}{2} \frac{(y_k-\hat{y_k})^2}{\sigma^2} \right)\right) \nonumber \\ &&\hspace{-5mm}= \arg \max_{\bf \hat{y}} \left(-K log \sigma -\frac{K}{2} log(2 \pi) - \sum_{k=1}^{K} \frac{(y_k-\hat{y_k})^2}{2\sigma^2} \right) = \arg \max_{\bf \hat{y}} \left(-\sum_{k=1}^{K} ((y_k-\hat{y_k})^2\right) \nonumber \\ &&\hspace{-5mm}= \arg \min_{\bf \hat{y}} \sum_{k=1}^{K} ((y_k-\hat{y_k})^2 = \arg \min_{\bf \hat{y}} \lVert {\bf \hat{y}} - {\bf y} \rVert_2^2 \nonumber. \end{aligned}}

Assuming the linear relation among ${\textstyle {\hat {y}}}$ and ${\textstyle {\bf {x}}}$ as ${\textstyle {\bf {\hat {y}}}={\bf {X}}{\bf {w}}}$, the above optimization with respect to ${\textstyle {\bf {w}}}$ results in the same estimation for ${\textstyle {\bf {w}}}$ as minimizing the MSE. Consequently the minimizing MSE can be seen as a ML estimation, which justifies the use of MSE due to the desirable properties of the ML estimation.

Klassifikation - Bayesian decision theory

Bayesian decision theory is a fundamental probabilistic approach to the task of classification. This approach uses probabilistic arguments and losses associated to decisions.

Bayes decision rule - with minimizing the error probability

Let ${\textstyle c_{1}}$ and ${\textstyle c_{2}}$ be two classes, e.g. two types of see fishes, like herring and mackerel. Suppose that an observer watching fishes arriving along a conveyor belt tries to predict which type of fish is the next one. The arriving type of fishes is random. It can be assumed that there is a probability ${\textstyle P(c_{1})}$ that the next fish is herring and a probability ${\textstyle P(c_{2})=1-P(c_{1})}$ that the next fish is mackerel. These probabilities are called a priori probabilities (or priors) reflecting that they represent the only knowledge on the emergence of these types of fishes. Having only these probabilities available for the decision, it seems logical to use a decision rule: Decide ${\textstyle c_{1}}$ if ${\textstyle P(c_{1})>P(c_{2})}$ and otherwise decide ${\textstyle c_{2}}$. This decision rule makes sense if there is only one fish to decide about its type. However applying this rule for a sequence of fishes seems to be incorrect: although we know that both types of fishes appear, we always decide the next one to be the same type. On this way we introduce an error whose probability is always the smaller one among ${\textstyle P(c_{1})}$ and ${\textstyle P(c_{2})}$.

Fortunately in most of the practical situations we have not to make decisions with so little amount of informations. Let us assume that informations on several features of the fish types, like e.g. their length, weights, etc. are available in advance. These features can be measured for the next emerging fish and can be organized in a vector ${\textstyle {\bf {x}}\in \mathbb {R} ^{d}}$. Now we assume the more general case of having more ${\textstyle C}$ classes, ${\textstyle c_{1},\ldots ,c_{C}}$. The information on the features belonging to class ${\textstyle c_{i}}$ can be given by the class-conditional density function ${\textstyle p({\bf {x}}|c_{i})}$. Suppose that both the priori probabilities ${\textstyle P(c_{i})}$ and the class-conditional density function ${\textstyle p({\bf {x}}|c_{i})}$ are given. Then the probability of each class, taking into account the informations observed in the features can be given by the conditional probability of that class, given the observed values of features, ${\textstyle P(c_{i}|{\bf {x}})}$. This conditional probability can be expressed by means of the Bayes formula as

$$P(c_{i}|{\bf {x}})={\frac {p({\bf {x}}|c_{i})P(c_{i})}{p({\bf {x}})}}={\frac {p({\bf {x}}|c_{i})P(c_{i})}{\sum _{j=1}^{C}p({\bf {x}}|c_{j})P(c_{j})}}.$$

The probability ${\textstyle P(c_{i}|{\bf {x}})}$ is called posteriori probability (or posterior) reflecting the incorporation of the informations on the features into the probability. The likelihood ${\textstyle p({\bf {x}}|c_{i})}$ indicates that if the priors of the classes are equal then the class with the highest likelihood is the most likely to be the right class.

At this point it seems logical to establish the decision rule:
Decide ${\textstyle c_{i}}$ with ${\textstyle P(c_{i}|{\bf {x}})>P(c_{j}|{\bf {x}})}$ for every ${\textstyle j\neq i}$.
The expected value of the probability of error for this decision rule is given by

$$P(error)=\int _{\mathbb {R} ^{d}}P(error,{\bf {x}})d{\bf {x}}=\int _{\mathbb {R} ^{d}}P(error|{\bf {x}})p({\bf {x}})d{\bf {x}}.$$

Deciding class ${\textstyle c_{i}}$ with highest ${\textstyle P(c_{i}|{\bf {x}})}$ leads to error with probability ${\textstyle 1-P(c_{i}|{\bf {x}}}$, for which ${\textstyle 1-P(c_{i}|{\bf {x}}<1-P(c_{j}|{\bf {x}}}$ for every ${\textstyle j\neq i}$. Therefore Fehler beim Parsen (Syntaxfehler): {\textstyle 1 - P(c_i|{\bf x} = \min P(\mbox{~error~}|{\bf x} )} , i.e. this error is the minimal one, for the given ${\textstyle {\bf {x}}}$. It ensures that Fehler beim Parsen (Syntaxfehler): {\textstyle P(\mbox{~error~}|{\bf x} )} in the above integral is as small as possible and hence the integral and thus also ${\textstyle P(error)}$ is minimal. So the above decision rule minimizes the probability of error. In fact it is a Bayes decision rule with minimizing the probability of error.

The general Bayes decision rule

We would like to generalize the Bayes decision rule by introducing a loss function instead of the probability of error. The decision among the classes is performed by taking the action ${\textstyle \alpha _{i}}$, ${\textstyle i=1,\ldots ,A}$. However if the true class is ${\textstyle c_{j}}$ then we involve a loss ${\textstyle \lambda (\alpha _{i}|c_{j})}$. Hence the expected loss by taking the action ${\textstyle \alpha _{i}}$ is given by

$$R(\alpha _{i}|{\bf {x}})=\sum _{j=1}^{C}\lambda (\alpha _{i}|c_{j})P(c_{j}|{\bf {x}})$$

In the decision-theoretic terminology ${\textstyle R(\alpha _{i}|{\bf {x}})}$ is called as conditional risk. Let ${\textstyle \alpha ({\bf {x}})}$ be the decision function taking one of the ${\textstyle \alpha _{i}}$ actions for each ${\textstyle {\bf {x}}}$. The overall risk is given by

$$R=\int _{\mathbb {R} ^{d}}R(\alpha ({\bf {x}})|{\bf {x}})p({\bf {x}})d{\bf {x}}.$$

Te goal is to find the decision function which minimizes the overall risk. To achieve it the action must be taken for each ${\textstyle {\bf {x}}}$, which minimizes the conditional risk for that ${\textstyle {\bf {x}}}$. In other words take ${\textstyle \alpha _{i}}$ with ${\textstyle i=\arg \min _{i}R(\alpha _{i}|{\bf {x}})}$. This leads to Bayes decision rule (also called Bayes decision procedure):
To minimize the overall risk,

1. Compute the conditional risk
   $$R(\alpha _{i}|{\bf {x}})=\sum _{j=1}^{C}\lambda (\alpha _{i}|c_{j})P(c_{j}|{\bf {x}})$$
   for ${\textstyle i=1,\ldots ,A}$ and
2. Select the action ${\textstyle \alpha _{i}}$ for which ${\textstyle R(\alpha _{i}|{\bf {x}})}$ is minimum, in other words select ${\textstyle \alpha _{i}}$ with ${\textstyle i=\arg \min _{i}R(\alpha _{i}|{\bf {x}})}$.

The overall risk resulted by applying the Bayes decision rule gives the Bayes risk, denoted by ${\textstyle R^{*}}$, which is the achievable lowest risk.

The general case with two classes

Let us ${\textstyle \alpha _{1}}$ and ${\textstyle \alpha _{2}}$ be interpreted as deciding class ${\textstyle c_{1}}$ and ${\textstyle c_{2}}$, respectively. This enables the simplified notation ${\textstyle \lambda _{i,j}=\lambda (\alpha _{i}|c_{j})}$, ${\textstyle i,j=1,2}$. The conditional risk for ${\textstyle \alpha _{1}}$ and ${\textstyle \alpha _{2}}$ can be given as

Fehler beim Parsen (Unbekannte Funktion „\hspace“): {\displaystyle \begin{aligned} &&\hspace{-5mm} R(\alpha_1|{\bf x}) = \lambda_{1,1} P(c_1|{\bf x}) + \lambda_{1,2} P(c_2|{\bf x}), \nonumber \\ &&\hspace{-5mm} R(\alpha_2|{\bf x}) = \lambda_{2,1} P(c_1|{\bf x}) + \lambda_{2,2} P(c_2|{\bf x}). \nonumber \end{aligned}}

The Bayes decision rule becomes

Fehler beim Parsen (Syntaxfehler): {\displaystyle \mbox{~Decide~} c_1 \mbox{~if~} R(\alpha_1|{\bf x}) < R(\alpha_2|{\bf x}), \mbox{~otherwise~} c_2.}

In terms of posteriori probabilities this becomes Fehler beim Parsen (Syntaxfehler): {\displaystyle \mbox{~Decide~} c_1 \mbox{~if~} (\lambda_{2,1} - \lambda_{1,1}) P(c_1|{\bf x}) > (\lambda_{1,2} - \lambda_{2,2}) P(c_2|{\bf x}), \mbox{~otherwise~} c_2.}

Usually making error should lead to higher loss, which means that both ${\textstyle (\lambda _{2,1}-\lambda _{1,1})}$ and ${\textstyle (\lambda _{1,2}-\lambda _{2,2})}$ are positive.

The above inequality can be rearranged by applying Bayes rule in it, which gives ${\textstyle (\lambda _{2,1}-\lambda _{1,1})p({\bf {x}}|c_{1})P(c_{1})>(\lambda _{1,2}-\lambda _{2,2})p({\bf {x}}|c_{2})P(c_{2})}$. Hence the Bayes decision rule can be alternatively formulated as Fehler beim Parsen (Syntaxfehler): {\displaystyle \mbox{~Decide~} c_1 \mbox{~if~} \frac{p({\bf x}|c_1 )}{p({\bf x}|c_2 )} > \frac{(\lambda_{1,2} - \lambda_{2,2}}{\lambda_{2,1} - \lambda_{1,1}} \frac{P(c_2)}{P(c_1)}, \mbox{~otherwise~} c_2.}

The quantities ${\textstyle p({\bf {x}}|c_{i})}$ are likelihoods, which enables to interpret this Bayes decision rule as deciding ${\textstyle c_{1}}$ if the likelihood ratio ${\textstyle {\frac {p({\bf {x}}|c_{1})}{p({\bf {x}}|c_{2})}}}$ exceeds some ${\textstyle {\bf {x}}}$ independent threshold.

Criteria for specific Bayes decision rules - minimum error-rate classification

From now on ${\textstyle \alpha _{i}}$ is interpreted as deciding class ${\textstyle c_{i}}$ and the simplified notation ${\textstyle \lambda _{i,j}=\lambda (\alpha _{i}|c_{j})}$ is enabled. Let us consider the loss given by the symmetrical or zero-one loss function:

Fehler beim Parsen (Unbekannte Funktion „\begin{array}“): {\displaystyle \begin{aligned} \lambda_{i,j} = \left\{ \begin{array}{l} 0, \mbox{~if~} i=j \\ 1, \mbox{~if~} i \neq j \end{array} \right\}, ~i,j = 1, \ldots, C. \nonumber \end{aligned}}

This loss function assigns 0 loss to correct decision and a unit loss to any erroneous decisions, i.e. all errors are equally punished. Thus this loss function can be seen as a function indicating the errors. The conditional risk is given by

$$R(\alpha _{i}|{\bf {x}})=\sum _{j=1}^{C}\lambda _{i,j}P(c_{j}|{\bf {x}})=\sum _{j\neq i}P(c_{j}|{\bf {x}})=1-P(c_{i}|{\bf {x}}),$$

which is exactly the probability of error, i.e. the error rate. Minimizing the probability of error is equivalent to maximizing the posteriori probability. Therefore the Bayes decision rule minimizing the conditional risk gives the decision rule

Fehler beim Parsen (Syntaxfehler): {\displaystyle \mbox{~Decide~} c_1 \mbox{~if~} P(c_1|{\bf x}) > P(c_2|{\bf x}) , \mbox{~otherwise~} c_2.}

This is the Bayes decision rule with minimizing the error rate, i.e. the error probability, which we already introduced before. Hence this logical decision rule corresponds to select the loss function being the zero-one function indicating the errors.

Criteria for specific Bayes decision rules - minimax criterion

The principle of minimax criterion will be shown for the classification with two classes. We show that the overall risk is a linear function of the prior, i.e. it is linear in e.g. ${\textstyle P(c_{1})}$. Let ${\textstyle {\mathcal {R}}_{1}}$ and ${\textstyle {\mathcal {R}}_{2}}$ the (unknown) region, where the classifier decides ${\textstyle c_{1}}$ and ${\textstyle c_{2}}$, respectively. It enables to express the overall risk in terms of the conditional risks as

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{aligned} R &&\hspace{-5mm}= \int_{\mathcal{R}_1} \left( \lambda_{1,1} P(c_1) p({\bf x}|c_1 ) + \lambda_{1,2} P(c_2) p({\bf x}|c_2 )\right) d{\bf x} \nonumber \\ &&\hspace{-5mm}+ \int_{\mathcal{R}_2} \left( \lambda_{2,1} P(c_1) p({\bf x}|c_1 ) + \lambda_{2,2} P(c_2) p({\bf x}|c_2 )\right) d{\bf x}. \nonumber \end{aligned}}

Using the relations ${\textstyle P(c_{2})=1-P(c_{1})}$ and ${\textstyle \int _{{\mathcal {R}}_{1}}p({\bf {x}}|c_{i})d{\bf {x}}+\int _{{\mathcal {R}}_{2}}p({\bf {x}}|c_{i})d{\bf {x}}=1}$, for ${\textstyle i=1,2}$ the above expression of the overall risk can be rearranged as

Fehler beim Parsen (Unbekannte Funktion „\hspace“): {\displaystyle \begin{aligned} R &&\hspace{-5mm}= \lambda_{1,1} P(c_1) \left(1- \int_{\mathcal{R}_2} p({\bf x}|c_1 ) d{\bf x} \right) + \lambda_{1,2} \left(1-P(c_1)\right) \int_{\mathcal{R}_1} p({\bf x}|c_2 ) d{\bf x} \nonumber \\ &&\hspace{-5mm}+ \lambda_{2,1} P(c_1) \int_{\mathcal{R}_2} p({\bf x}|c_1 ) d{\bf x} + \lambda_{2,2} \left(1- P(c_1)\right) \left(1 - \int_{\mathcal{R}_1} p({\bf x}|c_2 ) d{\bf x} \right) \nonumber \\ &&\hspace{-5mm}= \lambda_{2,2} + \left(\lambda_{1,2}-\lambda_{2,2}\right) \int_{\mathcal{R}_1} p({\bf x}|c_2 ) d{\bf x} \nonumber \\ &&\hspace{-5mm}+ P(c_1) \bigg(\left(\lambda_{1,1}-\lambda_{2,2}\right) + \left(\lambda_{2,1}-\lambda_{1,1}\right) \int_{\mathcal{R}_2} p({\bf x}|c_1 ) d{\bf x} - \left(\lambda_{1,2}-\lambda_{2,2}\right) \int_{\mathcal{R}_1} p({\bf x}|c_2 ) d{\bf x}\bigg). \nonumber \end{aligned}}

Therefore the overall risk usually depends on the prior ${\textstyle P(c_{1})}$ on linear way. Sometimes it is necessary to have a classifier, which performs well over a range of prior probabilities. This is the situation for example if the priori probabilities of the types of fishes arriving along a conveyor belt vary or we do not know the priori probabilities at all. Such a classifier can be designed by setting the coefficient of ${\textstyle P(c_{1})}$ in the above expression of the overall risk to ${\textstyle 0}$, i.e. by setting
${\textstyle {\bigg (}\left(\lambda _{1,1}-\lambda _{2,2}\right)+\left(\lambda _{2,1}-\lambda _{1,1}\right)\int _{{\mathcal {R}}_{2}}p({\bf {x}}|c_{1})d{\bf {x}}-\left(\lambda _{1,2}-\lambda _{2,2}\right)\int _{{\mathcal {R}}_{1}}p({\bf {x}}|c_{2})d{\bf {x}}{\bigg )}=0}$,
in which case the overall risk becomes independent of the prior ${\textstyle P(c_{1})}$. This setting is called the minimax solution and the resulted overall risk ${\textstyle \lambda _{2,2}+\left(\lambda _{1,2}-\lambda _{2,2}\right)\int _{{\mathcal {R}}_{1}}p({\bf {x}}|c_{2})d{\bf {x}}}$ is the minimax risk. It can be seen that the resulted risk is the maximum among the prior dependent Bayes risks (=minimum risks besides given prior), which explains the name minimax for this criterion.

Estimation of the posteriors

The design of a classifier based on Bayes decision rule requires the knowledge of the posteriori probabilities ${\textstyle P(c_{i}|{\bf {x}})}$, for ${\textstyle i=1,ldots,C}$, which are determined by the priors ${\textstyle P(c_{i})}$ and the likelihoods ${\textstyle p({\bf {x}}|c_{i})}$. Usually the likelihoods are computed by applying parametric statistic estimations, in which the distribution family is assumed to be either unimodal (like e.g. the multivariate normal density) or multimodal.

Klassifikation - lineare Diskriminanzfunktionen

General discriminant functions

A general way of representing a classifier is to specify it by a set of discriminant functions ${\textstyle d_{i}({\bf {x}})}$, for ${\textstyle i=1,ldots,C}$. The classifier decides to assign the class ${\textstyle c_{i}}$ to the input feature vector ${\textstyle {\bf {x}}}$, if

Fehler beim Parsen (Syntaxfehler): {\displaystyle d_i({\bf x}) > d_j({\bf x}) \mbox{~for~all~} j \neq i.}

The Bayes classifier can be also represented by means of discriminant functions. In general case the discriminant functions can be mapped as

$$d_{i}({\bf {x}})=-R(\alpha _{i}|{\bf {x}}).$$

The maximal among the ${\textstyle C}$ discriminant functions determines the class with the minimum conditional risks. A still simpler discriminant function can be given for the minimum error-rate classifier as

$$d_{i}({\bf {x}})=P(c_{i}|{\bf {x}}).$$

This can be further simplified by utilizing that the denominator of ${\textstyle P(c_{i}|{\bf {x}})={\frac {p({\bf {x}}|c_{i})P(c_{i})}{\sum _{j=1}{C}p({\bf {x}}|c_{j})P(c_{j})}}}$ is independent of ${\textstyle i}$, which leads to alternative discriminant function as

$$d_{i}({\bf {x}})=p({\bf {x}}|c_{i})P(c_{i})).$$

Any monotone function can be applied to discriminant functions, since it does not change the class belonging to the maximal one. Therefore a further discriminant function can be defined for the minimum error-rate classifier by the help of the monotone ${\textstyle ln()}$ function as

$$d_{i}({\bf {x}})=lnp({\bf {x}}|c_{i})+lnP(c_{i})).$$

In this case all the above different discriminant functions define the same decision rule. The discriminant functions divide the feature space into disjunct decision regions ${\textstyle {{\mathcal {R}}_{1}},\ldots ,{{\mathcal {R}}_{C}}}$. A feature vector ${\textstyle {\bf {x}}}$ falls into the decision region ${\textstyle {{\mathcal {R}}_{i}}}$ if ${\textstyle d_{i}({\bf {x}})>d_{j}({\bf {x}})}$ for every ${\textstyle j\neq i}$. Thus decision region ${\textstyle {{\mathcal {R}}_{i}}}$ represents the set of feature vectors for which the classifier decides class ${\textstyle c_{i}}$. The decision regions are separated by decision boundaries in the ${\textstyle d}$-dimensional space of feature vectors.

In the special case of classifier with two classes it is common to use a single discriminant function

$$d({\bf {x}})=d_{1}({\bf {x}})-d_{2}({\bf {x}}).$$

instead of ${\textstyle d_{1}({\bf {x}})}$ and ${\textstyle d_{2}({\bf {x}})}$. Hence the decision rule becomes

Fehler beim Parsen (Syntaxfehler): {\displaystyle \mbox{~Decide~} c_1 \mbox{~if~} d({\bf x}) > 0 , \mbox{~otherwise~} c_2.}

Figure z.

Linear discriminant functions

In case of discriminant functions for Bayes classifier the form of the underlying probability distribution must be assumed to be known. However discriminant functions without such assumption can be also designed. Hence, in limited, statistical sense, the procedure of determining such discriminant functions can be seen as nonparametric. An important class of such discriminant functions are the linear discriminant functions.

Linear discriminant functions are linear in the components of ${\textstyle {\bf {x}}}$ and can be given as the linear combination of the components of ${\textstyle {\bf {x}}}$, in other words:

$$d({\bf {x}})={\bf {w}}^{T}{\bf {x}}+w_{0},$$

where ${\textstyle {\bf {w}}}$ is the weight vector and ${\textstyle w_{0}}$ is the bias or threshold weight. The decision boundary becomes a decision surface.

For the case of classifier with two classes there is only one discriminant function, ${\textstyle d({\bf {x}})={\bf {w}}^{T}{\bf {x}}+w_{0}}$. The class ${\textstyle c_{1}}$ will be decided, if ${\textstyle {\bf {w}}^{T}{\bf {x}}}$ exceeds the threshold ${\textstyle -w_{0}}$, and the class ${\textstyle c_{2}}$ otherwise.

The principle of the operation of the linear classifier with two classes and d-dimensional feature vector is shown in Figure w1.

Figure w1.

The decision surface is a hyperplane. Let us consider two feature vectors ${\textstyle {\bf {x}}_{1}}$ and ${\textstyle {\bf {x}}_{2}}$ both on the decision surface. Then ${\textstyle d({\bf {x}}_{1})=0=d({\bf {x}}_{2})}$ holds, which means ${\textstyle {\bf {w}}^{T}{\bf {x}}_{1}+w_{0}={\bf {w}}^{T}{\bf {x}}_{2}+w_{0}}$, from which

$${\bf {w}}^{T}\left({\bf {x}}_{1}-{\bf {x}}_{2}\right)=0.$$

It follows that ${\textstyle {\bf {w}}}$ is perpendicular to any vector lying on the decision feature and hence the decision surface is a hyperplane with ${\textstyle {\bf {w}}}$ as normal vector.

The discriminant function ${\textstyle d({\bf {x}})}$ has a strong connection to the signed distance of ${\textstyle {\bf {x}}}$ to the hyperplane, ${\textstyle r}$. This can be seen by expressing ${\textstyle {\bf {x}}}$ as the sum of its projection to the hyperplane ${\textstyle {\bf {x}}_{p}}$ and ${\textstyle r}$ times the unit vector in the direction of ${\textstyle {\bf {w}}}$, i.e.

$${\bf {x}}={\bf {x}}_{p}+r{\frac {\bf {w}}{\lVert {\bf {w}}\rVert }}.$$

Using ${\textstyle d({\bf {x}}_{p})=0}$, for ${\textstyle d({\bf {x}})}$ we get

$$d({\bf {x}})={\bf {w}}^{T}{\bf {x}}_{p}+{\bf {w}}^{T}r{\frac {\bf {w}}{\lVert {\bf {w}}\rVert }}+w_{0}=d({\bf {x}}_{p})+r{\frac {\lVert {\bf {w}}\rVert ^{2}}{\lVert {\bf {w}}\rVert }}=r\lVert {\bf {w}}\rVert ,$$

from which

$$r={\frac {d({\bf {x}})}{\lVert {\bf {w}}\rVert }}.$$

The normal vector ${\textstyle {\bf {w}}}$ points into the decision region ${\textstyle {{\mathcal {R}}_{1}}}$, since ${\textstyle d({\bf {x}})>0}$ and thus ${\textstyle {\bf {w}}}$ points to the same side of the hyperplane as ${\textstyle {\bf {x}}}$, if ${\textstyle {\bf {x}}\in {{\mathcal {R}}_{1}}}$.

The distance of the origin to the hyperplane is ${\textstyle {\frac {w_{0}}{\lVert {\bf {w}}\rVert }}}$. The origin falls into the decision region ${\textstyle {{\mathcal {R}}_{1}}}$ if ${\textstyle w_{0}>0}$ and into ${\textstyle {{\mathcal {R}}_{2}}}$ if ${\textstyle w_{0}<0}$. If ${\textstyle w_{0}=0}$, then the hyperplane passes through the origin and linear discriminant function ${\textstyle d({\bf {x}})}$ has homogeneous form ${\textstyle d({\bf {x}})={\bf {w}}^{T}{\bf {x}}}$.

The above properties are illustrated geometrically on Figure w2.

Figure w2

For the general case of classifier with ${\textstyle C}$ classes, the linear discriminant functions are given as

$$d({\bf {x}})_{i}={\bf {w}}_{i}^{T}{\bf {x}}+w_{i0},$$

The decision rule is the same as the one for the general discriminant functions

Fehler beim Parsen (Syntaxfehler): {\displaystyle \mbox{~Decide~} c_i \mbox{~if~} d_i({\bf x}) > d_j({\bf x}) \mbox{~for~all~} j \neq i.}

In case of the values of two ore more discriminant functions being the same for some ${\textstyle {\bf {x}}}$, which is called ties (like in statistics), the decision is undefined. The classifier with ${\textstyle C}$ linear discriminant functions is also called as linear machine. It divides the d-dimensional feature space into ${\textstyle C}$ disjunct decision regions. For the boundary between two neighborous decision regions ${\textstyle {{\mathcal {R}}_{i}}}$ and ${\textstyle {{\mathcal {R}}_{j}}}$ holds ${\textstyle d({\bf {x}})_{i}=d({\bf {x}})_{j}}$, or equivalently

$$\left({\bf {w}}_{i}-{\bf {w}}_{j}\right)^{T}{\bf {x}}+\left(w_{i0}-w_{j0}\right)=0.$$

It follows from the considerations done for classifier with two classes that the boundary is a hyperplane with normal vector ${\textstyle \left({\bf {w}}_{i}-{\bf {w}}_{j}\right)}$. Furthermore the signed distance of ${\textstyle {\bf {x}}}$ to this hyperplane is given as ${\textstyle {\frac {d_{i}({\bf {x}})-d_{j}({\bf {x}})}{\lVert {\bf {w}}_{i}-{\bf {w}}_{j}\rVert }}}$. These expressions show that in linear machine the differences of the weights are important, not the weights itself. The total number of hyperplanes can be less than the ${\textstyle {\frac {C(C-1)}{2}}}$ possible number of pairs. It can be shown that the decision regions in ${\textstyle {\bf {x}}}$ are convex.

Generalized linear discriminant functions are linear in some given functions of ${\textstyle {\bf {x}}}$ and have a form as

$$d({\bf {x}})=\sum _{i=1}^{d}{\bf {a}}_{i}{\bf {y}}_{i}({\bf {x}}).$$

Truncated serial expansions of ${\textstyle d({\bf {x}})}$ with any ${\textstyle {\bf {y}}_{i}}$-s lead to polynomial discriminant functions as subclass of generalized linear discriminant functions. An example is the quadratic discriminant function, which can be given in the form

$$d({\bf {x}})=w_{0}+\sum _{i=1}^{d}{\bf {w}}_{i}{\bf {x}}_{i}+\sum _{i=1}^{d}\sum _{j=1}^{d}{\bf {w}}_{ij}{\bf {x}}_{i}{\bf {x}}_{j}.$$

Besides of the decision regions in ${\textstyle {\bf {y}}}$ being convex, they can have any dependency in ${\textstyle {\bf {x}}}$. Hence generalized linear discriminant functions can describe more general feature spaces, which is their beneficial property providing motivation to use them.

Finding linear discriminant functions

The parameters of the classifier with linear discriminant functions are the weights. Thus training the parameters of the classifier means to find proper linear discriminant functions. This is done by formulating the task as an optimization. A natural choice for the criterion of the optimization is to minimize the training error. To perform such minimization in a general settings, well-known numerical multivariate optimization algorithms, like e.g. gradient methods are used and adopted to the specialities of finding linear discriminant functions.

Lernen aus Beispiele Learning from examples is a fundamental approach in machine learning. The goal is to build up knowledge from examples by training a statistical model, which represent the knowledge also for unseen examples. On this way the statistical model represents a generalization of the knowledge extracted from the examples. In some contexts such learning is called also training.

The classical form of such learning assumes providing the correct output for the input in each example. It is usual to say to have labelled training set, which means that the in each example the input is labelled by the correct output. This type of learning is called supervised learning.

Example - estimation of the transition probability matrix of a DTMC (Beispiel: Schätzung der Übergangswahrscheinlichkeiten einer DTMC (mittels des Verfahrens der Lagrange-Multiplikatoren)) As an example for learning from examples we provide the estimation of the transition probability matrix of a DTMC from observed state sequences.

The model

Let ${\textstyle {\mathcal {S}}={s_{1},\ldots ,s_{|{\mathcal {S}}|}}}$ be the set of states of the DTMC. Furthermore let ${\textstyle {\overrightarrow {\bf {z}}}=(z_{0},z_{1},\ldots ,z_{T})}$ denote observed state sequence. The transition probability matrix of the DTMC is denoted by ${\textstyle {\bf {A}}}$, i.e. ${\textstyle {\bf {A}}_{i,j}=P(z_{t}=s_{j}|z_{t-1}=s_{i})}$ for ${\textstyle s_{i},s_{j}\in {\mathcal {S}}}$. Observe that a given state sequence ${\textstyle {\overrightarrow {\bf {z}}}}$ implicitly includes many labelled examples in the form ${\textstyle ..z_{t-1},z_{t}..}$, where the input is ${\textstyle z_{t-1}}$ and the next state ${\textstyle z_{t}}$ gives the corresponding correct output.

Problem formulation The task of estimating of the parameter matrix ${\textstyle {\bf {A}}}$ can be formulated as an optimization problem as

$${\bf {A}}^{*}=\arg \max _{\bf {A}}P({\overrightarrow {\bf {z}}}|{\bf {A}}),$$

where ${\textstyle {\bf {A}}^{*}}$ is the estimated parameter matrix. We are going to estimate the parameter matrix${\textstyle {\bf {A}}^{*}}$ by applying the Maximum-Likelihood statistical point estimation method. Therefore we maximize the log likelihood of ${\textstyle {\overrightarrow {\bf {z}}}|{\bf {A}}}$, which has maximum at the same point, where the likelihood.

By omitting the condition to get simpler notation, the log likelihood ${\textstyle logP({\overrightarrow {\bf {z}}})}$ can be expressed as

Fehler beim Parsen (Unbekannte Funktion „\hspace“): {\displaystyle \begin{aligned} log P(\overrightarrow{\bf z})&&\hspace{-5mm}= P(z_1,\ldots,z_T) = log P(z_T|z_{T-1},\ldots, z_1)P(z_{T-1}|z_{T-2},\ldots, z_1) \ldots P(z_1|z_0) P(z_0) \nonumber \\ &&\hspace{-5mm}= log P(z_T|z_{T-1}) P(z_{T-1}|z_{T-2})\ldots P(z_1|z_0)P(z_0) = log \prod_{t=1}^{T}P(z_{t}|z_{t-1}) P(z_0) \nonumber \\ &&\hspace{-5mm}= \prod_{t=1}^{T}{\bf A}_{z_{t-1},z_{t}}P(z_0) = \sum_{t=1}^{T} log {\bf A}_{z_{t-1},z_{t}} + log P(z_0), \nonumber \end{aligned}} where we used the multiplication theorem in the first and the Markov property in the second equality.

This can be further rearranged by introducing an indicator variable as

$$logP({\overrightarrow {\bf {z}}})=\sum _{i=1}^{|{\mathcal {S}}|}\sum _{j=1}^{|{\mathcal {S}}|}\sum _{t=1}^{T}1_{z_{t-1}=s_{i},z_{t}=s_{j}}log{\bf {A}}_{i,j}+logP(z_{0}).$$

Omitting the term ${\textstyle logP(z_{0})}$ does not influence the place of maximum of the log likelihood, since it does not depend on matrix ${\textstyle {\bf {A}}}$. Furthermore some constraints on matrix ${\textstyle {\bf {A}}}$ must be taken into account in the optimization. Matrix ${\textstyle {\bf {A}}}$ is stochastic and hence 1. ${\textstyle {\bf {A}}_{i,j}\neq 0}$, i.e. the elements of matrix ${\textstyle {\bf {A}}}$ are non-negative, 2. ${\textstyle \sum _{j=1}^{|{\mathcal {S}}|}{\bf {A}}_{i,j}=1}$ for ${\textstyle i=1,\ldots ,|{\mathcal {S}}|}$, i.e. the row sums of matrix ${\textstyle {\bf {A}}}$ are equal to 1.

We are going to apply the method of Lagrange multiplicator for the optimization. It ensures that the non-negativity of the resulted matrix ${\textstyle {\bf {A}}}$. Therefore the task can be formulated as the following constrainted optimization problem:

Fehler beim Parsen (Syntaxfehler): {\displaystyle \arg\max_{{\bf A}} \sum_{i=1}^{|\mathcal{S}|}\sum_{j=1}^{|\mathcal{S}|}\sum_{t=1}^{T} 1_{z_{t-1} = s_i, z_{t} = s_j} log {\bf A}_{i,j}, ~ \mbox{~subject~to~}~\sum_{j=1}^{|\mathcal{S}|} {\bf A}_{i,j} = 1, \mbox{~for~} i = 1, \ldots, |\mathcal{S}|.}

Solution by applying the method of Lagrange multiplier

Applying the method of Lagrange multiplicator requires the introduction of |S| Lagrange multipliers, ${\textstyle \alpha _{i}}$ for ${\textstyle i=1,\ldots ,|{\mathcal {S}}|}$, which can be arranged in a vector Fehler beim Parsen (Syntaxfehler): {\textstyle {\mbox{\boldmath$\alpha$}}} . Thus the Lagrange function can be given as

Fehler beim Parsen (Syntaxfehler): {\displaystyle \mathcal{L}({\bf A}, {\mbox{\boldmath$\alpha$}}) = \sum_{i=1}^{|\mathcal{S}|}\sum_{j=1}^{|\mathcal{S}|}\sum_{t=1}^{T} 1_{z_{t-1} = s_i, z_{t} = s_j} log {\bf A}_{i,j} + \sum_{i=1}^{|\mathcal{S}|} \alpha_i \left(1 - \sum_{j=1}^{|\mathcal{S}|} {\bf A}_{i,j} \right).}

Taking the first derivative of the Lagrange function with respect to ${\textstyle {\bf {A}}_{i,j}}$ and making equal to 0 yields

$${\frac {\partial {\mathcal {L}}}{\partial {\bf {A}}_{i,j}}}={\frac {1}{{\bf {A}}_{i,j}}}\sum _{t=1}^{T}1_{z_{t-1}=s_{i},z_{t}=s_{j}}-\alpha _{i}=0,~i,j=1,\ldots ,|{\mathcal {S}}|,$$

from which ${\textstyle {\bf {A}}_{i,j}}$ can be expressed as

$${\bf {A}}_{i,j}={\frac {1}{\alpha _{i}}}\sum _{t=1}^{T}1_{z_{t-1}=s_{i},z_{t}=s_{j}}~i,j=1,\ldots ,|{\mathcal {S}}|.$$

Now taking first derivative of the Lagrange function with respect to ${\textstyle \alpha _{i}}$, making equal to 0 and applying the above expression of ${\textstyle {\bf {A}}_{i,j}}$ yields

$${\frac {\partial {\mathcal {L}}}{\partial \alpha _{i}}}=1-\sum _{j=1}^{|{\mathcal {S}}|}{\bf {A}}_{i,j}=1-\sum _{j=1}^{|{\mathcal {S}}|}{\frac {1}{\alpha _{i}}}\sum _{t=1}^{T}1_{z_{t-1}=s_{i},z_{t}=s_{j}}=0,$$

from which we get the solution for ${\textstyle \alpha _{i}}$ as

$$\alpha _{i}=\sum _{j=1}^{|{\mathcal {S}}|}\sum _{t=1}^{T}1_{z_{t-1}=s_{i},z_{t}=s_{j}}=\sum _{t=1}^{T}1_{z_{t-1}=s_{i}}~i=1,\ldots ,|{\mathcal {S}}|.$$

Applying the final expression of ${\textstyle \alpha _{i}}$ in the expression of ${\textstyle {\bf {A}}_{i,j}}$, we get the for the estimate of ${\textstyle {\bf {A}}_{i,j}}$

$${\bf {A}}_{i,j}={\frac {\sum _{t=1}^{T}1_{z_{t-1}=s_{i},z_{t}=s_{j}}}{\sum _{t=1}^{T}1_{z_{t-1}=s_{i}}}}~i,j=1,\ldots ,|{\mathcal {S}}|.$$

This estimate of ${\textstyle {\bf {A}}_{i,j}}$ can be interpreted as the number of count of the transition ${\textstyle s_{i}-->s_{j}}$ divided by the number of count of ${\textstyle s_{i}}$, i.e. the count of observing the DTMC being in state ${\textstyle s_{i}}$. This estimate fits to the intuition.

Learning durch Steuereung - MDP Learning by means of control is an iterative process, in whose each step the actor reacts with an action to the environment’s answer to its previous action. Thus the actor learns its behaviour stepwise. Such process arise very often in the nature, e.g. as controlling the movement of animals during looking for some food.

Such learning process can be described by the mathematical model of Markov-Entscheidungsprozess (MEP) - Markov decision process (MDP). MDP is diskreter stochastischer Kontrollprozess. In each state ${\textstyle s}$ of the MDP, the actor can take an action ${\textstyle a}$, from the allowed set of actions at that state. It causes the MDP to move into the state ${\textstyle s^{'}}$ and giving a reward to the actor, which corresponds to the action and state transition, ${\textstyle R_{a}(s,s^{'})}$, both at the next time step. On such way the MDP realizes an action and reward-feedback based learning. The working flow of the MDP model is shown in Figure x.

Abbildung x

The mathematical definition of MDP is given as follows. MDP is a 4-tuple ${\textstyle ({\mathcal {S}},{\mathcal {A}},P,{\mathcal {R}})}$, where

• ${\textstyle {\mathcal {S}}}$ is the state space, i.e. set of states,
• ${\textstyle {\mathcal {A}}}$ is the action space, i.e. set of actions,
• ${\textstyle P}$, in function form ${\textstyle P_{a}(s,s^{'})=P(s(t+1)=s^{'}|s(t)=s,a(t)=a)}$ describes the state transition from ${\textstyle s}$ to ${\textstyle s^{'}}$ while the action ${\textstyle a}$ is taken and
• ${\textstyle {\mathcal {R}}}$ is the set of possible rewards, and ${\textstyle R_{a}(s,s^{'})}$ is the reward for the state transition from ${\textstyle s}$ to ${\textstyle s^{'}}$ when the action ${\textstyle a}$ is taken.

An example diagram of a MDP is shown in Figure y.

Abbildung y

MDP is an extension of the Discrete-Time Markov Chain (DTMC) by adding actions (allowing selection opportunities) and rewards (providing feedback for motivating) to it. It implies that an MDP with only one action and a common reward reduces to a DTMC. MDP can be used for solving optimization tasks and it is usually implemented by dynamic programming.

CI

Computational Intelligence (CI) is subarea of AI covering biologically motivated and hence computationally intensive methodologies and approaches.

Definition von CI

There is no commonly accepted unique definition of CI. The first definition origins from 1994 by Bezdek (see in ) and defines CI as having all of the following merkmalen:

• deals with numerical data,
• has a pattern-recognition component instead of represented knowledge,
• has computational adaptive and fault tolerance methodology and
• approximates human like performance in terms of speed and error-rate.

CI can be also defined by means of its major characteristics:

• a sub-field in KI,
• a set of nature-inspired approaches,
• addresses complex real-world problems, which may contain some uncertainties or might have stochastic nature.

Positionierung von CI gegenüber KI und seiner Geschichte zur Geschichte der KI

CI and KI both have the long-term goal of reaching general intelligence. However KI is based on hard computing techniques following binary logic having two values, the binary 0 or 1. This can be interpreted as an element in a set is either included or not. On the contrary CI is based on soft computing techniques following fuzzy logics, which enables real values between 0 and 1, which can be seen as a degree of membership an element in a set. This is a clear difference between KI and CI. On the other hand CI can be seen as a sub-area of KI in a broader sense.

While the history of KI began already in the 1950s, the term CI was first used in 1990 by the IEEE Neural Networks Council dealing with development of biological and artificial neural networks. In 2001 the Council became IEEE Computational Intelligence Society and several years later new areas such as fuzzy systems and evolutionary computation have been included into the area of interest of the society.

Hauptkomponenten der CI

The major components of CI are given as

1. Artificial Neural Networks based on the biological ones, which
   • enable processing and learning from experiential data and
   • provide fault tolerance in some extent.
2. Fuzzy logic being one of the major discipline of CI, which
   • enable soft computing techniques for modelling real-life complex processes by applying probabilistic methods and
   • can be applied for approximate reasoning, but not for learning.
3. Evolutionary computation (EC) providing algorithms (Evolutionary Algorithms -EA) for global optimization, which
   • are inspired by biological evolution
   • usually based on a population of candidate solutions

Evolutionäre Algorithmen (EA)

In this subsection we give the brief mathematical descriptions of the two most broadly known and applied EA algorithm: Optim book + Pattern rec book

• Particle Swarm Optimisations (PSO) and
• Genetic Algorithms.

Partikelschwarmoptimierungen - Particle Swarm Optimisations (PSO)

Genetischer Algorithmus - Genetic Algorithms (+ Programming ?)

Anwendungsgebiete von AI

Anwendungen von KG

In this subsection we discuss the applications of the KG.

(1) Information retrieval (IR) systems include tasks like - image retrieval, - music retrieval, - web search, - domain-specific retrieval (e.g. geographic, legal,..), - cross-lingual retrieval and - text summarization (mainly as extracted parts of the original text).

(2) Semantic search is realized by integrating KG into the results of the search engine. This leads to improved ,,Big Data“ search engine. It extends the conventional search engine with the following new features - offer more relevant information, - identify and disambiguate entities in text, - provide links to related entities (exploratory search). Examples include - Google search engine implemented via integrating Google’s KG, - Bing, the Microsoft search engine realized via integrating the Microsoft’s KB Satori.

(3) Question Answering System (QA) incorporate semantic info from KG in order to enhance search result for semantic question. Therefore they provide semantically aware question answering services. Examples include - Watson, the IBM’s QA system, which uses among others YAGO, DBpedia and Freebase, - Digital/virtual assistants like Siri, Cortana, Google Now The QA systems can be classified into extractive or generative QA systems. - In extractive QA the answer is extracted from context (BERT-like models). - In generative QA the model generates free text based on the context for which it uses Text Generation models. On the other hand the QA systems can be also classified as open or closed QA systems. - In open QA the answer is taken from context. - In closed QA there is no context provided and thus the answer is a completely generated one. The fast QA over many document works by inserting first ranking by using passge ranking models. There are QA datasets provided for academic benchmark tests. The most used QA datasets for academic benchmark of extractive QA systems is the Stanford Question Answering Dataset (SQuAD) consisting of 100000+ QA pairs on 500+ articles.

(4) Recommendation/Recommender System gives personalized recommendations based on user’s behaviour, common preferences and interests. Based on analysing user clicks, these content platforms can suggests another contents for users to view or read. In such applications KGs help to improve accuracy, increase diversity of recommended items and bring interpretability to recommendations. Typical examples of such KG applications are content platforms, like e.g. Netflix, Search Engine Optimization (SEO), which is ein Teilgebiet des Suchmaschinenmarketings, or social media.

(5) Natural Language Processing (NLP) addresses processing and understanding text and spoken speech by applying mainly machine learning techniques. Information extraction (IE) is a NLP technique targeting extraction of structured information from typically unstructured text. More precisely IE locates in the intersection of IR and NLP. There exists a mutually beneficial relationship between KG and NLP. On one hand KG is used to realize NLP techniques, like e.g. text summarization. But on the other hand NLP techniques, like (named) entity recognition and relation extraction, are used to create KG.

(6) Enterprise knowledge management is about applying KG in industrial sector in order to utilize the benefits provided by KG. This benefits include - applying big data in order to create new business value, - creating business viewpoints on different granularity levels, - providing new insights through hierarchical inclusion of company relevant data and - providing advanced accessibility of company information to employees.

(7) Domain-specific applications enable creating added value due to applying KG in different fields. - Biomedical KG applications enable question answering and decision support in the life sciences due to integrating multiple sources of biomedical information. - Medical application utilize KG for integrating textual medical knowledge. One such example is retrieving specific info via Schlussforgerung. - In cybersecurity applications KG is used to store modelling patterns in large datasets of transactions and organisations. This serves as a base for building applications, like e.g. detecting and predicting attacks, identifying potential frauds (=verschiedene Arten von Wirtschaftskriminalität) and identifying security threats via suspicious transactions, abnormal user behaviour or fake accounts. - In e-commerce applications KG is used to store semantic information about the interactions between customers and products, and their characteristics. These can be used for a variety of tasks including finding similar or compatible products, identifying product classes, retrieving relevant products for a given search term and retrieving similar search terms. - In financial applications KG is created by identifying named entities from news of companies and by extracting business links between relevant stocks. Such KGs are used for tasks like e.g. predicting stock’s price movement. - KG is used in the field of news to implement fake news detection. - In the field of education KG nodes are used to store instructional concepts, which are used in tasks like learning resource recommendation and concept visualisation. - In Geoscience applications KG stores the textual geoscience data used for information extraction and knowledge discovery services.

Anwendungen des MLs

ML is one of the technology which has many applications both commonly known ones and in a wide variety of Fachgebiets, including finance, healthcare, agriculture and many more.

In the following we give a brief descriptions of several commonly known applications.

Speech recognition is the process of converting the spoken speech into written n text. It is also called as speech to text (STT) or automatic speech recognition (ASR). Speech recognition or used e.g. in speech automated call centers, voice dialling (also called speech enabled dialling) or in Apple’s speech assistant Siri.

Speaker recognition (also called as voice recognition) is the task of identifying the speaker from a short (usually several seconds) speech.

Speech synthesis covers the task of converting written text into human speech. It is also called as text-to-speech (TTS) and it is the reverse task of the speech recognition.

Language translation, like e.g. Google Translate can translate written text in one language into the corresponding text in other language. It is based on Natural Language Processing(NLP) techniques including POS tagging and Named Entity Recognition (NER).

Image recognition is the task of identifying some pattern in an image or video. It can be used among others for face detection, face recognition or for further analysis.

Traffic pattern prediction. This task generates predictions about the upcoming traffic based on the actual one, which is used e.g. to identify and suggest the fastest route to the required destination.

Data mining has a goal of extracting information from a (usually large) data set and converting it into a structure, which is appropriate for further use. Data mining is applied e.g. by secret services or for outlier detection in the statistics.

E-commerce product recommendations. It is a marketing application generating product recommendations based on collected data on past customer behaviours, past shopping.

E-mail spam detection (email filtering) works by means of spam filters using ML algorithms for classifying the incoming e-mails being spam or not.

Malware detection is a pattern recognition system trained on features extracted by analysing suspicious activities.

Computer vision uses ML techniques to process, analyse, visualize or interpret high-dimensional real life data.

Transportation (Uber) uses ML to analyse traffic conditions in order to estimate the Estimated Time of Arrival (ETA) to the required Destination.

ML applied to business problems is also called as predictive analytics. Here we give short interpretations of several ML application examples in Finance.

• Stock Market and Day Trading. In this application ML is trained to predict the evolution of the prices in the stock market.
• Focused Account Holder Targeting. Here ML algorithms classify the account holders for segments with predefined balances and loans.
• Fraud Detection (in banking transactions) is implemented by ML algorithm giving a score for each transaction, which represents a probability of being a fraud. The training of the algorithm is based on patterns for unusual behaviour identified from large amount of transactional data. This is the most important use of ML in banking and finance area.
• Loan Eligibility Prediction is realized by different ML classifier (like e.g. Random Forest) to judge customers eligibility for being granted a loan.

As a next several applications of ML in Healthcare are shortly considered.

• In Personalized Treatment/Medication ML is used to identify patient gene patterns (=response markers) that could enable targeted therapies.
• In Genetics and Genomics ML is used to identify gene sequences in genome sequencing, gene modification and in general in genetic research.
• In Cancer Prognosis and Prediction (especially with ANNs) ML is used to construct prediction models to support decision on therapy and predict its evolution.
• In Drug development the process of drug discovery can be sped up by applying ML techniques.

Artificial Neural Networks (ANN) combine ML with NN model. The big majority of the applications has benefited from the usage of ANN instead of pure ML algorithms. These applications are e.g. image recognition, medical diagnosis, speech recognition, machine translation, computer vision, cancer prognosis and prediction, social network filtering, playing board and video games.

Embedded Machine Learning is a subfield of ML, in which ML is applied to embedded systems with limited resources. Such embedded systems include microcontrollers, wearable computers and edge devices. Using ML methods in embedded systems makes transferring and storing data on cloud servers unnecessary. Embedded Machine Learning techniques include among others approximate computing and hardware acceleration.

For more details on application of ML see e.g. the Wikipedia side .

Weitere Anwendungsgebiete von AI

Further application areas of AI include

1. Educational sector e.g. by creating automated messages to students, or by designing content based on the user’s interest (Smart Content Creation),
2. Robotics e.g. by making real time decisions possible based on NLP, Object Recognition and Human-Robotics Interaction (HRI),
3. Navigation e.g. by computing the best route based on GPS and AI technologies,
4. Healthcare e.g. by patient monitoring or surgical assistance,
5. Automobiles e.g. by Advanced Driving Assistance System (ADAS) or Autonomous Driving,
6. Agriculture e.g. by crops monitoring, supply chain maintenance or weather forecasting,
7. Human Resource e.g. by screening,
8. Lifestyle e.g. by Personalized Recommendation, Virtual Assistance,
9. Gaming e.g. by Animation,
10. Astronomy e.g. by Analysis of astronomical data and Detection e.g. of exoplanets,
11. Travel and Transport e.g. enabling Truck platooning,
12. Military e.g. by detecting Cyberattacks and Decision Support e.g. for resource allocation.

The feedback of recent development of NN to older AI concepts resulted in modern AI model combinations. Perhaps the two most important ones are the Neural Language Models and Large Language Models.

Neural Language Models (NLM) are LMs based on recurrent NN. They are also called as continuous space language models. They transform the LM representation of words into continuous low-dimensional vector space, called embedding space. This has the advantage of locating the semantically similar units closer to each other in the embedding space. Such units can be parts of corpus, sentences, sub-words or characters. Furthermore NLMs avoid the data sparsity problem of SLMs since they represent words as non-linear combinations of weights in a neural net . The NLMs can be categorized to be either Non-contextual Embeddings or Contextual Embeddings. Non-contextual Embeddings apply the same embeddings for a given semantic unit regardless of the given context. Examples of Non-contextual Embeddings include Word2Vec or Wikipedia2Vec . On the contrary Contextual Embeddings can represent different semantics of the semantic units in different context. Examples of Contextual Embeddings includes Bidirectional Encoder Representations from Transformers (BERT) introduced by Google or Sentence-BERT (SBERT), a fine-tuned version of BERT. The transformer model is a specific NN architecture introduced by Vaswani et al.

Large Language Models (LLM) are transformer NN based LMs, which are pre-trained using self-supervised learning, learn billions of parameters during training and need large computational resources for the training and during operation. They can achieve general-purpose language understanding and generate answer in the form of human-like generated text. These LLMs are used in generative AI systems. Recent versions can complete specific tasks prompt-engineered, i.e. providing a short structured description of the task that can be interpreted by the LLM. Most prominent examples are Open AI’s GPT-3.5 and GPT-4 model (used in ChatGPT) and Google’s PaLM (used in Bard).

Ethik in der KI

Ethik ist im allgemeinen eine Menge von moralischer Regeln und Leitfaden, die den Menschen helfen, zwischen Recht und Unrecht zu entscheiden. Es ist zu erwarten, das KI schon in der näheren Zukunft erhebliche Auswirkungen auf die ganze Menscheit und Welt haben wird. Deshalb ist es wichtig auf ethischen Fragen in Zusammenhang mit KI bedeutsam Aufmerksamkeit zu schenken.

In der vorigen Jahren haben Organisationen verschiedene Big Data Algoritmen und KI Lösungen eingesetzt meist um ihre Geschäftsergebnisse durch Automatisierung und datengesteuerte Entscheidungsfindung zu verbessern. Dabei wurden einige Unternehmen in Zusammenhang mit ihrer KI-Anwendungen mit unerwarteten negative Konsequenzen konfrontiert, insbesondere aufgrund unfairer Ergebnisse und durch Anwendung von mit Vorurteilen behafteten Datensätzen. Dies hat dazu geführt, dass führende Unternehmen und Forschungs-und Datenwissenschafts-Communities im Bereich der KI sich mit den ethischen Aspekten der KI eingehend befassen mussten. Mangel an angemessene Regeln in diesem Bereich kann zu Reputationsverlust, hohe Geldstrafen sowie zu regulatorischen und rechtlichen Problemen führen.

Ethik der KI (kurz KI-Ethik) ist ein Teilbereich der angewandten Ethik, der sich unten anderen mit der folgende Fragestellungen sich beschäftigt:

• die gezielte Rolle von KI-Syteme und die ethische Aspekte die ihre Benützung entsprechend ihrer Rollen ermöglichen,
• ethische Regeln, Leitpfaden für Menschen, die KI-Systeme planen, herstellen, testen, zertifizieren und benutzen.
• gewünschtes ethische Verhalten von KI-Systemen (Maschinenethik).

Als Leitfaden für die Ethik in der experimentellen Forschung und der Entwicklung von Algorithmen sind der Belmont-Bericht () in akademischer Gemeinschaft weit verbreitet. Die drei wesentliche Prinzipien des Belmont-Berichts lauten:

1. Respekt für Personen
2. Gutes tun
3. Gerechtigkeit (bzgl. Fairness und Gleichheit)

Obwohl eine vielzahl von ethischen Elemente, Prinzipien und Richtlinien für KI vorgeschlagen wurden, existiert derzeit keine einheitliche Richtlinien für KI-Ethik. Allerdings besteht eine gewisse Konsens über die folgende zwei Elemente in die KI-Ethik zu integrieren:

• Governance - um die Einhaltung der gesetzlichen Vorschriften in Zusammenarbeit mit Regierungsbehörden sicherzustellen.
• Erklärbarkeit - die Funktionsweise der KI Systeme zu erklären (Transparenz) um Vertrauen gegenüber KI-Systeme zu schaffen.

Es gibt mehrere Organisationen mit dem Ziel das KI-Ethik zu fördern. Dies sind die folgenden.

• CHAI: Das Center for Human-Compatible Artificial Intelligence () ist eine funktionierende Kooperation verschiedener Universitäten und Institute, welche dei vertrauenswürdige KI und nachweislich nutzbringender Systeme fördert.
• DARPA: Die Defense Advanced Research Projects Agency des US-Verteidigungsministeriums () fördert die erklärbarer KI-Forschung.
• NASCAI: Die National Security Commission on Artificial Intelligence () ist eine US Kommission ,,die die Methoden und Mittel prüft, die notwendig sind, um die Entwicklung von künstlicher Intelligenz, maschinellem Lernen und damit verbundenen Technologien voranzutreiben, um die nationalen Sicherheits- und Verteidigungsbedürfnisse der Vereinigten Staaten umfassend zu erfüllen.“
• AlgorithmWatch: Eine gemeinnützige Organisation (), die sich auf den Einsatz von erklärbaren und nachvollziehbaren Entscheidungsprozessen und Algorithmen abzielt.
• AI Now Institute: Eine gemeinnützige Organisation an der New York University (), die sich mit der sozialen Auswirkungen der KI beschäftigt.

Laut Luciano Floridi und Josh Cowls herrscht eine weitgehende Übereinstimmung darüber, dass es möglich ist, die ethischen Prinzipien für gesellschaftlich nützlichen Einsatz von KI basierend auf die vier Prinzipien der Medizinethik und ein zusätzliches fünftes Prinzip, Erklärbarkeit aufzubauen :

,,1. Fürsorge (Benefizienz): KI-Technologie soll der Menschheit nützen, das Wohlergehen fördern, die Menschenwürde wahren und der Erhaltung des Planeten dienen.
2. Schadensvermeidung (Non-Malefizienz): Negative Folgen eines übermäßigen oder missbräuchlichen Einsatzes von KI müssen vermieden werden, KI soll nur in einem sicheren Rahmen eingesetzt werden.
3. Autonomie: Menschen müssen die volle Entscheidungsfreiheit darüber haben, ob und welche Aufgaben sie an KI-Systeme delegieren, ihre Freiheit, sich eigene Normen und Standards zu setzen, muss gewahrt bleiben.
4. Gerechtigkeit: Wahrung der Solidarität, Vermeidung von Ungerechtigkeit, gleichberechtigter Zugang zu den Vorteilen der KI.
5. Erklärbarkeit (Verständlichkeit): Die Prinzipien 1 bis 4 sind nur realisierbar, wenn auch Laien nachvollziehen können, welchen Nutzen oder Schaden KI für die Gesellschaft hat und wer für welche Auswirkungen verantwortlich ist.“

Es gibt derzeit eine Reihe von ethischer Diskussionen bzgl. KI Systemen. Sollche KI-Ethik einbeziehende Debatten kommen in mehrere Bereichen vor. Autonomes Fahren stellt ein Musterbeispiel dar. Von automatisierter Systeme sind erwartet, dass sie im Vergleich zur menschlichen Fahrleistung zumindest eine Schadensminderung erzielen. Da derzeitige KI Syteme sehr selten, aber eventuell Fehlerhafte Reaktionen produzieren, ist es zumindest fragwürdig ob autonome Fahrzeuge diese Erwartung erfüllen können. Außerdem ist es auch problematisch, wie ein autonomes Fahrzeug in einem nicht normierbare dilemmatische Entscheidungen, wie z.B. Leben gegen Leben bei plötzlich auftretenden Gefahren, reagieren werden sollen. Ähnliche Debatte kommen auch im Bereiche Autonome Waffensysteme und Maschinenethik vor. Im Allgemeinen die folgende Debatte auslösende Quellen können identizifiert werden:

1. KI Systemen machen eventuell Fehler - durch Beschränkungen der Sammlung von Daten und Dokumentation sowie der algorithmischen Regeln und - Aufgrund der Unvollständigkeit der Korpora bei der Entscheidungsfindung (ist eine Angabe alle nötige Informationskanäle in die Korpora um die gleiche Entscheidung von KI zu haben, was ein Mensch machen würde, ist nicht möglich).
2. Bedenken hinsichtlich der Designziele des Systems, z.B. bessere Geschäftsergebnis zu schaffen statt öffentliches Interesse zu folgen. Eine andere Debatte bilden die Überlegungen über die technologische Singularität, i.e. wann die KI das Übertreffen die menschliche Intelligenz erreicht. Obwohl diese Superintelligenz steht nicht unmittelbar bevor, ist Sie mit Angst vor Gefahr auf die Menschheit verbunden. Allerdings ist diese Angst zumindest Teilweise unbegründet, da diese dadurch ausgelöst, dass die Funktionsweise der KI Systeme für meistens die Menschen nicht bekannt ist, also durch die fehlende Transparenz.