projects

Probabilistic Postal Address Elementalization

I haven’t posted in a few months because most of my time has been consumed with work and school. With respect to school, I have been taking Statistical Natural Language Processing at New York University. As my final project for this class, I have been working on something which I have been curious about for quite some time – probabilistic postal address elementalization.

What exactly does “postal address elementalization” mean? This is the process of breaking a postal address into tokens and classifying the function of each token, such as house number, street suffix or zip code. For my experiment, I created twelve distinct classes: five for administrative areas (country, state, county, city and neighborhood), one for postal codes and six for street address components (house number, prefix, pre-directional, base street name, post-directional and suffix). An example of an elementalized address is below:

address_elementalizationAlthough this seems like a straightforward problem, it is complicated by the fact that many countries have different languages and address formats. For example, in Ghana and Cameroon, there is no standard postal code system. In the Netherlands and Ireland, there is no province or state in the address. In some countries, such as France and Mexico, the postal code is placed before the city whereas other countries place it after the city. Furthermore, known names of terms in specific classes can overlap, so disambiguating streets can be tricky, like Avenue N in Brooklyn (“N” could be a post-directional or street name) or N Broadway in St. Louis (“St.” could be a suffix or part of a city name).

Traditionally, address elementalization has been implemented by building rule-based systems to handle each individual address format. This makes the process of building international address parsers very time consuming as one would need to implement a new rule-based parser for every single country. By building a statistical model to do this, implementing a new international format is as simple as training the model with a new data set.

Some interesting characteristics of postal addresses are that they have a grammar (as defined by the address format) and the elements are contextually dependent. These traits make the problem well-suited for natural language processing. There are natural language processing techniques that are used for similar purposes, namely part-of-speech taggers which are used to classify the parts of speech in a sentence.

For my final project, I looked at four different techniques of statistical part-of-speech tagging and applied them to the problem of postal address elementalization. The code is here.

The first strategy was a Hidden Markov model (HMM) tagger. HMMs are statistical models that can be used to find the most likely sequence of states for an input. This is done by using transition probabilities (the probability of a specific state given the previous state) and emission probabilities (the probability of the proposed state given the current input token). These probabilities are learned by observing a training set.  The model then tries to classify the input left to right, calculating the probability of a proposed state as the product of the transmission probability, emission probability, and maximum probability from the previous state. The model tries different state combinations over the input and returns the sequence of possible states with the highest overall probability.  A variation of this is the trigram HMM tagger, which uses the two previous probabilities to calculate the transition probability.

The second strategy was a Maximum-Entropy Markov model (MEMM) tagger. MEMMs are similar to HMMs in that they try to find the sequence of states that has the maximum total probability for an input. However, instead of just using observed counts for the transition and emission probabilities, we train a maximum-entropy distribution to calculate the probabilities. The main advantage of doing this is that we can have custom features factor into the probability, such as the current token length or whether the token contains a number. This allows for greater flexibility in tuning the tagger, but it makes the overall classification time slower.

The third strategy was a Transformation-Based Learning (TBL) tagger, also known as a Brill tagger. The TBL tagger generates rules based on observations in training. These rules indicate observed conditions on when a tag should be swapped with a different tag. During classification, initial tags are assigned to the terms based on the observed probability. The tagger iterates through the rules which were learned in training, swapping tags as necessary, until there are no more rules to be applied or a given score threshold is met.

The fourth strategy was a Conditional Random Field (CRF) tagger. CRFs implement a number of feature functions which take the proposed states and the input observation and return some value between 0 and 1. These features, like the features in MEMMs, can be just about anything, such as whether the current token is capitalized or whether it ends in -ed. Each of these feature functions has a different weight based on observations in training. The score for a sequence of states is calculated by summing the feature functions for every word over all words and then normalizing. Just like HMMs and MEMMs, we find the sequence that maximizes the overall probability.

From my initial work, I found that the Maximum-Entropy Markov model and the Conditional Random Field taggers consistently had the highest overall accuracy of the group. Both consistently had accuracies over 98%, even on partial addresses. For full format American addresses, these taggers had an accuracy around 99.7%. If I had to choose between them, I would go with the Conditional Random Field tagger as it was considerably faster in tagging the addresses.

I didn’t have enough time to finish everything that I wanted to implement, so this is still a work in progress. I still want to implement some smoothing techniques for unknown states, such as Katz backoff and Kneser-Ney interpolation. There are also a few more part-of-speech tagging techniques I would like to experiment with. I guess that old adage is true in this case – time flies when you are having fun…  🙂

DIY Night Vision Camera

I found this Instructable about how to make your own night vision camera. It seemed to be a fun project, so I decided to give it a try.

The first step is to remove the infrared (IR) filter from the camera. I broke my first camera attempting to do this. I was far more careful with my second one and successfully removed the filter. The little blue chip is the IR filter:

IMG_5319

This is how the photos look with the IR filter removed:

P1010003

Kitty is not impressed.

After successfully removing the filter, the next step was to build an IR LED array to be used as a light for the camera. With a little bit of help, I was able to laser cut a perfect array of holes for the LEDs. Following the instructions, I assembled the LED array and turned it on, only to be disappointed by an incredibly dim light.

What went wrong? Here’s the point where I confess that I am relatively new to electronics, and so there are certain lessons that are yet to be learned.  I wired the LEDs incorrectly. I got a second batch and wired them together.

IMG_8372

And still the array was too dim. It was time to really understand how the circuit of the array worked. There was something more at play here. I found a really cool LED array calculator online that helped me get to the bottom of my problem. I had to examine the LEDs more closely. The instructions use infrared LEDs from Radio Shack, which have a 940 nm wavelength, a 100 mA forward current and a 1.28 volt forward voltage. My first two attempts used LEDs that had a forward voltage of 1.5 volts, which meant that the LEDs were not getting enough power. I ordered a new set of IR LEDs with a lower forward voltage of 1.2 volts and assembled the array for the third time.

IMG_8378

The third attempt was better. With the new array, I was able to capture photos in the dark!

A hand in the dark

 I did a little test to get a feel for how well the camera worked. First, I set up a small scene to photograph. I was interested to see how the camera could capture color and detail. Here is the control photo, taken with my normal camera:

Control Photo

First, I took a photo with the lights on. The room was somewhat dark, so the photo did not come out very clear:

Lights on

Next, I took a photo with the lights off, about one foot away from the objects. The detail was still somewhat clear, although differentiating colors was not really possible.

P1010082

The second photo was taken from two feet away. At this point, some objects are no longer visible.

Two feet

The final photo was taken from three feet away. The objects are almost imperceptible at this point.

P1010079

Although it was fun to build this, it isn’t very practical for real-world use. The major problem seems to be the power, as the 9 volt battery drains very quickly and is not strong enough to power many high-power infrared LEDs. If I go back to this project, the first step would be to build an array with a larger power supply and brighter LEDs. In the interim, I will just have to be content with taking nighttime pictures of things up close.

Blinky Box

This was a gift for my two year old nephew. Since he is a fan of lights and buttons, I wanted to make something blinky for him to enjoy. The concept was simple: make a clear box with buttons and lights that would change color and pattern based on the buttons that were pressed.

Blinky Box

First, I had to find a clear acrylic box large enough for some LEDs, switches, buttons and a microcontroller. I found this great polycarbonate box from Hammond Manufacturing that seemed to be the right size. Next, I needed to find some buttons that could take a beating. Fortunately, Adafruit sells some translucent arcade buttons in bright colors. The lighting was a no-brainer as I am a huge fan of Adafruit’s addressable LED strips. I also found a glowy on/off switch for the power. Somewhere along the way, I thought it would be a cool idea to add a rotary knob so that he could select different blinking patterns.

The next step was to assemble the pieces and wire everything together. The polycarbonate box was harder to work with than I had hoped. The polycarbonate would discolor if I used the laser cutter, so I found myself drilling all of the holes with a rotary tool. I then added the buttons, knob and on/off switch.

Assembly

Once all of the bits were together, I had to add a microcontroller to control the button states and light transitions. I decided to go with the Teensy 3 as it was what I had on hand (and I had yet to work with one). Also, Teensy 3 allows all digital pins to be interrupted (as opposed to four on the Teensy 2), which would simplify reading the button state. The other great reason for selecting the Teensy is that it already has an Encoder library, which makes reading the knob state simple.

The code was easy. Interrupts on the arcade buttons would change a variable representing the color. The interrupt for the black button would kick off a rainbow display routine. In the main loop, I polled for changes in the rotary encoder state and transitioned the lights accordingly. When I was finished, there were five main light colors (white, red, yellow, green and blue), one rainbow routine and six possible blink patterns (always on, fade on/off, blink on/off, chasing light, random twinkling lights and alternating lights).

IMG_6082

I saved the hardest part for last: power. I wanted something that my nephew couldn’t disturb, so anything outside of the box was out of the question. Regular batteries would require opening the box to change, so I thought something rechargeable would work better. I decided to go with a Lithium Ion battery. Unfortunately, these are generally around 3.7 volts and the LED strips require 5 volts. This meant that I needed to find a way to recharge the battery from the outside and find a way to step up the voltage. Fortunately, SparkFun sells a power cell board that does both. Yay!

Power Supply

I added a power jack to the box and used an old 5 volt AC adapter to supply the charging power. I then connected the power cell board and the battery using this handy tutorial. Fortunately, the charging of the battery seemed to work! Unfortunately, the power cell board only provides 600 milliamps at 5 volts, which is not enough power to run a full meter of the LED strip. Sadly, I had to cut the strip in half. It was still impressive even with just one loop of lights! To make the battery last even longer, I also implemented some of the suggestions for conserving power with the Teensy.

The best part about this toy is that it is fully programmable. As he gets older, I can program new features or games into it. Perhaps one day, I can even teach him to program it himself! 🙂

Here is a short video of the assembled box

Motion-Sensitive Paper Lantern

Back in February, I made a motion-sensitive lantern for the Lunar New Year. The idea was simple: have a lantern that appeared to be mostly plain but would reveal a design when a person moved closer to it.

Lantern from far away

The easiest form to use was a round paper lantern. I started with a 14″ white paper lantern and some markers. I then attempted to draw some snakes on it, as 2013 is the year of the snake. As I am not an artist, let’s pretend that these squiggles look like snakes.

Lantern up close

The next part was to add some lighting. The lighting needed to change color. I decided to go with LED strips from Adafruit, as I could wrap them in the center of the lantern and have fairly uniform lighting. I had some left over pieces from a previous project and this seemed like the perfect occasion to use them.

Next, the lighting needed to respond to motion. There were a couple of sensors that would have allowed me to detect motion, but I decided on a passive infrared (PIR) sensor. Interestingly, these sensors work by detecting rapid changes in infrared radiation (including those given off by body heat).

PIR Sensor

The code for this was very straightforward. The PIR sensor sends a high signal on its output pin whenever motion is detected. Therefore, it’s as simple as polling the output pin with digitalRead() and transitioning the lights based on changes in the output pin state.

Finally, I had to find a lightweight power source. I found an Energizer power pack, which was the perfect power supply for Teensy. It even came with a mini USB adapter, which meant that I could plug it directly into the Teensy without having to solder anything. Here is the final internal assembly of the lamp!

The final assembly

And here is the lamp, fully assembled and running!

Dance Dance Revolution Keyboard

Over the weekend, I turned a Dance Dance Revolution dance pad into a keyboard input device. The pad will be used as part of a larger project at the NYC Resistor 2013 Interactive Show. Here is how I did it.

The pad itself is one of those metal arcade style Dance Dance Revolution pads. The only output was a 15 pin D-Sub connector, much like a VGA cable.

Dance Pad

The dance pad connector

Fortunately for me, a fellow Resistor already went through the arduous task of figuring out the pinout for this particular pad. A little further research based on the pinout revealed that this particular model was a TX-1000. The full pinout can be found here.

The next task was to wire the connector to a microcontroller and try to read input from the board. I decided to go with a Teensy as it already has a library that supports keyboard output. In order to have the Teensy be recognized as a HID by a computer, you have to change the USB type. This can be done by changing Tools -> USB Type to “Keyboard + Mouse + Joystick”.

Now I needed to write some code to read the input from the dance pad and convert it to keyboard output. First, I had to define the input pins in the setup function of the Teensy code. This was done with pinMode using pullup resistors.

pinMode(leftPin, INPUT_PULLUP);   // Left arrow

The next step was to read the input from the control pad and send the corresponding keyboard character when a pad was pressed. Fortunately, Teensy offers a Bounce library which makes debouncing switches easy. First you declare a Bounce object on your input pin.

Bounce leftButton = Bounce(leftPin, 400);

Next, poll the pin in the loop() method for state changes. Once a state change is detected, send the corresponding keyboard key.

if (leftButton.update()) {
    if (leftButton.fallingEdge()) {
         Keyboard.set_key1(KEY_LEFT);
    }
}

Once everything was wired up and the Teensy code was running, everything seemed to work… except the right arrow. Unfortunately, this meant that it was time to take the pad apart!

Underneath a panel

The wires

After a bit of investigating and a few false starts, I found that the wires were easily accessible under the up arrow. Thankfully, the wires for each button were a different color so it was easy to determine which wires to test. Testing with a multimeter showed that the right signal wire in the cable was not working. After running a new signal wire for the right pad (and soldering everything else I cut), everything worked as expected! I then used a solderable D-Sub connector and enclosure from RadioShack to make a connector for the pad.

The completed connector

I could then hook the dance pad connector to my homemade connector and then a mini USB to USB cable from the Teensy to my computer. There is nothing more satisfying than navigating your computer by dancing!