Formel- und Algorithmensammlung

Kompakte Sammlung aller Formeln und Algorithmen aus den EKI-Kapiteln (Hochschule Darmstadt) - direkt aus den Kapiteltexten uebernommen, ohne Erfindungen.

Formeln

EKI02 - Maschinelles Lernen: Klassifikation

$$H(M) = \sum_{i=1}^{n} -c_i \cdot \log_2(c_i) \quad \text{mit} \quad \sum_{i=1}^{n} c_i = 1$$

Entropie einer Menge $M$; $c_i$ = relativer Anteil der Klasse $i$. Maximal bei 50/50, 0 bei reiner Klasse.

$$\text{Gewinn} = H(T) - \frac{|T_{lower}|}{|T|}\cdot H(T_{lower}) - \frac{|T_{upper}|}{|T|}\cdot H(T_{upper})$$

Entropieverlust (Information Gain) eines Splits "Feature < Wert"; $T$ = Ausgangsmenge, $T_{lower}/T_{upper}$ = Teilmengen. Split mit groesstem Verlust waehlen.

EKI03 - Maschinelles Lernen: Regression

$$\text{Treffergenauigkeit} = \frac{TP + TN}{TP + TN + FP + FN}$$

Accuracy = Anteil korrekter Vorhersagen; TP/TN/FP/FN aus der Konfusionsmatrix.

$$\text{precision} = \frac{TP}{TP + FP}$$

Positiver Vorhersagewert; Anteil der als positiv Klassifizierten, die auch positiv sind.

$$\text{recall} = \frac{TP}{TP + FN}$$

Trefferquote (true positive rate); Wahrscheinlichkeit, einen Positiven auch zu erkennen.

$$F\text{ Score} = \frac{2}{\left(\dfrac{1}{\text{precision}}\right) + \left(\dfrac{1}{\text{recall}}\right)} = 2 \cdot \frac{\text{precision} \cdot \text{recall}}{\text{precision} + \text{recall}}$$

Harmonisches Mittel von precision und recall; besser als Accuracy bei unausgewogenen Datensaetzen.

$$\text{Negative Predictive Value } NPV = \frac{TN}{FN + TN} \qquad \text{specificity} = \frac{TN}{FP + TN}$$

NPV = Anteil korrekter Negativvorhersagen; Specificity = Anteil erkannter tatsaechlich Negativer.

$$MAE = \frac{1}{n} \sum_{i=1}^{n} \left| \hat{f}_i - y_i \right|$$

Mean Absolute Error; $\hat{f}_i$ = Vorhersage, $y_i$ = wahrer Wert, $n$ = Anzahl Faelle.

$$MSE = \frac{1}{n} \sum_{i=1}^{n} \left( \hat{f}_i - y_i \right)^2$$

Mean Squared Error; bestraft grosse Fehler staerker.

$$RMSE = \sqrt{\frac{1}{n} \sum_{i=1}^{n} \left( \hat{f}_i - y_i \right)^2}$$

Rooted MSE; hat die gleiche Einheit wie die Zielgroesse.

$$\text{Performance} = \frac{1}{k} \sum_{i=1}^{k} \text{Performance}_i$$

k-fache Kreuzvalidierung: Mittelwert der Guete ueber alle $k$ Iterationen.

EKI06 - Computer Vision

$$sum = \sum_i in_i \cdot w_i$$

Gewichtete Summe der Eingaenge eines Neurons; $in_i$ = Eingang, $w_i$ = Gewicht; $in_0=1, w_0=bias$.

$$out = \frac{1}{1 + e^{-sum}}$$

Aktivierung des Neurons mit der Sigmoid-Funktion; $out$ = Ausgabe (Axon-Signal).

$$f(x) = \frac{1}{1 + e^{-x}} \qquad f'(x) = f(x)\,\bigl(1 - f(x)\bigr)$$

Sigmoid-Funktion und ihre Ableitung; die Ableitung wird in der Backpropagation gebraucht.

$$Fehler = Cost(W;\cdot) = \sum_i (target - out)^2$$

Kostenfunktion = Summe der quadrierten Abweichungen zwischen Ziel- und Ist-Ausgabe.

$$- \eta \cdot \nabla Cost(\dots)$$

Gradientenabstieg: Gewichtsanpassung in Richtung des negativen Gradienten; $\eta$ = Lernrate.

$$e = \sum_i (target_i - out_i)^2 \qquad \Delta_i = f'(sum_i)\cdot(target_i - out_i)$$

Backpropagation Schritte 2/3: Fehler und Korrekturwert $\Delta_i$ eines Neurons der letzten Schicht.

$$\Delta_i = f'(sum_i)\cdot \sum_j w_{i,j}\cdot \Delta_j$$

Backpropagation Schritt 4: Korrekturwert eines Neurons $i$ aus den Deltas $\Delta_j$ der nachfolgenden Schicht.

$$w_{j,i} = w_{j,i} + \eta \cdot \Delta_i \cdot out_j$$

Backpropagation Schritt 5: Gewichtsupdate mit Lernrate $\eta$, Delta $\Delta_i$ und Ausgabe $out_j$ des Vorgaengerneurons.

$$O = N - F + 1$$

Ausgabegroesse einer Faltung bei Eingabegroesse $N$, Filtergroesse $F$, Schrittweite $S=1$ ohne Padding (ergaenzend, nicht Teil des Decks). Beispiel: $O = 5 - 3 + 1 = 3$ (5x5-Bild mit 3x3-Filter -> 3x3 feature map).

EKI07 - Natural Language Processing

$$\text{tfidf}(t, d, D) = \text{tf}(t, d) \cdot \text{idf}(t, D)$$

Gewicht eines Terms $t$ in Dokument $d$ des Korpus $D$; Produkt aus Worthaeufigkeit und inverser Dokumenthaeufigkeit.

$$\text{idf}(t, D) = \log \frac{N}{|\{d \in D : t \in d\}|}$$

Inverse Dokumenthaeufigkeit; $N = |D|$ = Anzahl Dokumente, Nenner = Zahl der Dokumente, die $t$ enthalten (df).

EKI05 - Complex Event Processing

$$7\,\text{inc} = \sum_{i=1}^{7} inc_i \cdot \frac{100{,}000}{\text{population}}$$

7-Tage-Inzidenz ueber ein 7-Tage Sliding Window; Summe der Tagesinzidenzen $inc_i$, normiert auf 100.000 Einwohner (Population Singapur ca. 5,686 Mio.).

$$crit(7\,\text{inc}) = \begin{cases} 4 & \text{falls } 7\,\text{inc} > 400 \\ 3 & \text{sonst falls } 7\,\text{inc} > 200 \\ 2 & \text{sonst falls } 7\,\text{inc} > 100 \\ 1 & \text{sonst falls } 7\,\text{inc} > 50 \\ 0 & \text{sonst} \end{cases}$$

Beispiel-Definition der Kritikalitaet als Stufenfunktion der 7-Tage-Inzidenz.

$$7\,\text{crit} = \min_{i=1}^{7} \bigl( crit(7\,\text{inc}_i) \bigr)$$

7-Tage-Kritikalitaets-Score als Minimum der Kritikalitaeten der letzten 7 Tage (glaettende Bewertung).

EKI09 - Unsupervised Learning

$$\mathrm{Varianz}(x) = \frac{1}{n-1} \sum_{i} (x_i - \bar{x})^2$$

Varianz eines Features $x$; $\bar{x}$ = Mittelwert, $n$ = Anzahl Datenpunkte. Basis der PCA (Varianz = Information).

$$V_n = 1 \qquad d_n = \sqrt{n} \qquad V([0,2]^n) = 2^n$$

Curse of Dimensionality (R. Bellman): Einheitsobjekt hat Volumen 1, aber Raumdiagonale $\sqrt{n}$; Volumen waechst exponentiell.

$$\phi(x) = R\,x$$

Zufallsprojektion von $\mathbb{R}^p$ nach $\mathbb{R}^d$ mit einer zufaelligen Matrix $R \in \mathbb{R}^{p \times d}$.

$$d(x, y) = \| x - y \|_2 = \sqrt{ \sum_{i=1}^{p} (x_i - y_i)^2 }$$

Euklidischer Abstand zweier Punkte $x, y \in \mathbb{R}^p$; Distanzmass von k-Means.

$$x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}}$$

Min-Max-Normalisierung auf $[0,1]$; noetig vor k-Means, damit keine Skala dominiert.

$$C_i = \left\{ X_j : \| X_j - m_i \|^2 = \min_{p=1,\ldots,k} \| X_j - m_p \|^2 \right\}$$

k-Means Zuordnung: jeder Punkt $X_j$ kommt in das Cluster mit naechstem Zentrum $m_i$.

$$m_i = \frac{1}{|C_i|} \sum_{X_j \in C_i} X_j$$

k-Means Update des Zentroids $m_i$ als Mittelwert der zugeordneten Punkte.

$$D(X) = \min_{i=1,\ldots,j-1} \| X - m_i \|$$

k-Means++: Abstand eines Punktes $X$ zum naechsten bereits gewaehlten Zentrum.

$$P(X_j) = \frac{D^2(X)}{\displaystyle\sum_{i=1}^{n} D^2(X_i)}$$

k-Means++: Wahrscheinlichkeit, $X$ als naechstes Zentrum zu waehlen (proportional zu $D^2$).

$$M\,x = \lambda\,x, \qquad x \neq 0$$

PCA-Eigenwertgleichung; $M$ = Kovarianzmatrix, $x$ = Eigenvektor (Hauptkomponente), $\lambda$ = Eigenwert (erklaerte Varianz).

Algorithmen (Pseudocode)

Entscheidungsbaum-Aufbau (Information Gain) - EKI02

buildTree(T):
  wenn alle Labels in T gleich (H(T) = 0) oder Abbruchkriterium:
     erzeuge Blatt mit der (Mehrheits-)Klasse und return

  bestGain    = -unendlich
  bestFeature = keines
  bestWert    = keiner

  fuer jedes Feature f:
     fuer jeden Schwellwert v (Split "f < v"):
        T_lower = { Datensaetze in T mit f < v }
        T_upper = { Datensaetze in T mit f >= v }
        Gewinn  = H(T)
                - (|T_lower| / |T|) * H(T_lower)
                - (|T_upper| / |T|) * H(T_upper)
        wenn Gewinn > bestGain:
           bestGain, bestFeature, bestWert = Gewinn, f, v

  erzeuge inneren Knoten mit Bedingung (bestFeature < bestWert)
  buildTree(T_lower)   // rekursiv fuer Ja-Zweig
  buildTree(T_upper)   // rekursiv fuer Nein-Zweig

k-fache Kreuzvalidierung - EKI03

1. Spalte den Datensatz in k Teildatensaetze (Folds) auf, z.B. k = 5.
2. Fuehre das Training mit k-1 Teildatensaetzen durch und benutze
   1 Teildatensatz fuer die Validierung.
3. Iteriere k-mal, jeweils mit einem anderen Teildatensatz zur
   Validierung -> Performance(1), ..., Performance(k).
4. Berechne das durchschnittliche Ergebnis ueber alle Iterationen:
      Performance = (1/k) * SUM_{i=1..k} Performance_i

k-Means - EKI09

1. Waehle zufaellig k Datensaetze als initiale Clusterzentren
   m_1, ..., m_k.

2. Ordne jeden Datensatz demjenigen Cluster zu, dessen Zentrum am
   naechsten liegt (kleinster euklidischer Abstand):
      C_i = { X_j : ||X_j - m_i||^2 = min_{p=1..k} ||X_j - m_p||^2 }

3. Berechne fuer jedes Cluster sein Zentrum neu als Mittelwert der
   zugeordneten Punkte:
      m_i = (1 / |C_i|) * SUM_{X_j in C_i} X_j

4. Wiederhole Schritte 2 und 3, bis sich die Clusterzentren nicht
   mehr veraendern (Konvergenz).

k-Means++ Initialisierung - EKI09

1. Waehle (gleichverteilt) ein zufaelliges Clusterzentrum m_1 aus dem
   Datensatz.

Fuer j = 2, ..., k:
   2. Bestimme fuer jeden Punkt X den Abstand zum naechsten bereits
      bekannten Clusterzentrum:
         D(X) = min_{i=1..j-1} ||X - m_i||

   3. Waehle das naechste Clusterzentrum m_j aus allen Punkten mit einer
      Wahrscheinlichkeit proportional zu D^2(X):
         P(X_j) = D^2(X) / SUM_{i=1..n} D^2(X_i)

(Danach: normales k-Means mit Zuordnung und Zentroid-Update.)

PCA (5 Schritte) - EKI09

1. Normalisiere (zentriere) die Features, sodass der Erwartungswert
   (Mittelwert) jedes Features null ist.
2. Berechne aus den n normalisierten Features die Kovarianzmatrix.
   -> symmetrische n x n Matrix
3. Berechne die n Eigenvektoren dieser Matrix und ihre zugehoerigen
   Eigenwerte:   M x = lambda x,  x != 0
4. Sortiere die Eigenvektoren nach absteigender Groesse ihrer Eigenwerte.
5. Bilde Linearkombinationen aus den Bestandteilen der Eigenvektoren
   und der Features:
     - Eigenvektor mit groesstem Eigenwert      -> Koeffizienten a_i -> PC1
     - Eigenvektor mit zweitgroesstem Eigenwert -> Koeffizienten b_i -> PC2
     - ...
     - Eigenvektor mit kleinstem Eigenwert      -> letzte Hauptkomponente

Backpropagation (Schritte) - EKI06

1. Leite die Trainingsdaten vorwaerts durch das Netzwerk:
      sum_i = SUM_j in_j * w_{j,i}
      out_i = 1 / (1 + e^{-sum_i})
2. Berechne den Fehler zwischen tatsaechlicher und gewuenschter Ausgabe
   in der letzten Schicht:
      e = SUM_i (target_i - out_i)^2
3. Berechne fuer jedes Neuron der letzten Schicht seinen Korrekturwert:
      Delta_i = f'(sum_i) * (target_i - out_i)
4. Iteriere rueckwaerts bis zur Eingabeschicht; nutze die Deltas der
   naechsten Schicht:
      Delta_i = f'(sum_i) * SUM_j w_{i,j} * Delta_j
5. Korrigiere jedes Gewicht mit dem zugehoerigen Korrekturwert:
      w_{j,i} = w_{j,i} + eta * Delta_i * out_j

CEP Sliding-Window-Auswertung - EKI05

Fuer jede neue Fensterposition (Sliding Window der Dauer n,
Versatz m):

1. Betrachte die juengsten n Ereignisse des Stroms
   (aktuelles Fenster).
2. Werte die persistente Regel ueber diesem Fenster aus, z.B.
   7-Tage-Inzidenz:
      7 inc = SUM_{i=1..7} inc_i * 100000 / population
3. Leite (iterativ) ein hoeheres Ereignis ab, z.B. Kritikalitaet:
      crit(7 inc) = 4 falls 7 inc > 400
                    3 sonst falls 7 inc > 200
                    2 sonst falls 7 inc > 100
                    1 sonst falls 7 inc > 50
                    0 sonst
      7 crit = min_{i=1..7} ( crit(7 inc_i) )
4. Gib das Ausgabeereignis aus (decision support); es kann erneut
   als Eingabe dienen (low-level -> high-level).
5. Ruecke das Fenster um m weiter und wiederhole.

Verweise

• EKI02
• EKI03
• EKI05
• EKI06
• EKI07
• EKI09