<jupyter_start><jupyter_text>IPython Notebook - N-gram TutorialI've always wondered how chat bots like [Alice](http://alice.pandorabots.com/) work. Now, they are obviously much more complex than this tutorial will delve into, but we can touch on some of the core principles. One of them is this idea of understanding the relationships between words in sentences. How can we get a machine to understand these relationships?Turns out there's the right way, and then there's the easy way. The right way involves delving deep into [semantic networks](https://en.wikipedia.org/wiki/Semantic_network) and ontologies, something I'd touched upon in my climate modelling days, but never mind that; We're doing **The Easy Way**. The Easy WayConversely, the easy way to learn the relationships is by throwing lots of data *en masse* at a machine, and letting it build up a model of the relationships (*this sounds suspiciously like Machine Learning*). An even simpler form of that is to track the number of words that are in sequence with one another, and keeping track of the frequency at which this occurs. We're actually starting to describe something that uses [N-grams](https://en.wikipedia.org/wiki/N-gram). An N-gram is a contiguous (*order matters*) sequence of items, which in this case is the words in text.What we want to do is build up a dictionary of N-grams, which are pairs, triplets or more (*the N*) of words that pop up in the training data, with the value being the number of times they showed up. After we have this dictionary, as a naive example we could actually predict sentences by just randomly choosing words within this dictionary and doing a weighted random sample of the connected words that are part of n-grams within the keys.Lets see how far we can get with N-grams without outside resources.<jupyter_code>%load_ext autoreload
%autoreload 2
# load data
path = "./../data/harry_potter_3.txt"
txt = open(path).read().lower()
print('corpus length:', len(txt))<jupyter_output>corpus length: 611606<jupyter_text>Great, now lets split into words into a big list, splitting on anything non-alphanumeric [A-Za-z0-9] (as well as punctuation) and forcing everything lowercase<jupyter_code>import re
words = re.split('[^A-Za-z]+', txt.lower())
words = list(filter(None, words)) # Remove empty strings

# Print length of list
print (len(words))<jupyter_output>108805<jupyter_text>SetsFrom this we can now generate N-grams, lets start with a 1-gram, basically the set of all the words    *Note* : One could use a dictionary instead of a set and keeping count of the occurances gives word frequency<jupyter_code>#import sets

# Create set of all unique words, this throws away any information about frequency however
gram1 = set(words)

print (len(gram1))

# Instead of printing all the elements in the set, create an iterator and print 20 elements only
gram1_iter = iter(gram1)
print ([gram1_iter.__next__() for i in range(20)])<jupyter_output>7393
['miss', 'to', 'tough', 'protector', 'rug', 'drills', 'spell', 'hugging', 'mongrels', 'mcgonagall', 'bowling', 'o', 'lace', 'cage', 'curly', 'whether', 'brute', 'hating', 'mgoing', 'unlucky']<jupyter_text>Lets try and get the 2-gram now, which is pairs of words. Let's have a quick look to see the last 10 and how they look.<jupyter_code># See the last 10 pairs
for i in range(len(words)-10, len(words)-1):
    print (words[i], words[i+1])<jupyter_output>like a
a much
much better
better summer
summer than
than the
the last
last the
the end<jupyter_text>Okay, seems good, lets get all word pairs, and then generate a set of unique pairs from it<jupyter_code>word_pairs = [(words[i], words[i+1]) for i in range(len(words)-1)]
print (len(word_pairs))

gram2 = set(word_pairs)
print (len(gram2))

# Print 20 elements from gram2
gram2_iter = iter(gram2)
print ([gram2_iter.__next__() for i in range(20)])<jupyter_output>108804
53720
[('slow', 'rattling'), ('nearest', 'dementor'), ('it', 's'), ('around', 'hear'), ('voice', 'right'), ('mornin', 'mind'), ('crookshanks', 'but'), ('much', 'that'), ('ginny', 's'), ('between', 'fudge'), ('hooch', 'who'), ('hogsmeade', 'and'), ('the', 'others'), ('sank', 'four'), ('frustration', 'as'), ('find', 'uses'), ('s', 'happened'), ('give', 'them'), ('of', 'snow'), ('hand', 'very')]<jupyter_text>FrequencyOkay, that was fun, but this isn't enough, we need frequency if we want to have any sense of probabilities, which is what N-grams are about. Instead of using sets, lets create a dictionary with counts<jupyter_code>gram1 = dict()

# Populate 1-gram dictionary
for word in words:
    if word in gram1:
        gram1[word] += 1
    else:
        gram1[word] = 1 # Start a new entry with 1 count since saw it for the first time.

# Turn into a list of (word, count) sorted by count from most to least
gram1 = sorted(gram1.items(), key=lambda (word, count): -count)

# Print top 20 most frequent words
print (gram1[:20])<jupyter_output><empty_output><jupyter_text>For Pride and Prejudice, the words 'the', 'to', 'of', and 'and' were the top four most common words. Sounds about right, not too interesting yet, lets see what happens with 2-grams.<jupyter_code>gram2 = dict()

# Populate 2-gram dictionary
for i in range(len(words)-1):
    key = (words[i], words[i+1])
    if key in gram2:
        gram2[key] += 1
    else:
        gram2[key] = 1

# Turn into a list of (word, count) sorted by count from most to least
gram2 = sorted(gram2.items(), key=lambda (_,count): -count)

# Print top 20 most frequent words
print (gram2[:20])<jupyter_output><empty_output><jupyter_text>It looks like `"of the"` and `"to be"` are the top two most common 2-grams, sounds good.  Next word predictionWhat can we do with this? Well lets see what happens if we take a random word from all the words, and build a sentence by just choosing the most common pair that has that word as it's start.<jupyter_code>start_word = words[int(len(words)/4)]
print (start_word)<jupyter_output>boarhound<jupyter_text>I just went ahead and chose the word that appears $1/4$ of the way into words, random enough.Now in a loop, iterate through the frequency list (most frequent first) and see if it matches the first word in a pair, if so, the next word is the second element in the word pair, and continue with that word. Stop after N words or the list does not contain that word.    *Note* : gram2 is a list that contains (key,value) where key is a word pair (first, second),             so you need element[0][0] for first word and element [0][1] for second word<jupyter_code>def get2GramSentence(word, n = 50):
    for i in range(n):
        print (word,)
        # Find Next word
        word = next((element[0][1] for element in gram2 if element[0][0] == word), None)
        if not word:
            break

word = start_word
print ("Start word: %s" % word)

print ("2-gram sentence: \"",
get2GramSentence(word, 20))
print ("\"")<jupyter_output>Start word: boarhound
boarhound
2-gram sentence: " None
"<jupyter_text>It gets stuck in a loop pretty much straight away. Not very interesting, try out other words and see what happens.<jupyter_code>for word in ['and', 'he', 'she', 'when', 'john', 'never', 'i', 'how']:
    print ("Start word: %s" % word)

    print ("2-gram sentence: \"",
    get2GramSentence(word, 20))
    print ("\"")<jupyter_output>Start word: and
and
2-gram sentence: " None
"
Start word: he
he
2-gram sentence: " None
"
Start word: she
she
2-gram sentence: " None
"
Start word: when
when
2-gram sentence: " None
"
Start word: john
john
2-gram sentence: " None
"
Start word: never
never
2-gram sentence: " None
"
Start word: i
i
s
h
e
v
e
v
e
v
e
v
e
v
e
v
e
v
e
v
e
2-gram sentence: " None
"
Start word: how
how
2-gram sentence: " None
"<jupyter_text>Weighted random choice based on frequencySame thing. Okay, lets randomly choose from the subset of all 2grams that matches the first word, using a weighted-probability based on counts.<jupyter_code>import random
def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      print (c,w)
      if upto + w > r:
         return c
      upto += w
    
def get2GramSentenceRandom(word, n = 50):
    for i in range(n):
        print (word,)
        # Get all possible elements ((first word, second word), frequency)
        choices = [element for element in gram2 if element[0][0] == word]
        if not choices:
            break
        
        # Choose a pair with weighted probability from the choice list
        word = weighted_choice(choices)[1]
for word in ['and', 'he', 'she', 'when', 'john', 'never', 'i', 'how']:
    print ("Start word: %s" % word)

    print ("2-gram sentence: \"",
    get2GramSentenceRandom(word, 20))
    print ("\"")<jupyter_output>Start word: and
and
2-gram sentence: " None
"
Start word: he
he
2-gram sentence: " None
"
Start word: she
she
2-gram sentence: " None
"
Start word: when
when
2-gram sentence: " None
"
Start word: john
john
2-gram sentence: " None
"
Start word: never
never
2-gram sentence: " None
"
Start word: i
i<jupyter_text>**Now that's way more interesting!** Those are starting to look like sentences!    *Note* It's pretty interesting to see that for the sentence " when he believed him from the amiable but mrs hurst s being ill of being the discussion of course of ", we have hurst s, which we can tell came from Hurst's, an artifact of our stripping away all punctuation but keeping the s.Let's try a longer sentence<jupyter_code>word = 'it'
print ("Start word: %s" % word)
print ("2-gram sentence: \"",
get2GramSentenceRandom(word, 50))
print ("\"")<jupyter_output>Start word: it
it
2-gram sentence: " None
"<jupyter_text>Pretty cool, lets see what happens when we go to N-grams above 2. Tri-grams and moreOkay, let's create a Ngram generator that can let us make ngrams of arbitrary sizes<jupyter_code>def generateNgram(n=1):
    gram = dict()
    
    # Some helpers to keep us crashing the PC for now
    assert n > 0 and n < 100
    
    # Populate N-gram dictionary
    for i in range(len(words)-(n-1)):
        key = tuple(words[i:i+n])
        if key in gram:
            gram[key] += 1
        else:
            gram[key] = 1

    # Turn into a list of (word, count) sorted by count from most to least
    gram = sorted(gram.items(), key=lambda (_, count): -count)
    return gram

trigram = generateNgram(3)
# Print top 20 most frequent ngrams
print (trigram[:20])<jupyter_output><empty_output><jupyter_text>Cool! Okay, let's see a selection of sentences for N-grams with N = 2 to 10 and a few starting words!<jupyter_code>def getNGramSentenceRandom(gram, word, n = 50):
    for i in range(n):
        print (word,)
        # Get all possible elements ((first word, second word), frequency)
        choices = [element for element in gram if element[0][0] == word]
        if not choices:
            break
        
        # Choose a pair with weighted probability from the choice list
        word = weighted_choice(choices)[1]
for n in range(2,10):
    # Generate ngram list
    print ()
    print ("Generating %d-gram list..." % n,
    ngram = generateNgram(n))
    print ("Done")
    
    # Try out a bunch of sentences
    for word in ['and', 'he', 'she', 'when', 'john', 'never', 'i', 'how']:
        print ("  %d-gram: \"" % n,
        getNGramSentenceRandom(ngram, word, 15))
        print ("\"")<jupyter_output><jupyter_text>You can clearly see the sentences getting better and better with larger n-grams, this correlates to the ngram having more foresight into the sentence structure.<jupyter_code># Generate 10gram list
print ()
print ("Generating %d-gram list..." % n,
gram10 = generateNgram(10))
print ("Done")<jupyter_output><jupyter_text>Let's play with the 10gram and see what sort of sentence comes out.<jupyter_code># Try out a bunch of sentences
for word in ['and', 'he', 'she', 'when', 'john', 'never', 'i', 'how']:
    print ("  %d-gram: \"" % n,
    getNGramSentenceRandom(ngram, word, 100))
    print ("\"")<jupyter_output><empty_output><jupyter_text>Looks almost like normal sentences if you squint a little! Well, that was fun. Next up let's see some ways to improve upon this.Instead of just taking the next word every time, we could take the next k words etc.To be continue...<jupyter_code># Generate 10gram list
n = 50
print
print ("Generating %d-gram list..." % n,
gram30 = generateNgram(n))
print ("Done")
# Try out a bunch of sentences
for word in ['and', 'he', 'she', 'when', 'john', 'never', 'i', 'how']:
    print ("  %d-gram: \"" % n,
    getNGramSentenceRandom(ngram, word, 20))
    print ("\"")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11479430379746836, 'fraction_numerical': 0.01574367088607595, 'mean_word_length': 4.02824184566428, 'pattern_counts': {'":': 0, '<': 58, '<?xml version=': 0, '>': 59, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '268978', 'license': 'MIT', 'n_tokens_mistral': 4111, 'n_tokens_neox': 3928, 'n_words': 1682, 'path': 'module1/N-gram.ipynb', 'repo_name': 'kochhar/Representation-Learning-for-NLP', 'size': '12640'}