<!-- Abstract: CS 461 Introduction to Deep Learning Lecture 11 --> <!-- To left align everything <style type="text/css"> .reveal p { text-align: left; } .reveal ul { display: block; } .reveal ol { display: block; } </style> --> # CS 461 - Lecture 11 ## Machine Learning Principles ### Sequence Modelling Bernhard Firner 2025-10-11 --- ## Reading * Recommended reading * Machine Learning: A Probabilistic Perspective by Murphy * 17 Markov and hidden Markov models --- ## Review * Last time we covered AdaBoost * Method to train an ensemble of models * For each model, track errors on training data * Giving each model a confidence score, $\alpha$, from the weighted error rate * Use that error rate to re-weight the training points * Show this with decision trunks last time --- ## Boosting * The weighting of sample points *boosts* the models in the ensemble * This forces them to be different, improving the ensemble * Better concept than bagging * Weight adjusting is finer than duplication * Guarantees that the next model in the ensemble is focusing on different datapoints than the last --- ## Weight Adjustment * Initialize weights to 1/N for N samples * After training each classified * Multiply misclassified weights by $1/(2\epsilon)$ * Multiply correctly classified weights by $1/(1 - 2\epsilon)$ * As long as $\epsilon < 0.5$, this increased the weight of misclassified samples * If the error rate is over 0.5 something is wrong --- ## Confidence Factor * To improve the ensemble, we also want to assign a confidence, $\alpha$, to each model * AdaBoost, the most popular boosting method * Applies an exponential penalty for misclassification * $ln\sqrt\frac{1-\epsilon_t}{\epsilon_t}$ for the model at step t * We use this confidence to weight each model in the ensemble --- ## Decision Stumps * Common with adaboost * Each stump uses a `pivot column`, a `boundary` value, and a `polarity` * It will also gain a confidence, $\alpha$, once its error rate it measured --- ## Stump ```python class DecisionStump: """Also called univariate decision tree. Has depth 1, making a single decision. Returns either -1 or 1 upon classification. """ def __init__(self, feature_index, boundary, polarity): # The column of the chosen feature self.feature_index = feature_index self.boundary = boundary # Says if the output is -1 or 1 beyond the boundary self.polarity = polarity # The certainty weighting from AdaBoost self.alpha = None # The error of the stump self.error = None def predict(self, X): # The default polarity predictions = self.polarity * np.ones(X.shape[1]) # Reverse polarity for anything below the decision boundary predictions[X[self.feature_index] < self.boundary] *= -1 return predictions ``` --- ## Training with Weight ```python def train_stump(X, y, weights): """ Arguments: X: Column first samples y: Class labels weights: Weights to rows in X """ columns, samples = X.shape min_error = float('inf') best_stump = None for fidx, feature in enumerate(X): # Just like regular trees, check each unique value as the decision boundary boundaries = np.unique(feature) for boundary in boundaries: for polarity in [1, -1]: stump = DecisionStump(fidx, boundary, polarity) predictions = stump.predict(X) # Find the errors and then weight them errors = (predictions != y) weighted_error = np.sum(weights[errors]) if weighted_error < min_error: min_error = weighted_error best_stump = stump best_stump.error = weighted_error return best_stump ``` --- ## Stump Example * Initial weights for points are all $1/6$ <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_1.png" /> --- ## Stump Example * First stump has alpha 0.35 * It has errors, so weights are updated: * 0.25 0.125 0.25 0.125 0.125 0.125 <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_2.png" /> --- ## Stump Example * Second stump has alpha 0.549 * High because it fixed high weight errors from before * New weights: 0.167 0.083 0.167 0.083 0.25 0.25 <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_3.png" /> --- ## Stump Example * Third stump has alpha 0.346 * It's going back and repeating the first line * New weights: 0.25 0.0625 0.25 0.0625 0.1875 0.1875 <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_4.png" /> --- ## Stump Example * Fourth stump has alpha 0.394 <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_5.png" /> --- ## Stump Example * Fifth stump has alpha 0.381 <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_6.png" /> --- ## Stump Example * Sixth stump has alpha 0.472 <img style="width: 95%" class="r-stretch" src="./figures/adaboost_points_example_7.png" /> --- ## Adaboost and Regression * We used adaboost and decision stumps because that is most common * But we could also use adaboost with logistic regression * Just multiply the errors by the weights before the parameter update step * Voting is the same as in stumps, summing all predictions and converting to a class --- ## Weighted Regression ```python import math import numpy as np def sigmoid(eta): """ The sigmoid function. """ return 1 / (1 + np.exp(-eta)) def logistic_regression(X, y, weights, learning_rate=0.5, epochs=50): """ Performs logistic regression to draw a decision boundary through (hopefully) linearly separable data. Args: X (float): Input data y (int): Target y class learning_rate (float): Update rate epochs (int): Number of times to iterate through the data """ X = X.T n_samples, n_features = X.shape # Weights and bias beta = np.random.randn(n_features) * 0.01 bias = 0 # Gradient descent for i in range(epochs): # Get the predicted probabilities y_hat = sigmoid(X @ beta + bias) weighted_error = weights * (y_hat - y) # Calculate gradients w.r.t. w and b # Average over the size of the dataset dw = (1 / len(y)) * weighted_error @ X db = (1 / len(y)) * np.sum(weighted_error) # Update w beta -= learning_rate * dw bias -= learning_rate * db #print(f"epoch {i} error is {np.mean(weighted_error):.4f}") return beta, bias def logistic_predict(beta, bias, X): return sigmoid(X.T @ beta + bias).round().astype(int) class regressor(): def __init__(self, beta, bias): self.beta = beta self.bias = bias self.alpha = None self.error = None def predict(self, X): return logistic_predict(self.beta, self.bias, X) def fitRegression(X, y, num_lines): columns, samples = X.shape # Equally weight all samples to begin weights = np.full(samples, 1/samples) lines = [] for t in range(num_lines): beta, bias = logistic_regression(X, y, weights) line = regressor(beta, bias) y_hat = line.predict(X) error_mask = (y != y_hat) # Convert to 1, -1 predictions for adaboost math y_pred = np.where(y_hat == 1, 1, -1) weighted_error = np.sum(weights[error_mask]) line.error = weighted_error # Same as the stump code, for the most part # Calculate confidence factor of the line alpha = 0.5 * np.log((1.0 - line.error) / (line.error + 1e-10)) line.alpha = alpha lines.append(line) # We predict 0 and 1 instead of -1 and 1, so there is no cute multiply trick. # Populate an array with alpha and -alpha adjustments = np.where(error_mask, alpha, -alpha) weights *= np.exp(adjustments) # Ensure weights sum to 1 weights /= np.sum(weights) return lines def predictLines(lines, X): num_samples = X.shape[1] y_hat_sums = np.zeros(num_samples) for line in lines: y_hats = line.predict(X) y_hat_sums += line.alpha * (y_hats - 0.5) predictions = (np.sign(y_hat_sums) + 1)/2 return predictions ``` --- ## Regression Ensembles * Have to imagine overlapping hyperplanes  -v- ## Regression Ensembles  -v- ## Regression Ensembles ``` line_1(x,y)=sigmoid(-0.17387894672624615 + x*-0.08628491 + y*0.23243224) alpha1=0.34657359012997274 ```  -v- ## Regression Ensembles  -v- ## Regression Ensembles  -v- ## Regression Ensembles  -v- ## Regression Ensembles  -v- ## Regression Ensembles  -v- ## Regression Ensembles  -v- ## Regression Ensembles  -v- ## Line Parameters ``` line_1(x,y)=sigmoid(-0.17387894672624615 + x*-0.08628491 + y*0.23243224) line_2(x,y)=sigmoid(-0.19374862580876911 + x*-0.15113262 + y*0.07758373) line_3(x,y)=sigmoid(-0.10837138367819123 + x*-0.11416898 + y*0.19966443) line_4(x,y)=sigmoid(-0.13365782168540152 + x*-0.15260182 + y*0.10953851) line_5(x,y)=sigmoid(-0.08328346858127633 + x*-0.12128242 + y*0.18372819) line_6(x,y)=sigmoid(-0.30712535287714304 + x*0.11825315 + y*-0.18305295) line_7(x,y)=sigmoid(-0.2099824499433603 + x*0.21760769 + y*-0.00529652) line_8(x,y)=sigmoid(-0.1658324855732975 + x*-0.27519619 + y*0.02563761) alpha1=0.34657359012997274 alpha2=0.255412811629662 alpha3=0.20273255386797107 alpha4=0.1682361181558446 alpha5=0.6496414918165446 alpha6=0.38107002573182935 alpha7=0.935901087703694 alpha8=0.451433855374858 ``` --- ## Adaboost Regression Results * Got 95.8% success on the Spambase test set with 10000 regressors * When using PCA, terrible otherwise * Very noisy * Learning rate changes results drastically * Could also add and tune l2 loss * Very fast * 10k regressors in the same time as 1000 stumps --- ## Beyond Aggregate Statistics * The Spambase dataset used document statistics as the feature columns * These replaced the original words of the emails * Simplified the problem * Don't need a huge corpus to see examples of all words * Allowed us to use arbitrary continuous techniques * Didn't need a method to work with inputs of different sizes --- ## Merits and Demerits * Better than a naive Bayes approach * Not vulnerable to Bayesian poisoning, where spam avoids known keywords, evading filters * Treats messages as bags of words * No correlation between the words * Which can't be right * Features are human-chosen * Good at first, but easily evaded once known --- ## Other Weaknesses * This approach also assumes similar document lengths * SMS also includes large volumes of spam, but all messages have similar, small lengths * Those document statistics will be much less meaningful here * Word correlation, through naive Bayes, feels more meaningful * It's just vulnerable to attack --- ## Email Example * A lot of spam has been sent to sell different pills, especially Viagra * So we can just filter on that word and get rid of the spam, right? * Let's look at the first sample from the TREC2007 dataset: <pre> Try V ia gr a ..... your anxiety will be a thing of the past and you will be back to your old self. </pre> --- ## Tricked! * Simple rules are too easily tricked --- ## Improvements * What do we want? * To find a way to use probabilities again * That means making sense of the words * Consider semantic meaning rather than just bags of unrelated letters and words --- ## Things That Won't Work * We don't want to build a decision tree on entire sentences * There just isn't enough data to do that * And trees are too sensitive * They could be fooled similarly to naive Bayes approaches * We also don't want a solution that requires huge amount of input text * Some messages are short; decisions should be possible with small samples --- ## Things That Could Work * Two things we've done could work * Assume something about structure * Simplify the problem by assuming that spam and real messages follow some rules * Work in a latent space rather than the observed space * Then find the parameters of the spam and not spam sources --- ## 2 Problems 1. What structure do we assume? 2. How do we learn latent variables that represent spammers vs not spammers? --- ## Structure * Words are obviously related to the words that came before * So we'll build *temporal* models * This doesn't necessarily mean time-based, just that there is some ordered relationship in the data --- ## Latent Variables * Classification can always be thought of as a variant of a clustering problem * Mixtures models (of gaussians or gaussian and categorical experts) learned about the latent space * So can we learn about the latent space that generates text? --- ## The Idea * Both your friend and a spammer may write a message saying, "hey, look at this thing!" * The spammer will have a completely different set of priors that affect their message * They know nothing about the receiver * They are not real users of the product they are selling * Their messages may be circuitous to evade current filters * It follows that their messages must be somehow different --- ## Not One to One * Unfortunately, our mixture models assumed a one to one mapping of distributions and observed variables * With text, won't multiple characters or words come from the same latent space? * PCA helped in the continuous space, but we don't know a way to create an embedding from words * We'll learn more about this later, but we're helpless now --- ## Topics * Let's tackle these problems one at a time * First, how can we represent ordered relationships in the data? * Second, how can we use a different number of latent variables than visible space observations? --- ## Dataset * Let's start doing some real examples * Before we go to the messy email set, let's look at something simpler * Grabbed 12 books from projects Gutenberg * Let's see if we can predict something about the authors from their writing --- ## Whales * *whale* or *whales* appears 1727 times in the 12-book corpus * 1705 times in Moby Dick * 21 times in the other books * 4 in Frankenstein, 2 in Gulliver's Travels, 1 in Leviathon, 14 times in On the Origin of Species * 0 times in Anna Karenina, War and Peace, Psyche, Calculus Made Easy, Pride and Prejudice, or Romeo and Juliet --- ## Naive Bayes * So if we see the word "whale", we can be 98.7% sure we're reading Moby Dick * That's the power of naive Bayes; some tokens will be very highly correlated, or anti-correlated, with a class --- ## Attack Avenue * If we are a Melville enthusiast, we may allow all emails with the word "whale" through our filter * In mere moments that will be discovered, and all of our spam will begin with the word "whale" * Or if we hate Melville, we could ban "whale" * But then enthusiasts would misspell it: "wale," "whail," etc * Can we discover more robust indicators? --- ## Temporal Dependencies * A solution that involves finding temporal relationships * Temporal as in sequences; "A and then B" * This preserves the structure of the original data * Words in a document * Base pairs in DNA or RNA * Notes in music * etc --- ## Temporal Models <style> .container { display: flex; } .col {flex: 1;} </style> <div class="container"> <div class="col"> <img style="width: 40%" class="r-stretch" src="./figures/mm_abc.png" /> </div> </div> * We can reach state C from state B * If we only reach B after A, then P(A) should be considered in P(C) * The `ordered markov property` asserts that we only need to consider the previous step when predicting the next * With writing, states are words or characters --- ## Markov Models * Consider a sequence of observed tokens, $X_1,...,X_T$ * $T$ is the last step in a chain * The probability of observing $X_T$ considers the entire pathway * $p(X_T) = p(X_1)\prod_{t=2}^{T}p(X_t|X_{t-1})$ * This is called a Markov Chain --- ## Modelling * We don't want to create models so specific that they need an entire sequence * e.g. $X_{t=1}$ could be the first word of a book or email * Feels too specific to start there and predict the thousandth word --- ## Time-Invariant * Instead, we want to assume that $P(X_t|X_{t-1})$ is independent of how we got to $X_{t-1}$ * e.g. Melville is very likely to write "whale" after the word "the" * More likely than most other writers, at least * We call this time-invariant, since we'll pretend it doesn't matter how we reached $X_{t-1}$ --- ## The Whale <pre> ./MobyDick_HermanMelville.txt:21746:Whale’s way now began to abate, as it seemed, from the boat so rapidly ./MobyDick_HermanMelville.txt:21747:nearing him once more; though indeed the whale’s last start had not ./MobyDick_HermanMelville.txt:21760:muttered—“whether these sharks swim to feast on the whale or on ./MobyDick_HermanMelville.txt:21766:the White Whale’s flank, he seemed strangely oblivious of its ./MobyDick_HermanMelville.txt:21767:advance—as the whale sometimes will—and Ahab was fairly within the ./MobyDick_HermanMelville.txt:21768:smoky mountain mist, which, thrown off from the whale’s spout, curled ./MobyDick_HermanMelville.txt:21772:hated whale. As both steel and curse sank to the socket, as if sucked ./MobyDick_HermanMelville.txt:21785:instantaneous swiftness, the White Whale darted through the weltering ./MobyDick_HermanMelville.txt:21794:Hearing the tremendous rush of the sea-crashing boat, the whale wheeled ./MobyDick_HermanMelville.txt:21804:“The whale! The ship!” cried the cringing oarsmen. ./MobyDick_HermanMelville.txt:21811:sledge-hammering seas, the before whale-smitten bow-ends of two planks ./MobyDick_HermanMelville.txt:21823:“The whale, the whale! Up helm, up helm! Oh, all ye sweet powers of </pre> --- ## n-grams <img style="width: 95%" class="r-stretch" src="./figures/mm_2gram.png" /> * Looking only at the previous token discards too much information, probably * In non-Melville-whale data * Instead, we'll choose some amount of the past, n * Called an n-gram * A 0-gram (or unigram) is just naive Bayes, with no past dependency * Let's motivate using n-grams --- ## Counting Letter N-grams ```python #! /usr/bin/python3 import argparse import itertools import numpy as np import string import sys if __name__ == "__main__": parser = argparse.ArgumentParser() parser.add_argument( "path", type=str, help="Path to a text file.") parser.add_argument( "order", type=int, help="Number of past characters to look at. 0 for unigrams.") args = parser.parse_args() try: with open(args.path, 'r', encoding='utf-8') as corpus: text = corpus.read() except FileNotFoundError: print(f"Error: The file '{args.path}' was not found.") sys.exit(1) # Change everything to lowercase and remove all non alphabetic characters except for spaces. text = text.lower().replace('\n', ' ').replace('\t', ' ') text = ''.join(c for c in text if (c.isalpha() or c == ' ')) # Initialize the ngrams # The indices of the frequency list will be all possible ngrams ngram_tokens = list(string.ascii_lowercase) + [' '] # Draw permutations equal to whatever was requested if args.order > 0: ngram_tokens = [''.join(token) for token in itertools.product(ngram_tokens, repeat = args.order+1)] # Observations # We could initialize this to 0, but, depending upon the ngram length, some occurences may not occur at all ngram_counts = dict() # Now loop through the text for i in range(args.order, len(text)): ngram = text[i-args.order:i+1] if ngram not in ngram_counts: ngram_counts[ngram] = 0 ngram_counts[ngram] = ngram_counts[ngram] + 1 total_ngrams = len(text) - args.order print(f"Collected {total_ngrams} total ngrams") # Now print out the normalized frequences for each ngram column_names = ["t"+str(x-args.order) for x in range(args.order)] + ["t"] # Header row print(f"{','.join(column_names)}, ngram") for token in ngram_tokens: if token in ngram_counts: print(','.join(token) + f",{ngram_counts[token]/total_ngrams}") ``` --- ## Darwin Vs Tolstoy    --- ## Darwin Vs Tolstoy  --- ## Darwin Vs Tolstoy  --- ## Darwin Vs Tolstoy  --- ## Darwin Vs Tolstoy * No discernible difference in letter frequency * But bigrams have differences * ' h' far more common in Tolstoy * frequency of 0.0187 and 0.016 in Anna Karenina and War and Peace * 0.0059 in Origin of Species * So seeing a word beginning with 'h' gives us a 75% probability of being in a Tolstoy novel * Not bad! --- ## Words Vs Letters * Letters are easier to look at (only 26 of them, plus space) * But words will be more meaningful --- ## Building Word N-grams ```python #! /usr/bin/python3 import argparse import itertools import numpy as np import string import sys if __name__ == "__main__": parser = argparse.ArgumentParser() parser.add_argument( "path", type=str, help="Path to a text file.") parser.add_argument( "order", type=int, help="Number of past words to look at. 0 for unigrams.") args = parser.parse_args() try: with open(args.path, 'r', encoding='utf-8') as corpus: text = corpus.read() except FileNotFoundError: print(f"Error: The file '{args.path}' was not found.") sys.exit(1) # Change everything to lowercase. # Count the end of sentences as their own tokens. text = text.lower().replace('\n', ' ').replace('.', ' .').replace('?', ' ?').replace('!', ' !') # Replace unknown characters with a space text = ''.join([c if (c.isalpha() or c in ".?! ") else ' ' for c in text]) words = text.split() # Initialize the ngrams # The indices of the frequency list will be all possible ngrams original_tokens = np.unique(words).tolist() # Draw permutations equal to whatever was requested if args.order > 0: ngram_tokens = list(itertools.product(original_tokens, repeat = args.order+1)) else: ngram_tokens = original_tokens # Observations # We could initialize this to 0, but, depending upon the ngram length, some occurences may not occur at all ngram_counts = dict() total_ngrams = 0 # Use the ngrams joined by an unused character as the key def ngram_to_key(ngram): return '-'.join(ngram) # Now loop through the words for i in range(args.order, len(words)): ngram = words[i-args.order:i+1] key = ngram_to_key(ngram) if key not in ngram_counts: ngram_counts[key] = 0 ngram_counts[key] = ngram_counts[key] + 1 total_ngrams += 1 # Now print out the normalized frequences for each ngram indices = [str(i) for i in range(args.order+1)] column_names = [f"index {i}" for i in indices] + ["t"+str(x-args.order) for x in range(args.order)] + ["t"] # Header row print(f"{','.join(column_names)},ngram") for token in ngram_tokens: key = ngram_to_key(token) if key in ngram_counts: token_is = ','.join([str(original_tokens.index(t)) for t in token]) print(token_is + ',' + ','.join(token) + f",{ngram_counts[key]/total_ngrams}") ``` --- ## Representation * We'll represent the $P(X_t|X_{t-1})$ as a matrix * Called a `transition matrix` * $KxK$, where $K$ is the number of tokens * $k=27$ for the letter + space unigram * Let's call the transition matrix $A$ for simplicity --- ## Transition Matrix * $A_{ij}$ is the probability of getting from $i$ to $j$ in one step * An n-step transition's probability is * $A_{ij}(n) \triangleq P(X_{t+n} = j|X_t = i)$ * At state $i$ at time $t$ and arrive at state $j$ at time $t+n$ --- ## Uses * How can we use this? * We haven't yet gotten to the latent estimation part * Still some useful properties though * First, we can give probabilities to sequences * If we train two models for two different classes we can then compare the probability of being in one vs the other * Still brittle to poisoning attacks --- ## Uses --- Typos * But what if we add tokens that represent actions? * For example, a token that represents deleting or adding characters? * Now we can represent an intentionally misspelled word * We can also create transition states for for misspellings and see if spammers look different from authentic senders --- ## Estimating Probabilities * We haven't covered how to estimate probabilities yet * If our chain is long, we'll end up with sparse data * With $K$ tokens, and n-gram transition matrix has $O(K^n)$ parameters * Most of them will be unexplored, unless we get to huge training sets * For $K=1000$, a chain of 4 is a million, 7 is a billion, ... * Even War and Peace has only 566k words * So a predictor will be quite weak --- ## Sentence Predictor ```python #! /usr/bin/python3 import argparse import itertools import numpy as np import string import sys if __name__ == "__main__": parser = argparse.ArgumentParser() parser.add_argument( "path", type=str, help="Path to a text file.") parser.add_argument( "order", type=int, help="Number of past words to look at. 0 for unigrams.") parser.add_argument( "start", type=str, nargs='+', help="Starting words for the predictions. Should be > order-1") args = parser.parse_args() assert(args.order < len(args.start)+1) try: with open(args.path, 'r', encoding='utf-8') as corpus: text = corpus.read() except FileNotFoundError: print(f"Error: The file '{args.path}' was not found.") sys.exit(1) # Change everything to lowercase. # Count the end of sentences as their own tokens. text = text.lower().replace('\n', ' ').replace('.', ' .').replace('?', ' ?').replace('!', ' !') # Replace unknown characters with a space text = ''.join([c if (c.isalpha() or c in ['.', '?', '!']) else ' ' for c in text]) words = text.split() # Observations # We could initialize this to 0, but, depending upon the ngram length, some occurences may not occur at all ngram_chains = dict() # Now loop through the words for i in range(args.order, len(words)): ngram = words[i-args.order:i+1] # Loop through the ngram chain and fill in any missing links cur_dict = ngram_chains for gram in ngram[:-1]: if gram not in cur_dict: cur_dict[gram] = dict() cur_dict = cur_dict[gram] if ngram[-1] not in cur_dict: cur_dict[ngram[-1]] = 0 cur_dict[ngram[-1]] += 1 # Use the starting word to predict some sentences for sample in range(10): cur_sentence = [word for word in args.start] while cur_sentence[-1] not in ['.', '?', '!'] and len(cur_sentence) < 50: # Use the tokens from our sentence to fetch the next word probabilities tokens = cur_sentence[-args.order:] cur_dict = ngram_chains for token in tokens: cur_dict = cur_dict[token] possible_words = list(cur_dict.keys()) frequencies = np.array(list(cur_dict.values())) probabilities = frequencies/np.sum(frequencies) next_word = np.random.choice(possible_words, p=probabilities) cur_sentence.append(next_word) print(' '.join(cur_sentence)) ``` --- ## Predicting Sentences * We can use this to predict sentences: <pre> $ python3 predict_similar_sentences.py MobyDick_HermanMelville.txt 2 the whale the whale . the whale whose distant jet is so passing wonderful ! the whale ship carries no cargo but herself and crew their weapons . the whale by his subsequent ocean life and only god bullied hull thou firm deck and in that quarter of the various lines and courses on the point of all oceanica . the whale . the whale as much blood as will presently be seen . the whale s is to be borne in mind it s not the whiteness of the narwhale however that may be mine let me learnedly define it . the whale fishery had been made to spout thick blood such a basis . the whale . the whale alongside a day and though from the whale . </pre> * Fairly meaningless without longer ngrams --- ## Trigrams <pre> $ python3 predict_similar_sentences.py MobyDick_HermanMelville.txt 3 the whale had the whale had sounded but intending to be near him at the next fifty seeming to commence at number one each time as though he thought it a great pity that such a sensible young man should be a thing for salamander giants only to encounter how small the chances the whale had sounded but intending to be near him at the next rising he held on his way to john ferdinando as he calls the modern juan fernandes . the whale had reeled the involutions of the lines around him the mighty idler seemed the cunning weaver himself all woven over with the vines every month assuming greener fresher verdure but himself a skeleton . the whale had reeled the involutions of the lines around him the mighty idler seemed the cunning weaver himself all woven over with the vines every month assuming greener fresher verdure but himself a skeleton . the whale had sounded but intending to be near him at the first tap of the boat resting crosswise upon the loom or handle of every man s and if on that day i shall again raise him then ten times its sum shall be divided among all of ye the whale had at length become aware of his pursuers . the whale had hitherto been popularly regarded . the whale had at length become aware of his pursuers . the whale had sounded but intending to be near him at the first tap of the boat and climbing the gunwale stood face to face saw the parsee and with fixed upward eye and high flung right arm he stood erect before the lofty tri pointed trinity of flames . the whale had at length become aware of his pursuers . </pre> --- ## Anna Karenina Trigrams <pre> $ python3 predict_similar_sentences.py AnnaKarenina_LeoTolstoy.txt 3 the world was the world was open for him personally but would only perhaps detract from his romantic character in the eyes of others . the world was exposed to such incidents but that he would go mowing however awkward he might feel about it with his whole hand as it were with perplexity or reproach in her eyes died away but the word love and for a long time . the world was exposed to such incidents but that he did not know on what terms you will be so . the world was exposed to such incidents but that he would never go and see her today . the world was shut on them he put it to the footman . the world was shut on them he put it to her lips . the world was exposed to such incidents but that he only knew much later . the world was exposed to such incidents but that he could not decide this straight off and taking off his cap let her pass before him . the world was open for him personally but would only perhaps detract from his romantic character in the eyes of betsy or any other work associated in any way it was such torture ? </pre> --- ## Why is this awful? * Any arbitrary ngram isn't very likely, so we're data starved <pre> $ python3 predict_similar_sentences.py RomeoAndJuliet_WilliamShakespeare.txt 2 the pox the pox of such damage . the pox of such damage . the pox of such prolixity we ll to dinner thither . the pox of such damage . the pox of such antic lisping affecting phantasies these new tuners of accent . the pox of such prolixity we ll to my sweet love . the pox of such sweet sorrow that i were sleep and peace so sweet saluteth me ? the pox of such antic lisping affecting phantasies these new tuners of accent . the pox of such sweet flesh ? the pox of such antic lisping affecting phantasies these new tuners of accent . </pre> --- ## Solutions to Missing Data * Add more data! * Google has n-gram models fit to 5 by gathering one trillion words * 100GB text dataset * [https://research.google/blog/all-our-n-gram-are-belong-to-you/](https://research.google/blog/all-our-n-gram-are-belong-to-you/) * Or we could use a statistical approach --- ## Next Time * We've got our temporal dependencies * But we need to deal with sparse data * And what about that latent space estimation? * We'll add that with `hidden markov models` <!-- Graphs of unigrams and bigrams for Origin of Species Vs (maybe Anna Karenina) (Compare Anna Karenina with War and Peace, see if there is any author similarity) TODO Show some sentence predictions. Build transition matrix (17.2.2.1) (math representation, the transition matrix 17.2.1) (language model 17.2.2.1) (sparse data problem) (17.2.2.2 working with less data) (17.2.2.3 out of vocabulary words) (stationary distribution? pagerank? -->