Eigenes KNN mit Python

Wir bauen ein eigenes KNN mit Python. Der Einfachheit halber beschränken wir uns aber auf ein KNN bestehend aus einem einzigen Neuron. Trotzdem können wir die Funktionsweise eines KNN so veranschaulichen. Wir beziehen uns dabei auf einen Artikel von Milo Spencer-Harper.

Ziel

Unser Neuron soll 3 Eingänge und einen Ausgang haben. Wir trainieren das Neuron mit 4 Beispielen und schauen, ob es bei einem unbekannten Input das gewünschte Ergebnis liefert.

Input Output
Beispiel 1 0 0 1 0
Beispiel 2 1 1 1 1
Beispiel 3 1 0 1 1
Beispiel 4 0 1 1 0
unbekannt 1 0 0 ?
Trainings-Set und unbekannte Situation

Bemerkst du eine Abhängigkeit zwischen den Inputs und den Outputs der 4 Beispiele? Wie müsste der Output des unbekannten Inputs sein? 0 oder 1?

Trainieren

Jeder Eingang des Neurons erhält ein Gewicht, eine positive oder negative Zahl. Je grösser die Zahl (negativ oder positiv), umso grösser der Effekt dieses Inputs auf den Output. Zu Beginn setzen wir die Gewichte auf Zufallswerte. Dann starten wir das Training:

  1. Nimm die Inputs des «Training Sets» (die 4 Beispiele), multipliziere sie mit den Gewichten und füttere sie der Formel für den Output des Neurons.
  2. Berechne den Error, also die Differenz zwischen dem berechneten und dem gewünschten Output.
  3. Je nach Richtung der Abweichung, passe die Gewichte ein klein bisschen an.
  4. Wiederhole das Ganze 10'000 Mal.

Irgendwann erreichen die Gewichte optimale Werte für das Trainings-Set. Wenn wir das Neuron jetzt über eine unbekannte Situation nachdenken lassen, welche einem ähnlichen Muster folgt, sollte es eine gute Vorhersage machen können.

Formel für den Output des Neurons

Die Formeln nimmt zuerst die gewichtete Summe der Inputs des Neurons:

\[ \sum_{i=1}^{3} weight_i \cdot input_i = weight_1 \cdot input_1 + weight_2 \cdot input_2 + weight_3 \cdot input_3\]

Gewichtete Summe aller Inputs

Dieses Ergebnis wird normalisiert, so dass es immer zwischen 0 und 1 liegt. Dafür verwenden wir die Sigmoid-Funktion:

\[ f(x) = \frac{1}{1 + e^{-x}}\]

Sigmoid-Funktion
Graph der Sigmoid-Funktion

Wenn wir also die gewichtete Summe in die Sigmoid-Funktion einsetzen erhalten wir:

\[ \text{Output des Neurons} = \frac{1}{1 + e^{-\sum weight_i \cdot input_i }}\]

Formel für die Anpassung der Gewichte

Während des Trainings werden die Gewichte angepasst. Auch dafür brauchen wir eine Formel:

\[ \text{Anpassung Gewichte} = error \cdot input \cdot SigmoidCurveGradient(output)\]

Durch diese Formel erreichen wir, dass die Anpassung proportional zur Fehlergrösse ist. Dann multiplizieren wir durch den Input der 0 oder 1 ist. Bei Input 0 werden die Gewichte nicht angepasst. Schlussendlich multiplizieren wir mit der Steigung der Sigmoid-Kurve. Dies tun wir aus den folgenden Gründen:

  1. Wir haben die Sigmoid-Funktion bereits für die Berechnung des Outputs verwendet.
  2. Wenn der Output eine grosse negative oder positive Zahl ist, bedeutet das dass das Neuron sich ziemlich sicher ist.
  3. Aus dem Graph der Sigmoid-Funktion erkennen wir, dass bei grossem x die Steigung sehr gering ist.
  4. Wenn sich das Neuron über den Output sehr sicher ist, dann sollte nur sehr wenig geändert werden. Dies wird durch die Multiplikation mit der Steigung der Sigmoid-Kurve erreicht.

Die Steigung der Sigmoid-Kurve kann mit der Ableitung der Sigmoid-Funktion berechnet werden:

\[ SigmoidCurveGradient(output) = output \cdot (1-output)\]

Also erhalten wir die folgende Funktion um die Änderung der Gewichte zu berechnen:

\[ \text{Anpassung Gewichte} = error \cdot input \cdot output \cdot (1-output)\]

Python-Code erstellen

Wir bauen unser KNN ohne spezialisierte Bibliotheken. Wir verwenden aber 4 Funktionen aus der mathematischen Bibliothek «numpy»:

  • exp – Exponentialfunktion \(e^x\)
  • array – erzeugt eine Matrix
  • dot – multipliziert Matrizen
  • random – erzeugt Zufallszahlen

Zum Beispiel können wir die array-Funktion verwenden um das Trainings-Set darzustellen:

training_set_inputs = array([[0, 0, 1], [1, 1, 1], [1, 0, 1], [0, 1, 1]])
training_set_outputs = array([[0, 1, 1, 0]]).T

Die T-Funktion in der zweiten Zeile «transponiert» die Matrix, d.h. sie dreht die Matrix von «horizontal» auf «vertikal». Der Computer speichert die Werte also wie folgt:

\[ \text{training_set_inputs} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \qquad \text{training_set_outputs} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}\]

Hier folgt nun also der kommentiere Code:

from numpy import exp, array, random, dot

class NeuralNetwork():
    def __init__(self):
        # Den Zufallsgenerator in einen bestimmten Zustand stellen.
        # Bei jeder Programm-Ausführung werden die selben Zufallszahlen generiert.
        random.seed(1)

        # Wir modellieren ein einzelnes Neuron bestehend aus 3 Eingängen und einem Ausgang.
        # Wir erstellen eine 3x1-Matrix bestehend aus zufälligen Werten und
        self.synaptic_weights = 2 * random.random((3, 1)) - 1

    # Die Sigmoid-Funktion, welche unsere S-förmige Kurve beschreibt.
    # Wir füttern ihr die gewichtete Summe der Inputs, damit diese normalisiert wird.
    def __sigmoid(self, x):
        return 1 / (1 + exp(-x))

    # Die Ableitung deer Sigmoid-Funktion.
    # Dies stellt die Steigung der Sigmoid-Kurve dar.
    def __sigmoid_derivative(self, x):
        return x * (1 - x)

    # Wir trainieren das KNN durch trial and error.
    # Dabei passen wir die Gewichte jeweils entsprechen an.
    def train(self, training_set_inputs, training_set_outputs, number_of_training_iterations):
        for iteration in range(number_of_training_iterations):
            # Wir füttern unserem Neuron das Trainings-Set.
            output = self.think(training_set_inputs)

            # Wir berechnen den Error.
            # (Die Abweichung des berechneten zum gewünschten Outputs)
            error = training_set_outputs - output

            # Multiplizieren densError mit dem Input und der Steigung der Sigmoid-Kurve.
            # Das heisst: weniger sichere Gewichte werden stärker angepasst.
            # Das heisst: Inputs welche 0 sind, führen zu keinen Änderungen der Gewichte.
            adjustment = dot(training_set_inputs.T, error * self.__sigmoid_derivative(output))

            # Anpassung der Gewichte.
            self.synaptic_weights += adjustment

    # Umser KNN denkt.
    def think(self, inputs):
        # Gib die Inputs durch unsere KNN (unserem einzelnen Neuron).
        return self.__sigmoid(dot(inputs, self.synaptic_weights))

if __name__ == "__main__":

    # Initialisiere ein KNN mit einem einzelnen Neuron.
    neural_network = NeuralNetwork()

    print("Zufällig gewählte Gewichte: ")
    print(neural_network.synaptic_weights)

    # Unser Training Set bestehend aus 4 Beispielen.
    # Jedes besteht aus 3 Werten und einem Output-Wert.
    training_set_inputs = array([[0, 0, 1], [1, 1, 1], [1, 0, 1], [0, 1, 1]])
    training_set_outputs = array([[0, 1, 1, 0]]).T

    # Trainiere unser KNN mit dem Trainings-Set.
    # 10'000 Durchläufe mit kleinen Anpassungen der Gewichte.
    neural_network.train(training_set_inputs, training_set_outputs, 10000)

    print("Gewichte nach dem Training: ")
    print(neural_network.synaptic_weights)

    # Wende das KNN auf eine unbekannte Situtation an.
    print("unbekannte Situation: [1, 0, 0] -> ?: ")
    print(neural_network.think(array([1, 0, 0])))

Ergebnis

Wenn wir das Programm ausführen sollten wir den folgenden Output erhalten:

Zufällig gewählte Gewichte: 
[[-0.16595599]
 [ 0.44064899]
 [-0.99977125]]
Gewichte nach dem Training: 
[[ 9.67299303]
 [-0.2078435 ]
 [-4.62963669]]
unbekannte Situation: [1, 0, 0] -> ?: 
[0.99993704]

Unser KNN funktioniert!

Zuerst weist sich das KNN zufällige Gewichte zu, dann werden die Gewichte in der Trainingsphase angepasst. Am Schluss wird die unbekannte Situation [1,0,0] mit 0.99993704 vorhergesagt, was ja sehr nahe beim korrekten 1 ist.