Machine learning techniques for parsing strings?

Question

I have a lot of address strings:

1600 Pennsylvania Ave, Washington, DC 20500 USA

I want to parse them into their components:

street: 1600 Pennsylvania Ave
city: Washington
province: DC
postcode: 20500
country: USA

But of course the data is dirty: it comes from many countries in many languages, written in different ways, contains misspellings, is missing pieces, has extra junk, etc.

Right now our approach is to use rules combined with fuzzy gazetteer matching, but we'd like to explore machine learning techniques. We have labeled training data for supervised learning. The question is, what sort of machine learning problem is this? It doesn't really seem to be clustering, or classification, or regression....

The closest I can come up with would be classifying each token, but then you really want to classify them all simultaneously, satisfying constraints like "there should be at most one country;" and really there are many ways to tokenize a string, and you want to try each one and pick the best.... I know there exists a thing called statistical parsing, but don't know anything about it.

So: what machine learning techniques could I explore for parsing addresses?

Answer 1

This can be seen as a sequence labeling problem, in which you have a sequence of tokens and want to give a classification for each one. You can use hidden Markov models (HMM) or conditional random fields (CRF) to solve the problem. There are good implementations of HMM and CRF in an open-source package called Mallet.

In your example, you should convert the input to the format below. Moreover, you should generate extra-features.

1600 STREET
Pennsylvania STREET
Ave STREET
, OUT
Washington CITY
, OUT
DC PROVINCE
20500 POSTCODE
USA COUNTRY