30 Days of Python: Day 30 Saving the Whales

I’ve made a small project every day in python for the past 30 days (minus some vacation days). I’ve learned many new packages and  made a wide variety of projects, including games, computer tools, machine learning, and some science. It was a lot of fun.

Day 30: Saving the Whales

For my last project, I thought I would revisit the Whale Detection Competition on Kaggle that I competed in last year. The goal was to train a model that could detect the presence of a whale call in an audio file. The data was provided by Cornell and consisted of 2 second sound recordings  from buoys out in Massachusetts Bay of either background ocean noise or a Right whale’s “up call” which starts low and rises up. The Right whale is endangered (only 400 left) and doesn’t call out very often so it can be harder to detect than, say, a Humpback whale, so better detection algorithms will help save the whales from being hit by shipping traffic.

I did pretty well last year in the competition, scoring 0.95 Area Under the Curve score (AUC) where perfect would be 1.0. I utilized the deep learning models that I learned in Geoffery Hinton’s Coursera course on Neural Networks to build the models but I did all of the work in R, which brings me to the present project.

My main tool over the years for data analysis has been Matlab at school and then at work, but last year, I learned R as an open source alternative. I took the deep belief net code that I learned from the Hinton course and retooled it from Matlab to R. I added evaluation features and hyper-parameters  for controlling various learning rates and just in general kept developing that code to work on further projects.

But the R code was clunky and messy. It got harder and harder to add new features each building on previous functions. Additionally a lot of the algorithms I wanted to try out and learn were in Matlab or Python (for instance the winning solution to the whale detection challenge). This was one of the big motivations behind learning Python. So in order to fully transition from R to Python I thought I would take the time to rework the Whale detection code into Python and learn about the various data tools in the process.

Fair warning: I didn’t finish the deep learning portion of the project, but I walk through what I did complete and show how a simple model fairs with the feature set that I constructed.

Pre-processing and Feature Extraction:

The data is a zipped up folder of .aiff files, so the first thing that’s necessary to build a program to read in the files and extract whatever features are needed for the model. In R there was no direct way to read in a .aiff file so I had to run the sox tool in a .bat file to convert the files into .wav files. To my delight not only is there an easy way to read .aiff files in Python, but it is part of the standard modules – batteries included so to speak.

With the file ingested, I converted it to a numpy array and then used matplotlib to plot a spectrogram of the audio file. A spectrogram is way of examining the spectrum of a time signal as it evolves over time. Specifically it takes short chunks of time, computes the FFT, and then plots these snapshots of the spectrum on the y axis versus time on the x axis (amplitude of the spectrum is intensity in the image).

Here’s how to do that in code:

plt.figure(figsize=(18.,12.))
for i, file_name in enumerate(file_names[j*N_plot:(j+1)*N_plot]):
    f = aifc.open(os.path.join(data_loc,train_folder,file_name), 'r')
    str_frames = f.readframes(f.getnframes())
    Fs = f.getframerate()
    time_data = np.fromstring(str_frames, np.short).byteswap()
    f.close()

    # spectrogram of file
    plt.subplot(N_plot/4, 4, i+1)
    Pxx, freqs, bins, im = plt.specgram(time_data,Fs=Fs,noverlap=90,cmap=plt.cm.gist_heat)
    plt.title(file_name+' '+file_name_to_labels[file_name])

Instead of just looking at one file, which might not be a great example and would only show either a whale call or not a whale call, I used matplotlib to tile multiple images to get a better sense of the data. This was way easier to do then my experiences with R and being able to easily control its size was easier than Matlab.

Here’s what some of those look like:

Whale Call Spectrograms

Right Whale Call Spectrograms (calls are labelled 1)

To make this useable as inputs to the data model, I needed the raw data that went into the image that matplotlib created, which was readily available in the data returned by the specgram function. As is this would yield almost 3000 features per audio file which is too much for my computer to handle (there are 30,000 audio files). So I used the frequency vector and bin vector (time) to eliminate the lowest and highest frequencies as well as the beginning and ending of each clip. The result was reduced to 600 features per clip, which is more manageable.

I turned the plotting routine into a function, wrapped that in a list comprehension which looped over each file in the the list of files and finally constructed a numpy array out of the resulting list. I used cPickle to save this to disk so I wouldn’t need to repeat it. This portion of the project took me a while to do since I had never done any of these operations before and my original whales project was quite a while ago.

Building Restricted Boltzmann Machines and Deep Belief Nets

Unfortunately, I ran out of time and was unable to complete the conversion of the stacked RBM code. I did however complete the optimize function that could perform the model updates and I was able to verify that the RBM executed properly (although I couldn’t test its efficacy).

My deep learning model is a Neural Network constructed from a Deep Belief Net, which in turn is made of stacked Restricted Boltzmann machines. Restricted Boltzmann machines (RBM) are like one layer of a neural network but they are trained in a special way, Contrastive Divergence, that doesn’t require the data labels. This unsupervised learning algorithm seeks to improve the ability of the RBM to represent the data by training it to reconstruct the the input data from the hidden layer of the network. For a better explanation of why this works, I recommend Hinton’s homepage which is full of his papers and lectures.

Here’s the Python version of the Contrastive Divergence algorithm:


def logistic(x):
    '''Computes the logistic'''
    return 1./(1 + np.exp(-x))

def sample_bernoulli(probabilities):
    '''Samples from a bernoulli distribution for each element of the matrix'''
    return np.greater(probabilities, np.random.rand(*np.shape(probabilities))).astype(np.float)

def cd1(model, visible_data):
    '''Computes one iteration of contrastive divergence on the rbm model'''
    N_cases = np.shape(visible_data)[1]

    #forward propagation of the inputs
    vis_prob_0 = visible_data
    vis_states_0 = sample_bernoulli(vis_prob_0)

    hid_prob_0 = logistic(model['W']*vis_states_0 + model['fwd_bias'])
    hid_states_0 = sample_bernoulli(hid_prob_0)

    #reverse propagation to reconstruct the inputs
    vis_prob_n = logistic(model['W'].T*hid_states_0 + model['rev_bias'])
    vis_states_n = sample_bernoulli(vis_prob_n)

    hid_prob_n = logistic(model['W']*vis_states_n + model['fwd_bias'])

    #compute how good the reconstruction was
    vh0 = hid_states_0 * vis_states_0.T / N_cases
    vh1 = hid_prob_n * vis_states_n.T / N_cases

    cd1_value = vh0 - vh1

    model_delta = dict([('W', cd1_value),
                        ('fwd_bias',np.mean(hid_states_0 - hid_prob_n, axis=1)),
                        ('rev_bias',np.mean(visible_data - vis_prob_n, axis=1))])
    return model_delta

A Deep Belief Network (DBN) is a stacked up version of pre-trained RBM models which can then be treated as a Neural Network and fine tuned by the standard back propagation algorithm using the data labels. Because the model is pre-trained on the data, the back propagation step doesn’t have to change as much to get a good model and because the pre-training didn’t use the labels it is less likely to overfit.

K Nearest Neighbors

To achieve some closure in this project, I ran the feature set that I built through the K nearest neighbors algorithm in scikit-learn. The results weren’t great but they were about the same as the Conrell Benchmark for the competition. I really like how easy it is to get all of the reporting tools so easily in python:

Classification report for classifier KNeighborsClassifier(algorithm=auto, leaf_size=30,
metric=minkowski, n_neighbors=5, p=2, weights=uniform):
            precision recall f1-score support
          0      0.84   0.90     0.87   11286
          1      0.61   0.48     0.54    3714

avg / total      0.78   0.79     0.79   15000

Confusion matrix:
    [[10119 1167]
     [ 1923 1791]]
AUC:
0.689413478377

Conclusions

Overall I am very pleased with writing these algorithms in Python. I had to jump through many hoops to get the matrices to work right when I wrote it in R. For Python, the ability to use numpy algorithms over and over again in clear and simple ways was quite nice. I think I was more slowed down by reading my old code in R then writing the Python version, although testing each bit of code to make sure it was right did also take some time.  I decided to end this project early because I knew I wouldn’t be able to write good Python code if I rushed it any more than I already had, and I plan on using Python for a while so it was better to get it right. Rest assured I will follow up with the completion of the conversion to Python; after all, the Whale Detection Challenge inspired half of this blog’s name.

Final thoughts for 30 Days of Python

These 30 days have been a great experience. I did find the process quite exhausting at times and I wasn’t always sure I would get through it. I came out the other side though with a lot more knowledge of how to do useful things in Python. I’ve already started applying this knowledge at work. I hope to continue this learning process at a slower pace and also take the time to dive into some deeper projects that I thought of while doing my 30 days. I want to thank everyone who left comments, liked a post (here or on google+), or even just read what I wrote. Knowing that people were paying attention really kept me to my schedule and I learned a lot of useful information from people’s feedback.

Thanks,
Robb

30 Days of Python: Day 29 Visualizing Particle Filters

I’m making a small project every day in python for the next 30 days (minus some vacation days). I’m hoping to learn many new packages and  make a wide variety of projects, including games, computer tools, machine learning, and maybe some science. It should be a good variety and I think it will be a lot of fun.

Day 29: Visualizing Particle Filters for Robot Localization

Back in the spring I took Udacity’s Artificial Intelligence for Robotics class. It was a great class that covered a wide range of topics all centered around the algorithms that go into an autonomous car (the instructor, Sebastian Thrun, is the guy behind Google’s and Stanford’s self-driving car). I really enjoyed that the class had python based homework assignments. One assignment was to program a particle filter to perform localization for a robot. A particle filter uses several hundred “particles” to model a robot’s motion and then the average position acts as an estimate of the robot’s position, at least, if it doesn’t diverge. Because the course had us programming in a web interface, we couldn’t do much visualization of what was going wrong. Now that I’ve learned more about python, I thought I’d give it a crack offline.

So for today’s project, I used the python turtle package to draw the world, the robot, and the particles. You can actually watch the particles converge as they go through each motion the robot takes. Below is a GIF of the robot and particles in action. The robot moves through a sequence of moves first in blue. We have no idea where the robot is so we initialize the particles all over the world (in red) with all possible orientations. We do however know what move the robot made and how far the robot was from the four landmarks (black circles). For each step of the particle filter we move all the particles according to how the robot moved, estimate the probablity of the particle being correct by comparing its measurements to the robot’s, and then we resample the particle distribution. That resampling piece is key. The particles that are most likely to be right get resampled the most and unlikely ones don’t get sampled at all. Because both the motions and measurements are noisy, the resampled particles diverge from each other. But because any that diverge too much from the actual robot die off, the clump of particles converge around the robot. In the picture below the particles alternate between a movement and the subsequent resampling.

Robot Localization by Particle Filer

Robot Localization by Particle Filer

After just one motion,  measurement, and resampling the particles have already closed in quite a bit on the robot. Overall turtle worked really well for visualizing this. I thought about static plots with matplotlib but the animation is definitely the most important part for this. I might do another project in the future centered around more complex particle filters because they are a pretty good way to localize on a map.

 

30 Days of Python: Day 28 Interactive Unix Tools

I’m making a small project every day in python for the next 30 days (minus some vacation days). I’m hoping to learn many new packages and  make a wide variety of projects, including games, computer tools, machine learning, and maybe some science. It should be a good variety and I think it will be a lot of fun.

Day 28: Interactive Unix Tools

For today’s project, I went back to my utilities projects and modified them to work well in the interactive python shell. These are the tools that duplicated Unix functionality for windows (cat, head, grep, wc, nl, and tail). The idea was to make using windows more like using the Linux or Unix shell. The tools worked great from the windows command line but sometimes you’d prefer to be in the more powerful python interactive shell. The tools as they were always dumped the output to standard out. It wasn’t possible to chain them together and create pipelines in the python shell.

To remedy this I made each of the tools return a generator. In order to keep the windows command line functionality, I changed the main command to call a wrapped version of the function that sends the generator to standard out. One other feature I added was the ability for each tool to work with either a file object or a file name. Here’s an example of how this pattern was applied to nl the line numbering tool:

def nl_file_name(file_name):
'''Generates numbered lines for a file'''
    with open(file_name) as f_in:
        return (line for line in list(nl_file_in(f_in)))

def nl_file_in(file_in):
    '''Generates numbered lines for an open file'''
    return (str(i)+'\t'+line for i, line in enumerate(file_in))

def nl(file1):
    '''Numbers the lines in the file'''
    if isinstance(file1,str):
        return nl_file_name(file1)
    else:
        return nl_file_in(file1)

def nl_dump(file1):
    '''Numbers the lines in the file'''
    sys.stdout.writelines(nl(file1))

Note that the version that opens the file has to force the generator into a list in order to deal with the file closing. To truly create a pipeline with out worrying about memory issues, it would be best to use the tools with the files already open instead of by file name. Adding the interactive mode to the utilities, leaves me pretty satisfied with my toolset.

 

For those that are interested, here’s my desert island utilities repository: https://github.com/robb07/utilities

30 Days of Python: Day 27 Traveling Electrons

I’m making a small project every day in python for the next 30 days (minus some vacation days). I’m hoping to learn many new packages and  make a wide variety of projects, including games, computer tools, machine learning, and maybe some science. It should be a good variety and I think it will be a lot of fun.

Day 27: Traveling Electrons

For today’s project, I simulated an electron moving in electric and magnet fields. I used the vpython package which is a great tool for physical simulations because it is simple to do the vector calculations in and to pair those with visible objects in a screen. Unlike the orrery project where I used a clockwork model of the system, for this project I simulated the net force on the particle. The Lorenz Force describes the force of an electric and magnetic field on a particle charge. Here’s what it looks like in code:

while True:
    F = particle.charge*(E_field.mag*E_field.axis + particle.vel.cross(M_field.mag*M_field.axis))
    accel = F/particle.mass
    particle.vel = particle.vel + accel*DT
    particle.pos = particle.pos + particle.vel*DT

Because the magnetic force on the particle is perpendicular to both the particles velocity and the magnetic field, it creates a centripetal force on the particle sending it in a circle:

Only Magnetic Field Circle

Only Magnetic Field – Circle

If the particle has a small portion of the velocity in the same direction as the magnetic field, the result is a helix in the direction of the magnetic field:

Only Magnetic Field Helix

Only Magnetic Field – Helix

If an electric field is added on top of that the helix expands in the direction of the electric field:

Electric and Magnetic Field - Expanding Helix

Electric and Magnetic Field – Expanding Helix

If the electric field points to a side then it causes drift:

Electric and Magnetic Field - Drifting Helix

Electric and Magnetic Field – Drifting Helix

I initially had a bug in my code that made all of the shapes wrong and not match my intuition. I finally spotted it and the simulation started behaving correctly. That’s a good lesson learned to really work out what a few solutions should look like before moving on to the more complex ones. I’d like to spend more time with this one and see if I can add in varying electromagnetic fields to see what I can get the electron to do!

For those that are interested, here’s my science simulations repository: https://github.com/robb07/science_sims

30 Days of Python: Day 26 Cryptoquip

I’m making a small project every day in python for the next 30 days (minus some vacation days). I’m hoping to learn many new packages and  make a wide variety of projects, including games, computer tools, machine learning, and maybe some science. It should be a good variety and I think it will be a lot of fun.

Day 26: Cryptoquip

For today’s project, I made a cryptoquip game. This is my favorite newspaper puzzle where the goal is to decode a witty saying that’s been encrypted with a substitution cipher. Spaces and punctuation are left in tack so it’s all about guessing which letters are which by looking for letters that might be by themselves (a, I) or double letters (often e, l, etc.). It’s a fun puzzle to play. Here’s a screenshot of one that’s nearly solved:

Einstein Quote

The encryption method is very easy to implement. The key is a dictionary with a random shuffle of a ciphertext alphabet mapped to the plaintext alphabet. The ciphertext (the encoded message) uses all caps, while the plaintext uses lower case. A simple list comprehension can do the substitution:

def encrypt_substitute(message, key):
    '''Encrypts the message with a substitution cipher'''
    return ''.join([key[m] if m in key else m for m in message])

For the guessing portion, the player moves the cursor around with the arrows and can work in either the message or on the side in the key. The working key is initialized with all underscores for each ciphertext letter. The same encryption method does the encryption with the reversed key. I wanted to add the ability click on the letter you want to change but I ran out of time. Perhaps I’ll come back and add that after the 30 days are up, which isgetting quite close.

For those who are interested here’s my github repo for the games project: https://github.com/robb07/python_games

 

 

30 Days of Python: Day 25 Packaging

I’m making a small project every day in python for the next 30 days (minus some vacation days). I’m hoping to learn many new packages and  make a wide variety of projects, including games, computer tools, machine learning, and maybe some science. It should be a good variety and I think it will be a lot of fun.

Day 25: Packaging

Today’s project was learning about packages in Python. I refactored my code for both the utilities project and the games projects to use packages. To make a package in python you simply add an __init__.py file to a directory. The resulting package will have the same name as the directory did. And this is why I had to refactor my code; I didn’t want packages named src. Originally, my code was just in the src directory in the eclipse projects:

#The original projects:
utilities/
    src/
        cat.py
        du.py
        ...
        tail.py
        wc.py
    resources/
    README.md

games/
    src/
        breakout.py
        fifteen.py
        menu.py
        tetris.py
        ...
        sprite.py
        simplegui.py
    lib/
    README.md

The new version has one package in the utilities project (utilities) and two in the games (game_tools and games):

#The refactored projects:
utilities/
    utilities/
        __init__.py
        cat.py
        du.py
        ...
        tail.py
        wc.py
    resources/
    README.md

games/
    src/
        game_tools/
            __init__.py
            sprite.py
            simplegui.py
        games/
            __init__.py
            breakout.py
            fifteen.py
            tetris.py
            ...
        menu.py
    lib/
    README.md

I had to keep menu.py at the top level if I wanted to call it directly (otherwise it has to be called from inside games and the absolute paths are all wrong). It’s still a work in progress but I can use import statements in interactive mode to pull in the various modules and start up the games. If you know of any good links that explain project setup, feel free to leave them in the comments!

For those who are interested here’s my github repo for the games project: https://github.com/robb07/python_games

And here’s my desert island utilities repository: https://github.com/robb07/utilities

 

30 Days of Python: Day 24 Fractal Turtles

I’m making a small project every day in python for the next 30 days (minus some vacation days). I’m hoping to learn many new packages and  make a wide variety of projects, including games, computer tools, machine learning, and maybe some science. It should be a good variety and I think it will be a lot of fun.

Day 24: Fractal Turtle

Today’s project was using the turtle package to draw fractals. These fractals can all be expressed as an “L-System” which means that each iteration of the fractal can be created from the previous iteration based on a simple rule set applied to a string describing the “path” that the turtle takes. Here’s the 4th iteration of the Koch’s snowflake:

Koch Snowflake

Koch Snowflake

And another classic is the Dragon fractal, which was featured in the Jurasic Park book:

Dragon Fractal

Dragon Fractal

I’ve drawn fractals before but always as static plots. By using the turtle package in python I was able to watch it draw the fractal. For each fractal there’s a turning angle, starting path string, and a string replacement rule. The letters in the strings are turned into directions for the turtle (R: right turn, L: left turn, F: forward).


def expand_path(N, path='F', rules=dict([])):
    '''Expand the path using the rule set'''
    for i in range(N):
        path = ''.join([rules[p] if p in rules else p for p in path])
    return path

#Koch snowflake
rules = dict([('F','FLFRRFLF')])
path = 'FRRFRRF'
angle = 60

#Dragon -- X and Y are ignored by the turtle but expanded during the iterations
rules = dict([('X','XLYF'),('Y','FXRY')])
path = 'FX'
angle = 90

...

path = expand_path(N, path, rules)
the_turtle = turtle.Turtle()

for p in path:
    if p == 'R':
        the_turtle.right(angle)
    elif p == 'L':
        the_turtle.left(angle)
    elif p == 'F':
        the_turtle.forward(step_size)

Here’s the first few iterations of the path for the Koch Snowflake (it starts as a triangle):


0 FRRFRRF
1 FLFRRFLFRRFLFRRFLFRRFLFRRFLF
2 FLFRRFLFLFLFRRFLFRRFLFRRFLFL
  FLFRRFLFRRFLFRRFLFLFLFRRFLFR
  RFLFRRFLFLFLFRRFLFRRFLFRRFLF
  LFLFRRFLFRRFLFRRFLFLFLFRRFLF