Archive for June 20th, 2009

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

Posted in: Programming, Projects.

PechaKucha Night & Multidisciplinary Symposium on Reinforcement Learning

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

I gave my talk at PechaKucha night a few days ago. It feels much shorter than 6:40 when you get up there! There was about 300 people, I presented first :)

I just want to show some pictures of the set up:


Montreal PechaKucha Night #12

It’s really cool. There’s an area there that is separated from the other lounge areas by a curtain. In this area there’s 3 screens. Now, the 3 screens are extremely handy when you’re presenting because you don’t have to turn around completely to know that the slide changed. Also, when you’re looking at the presentation, for some reason it makes it feel more 3D when you see the slides from different angles. Pretty spectacular!

This is what one of the lounge areas looked like:


Montreal PechaKucha Night #12

As you can also see by the screen, this was the 2 year anniversary! Woohoo!

It is also worth noting the efforts I went to to make sure I knew what I was talking about. I practiced an insane amount of times, and I even made an app that shows my slide notes, and I can just swipe through them. (Though, when I got there and decided to look at it, the app crashed just about at slide 10. LOL) But, when I got up there, I completely winged it. :P The key points were the same, but I have absolutely no recollection of what I said, exactly.

So yeah, PechaKucha was really fun, and the people there were amazing.

Oh yeah: My dad was going to record it so that I could share it with yall, but I forgot the batteries. ROFL! I know right, a roboticist forgot the batteries. Total shame!

The next day I went to McGill for this Multidisciplinary Symposium on Reinforcement Learning.

I had to sit on the floor because there were not enough chairs. I also found the general attitude of some of the presenters was ‘my way, or the highway’.

With that being said, it was all worth it in order to listen to Andrew Ng’s talk (Ng doesn’t have the attitude of ‘my way or the highway’). He was most definitely the only person there that had a great in-depth and practical knowledge of what RL is all about. He was leaps beyond many of the other presenters.


MSRL

It’s funny though because it felt like the other presenters (who thought that they were all the key to the earth), thought that Ng was using the wrong principles, not RL, in his Little Dog algorithms. They didn’t catch on what it was all about. I lol at them!

In any case, I didn’t go back the next day because I figured I could learn more online and do some of my own research, where I would be learning more.

I like AI & ML more than RL. To me, RL is just AI + ML but in a loop. Long live AI & ML!

Posted in: Art, Other, Projects, School.









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