Neuronales Netz in Go

Im ersten Teil haben wir uns mit der Zielsetzung und der Zerlegung der Eingangsdaten beschäftigt, der zweite Teil hat das neuronale Netz theoretisch beschrieben. Der dritte Teil besteht aus Quellcode: In rund 300 Zeilen wird das neuronale Netz erstellt, trainiert und getestet.

main.go

package main

import (
   "bufio"
   "fmt"
   "log"
   "os"
)

var Neurons [32]NeuronType

func main() {
   Init()

   // Create and init the neurons
   for i, _ := range Neurons {
      Neurons[i] = NewNeuron()
   }

   // Analyse a sample word
   data := NewData("Autobahn")

   // Show the results of the untrained neurons
   for i, n := range Neurons {
      log.Printf("Neuron %d: %v", i, n.Rate(data))
   }

   // Read garbage created using "pwgen" and a dictionary as training
   trainFile("garbage.txt", false)
   trainFile("de.txt", true)
   trainFile("garbage.txt", false)
   trainFile("de.txt", true)
   trainFile("garbage.txt", false)
   trainFile("de.txt", true)
   trainFile("garbage.txt", false)
   trainFile("de.txt", true)
   trainFile("garbage.txt", false)
   trainFile("de.txt", true)

   // Rate the sample word again and show the results of the trained neurons
   for i, n := range Neurons {
      log.Printf("Neuron %d: %v", i, n.Rate(data))
   }

   // Rate some additional samples and show the overall (voting) result
   for _, w := range []string{"Auto", "garbage", "as9Boo", "lae5uZee", "Be5Eirae", "igieng5I", "1.11.2011"} {
      fmt.Printf("%v: %v\n", w, rate(w))
   }

   // Use the training files and show the success rate of each
   var hit int
   inFile, _ := os.Open("de.txt")
   defer inFile.Close()
   scanner := bufio.NewScanner(inFile)
   scanner.Split(bufio.ScanLines)
   for scanner.Scan() {
      if rate(scanner.Text()) > 0 {
         hit++
      }
   }
   log.Print(hit)

   hit = 0
   inFile, _ = os.Open("garbage.txt")
   defer inFile.Close()
   scanner = bufio.NewScanner(inFile)
   scanner.Split(bufio.ScanLines)
   for scanner.Scan() {
      if rate(scanner.Text()) < 0 {
         hit++
      }
   }
   log.Print(hit)
}

// Reads a file containing ham or spam and trains the net
func trainFile(filename string, expected bool) {
   inFile, _ := os.Open(filename)
   defer inFile.Close()
   scanner := bufio.NewScanner(inFile)
   scanner.Split(bufio.ScanLines)
   for scanner.Scan() {
      train(scanner.Text(), expected)
   }
}

// Trains the network using one given word
func train(w string, expected bool) {
   data := NewData(w) // Analyze

   var bestNeutron int = -1
   var bestResult float32
   var votes int

   // Let each neuron vote for or against the word
   for i, n := range Neurons {
      r := n.Rate(data)

      if r > 0 {
         votes++
      } else if r < 0 {
         votes--
      }

      // Remember the best-of-the-worse
      if (r > 0 && !expected) || (r < 0 && expected) {
         if expected {
            if (bestResult == 0) || (r > bestResult) {
               bestNeutron = i
               bestResult = r
            }
         } else if !expected {
            if (bestResult == 0) || (r < bestResult) {
               bestNeutron = i
               bestResult = r
            }
         }
      }
   }

   if (votes > 0 && expected) || (votes < 0 && !expected) {
      // Neurons decision was correct, nothing to do
      return
   }

   // Neurons failed, train the best of the worst
   if bestNeutron >= 0 {
      // log.Printf("Best fail is %v", bestNeutron)
      Neurons[bestNeutron].Train(data, expected)
   }
}

// Rate a word and return the voting result
func rate(w string) int {
   data := NewData(w)

   var votes int

   for _, n := range Neurons {
      r := n.Rate(data)

      if r > 0 {
         votes++ // Looks like a word
      } else if r < 0 {
         votes-- // Looks like garbage
      }
   }

   return votes

}

neuron.go

package main

import (
   "fmt"
   "math/rand"
   "strings"
)

const Charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ."

var CharCode = make(map[int32]int)

// Consonants/Vowels map
var isVowel = map[int32]bool{
   65: true,  // A
   66: false, // B
   67: false, // C
   68: false, // D
   69: true,  // E
   70: false, // F
   71: false, // G
   72: false, // H
   73: true,  // I
   74: false, // J
   75: false, // K
   76: false, // L
   77: false, // M
   78: false, // N
   79: true,  // O
   80: false, // P
   81: false, // Q
   82: false, // R
   83: false, // S
   84: false, // T
   85: true,  // U
   86: false, // V
   87: false, // W
   88: false, // X
   89: false, // Y
   90: false, // Z
}

/*
Attributes:
    0 -   19   Length (one item per possible length)
   20 -   20   Consonants/Vowels rate (consonants / length)
   21 -   40   Char at this position is non-char/number
   41 - 1484   2-Char combination count (charset: A-Z, 0-9, " ", ".") = 38²
 1485 - 2244   Char position bits (A1 ... A20, B1 ... B20, ..., "."1 ... "."20)
*/
type NeuronType struct {
   Weights   [2244]float32 // Weight per attribute
   MinWeight float32       // Minimum weight sum to return true
}

// Input data
type NeuronDataType struct {
   Word  string        // as cleartext
   Attrs [2244]float32 // as attributes
}

// Create new neuron
func NewNeuron() (n NeuronType) {
   for i, _ := range n.Weights {
      // Init each weight with a random value between -100 and +100
      n.Weights[i] = (float32(rand.Intn(2010)) - 1000) / 10
   }

   return
}

func Init() {
   // Convert charset for simple access
   for i, c := range Charset {
      CharCode[c] = i
   }
}

// Parse input data
func NewData(w string) (d NeuronDataType) {
   d.Word = strings.ToUpper(w)

   wordlen := len(d.Word)
   if wordlen > 20 {
      panic(fmt.Sprintf("Input word \"%s\" is too long: %v chars", w, wordlen))
   }

   // Set attributes for length of word
   for i := 0; i < 20; i++ {
      if wordlen == (i + 1) {
         d.Attrs[i] = 1
      } else {
         d.Attrs[i] = 0
      }
   }

   // Counters for consonants and vowels
   cons := 0
   vowels := 0

   // Walk though word
   for i, c := range d.Word {
      // Increase consonants/vowels counters
      isV, ok := isVowel[c]
      if isV {
         vowels++
      } else if ok {
         cons++
      } else if c < 48 || c > 57 { // Non number
         d.Attrs[i+21] = 1
      }

      // Set char/position attribute
      if _, ok = CharCode[c]; ok {
         d.Attrs[1485+(CharCode[c]*20)+i] = 1
      }

      // Count char pairs
      if i > 0 {
         c1, ok1 := CharCode[int32(d.Word[i-1])]
         c2, ok2 := CharCode[c]
         if ok1 && ok2 {
            d.Attrs[41+c1*len(Charset)+c2]++
         }
      }
   }

   // Calculate consonants/vowels ratio
   if (cons + vowels) > 0 {
      d.Attrs[20] = float32(cons) / float32(cons+vowels)
   }

   return
}

// Rate a word using the current weights and return the overall result
func (n *NeuronType) Rate(d NeuronDataType) (weightSum float32) {
   weightSum = 0 // Init

   for i, v := range d.Attrs {
      weightSum += v * n.Weights[i]
   }

   return
}

// Train Neuron
func (n *NeuronType) Train(d NeuronDataType, isValid bool) {
   for i, v := range d.Attrs {
      r := v * n.Weights[i]
      // Change weight on error
      // false-negative: r is <0, -= r will increase weight
      // false-positive: r is >0, -= r will decrease weight
      if (r < 0 && isValid) || (r > 0 && !isValid) {
         n.Weights[i] -= r / 10
      }
   }

   return

}

Ergebnis

Nach dem Training arbeitet das neuronale Netz erstaunlich gut. Die Testdaten werden bis auf einen Ausreißer richtig eingeordnet:

Auto: 12
garbage: 10
as9Boo: -6
lae5uZee: -14
Be5Eirae: -4
igieng5I: 2
1.11.2011: -12

Lediglich beim vorletzten Beispiel stimmt eine kleine Mehrheit für ein echtes Wort. Davor wird sogar das englische Wort garbage richtig erkannt, obwohl das Netz nur mit deutschen Wörtern trainiert wurde.

Bei der Erkennung der Trainingsdaten liegt die KI fast immer richtig: 60.167 von 60.840 Wörtern werden als solche erkannt und 95.677 von 100.000 von pwgen erzeugte Zufallswerte als Müll. Das entspricht 1,1% False-Positives und 4,3% False-Negatives. Beim zweiten Wert ist allerdings nicht ganz auszuschließen, dass die generierten Daten auch tatsächlich echte Wörter enthalten - aber eigentlich ist das ziemlich unwahrscheinlich, da pwgen gerade keine Passwörter generieren soll, die sich mit einer Brute-Force-Wörterbuchattacke erraten lassen. Bei tatsächlich existierenden Wörtern wäre die Wahrscheinlichkeit eines erfolgreichen Angriffs ungleich größer als bei einer zufälligen Kombination von Buchstaben, die nicht in einem Wörterbuch stehen.

Für rund einen Tag Arbeit bin ich mit dem Ergebnis zufrieden.

Ist das wirklich ein neuronales Netz?

Vermutlich nicht. Ein echtes neuronales Netz zu definieren kostet erfahrene Profis Wochen, manchmal Monate. Die eigentliche Trainingsphase läuft üblicherweise nochmal einige Wochen auf Grafikkarten, deren GPUs auf Vektormultiplikationen optimiert sind. Mein Programm läuft auf meinem fünf Jahre alten Laptop rund drei Minuten auf der CPU (nicht GPU), die um Größenordnungen langsamer bei solchen Operationen ist und liefert bereits ein Ergebnis.

Das Projekt verfolgt die Ansätze eines neuronalen Netzes. Es lernt auf Basis existierender Daten und erkennt selbst, welche Faktoren am Ende relevant sind und welche nicht. Für mich war es eine schöne Denkaufgabe, unter Verwendung der Podcast - Informationen selbst eine Lösung zu entwickeln und eine nette Fingerübung in Go. Ich denke, dass die Grundsätze neuronaler Netze im Prinzip abgebildet sind, auch wenn tatsächlich kein neuronales Netz entstanden ist.

Was haltet Ihr von meiner Lösung? Hinterlasst gerne einen Kommentar mit Eurer Meinung.