2c:null 2d:["$","title",null,{"children":"Exploring n-grams | Daniel Howe | Observable"}] 32:T43b, The basics of n-gram language models are relatively straightforward. We take a window of some length, called *n*, and look at each sequence of *n* tokens (usually letters or words) in a text. We store the first *n-1* sequences in our model, together with the token directly following it (the *nth*). Using this data we can estimate which tokens are more or less likely to follow which other tokens in our data. With a model like this we can either analyze existing texts or generate a new text. In either case we are attempting to iteratively predict a _next_ token, given a sequence of preceding tokens. Those familiar with large-language models like ChatGPT or Claude will recognize this as a high-level description of what they do. The full picture of how LLMs work is more complex but the core task of most language models, whether a simple n-gram or a complex transformer, is to "read" text and predict the word most likely to come next. 33:T63d, ------- ### A first n-gram model Let's think about how a simple `n-gram` model might work. For this toy example, we'll use words as our tokens, and our training data will consist of the single sentence `The quick brown fox jumped over the lazy dog`. We can create an n-gram model with `n=4` by looking at each sequence of 3 words in our sentence: `'The quick brown'`, `'quick brown fox'`, `'brown fox jumped'`, and remembering which word comes *next* (the *4th*) after each. In a simple implementation we might store each of the sequences in an object, where the key is the 3-word phrase and the value is the array of _next_ words from our training data: ```js { 'The quick brown': ['fox'], 'quick brown fox': ['jumped'], 'brown fox jumped': ['over'], ... } ``` As we add more sentences to the model, we will eventually fill out the array values to contain all possible *next* tokens for every sequence of 3 words we've seen. Depending on the additional training data, we might end up with an entry like: ```js 'brown fox jumped': ['over', 'over', 'on', '.', ',', 'over', 'on'] ``` Notice that in addition to words we also have punctuation and, in this simple example, we allow duplicates like `'over'` and `'on'` (though to conserve memory we might keep counts instead.) Once we've created such a model, we can use it to predict the word or words most likely to follow a sequence in a text that we haven't yet seen (text that is NOT in our training data). This can be useful in text analysis, for example, when trying to detect whether a text was written by a specific author. 34:T414,But let's focus on generating text. We can begin with a starting sequence of *n-1* tokens (either supplied as a *prompt* or randomly chosen), then select from possible next tokens according to their probabilities. We add the selected word to our search phrase, and drop the first word to maintain a length of 3 tokens (our *n-1*). We continue this process until we reach the desired number of words, or we hit some predefined end-of-sequence token. As an example, we can imaging starting with our toy prompt `'The quick brown'`. Our model might return `'fox'` as a possible next token. We then add `'fox'` at the end of our prompt, and drop the first word, giving us `'quick brown fox'`. We again query the model with this prompt and get the following possible next tokens (as above): `['over', 'over', 'on', '.', ',', 'over', 'on']`. We select one, let's pick the comma, and then repeat the process, searching next for `'brown fox,'`. If we stop after hitting an `end-of-sequence` token, we will have generated one "sentence" from the model. 35:T500,--- ### Generating sentences To output simple English sentences, we need to add a few more constraints to our generator. We probably always want to start with a capital letter and to end with a period, question mark or exclamation point. A simple version of a `generate()` function might look like this: ```js generate() { const startToken = /^[A-Z]/; const endToken = /[.,!]/; const result = []; // find all the tokens matching the startToken pattern const starts = Object.keys(this.data).filter(t => startToken.test(t)); // pick a first token randomly and add it to 'result' const first = starts[Math.floor(Math.random() * starts.length)]; result.push(...first.split(' ')); // now generate until we hit an end-token while (true) { // find the next token const query = result.slice(-(this.n - 1)).join(' '); // n-1 token query const options = this.data[query]; // the options to choose from const index = Math.floor(Math.random() * options.length); // random choice const next = options[index]; // the next token // add it to our 'result' so far result.push(next); // check for an end token if (endToken.test(next)) { return result; // done } } } } ``` 36:T8af,### The problem of scale: infinite n-grams An important problem we need to address when thinking about n-gram generation is that of scale. For generation to be effective, we generally want to use a large amount of text. To address dependencies at a distance in text (for example, open and closing parentheses) we need the model to be able to compute sequences with higher `n` values. Yet storing this data in memory, at least using an implementation like above, is practically infeasible. As we increase our `n`, the size of our model grows exponentially. To solve this problem we can employ an interesting data structure known as the suffix array, introduced first in [CITE]. A suffix array stores all the possible suffixes of a string in sorted order. As an example, the suffix array for the word "overwhelmed", would look like this, with `$` marking the end of the word: ```js [ 0: 'd$', 1: 'ed$', 2: 'elmed$', 3: 'erwhelmed$', 4: 'helmed$', 5: 'lmed$', 6: 'med$', 7: 'overwhelmed$', 8: 'rwhelmed$', 9: 'verwhelmed$', 10: 'whelmed$' ] ``` To store this data, we only need store the input string, and one numeric index for each suffix. So the actual data stored in this example is the array of indexes: ```js [ 10, 9, 6, 2, 5, 7, 8, 0, 3, 1, 4 ]``` from which, using `substring()` or `slice()`, we can construct the suffixes listed above. So the total storage for a suffix array built from a string of length `k` is Θ(k). More importantly, with some clever coding (see [A,B,C]), we can build a suffix array in time linear to the input, also Θ(k). Finally, because the entries in the model are sorted, we can use binary search to find any sequence in our model in Θ(log k) time. For example, in our toy example above, if we want to find all sequences starting with the letter `e`, as we know that they will be neighbors in our array, we can use binary range search [see implementation here], to find the starting and ending index for that pattern, namely indexes `1` and `3`. Perhaps surprisingly this data structure allows us to efficiently store _all_ the possible n-gram sequences for a model, and to quickly find them as needed, even for very large input texts. Thus, infinite n-grams...37:T4cd, -------- ### Bidirectional generation Because we have used a Suffix Array for our language model, and the suffixes are sorted, we know that sequences of common words (like `['over', 'the']` in the example above, are stored next to each other. This makes it relatively easy/efficient to identify such "crossover" points as we load the model. Once these are identified, rather than starting a generation from a sentence start, we can start from a crossover point, and then work in both directions toward the start and end of the sentence. To do this, we need to be able to generate in both forward and reverse. One way of achieving this is to add a second model that trains on the same input, but in reverse, answering the question of which word, given a sequence of words, is the most likely to come _before_. We can create a bidirectional model by aggregating the forward and reverse models, allowing the model to answer the question of what, given a sequence of words, word(s) are most likely to come before and after. With this aggregate, or bidirectional model, we can start our generation on an arbitrary word and precede in both directions, simultaneously, until a complete sentence has been generated. (in-progress) 38:[] 30:{"id":"8fedbf9b89eb50ba","slug":"ngram-generation-deep-dive","title":"Exploring n-grams","thumbnail":"0b226c532dbdb6381ca1d42ee19266b4e45afb1f0dad902787aeb65dece5a84c","access_level":"public","create_time":"$D2024-06-08T17:39:35.230Z","update_time":"$D2025-03-10T01:53:48.136Z","view_time":null,"first_public_time":"$D2025-03-10T01:47:48.741Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"636cf123a07db681","login":"dhowe","name":"Daniel Howe","avatar_url":"https://avatars-next.observableusercontent.com/a5081aaa56ae9990aa27642040dc61de3ce8cea67f6f778a5b864e41111ba7a3","tier":"starter_2024"},"version":309,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"32869872eb6f2f82","login":"dhowe","name":"Daniel Howe","avatar_url":"https://avatars-next.observableusercontent.com/a5081aaa56ae9990aa27642040dc61de3ce8cea67f6f778a5b864e41111ba7a3","tier":null}],"members":[{"type":"individual","id":"32869872eb6f2f82","login":"dhowe","name":"Daniel Howe","avatar_url":"https://avatars-next.observableusercontent.com/a5081aaa56ae9990aa27642040dc61de3ce8cea67f6f778a5b864e41111ba7a3","tier":null,"role":"editor"},{"type":"team","id":"636cf123a07db681","login":"dhowe","name":"Daniel Howe","avatar_url":"https://avatars-next.observableusercontent.com/a5081aaa56ae9990aa27642040dc61de3ce8cea67f6f778a5b864e41111ba7a3","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Exploring n-grams","cells":[{"id":97,"value":"# Exploring n-grams\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":91,"value":"

Note: If you're not at all familiar with n-grams, you might want to check out this notebook first.

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":134,"value":"ToC()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":13,"value":"

NOTE: Technically, some language models predict words in the middle of a text, but next-word prediction is still very common.

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":16,"value":"If given the sentence, “The quick brown fox jumped,” and asked what comes next, a language model would likely suggest \"over.”\n\nThis may not seem relevant to the feats we hear that LLMs are able to accomplish, but the right input sentence can turn a simple word-prediction machine into a question-answering machine. Take this prompt, for example:\n\n`The actor that plays Neo in the 1999 film 'The Matrix' is named ...`\n\nWhen an LLM receives a sentence like this as input, it attempts to predict the word that comes next. To do this, the model computes the probabilities for all possible next words, based on the text it has previously seen (its training data), and then picks one of the highest probability words to continue the sentence. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":26,"value":"

NOTE: While some LM do pick the word with the highest probability, creative practitioners will note that less frequent completions may be more interesting. Later I will show some different ways we can manage this tradeoff.

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":28,"value":"\n\nSimilarly, by adjusting the prompt, we can use a next-word model to carry out simple tasks. Consider the following prompt:\n\n`Now I will write a Python function to convert Celsius to Fahrenheit:`\n\nAgain the model takes this input text and predicts what words come next — in this case, the code to carry out the task in question:\n\n```python\ndef convert_celsius_to_fahrenheit(celsius): \n return celsius * (9 / 5) + 32\n```\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":34,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":109,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":62,"value":"---\n\n### Loading the model\nNow we're ready to write a class that will hold our model. Below I've added a constructor and a `loadText()` function that reads in our text, as described above.\n\n```js\nclass NgramModel {\n \n constructor(n) {\n this.n = n;\n this.data = {};\n }\n\n loadText(text) {\n let words = text.split(' ');\n for (let i = 0; i < words.length; i++) {\n\n // get each sequence of 'n' words\n let sequence = words.slice(i, i + this.n-1);\n let sequenceStr = sequence.join(' ');\n\n // now find the next word following the sequence\n let nextWord = words[i + this.n-1];\n\n // and add it to our array of possible next words\n if (!this.data[sequenceStr]) {\n this.data[sequenceStr] = [];\n }\n this.data[sequenceStr].push(nextWord);\n }\n }\n}\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":42,"value":"$35","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":140,"value":"$36","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":197,"value":"---------\n### Generating with Infinite n-grams\n\nWhile the possibility of infinite length n-grams is intriguing, its not immediately clear how it can help us with generation. The questions remains as to how we can satisfy our constraint of novelty? And there are other constraints we may wish to consider as well, for example (thinking only about single \"sentences\" here):\n* min/max sentence length\n* inclusion/exclusion of specific words\n* inclusion/exclusion of linguistic features (rhyme, meter, etc.)\n\nOne approach would be that of 'generate-and-test', repeatedly generating a sentence until it passes our set of constraints, backtracking each time a constraint is violated or a sentence ends without satisfying another.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":247,"value":"-------\n### Generate and test: a backoff model\nAt a very high-level, our algorithm for a backoff-model using generate-and-test might look something like this:\n```js\ngenerate() {\n sofar = [];\n exclude = [];\n constraints = {...};\n next = selectStartToken();\n \n for (tries = 0; tries < maxTries;) {\n next = selectNextToken(sofar, exclude);\n if (!next) {\n sofar.pop(); // remove last word\n exclude = [];\n if (sofar.length == 0) { \n next = selectStartToken(); // start again\n tries++;\n }\n }\n \n // check if adding the new word would violate a constraint\n if (checkConstraints(constraints, sofar, next)) {\n sofar.add(next); // if not, add it\n \n if (next === endToken) break; // check if we're done\n }\n else {\n // if the new word violates a constraint, don't pick it again\n exclude.add(next);\n }\n }\n return sofar;\n}\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":295,"value":"--------\n### Ensuring originality\nThere is another problem we should consider if we are looking to create novel outputs with our language model, specifically that the model _could_ output one of the sentences from its input, word for word. As we're trying to create new and interesting language, this is clearly a problem. How can we organise are generation so that only novel outputs are generated ?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":262,"value":"Let's look at a test example with just two sentences:\n```\nA red fox jumped over the fallen log.\nThe brown dog wept over the treat.\n```\nYou might notice that there is exactly one shared bigram between these two sentences, specifically `\"over the\"`. If we set n=3, there are exactly 4 sentences we can generate:\n```\nA red fox jumped over the fallen log.\nThe brown dog wept over the treat.\nA red fox jumped over the treat.\nThe brown dog wept over the fallen log.\n```\nThe first two are clearly from our input, while the second two are original, at least as far as this trivial example goes. If we examine these outputs we see that the model used this repeated bigram to _jump_, or _cross over_, from one input sentence to the other.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":236,"value":"$37","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":146,"value":"--------\n### Telescoping n-Factor (tbd)\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":158,"value":"--------\n### Skip-grams (tbd)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":174,"value":"------\n### Models with embeddings (tbd)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":30,"value":"\n--------\n\n### References / appendices\nToner, H., & Burtell, M. (2024, March 11). The surprising power of next word prediction: Large language models explained, part 1. https://cset.georgetown.edu/article/the-surprising-power-of-next-word-prediction-large-language-models-explained-part-1/ ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":124,"value":"import {ToC} from \"@rmw4269/contents\" ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1"}} 31:"$30:body"