Add-1 laplace smoothing for bigram implementation8

Question

I am doing an exercise where I am determining the most likely corpus from a number of corpora when given a test sentence. I am trying to test an and-1 (laplace) smoothing model for this exercise. I generally think I have the algorithm down, but my results are very skewed. I am aware that and-1 is not optimal (to say the least), but I just want to be certain my results are from the and-1 methodology itself and not my attempt.

Now, the And-1/Laplace smoothing technique seeks to avoid 0 probabilities by, essentially, taking from the rich and giving to the poor. Therefore, a bigram that is found to have a zero probability becomes:

 1/V, V=the number of types 

This means that the probability of every other bigram becomes:

 P(B|A) = Count(W[i-1][W[i])/(Count(W[i-1])+V) 

You would then take a sentence to test and break each into bigrams and test them against the probabilities (doing the above for 0 probabilities), then multiply them all together to get the final probability of the sentence occurring.

I am implementing this in Python. My code looks like this, all function calls are verified to work:

 #return is a counter of tuples containing ngrams: {('A','B'):C} 
 #this means ('A','B') means (B|A) in probabilistic terms 
 bigrams[0]=getBigrams(corpus[0]) 
 ... 
 bigrams[n]=getBigrams(corpus[n]) 

 #return is a dictionary of the form P['A']=C 
 unigrams[0]=getUnigrams(corpus[0]) 
 ... 
 unigrams[N]=getUnigrams(corpus[n]) 

 #generate bigram probabilities, return is P('A','B')=p, add one is done 
 prob[0]=getAddOneProb(unigrams[0],bigrams[0]) 
 ... 
 prob(n)=getAddOneProb(unigrams[n],bigrams[n]) 

 for sentence in test: 
      bi=getBigrams(sentence) 
      uni=getUnigrams(sentence) 
      P[0]=...=P[n]=1 #set to 1 
      for b in bi: 
           tup=b 
           try: 
                P[0]*=prob[tup] 
           except KeyError: 
                P[0]=(1/len(unigrams[0]) 
           #do this for all corpora 

At the then I would compare all corpora, P[0] through P[n] and find the one with the highest probability

My results aren't that great but I am trying to understand if this is a function of poor coding, incorrect implementation, or inherent and-1 problems.

Answer 1

The overall implementation looks good. I have few suggestions here. First of all, the equation of Bigram (with add-1) is not correct in the question. In Laplace smoothing (add-1), we have to add 1 in the numerator to avoid zero-probability issue. So, we need to also add V (total number of lines in vocabulary) in the denominator.

After doing this modification, the equation will become,

P(B|A) = (Count(W[i-1]W[i]) + 1) / (Count(W[i-1]) + V) 

Irrespective of whether the count of combination of two-words is 0 or not, we will need to add 1. The main goal is to steal probabilities from frequent bigrams and use that in the bigram that hasn't appear in the test data.

Based on the given python code, I am assuming that bigrams[N] and unigrams[N] will give the frequency (counts) of combination of words and a single word respectively.

Based on the add-1 smoothing equation, the probability function can be like this:

import math

def getAddOneProb(unigrams_count, bigrams_count):
    return(math.log(bigrams_count + 1) - math.log(unigram_count + V))

If you don't want to count the log probability, then you can also remove math.log and can use / instead of - symbol.

The another suggestion is to use add-K smoothing for bigrams instead of add-1. In most of the cases, add-K works better than add-1.