The genetic optimizer is complete and works both for Int and Double based problem domains. I also have similar implementations for random, hill climbing and annealing (all based on Programming Collective Intelligence).

class GeneticOptimizer[@specialized(Int, Double) T](
    popsize:Int=50, mutprop:Double=0.2, elite:Double=0.2, maxiter:Int=100)
    (implicit ops:OptimizeOps[T], s:Scalar[T])
    extends Optimizer[T] {

  override def apply(query:OptimizeQuery[T])(implicit ops:OptimizeOps[T], s:Scalar[T]):DenseVectorCol[T] = {
    var pop = (0 until popsize).map(i => ops.generateRandom(query.domain))
    val topelite = (elite*popsize).toInt
    var scores:IndexedSeq[(Double,ops.VectorType)] = null

    def iter = {
      scores = (for(v <- pop) yield (query.cost(v),v)).sortWith(_._1 < _._1)
      val ranked = for((s,v) <- scores) yield v

      pop = ranked.slice(0,topelite)

      def fill = {
        if (random < mutprop)
          pop = pop :+ ops.mutate(ranked((random*topelite).toInt),query.step,query.domain)
        else
          pop = pop :+ ops.crossover(ranked((random*topelite).toInt),
                                     ranked((random*topelite).toInt),
                                     query.domain)
      }

      (pop.size to popsize).foreach(i => fill)
    }

    (0 until maxiter).foreach(i => iter)

    scores.head._2
  }
}

The OptimizeQuery is what needs to be defined by an application that needs to use the optimizers (it is the same one for all the optimizers:

trait OptimizeQuery[@specialized(Int, Double) T] {
  def cost(sol:DenseVectorCol[T]):Double
  def domain:IndexedSeq[(T,T)]
  def step:T
}

The cost function should calculate the cost of the given solution. The domain is a sequence of allowed min and max values for each item in a solution vector. The step controls the learning rate (should really be dynamic for Double based problem domains).

The OptimizeOps is an internal class with the necessary primitive ops for the problem domains with specializations for Int and Double. The template class looks as follows:

@implicitNotFound(msg="${T} is not an optimizable scalar value")
trait OptimizeOps[@specialized(Int, Double) T] {
  type VectorType = DenseVectorCol[T]
  def generateOffset(sol:VectorType,i:Int,dir:T,domain:IndexedSeq[(T,T)]):VectorType
  def generateRandom(domain:IndexedSeq[(T,T)]):VectorType
  def generateNeighbors(sol:VectorType,step:T,domain:IndexedSeq[(T,T)]):List[VectorType]
  def mutate(vec:VectorType,step:T,domain:IndexedSeq[(T,T)]):VectorType
  def crossover(vec1:VectorType,vec2:VectorType,domain:IndexedSeq[(T,T)]):VectorType
  def rand(min:T,max:T):T
}

Real world complexity and optimization

I am just finishing a small optimizer using a genetic algorithm (it works and is under 30 lines of code but not nice enough yet) and I saw the following TED video discussing genetic algorithms:

Switched to Intellij IDEA

I just switched to Intellij IDEA from Eclipse. The IDEA has a fsc build server that compensates (at least to some extent) for the slow builds of Scala.

I found a plugin to generate IDEA projects from SBT: https://github.com/mpeltonen/sbt-idea. After a few tweaks it seems to work great.

I am becoming more and more impressed with the SBT, it is really powerful stuff.

The Scala compiler is however dead slow (even with fsc). It is really a grind. I estimate it to be 4-5 times slower than a Java build (which is not exactly lighting fast). Can there not be a development mode that avoids optimizations and stuff?

ANN in Scala

I just finished a port of a back-propagating Artificial Neural Network, ANN. The original code can be found here (also written in Scala).

My code uses the Scalala library and, because of that, much more compact, only 130 lines of code.

I find the Scalala library to be very nice but there seems to be a lot of small bugs and not always easy to learn.

The code still missing to account for the bias (just like the original code).

 

package scalai.ann

import scalala.scalar._
import scalala.tensor._
import scalala.library._
import scalai._
import scalai.utils._
import scalai.distance.Distance._
import scalala.tensor.dense.{DenseVectorCol, DenseMatrix, DenseVector}
import scala.math._

abstract class ActivationFunction{
	def eval( value : Double) : Double
}

object Sigmoid extends ActivationFunction {
	override def eval ( value: Double) : Double = {
		1d / (1d + exp(-value))
	}
}

class Layer(val inputNum: Int, var weights:DenseMatrix[Double]) {

  import Sigmoid.eval

  val numNeurons = weights.numRows
  val numWeights = weights.numCols - 1
  val biasPos = numWeights
  var errors = DenseVectorCol.zeros[Double](weights.numRows)
  var outputs = DenseVectorCol.zeros[Double](weights.numRows)
  var pastErrors = DenseMatrix.zeros[Double](weights.numRows, weights.numCols)
  
  def this(inputNum: Int, neuronNum: Int) = {
    this(inputNum,Utils.random(neuronNum,inputNum+1,-2.4,2.4))
  }
  
  def run(inputs:DenseVectorCol[Double]) : DenseVectorCol[Double] = {
    outputs = weights(::,0 until numWeights) * inputs
    outputs.foreachKey((i) => outputs(i) = eval(outputs(i)))
    //println(outputs.t)
    outputs
  }
  
  override def toString() : String = {  
    weights.toString(weights.numRows, weights.numCols, (d:Double) => d.toString)
  }
}

class Perceptron(val layers:Array[Layer]){
  
  def this(perceptronInputNum:Int, neuronLayerNum:Array[Int]) = {
    this(new Array[Layer](neuronLayerNum.size))
    
    //Inputs for first layer equals the inputs of the perceptron
    var layerInputNum = perceptronInputNum

    //Creates the layers with each the right number of weights
    for(i <- 0 until neuronLayerNum.size){

      //creates the layer
      layers(i) = new Layer(layerInputNum, neuronLayerNum(i))

      //the number of inputs of the next
      //layer is the current number of weights
      layerInputNum = neuronLayerNum(i)
    }
  }
  
  def run(inputs:DenseVectorCol[Double]):DenseVectorCol[Double] = {
    var layerInput = inputs

    layers.foreach(l => layerInput = l.run(layerInput))

    layerInput
  }
  
  def calculateErrors (inputs: DenseVectorCol[Double], outputs: DenseVectorCol[Double]) = {

    //For each layer from last to first
    for (layerIndex <- (0 until layers.size).reverse) {
      //current layer
      val layer = layers(layerIndex)

      //Last factor of the error calculation
      if(layerIndex == layers.size - 1){ //Last layer`
        layer.errors := (layer.outputs - (layer.outputs :* layer.outputs)) :* (outputs - layer.outputs)
      } else { //Hidden layers
        val nextLayer = layers(layerIndex + 1)
        val tmp = nextLayer.errors.t * nextLayer.weights(::,0 until nextLayer.numWeights)
        layer.errors := (layer.outputs - (layer.outputs :* layer.outputs)) :* tmp
      }
    }
  }
  
  def learn (inputs: DenseVectorCol[Double], outputs: DenseVectorCol[Double]) : Double = {

    val learnLevel : Double = 0.3
    val alfa : Double =  0.9

    //For all the layers but the first
    for(layerIndex <- (1 until layers.size).reverse) {
      val layer = layers(layerIndex)
      val prevLayer = layers(layerIndex - 1)

      layer.pastErrors(::,0 until layer.numWeights) := layer.errors * prevLayer.outputs.t * learnLevel +
                                                       layer.pastErrors(::,0 until layer.numWeights) * alfa
      layer.weights(::,0 until layer.numWeights) := layer.pastErrors(::,0 until layer.numWeights) +
                                                    layer.weights(::,0 until layer.numWeights)
      
      layer.pastErrors(::,layer.biasPos) := layer.errors * -learnLevel +
                                                layer.pastErrors(::,layer.biasPos) * alfa
      layer.weights(::,layer.biasPos) := layer.pastErrors(::,layer.biasPos) +
                                             layer.weights(::,layer.biasPos)
    }

    //For the first layer
    val layer = layers.head
    
    layer.pastErrors(::,0 until layer.numWeights) := layer.errors * inputs.t * learnLevel +
                                                     layer.pastErrors(::,0 until layer.numWeights) * alfa
    layer.weights(::,0 until layer.numWeights) := layer.pastErrors(::,0 until layer.numWeights) +
                                                  layer.weights(::,0 until layer.numWeights)

    layer.pastErrors(::,layer.biasPos) := layer.errors * -learnLevel +
                                              layer.pastErrors(::,layer.biasPos) * alfa
    layer.weights(::,layer.biasPos) := layer.pastErrors(::,layer.biasPos) + layer.weights(::,layer.biasPos)

    (outputs - layers.last.outputs).map(pow(_,2)).sum
  }
}

My first Scala drawing

I ported some code from Collective Intelligence. The code has converted from Python to Scala.

The code is for a Dendrogram. Looks very much like the original Python code but this is type safe and runs several times faster, pretty cool:

class Dendrogram(hier:Hierarchical,labels:List[String]){
    def height:Double = 20*hier.height
    def width:Double = 1200
    
    def draw(draw:DrawContext):Unit = {
      if (height == 0) return 

      val scaling=(draw.width-150)/hier.depth
      
      def drawNode(hier:Hierarchical,x:Double,y:Double):Unit = {       
        if (hier.id < 0) {
          val children = hier.children
          assert(children.length == 2)
          
          val h = children.map(_.height*20)
          val top = y - h.sum/h.length
          val bottom = y + h.sum/h.length
          val ll = hier.distance*scaling
          
          draw.line((x,top+h(0)/2,x,bottom-h(1)/2),fill=(255,0,0))
          draw.line((x,top+h(0)/2,x+ll,top+h(0)/2),fill=(255,0,0))
          draw.line((x,bottom-h(1)/2,x+ll,bottom-h(1)/2),fill=(255,0,0))
          
          drawNode(children(0),x+ll,top+h(0)/2)
          drawNode(children(1),x+ll,bottom-h(1)/2)          
        } else {
          assert(hier.children.length == 0)
          draw.text((x+5,y+6),labels(hier.id),(0,0,0))
        }
      }

      draw.rect(fill=(255,255,255))

      draw.line((0,draw.height/2,10,draw.height/2),fill=(255,0,0))
      
      drawNode(hier,10,draw.height/2)
    }
}

Getting started with Scala

I just recently had a look at the Scala programming language. It seems to have some great features and can run all Java libraries.

I have found a few problems getting started. It mainly involves:

• A lot of new libraries that work in different ways than I am used to (like a mix of Java and functional, which it is).
• Problems with tools and IDEs. Netbeans integration is totally worthless. Eclipse integration works but very bad compared to what is supported in Java.
• Quibbles with generic programming and traits. Seems like there are a lot of implicit magic going on and it seems to get it wrong sometimes.

So far I am not sold on the advanced type system. It seems to be more confusing than helpful. It looked great when I read Martin Oderskys excellent book, hmm. It is also very hard to follow the documentation and all the implicit conversions taking place.

I intend to use Scala to develop some utilities for machine learning and simulation. I have found the following libraries could be helpful:

• Scalala – Linear Algebra library similar to Matlab.
• Slick – Java library for 2d games. Helpful for visualization.
• Sbt – Scala Simple Build Tool. Seems excellent. Automatically downloads dependencies, supports sub projects, building, packaging, console (since Scala can be used as an interpreter).
• SbtEclipsify – Creates Eclipse projects from Sbt projects. Works very easily (you still have to add project dependencies in Eclipse though).

Exponential growth and medicine

The beginning

This blog will contain a bit of everything but will focus mainly on gameification, machine learning, behavior simulation and games in society. If your interest is mainly in video games you are probably better of somewhere else.

Please note that I am not an expert in either of these subjects.

Wikipedias definition of Gameification:

The use of game play mechanics for non-game applications.

The basis for most game play mechanics in gameification is to provide the right incentives for people to do something and to keep doing it.

An example is the frequent flyer programs offered by airlines. It gives an incentive for passengers to fly more while keeping the costs down for the airlines. The incentive? Status.

A great introduction to this subject can be found in this video (it also contains a serious mistake in the frequent flyer programs). The video is however 1 hour long so make sure to make time for it before watching: