implementation for the address parser.
One of the main issues with the greedy averaged perceptron tagger used currently
in libpostal is that it predicts left-to-right and commits to its
answers i.e. doesn't revise its previous predictions. The model can use
its own previous predictions to classify the current word, but
effectively it makes the best local decision it can and never looks back
(the YOLO approach to parsing).
This can be problematic in a multilingual setting like libpostal,
since the order of address components is language/country dependent.
It would be preferable to have a model that scores whole
_sequences_ instead of individual tagging decisions.
That's exactly what a Conditional Random Field (CRF) does. Instead of modeling
P(y_i|x_i, y_i-1), we're modeling P(y|x) where y is the whole sequence of labels
and x is the whole sequence of features. They achieve state-of-the-art results
in many tasks (or are a component in the state-of-the-art model - LSTM-CRFs
have been an interesting direction along these lines).
The crf_context module is heavily borrowed from the version in CRFSuite
(https://github.com/chokkan/crfsuite) though using libpostal's data structures and
allowing for "state-transition features." CRFSuite has state features
like "word=the", and transition features i.e. "prev tag=house", but
no notion of a feature which incorporates both local and transition
information e.g. "word=the and prev tag=house". These types of features are useful
in our setting where there are many languages and it might not make as
much sense to simply have a weight for "house_number => road" because that
highly depends on the country. This implementation introduces a T x L^2 matrix for
those state-transition scores.
For linear-chain CRFs, the Viterbi algorithm is used for computing the
most probable sequence. There are versions of Viterbi for computing the
N most probable sequences as well, which may come in handy later. This
can also compute marginal probabilities of a sequence (though it would
need to wait until a gradient-based learning method that produces
well-calibrated probabilities is implemented).
The cool thing architecturally about crf_context as a separate module is that the
weights can be learned through any method we want. As long as the state
scores, state-transition scores, and transition scores are populated on
the context struct, we have everything we need to run Viterbi inference,
etc. without really caring about which training algorithm was used to optimize
the weights, what the features are, how they're stored, etc.
So far the results have been very encouraging. While it is slower to
train a linear-chain CRF, and it will likely add several days to the
training process, it's still reasonably fast at runtime and not all that
slow at training time. In unscientific tests on a busy MacBook Pro, so far
training has been chunking through ~3k addresses / sec, which is only
about half the speed of the greedy tagger (haven't benchmarked the runtime
difference but anecdotally it's hardly noticeable). Libpostal training
runs considerably faster on Linux with gcc, so 3k might be a little low.
I'd also guess that re-computing features every iteration means there's
a limit on the performance of the greedy tagger. The differences might
be more pronounced if features were pre-computed (a possible optimization).
- store a vector of update counts for each feature in the model
- when the model updates after making a mistake, increment the update
counters for the observed features in that example
- after the model is finished training, keep only the features that
participated in a minimum number of updates
This method is described in greater detail in this paper from Yoav
Goldberg: https://www.cs.bgu.ac.il/~yoavg/publications/acl2011sparse.pdf
The authors there report a 4x size reduction at only a trivial cost in
terms of accuracy. So far the trials on libpostal indicate roughly the
same, though at lower training set sizes the accuracy cost is greater.
This method is more effective than simple feature pruning as feature
pruning methods are usually based on the frequency of the feature
in the training set, and infrequent features can still be important.
However, the perceptron's early iterations make many updates on
irrelevant featuers simply because the weights for the more relevant
features aren't tuned yet. The number of updates a feature participates
in can be seen as a measure of its relevance to classifying examples.
This commit introduces --min-features option to address_parser_train
(default=5), so it can effectively be turned off by using
"--min-features 0" or "--min-features 1".
