Posts Tagged ‘Harry Potter’

Expelliarmus = Bayes Filter Algorithm

Posted by Erin, the RobotGrrl on Saturday, June 20th, 2009

In the final Harry Potter book, it is mentioned quite often that HP depends on this simple yet extremely functional spell called ‘Expelliarmus’.

I often find myself comparing Expelliarmus in the wizarding world to the Bayes Filter Algorithm in my world. It is such a simple method to give your program a little AI.

Before I go on any further, I just want to say that I didn’t invent the Bayes Filter Algorithm, I found it in this book. It is also said in this powerpoint. Additionally, for good measure, here’s a citation:
The Bayes Filter Algorithm I am using is based on the one in the book Probablistic Robotics. (Thrun, Sebastien, Wolfram Burgard, and Dieter Fox. Probablistic Robotics. Cambridge: The MIT Press, 2006.)
OK, now I think I have all of my bases covered.

So, the Bayes Filter algorithm uses Bayes Law, some initial and conditional probabilities, and the actual probabilities, to give you the final probability.

The first thing that happens is that the prior belief is calculated by adding up the multiplication of the conditional probability table and the initial beliefs.

After that, you add up the multiplication of the probability table and the prior belief.

You then find the normalizer by taking that summation and inversing it.

FINALLY, you can get the final belief when you multiply the normalizer and the number where you multiplied the probability table and the prior belief.

If you want, you can even take it a step further by putting log odds to it based on the final belief and the prior belief.

Here is a class I created in Java (in Processing) that is the Bayes Filter Algorithm:

  1. class BFA {
  2.  
  3.   public int numberOfStates;
  4.   public int numberOfSenses;
  5.   public float[][] probabilityTable;
  6.   public float[] initialBels;
  7.   public float[][][] conditionalProbabilityTable;
  8.  
  9.   BFA(int theNumberOfStates, int theNumberOfSenses, float[][] theProbabilityTable, float[] theInitialBels, float[][][] theConditionalProbabilityTable) {
  10.     numberOfStates = theNumberOfStates;
  11.     numberOfSenses = theNumberOfSenses;
  12.     probabilityTable = theProbabilityTable;
  13.     initialBels = theInitialBels;
  14.     conditionalProbabilityTable = theConditionalProbabilityTable;
  15.   }
  16.  
  17.   public void printProbabilityTable() {
  18.    for(int j=0; j<numberOfSenses; j++) {
  19.     for(int i=0; i<numberOfStates; i++) {
  20.      print("     " + probabilityTable[j][i] + "     ");
  21.     }
  22.     println(" ");
  23.    }
  24.    
  25.    println("\n");
  26.    
  27.    for(int j=0; j<numberOfStates; j++) {
  28.     print("   " + initialBels[j] + "   ");
  29.    }
  30.    
  31.    println("\n");
  32.    
  33.    for(int j=0; j<numberOfStates; j++) {
  34.     for(int i=0; i<numberOfStates; i++) {
  35.      print("     " + conditionalProbabilityTable[0][j][i] + "     ");
  36.     }
  37.     println(" ");
  38.    }
  39.    
  40.    println("\n");
  41.    
  42.   }
  43.  
  44. public float calculateProbability(int theStateQuestioned, int sensorData, boolean logOdds, boolean logData, boolean printThem) {
  45.    
  46.     float priorbel[] = new float[this.numberOfStates+1];
  47.     float multiplier[][] = new float[this.numberOfSenses+1][this.numberOfStates+1];
  48.  
  49.     float tempResult = 0.0;
  50.     float normalizer = 0;
  51.     float summation = 0;
  52.     float logOddsResult;
  53.    
  54.     if(logData) output.println(getTime() + "Entering Bayes Filter Algorithm");
  55.    
  56.     for(int i=0; i<numberOfStates; i++) {
  57.      for(int j=0; j<numberOfStates; j++) {
  58.       tempResult += (conditionalProbabilityTable[0][i][j]*initialBels[j]);
  59.      }
  60.      priorbel[i] = tempResult;
  61.      if(logData) output.println(getTime() + "Prior belief calculated. priorbel[" + i + "]: " + priorbel[i]);
  62.      if(printThem) println("Prior bel[" + i + "]: " + priorbel[i] + " Temp result: " + tempResult);
  63.      tempResult = 0.0;
  64.     }
  65.  
  66.    for(int i=0; i<numberOfStates; i++) {
  67.     multiplier[sensorData][i] = probabilityTable[sensorData][i]*priorbel[i];
  68.     summation += multiplier[sensorData][i];
  69.     if(logData) output.println(getTime() + "Summation and multiplier calculated. Summation: " + summation + " Multiplier: " + multiplier[sensorData][i]);
  70.     if(printThem) println("Summation: " + summation + " Multiplier: " + multiplier[sensorData][i]);
  71.    }
  72.    
  73.    normalizer = pow(summation, -1);
  74.    if(logData) output.println(getTime() + "Normalizer and multiplied together calculated. Normalizer: " + normalizer + " Multiplied together: " + summation*normalizer);
  75.    if(printThem) println("Normalizer: " + normalizer);
  76.    if(printThem) println("Multiplied together: " + summation*normalizer);
  77.    
  78.    float finalProbability = normalizer*multiplier[sensorData][theStateQuestioned];
  79.    float priorProbability = priorbel[theStateQuestioned];
  80.    
  81.    if(logData) output.println(getTime() + "Prior probability calculated. Prior probability: " + priorProbability);
  82.    if(logData) output.println(getTime() + "Final probability calculated. Final probability: " + finalProbability);
  83.    if(printThem) println("Final probability: " + finalProbability);
  84.  
  85.     if(logOdds) {
  86.      logOddsResult = log(finalProbability/(1-finalProbability))-log(priorProbability/(1-priorProbability));
  87.      if(logData) output.println(getTime() + "Log odds probability calculated. Log odds: " + logOddsResult);
  88.      if(logData) output.println(getTime() + "Bayes filter algorithm complete.");
  89.      return logOddsResult; // log base e
  90.     } else {
  91.      if(logData) output.println(getTime() + "Bayes filter algorithm complete.");
  92.      return finalProbability;
  93.     }
  94.    
  95.   }
  96.  
  97.   public void setNumberOfStates(int theNumber) {
  98.    numberOfStates = theNumber;
  99.   }
  100.  
  101.   public int getNumberOfStates() {
  102.    return numberOfStates;
  103.   }
  104.  
  105. }

The Bayes Filter Algorithm is super handy because you can check it by hand. There are no ambiguities introduced into the algorithm. Some of the algorithms, like the Kalman Filter, use covariance in the algorithm to adjust the final belief. This is great, but definitely more tricky to calculate by hand.

I favour the Bayes Filter Algorithm right now because of its ease of use, and it gives me what I want. However, for more interesting results, the Kalman Filter would be a better way to go. If I have time at the end of this project, I’ll probably implement the Kalman Filter and use it instead of the Bayes Filter Algorithm. :D

Post to Twitter Post to Delicious Post to Digg Post to Facebook Post to Reddit Post to StumbleUpon

Posted in: Programming, Projects.

Welcome!

    Welcome to RobotGrrl's blog! The posts that are updated here explain the various projects that I am working on, including robots, programs, Apps, photography, and explorations within sociable robotics.

    Robot Party

    The Robot Party is a weekly 30 minute Google+ hangout where we gather to demonstrate and discuss our robots!


    Thursday @ 8:00PM ET
    Robot Party page!

    You can participate in the Q&A of the Robot Party through the chat widget on the Robot Party page!

Social



Robotic Fund

Housekeeping