Daten und Sensoren

Metriken von Daten

Metriken von Aussagen

Sensoren als Datenquellen

Daten

Daten sind die Grundlage für die Modellbildung und Modelltestung

Daten können aus einer Vielzahl von Quellen stammen

Experiment

Simulation

Feldstudie

Abgeleitet aus anderen Datensätzen:
MapAndReduce(D): D → D'

Allgemein kann man Daten und deren Werte unterteilen in:

Skalare Werte, wie Temperatur, Alter, usw.

Serien von Skalaren Werten, wie Zeitserien

Vektorielle Werte wie Bilder

Zusammengesetzte Daten, also Datenrecords

Daten haben daher eine Dimensionalität 𝕏N, wobei die Wertemenge 𝕏 einer Dimension aus den ganzen ℕ, reelen ℝ, der Zeit 𝕋 oder kategorischen Wertemengen 𝕊 bestehen kann (oder Untermengen davon).

Datenreduktion

Ziel der Datenanalyse ist die Reduktion von Eingabedaten bezüglich Größe und Dimensionalität:

image-placeholder
(1-1)

1: function isRaining(temp,sunrad,moisture) =
2:   temp < 0 ? → false
3:   temp > 40 ? → false
4:   (sunrad-moisture) > 30? → false
5:   true

Beispiel 1. Beispiel einer Datenreduktionsfunktion ℝ^3^ → 𝔹

|Y|<|X|, M<N

1: function isStrong(age,weight,length) =
2:   age < 10 ? → false
3:   weight > 200 ? → false
4:   (weight/length) > 30? → false
5:   true

Datenklassen

Numerische und Metrische Werte

Das sind Werte die abzählbar sind und wo man Relationen (wie kleiner oder größer) sinnvoll definieren kann, also alle reellen und ganzen Zahlen.

Beispiele: Temperatur, Länge, Ort, Zeit

Kategorische Werte

Das sind symbolische Werte für die entweder keine (sinnvolle) Ordnungsrelation existiert oder wo sich wenigstens keine Differenzen bilden lassen.

Beispiele: Staatsangehörigkeit, Farbennamen (rot < gelb???), Schadenstyp

Skalierung der numerischen Werte

Intervallskaliert

Für diese Art von Attributen sind nur Unterschiede (Addition oder Subtraktion) sinnvoll. Beispielsweise wird die in °C oder °F gemessene Temperatur intervallskaliert. Wenn es 20 °C an einem Tag und 10 °C am folgenden Tag ist, ist es sinnvoll, über einen Temperaturabfall von 10 °C zu sprechen, aber es ist nicht sinnvoll zu sagen, dass es doppelt so kalt ist wie am Vortag.

Verhältnisskaliert

Hier kann man sowohl Differenzen als auch Verhältnisse zwischen Werten berechnen. Zum Beispiel kann man für das Alter sagen, dass jemand, der 20 Jahre alt ist, doppelt so alt ist wie jemand, der 10 Jahre alt ist.

Ordnungsrelationen

Nominal

Die Attributwerte in der Domäne sind ungeordnet und somit nur Gleichheitsvergleiche sinnvoll. Das heißt, wir können nur überprüfen, ob der Wert des Attributs für zwei bestimmte Instanzen gleich ist oder nicht. Zum Beispiel ist Geschlecht ein nominales Attribut.

Ordinal

Die Attributwerte sind geordnet und somit Gleichheitsvergleiche (ist ein Wert gleich einem anderen?) und relationale Vergleiche (ist ein Wert kleiner oder größer als ein anderer?) sind erlaubt, obwohl es möglicherweise nicht möglich ist, die Differenz zwischen den Werten zu quantifizieren!

Daten

Datensätze als Matrizen

Ein Menge von Daten kann in Matrizenform als Matrix D dargestellt werden (Analogie zur Tabellenform) [1]:

Die Zeilen sind Rekords der Variablenmenge {Xi|i=1,d} und geben als d-stelliges Tupel je nach Anwendung und Zielsetzung einzelne Beispiele, Instanzen, Experimente, Entitäten, Objekte, und Eigenschaftsvektoren wieder

image-placeholder
(1-2)

Der Vektor X ist die Menge aller Variablen (Sensoren) und die Spalten der Matrix D:

image-placeholder
(1-3)

type row = { X1:number, X2:number, .., Xd:number }
type table = row array;

Eingabe- und Ausgabevariablen

Sensoren sind typischerweise Eingabevariablen x

Aussagen sind Ausgabevariablen y, also Ergebnisse die sich aus den Eingangsvariablen ableiten lassen können (durch eine Funktion F):

image-placeholder
(1-4)

mit u+v=d.

Beispiel einer Datenmatrix

Botanischer Datensatz mit geometrischen (numerischen) Eigenschaften einer Pflanze und kategorischer Klassifikation:

[1]

Attribute

Die gemessenen Variablen X₁ bis X₄ sind metrische Datenvariablen, die Variable X₅=y ist eine kategorische Variable!

Die gemessenen Variablen X₁ bis X₄ (also Sensoren) nennt man Attribute, da sie Eigenschaften und beschreibende Variablen der Zielvariablen y sind

Sensoren

Welche Sensoren und Messdaten kennt ihr:

Messtechnik

Physikalische Größen wie Temperatur, Dehnung, Spannung, Zeit

Fusionierte Umfragevariablen (z.B. Ensemblemittelwerte)

Bei der Messung mit Sensoren unterscheidet man:

Einmalige bzw. einzelne Messungen (single shot)

Wiederholte Messungen der gleichen physikalischen Größe (Mittelwertbildung..)

Serien von Messwerten, vor allem zeitaufgelöste Datenserien:
D = {d₁,d₂,..,dn}, wobei i.A. Δt(di,di+1)=constant

Sensormodell

Ein Sensor ist ein Messwandler, auch in der Soziologie (Indikator für eine Eigenschaft die nicht direkt messbar ist)

Ein Sensor bildet daher eine i.A. physikalische Größe x auf eine andere Größe y ab:

image-placeholder
(1-5)

Es gibt i.A. eine Kalibrierungsfunktion K(f,x,y)

Beispiele: Druck → Spannung, Strahlung → Strom, usw.

Sensordaten

Sensoren S sind Datenquellen d von physikalischen, soziologischen oder sonstigen natürlichen nicht direkt erfassbaren Größen x

Die Datenwerte (numerisch) werden in einem definierbaren Intervall liegen

Die Kenntnis des Werteintervalls ist wichtig für spätere Datenverarbeitung, Analyse, und Maschinelles Lernen!

Kategorische Werte werden ebenfalls durch eine Menge definiert

image-placeholder
(1-6)

Mess- und Sensorische Systeme

Der Ursprung der Daten für Analyse und Maschinelles Lernen!

Ein Sensor kommt selten allein.

Sensoraggregation

Sensorklassen

Physische Sensoren

Physische Sensoren messen direkt eine Größe mit einem Messinstrument (kann auch die Auswertung einer Frage in einem Fragebogen sein), Smartphone

Virtuelle Sensoren

Verwenden Daten (von physischen und anderen virtuellen Sensoren) um neue sensorische Werte zu berechnen (kein Messinstrument) → Aggregatoren!!

Schichtenmodell von Sensorischen Systemen

In sensorischen Systemen werden Sensordaten in verschiedenen Ebenen verarbeitet:

Vertikale Ebenen repräsentieren die sensorischen Domainen und die Sensorklassen;

Horizontale Ebenen repräsentieren die Datenverarbeitung.

Vertikale Ebenen

Perzeption

Hier findet die Akquisition der rohen Sensordaten statt. Die Sensoren sind räumlich verteilt und werden lokal vorverarbeitet.

Aggregation

Einzelne Sensordaten werden zeitlich und räumlich zusammengeführt und gesammelt (Sensorfusion)

Applikation

Die gesammelten Daten werden nutzbar gemacht: Weitere Datenverarbeitung, Aufbereitung, Eigenschaftsselektion, Informationsgewinnung, Visualisierung

Horizontale Ebenen

Die horizontalen Ebenen durchziehen alle vertikalen Ebenen:

Sicherheit

Datenverarbeitung

Kommunikation

Datenspeicherung

Nachrichtenvermittlung

Management

Abbildung 1. Grundlegender Zusammenhang der horizontalen und vertikalen Ebenen in Sensorischen Systemen

Abbildung 2. Räumliche Abbildung der vertikalen Ebenen auf Cloud Computing

Sensoren in den Ebenen

Perzeption

Vorwiegend physische Sensoren

Aggregation

Virtuelle Sensoren, Datenreduktion (Größe und Dimensionalität)

Applikation

Datenanalyse und Modellbildung, Inferenz von Information, Maschinelles Lernen

Messfehler und Vertrauen

Die Messgrößen können statisch (zeitlich konstant) oder dynamisch (zeitlich veränderlich) sein. Die Wandlung dieser Messgrößen ergeben dann entsprechend Gleich- und Wechselsignale.

Auch eine prinzipiell zeitlich unveränderliche Messgröße (bezogen auf die Messung in einem vorgegeben Zeitinterval τ) erzeugt kein konstantes Signal. Ursache: Rauschen

Wiederholt man daher eine Messung N-mal unter gleichen Bedingungen, so wird man eine Reihe von verschiedenen Messwerten {s₁,s₂,...,sn} erhalten.

Es gibt systematische und zufällige Fehler bei der Messung, die sich überlagern.

Systematische Abweichung (systematischer Fehler)

Abweichung wird durch den Sensor verursacht

z.B.: falsche Eichung, dauernd vorhandene Störungen wie Reibung

lässt sich nur durch sorgfältiges Untersuchen der Fehlerquelle beseitigen

Zufällige Abweichung (zufälliger oder statistischer Fehler)

Abweichung wird durch unvermeidbare, regellose Störungen verursacht

bei wiederholter Messung weichen Einzelergebnisse voneinander ab

Einzelergebnisse schwanken um einen Mittelwert

Abbildung 3. Offset und Präzision bei der Messung einer Variable *X* [9]

Systematische Fehler

Eine Messgröße X ist meistens durch störende Messgrößen Y,Z,... usw. überlagert:

image-placeholder
(2-1)

So kann z.B. bei einer Messung einer Kraft oder einer Dehnung die umgebende Temperatur T oder Strukturschwingungen Einfluss auf den Sensor und dessen Übertragungsfunktion und somit auf das Messsignal S haben.

[9]

Systematische Fehler verfälschen die Kalibrierungsfunktion (z. B. bei Geraden den Offset und Steigung). Sind sie bekannt, können sie kompensiert (rausgerechnet) werden.

Systematische Fehler können aber auch während der Signalverarbeitung entstehen, so z. B. Offsetspannungen und zeitlicher Drift von Parametern (Verstärkungsfaktor).

Zufällige Fehler - Streuung

Zufällige Fehler beeinflussen die Genauigkeit einer Messung (Rauschen).

Wiederholt man eine Messung einer Größe X die durch reine zufälligen Fehler verfälscht wird, so ist die Häufigkeitsverteilung der Messwerte S={s₁,s₂,...,sn} um einen Mittelwert $\bar S$ durch eine Gaussverteilung gegeben (dabei muss die Anzahl der Messungen N groß sein).

Abbildung 4. Häufigkeitsverteilung nach Gauss von Messwerten um einen Mittelwert [9]

Der Mittelwert S repräsentiert die Abschätzung des wahren/wirklichen Wertes Σ der Messgröße X (oder S):

image-placeholder
(2-2)

Die Standardabweichung ist ein Maß für die Zuverlässigkeit (Präzision) der einzelnen Messwerte einer Messreihe {s₁,s₂,...,sn}:

image-placeholder
(2-3)

Eine Vergrößerung der Anzahl N der Messungen (unter gleichen Bedingungen!) führt zu einer Verbesserung des Mittelwertes $\bar S$ (Grenzfall N → ∞), nicht aber zu einer wesentlichen Verkleinerung der Standardabweichung σ, da die Genauigkeit nicht steigt!

Der wirkliche Mittelwert Σ ist nicht bekannt (nur im Grenzfall N → ∞ ist $\bar S$=Σ) - Es gibt aber ein Vertrauensintervall mit einer Wahrscheinlichkeit P dass dieser darin enthalten ist:

Σ ∈ [$\bar S$-σ,$\bar S$+σ] mit 68.3%

Σ ∈ [$\bar S$-2σ,$\bar S$+2σ] mit 95.4%

Σ ∈ [$\bar S$-3σ,$\bar S$+3σ] mit 99.73%

Auch in der Soziologie!

Abbildung 5. Rauschquellen bei einer Messung

Beispiele

/webwork

Plot

Plot(Array.random(200),{width:'70%',size:20})

Analysis

Math.statistics.analysis(Array.random(200))

Datenanalyse und Eigenschaftsselektion

Häufig sind die rohen sensorischen Daten(variablen) zu hochdimensional und abhängig voneinander

Reduktion auf wesentliche Merkmale kann ML Qualität deutlich verbessern

Häufig besitzen einzelne Sensorvariablen keine oder nur geringe Aussagekraft (geringe Entscheidbarkeitsqualität)

Datenqualität

Die Daten D werden durch vier wesentliche Eigenschaften beschrieben, die auch mit statistischer Analyse quantifiziert werden können:

Rauschen. Rauschen ist die Verzerrung der Daten. Diese Verzerrung muss entfernt oder Ihre nachteiligen Auswirkungen vermindert werden, bevor ML Algorithmen ausgeführt werden, da die Leistung und Qualität der Algorithmen beeinträchtigen kwerden ann.

Es gibt eine Vielzahl von Filteralgorithmen um den Effekt von Rauschen zu vermindern.

Ausreißer. Ausreißer sind Instanzen, die sich erheblich von anderen Instanzen im Datensatz unterscheiden. Beispiel: Durchschnittliche Anzahl der Follower von Nutzern auf Twitter. Eine Berühmtheit mit vielen Followern kann die Durchschnittliche Anzahl von Followern pro Person leicht verzerren. Da die prominenten Ausreißer sind, müssen Sie aus der Gruppe der Personen entfernt werden, um die Durchschnittliche Anzahl der Follower genau zu Messen.

Aber: Ausreißer können in besonderen Fällen nützliche Muster darstellen und die Entscheidung, sie zu entfernen, hängt vom Kontext und Fragestellung ab.

Fehlende Werte. Fehlende Werte sind Funktionswerte, die in Instanzen fehlen. Zum Beispiel, Einzelpersonen können es vermeiden, Profilinformationen auf social-media-Websites zu melden, wie Ihr Alter, Standort, oder Hobbys. Um dieses Problem zu lösen, können wir (1) Instanzen mit fehlenden Werten entfernen, (2) fehlende Werte schätzen (Z. B. durch den gängigsten Wert ersetzen) oder (3) fehlende Werte ignorieren, wenn data mining-algorithmen ausgeführt werden.

Duplikate. Doppelte Daten treten auf, wenn mehrere Instanzen mit genau denselben Funktionswerten vorhanden sind. Doppelte blog-posts, doppelte tweets oder Profile auf Social-media-Websites mit doppelten Informationen sind Beispiele für dieses Phänomen. Je nach Kontext können diese Instanzen entweder entfernt oder beibehalten werden. Wenn Instanzen beispielsweise eindeutig sein müssen, sollten doppelte Instanzen entfernt werden.

Statistische Analyse

Statistische Analysen von Mess- und Sensordaten können neue Datenvariablen erzeugen und Informationen über die Daten liefern:

Eigenschaftsselektion (Feature Selection) für ML und Informationsgewinnung

Variablentransformation mit Datenreduktion

Statistische Analyse liefert eine Reihe von Kennzahlen über Datenvariablen, das können Eigenschaften für die Weiterverabeitung sein:

image-placeholder
(3-1)

Welche statistische Größen gibt es? Was können statistische Größen über Daten aussagen?

Statistische Funktionen

[2:173]

[2:173]

Korrelation von Datenvariablen

Variablen X sollten möglichst (linear) unabängig sein,

Um eine geeignete, robuste und genaue Modellsynthese (also ML) zu ermöglichen, d.h.

Es sollte möglichst keine Zusammenhänge der Form ∃correlation(Xi,Xj) geben!

Um den Modellsyntheseprozess zu beschleunigen (also das Training); Rechenzeit reduzieren

Um Modelle klein und kompakt zu halten

Abhängige Variablen sollten identifiziert und in unabhängige "transformiert" werden!

Beispiel Prozessanalyse

Eine Datentabelle D mit experimentellen Messgrößen und Fertigungsparametern (Prozessparameter) von additiv gefertigten Bauteilen hatte zunächst 7 Variablen (numerisch):

X₁: Hatchabstand [mm]

X₂: Scangeschwindigkeit [mm/s]

X₃: Laserleistung [W]

X₄: Schichtstärke [mm]

X₅: Volumenenergiedichte [J/mm^3^]

X₆: Bauplatten Position x

X₇: Bauplatten Position y

Y₁: Dichte (%)

D bestand aus 61 Experimenten mit unterschiedlichen Fertigungsserien

Mit einer Principle Component Analysis (PCA) konnte die ganze Tabelle auf die Variablen PC₁ und Y₁reduziert werden!

Die Genauigkeit der mit ML synthetitisierten Funktion M(X): X → Dichte konnte ohne signifikanten Genauigkeitsverlust nur aus PC₁ abgeleitet werden, d.h. M(PC1): PC1 → Dichte

Aber: Für die Inferenz (Applikation) von M muss die PCA für die Eingabedaten X wiederholt werden bzw. die Datentransformation durchgeführt werden!

Analyse Kategorischer Variablen

Die Analyse von kategorischen Variablen vereint die Konzepte:

Mengenlehre

Kodierung/Dekodierung

Verteilung (Wahrscheinlichkeit des Auftretens)

[5]

Messdaten

Abbildung 1. Beispiel einer rein kategorischen Datentabelle ***D***. Die Zielvariable *Klasse* mit den Werten {N,P} ist ebenfalls kategorisch, z.B. Klasse=P ⇒ Sportliche Aktivität [5:53]

Gemischte Variablenklassen

Abbildung 2. Einige Datenvariablen wurden mit numerischen/metrischen Werten ersetzt (Klasse → Play-time) [7:47]

Kann aus der vorherigen Datentabelle mit numerischen Variablen noch ein Zusammenhang aus X zu Y hergestellt werden?

Reicht die Anzahl der Experimente im Vergleich zu der rein kategorischen Datentabelle?

Wo liegen die Probleme?

Weiteres Beispiel

[7:7]

Kategorische Variablen (sowohl Attribute als auch Zielvariablen) können von einer Vielzahl von numerisch basierten ML Verfahren nicht verarbeitet werden (wie neuronale Netze)

1: {sonnig,bewölkt,regnerisch} → {3,2,1}
2: {ja,nein} → {1,0}
3: {Schaden A, Schaden B, Schaden C} → { 1,2,3 }
4: {rot,grün,blau,braun,weiß} → {1,2,4,8,16}
5: {Sport, Kino, Theater, Musik} → {1,2,4,8}
6: {heiß,kalt} → {[1,0],[0,1]}

Die Kodierung ist umkehrbar mit einer Dekodierungsfunktion (unter Kenntnis der Kodierungsvorschrift)

Entropie und Informationsgehalt

Sensorvariablen können unterschiedlichen Informationsgehalt besitzen

Nur auf den Dateninhalt (Werte) der Variable Xi bezogen (inherenter Informationsgehalt)

Oder zusätzlich bezogen auf die Zielvariable Y (abhängiger Informationsgehalt)

Der Informationsgehalt einer Menge X aus Elementen der Menge C wird durch die Entropie E(X) gegeben:

image-placeholder
(3-2)

Dabie ist k die Anzahl der unterscheidbaren Elemente/Klassen Val(X) ⊆ C in der Datenmenge X (z.B. die Spalte einer Tabelle) und pi die Häufigkeit des Auftretens eines Elements ci ∈ C in X.

Beispiele:

1: X₁={A, C, B, C, B, C} → Val(X₁)=C={A, B, C},N=6
2: E(X₁)=-(1/6)log(1/6)-(2/6)log(2/6)-(3/6)log(3/6)=1.46
3: X₂={A, B, C} → Val(X₂)=C={A, B, C},N=3
4: E(X₂)=-(1/3)log(1/3)-(1/3)log(1/3)-(1/3)log(1/3)=1.58
5: X₃={A, A, A, A, B, B} → Val(X₃)={A,B} ⊂ C={A, B, C},N=6
6: E(X₃)=-(4/6)log(4/6)-(2/6)log(2/6)-(0/6)log(0/6)=0.92
7: X₄={A, A, A, A, B, B} → Val(X₄)=C={A, B},N=6
8: E(X₄)=-(4/6)log(4/6)-(2/6)log(2/6)=0.92

Die Entropie ist Null wenn die Datenmenge X "rein" ist, d.h., nur Elemente einer einzigen Attributklasse c₁ ∈ C enthält, z.B. X={A,A,A}.

Die Entropie ist log₂(|C|) wenn alle Werte gleichverteilt vorkommen, wenn nicht dann kleiner (nicht gleichverteilt).

Die Entropie reicht allein zur Bewertung des Informationsgehaltes nicht aus:

X1 | X2 | Y
A | C | P
B | C | P
A | D | N
B | D | N

E(X1)=1, E(X2)=1 !! Welche Variable X ist für die Entscheidung der Zielvariable Y geeignet?

/webwork

title

DataSports

data = [ { Beispiel: 1,
    Aussicht: 'sonnig',
    Temperatur: 'hei�',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'nein',
    Klasse: 'N' },
  { Beispiel: 2,
    Aussicht: 'sonnig',
    Temperatur: 'hei�',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'ja',
    Klasse: 'N' },
  { Beispiel: 3,
    Aussicht: 'bew�lkt',
    Temperatur: 'hei�',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'nein',
    Klasse: 'P' },
  { Beispiel: 4,
    Aussicht: 'regnerisch',
    Temperatur: 'mild',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'nein',
    Klasse: 'P' },
  { Beispiel: 5,
    Aussicht: 'regnerisch',
    Temperatur: 'kalt',
    'Luftfeuchtigk.': 'normal',
    'Windig?': 'nein',
    Klasse: 'P' },
...

AnalysisSports

print(Math.statistics.analysis(data.pluck('Aussicht')))
print(Math.statistics.analysis(data.pluck('Temperatur')))
print(Math.statistics.analysis(data.pluck('Luftfeuchtigk.')))
print(Math.statistics.analysis(data.pluck('Windig?')))
print(Math.statistics.analysis(data.pluck('Klasse')))

DataLenses

data=[ { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Reduced',
    'Recommended Lenses': 'None' },
  { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Normal',
    'Recommended Lenses': 'Soft' },
  { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'Yes',
    'Tear Production Rate': 'Reduced',
    'Recommended Lenses': 'None' },
  { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'Yes',
    'Tear Production Rate': 'Normal',
    'Recommended Lenses': 'Hard' },
  { Age: 'Young',
    'Spectacle Prescription': 'Hypermetrope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Reduced',
    'Recommended Lenses': 'None' },
  { Age: 'Young',
    'Spectacle Prescription': 'Hypermetrope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Normal',
    'Recommended Lenses': 'Soft' },
...

AnalysisLenses

print(Math.statistics.analysis(data.pluck('Age')))
print(Math.statistics.analysis(data.pluck('Spectacle Prescription')))
print(Math.statistics.analysis(data.pluck('Astigmatism')))
print(Math.statistics.analysis(data.pluck('Tear Production Rate')))
print(Math.statistics.analysis(data.pluck('Recommended Lenses')))

Informationsgewinn (Gain)

Ansatz: Die Datenmenge Y wird nach den möglichen Werten von X partitioniert, also je eine Partition pro ci ∈ Val(X).

image-placeholder
(3-3)

Die Menge Yv enthält nur Werte für die X=v ist!

Ein Verteilungsvektor ist dann Dist(X)=[|*v*~1~|,|*v*~2~|,..] und bedeutet wie häufig der bestimmte Wert vi ∈ Val(X) in X auftaucht!

Ein Verteilungsvektor ist dann Dist(Yv|X)=[|*u*~1~|,|*u*~2~|,..] und bedeutet wie häufig der bestimmte Wert u ∈ Val(Y) in Yv auftaucht!

Beispiele

[12]

/webwork

title

DataSports

data = [ { Beispiel: 1,
    Aussicht: 'sonnig',
    Temperatur: 'hei�',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'nein',
    Klasse: 'N' },
  { Beispiel: 2,
    Aussicht: 'sonnig',
    Temperatur: 'hei�',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'ja',
    Klasse: 'N' },
  { Beispiel: 3,
    Aussicht: 'bew�lkt',
    Temperatur: 'hei�',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'nein',
    Klasse: 'P' },
  { Beispiel: 4,
    Aussicht: 'regnerisch',
    Temperatur: 'mild',
    'Luftfeuchtigk.': 'hoch',
    'Windig?': 'nein',
    Klasse: 'P' },
  { Beispiel: 5,
    Aussicht: 'regnerisch',
    Temperatur: 'kalt',
    'Luftfeuchtigk.': 'normal',
    'Windig?': 'nein',
    Klasse: 'P' },
...

AnalysisSports

print('gain(Aussicht)='+ML.statistics.gain(
 data,
 'Aussicht',
 'Klasse',
  ML.statistics.unique(data.pluck('Klasse'))));
print('gain(Temperatur)='+ML.statistics.gain(
 data,
 'Temperatur',
 'Klasse',
  ML.statistics.unique(data.pluck('Klasse'))));
print('gain(Luftfeughtigk.)='+ML.statistics.gain(
 data,
 'Luftfeuchtigk.',
 'Klasse',
  ML.statistics.unique(data.pluck('Klasse'))));
print('gain(Windig?)='+ML.statistics.gain(
 data,
 'Windig?',
 'Klasse',
  ML.statistics.unique(data.pluck('Klasse'))));

DataLenses

data=[ { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Reduced',
    'Recommended Lenses': 'None' },
  { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Normal',
    'Recommended Lenses': 'Soft' },
  { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'Yes',
    'Tear Production Rate': 'Reduced',
    'Recommended Lenses': 'None' },
  { Age: 'Young',
    'Spectacle Prescription': 'Myope',
    Astigmatism: 'Yes',
    'Tear Production Rate': 'Normal',
    'Recommended Lenses': 'Hard' },
  { Age: 'Young',
    'Spectacle Prescription': 'Hypermetrope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Reduced',
    'Recommended Lenses': 'None' },
  { Age: 'Young',
    'Spectacle Prescription': 'Hypermetrope',
    Astigmatism: 'No',
    'Tear Production Rate': 'Normal',
    'Recommended Lenses': 'Soft' },
...

AnalysisLenses

print('gain(Age)='+ML.statistics.gain(
 data,
 'Age',
 'Recommended Lenses',
  ML.statistics.unique(data.pluck('Recommended Lenses'))));
print('gain(Spectacle Prescription)='+ML.statistics.gain(
 data,
 'Spectacle Prescription',
 'Recommended Lenses',
  ML.statistics.unique(data.pluck('Recommended Lenses'))));
print('gain(Astigmatism)='+ML.statistics.gain(
 data,
 'Astigmatism',
 'Recommended Lenses',
  ML.statistics.unique(data.pluck('Recommended Lenses'))));
print('gain(Tear Production Rate)='+ML.statistics.gain(
 data,
 'Tear Production Rate',
 'Recommended Lenses',
  ML.statistics.unique(data.pluck('Recommended Lenses'))));

Principle Component Analysis

PCA: Klassische Methode zur unüberwachten linearen Dimensionsreduktion → Analyse der Hauptkomponenten

Reduktion von Redundanz in den Attributen X

Bessere Trennung bei der Inferenz von kategorischen (und ggfs. auch numerischen) Zielvariablen

Weitere Verfahren:

Lineare Diskriminanzanalyse (LDA)

Singuläre Wertzerlegung (SVD)

Beispiel

D=[*X*~1~,*X*~2~,*Y*], mit Val(Y)={Class1,Class2}

"Rotation" des zweidimensionalen Attributraums führt zu einer reduzierten Datentabelle D'=[*PC*~1~,*Y*] (PC₂ kann weg gelassen werden)

[Czarnek,]

Spektrale Analyse

Diskerete Fourieranalyse

(DFT) und schnelle FA (FFT) → (Frequenzspektrum)

Spektrum der DFT/FFT hat nur N/2 Punkte (Datenreduktion)

Aber Problem bei DFT ist: Wenn Anzahl Datenpunkte N klein ist gibt es schlechte Auflösung des Spektrums

Vor allem bei "kontinuierlichen" Datenströmen mit fliessenden Fensterverfahren ein Problem (Fensterbreite Nwin ist klein)

Es gilt: Das aus der DFT erhaltene Frequenspektrum hat die höchste Frequenz:

image-placeholder
(3-4)

Diskrete Fouriertransformation

Eine zeitaufgelöste Variable X wird in eine frequenzaufgelöste Variable F transformiert:

image-placeholder
(3-5)

für k = 0,1,2, ... , N–1

Dabei ist X eine komplexwertige Datenserie {⟨re(xi),im(xi)⟩|i=0,1,..,N-1}, und

Das Ergebnis F ist ebenfalls eine komplexwertige Datenserie {⟨re(fi),im(fi)⟩|i=0,1,..,N-1}

Der Imaginärteil von X wird i.A. auf Null gesetzt (Sensoren sind i.A. reellwertig).

Amplitudenspektrum

image-placeholder
(3-6)

Phasenspektrum

image-placeholder
(3-7)

Leistungsspektrum

image-placeholder
(3-8)

Beispiel für Spektrale Eigenschaftsselektion

Sinus- und Cosinusschwingungen

/webwork

title

SinWaves

data1=Array.init(128,Math.sin);
data2=Array.init(128,Math.cos);
data3=Array.init(128,function (x) { return Math.sin(x/2) });
Plot(data1.merge(data2,'c').merge(data3,'c'),{type:'line'});

FFT

N=128; // data points

fft1=Math.FFT.FFT(N);
re=data1.slice();
im=Array.init(re.length);
fft1.fft1d(re,im);
spectrum=fft1.spectrum(re,im).slice(0,N/2);
Plot(spectrum,{})
print(spectrum.max(true /*position in array*/));

Waveletanalyse

Diskrete Wavelet Transformation (DWT)

DFT liefert nur Informationen im Frequenzraum

DWT liefert Informationen aus Zeit- und Frequenzraum

Höherer Informationsgehalt

DWT verwendet lange Zeitfenster für niedrige Frequenzen und kurze Zeitfenster für höhere Frequenzen, was zu einer guten zeitfrequenzanalyse führt.

DWT kann mit digitalen Filterkaskaden aufgebaut werden:

Jede Ebene der Filterkaskade besteht aus einem Hoch- und einem Tiefpassfilter

Der Hochpassfilter liefert die Details, der Tiefpassfilter die Approximation der DWT auf der n-ten Ebene

Die Approximation der Ebene n ist das Eingangssignal für die Ebene n+1

In jeder Ebene wird der Eingangsvektor |xi|=N auf N/2 reduziert, d.h. |xi+1|=N/2

Histogrammanalyse

Ein Histogramm gibt die (intervallbasierte) Verteilung von unterscheidbaren Elementen in einer Datenmenge X an

Beispiel sind Histogramme von Bildern die die Verteilung der Farb-/Grauwerte mit den Werten == Kanälen {0,1,..,255} wiedergeben.

[wavemetrics]

Analyse von Datenserien

Welcher Sensoren können bei der Bauteilprüfung und Schadensüberwachung Zeit- oder Datenserien erzeugen..

Messdaten

Abbildung 3. Zeitaufgelöste Sensordaten *s*(*t*) eines Beschleunigungssensors einer Maschine ohne und mit Schäden [2:164]

Korrelationsanalyse

Abbildung 4. Autokorrlelation der zeitaufgelösten Sensordaten *s*(*t*) eines Beschleunigungssensors einer Maschine ohne und mit Schäden [2:164]

Spektralanalyse

Abbildung 5. Spektralanalyse der zeitaufgelösten Sensordaten *s*(*t*) eines Beschleunigungssensors einer Maschine ohne und mit Schäden [2:167]

Merkmalsselektion

Abbildung 6. Die statistische und weitere Analysen können die Eingabe für ML liefern, aber auch die Modellsynthese parametrisieren bzw. beeinflussen

Zusammenfassung

Die statistische Analyse von Datentabellen liefert wichtige Informationen über die Qualität der Daten

Die Merkmalsselektion transformiert die Rohdaten auf neue möglichst linear unabhängige Attribute

Datenreduktion → Dimensionalität

Datenreduktion → Datengröße

Datenqualitätserhöhung

Es werden Verfahren für kategorische und numerische Datenvariablen unterschieden

Taxonomie des Maschinellen Lernens

Zielvariablen: Kategorische Klassifikation, Numerische Prädiktorfunktionen, Gruppierung

Modellfunktionen: Mit welchen Daten- und Programmarchitekturen können Eingabevariablen auf Zielvariablen abgebildet werden?

Training und Algorithmen: Wie können die Modellfunktionen an das Problem angepasst werden?

Überwachtes, nicht überwachtes und Agentenlernen

Datenverarbeitung

Die Daten die als Grundlage für die Induktion (Lernen) und die Deduktion (Applikation/Inferenz der Zielvariablen) müssen i.A. vorverabeitet werden → Merkmalsselektion

Abbildung 1. Maschinelles Lernen ist ein Werkzeug der Datenanalyse und des Data Minings [6]

Die Modellfunktion

Die Modellfunktion soll möglichst genau und effizient die Eingabedaten X auf die Zielvariablen Y abbilden:

image-placeholder
(4-1)

Die Modellfunktion M approximiert eine i.A. nicht bekannte Funktion F, d.h. eine axiomatisch oder analytisch abgeleitete Modellfunktion (z.B. phys. Gesetze) → M ist Hypothese von F!

Beispiel

Abbildung 2. Kausale vs. Prädiktive Modellbildung und Physikalische Modelle versa algorithmisch bestimmte Modelle (Hypothesen) [100]

Lernen

Lernen bedeutet die gewünschte Modellfunktion M möglichst genau zu approximieren so dass min error(|Y₀-Y|) für alle (X,Y₀) Paare gilt (Y₀: Referenzdaten).

I.a. ist M eine parametrisierbare Funktion f(P) oder eine parametrisierbare Datenstruktur

Der Parametersatz P={p₁,p₂,..,pi} bestimmt sowohl Funktion als auch Struktur (z.B. eines Entscheidungsbaumes)

Es gibt nicht eine Modellfunktion M, sondern eine große Menge möglicher Funktionen, genannt Hypothesen ℍ.

Lernen bedeutet also die bestmögliche Anpassung des Parametersatzes P um den Fehler zu minimieren und eine geeignet Hypothesenfunktion zu finden.

Man unterscheidet bekannte Referenzwerte der Zielvariablen (und Beziehung zu X) Y₀, auch Labels genannt, und prognostische Werte Y die als Ergebnis von M(X) geliefert werden (Inferenzwerte), d.h. bei der Applikation ist der wahre Wert Yt unbekannt (Schätzung von Yt)

image-placeholder
(4-2)

Beispiele

Abbildung 3. Verschiedene Modellfunktionen *M* die die (Trainings) Daten repräsentieren

Kreuzvalidierung

Beim Training wird ein Inferenzfehler zunächst aus Trainingsdaten bestimmt → Trugschluß!

Stattdessen müssen auch unabhängigige Testdaten für eine Kreuzvalidierung herangezogen werden, und dann ...

[13]

Fehler (Verlust)

Jede Hypothesenfunktion M ∈ ℍ führt zu einem Informationsverlust durch Appoximation der tatsächlichen und unbekannten Modellfunktione F.

Es gilt also:

image-placeholder
(4-3)

mit E als eine Fehlerfunktion (i.A. zufälliger Fehler) und $\hat{E}$ als mittlerer Prädiktionsfehler.

Die Hypothesenmenge ℍ ist also tatsächlich eine Approximation eines unbekannten "exakten" Modells (Modellfunktion) MF, die z.B. mittels physikalischer oder soziologischer Modelle ableitbar wäre.

Genauso wie eine Sensor eine physikalische Größe nur approximieren kann, der tatsächliche Wert der zu messenden Größe ist nicht bekannt

Abbildung 4. Training als Anpassung von Hypothesen für die Abbildungfunktion *X* → *Y* mit Trainingsdaten [11]

Parametrisierung

Die Paramater in dem Parametersatz P bestehen aus zwei Klassen:

Statische Parameter Ps

Parameter die die Modellimplementierung (Funktion, Datenstruktur, usw.) festlegen und i.A. während des Trainings und der Applikation unverändert bleiben. (Ausnahme: Evolutionäre Algorithmen) → Konfiguration

Dynamische Parameter Pd

Parameter die während des Trainings verändert (angepasst) werden. Z.B. Funktionsparameter oder Kantengewichte von neuronalen Netzen → Adaption

Beispiele

Numerische Prädiktorfunktionen (T: Temperatur, S: Satisfaction) → Regression

image-placeholder
(4-4)

Künstliches Neuronales Netzwerk

Daten

Trainingsdaten Dtrain

Datentabellen die aus Zeilen mit einer bekannten Beziehung (X,Y) bestehen und verwendet werden die Modellfunktion M durch Veränderung von P zu approximieren

Testdaten Dtest

Datentabellen die aus Zeilen mit einer bekannten Beziehung (X,Y) bestehen und verwendet werden die Modellfunktion M auf Genauigkeit und Fehler zu testen. Man spricht auch von einer Kreuzvalidierung da Dtest ∩ Dtrain = ∅ sein sollte.

Inferenzdaten Dinf

Datentabellen die nur aus Zeilen X bestehen (Y ist unbekannt)

Es gilt: Dtrain ⊆ Dall, Dtest ⊆ Dall, Dinf ⊆ Dall aber Dtrain ∩ Dtest = ∅ und Dtrain ∩ Dtest ∩ Dinf ≠ ∅ (Idealfall!)

Die großen Probleme beim algorthmischen/trainierten Modellieren:

Die Trainingsdaten sind nicht repräsentativ (Umfang, Varianz, Qualität)

Die Testdaten sind nicht repräsentativ (Umfang, Varianz, Qualität)

Die Trainingsdaten enthalten schwache Variablen die nicht entfernt wurden (Inkonsistenz und geringer Informationsgewinn)

Generalisierung. Das gelernte Modell M bildet alle drei Datenmengen gleichermaßen gut ab!

Ergänzung:

Bewertungsdaten

Beim Einsatz eines gelernten Modells kann eine Evaluierung bezüglich Qualität / Genauigkeit stattfinden. Diese Daten können dann ggfs. für eine Adaption des Modells und dessen Parametersatz P verwendet werden.

D.h. bei der Anwendung des Modells können somit auch neue Trainingsdaten gewonnen werden, z.B. im Rahmen eines Produktlebenszyklusmanagements!

Lernverfahren

Überwachtes Lernen

Es gibt Trainingsdaten mit bekannten Beziehungen (X,Y) die verwendet werden um die Modellfunktion mit minimalen Fehler anzupassen. Überwachugn benötigt i.A. einen Experten der die Beziehungen (X,Y) erstellt und analytisch den Fehler bewertet.

Unüberwachtes Lernen

Es gibt Trainingsdaten ohne bekannte beziehung (X,Y), d.h., schon das Lernen führt zu einer automatischen Inferenz der zielvariablen Y, die aber in diesem Fall i.A. nur durch Gruppenmengen ℚ bestehen. Eine Gruppenmenge Q={Xi} ⊆ ℚ bringt verschiedene Eingabewerte in Beziehung. D.h. Y ≡ ℚ.

Belohnungs- und Agentenlernen

Die Abbildungsfunktion f(X): X → Y wird schrittweise durch eine Evaluierung des inferrierten Y mit einem Belohnungswert r=[0,1] gelernt. Training und Inferenz findet gleichzeitig statt.

Abbildung 5. Ablauf Überwachtes Lernen mit Trainings- (Induktion) und Applikationsphasen (Deduktion) [6]

Taxonomie der Verfahren

[Abdul]

Überwachte Lernverfahren - Unterklassen

Abbildung 6. Zwei wichtige Unterklassen von überwachten Lernen: Regression (Numerische Zielvariablen) und Klassifikation (Kategorische Zielvariablen) [4]

Dimensionalitätsreduktion

ML kann auch für die Reduktion von Datendimensionalität eingesetzt werden (Informationen sind reduzierte Daten)

Beispiele: Principle Component Analysis, Single Value Decomposition, ..

Abbildung 7. Abbildung von hochdimensionale Daten *X*^n^ auf niederdimensionale *X*^m^ mit *m* < *n* [4]

Unüberwachtes Lernen - Unterklassen

Abbildung 8. Zwei wichtige Unterklassen von nicht überwachten Lernen: Clustering (Gruppenbildung) und Ausreißerdetektion [4]

Training

Das Training einer Modellfunktion M kann

monolitisch (alle Dateninstanzen werden "parallel" verwendet), oder

stapelbasiert (d.h. Gruppen von Instanzen werden "parallel" verarbeitet), oder

iterativ (Dateninstanzen werden "sequenziell" verwendet), und

inkrementell (iterativ mit neuen Daten).

Inkrementelle Trainings- und Anpassungsverfahren könnne alte Datensätze verwerfen → Stromldatenlernen!

Nicht jede Modellimplementierung ist geeignet:

Graphen (Bäume) können i.A. nur monolotisch trainiert = erzeugt werden!

Regression von math. Funktionen kann monolitisch und/oder iterativ erfolgen;

Neuronale Netze können monolitisch, stapelbasiert, iterativ, und vor allem inkrementell trainiert werden.

Modellimplementierungen

Es gibt im wesentlichen vier verschiedene Architekturen die Modelle M zu implementieren:

Funktionen

Die Struktur einer mathematischen Funktion wird durch ihre Terme gebildet (Berechnungsknoten), z.B. ax+bx². Zu jedem Term gehört ein dynamischer Parameter der beim Training angepasst wird um den Fehler zu minimieren. Das Ergebnis ist die Zielvariable y.

Gerichtete Graphen

Gerichtete Graphen (oder Entscheidungsbäume) bestehen aus Knoten und Kanten. Die Knoten repräsentieren eine Eingabevariable (Attribute) x ∈ X. Die Kanten beschreiben die Entwicklung eine Graphens beginnend vom Wurzelknoten hin zu den Blättern. Die Blätter enthalten die Werte der Zielvariable(n) y. Der dynamische Paremetersatz ist der Graph (dessen Struktur).

Funktionale Graphen

Hybrid aus gerichteten Graph und Funktion → Künstliche Neuronale Netze. Die Knoten repräsentieren Berechnungsfunktionen, die Kanten verbinden Ausgänge von Funktionen mit Eingängen. Es gibt Eingangsknoten die mit den Eingabevariablen X verbunden sind, und Ausgangsknoten die mit den Ausgangsvariablen Y verbunden sind.

Ungerichtete Graphen

Hier repräsentieren die Knoten Dateninstanzen X, und die Kanten verbinden die nächsten Nachbarn miteinander. Hier geht es um Gruppenbildung (k nächste Nachbarn/kNN Problem).

Abbildung 9. Verschiedene Modellimplementierungen

Hybride Modelle

Multiinstanz Modelle

Ensemblelernen vereint multiple Modelle (gleicher Klasse oder unterschiedlich)

image-placeholder
(4-5)

Die einzelnen Modellinstanzen arbeiten mit gleichen oder verschiedenen Dateninstanzen

Es gibt eine Split- und eine Join Schicht (Kombinierer, Modellfusion)

Abbildung 10. Verschiedene Architekturen für Multiinstanz Lernen und Inferenz [Jay]

Instanzklassifikation

SLSP

Einzelinstanz Lernen (auf allen Daten) und Einzelinstanz Prädiktion (Inferenz auf allen Daten)

SLMP

Einzelinstanz Lernen (auf allen Daten) und replizierte Multiinstanz Prädiktion (Inferenz auf Teildaten mit Modellfusion)

MLSP

Multiinstanz Lernen (auf Teildaten) mit Modellfusion und Einzeninstanz Prädiktion (Inferenz auf allen Daten)

MLMP

Multiinstanz Lernen und Multiinstanz Prädiktion (Modellfusion)

Ablauf und Phasen von ML

Statistische Analyse und Bewertung der Daten

Merkmalsselektion

Aufteilung der Daten in Trainings- und Testdaten (i.A. randomisiert) D=Dtrain ∪Dtest

Training einer Modellfunktion M mit bekannten (gelabelten bei ÜL) Trainingsdaten Dtrain unter Bewertung des Modellfehlers E(X)

Test und Bewertung von M mit bekannten Daten Dtest

Applikation (Inferenz) von M auf unbekannten Daten D

Zusammenfassung

Maschinelles Lernen besteht aus:

Modellimplementierungen:

Funktionen, Gerichtete Graphen, Funktionalen Graphen, Ungerichtete Graphen, also mit/für

Regression, Entscheidungsbäume, Neuronale Netze, Clustering (kNN)

Aufgaben

Regression, Klassifikation, Gruppierung (Clustering), Prognostik

Methoden und Verfahren

Überwachtes, nicht überwachtes, und rückgekoppeltes Belohnungslernen

Monolitisches, stapelbasiertes, iteratives, und inkrementelles Lernen

Einzel- versa Multiinstanzlernen

Enscheidungsbaumlernen (Konstruktion), Support Vector Machines (Regression), Backpropagation in Neuronalen Netze, usw.

ML besteht aus mehreren Phasen:

Datenerhebung, Datenvorverarbeitung, Statistische Bewertung, Merkmalsselektion, Modellertsellung, Training, Test und Analyse (Kreuzvalidierung), Anwendung/Inferenz

Daten werden unterteilt in:

Trainingsdaten , Testdaten, Anwendungsdaten

Trainings- und Testdaten bei ÜL mit (x,y) Beziehungen (Labelling)

Klassifikation mit Entscheidungsbäumen

Zielvariablen: Kategorische Variablen

Eigenschaftsvariablen: Kategorische und Numerische Variablen

Modell: Gerichteter azyklischer Graph (Baumstruktur)

Training und Algorithmen: C4.5, ID3, INN

Klasse: Überwachtes Lernen

Entscheidungsbäume

Ein Entscheidungsbaum ist ein gerichteter azyklischer Graph bestehend aus einer Menge von Knoten N die mit den Eingabevariablen x verknüpft sind und Kanten E die die Knoten verbinden

Die Endknoten sind Blätter und enthalten Werte der Zielvariablen y (daher kann y nur eine kategorische Variable sein, oder eine intervallkategorisierte)

Die Kanten bestimmen die Evaluierung des Entscheidungsbaum beginnend von dem Wurzelknoten bis zu einem Blattknoten

Jede Kante hat eine Evaluierungsbedingung ε(x) der Variable des ausgehenden Knotens x

Zusammengefasst ausgedrückt:

image-placeholder
(5-1)

Entscheidungsbäume können neben dem Graphen auch funktional dargestellt werden:

image-placeholder
(5-2)

Baumklassen

Man unterscheidet:

Binäre Bäume. Jeder Knoten hat genau (oder maximal) zwei ausgehende Kanten (Verzweigungen). Der Test der Variable x kann daher nur x < v, x > v, x ≥ v, oder x ≤ v sein! Wird vor allem bei numerischen Variablen eingesetzt.

Bereichs- und Mehrfachbäume. Jeder Knoten hat 1..k ausgehende Kanten (Knotengrad k). Der Test der Variable x kann auf einen bestimmten Wert x ∈ V oder auf ein Intervall [*a*,*b*] erfolgen! Wird vor allem bei kategorischen Variablen eingesetzt.

Baumstruktur

Abbildung 1. Grundlegende Struktur eines Entscheidungbaumes

Vorteile

⊕ Entscheidungsbäume sind einfach aufgebaut und können mit einfachen Algorithmen erzeugt werden.
⊕ Entscheidungsbäume als inferriertes Modell erlauben eine Erklärbarkeit des Modells, also die Antwort auf die Frage wie sich ein y aus einem x ergibt.
⊕ Weiterhin ist eine Ableitung eines inversen Problems möglich, d.h. welche Werte x für gegebenes y sind möglich?

Nachteile

⊗ Entscheidungsbäume können schnell spezialisieren, d.h. es fehlt an Generalisierung.
⊗ Theoretisch kann mit einem Entscheidungsbaum jede Trainingsdatentabelle mit einer Trefferquote von 100% abgebildet werden. Der Test mit nicht trainierten Daten ergibt aber Prädiktion in der Größenordnung der Ratewahrscheinlichkeit!

Training

Das Training mit Trainingsdaten Dtrain erzeugt den Baum schrittweise:

Es werden geeignete Variablen x ∈ X ausgewählt die einen Knoten im Baum erzeugen

Jeder hinzugefügte Knoten erzeugt neue Teilbäume (durch Verzweigungen)

Die Verzweigungsbedingungen ε (Kanten) werden ebenfalls vom Trainer anhand der Werte der Variable x in Abhängigkeit von der Zielvariablen y gewählt/berechnet.

Die Auswahl der Variablen und die Verzweigungsbedingungen können je nach Algorithmus und Baumklasse variieren!

Beispiel

Abbildung 2. Schrittweise Erzeugung des Entscheidungsbaums aus den Eingabedaten (a) erst mit einer Variable (b,c), dann mit zwei (d) unter Beachtung des Klassifikationsfehlers [10]

Jeder Knoten in einem binären Baum stellt eine lineare Separation des Eingabedatenraums dar.

Probleme bei Mehrbereichsbäumen

Wenn die Wertemenge val(x) groß ist gibt es entsprechend auch viele Verzweigungen im Baum!

Die Größe des Baums wächst an (Speicher)

Die Rechenzeit für das Training (Induktion) aber auch die Anwendung (Inferenz, Deduktion) wächst

Die Entropie kann als Maß der Varianz der Wertemenge gesehen werden.

Das "NP" Problembeispiel

Abbildung 3. k-stelliger Entscheidungsbaum für kategorische Variablen [14]

Beispiel Materialeigenschaften

Abbildung 4. (Links) Entscheidungsbaum für die Vorhersage von Reibungskoeffizienten von Materialien auf der Grundlage von sechs grundlegenden Materialmerkmalen (Rechts) Vergleich der vorhergesagten und experimentellen Reibungskoeffizienten [100]

Trainingsalgorithmen

Es gibt verschiedene Trainingsverfahren (für verschiedene Baumklassen):

ID3. Der Klassiker (Iterative DiChaudomiser 3, Ross Quinlan, 1975-1986) für kategorische Variablen (k-stelliger Baum)

C4.5. Der Klassiker (Ross Quinlan 1988-1993) für numerische (und kategorische) Variablen (Binär- und k-stelliger Baum) als Erweiterung des ID3 Verfahrens.

INN. Die Eigenkreation (ICE, Stefan Bosse, 2016) für numerische Werte mit Intervallarithmetik für unsichere verrauschte Sensorwerte (also im Prinzip mit Intervallkategorisierung und Kantenbedingungen sind x ∈ [*a*,*b*]), basierend auf C4.5 und ID3

Vergleich ID3 - C4.5

Der ID3-Algorithmus wählt das beste Attribut basierend auf dem Konzept der Entropie und dem Informationsgewinn für die Entwicklung des Baumes.

Der C4.5-Algorithmus verhält sich ähnlich wie ID3, verbessert jedoch einige ID3-Verhaltensweisen:

Möglichkeit, numerische (kont.) Daten zu verarbeiten.

Verarbeitung unbekannter (fehlender) Werte

Möglichkeit, Attribute mit unterschiedlichen Gewichten zu verwenden.

Beschneiden des Baumes nach der Erstellung (Modellkompaktierung).

Vorhersage der Fehler

Hervorhebung und Extraktion von Teilbäumen

ID3 Verfahren

[1] J. R. Quinlan, “Induction of Decision Trees,” in Machine Learning, Kluwer Academic Publishers, Boston, 1986.

Ausgangspunkt für die Konstruktion des Entscheidungsbaums ist die (Shannon) Entropie einer Spalte X der Datentabelle (mit der Variable x):

image-placeholder
(5-3)

Dann der Informationsgewinn einer Spalte X hinsichtlich der Zielvariablenspalte Y:

image-placeholder
(5-4)

Der Informationsgewinn, der durch Auswahl des Attributs x und der Spalte X erzielt wird, errechnet sich dann als Differenz der Entropie von Y und der erwarteten/durchschnittlichen Entropie von Y bei Fixierung von x.

Algorithmus

 1: 0. Starte mit leeren Baum, allen Eingansattributen X, der Zielvariablen Y,
 2:    und der vollständigen Datentabelle D(X,Y).
 3: 1. Berechne den Informationsgewinn für jede Attributevariable x ∈ X.
 4: 2. Wenn nicht alle Zeilen zum selben Zielvariablenwert gehören,
 5:    wird der Datensatz D in Teilmengen D'~xbest,v1~, D'xbest,v₂, usw.
 6:    aufgeteilt für das Attribut xbest ∈ X mit dem größten Informationsgewinn.
 7: 3. Es wird ein Knoten mit der Attributevariable xbest erstellt.
 8: 4. Wenn alle Zeilen zur selben Klasse gehören, wird ein Blattknoten
 9:    mit dem Wert der Zielvariable erstellt.
10: 5. Wiederholung von 1-4 für die verbleibenden Attribute X'=X / xbest,
11:    allen Teilbäumen (Verzweigungen von aktuellen Knoten) mit jeweiligen D',
12:    bis alle Attribute verwendet wurden,
13:    oder der Entscheidungsbaum alle Blattknoten enthält.

C4.5 Verfahren

[1] J. R. Quinlan, "C4.5: Programs For Machine Learning". Morgan Kaufmann, 1988.

Wie ID3 werden die Daten und Attribute an jedem Knoten des Baums bewertet um das beste Teilungsattribut zu bestimmen.

Aber C4.5 verwendet die Methode der "gain ratio impurity", um das Teilungsattribut zu bewerten (Quinlan, 1993).

Entscheidungsbäume werden in C4.5 mithilfe eines Satzes von Trainingsdaten oder Datensätzen wie in ID3 erstellt.

An jedem Knoten des Baums wählt C4.5 ein Attribut der Daten aus, das seinen Satz von Samples am effektivsten in Teilmengen aufteilt, die in der einen oder anderen Klasse verteilt sind.

Das Kriterium ist der normalisierte Informationsgewinn:

Verhältnis des Informationsgewinns G (Gain) zu einer sog. Teilungsqualität (Split Info SI), die sich aus der Zielvariable Y zum Aufteilen nach den Y Werten der Daten ergibt.

Das Attribut mit dem höchsten Verhältnis GR (Gain Ratio) wird ausgewählt, um die Entscheidung für die Teilung zu treffen.

image-placeholder
(5-5)

Teilung von kategorischen und numerischen Variablen

Bei kategorischen Variablen bestimmen die Werte Val(X) einer Spalte der Datentabelle einer Variablen x die Aufteilung eines Entscheidungbaums (Partitionierung).

Bei nuemrischen Variablen muss ein Wert als Teilungspunkt aus der Werteverteilung bestimmt!

Nicht trivial; Welches Kriterium?

Intervallkategorisierung und Wertepartitionierung kann helfen!

D.h. mit intervallkategorisierten diskrete Werter wird die Spalte X entsprechend der Zielvariable Y partitioniert.

Und diese Partitionen werden bewertet und der Teilungspunkt xsplit ∈ X bestimmt (z.B. über Mittelwerte der Intervalle)

Vertiefung

Rokach and O. Maimon, Data Mining with Decision Trees - Theory and Applications. World Scientific Publishing, 2015.

Intervallkodierung

Abbildung 5. Einteilung von kontinuierlichen Werteverteilungen in Intervall und Abbildung auf kategorische (diskrete) Werte

Unvollständige Trainingsdaten

Es kommt vor allem in der Soziologie aber auch in der Mess- und Prüftechnik vor, dass nicht alle Werte der Attributvariablen X für alle Trainingssätze bekannt sind.

Die Behandlung fehlender Attributwerte in den Zeilen der Datentabellen ist schwierig

Es gibt keine Universallösung für den Umgang mit ? Werten. Möglichkeiten:

Ersetzen des fehlenden Werts mit einem Standardwert

Ersetzen des fehlenden Werts mit einem probalistisch über Verzeilungshäufigkeiten bestimmten Wert (auch unter Einbeziehung des gesamten Datensamples)

Attributevariablen mit fehlenden Werten nicht verwenden

Intervallkategorisierte Entscheidungsbäume (INN/ICE)

Bisherige Entscheidungsbäume (C4.5/ID3) wurden entweder mit einer diskreten Anzahl von kategorischen Werten verzweigt oder mittels binärer Relationen!

Aber Sensoren (sowohl in der Mess-und Prüftechnik als auch ind er Soziologie) sind fehlerbehaftet, d.h. es gibt bei jedem x-Wert ein Unsicherheitsintervall [*x*-δ,*x*+δ] → Rauschen

Damit können Entscheidngsbäume (anders als Neuronale Netze oder Regressionslerner) nicht umgehen.

Wenn der Split mit x<50 und x≥50 an einem Knoten mit x erfolgt würde bei Werten um 50 und überlagerten Rauschen ein Entscheidungsproblem entstehen!

Lösung: k-stellige Knoten mit Intervallverzweigungen, also:

image-placeholder
(5-6)

Abbildung 6. Vergleich der verschiedenen Baumarten und Knotenverzweigungen

Bei der Konstruktion des Entscheidungsbaums werden wieder nach Informationsgewinn bzw. Gewinnverhältnis Attributvariablen und Spalten der Datentabelle ausgewählt.

Die numerischen Werte werden sowohl beim Training als auch bei der Inferenz durch Intervalle ersetzt → Ersetzung von diskreter mit Intervallarithmetik

Entropien usw. werden durch kategorisierte Intervalle bestimmt

Das große Problem: Für jede Variable muss ein ε abgeschätzt werden → Statistisches Modell erforderlich.

Und was bedeuten jetzt überschneidende Intervalle?

Überschneidungen bedeuten Ununterscheidbarkeit!

Inferenz mit NN Suche

Jeder Knoten xi hat ausgehende Kanten mit annotierten Intervallen [*v*~j~-ε,*v*~j~+ε]

Bei einem neuen zu testenden Variablenwert v wird einseits auch ein Intervall [*v*-ε,*v*+ε] gebildet und mit den Kantenintervallen verglichen, andererseits wird das nächstliegende Intervall gesucht

Random Forest Trees

Multiinstanzmodell

Es werden m Entscheidungsbäume DT={dt₁,..,dtm} getrennt gelernt und erzeugt

"Random": Die Aufteilung der Daten in Teilungsvariablen erfolgt randomisiert!

Eingabedaten werden zur Inferenz an alle Teilbäume dti ∈ DT gegeben

Alle Ausgabevariablen der Teilbäume werden fusioniert

Fusion:

Mittelwert (bei intervallkodierten oder intervallskalierbaren kat. Zielvariablen durch Dekodierung in numerische Werte)

Mehrheitsentscheid

Konsensfindung (Verhandlung)

Parametersatz:

Stelligkeit eines Knotens (Anzahl der ausgehenden Kanten)

Anzahl der Teilbäume

Partitionierung des Eingaberaums (d.h. ein bestimmter Baum verwendet nur eine Teilmenge der Spalten aus D)

Fusionsmodell und Algorithmus

Abbildung 7. Grundprinzip von Multibaumklassifikatoren [Abhishek]

Beispiel

Experiment

Sensornetzwerk von (3 × 4) Dehnungssensoren

Stimulus: Bauteilschwingung

Varianz: Bauteilschäden (Defekte)

Zielvariable: Schadensklassifikation (9 Positionen)

Merkmalsvektor: Downgesampletes zeitaufeglöstes Sensorsignal einer

Ressourcen

Genauigkeit

Zusammenfassung

Entscheidungsbäume sind für die Klassifikation von kategorischen Zielvariablen geeignet

Numerische Zielvariablen müssen intervallkodiert werden.

ID3/C4.5 Lerner können numerische und kategorische Eingabevariablen (Attribute) verwenden

Ein Attributariable ist ein Teilungspunkt

Rauschen auf Sensordaten muss durch "Unsicherheitsintervall" und Intervallarithmetik behandelt werden

Vergleich mit anderen Lernverfahren zeigt gute Ergebnisse (je nach Problem)

Klassifikation mit Künstlichen Neuronale Netze

Zielvariablen: Numerische Variablen

Eigenschaftsvariablen: Numerische Variablen

Modell: Gerichteter Graph (zyklisch oder azyklisch)

Training und Algorithmen: Backpropagation

Klasse: Überwachtes Lernen

Künstliche Neuronale Netze

Ein Künstliches Neuronales Netz (KNN) ist ein gerichteter Graph bestehend aus einer Menge von Knoten N und Kanten E die die Knoten verbinden

Knoten: Neuron oder Perzeptron mit einem oder mehreren Eingängen I und einem Ausgang o; Berechnungsfunktion g(I): I → o

Kanten: Gewichteter Datenfluß vom Ausgang eines Neurons zum Eingang eines anderen (oder des selben) Neurons

Ein KNN ist eine Komposition aus einer Vielzahl von Abbildungsfunktionen G=(g₁,g₂,..,gm). Es gibt Parallelen zu Regressionsverfahren mit Funktionen.

Zusammengefasst ausgedrückt:

image-placeholder
(6-1)

f ist eine Transferfunktion die die akkumulierten Eingangswerte auf den Ausgangswert o abbildet, und g ist dann die gewichtete und akkumulative Transferfunktion

Unterschied (künstliches) Neuron und Perzeptron:

Ein Neuron ist immer eine Elementarzelle

Ein Perzeptron kann ein einzelnes Neuron oder ein Netzwerk aus Neuronen beschreiben

Daher gibt es:

Single Layer Perceptron (SLP) → Nur Eingangs- Nx und Ausgangsneuronen Ny

Multi Layer Perceptron (MLP) → + Innere Neuronen Nd

Das Neuron

Abbildung 1. Ein einzelnes Neuron mit einem einzelnen Eingang *p* und einem Ausgang *o*. *w* ist ein Gewichtungsfaktor (ein Gewicht für eingehendes *p*) und *b* ist ein Bias (Offset) [15]

Das Mehreingangsneuron

Abbildung 2. Ein einzelnes Neuron mit einem Eingangsvektor ***p*** und einem skalaren Ausgang *o*. ***w*** ist ein Gewichtungsfaktorvektor (ein Gewicht für eingehendes *p*) und *b* ist ein Bias (Offset) [15]

Neuronale Netze und Matrizen

Neuronale Netze werden durch eine Graphenstruktur (statische Paremeter) und mathematisch durch Matrizen (dynamische Parameter) beschrieben:

Abbildung 3. Ein einzelnes Neuron mit einem Eingangsvektor ***p*** und einem skalaren Ausgang *o*. ***w*** ist ein Gewichtungsfaktorvektor (ein Gewicht für eingehendes *p*) und *b* ist ein Bias (Offset); jetzt in Matrizenform (Annotation) [15]

Schichten von Neuronalen Netzen

I.A. werden Neuronen von neuronalen Netzen in Schichten (Layern) angeordnet und gruppiert

Günstig für Matrixalgebra

Aber nicht notwendig!

[15]

Struktur eines KNN

Abbildung 4. Grundlegende Struktur eines KNN mit Matrizen (blaue Ellipse=1 Neuron) [15]

Vereinfachte Form eines KNN

Abbildung 5. Vereinfachte Struktur eines KNN mit Matrizen [15]

Klassen von KNN

Forwärtsgekoppelte Netzwerke

Azyklischer gerichteter Graph, d.h. es gibt nur eine Vorwärtspropagation von einer Schicht zur nächsten (keine Rückkopplung).

Diese Netzwerke können rein funktional beschrieben und berechnet werden.

Es gibt keinen Zustand!

D.h. die aktuellen Ausgangswerte hängen nur von den aktuellen Eingangswerten ab!

Rückgekoppelte Netzwerke

Zyklischer gerichteter Graph, d.h. es gibt Rückkopplungen (Ausgang eines Neurons geht in Eingänge der aktuellen oder vorherigen Schichten).

Diese Netzwerk können nicht rein funktional beschrieben und berechntet werden!

Sie besitzen einen Zustand, d.h. der Ausgangswert hängt von der Historie vergangener Eingabewerte ab!

Rückgekoppelte Netzwerke

Geeignet für Prädiktion auf zeit- und Datenserien D(t)=d₀,d₁,...,dt

Abbildung 6. Rückgekoppeltes und zustandsbehaftetes KNN mit einer Verzögerungsfunktion (Speicher) [15]

Transferfunktion

Auch Aktivierungsfunktion genannt (in Anlehnung an biologische Vorbild)

Biologisch: Häufig eine Schwellwertfunktion

Künstlich / ML: Auch lineare Übertragunsfunktionen!

Es gibt eine Vielzahl verschiedener Funktionen

Die einfachste wäre (wenn auch wenig in Gebrauch): f(a)=a

Warum ist eine solche Übertragungsfunktion ungeeignet bzw. problematisch?

Welche mathematischen Eigenschaften (Übertragungskurve) sollte wohl eine Transferfunktion besitzen?

Zur Erinnerung: Wir nehmen an dass der Wertebereich von einem x ≈ [-1,1] ist. Ebenso für ein y ≈ [-1,1].

Transferfunktionen besitzen häufig begrenzende Eigenschaften (Sättigungsverhalten), und nicht lineares Übertragungsverhalten

Abbildung 7. Verschiedene gebräuchliche Transferfunktionen *f*(*a*) [15]

Ein einfaches Neuron - Funktional

image-placeholder
(6-2)

/webwork

Neuron

function sigmoid(x) {
  return 1/(1+Math.exp(-x))
}
print(sigmoid(0))
var data = [
  {x1:1,  x2:2,  y:1.0},
  {x1:-1, x2:2,  y:0.0},
  {x1:0,  x2:-1, y:0.0},
]
function neuron(x1,x2,w,b) {
  var accu = x1*w[0]+x2*w[1];
  return sigmoid(accu+b)
}
var w = [1.0,1.0], b=0;
data.forEach(function (row) { print(neuron(row.x1,row.x2,w,b),row.y) });

Parametersatz des KNN

Statische Parameter

Anzahl der Eingangsneuronen (verbunden mit x), abhängig von der Anzahl der Eingabevariablen |x| und der Kodierung (numerisch vs. kategorisch)

Anzahl der Ausgangsneuronen (abhängig von der Kodierung). Bei numerischen Zielvariablen y gilt also: |Ny|=|y|

Anzahl der inneren verdeckten Neuronen |Nd| und deren Anordnung in Schichten

D.h. die Konfiguration des Netwerkes ist [*c*~1~,*c*~2~,..,*c*~m~] bei m Schichten und ci Neuronen pro Schicht

Bei vollständig verbundenen Schichten ist keine Angabe der Vernetzung notwendig

Dynamische Parameter

Im wesentlichen die Gewichtematrix Wi (Schicht i):

image-placeholder
(6-3)

Mit S: Anzahl der Neuronen in der Schicht, R: Anzahl der Eingangsvariablen (oder Neuronen der vorherigen Schicht)

Der Ausgangswert eines Neurons nj ist dann gegeben durch einen Wert aus B und die j-te Zeile von W:

image-placeholder
(6-4)

Bei mehrschichtigen Netzwerken hat man eine Menge von Gewichtematrizen, die zu einem Tensor zusammengefasst werden können.

Training von KNN

Wie bei allen überwachten Lernproblemen gilt es eine Fehlerfunktion zu minimieren:

image-placeholder
(6-5)

Ziel ist die Minimierung des Fehlers unserer Modellhypothese M(x) durch Anpassung der Gewichtematrix W und evtl. (wenn vorhanden) des Offsetvektors B

Es ist leicht zu erkennen dass das Training einen hochdimensionalen Parametersatz anpassen muss. Es ist nicht unmittelbar klar wie ein optimales W abgeleitet werden kann!

Erklärbarkeit

Der Zusammenhang von y und x (x → y) ist schon bei einem einschichtigen Netzwerk nur noch schwer nachvollziehbar!

Eine Invertierung (inverses Problem y → x) ist ebenso nur schwer möglich

Eigentlich ist nur ein einzelnes Neuron erklärbar und verständlich

Dort ist die Anpassung (des Gewichtevektors w) noch durch multivariate Regression möglich

Beispiel

"Gradient Descent" Verfahren

Problem: x=(a,b), y

Netzwerk: Ein Neuron, Sigmoid Transferfunktion

/webwork

Neuron

function sigmoid(x) {
  return 1/(1+Math.exp(-x))
}
print(sigmoid(0))
var data = [
  {x1:1,  x2:2,  y:1.0},
  {x1:-1, x2:2,  y:0.0},
  {x1:0,  x2:-1, y:0.0},
]
function neuron(x1,x2,w,b) {
  var accu = x1*w[0]+x2*w[1];
  return sigmoid(accu+b)
}
var w = [1.0,1.0], b=0, sets=[0,1,2], rate=0.1, errors=[];
for(var run=0;run<10000;run++) {
  var set=Math.random.select(sets),
      row=data[set];
  var y=neuron(row.x1,row.x2,w,b), err=y-row.y;
  if ((run % 100)==0) { errors.push(Math.abs(err)); print(Math.abs(err))}
  w[0]=w[0]-rate*err*row.x1;
  w[1]=w[1]-rate*err*row.x2;
}
print(w)
data.forEach(function (row) { print(neuron(row.x1,row.x2,w,b),row.y) });

Nicht lineare Probleme

SLP können nur lineare Probleme separieren.

Abbildung 8. Nicht linear separierbare Probleme - nur mit MLP klassifizierbar [15]

/webwork

Neuron

function sigmoid(x) {
  return 1/(1+Math.exp(-x))
}
print(sigmoid(0))
var data = [
  {x1:0,  x2:0,  y:0},
  {x1:1,  x2:0,  y:1},
  {x1:0,  x2:1,  y:1},
  {x1:1,  x2:1,  y:0},
]
function neuron(x1,x2,w,b) {
  var accu = x1*w[0]+x2*w[1];
  return sigmoid(accu+b)
}
var w = [1.0,1.0], b=0, sets=[0,1,2], rate=0.1, errors=[];
for(var run=0;run<10000;run++) {
  var set=Math.random.select(sets),
      row=data[set];
  var y=neuron(row.x1,row.x2,w,b), err=y-row.y;
  if ((run % 100)==0) { errors.push(Math.abs(err)); print(Math.abs(err))}
  w[0]=w[0]-rate*err*row.x1;
  w[1]=w[1]-rate*err*row.x2;
}
print(w)
data.forEach(function (row) { print(neuron(row.x1,row.x2,w,b),row.y) });

Backpropagation Verfahren

Bekanntes und gängiges Verfahren

https://hmkcode.com/ai/backpropagation-step-by-step

Gradientenverfahren

Baut auf dem Minimierungsansatz "Gradient Descent" (GD) auf (Absteigender Gradient)

Beim GD Verfahren wird eine Funktion, z.B. f(x,w): x → y derart über den Parameter w angepasst wird dass der Fehler err=|y-y₀| minimal wird

Es wird nun die Änderung des Fehlers beobachtet Δerr und der (oder später die) Parameter w mit der Ableitung des Fehlerwerts ∂err/∂w zu der Änderung des Parameters korrigiert:

image-placeholder
(6-6)

Vereinfacht gilt:

image-placeholder
(6-7)

Jetzt wird ein neuronales Netzwerk betrachtet, wo die Neuronen ebenfalls Funktionen mit Eingangsvariablen und Ausgangsvariablen sind

Bei zusammengesetzten Funktionen (z.B. auch Neuronen in inneren Schichten) müssen die Gewichte schrittweise von hinten nach vorne angepasst werden

Abbildung 9. Beispiel eines ANN mit Kantengewichten und dem Ansatz der Backpropagation [hmkcode.com/ai/backpropagation-step-by-step]

Die Gewichte werden nun Schicht für Schicht unter Einbeziehung der gewichteten Fehlerpropagation fleichermaßen angepasst

Abbildung 10. Backpropagation des Fehlers zu den Eingängen des Beispielnetzwerkes [hmkcode.com/ai/backpropagation-step-by-step]

Kategorische Multiklassen Probleme

Wenn die Ergbnisvariable vom kategorischen Typ ist dann gibt es zwei Möglichkeiten:

One-Hot Kodierung

Jedes Klassensymbol (also ein diskreter Wert vi der Zielvariable y) wird durch ein Ausgangsneuron repräsentiert

Multi-level Kodierung

Jedes Klassensymbol wird durch einen Wert aus dem Wertebereich eines Ausgangsneurons repräsentiert

Problem: Nicht lineare Transferfunktion und Sättigungsverhalten

Die gleichen Verfahren sind auch auf kategorische Eingabevariablen anwendbar

Numerische Prädiktorfunktionen

Neben der Klassfikation lassen sich mit ANN auch numerische (kontinuierliche) Funktionen lernen

Damit wird Funktionsapproximation wie bei den Regressionsverfahren möglich

Unterschied: Bei der Regression ist die funktionale Struktur von f(x): x → y bereits fest und muss vorgegeben sein

Die Verwendung eines ANN bietet da auch noch indirekt das Lernen der funktionalen Strukturen neben der Anpassung der Parameter

Literatur zur Vertiefung

[1] M. T. Hagan, howard B. Demuth, M. H. Beale, and O. D. Jesus, Neural Network Design. https://hagan.okstate.edu/nnd.html

Zusammenfassung

Neuronale Netze bestehen aus Neuronen

Neuronen sind Funktionen

Die Kanten verbinden Ausgänge von Neuronen mit den Eingängen nachfolgender Neuronen mit einer Multiplikation eines Gewichtfaktors

Alle Eingänge eines Neurons werden summiert, das Ergebnis einer Transfer/Aktivierungsfunktion übergeben

Training bedeutet Anpassung der Gewichte um den Ausgangsfehler zu minimieren

Gängiges Verfahren: Fehlerrückpropagation

Ein- und Ausgabeschnittstellen von Prädiktorfunktionen

Kodierung und Dekodierung von Variablen für kont. Prädiktorfunktionen

Normalisierung und Skalierung von Daten

Kagetorische Variablen

Kategorische Variablen müssen für die Verwendung in Prädiktorfunktionen in numerische Werte kodiert werden

Multi-level Kodierung: Abbildung von allen kategorischen Werten auf unterschiedlich numerische Werte (skalare und vektorielle Werte)

One-hot Kodierung: Abbildung von allen kategorischen Werten auf 01 Vektoren

Aber: Anders als die Intervallkodierung von numerischen Variablen (z.B. für Entsch.bäume) muss im umgekehrten Fall der Kodierung einer kat. Variable in eine numerische Variable eine Intervall- und Verhältnisskalierung existieren!!

Beispiele

Farben C={rot,grün,blau,braun}

Kodierung in skalaren kont. Variable aber mit diskreten Werten

Kodierung in vektorielle Variable mit kont. Werten → RGB

image-placeholder
(7-1)

Welche Probleme ergeben sich bei der Multi-level Kodierung (skalar) von Zielvariablen bei typischen Sigmoid Transferfunktionen von Neuronen?

Nichtlinearität an den Rändern [0,1]

Ein- und Ausgabeschnittstellen

Abbildung 1. Verschiedene Kodierungen von ein-/ausg. kat. Variablen

Die One-hot Kodierung von Eingabevariablen erfordert die Berechnung eines diskretwertigen Vektors

Aber die One-hot Kodierung von Ausgabevariablen ergibt einen kontinuierlichen Vektor der noch diskretisiert werden muss:

Schwellwertfunktion → Es kann zu Mehrdeutigkeiten kommen (Unentscheidbarkeit)

Der kont. Ausgangswert yi (Ci) wenn im Bereich [0,1] kann als ein Maß für die Wahkrscheinlichkeit des Auftretens eines Klassensymbols Ci verwendet werden!

Softmax Funktion: Diese bildet einen n-dimensionalen Vektor y mit yi ∈ [0,1] und max (Σ yi) = |y| auf einen n-dimensionalen Vektor ab mit max (Σ yi) = 1!

Softmax Funktion

image-placeholder
(7-2)

Fehleranalyse und Kostenfunktionen

Bewertung der Qualität eines Klassifikators oder von Prädiktorfunktionen

Aufteilung von Datensätzen

Künstliche Erweiterung von Datensätzen

Fehlerfunktionen

Ziel ist ein aussagekräftiger Fehlerwert um die Qualität des Trainings und des erzeugten Modells M(x):x → y bewerten zu können

Fehlerwerte bei kategorischen Zielvariablen vergleichen direkt die Übereinstimmung der inferrierten und vorgegebenen Werte der Zielvariablen

Gesamtfehler (falsche Klassifikation)

Falsch-positiver Fehler (binärer Klassifikator)

Falsch-negativer Fehler (binärer Klassifikator)

Falsch-C Fehler (Multiklassifikator)

Klassenspezifischer Fehler (Multiklassifikator)

Fehlerberechnung

Daten

Es sei D die Gesamtmenge der Dateninstanzen D

Es sei Dtest die Testdatenmenge Dtest ⊆ D

Klassifikationsfehler

image-placeholder
(8-1)

Dabei sind Y⁰ die vorgegebenen Werte der Zielvariablen und Yp die aus dem trainierten Modell berechneten (inferrierten) Werte

Der Inferenzfehler liegt dann im Bereich [0,1]

Bei binärer Klassifikation sollten die Falsch-positiv und Falsch-negativ Fehler zusätzlich getrennt bestimmt werden:

image-placeholder
(8-2)

Konfusionsmatrix

Bei Multiklassifikation bietet sich die Konfusionsmatrix an um eine Bewertung der Klassifikationsqualität mit falsch-C Bewertungen einer Klasse C und somit errC zu erfassen

Kreuzentropie

Bei kontinuierlichen Ausgabevariablen (KNN, SVM) aber evtl. kategorischen Zielvariablen ist die Berechnung der Kreutentropie zwischen Y⁰ und Yp aussagekräftiger

Eine Kreuzentropie → 0 bedeutet vollständige Übereinstimmung, Werte > 0 bedeuten Abweichungen

Je größer die Kreuzentropie zwischen zwei Vektoren/Matrizen ist, desto größer ist die Abweichung

Berechnung der Kreuzentropie zweier Matrizen

Eingabewerte: Matrix U und V mit Zellenwerten im Bereich [0,1]

Ergebnis: Skalarer Wert

Problem (siehe unten): log(0) → -∞

image-placeholder
(8-3)

Beispiele

/webwork

confmat

var confmat = [
 [1,0,0],
 [0,0.3,0.2],
 [0,0.7,0.8]
]
Plot(confmat,
     {type:'confusion',
      title:'Machine Learning Results',
      labels:{data:['A','B','C']}})

crossEntr

U=[[0,1],[1,0],[0,1],[0,1]]
V=[[0.1,0.99],[0.6,0.4],[0.01,0.99],[0.1,0.95]]
var cross=ML.statistics.crossEntropy(U,V)
var error= ML.math.meanMat(
  ML.math.activateTwoMat(U,V,
    function (u,v) { return Math.pow(u-v,2) }))
print('Cross Entropy  = '+cross);
print('Mean Sq. Error = '+(error*100));

Netzwerkkonfiguration

Konfiguration von ein- und mehrschichtigen neuronalen Netzwerken

Festlegung der Anzahl der Schichten, Knoten pro Schicht, und Vernetzung

Neuronale Netze

Ein neuronales Netz ist ein gerichteter Funktionsgraph

Einzelne Funktionsknoten können zu Schichten zusammengefasst werden

Eingabeschicht

Die Anzahl der Eingabeneuronen wird durch den Eingangsvektor x und der Kodierung bestimmt! Jedes Element von x ist mit einem Eingang eines Eingangsneurons verbunden

Ausgabeschicht

Die Anzahl der Ausgabeneuronen wird durch den Ausgangsvektor y und der Kodierung bestimmt! Jedes Element von y ist mit einem Ausgang eines Ausgangsneurons verbunden

Innere Schichten

Neuronen die weder mit den Ein- noch den Ausgängen direkt verbunden sind.

Konfiguration

Wenn von vollständig verbundenen Schichten ausgegangen wird kann die Konfiguration eines KNN mit einem Vektor/Array angegeben werden. Jedes Element gibt die Anzahl der Neuronen pro Schicht an.

Beispiele:

layers=[1] → SLP
layers=[2,1] → SLP
layers=[2,3,1] → MLP
layers=[1,4,3,1] → MLP

Verbindungen

1:1

Der Ausgang eines Neurons einer Schicht i (oder einer Eingabevariable x) wird mit dem Eingang eines folgenden Neurons der Schicht j verbunden

1:n

Die Ausgänge aller Neuronen einer Schicht i (oder alle Eingabevariablen x) werden mit den Eingängen jedes folgenden Neurons der Schicht j verbunden → Vollständig verbundene Schicht

0/1:k

Nur ein Teil der Ausgänge werden mit den Eingängen von folgenden Neuronen verbunden → Unvollständig und irregulär verbundene Schichten (eher Sonderfall)

Abbildung 1. Vollständig verbundenes Netzwerk [16]

Die statische Festlegung der Konfiguration der inneren Schichten ist schwierig!

Es gilt:

Linear separierbare Probleme verwenden keine inneren Schichten!

Nichtlinear separierbare Probleme können innere Schichten verwenden

Beim Training wirken innere Schichten zunächst wie eine "Mauer", die Wirkung auf den Ausgang wird kleiner

Bei inneren Schichten muss die Trainingsdatenvarianz und Anzahl der Instanzen groß sein

Je mehr innere Schichten und Neuronen um so mehr Trainingsinstanzen und Anstieg der Rechenzeit!

ML Frameworks

Tensorflow

Neataptic

Torch

ML

Tensorflow

Datenverarbeitung mit tiefen Künstlichen Neuronalen Netzwerken ("Deep Learning") → "Google Brain"

Strombasierte Datenverarbeitung mit Pipelines (Queues)

Datenverarbeitungsgraph (Datenflussdiagram)

[103]

TensorFlow verwendet ein einheitliches Datenflussdiagramm, um sowohl die Berechnung in einem Algorithmus als auch den Zustand darzustellen, in dem der Algorithmus arbeitet.

Im Gegensatz zu herkömmlichen Datenflusssystemen, bei denen Knoten funktionale Berechnungen für unveränderliche Daten darstellen, ermöglicht TensorFlow Kanten mit Berechnungen darzustellen, die einen veränderlichen Zustand besitzen oder aktualisieren [103].

https://www.tensorflow.org

Durch die Vereinheitlichung des Berechnungs- und Zustandsmanagements in einem einzigen Programmiermodell ermöglicht TensorFlow Programmierern, mit verschiedenen Parallelisierungsschemata zu experimentieren, die beispielsweise die Berechnung auf Servern oder GPUs erlauben.

Eine typische TensorFlow-Anwendung hat zwei verschiedene Phasen:

Die erste Phase definiert das Programm (Z. B. ein zu trainierendes neuronales Netzwerk und die Aktualisierungsregeln) als Symbolisches Datenflussdiagramm mit Platzhaltern für die Eingabedaten und Variablen, die den Status darstellen.

Die zweite phase führt eine optimierte Version des Programms auf einer Menge verfügbarer Geräte aus (z.B. Server, CPU, GPU).

Verabeitungseinheiten

Das "Programm" ist zunächst unabhängig von der verwendeten Verarbeitungsarchitektur

Abstraktion für heterogene Beschleuniger: Neben Allzweckgeräten wie multicore-CPUs und GPUs können spezielle Beschleuniger für Deep Learning signifikante Leistungsverbesserungen und Energieeinsparungen erzielen.

Verabeitungsmodell und Parallelität

TensorFlow unterscheidet sich von batchbasierten Datenflusssystemen in zweierlei Hinsicht:

Das Modell unterstützt mehrere gleichzeitige Ausführungen auf überlappenden Teilgraphen des Gesamtgraphen.

Das Modell unterstützt verteilte Berechnung

Einzelne Knoten des Graphes können einen veränderlichen Zustand haben, der zwischen verschiedenen Ausführungen des Diagramms geteilt werden kann.

Elemente des Datenflussgraphens

In einem TensorFlow-Diagramm stellt jeder Knoten eine Einheit der lokalen Berechnung dar, und jede Kante repräsentiert die Ausgabe von oder Eingabe in einen Knoten.

Die Berechnung findet an Eckpunkten mit Operationen auf Werten statt, die entlang der Kanten als Tensoren fließen.

Tensoren

Alle Daten werden als monosortige Tensoren modelliert (n-dimensionale Arrays), wobei die Elemente vom primitiver Typ wie int32, float32 oder string sind (wobei string Binärdaten darstellen kann).

Operatoren

Eine Operation nimmt m ≥ 0 Tensoren als Eingangswerte und erzeugt n ≥ 0 Tensoren als Ausgangswerte.

Zustansbasierte Operationen

Eine Operation kann einen veränderlichen zustand besitzen, der bei jeder Ausführung gelesen und/oder geschrieben wird. D.h. das Ergebnis einer Operation hängt von vorherigen Berechnungen ab!

Queues

TensorFlow unerstützt mehrere Warteschlangenimplementierungen, die Koordination von Berechnungen unterstützen.

tensforflow.js

Tensorflow ist primär in C++ implementiert

Ausführung auf speziellen Verarbeitungseinheiten wie GPUs erfordert eine Kodeübersetzung zur Laufzeit

Es gibt Python Anbindungen

tensorflow.js ist eine Implementierung von Tensorflow rein in JavaScript und kann in Browsern ausgeführt werden

GPU Nutzung z.B. über Open/WEBGL

https://www.tensorflow.org/js

Nachteile von Tensorflow

Durch die Trennung von Daten, Kode, und Verarbeitungseinheiten schlechte Performanz bei "kleinen" Problemen (hohe Initialisierungszeit und Overhead)

Beispiel Lernen des EXOR Problems: Tensorflow.js benötigt ca 3-5 Minuten für das Training, Neataptic.js nur 100ms!

Durch primäre Matrixalgebra nicht flexibel anpassbar

Z.B. kaum Möglichkeit der Verwendung von evolutionären Algorithmen (Dynamische Restrukturierung des KNN)

Lernkurve ist am Anfang flach

Neataptic

Ebenfalls ein KNN Framework,

Reine JavaScript Implementierung

Basiert NICHT auf Matrixalgebra; die Neuronen werden einzeln berechnet

Aber mit (optionalen) evolutionären Algorithmen

Das Training kann neben Kantengewichten auch die Struktur ändern: Knoten und Kanten können getauscht, entfernt, oder hinzugefügt werden!

Für kleine Probleme gute Perfomanz

Lernkurve ist "steil"

Bietet eine Vielzahl von Berechnungsfunktionen und Strukturen

Struktur kann beliebig und irregulär programmiert werden

Es gibt "Architekten" für viele gängige Architekturen

Forwärtsgekoppelte und rückgekoppelte Architekturen

https://wagenaartje.github.io/neataptic/

Torch

Torch ist eine open-source-Bibliothek für maschinelles lernen, ein scientific computing framework und eine Skriptsprache, die auf der Programmiersprache Lua basiert.

Daher kann mit einer einfach zu erlernden Programmiersprache direkt auf Torch gearbeitet werden

http://torch.ch

Torch gibt es auch für R!

https://torch.mlverse.org

Lernkurve ist "steil"

ML

Eigenes Framework (Stefan Bosse) dass eine Vielzahl von Lernalgorithmen und Modellen zusammenfasst:

Entscheidungsbäume (C4.5, ID3, ICE, usw.)

KNN (ANN → Neataptic, MLP → SMO, usw.)

Belohnungslernen (Reinforcement und Agenten L.)

kNN

Clustering (SOM)

Textanalyse

...

Reine JavaScript Implementierung

Trennung von Daten und Algorithmen (d.h. prozedurale Progarmmierung)

Viele Modelle sind portabel, d.h. können direkt mit JSON.stringify und JSON.parse serialisiert und deseralisiert werden

Enthalten in bzw. verfügbar für verschiedene Software Frameworks:

WorkBook

NoteBook (digitale Übungen)

JAM (JavaScript Agent Machine)

Beispiele

/webwork

data

var x = [
  [0,0],
  [0,1],
  [1,0],
  [1,1]
]
var y = [
  [0],
  [1],
  [1],
  [0]
]
ML.log(function () { print(inspect(arguments)) })

model

model=ML.learner({
  algorithm: ML.ML.MLP,
  layers : [2,4,1],
  verbose: 1,
});

train

ML.train(model,{
  x:x,
  y:y,
  epochs:1000
});

test

var results=ML.predict(model,x);
print(results)
print(ML.statistics.crossEntropy(ML.math.vec2Mat(results),y));

Zusammenfassung

Es wird zwischen Klassifikatoren (kategorische Zielvariablen) und Prädiktorfunktionen (numerische Zielvariablen) unterschieden

Klassifikation mit Prädiktorfunktionen erfordert Kodierung und Dekodierung!

Die Fehleranalyse während und nach dem Training kann mit den statistischen Größen "Mean Squared Error" und Kreuzentropie erfolgen

Die Konfiguration der inneren Schichten von KNN ist schwierig und häufig ein iterativer Prozess

Daten- und Dimensionalitätsreduktion

Datenreduktion ist ein wichtiger Schritt in der Datenvorverarbeitung für ML

Ziel: Reduktion der Datenvariablen (Attribute) → Dimensionalitätsreduktion pro Instanz

Ziel: Reduktion der Dateninstanzen (durch kleine Anzahl von Repräsentanteninstanzen) → Datenvolumenreduktion

Motivation für Datenreduktion

Die Daten sind sowohl hinsichtlich Dimensionalität des Eingabevektors x als auch hinsichtlich der Anzahl von Dateninstanzen |D| sehr groß

Es gibt Redundanzen

a. Von Datenvariablen (lineare Abhängigkeit)

b. Von Dateninstanzen (Redundanz und Überlappung)

Aber: Reduktion bei b. kann die geforderte Datenvarianz verschlechtern!

Trennung von wenig aussagekräftigen (schwachen) von aussagekräftigen (starken) Variablen

Wenn die Dimensionalität der Eingabedaten x zunimmt, wird jedes Lernproblem immer schwieriger und rechenintensiver!

Beispielsweise werden in regelmäßigen Abständen 5 Punkte von [0,1] abgetastet.

Das sammeln von Proben auf die gleiche Weise im d-dimensionalen Raum erfordert 5d-Punkte, die exponentiell in Bezug auf d wachsen.

[4]

Ein weiteres Problem bei hochdimensionalen Daten ist, dass unsere geometrische Interpretation von Daten irreführend sein kann.

Betrachtet man zum Beispiel die ausfüllende Hypersphäre des Einheishyperwürfels im d-dimensionalen Raum

Wenn d = 1 ist, ist das Volumen einer eingepassten Hypersphäre 1, was dem Hyperwürfel entspricht.

Wenn d auf 2 und 3 erhöht wird, ist das Volumen des Hyperkubus immer noch 1, aber das Volumen der Hypersphäre ist ungefähr 0,79 bzw. 0,52.

[4]

Unsere geometrische Intuition ist falsch,

da obwohl die eingepasste Hypersphäre kleiner als der Hyperwürfel ist, ist die Hypersphäre nicht extrem klein.

Wenn jedoch d weiter erhöht wird, ist das Volumen des Hyperkubus immer noch 1, aber das Volumen der ausfüllenden Hypersphäre neigt zu 0.

Dies bedeutet, dass, wenn d groß ist, die Hypersphäre fast vernachlässigbar ist.

Verfahrem und Methoden

Lineare Algebra

Bestimmung von Eigenvektoren und Hauptkomponenten mit der Principle Component Analysis

Abbildung des Eingabedatenraums auf einen niedrigdimensionaleren Datenraum unter Beibehaltung der Datenrepräsentation

Ziel: Reduktion der Attribute, Beibehaltung der Dateninstanzen

Clustering

Bestimmung von Gruppen von Dateninstanzen (mit geometrischer Gemeinsamkeit durch "Nähe") durch dichtebasierte Clusteringverfahren (DBSCAN)

Ziel: Reduktion der Instanzmenge durch wenige repräsentative Instanzen; Beibehaltung der Datenvariablen

Repräsentative Instanzen können (aber müssen nicht) mehrheitlich die Instanzen der Gruppe mit einem bestimmten Wert der Zielvariable (sofern kategortisch oder intervallkodiert) verknüpfen

Hohe Zielvariablenwertdiversität in Gruppen zeigt schwache Korrelation von x mit y!

Lineare Dimensionalitätsreduktion

Lineare Dimensionalitätsreduktion transformiert die ursprünglichen d-dimensionalen Dateninstanzen {xi}n in nieder m-dimensionale Ausdrücke {zi}n durch eine lineare Transformation T ∈ ℝ^m×d^

image-placeholder
(11-1)

T ist die Transformationsmatrix, z der reduzierte Datenvektor (pro Dateninstanz i) und x der ursprüngliche Datenvektor.

Abbildung 1. (a) Lineare Dimensionalitätsreduktion (b) Projektion von Daten auf einen linearen Subraum [4]

Zentrierung von Daten

Verschiebung der Daten in Richtung "Koordinatenursprung"

image-placeholder
(11-2)

[4]

Unüberwachte Dimensionsreduktion

Hauptkomponentenanalyse (PCA)

Reduktion der Datendimesionalität unter Beibehaltung der intrinsischen Information der Daten und der Datenstruktur

Abbildung 2. PCA: (a) Reduktion der Dimensionalität 3 → 2 unter Beibehaltung der ursprünglichen geometrischen Eigenschaften der Punkte zueinander (Position) und der Gruppenzugehörigkeit (b) [4]

Das bedeutet dass zi eine orthogonale Projektion von xi ist

D.h. T TT = Im mit Im als Identitätsmatrix und a^T^ die transponierte Matrix

Die "Distanz" zwischen x und z kann aber (als Fehler) nicht unmittelbar bestimmmt werden

Daher wird z wieder in den ursprünglich d-dimensionalen Datenraum durch TT zurück transformiert

Die euklidische Distanz ist dann gegeben durch die totale statistische Streumatrix C und der Spur einer Matrix tr:

image-placeholder
(11-3)

mit:

image-placeholder
(11-4)

D.h. PCA ist ein Optimierungsproblem mit:

image-placeholder
(11-5)

Es gibt eine globale Lösung:

image-placeholder
(11-6)

mit ei als Eigenvektor der Matrix C mit den Eigenwerten λ₁ ≥ λ₂ ≥ .. ≥ λd ≥ 0.

D.h. es gilt:

image-placeholder
(11-7)

Es wird "kleine" und "große" Eigenvektoren geben

Die Transformationsmatrix T der PCA ist also eine orthogonale Projektion in einen Subraum der durch die "großen" Eigenvektoren aufgespannt wird,

Die kleinen Eigenvektoren werden daher entfernt

Und: PCA transformierte Variablen sind unkorreliert!

PCA liefert aber i.A. keine Struktureigenschaften wie Cluster

Abbildung 3. Weiteres Beispiel von PCA: Die Analyse der Hauptkomponenten zentriert die Dateninstanzen und dreht dann die Achsen, um Sie mit den Richtungen der höchsten Varianz in Einklang zu bringen. Wenn die Varianz auf *z*~2~ klein ist, kann Sie ignoriert werden und wir haben eine Dimensionalitätsreduktion von zwei auf eins. [17]

ML.pca

Das ML Framework stellt ein PCA Modul zur Verfügung:

Die Daten D müssen in Matrixform vorliegen (keine Recordtabellen)

Eigenvektoren berechnen

ML.pca.getEigenVectors = function(data:number [][]) → {
  eigenvalue: number, vector: number []
} [];

Transformation der Datentabelle berechnen

ML.pca.computeAdjustedData =
  function (data:number [][],
            eigenVector1:{},eigenVector2?:{},..)
→ {
  adjustedData: number [][],
  formattedAdjustedData: number [][],
  avgData: number [][],
  selectedVectors: number [][]
}

Achtung: Das Datenformat von adjustedData ist transponiert und muss für eine Tabelle rekonstruiert werden

Rekonstruktion der Datentabelle aus der reduzierten Tabelle

ML.pca.computeOriginalData = function(
  formattedAdjustedData,
  selectedVectors,
  avgData) → {
  formattedOriginalData,
}

PCA Beispiel

/webwork

data

data = [
  {
    "length":5.1,
    "width":3.5,
    "petal_length":1.4,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":4.7,
    "width":3.2,
    "petal_length":1.3,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":4.6,
    "width":3.1,
    "petal_length":1.5,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":5,
    "width":3.6,
    "petal_length":1.4,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
...

eigen

dataX=ML.preprocess(data,'m',
 {features:
   ['length','width','petal_length','petal_width']
}).data;
eigenX=ML.pca.getEigenVectors(dataX);

adjust

dataZ=ML.pca.computeAdjustedData(dataX,eigenX[0],eigenX[1]).adjustedData;

reconstruct

dataXR=ML.pca.computeOriginalData(
  dataZ.formattedAdjustedData,
  dataZ.selectedVectors,
  dataZ.avgData).formattedOriginalData;

Lokalitätsbewahrende Projektion

Ähnlichkeit zwischen Instanzen xi und xj wird untersucht und mit einem Wert 0 ≤ Wi,j ≤ 1 ausgedrückt.

Ähnlichkeitsfunktionen

Gaußfunktion

image-placeholder
(11-8)

(t ist ein Anpassungsparameter)

k-Nächster Nachbar (kNN)

image-placeholder
(11-9)

Nk(x) ist die Menge aller Nachbarschaftsinstanzen (k ist die Anzahl der Menge)

k ist ein Anpassungsparameter der die Lokalität einstellt (Reichweite)

Transformation

image-placeholder
(11-10)

Problem: T=0 ist eine Lösung, aber nutzlos!

Daher weitere Randbedingung für die Minimierung (Anpassung von T):

image-placeholder
(11-11)

Dichtebasiertes Clustering

kNN kann ebenso als ein ML Clusterer mit Inferenz auf unbekannten eingesetzt werden

Dichtebasierte Clusteringmethoden können primär für die Datenreduktion eingesetzt werden

Reduktion von einer Menge von Dateninstanzen auf Gruppen (wobei die Instanzen erhalten bleiben, aber in jeder Gruppe reduziert werden können)

DBSCAN

Dichtebasiertes Räumliches Clustering mit Rauschen (DBSCAN) ist ein Basisalgorithmus. Es kann Cluster unterschiedlicher Formen und Größen aus einer großen Datenmenge entdecken, die Rauschen und Ausreißer enthält.

Algorithmische Schritte für DBSCAN Clustering

Der Algorithmus iteriert über alle Punkte indem er willkürlich einen Punkt im Datensatz aufnimmt (bis alle Punkte besucht wurden)

Wenn es mindestens minPoint - Punkte in einem radius von ε bis zu dem Punkt gibt, werden alle diese Punkte als Teil desselben Clusters betrachet.

Die Cluster werden dann erweitert, indem die Nachbarschaftsberechnung für jeden Nachbarpunkt rekursiv wiederholt wird.

Eventuell gibt es Beschränkungen bezüglich der Dimension der Dateninstanzen (typisch 2: Clustering von Bildpunkten)

Wahl der Parameter

Jede Data Mining Aufgabe hat das Problem der Parameterwahl.

Jeder Parameter beeinflusst den Algorithmus auf bestimmte Weise. Für DBSCAN werden die Parameter ε und minPts benötigt.

minPts

Das Minimum von minPts kann aus der Dimension des Datensatzes *D abgeleitet werden, so dass minPts ≥ D + 1 gilt.

ε

Der Wert für ε kann dann unter Verwendung eines k-Entfernungsgraphen ausgewählt werden, der den Abstand zum k = minPts-1 nächsten Nachbarn zeichnet, der vom größten zum kleinsten Wert geordnet ist.

Bei guten Werten von ε gibt es eine ausgewogene Verteilung der Dateninstanzen in Gruppen

Wenn ε viel zu klein gewählt wird, wird ein großer Teil der Daten nicht gruppiert, während für

einen zu hohen Wert von ε Cluster zusammengeführt werden und sich die Mehrheit der Objekte im selben Cluster befinden.

Aufgrund minPts Randbedingung werden u.U. nicht alle Instanzen gruppiert!

Beispiel DBSCAN

/webwork

data

data = [
  {
    "length":5.1,
    "width":3.5,
    "petal_length":1.4,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":4.7,
    "width":3.2,
    "petal_length":1.3,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":4.6,
    "width":3.1,
    "petal_length":1.5,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":5,
    "width":3.6,
    "petal_length":1.4,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
...

pca1

dataX=ML.preprocess(data,'m',
 {features:
   ['length','width','petal_length','petal_width']
}).data;
eigenX=ML.pca.getEigenVectors(dataX);

pca2

dataZ=ML.pca.computeAdjustedData(dataX,eigenX[0],eigenX[1]).adjustedData;

clust1

dataZ2=dataZ[0].merge(dataZ[1],'c')
dbscan=new ML.DBCLUST.DBSCAN();

clust2

eps=0.3;
clusters=dbscan.run(dataZ2,eps,10);

Zusammenfassung

Datenreduktion ist ein wichtiger Schritt in der Datenvorverarbeitung

Datenreduktion bedeutet die Reduktion der Datenmenge und/oder ihrer Dimensionalität

Datenreduktion ist bereits eine Merkmalsselektion (Reduktion auf wesentliche Attribute und Werte)

PCA ist geeignet um numerische Eingabedaten in ihrer Dimensionalitä zu reduzieren (Reduktion der Datenvariablen und Ersatz mit transformierten)

DBSCAN ist geeignet um Gruppen von Dateninstanzen zu finden um schliesslich repräsentative Instanzen daraus zu ermitteln

Support Vector Machines

SVM gehören zu den Regressionsverfahren

SVM nutzen aber bei der Parameteranpassung (Training) eine andere Fehlerfunktion (Loss) als bei anderen gängigen Regressionsverfahren (z.B. LS Minimierung)

SVM können primär kategorische und weniger numerische Zielvariablen verwenden

SVM sind (zunächst) lineare Klassifikatoren!

Binärer Klassifikator

Ein binärer Klassifikator soll durch eine lineare Funktion repräsentiert werden (y={-1,+1}):

image-placeholder
(12-1)

Dabei sind w und γ die Parameter des Modells die durch das Training an das Problem angepasst werden müssen.

w ist ein Normalenvektor der bei einem binären Klassifikationsproblem die beiden Instanzklassen trennt

Abbildung 1. (Oben) ***w*** ist der Normalenvektor und γ die Verschiebung der Trennungsgrenze für zwei Klasseninstanzen (Unten) Verschiedene ***w***/γ Varianten der Trennungsgrenze mit unterschiedlichen Rändern (Sicherheitsbereichen) [4]

Training

Das Lernen von w und γ erfordert die Berechnung des Abstandes von allen Dateninstanzen von der Trenngrenze. Die Abstände müssen positiv sein:

image-placeholder
(12-2)

für alle Dateninstanzen D={(xi,yi)}n.

Da w und γ beliebig gewählt werden können, kann die Randbedingung auch mit (..)yi ≥ 1 gewählt werden.

Weiterhin kann es sinnvoll sein alle Dateninstanzen um den Ursprung des Koordinatensystems zu zentrieren

Wichtig: Die Werte für y liegen im Intervall [-1,1]!

Alle Probleme die (..)yi ≥ 1 erfüllen mit einem (w,γ) sind linear separierbar.

Es gibt unendlich viele Lösungen (also Entscheidungsgrenzen)

Man wählt das (w,γ) aus bei der alle Dateninstanzen die größte Trennung besitzen (breitester Trennbereich, siehe Abb.)

Der Abstand der Dateninstanzen D ist definiert als das Minimum des normalisierten Abstandes:

image-placeholder
(12-3)

D.h. SVM zu trainieren ist das Minimierungsproblem:

image-placeholder
(12-4)

Harter Trennungsbereich (Hard SVM)

Bei einer "harten" Trennung einer SVM gilt dann:

image-placeholder
(12-5)

Weicher Trennungsbereich (Soft SVM)

Die SVM mit harten Trennungsbereich erfordert lineare Separierbarkeit der Dateninstanzen

Ist in der Realität aber nicht immer oder eher selten gegeben

Die weiche Trennung durch eine SVM führt einen Fehlerparametervektor ξ={ξi}n für die Bestimmung des Trennbereichs ein:

image-placeholder
(12-6)

Abbildung 2. Weicher Trennbereich einer SVM (Soft margin SVM). Durch ξ werden kleine Klassifikationsfehlerbereiche erlaubt. [4]

Multiklassen SVM

Jedes Multiklassenproblem mit m verschiedenen (diskreten) Klassenwerten kann auf m binäre Klassifikationsprobleme transformiert werden

Anders als bei ANN ist bei SVMs aber nur eine One-hot Kodierung möglich (ggfs. mit Softmaxfunktion).

ML Framework API für SVM

ML.learn({
    algorithm:ML.ML.SVM,
    x:number [][],
    y:number [],
    // threshold function on output? highest value of multi-svms is winner

    threshold:boolean,
    // default : 1.0. C in SVM.

    C : number,
    // default : 1e-4. Higher tolerance --> Higher precision

    tol : number,
    // default : 20. Higher max_passes --> Higher precision

    max_passes : number,
    // default : 1e-5. Higher alpha_tolerance --> Higher precision

    alpha_tol : number,
    kernel : { type: 'rbf', sigma: 0.5 }
    // { type: "polynomial", c: 1, d: 5}

}) → model

Beispiel

/webwork

data

data = [
  {
    "length":5.1,
    "width":3.5,
    "petal_length":1.4,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":4.7,
    "width":3.2,
    "petal_length":1.3,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":4.6,
    "width":3.1,
    "petal_length":1.5,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
    "length":5,
    "width":3.6,
    "petal_length":1.4,
    "petal_width":0.2,
    "species":"setosa"
  },
  {
...

prepro

// {}[] -> x:number[][], y:string [][]

dataN = ML.preprocess(
  data,
  'xmy',
  {
    features:['length','width','petal_length','petal_width'],
    target:['species']
  }
)
// Kodierung der y-Variable

dataN.y = dataN.y.map(function (row) {
  switch (row[0]) {
    case 'setosa': return [-1,-1,1];
    case 'versicolor': return [-1,1,-1];
    case 'virginica': return [1,-1,-1];
  }
});
models=[]
results=[]

train

var target = 0; // 0,1,2

models[target] = ML.learn({
    algorithm:ML.ML.SVM,
    x:dataN.x,
    y:dataN.y.pluck(target),
    threshold:false,  // no threshold function on output; highest value of svms is winner

    C : 15.0, // default : 1.0. C in SVM.

    tol : 1e-5, // default : 1e-4. Higher tolerance --> Higher precision

    max_passes : 200, // default : 20. Higher max_passes --> Higher precision

    alpha_tol : 1e-5, // default : 1e-5. Higher alpha_tolerance --> Higher precision

    kernel : { type: 'rbf', sigma: 0.5 } // { type: "polynomial", c: 1, d: 5}

})

test

var target = 0; // 0,1,2

results[target]=ML.predict(models[target],dataN.x).merge(dataN.y.pluck(target),'c')

[Sugiyama, ItSML, pp 303]

Zusammenfassung

Eine SVM wird als binärer Klassifikator verwendet und wird i.A. durch eine lineare Funktion (Kernel) repräsentiert

Das Problem sollte dann linear separierbar sein!

Multiklassenprobleme werden auf Multi-SVMs zurückgeführt

Verwendung einer Softmax Funktion für eindeutige Klassentrennung

Das Training einer SVM ist ein Minimierungsproblem dass den Trennbereich maximiert und den Fehler minimiert

Zustandsbasierte Netze

Bisher wurden nur "vorwärtsgerichtete" ANN betrachtet (Feed forward/ FF-ANN)

Die Ausgänge von FF-ANN hängen nur von aktuellen Eingängen ab!

Rückgekoppelte ANN (Recurrent / RNN) besitzen Zusatnd und Gedächtnis!

Eignung für Daten- und Zeitserienprädiktion!

Wiederholung: FF-ANN

Ein vorwärtsgekoppeltes ANN (Feed forward) besteht aus Neuronen die jeweils durch Funktionen f(i):i → o repräsentiert werden können.

Die Funktionen f werden als azyklischer gerichteter Graph dargestellt (also das NN), d.h., kein Neuron hat ein Eingangssignal von nachfolgenden Neuronen (die das Ausgangssignal dieses Neurons enthalten)

D.h: Das aktuelle Ausgangssignal y eine FF-ANN hängt nur von den aktuellen Eingangssignalen x ab!

Recurrent ANN: Die Rückkopplung

Ausgänge von Ausgangs- oder inneren Neuron werden auf Eingänge von vorherigen Neuronen gekoppelt

Dadurch werden die Netzwerke zustandsbasiert, d.h., die aktuellen Ausgänge hängen neben den aktuellen Werten der Eingänge von der Historie der Werte von Ein- und Ausgängen ab!

Recurrent ANN (RNN) sind durch hohe "Instabilität" schwierig mit gradientenbasierten Verfahren zu trainieren!

Daher im Laufe der Zeit verbesserte Architekturen wie LSTM oder GRU Netzwerke

LSTM Netzwerke

Long-short-term Memory (LSTM) Netzwerke bilden eine bekannte Architektur die:

Für die Daten- und zeitserienprädiktion verwendbar sind

Mit gradientenbasierten Trainingsverfahren einigermaßen stabil (konvergent) trainiert werden können

Daten- und Zeitserien

Es sei {xn}t eine Serie von Eingabedaten (z.B. zeitaufgelöstes Sensorsignal einer Ultraschallmessung), d.h. {xn}={x₁,x₂,..,xt}

Die einzelnen Werte (skalar oder vektoriell) sind aufeinanderfolgend → Ordnungsrelation

image-placeholder
(13-1)

Abbildung 1. Datenserie und Prädiktion *s*(*n*+δ)

Neben der Prädiktion von "zukünftigen" Entwicklungen einer Variable xi kann auch eine zukünftige Prognostik einer anderen Zielvariable yi erfolgen:

image-placeholder
(13-2)

Etwaige Zielvariablen könnten aus dem Signal abgeleitete Eigenschaften (Merkmale) sein:

Schadensinformation

Änderung einer zweiten Sensorvariable

Zustandsvariable

Veränderung von Betriebsbedingungen

Prozessparameter

Netzwerkarchitekturen

Abbildung 2. (Oben) Die Datenserie kann sequentiell (in ein RNN/LSTM) oder auch (Unten) parallel in ein FNN eingegeben werden

LSTM Zelle

Eine LST Zelle besteht aus:

Einer "Speicherzelle"

Mehreren Gattern die aktiv Verbindungen (Kanten) zwischen Neuronen steuern, d.h., effektiv das Kantengewicht in Abhängigkeit von Ausgangswerten von Neuronen verändern /Ventile/

Ein wichtige Rolle bei der Speicherung vergangener Daten (Gedächnis) ist das Vergessen gesteuert durch das "Forget Gate"

Beispiel für eine "gedämpfte" Gedächnisfunktion: Ein Tiefpassfilter 1. Ordnung

image-placeholder
(13-3)

Der Parameter β=(0,1) bestimmt den Einfluß neuer Werte x und der Parameter α=(0,1) bestimmt den Einfluß alter Werte (Vergessen); i.A. α=1-β

Abbildung 3. Aufbau einer LSTM Zelle mit zentraler Speicherzelle (Neuron) und den Gattern

LSTM Demo

Lernen einer Prädiktorfunktion für Datenserien nach der Sinusfunktion mit LSTM Netzwerk:

image-placeholder
(13-4)

Für jedes δ={1,2,..,m} muss eine eigene Prädiktorfunktion fδ erzeugt und trainiert werden

Konfiguration des Netzwerks: [1,*l*,1], wobei l={1,2,..} die Anzahl der LSTM Zellen in der inneren Schicht ist.

/webwork

data

delta=5;
dataI=Array.sequence(0,99);
dataX=Math.Matrix(100,2).map(function (v,i,j) {
  if (j==0) v=1+Math.sin((i)/5);
  else      v=1+Math.sin((i+delta)/5);
  return v/2;
});
dataN=ML.preprocess(dataX.data,'io',{ features:[0], target:[1] })
Plot({x:dataI,y1:dataX.pluck(0),y2:dataX.pluck(1)},{type:'line'})

model

model = ML.learner({
 algorithm : ML.ML.ANN,
 architect : 'LSTM',
 layers    : [1,1,1],
    // outputToMemory:true,

    //memoryToMemory:true,

    // outputToGates:true,

    // inputToOutput:false,

    // inputToDeep:false,

})

train

ML.train(model,
  dataN,
  {
      error    : 0.00001,
      rate     : 0.1,
      // ratePolicy:ML.ANN.methods.rate.STEP(0.9,100),

      momentum     : 0, // 0.5,

      iterations   : 10000,
      dropout      : 0,
      // shuffle:true,

      // batchSize : 20,

      clear:true,
      verbose: true,
      // crossValidate : { testSize: 0.2, testError: 0.0002 },

  });
print('Done. ('+model.time+' ms)')

test

var results = ML.predict(model,
                 dataX.pluck(0).wrap())
Plot({x:dataI,
      y1:results.unwrap(),
      y2:dataX.pluck(1)},{type:'line'})

Zusammenfassung

Diskrete Daten- und Zeitserien x(i) kommen in der Mess- und Prüftechnik als Sensorsignal häufig vor, aber auch bei

Wirtschaftsdaten (Aktienkurse), Wetterdaten, Klimadaten, usw.

Die Vorhersage von unbekannten zukünftigen Datenwerten aus historischen bekannten Datenwerten erfordert zustandsbasierte Prädiktorfunktionen sofern es

keinen ausgewiesenen Start- und Endpunkt gibt (also sequentielle Aktivierung von M).

Gibt es ausgewiesene Start- und Endpunkte der Serie kann auch eine zustandslose Prädiktorfunktion verwendet werden (parallele Aktivierung einer Auswahl von Datenpunkten)

Die Long Short Term Memory Zelle ist eine bekannte Architektur für eine RNN PF mit Zustand (Speicher)

Problem beim Trainieren von RNN ist Instabilität und der Zustandsspeicher (wirkt sich auf Fehlerberechnung ungünstig aus)

Rechnerarchitekturen für ML

Die Software für Implementierung der Modelle und Algorithmen ist stark verknüpft mit der Rechnerarchitektur

Performanzprobleme vor allem bei Training, aber auch bei Inferenz!

Parallelisierung kann die Performanz steigern

Effizienz: Optimierung von Rechenzeit + Speicherbedarf + Energie!

Rechnerklassifikation

Datenverarbeitung bedeutet die Verarbeitung eines Daten- und eines Instruktionsstromes (DS/IS)

Eine Datenverarbeitungsanlage enthält:

VE

Verarbeitungseinheit für Daten

SM

Speichermodul → (Static/Dynamic) RAM, Registerbank, Cache

KE

Kontrolleinheit für die Ablaufsteuerung, kann in VE enthalten sein.

Dabei sind diese drei Einheiten über Instruktionsströme und Datenströme gekoppelt:

Man kann grob Rechnerarchitekturen nach der Art der Verarbeitung des DS/IS und möglicher Parallelisierung klassifizieren ⇒ Flynn Klassifikation

SISD

Single-Instruction ⊗ Single-Data Stream

SIMD

Single-Instruction ⊗ Multiple-Data Stream

MISD

Multiple-Instruction ⊗ Single-Data Stream

MIMD

Multiple-Instruction ⊗ Multiple-Data Stream

Funktionale Dekomposition

Die Modelle lassen sich je nach Architektur und Aufbau funktional darstellen → Funktionale Komposition mit Datenfluss

Neuronales Netzwerk

Jedes Neuron N besteht aus zwei gekoppelten Funktionen Σ als Summierer und f als Transferfunktion:

image-placeholder
(14-1)

Das Netzwerk kann als eine große Funktion M(x) aus Funktionen (Neuronen einer Ebene sind zu einer Funktion L zusammengefasst) gebaut werden:

image-placeholder
(14-2)

Abbildung 1. Funktionale Dekomposition eines SLP (Neuron *N*)

Die Berechnung aller {Ni} Funktionen in einer Ebene Li kann parallel erfolgen!

Entscheidungsbäume

Auch ein Entscheidungsbaum kann funktional dargestellt werden durch geschachtelte konditionale Ausdrücke:

image-placeholder
(14-3)

image-placeholder
(14-4)

Matrixalgebra

Parallelisierung ist gut auf Probleme mit "Schleifeniterationen" anwendbar

Matrixalgebra zeigt inherente Parallelität in Matrixoperationen (häufig sequenziell durch Schleifeniteration verabeitet)

Neuronale Netze (i.A. mit regulärer Struktur) können durch Matrixalgebra abgebildet werden

Parallelisierung

Parallelisierung erfolgt auf der Daten- und Kontrollpfadebene

Kontrollpfadparallelität bedeutet Paritionierung einer Berechnung in separate Prozesse → Multiprocessing & Multithreading → Mehrprozessorechner (MCPU)

Datenpfadparallelität bedeutet die Belegung mehrerer Verarbeitungseinheiten (Rechenwerke) → GPU, FPGA, (CPU:MMX)

Inferenz

Bei Entscheidungsbäumen kann der Baum nur sequenziell berechntet werden (höchstens spekulativ mit parallelen Teilbäumen). Aber es gibt auch Multibäume (Random Forest). Diese können parallel berechnet werden.
Bei neuronalen Netzen können alle Neuronenfunktionen einer Ebene parallel berechnet werden.

Training

Bei Entscheidungsbäumen (Monobäumen) ist nur bei der Datenanalyse eine Parallelisierung möglich. Aber es gibt auch Multibäume (Random Forest). Diese können parallel erzeugt werden (mit gemeinsamer Datenanalyse).
Bei neuronalen Netzen ist Parallelisierung auf die Matrixalgebra anwendbar.

Berechnungskomplexität

Inferenz

Bei Entscheidungsbäumen hängt die Berechnungskomplexität nur noch von der Höhe des Baums (Anzahl der Ebenen) ab → Selektiv aktivierbare Teilberechnung (trivial, Berechnung einfacher Ausdrücke).
Bei neuronalen Netzen müssen i.A. alle Funktionen berechntet werden (Komplexität ist noch klein) und die Berechnung muss Datenabhängigkeiten beachten.

Training

Bei Entscheidungsbäumen müssen die Datenspalten vs. Parititionierung der Zielvariablen analysiert werden (also Rechenzeit ∝ |D||X|).
Bei neuronalen Netzen findet zunächst eine vollständig Berechnung aller Neuronenfunktionen statt (für alle Datensätze also Rechenzeit ∝ |D||NN|) und anschliessend werden alle Gewichte mit Fehlerfunktionen neu berechnet!
|D|: Anzahl der Dateninstanzen, |X|: Anzahl der Eingabevariablen, |NN|: Anzahl der Neuronen im KNN

Approximation

Tatsächlich ist jede Berechnung mit einem Digitalrechner eine Approximation!

Reelle Zahlen können nicht mit Digitalrechnern verarbeitet werden

Digitalrechner können nur ganze Zahle verarbeiten

Fliesskommaarithmetik ist tatsächlich Granzzahlrechnung mit einem "verschobenen" Komma

Unterschiedliche Datentypen und Rechenwerke benötigen unterschiedlichen Speicherbedarf

Daten: Float64 → 64 Bit / 8 Byte,
Rechenwerk (ALU): > 1M Logikgatter

Daten: Int16 → 16 Bit / 2 Byte,
Rechenwerk (ALU): ≈ 10k Logikgatter

Bei der Rechenzeit / Operation gab es früher großen Unterschied top(Float) ≫ top(Integer), heute gilt in modernen CPUs aber top(Float) ≈ top(Integer)

Bei der Berechnung, z.B. Matrixalgebra, spielt aber in heutigen Rechnerarchitekturen der Datenfluss die Hauptrolle → Speicherzugriff ist langsam!

Parallelisierungsgrad P

Die maximalze Anzahl von binären Stellen (bits) pro Zeiteinheit (Taktzyklus) die von einer Datenverarbeitungsanlage verarbeitet werden kann.

Es gilt: P = W • B

Wortlänge W

Die Wortlänge oder Wortbreite gibt die Anzahl der Bits eines Datenpfades an.

Bitslice-Länge B

Die Bitslice-Länge setzt sich zusammen aus der Anzahl von Verarbeitungseinheiten VE, die parallel ausgeführt werden können, und der Anzahl der Pipeline-Stufen einer VE.

Es gilt: B = NVE • NStages

Abbildung 2. Illustration Parallelisierungsgrad und Beispiel

Die Reduktion der Datenwortbreite bei Berechnungen bringt eine Steigerung der Verarbeitungsgeschwindigkeit wenn Datendurchsatz oder Ressourcen limitierende Faktoren sind!

Aber Reduktion der Datenwortbreite bedeutet approximatives Rechnen.

Hochparallele Verarbeitungsarchitekturen

Abbildung 3. Fein granulierte parallele DV auf Datenpfadebene mit Multi-ALU Architekturen [Sze,]

MACHINE LEARNING COMPUTE PLATFORMS

Abbildung 4. Metrik der Berechnungsplattformen für ML (CPU, GPU, DSP, FPGA, ASIC) [Moor]

Generische Prozessoren und Rechner

Berechnungen finden sequenziell statt:

Es gibt i.A. nur eine ALU (Rechenwerk)

Parallelität auf Kontrollpfadebene bei Mehrkern- oder Mehrprozessorrechnern möglich

Skalierbarkeit im Bereich [1.5,0.8*N*] bei N ≥ 2 Prozessoren/Kernen

Wichtig: Mehrkernrechner nutzen einen geteilten Speicher (DRAM). Speicherhierarchie beachten!

Der L2/L1 Cache ist wesentlich für die Rechenleistung (Ops/s)

Grafikprozessoren

Eine GPU entspricht der MIMD Klasse.

Aber: GPUs sind keine generischen Rechneranlagen sondern sind auf Grafikoperation (häufig Matrixalgebra) spezialisiert! (Aber: Übergang zu GPGPU Arch.)

Eine GPU-Einheit besteht aus:

mehreren Prozessorclustern (PC), die

mehrere Streaming-Multiprozessoren (SM) enthalten.

Jede SM hat eine Layer-1-Befehls-Cache-Schicht mit den zugehörigen Kernen.

In der Regel verwendet ein SM einen L1-Cache und einen gemeinsam genutzten L2-Cache

Seine Architektur ist tolerant gegenüber Speicherlatenz.

Häufig reduzierte Rechenauflösung ("Float16")

[nielshagoort.com/2019/03/12/exploring-the-gpu-architecture/]

Vergleich CPU mit GPU Architektur

Abbildung 5. CPU sind kontrollpfadorientier, GPU sind datenpfadorientiert

Digitallogik und FPGA

FPGA: Field Programmable (Logic) Gate Array

Funktionale Systeme können 1:1 unter Ausnutzung maximaler Parallelität auf Digitallogiksysteme abgebildet werden

Aber Fliesskommarithmetik erfordert großen Ressourcenbedarf (Multi-ALU Architekturen nur begrenzt möglich)

Daher Übergang auf Ganzzahlarithmetik und Intervallartihmetik (bzw. Festpunktarithmetik)!

Ein FPGA kann (1) Algorithmen und (2) funktionale Modelle implementieren

Abbildung von Algorithmen (wie z.B. Gleichungslöser, Regler, FFT, usw.) ermöglicht beschleunigte Berechnung des Algorithmus → Lernalgrotihmen werden i.A. nicht auf FPGAs übertragen!

Abbildung von Funktionsmodellen hier das ANN und deren Berechnung (Vorwärtspropagation) auf FPGA

Problem: Training mit Backpropagation außerhalb i.A. mit CPU

Daher besser Übertragung eines in Software trainierten Modells auf die Hardware (d.h. nur für Inferenz)

Aber: Ein mit "Float64" trainiertes Modell muss auf Ganzzahlarithmetik "Int16" transformiert werden und kann u.U. schlechte Ergebnisse ergeben!

Daher schon Training mit Zieldatenformat und Einführung von speziellen approximativen Berechnungen (d.h. Übersetzung)

Generische KNN-FPGA Architekturen

Bisher sind die Implementierungen von KNN in FPGA problemspezifisch

Generische Architekturen wären problemspezifisch konfigurierbar

Dazu müssen die Elementaroperationen und Verbindungselemente eines KNN in einem FPGA frei konfigurierbar implementiert werden

Ein spezifisches KNN wird dann im FPGA durch Verbindung und Konfiguration der Elementarblöcke individuell angepasst

Abbildung 6. Die FPGA Blöcke bilden Elementaroperationen von KNN ab [Hao,]

Zusammenfassung

Abbildung 7. Taxonomie der Hardwarearchitekturen für KNN: Fexibilität vs. Effizienz [Jawandhiya,]

Referenzen

Bücher

M. J. Zaki and W. Meira, Data Mining and Machine Learning - Fundamental Concepts and Algorithms. Cambridge University Press, 2020.

C. R. Farrar and K. Worden, Structural Health Monitoring: A Machine Learning Perspective. Wiley-Interscience, 2013.

X.-S. Yang, Introduction to Algorithms for Data Mining and Machine Learning. Elsevier, 2019.

M. Sugiyama, Introduction to Statistical Machine Learning. 2016.

J. Herrmann, Maschinelles Lernen und Wissensbasierte Systeme. Springer, 1997.

R. Zafarani, M. A. Abbasi, and H. Liu, Social Data Mining. 2014.

I. H. Witten, E. Frank, M. A. Hall, and C. J. Pal, Data Mining Practical Machine Learning Tools and Techniques. Morgan Kaufmann.

C. Borcea, M. Talasila, and R. Curtmola, Mobile Crowdsensing. CRC Press, 2017.

J. G. Webster, Measurement, Instrumentation and Sensors Handbook, no. 0. 1999.

L. Rokach and O. Maimon, Data Mining with Decision Trees - Theory and Applications. World Scientific Publishing, 2015.

N. J. Nilsson, Introduction To Machine Learning. 1996.

T. M. Mitchel, Machine Learning. McGraw Hill, 1997.

P. Attewell and D. B. Monaghan, Data mining for the social sciences : an introduction. University of California Press, 2015.

J. R. Quinlan, “Induction of Decision Trees,” in Machine Learning, Kluwer Academic Publishers, Boston, 1986

M. T. Hagan, howard B. Demuth, M. H. Beale, and O. D. Jesus, Neural Network Design.

L. Fausett, Fundamentals of Neural Networks. 1994.

E. Alpaydın, Introduction to Machine Learning. MIT Press, 2010.

Artikel

T. Mueller, A. G. Kusne, and R. Ramprasad, “Machine learning in materials science: Recent progress and emerging applications,” Reviews in Computational Chemistry, Volume 29, First Edition., 2016.

N.-C. Chen et al., “Challenges of Applying Machine Learning to Qualitative Coding.”

J. Radford, K. Joseph, "Theory In, Theory Out: The Uses of Social Theory in Machine Learning for Social Science", Front. Big Data

Abadi et al., "TensorFlow: A system for large-scale machine learning", 2th USENIX Symposium on Operating Systems Design and Implementation, USENIX Association