The curious case of the burning finger

April fooled!

Last week, Prof. Om Damani announced our next assignment. We had to implement statistical machine translation, that too with exams just 15 days away. Given that he took almost around 4 classes (that's about 6 hours) to give the overview of the procedure, we simply had no clue how we would manage it.

Well, we got this email from him today.

Was it April 1st when I announced it  :)
Sorry to disappoint you, but no assignment 6.
- Om

I've never ever felt this good after being fooled!

munnabhai@cse.iitb.ac.in

Life at IITB surely rocks, and so does our department :)



Starring Adil as Munna Bhai, and Sree Shankar as Circuit.

Viterbi algorithm for second order Hidden Markov model

This post is a supplement to the Viterbi article on Wikipedia I'm posting this because I couldn't find an understandable implementation of Viterbi for second order HMM anywhere (I badly needed it for my assignment). So, Anup, Saurabh and I put our heads together and modified the Wiki article's Viterbi code to work for 2nd order HMM.

The story goes thus(from Wiki) - Two friends, Alice and Bob, who live far apart from each other and who talk together daily over the telephone about what they did that day. Bob is only interested in three activities: walking in the park, shopping, and cleaning his apartment. The choice of what to do is determined exclusively by the weather on a given day. Alice has no definite information about the weather where Bob lives, but she knows general trends. Based on what Bob tells her he did each day, Alice tries to guess what the weather must have been like.

Alice believes that the weather operates as a discrete Markov chain. There are two states, "Rainy" and "Sunny", but she cannot observe them directly, that is, they are hidden from her. On each day, there is a certain chance that Bob will perform one of the following activities, depending on the weather: "walk", "shop", or "clean". Since Bob tells Alice about his activities, those are the observations. The entire system is that of a hidden Markov model (HMM).

Alice knows the general weather trends in the area, and what Bob likes to do on average. start_probability reflects Alice's belief that it is rainy on a given day, there is a probability of 0.7 that it'll rain the next day as well.

Below is the python code (with some helpful print statements added). Feel free to copy :)

states = ('Rainy', 'Sunny')

observations = ('walk', 'shop', 'clean')

start_probability = {
'Rainy|Rainy' : 0.7,
'Rainy|Sunny' : 0.3,
'Sunny|Rainy' : 0.4,
'Sunny|Sunny' : 0.6
}

transition_probability = {
'Rainy|Rainy' : {'Rainy' : 0.8, 'Sunny' : 0.2},
'Rainy|Sunny' : {'Rainy' : 0.5, 'Sunny' : 0.5},
'Sunny|Rainy' : {'Rainy' : 0.6, 'Sunny' : 0.4},
'Sunny|Sunny' : {'Rainy' : 0.3, 'Sunny' : 0.7},
}

emission_probability = {
'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}

def forward_viterbi(obs, states, start_p, trans_p, emit_p):
T = {}
for state1 in states:
  for state2 in states:
  ##          prob.           V. path  V. prob.
      T[state1+"|"+state2] = (start_p[state1+"|"+state2], [state2], start_p[state1+"|"+state2])
for output in obs:

  U = {}
  print "--------------------\nObservation:",output
  for next_state in states:
      total=0
      argmax=None
      valmax=0
      print "Next state:"+next_state
      for curr_state in states:
          for prv_state in states:
              print "\tprv_state|curr_state:",prv_state+"|"+curr_state
              try:
                   (prob, v_path,v_prob)=T[prv_state+"|"+curr_state]
              except KeyError:
                   (prob, v_path,v_prob)=T[prv_state+"|"+curr_state]=(0,None,0)

              p=emit_p[curr_state][output] * trans_p[prv_state+"|"+curr_state][next_state]
              prob *= p
              v_prob *= p
              total += prob
              if v_prob > valmax:
                   argmax=v_path+[next_state]
                   valmax=v_prob
              print "\t\t",v_path,v_prob
      U[curr_state+"|"+next_state] = (total, argmax, valmax)
      print "\targmax:",argmax,"valmax:",valmax
  T=U  
## apply sum/max to the final states:
total = 0
argmax = None
valmax = 0
for state1 in states:
  for state2 in states:
      try:
          (prob, v_path, v_prob) = T[state1+"|"+state2]
      except KeyError:
          (prob, v_path, v_prob) = T[state1+"|"+state2]=(0,None,0)
      total += prob
      if v_prob > valmax:
          argmax = v_path
          valmax = v_prob
return (total, argmax, valmax)

def example():
return forward_viterbi(observations,
                      states,
                      start_probability,
                      transition_probability,
                      emission_probability)

res=example()
print "\nResult:",res

Side-Middle Berth!!!

Population is increasing. There's no space for more lines, we can't introduce new trains. So what do we do? Increase packing density :)

My first 0

I got my first ever 0 in AI mid sem exams. Prof. Pushpak Bhattacharyya had a wry smile on as he distributed the answerbooks, as if to say "Welcome to IIT". I managed a BB in the subject :-)

A do-anything firefox toolbar

We have a course called "Software Lab" at IITB. The agenda of this course is - one programming language every week, with a side effect - you fall in love with linux and everything that is free and open source. As a part of the course, we have to contribute something to the open source community. So, I, along with Sumair and Sree developed "Run-a-prog", a do-anything toolbar for firefox. Screenshot

Run-a-prog allows you to run ANY program on the text selected on a webpage. For example, if you have a text2speech program, you can add it to the toolbar and make it read out the text you selected on the page at the click of a button. You can write your own programs using any programming language of your choice and add it to the toolbar, and run it on selected text. All your program has to do is take a file name as a command line argument. Besides this, there are a few other useful features as well ;)



Run-a-prog has been tested on Fedora Core, Ubuntu and Windows XP and works fine with Firefox 2.0 and 3.0. To install Run-a-prog, download our cross platform installer and open it with firefox. Comments and suggestions are welcome :)

I have published the project on Mozdev.org, and can be accessed at http://runaprog.mozdev.org

Here is a presentation which gives an overview of the functionality and design. The source code and the documentation is available here.