Graham's Research Blog

One popular method for estimating statistical models is sampling, and in particular Gibbs sampling. As I’ve written before, sampling is based on randomness, which makes it somewhat difficult to debug.

On the other hand, one popular way to ensure the quality of code is through arrays of unit tests, which are designed to test your code at a very fine-grained level (e.g. one test for each function in the code base). However, because sampling is by nature random, the output of a sampling algorithm can be expected to change every time you run it, and thus it is not trivial to write unit tests. This article shows two simple ways that I’ve used to overcome this difficulty and write unit tests for sampling algorithms.

First, let’s assume that we have a sampling function called SampleMultinomial, which samples a single value from a multinomial distribution, defined by an array of doubles. In the program below, we sample from the distribution {0.5, 0.3, 0.2}, so we should expect the program to print “0″ 50% of the time, “1″ 30% of the time, and “2″ 20% of the time.

#include <vector>
#include <iostream>
#include <cstdlib>

using namespace std;

int SampleMultinomial(const vector<double> & distribution) {
    double value = (double)rand()/RAND_MAX;
    for(int i = 0; i < distribution.size(); i++)
        if( (value -= distribution[i]) <= 0 )
            return i;
    cerr << "Overflow in SampleMultinomial()" << endl;
    return -1;
}

int main() {
    srand( time(NULL) );
    vector<double> my_distribution(3);
    my_distribution[0] = 0.5;
    my_distribution[1] = 0.3;
    my_distribution[2] = 0.2;
    cout << SampleMultinomial(my_distribution) << endl;
    return 0;
}

Now, how do we test this function? We can do so by utilizing the fact that sampling enough times will help us recover the true probability distribution (the law of large numbers), or we can utilize the fact that the “random” numbers that the computer is generating are actually pseudo-random.

Utilizing the Law of Large Numbers

The original motivation for sampling is that if we take enough samples, we can approximate the true distribution. In our previous example, this means that if we take the count of the number of times that SampleMultinomial returns “0″ (c(x=”0″), and divide it by the total number of times, that we called SampleMultinomial (C), this will approach the true probability of “0″ (p(x=”0″)), as C approaches infinity:

Now, let’s try to write this in code. We do this by writing a loop that calls SampleMultinomial “C” times, and counts the number of times we get each result. Finally, for each of “x=0″ “x=1″ and “x=2″, we check that its probability is sufficiently close to the true expected probability.

bool TestLawOfLargeNumbers(const vector<double> & distribution) {
    // Call SampleMultinomial C times, and count the number of times we get
    // each result
    int C = 1000000;
    vector<int> counts(distribution.size(), 0);
    for(int i = 0; i < C; i++) {
        int x = SampleMultinomial(distribution);
        counts[x]++;
    }
    // Check to make sure that the value of the probabilities match the true
    // probabilities of the distribution within a confidence threshold
    double confidence = 0.005;
    bool passed = true;
    for(int i = 0; i < distribution.size(); i++) {
        double estimated_probability = (double)counts[i]/C;
        if(abs(distribution[i] - estimated_probability) > confidence) {
            cerr << "FAILED: Difference between at " << i << " ("
                 << abs(distribution[i] - estimated_probability)
                 << ") is more than confidence " << confidence << endl;
            passed = false;
        }
    }
    return passed;
}

It should be noted that this works for discrete distributions where we can explicitly count the number of times each instance is generated. If we are handling continuous distributions, it may be possible to handle them in this way by measuring the Kullback-Leibler divergence from the true distribution, or quantizing the distribution, but I have never tried these.

Utilizing Pseudo-Randomness

Using the law of large numbers relatively simple to implement, and can be used without any knowledge of the internals of the algorithm. On the other hand, when generating samples is expensive, it may be relatively slow to acquire enough samples to ensure that we will get close enough to the true distribution. Also, as mentioned above, continuous distributions are not easy to handle. An alternative method that is useful in these cases is to utilize pseudo-randomness to ensure that we will get the same result every time, then use the expected result to test our algorithm.

To do so, we first set the random seed of our pseudo-random number generator to a specific value, say 1234, and generate as many numbers as we need in sequence.

int main() {
    srand( 1234 );
    const int C = 10;
    for(int i = 0; i < C; i++)
        cout << (double)rand()/RAND_MAX << endl;
    return 0;
}

This gives us an output of:

0.223118
0.216796
0.447559
0.492617
0.569365
0.473787
0.474919
0.0336593
0.954041
0.958502

Given these random numbers, and a grasp of how the sampling algorithm works, we can estimate the results of the sampling algorithm based on these numbers.* For example given an array {0.5, 0.3, 0.2}, SampleMultinomial should convert all random numbers [0.0,0.5] into “0,” numbers (0.5,0.8] into “1,” and numbers (0.8,1.0] into “2.” Using this fact, we manually create an array of answers that corresponds to our random seeds, and create a test function that checks to make sure that these are actually the values that our sampling algorithm produces.

bool TestPseudoRandom(const vector<double> & distribution) {
    srand( 1234 );
    const int C = 10;
    int expected[C] = { 0, 0, 0, 0, 1, 0, 0, 0, 2, 2 };
    bool passed = true;
    for(int i = 0; i < C; i++) {
        int x = SampleMultinomial(distribution);
        if(x != expected[i]) {
            cerr << "FAILED: Actual value at " << i << " (" << x
                 << ") not equal to expected (" << expected[i] << ")" << endl;
            passed = false;
        }
    }
    return passed;
}

If you’d like to try this yourself, I’ve made the full code available here.

*One thing we need to be careful here is that this is also relying on the fact that the random number generator will generate the same numbers given a particular seed, which may not be true for some languages or operating systems.

I was wondering what papers had the most influence on the field of computational linguistics and natural language processing, so I tried making a list of the most cited papers from the annual meeting of the ACL (Association for Computational Linguistics) for the past twenty years. All citation counts are from Google scholar as of today, so take them with a grain of salt, but here goes:

• 1990: Steedman, Mark “Structure and intonation in spoken language understanding” (344 citations)
• 1991: Peter F. Brown; Jennifer C. Lai; Robert L. Mercer “Aligning sentences in parallel corpora” (477 citations)
• 1992: Fernando Pereira; Yves Schabes “Inside-outside re-estimation from partially bracketed corpora” (366 citations)
• 1993: Fernando Pereira; Naftali Tishby; Lillian Lee “Distributional clustering of English words” (914 citations)
• 1994: Marti A. Hearst “Multi-paragraph segmentation of expository text” (576 citations)
• 1995: David Yarowsky “Unsupervised word sense disambiguation rivaling supervised methods” (1285 citations)
• 1996: Stanley F. Chen; Joshua Goodman “An Empirical Study of Smoothing Techniques for Language Modeling” (974 citations)
• 1997: Michael Collins “Three generative, lexicalised models for statistical parsing” (896 citations)
• 1998: Dekang Lin “Automatic retrieval and clustering of similar words” (1026 citations)
• 1999: Lillian Lee “Measures of distributional similarity” (360 citations)
• 2000: Franz Josef Och; Hermann Ney “Improved statistical alignment models” (683 citations)
• 2001: Kenji Yamada; Kevin Knight “A syntax-based statistical translation model” (542 citations)
• 2002: Kishore Papineni; Salim Roukos; Todd Ward; Wei-Jing Zhu “BLEU: a method for automatic evaluation of machine translation” (2467 citations)
• 2003: Franz Josef Och “Minimum error rate training in statistical machine translation” (1049 citations)
• 2004: Bo Pang; Lillian Lee “A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts” (617 citations)
• 2005: David Chiang “A hierarchical phrase-based model for statistical machine translation” (563 citations)
• 2006: Patrick Pantel; Marco Pennacchiotti “Espresso: Leveraging Generic Patterns for Automatically Harvesting Semantic Relations” (229 citations)
• 2007: John Blitzer; Mark Dredze; Fernando Pereira “Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification” (244 citations)
• 2008: Libin Shen; Jinxi Xu; Ralph Weischedel “A new string-to-dependency machine translation algorithm with a target dependency language model” (109 citations)
• 2009: Mike Mintz; Steven Bills; Rion Snow; Daniel Jurafsky “Distant supervision for relation extraction without labeled data” (40 citations)

Recently I’ve been reading a bit about Psycholinguistics, the two books below for example:

Introduction to Psycholinguistics was quite good, with a lot of useful and eye-opening information. The computational modeling book is also rather good (I’m only halfway through), but maybe a bit thin for the money at only 70-some pages.

How do children learn language?

The thing that struck me the most when reading both books was that it seems that a certain pattern pervades children’s language learning, be it the learning of phonemes, word/concept mappings, or morphology. This is the fact that children first under-generalize, then over-generalize, then get it about right.

What does this mean? Let’s take the example of a child that wants to learn what the word “rose” means. In the under-generalization stage, the child may be able to appropriately identify red roses, but not identify white roses when they are told “look at the rose.” In the over-generalization stage, they will identify both of the roses, and also tulips as a “rose.” Finally, as they grow older their idea of roses will come into line with adults, and they will be able to properly identify both colors of roses, but realize that the tulip is something different.

This pattern is most pronounced in morphology. At first kids will be able to identify only a small amount of both regular and irregular verbs, probably remembering each word exactly as they hear it. After that, they will learn how to conjugate, but mistakenly conjugate irregular verbs using regular conjugations (like “goed”). And finally they will (mostly) converge on the actual usage of verbs in the language that they are learning.

For phoneme learning, I’m not sure if the over-generalization phase occurs, but apparently young babies are able to recognize the difference between phonemes, even if they are not distinct in their native language. For example, Japanese babies can recognize the difference between “l” and “r” easily, while Japanese adults cannot.

What can we do to mimic them?

So the question is, what does this mean when we are building computer programs to try to do unsupervised language acquisition, particularly in a statistical framework? Well, it couldn’t hurt to try to mimic this learning style. After all, it works for humans, right?

For learning phonemes, this could indicate that we want to start with an acoustic model with a large number of HMM states or Gaussian mixtures. This model would over-fit the data heavily, but as we get more evidence, some of the Gaussian clusters will start to run together, so we set a threshold based on something like KL divergence, and merge clusters together that go under the threshold. Or it’s possible that we could formulate something like this with non-parametric Bayesian statistics.

For learning morphology, it seems clear that we need some sort of device that first checks whether a word is irregular, then falls back to generating it from regular patterns if it is not. In the early learning phase, the regular patterns have not been learned yet, so unless we’ve seen the word already we’re out of luck. In the later learning phase, the back-off probability goes too high, so we generate from standard patterns too often. Finally, the back-off and generation of irregulars from memory becomes balanced correctly. This also seems like something that non-parametric Bayes would be good at, particularly with a hierarchical model. The irregular verbs could be generated from a Dirichlet process, with the regular patterns as its base measure.

For the concept mapping, this is a little bit more difficult, but it seems a bit like the phoneme learning problem. We could map, say images, into a continuous feature space and model this with a Gaussian mixture model, and it would be reduced to the same problem.

This, of course, is not my specialty, so I’d love to hear more comments, especially from people who have done work on something like this in the past.