Backpropogation algorithm / Алгоритм обратного распространения ошибки

backpropogation.rb

# Backpropogation algorithm
# http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D1%88%D0%B8%D0%B1%D0%BA%D0%B8
# http://galaxy.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html
# http://ai4r.rubyforge.org/neuralNetworks.html
# http://ai4r.rubyforge.org/rdoc/classes/Ai4r/NeuralNetwork/Backpropagation.html

class NeuralNetwork
  #[2, 3, 3] - NN with 2 neurons in input layer, 1 hidden layer with 3 neurons and output layer with 3 neurons
  #[2, 3, 3, 3] - NN with 2 neurons in input layer, 2 hidden layers with 3 neurons in each and output layer with 3 neurons
  attr_accessor :weights, :outputs, :deltas
  def initialize(structure)

    @structure = structure
    @nu = 0.15
    @momentum = 0.05

    init_weights
    # [layer, source, dest] => {weight, output, delta}
  end

  # [[[1, 2, 3], [2, ,1 ,3]], [[0, 1, 2], [0,2,3], [1,2,30]], ... ]
  def init_weights
    #[nil, nil]
    @weights = Array.new(@structure.length - 1)
    #[[nil, nil], [nil,nil]]
    @weights.each_index do |i|
      @weights[i] = Array.new( @structure[i] )
    end
    #[ [ [nil, nil], [nil, nil] ], [nil, nil] ]
    @weights.each_index do |src|
      @structure[src].times do |dst|
        @weights[src][dst] = Array.new( @structure[src + 1] )
      end
    end

    set_default_weights
  end

  def to_s
    p "Neural Network parameters: "
    p "------------------------------"
    p "Structure - #{@structure}"
    p "Training rate - #{@nu}"
    p "Momentum( inertiality coeff. - #{@momentum}"
    p "------------------------------"
  end

  def set_default_weights
    @weights.each_index do |layer_ind|
      @weights[layer_ind].each_index do |node_src_ind|
        @weights[layer_ind][node_src_ind].each_index do |node_dst_ind|
          @weights[layer_ind][node_src_ind][node_dst_ind] = (rand(2000)/1000.0) - 1
        end
      end
    end
  end

  def train( example, result )
    @input = example
    evaluate( example )
    backpropogate( result )
  end

  def backpropogate( result )
    init_deltas  if !@deltas
    init_last_changes if !@last_changes
    calculate_output_deltas( result )
    calculate_deltas
    update_weights
  end

  def init_deltas
    @deltas = Array.new(@structure.length - 1)
    @deltas.each_index do |i|
      @deltas[i] = Array.new( @structure[i+1], 0 )
    end
  end

  def calculate_output_deltas( result )
    @deltas[@structure.length - 2].each_index do |node|
      error = result[node] - @outputs[@structure.length - 2][node]
      @deltas[@structure.length - 2][node] = derivative( @outputs[@structure.length - 2][node] ) * error
    end
  end

  # С предпоследнего слоя
  def calculate_deltas
    (@weights.length-1).downto(1) do |layer_ind|
      @weights[layer_ind].each_index do |node_src_ind|
        error  = 0.0
        @weights[layer_ind][node_src_ind].each_index do |node_dst_ind|
          error += @deltas[layer_ind][node_dst_ind]*@weights[layer_ind][node_src_ind][node_dst_ind]
        end
        @deltas[layer_ind-1][node_src_ind] = derivative( @outputs[layer_ind-1][node_src_ind] )*error
      end
    end
  end

  def update_weights
    @weights.each_index do |layer_ind|
      @weights[layer_ind].each_index do |node_src_ind|
        @weights[layer_ind][node_src_ind].each_index do |node_dst_ind|
          if layer_ind == 0
            changes = @deltas[layer_ind][node_dst_ind]*@input[node_src_ind]
            @weights[layer_ind][node_src_ind][node_dst_ind] += (1-@momentum)*@nu * changes + @momentum*@last_changes[layer_ind][node_src_ind][node_dst_ind]
            @last_changes[layer_ind][node_src_ind][node_dst_ind] = changes
          else
            changes = @momentum*@last_changes[layer_ind][node_src_ind][node_dst_ind] + (1-@momentum)*@nu*@deltas[layer_ind][node_dst_ind]*@outputs[layer_ind-1][node_src_ind]
            @weights[layer_ind][node_src_ind][node_dst_ind] += changes
            @last_changes[layer_ind][node_src_ind][node_dst_ind] = changes
          end
        end
      end
    end
  end

  def apply_function( x )
    1.0/(1+Math.exp(-1*(x)))
  end

  def derivative( y )
    y*(1.0-y)
  end

  # Для outputs - начинаем отсчет с 1го слоя, т.е arr[0] - это первый слой, а arr[last] - это последний
  # Для weights - начинаем отсчет с 0го слоя т.е arr[0]  - это 0 слой, а arr[last] - это предпоследний слой
  def init_outputs
    if !@outputs
      @outputs = Array.new( @structure.length-1 )
      @outputs.each_index do |i|
        @outputs[i] = Array.new( @structure[i+1], 1 )
      end
    end
  end

  def calculate_outputs( input )
    init_outputs if !@outputs
    @weights.each_index do |layer_ind|
      @weights[layer_ind].each_index do |node_src_ind|
        @weights[layer_ind][node_src_ind].each_index do |node_dst_ind|
          if layer_ind == 0
            @outputs[layer_ind][node_dst_ind] += @weights[layer_ind][node_src_ind][node_dst_ind]*input[node_src_ind]
          else
            @outputs[layer_ind][node_dst_ind] += @weights[layer_ind][node_src_ind][node_dst_ind]*@outputs[layer_ind-1][node_src_ind]
          end
        end
      end
      @outputs[layer_ind].each_index do |node|
        @outputs[layer_ind][node] = apply_function( @outputs[layer_ind][node] )
      end
    end
  end

  def calculate_error(expected_output)
    output_values = @outputs.last
    error = 0.0
    expected_output.each_index do |output_index|
      error +=
        0.5*(output_values[output_index]-expected_output[output_index])**2
    end
    return error
  end

  def feedforward( input )
    calculate_outputs( input )
  end

  def evaluate( input )
    raise ArgumentError if input.length != @structure[0]
    feedforward(input)
    return @outputs.last
  end


  # Momentum usage need to know how much a weight changed in the
  # previous training. This method initialize the @last_changes
  # structure with 0 values.
  def init_last_changes
    @last_changes = Array.new(@weights.length) do |w|
      Array.new(@weights[w].length) do |i|
        Array.new(@weights[w][i].length, 0.0)
      end
    end
  end
end

backpropogation_spec.rb

# little specs
require_relative '../backpropogation.rb'

describe 'Function testing' do
  it "should return correct weights" do
    structure = [2,3,1]
    nn = NeuralNetwork.new structure

    # should print [ [ [1, 2, 3], [1, 2, 3] ], [ [1], [2], [3] ] ]
    nn.weights[0].count.should == 2
    nn.weights[1].count.should == 3
    nn.weights[0][0].count.should == 3
    nn.weights[0][1].count.should == 3
    nn.weights[1][0].count.should == 1
    nn.weights[1][1].count.should == 1
    nn.weights[1][2].count.should == 1

    structure = [3, 5, 2, 3]
    #should print [ [ [1, 2, 3, 4, 5], [1,2,3,4,5], [1,2,3,4,5] ], [ [1,2], [1,2], [1,2], [1,2], [1,2] ], [ [1,2,3], [1,2,3] ] ]
    nn = NeuralNetwork.new structure
    nn.weights[0].count.should == 3
    nn.weights[1].count.should == 5
    nn.weights[2].count.should == 2
    nn.weights[0][0].count.should == 5
    nn.weights[0][1].count.should == 5
    nn.weights[0][2].count.should == 5
    nn.weights[1][0].count.should == 2
    nn.weights[1][1].count.should == 2
    nn.weights[2][1].count.should == 3

  end

  it "should correct calculate outputs" do
    structure = [2, 3, 2, 1]
    nn = NeuralNetwork.new structure

    input = [1,2]
    nn.evaluate( input )
    nn.outputs[0].count.should == 3
    nn.outputs[1].count.should == 2
    nn.outputs[2].count.should == 1
  end

  it "should correct calculate deltas" do
    structure = [2, 3, 2, 1]
    nn = NeuralNetwork.new structure

    input = [1,2]
    right = [0.5]
    nn.train( input, right )
  end

  it "should correct update weights" do
  end
end

testing_network.rb

# http://ai4r.rubyforge.org/neuralNetworks.html - good examples to testing neural network
require 'rubygems'
require 'hornetseye_rmagick'
require 'hornetseye_xorg'
require_relative './backpropogation.rb'

def test_xor
  print(" Neural Network with 2 input neurons, 1 hidden layer with 5 neurons and 1 output neuron \n")
  print( "Testing XOR \n")
  nn = NeuralNetwork.new( [2, 5, 1])
  training_time = 4000

  p nn.to_s
  p "Training network #{training_time} times"
  training_time.times do |i|
    nn.train([0,0], [0])
    nn.train([1,0], [1])
    nn.train([0,1], [1])
    nn.train([1,1], [1])
  end

  p "---------------------------------------"
  p "0 XOR 0 is  #{nn.evaluate([0, 0])} "
  p "0 XOR 1 is #{nn.evaluate([0, 1])}"
  p "1 XOR 0 is #{nn.evaluate([1, 0])}"
  p "1 XOR 1 is #{nn.evaluate([1, 1])}"
  p "Error is #{nn.calculate_error([1])}"
  p "---------------------------------------"
end

def test_image_recognition
  p "Testing cross, square and triangle recognition"
  include Hornetseye
  triangle = MultiArray.load_ubyte( 'images/t.png').to_a.flatten
  cross = MultiArray.load_ubyte( 'images/c.png').to_a.flatten
  square = MultiArray.load_ubyte( 'images/s.png').to_a.flatten
  square2 = MultiArray.load_ubyte( 'images/sq2.jpeg').to_a.flatten

  nn = NeuralNetwork.new([256, 13, 3, 3])
  training_time = 2000

  training_time.times do |i|
    nn.train( triangle, [1, 0, 0] )
    nn.train( square, [0, 1, 0] )
    nn.train( square2, [0, 1, 0] )
    nn.train( cross, [0, 0, 1] )
  end

  print(" Neural Network with 256 input neurons, 13 hidden layer with 3 neurons in each and 3 output neuron \n")
  p nn.evaluate(square)
  p nn.calculate_error([0,1,0])
  p "From example set should [0,1,0]"

  square4 = MultiArray.load_ubyte( 'images/sq3.jpg').to_a.flatten
  p nn.evaluate(square4)
  p nn.calculate_error([0,1,0])
  p "From test set should [0,1,0]"

  square5 = MultiArray.load_ubyte( 'images/sq4.png').to_a.flatten
  p nn.evaluate(square5)
  p nn.calculate_error([0,1,0])
  p "From test set should [0,1,0]"


end


print "Testing Neural Network...\n"
test_xor
test_image_recognition