The exploration-exploitation dilemma in Multiarm bandit problem

slot-machine-2304135_1280

Let’s say you are in a casino and there 4 slot machines. Each slot machine gives you a reward of 1 or 0. The win percentage of each of the slot machines are different and they are not known. The results are truly random. The goal is to choose the slot machine with the highest win rate. The only way you could discover their relative win capabilities is by playing each these slot machines and collecting data, but this naive approach has its downside. In the process of collecting the data you would spend lot of time playing the less optimal slot machines. There is a an exploration-exploitation dilemma here.

Exploration finds more information about the environment and exploitation uses the already known information to maximize the reward. So your approach needs to include both maximizing your earning and also in the process find out the slot machine with the maximum win rate.

A number called epsilon is used which represents the probability of exploration, Here is how epsilon is used to choose between explorating a random slot machine and the machine with highest win rate at that point in time.

p = generate_random_number()
if p > e:
  pull a random arm 
else: 
  pull the arm with best win rate at this point

In the above process you’ll eventually get to know the arm with the best win rate. This is also called as the Multiarm bandit problem. There are numerous ways of approaching this problem. In next few blog posts will walk through some of the solution for a Multiarm bandit problem.

Advertisements

Importance of Kalman Gain parameter in Kalman filters

Kalman filter gain parameter plays a very important role in kalman filter estimation, In the last blog I’ve given an introduction on what are Kalman filters and why to use them.

Kalman filter gain decides how much of the new measurement has to be considered for the estimation. Here is the formula for Kalman gain.

Screen Shot 2017-12-06 at 7.17.40 PM

KalmanGain = Error In Estimation / (Error in estimation + Error in measurement) .
If the error in measurement in small then the value of Kalman Gain would be close to 1. If the error in estimation is large then value heads towards 0.
Here is the update equation for the state using the Kalman gain.

Screen Shot 2017-12-06 at 7.20.33 PM

As you can see in the above equation, If the Kalman gain (KG) is close to 0, this implies that the error in the measured value from the sensor is really high and thus they are unstable. In this scenario we don’t want the contribution of the measured value to be notable on the prediction, this is controlled by the additive factor for the previous estimation, this quantity is meager when the KG value is close to 0, and thus it just slightly adds up to the previous estimation, so the Kalman gain(KG) helps invest better confidence on the estimation rather than on the measurement.

On the other hand, If the Kalman Gain is close to 1, that is in case where the error in estimation is really high compared to the error in the measurement from the sensors, The additive value for the previous estimate in the update equation above will be significant, thus the updated value will considerably different from the estimation since the contribution from the measurement will be higher.
Thus Kalman filter gain helps to weigh the contribution of the difference between the previous estimate and the current measurement to update the previous estimate to arrive at the new estimate.

Code Puzzle : Making Anagram problem

Problem statement: Calculate the minimum number of characters to be removed from any of the given two strings so that they become anagram.

Strategy: Store the frequency of occurrence of every characters (from a-z) of each of the strings in separate arrays, then the summation of difference in frequency of each character gives you the solution, abs(count1[str1[i]-‘a’] – count2[str2[i]-‘a’])

Here is the code,


#include <iostream>

using namespace std;

int min_remove_anagram(string a, string b) {
    int char_count_a[26]={0}, char_count_b[26]={0}, num_needed=0;
    // Count the frequencies of all characters in string a and b
    for(int i=0; i < a.size(); i++) {
        char_count_a[a[i] - 'a']++;
    }
    for(int i=0; i < b.size(); i++) {
        char_count_b[b[i] - 'a']++;
    }

    // The difference in the frequency count of all the characters is the solution.
    for(int i = 0; i < 26; i++) {        
       num_needed += abs(char_count_a[i] - char_count_b[i]);
    }
 return num_needed; 
}


int main()
{
    string str1 = "bcadeh", str2 = "hea";
    cout << min_remove_anagram(str1, str2);
    return 0;
}

Hello World ROS: Creating ROS workspace and a empty node.

The Robot Operating System (ROS) is a flexible framework for writing robot software. It is a collection of tools, libraries, and conventions that aim to simplify the task of creating complex and robust robot behavior across a wide variety of robotic platforms.

Creating the ROS work space

  • ROS has package management system called catkin.
  • All the packages are maintained usually in a single workspace under different directories.
  • Catkin workspace is a directory where the catkin packages are build, maintained and modified.
  • First, you need to create the top level catkin workspace directory and a sub-directory named src. The top level directory’s name is arbitrary, it can be anything, but is often called catkin_ws (an abbreviation of catkin_workspace),
$ mkdir -p ~/catkin_ws/src
$ cd ~/catkin_ws/src
  • Initialize and building the workspace.
$ catkin_init_workspace
$  cd ~/catkin_ws && catkin_make

You now have two new directories: build and devel. The aptly named build directory is the build space for C++/Python packages. The devel directory contain  a file named setup.bash. This setup.bash script must be sourced before using the catkin workspace.

Creating a package

  • ROS softwares are distributed and maintained as catkin packages.
  • Its again a directory containing variety of resources.
  • Let’s clone an existing package and add it to our newly created workspace.
  • You will start by navigating to the src directory and cloning the simple_arm package for this lesson from its github repo.
$ cd ~/catkin_ws/src
$ git clone https://github.com/udacity/simple_arm_01.git simple_arm

After the repo has finished cloning, you can change directory to the top-level of the ros workspace and build the new package.

$ cd ../../
$ catkin_make

If you see the following error

I see a CMake Error. “Could not find a package configuration file provided by controller_manager”,

The following is missing just install it using the command below,

$ sudo apt-get install ros-kinetic-controller-manager

build again

$ cd ~/catkin_ws
$ catkin_make

Once the workspace has been built, now source the setup script

$ source devel/setup.bash

 Now launch simple_arm:

$ roslaunch simple_arm robot_spawn.launch

Creating the node

Step 1: In order to create a new node in python, you must first create the scripts directory within the simple_arm package.

$ cd ~/catkin_ws/src/simple_arm/
$ mkdir scripts

Step 2: Create scripts inside the script folder, give execution permission to the script

$ cd scripts
$ echo '#!/bin/bash' >> hello
$ echo 'echo Hello World' >> hello
$ chmod u+x hello

Step 3: Rebuild the workspace

$ cd ~/catkin_ws
$ catkin_make

Step 4: Source the setup.bash

$ source devel/setup.bash

Step 5: Use rosrun to run the node

rosrun <package name> <script name>
$ rosrun simple_arm hello

We have created a empty node.

What are Kalman filters ?

Why to use Kalman filter ?

The sensor measurements are not generally accurate, they usually have unpredictable, random and uncertain error/variation in their measurements. What does that mean ? Consider a thermometer which reads/measures room temperature, In a room with steady/constant temperature the sensor outputs a varying temperature measurement within a given range, the readings will be scattered around the actual room temperature, this is because the sensors generally have a degree of uncertainty in their measurement.

In the image below the marked X’s demonstrates the sensor readings over a period of time. You can see the though the actual temperature of the room is constant, the readings are distributed over a range of values around the actual temperature.

Screen Shot 2017-12-04 at 8.08.28 AM

 

If sensor measurements return uncertain measurements, how do we know the actual room temperature ?

We’ll, that’s where Kalman filters comes to your rescue. Kalman filter is an iterative mathematical approach which is used to quickly (with less number of actual readings and iterations) converge to a better estimation of the actual value (better than the sensor measurement itself). In this case using Kalman filter will quickly help us estimate the actual room temperature using the uncertain measurements. In the above you can see how Kalman filter technique helps to quickly approximate the actual room temperature by converging close to the actual value by making use of the uncertain sensor measurements.

The application of Kalman filters are wide, For example Similar issues too are found when Lidar or Radar measurements are used to object tracking in self driving cars, the right estimate of other vehicle on the road is critical for safe driving, Kalman filter are used here too for estimation the actual position and velocity of other vehicles on the road.

Parallelism Is Not Concurrency

Existential Type

In an earlier post I mentioned that one goal of the new introductory curriculum at Carnegie Mellon is to teach parallelism as the general case of computing, rather than an esoteric, specialized subject for advanced students.  Many people are incredulous when I tell them this, because it immediately conjures in their mind the myriad complexities of concurrency: locks, monitors, deadlock, dining philosophers, ….  And if you look at the recent research literature, you will see countless papers of the form (a) parallelism is important, so (b) let’s talk about concurrency.  The situation has gotten so bad that I think that most computer scientists cannot distinguish the two concepts.  (Or maybe they willfully confuse the two so as to justify funding for work on concurrency by appealing to the importance of parallelism.)

Given this state of affairs, I cannot explain what we are doing at Carnegie Mellon (to anyone who doesn’t…

View original post 1,830 more words

Http/2 and implementation in GoLang-1: Http/2 Frameheaders and parsing HTTP/2 Frameheaders in Golang

Http/2 is around the corner and its specifications look really interesting ! The complete specification of Http/2 can be seen at this following link https://http2.github.io/http2-spec/ .

In this post ill be discussing about Http/2 FrameHeader and lets figure out the binary math done to parse it in GoLang .
The complete Http/2 implementation of Golang is available at https://github.com/bradfitz/http2 .

Now Lets Look at the structure of HTTP Frameheader from its spec

+———————————————–+
| Length (24) |
+—————+—————+—————+
| Type (8) | Flags (8) |
+-+————-+—————+——————————-+
|R| Stream Identifier (31) |
+=+=============================================================+
| Frame Payload (0…) …
+—————————————————————+

The fields of the frame header are defined as:

Length:
The length of the frame payload expressed as an unsigned 24-bit integer. Values greater than 214 (16,384) MUST NOT be sent unless the receiver has set a larger value for SETTINGS_MAX_FRAME_SIZE.

The 9 octets of the frame header are not included in this value.

Type:
The 8-bit type of the frame. The frame type determines the format and semantics of the frame. Implementations MUST ignore and discard any frame that has a type that is unknown.

Flags:
An 8-bit field reserved for frame-type specific boolean flags.

Flags are assigned semantics specific to the indicated frame type. Flags that have no defined semantics for a particular frame type MUST be ignored, and MUST be left unset (0x0) when sending.

R:
A reserved 1-bit field. The semantics of this bit are undefined and the bit MUST remain unset (0x0) when sending and MUST be ignored when receiving.

Stream Identifier:
A stream identifier expressed as an unsigned 31-bit integer. The value 0x0 is reserved for frames that are associated with the connection as a whole as opposed to an individual stream.

Now let us look at the implementation of Parsing Http/2 FrameHeader in GoLang
Let us look at the function readFrameHeader https://github.com/bradfitz/http2/blob/master/frame.go . Here is the code

func readFrameHeader(buf []byte, r io.Reader) (FrameHeader, error) {
	_, err := io.ReadFull(r, buf[:frameHeaderLen])
	if err != nil {
		return FrameHeader{}, err
	}
	return FrameHeader{
		Length:   (uint32(buf[0])<<16 | uint32(buf[1])<<8 | uint32(buf[2])),
		Type:     FrameType(buf[3]),
		Flags:    Flags(buf[4]),
		StreamID: binary.BigEndian.Uint32(buf[5:]) & (1<<31 - 1),
		valid:    true,
	}, nil
}

Looks like Greek isn’t it 😛 Lets do some binary math to understanding the parsing of the buffer containing the HTTP/2 Frame .
From the structure of the HTTP/2 Frameheader the first 24 bytes contains the Length of the payload , but since the Http Frame along with its data is obtained in the form of a byte Array ([]byte) , the header now has to be parsed from the same .Since each element in an byte array is a byte, it can only hold 8 bit of data . So now the 24 bit Payload length is spread across 3 consecutive members of the byte array ranging from buf[0] to buf[2] .

Now the challenge is to parse these 3 elements of the array into one integer number . But first lets see how in the first place a 24 bit integer is made to fit into a byte array

Let do a small exercise to understand this .
Let take an random integer , hmm, lets consider the integer 99999 and convert this to binary and present it in 24 bit

99999 = 00000001 10000110 10011111

Here is its binary representation again and how it is stuffed as bytes inside byte array

00000001 10000110 10011111
| | |
| | |
buf[0] buf[1] buf[2]

Oh now i know how in first place how this 24 bit integer is stuffed inside byte array , but do i now parse it back into an integer

Very Simple , Here is how an 0 valued 32 bit integer looks like

00000000 00000000 00000000 00000000

First take buf[0] and place it at the 3rd byte from left of the 32 bit integer and make it look like this

00000000 00000001 00000000 00000000

How to do that ???

Simple …. First convert buf[0] into a 32 bit int

(uint32(buf[0])

)
After this the 32 bit integer look like this

00000000 00000000 00000000 000000001

Thhhhhh…!! But content of buf[0] is supposed to be in 3rd byte position but its now 1 byte position !

Okay , now just left shift the integer by two bytes (16 bits) , after this the content of buf[0] will be moved to the 3rd byte position .

 (uint32(buf[0])<<16 

)
Now in the same fashion , you gotto generate a 32 bit integer with the content of buf[1] in the 2nd byte position . This is the done by now left shifting the integer by a byte (8 bits) .

uint32(buf[1])<<8

and at the end just convert buf[2] into a 32 bit integer .

Now just perform a logical OR (|) on these 3 integers which will fetch one integer representing the 24 bit Frame Payload Length parsed .

After first 24 bits in the Http Frameheader the next 8 bits correspond to the FrameType . This can be easy retrieved by converting buf[3] into an integer

uint32(buf[3])

)

The next 8 bits correspond to the Flags . This can be easy retrieved by converting buf[3] into an integer

uint32(buf[4])

)

As you can see in the FrameHeader image the next 1 bit is a Reserved bit and 31 bit following it is the Stream ID .

Now the Last 31 bit has to be parsed from the buffer to be able to obtain the stream ID . To be able to do it first fast last 32 bits a 32 bit int

uint32(buf[5])<<24| ]uint32(buf[5]) <<16 | ]uint32(buf[5]) << 8| ]uint32(buf[5])

)

or there is an equivalent function from the package binary, which does the above functionality

 binary.BigEndian.Uint32(buf[5:]) 

)
The following link explains more about binary.BigEndian.Uint32 , http://stackoverflow.com/questions/7380158/how-to-convert-4uint8-into-uint32-in-go

Now the challenge is to turn the 32nd bit to 0 so that the 31 bit Stream ID is retrieved .

But how to achieve it ??
Well , easy . Take a number which in binary is equivalent to 0 followed by 31 1’s and then perform a logical AND (&) operation with the number on which you want to strip out or set the 32nd bit of the number to be zero .

First generate an integer which in binary representation is equivalent to 0 followed by 31 1’s

(1<<31 - 1)

)

This is how at the end last 31 bit representing the Stream ID is obtained

binary.BigEndian.Uint32(buf[5:]) & (1<<31 - 1)

)

Here is the source from https://github.com/bradfitz/http2 , The GoLang Http2 implementation which corresponds to parsing of HTTP2 FrameHeader and i hope after all the explanation the source should make some sense 😛

func readFrameHeader(buf []byte, r io.Reader) (FrameHeader, error) {
	_, err := io.ReadFull(r, buf[:frameHeaderLen])
	if err != nil {
		return FrameHeader{}, err
	}
	return FrameHeader{
		Length:   (uint32(buf[0])<<16 | uint32(buf[1])<<8 | uint32(buf[2])),
		Type:     FrameType(buf[3]),
		Flags:    Flags(buf[4]),
		StreamID: binary.BigEndian.Uint32(buf[5:]) & (1<<31 - 1),
		valid:    true,
	}, nil
}

)a

ssssssssssssssss …..Thats it for now !!! I hope this helped you guys to understand the structure of parsing of Http2 . Will follow up with lots of blogs on Http2 implementation in GoLang..Till then , Happy Coding 😀