title: Good-Turing smoothing implementation problems
body: <p>I want to implement the Good-Turing smoothing method which will improve my language model.</p>
  
  <p>Let's start with the theory (for simplicity, consider the unigram model).</p>
  
  <p>There is a corpus (e.g. a literary work or any huge text). Through it we are building a language model. After we built it, we can find the probability of occurrence of the word. I have created this model using MLE (Maximum Likelihood Estimation) with a high value of perplexity (the value of the quality of the constructed model, a high value is bad).</p>
  
  <p>I found a way to improve it with using Good-Turing smoothing:</p>
  
  <p><a href="https://i.stack.imgur.com/8X20F.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8X20F.gif" alt="Good-Turing smoothing"></a></p>
  
  <p><a href="https://i.stack.imgur.com/YNI0t.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YNI0t.gif" alt="Good-Turing smoothing 2"></a></p>
  
  <p>Here: </p>
  
  <pre><code>P - the probability of use of the word
  c - the number of use of the word
  N_c - the count words with a frequency - c
  N - the count words in the corpus
  </code></pre>
  
  <p>My code on Python 3:</p>
  
  <pre><code>def good_turing(tokens):
      N = len(tokens) + 1    
      C = Counter(tokens)    
      N_c = Counter(list(C.values()))
      assert(N == sum([k * v for k, v in N_c.items()]))
      default_value = N_c[1] / N
      model = defaultdict(lambda: default_value)
      types = C.keys()
      B = len(types)  
      for _type in types:
          c = C[_type]
          model[_type] = (c + 1) * N_c[c + 1] / (N_c[c] * N) # Exception - "math domain error"
      return model
  </code></pre>
  
  <p>There are problems here:</p>
  
  <ul>
  <li><p><strong>word with a frequency c + 1 can not be in the corpus</strong>, so we try to
  take log(0) and get Math Domain Error</p></li>
  <li><p>how to calculate <strong>the probability of the most used word</strong> after smoothing?</p></li>
  </ul>
  
  <p>After reading a few articles my study of this subject came to the construction of the following formulas:</p>
  
  <p><a href="https://i.stack.imgur.com/LuTFg.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LuTFg.gif" alt="estimate"></a></p>
  
  <p>So the main question is: <strong>how to get this <em>E</em> function</strong>?
  I found this:</p>
  
  <p><a href="https://i.stack.imgur.com/Fzyjf.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Fzyjf.gif" alt="log"></a></p>
  
  <p>but I don't know how to search <em>a</em> and <em>b</em> coefficients in scipy or etc.</p>