EPISODE TRANSCRIPT
Introduction to Natural Language Processing (Jacob Eisenstein)
Automatically transcribed from the episode audio. Some words and names may be inaccurate.
Listen to the episodeDownload textDownload captions
Welcome, the learner, to the Deep Dive. We are, well, we're really thrilled to have you here with us today. You know, usually when we talk about a physical system, there's this expectation of smooth continuity. Think about, like, engineering or physics. If you drop a tennis ball off a roof, gravity pulls it down. and its trajectory is this continuous, predictable arc. Right, yeah. You could hypothetically measure its position at, I mean, any infinitesimally small fraction of a second, and you would find it moving along a perfectly smooth mathematical curve. It is, you know, a very comforting way to view the universe.
Physical laws just lend themselves so beautifully to continuous mathematics. The equations of motion allow for infinite gradations, which makes modeling them computationally, well, pretty straightforward. But then you step into the world of human language, and suddenly that smooth, continuous curve just completely shatters. For those of you listening, imagine trying to plot a conversation on a graph. We're looking at a landscape that is fundamentally discrete, incredibly messy, and honestly, entirely murky. Yeah, that's the core issue. Language operates in discrete combinatorial chunks. You cannot utter a sound that is mathematically like halfway between the word cat and the word dog to convey some sort of hybrid animal. Right, a dat, a cog, doesn't work. Exactly. You either select the discrete symbol for cat or you select the discrete symbol for dog. There is no smooth gradient there. And that fundamental friction.
Between the continuous math that computers absolutely love and the discrete, chaotic building blocks of human language is our mission for today. We are going to meticulously unpack a truly foundational text in the realm of artificial intelligence. I'm talking about Jacob Eisenstein's introduction to natural language processing. It's an incredible text. It really is. And our goal for you today is to explore the specific mathematical and computational toolkit that engineers use to translate our messy communication into something a machine can process, learn from, and ultimately generate on its own.
Bridging that gap really is the central challenge of the entire field because Beyond just being discrete, language is wildly compositional. We take these distinct symbols words and we snap them together to form phrases, which then snap together to form sentences. Like Legos, basically. Exactly like Legos. The number of possible valid sentences you can create is virtually infinite. Yet historically, computational hardware is built to multiply matrices of continuous numbers. Reconciling those two completely different realities requires some... Well, some extraordinary mathematical ingenuity. Yeah, and before we get into the heavy machinery of how computers actually read, I think we need to set a baseline here. Eisenstein draws a really important distinction early on between computational linguistics and natural language processing. Because, you know, on the surface, they sound like the exact same discipline. They do, and they frequently share academic spaces, but their underlying philosophies are entirely distinct. Computational linguistics is primarily a scientific endeavor. The ultimate goal is to understand the cognitive and structural realities of human language. Okay, so it's about the humans, not the computers. Right. A computational linguist uses the computer as a microscope, a tool to test hypotheses about how the human brain processes grammar or acquires vocabulary. So the computer is just serving the science of linguistics. But NLP natural language processing is completely different, right? NLP is an engineering discipline.
The goal is to build computational algorithms to actually do a specific task. Like if you're building a spam filter, a machine translation app, or a virtual assistant, your goal is pure utility. Yes, utility is the perfect word. If the machine translation system successfully translates a highly complex medical document from Mandarin to English, that is a massive triumph of NLP. It really does not matter if the algorithm used to achieve that translation bears absolutely no resemblance to how a bilingual human being actually translates language in their head. The machine doesn't have to think like us, it just has to perform for us. Exactly. NLP cares about the functional output, not necessarily cognitive plausibility. That makes total sense. And to build these highly functional systems, Eisenstein introduces a core motif that we are going to see over and over today. It's this duality, search versus learning. Yeah, any robust NLP system has to balance those two forces. To understand the distinction, we really need to look at how a machine approaches a problem space. Okay, let me try out an analogy here for the listener.
Imagine learning is like figuring out the rules of a new, incredibly complex board game just by watching people play it over and over again. You observe thousands of matches. Eventually, you synthesize a model in your head, like, aha, the night piece moves in an L shape. I like that, yeah. So that's the learning part, building your internal model of how the universe of the game works. But search is the act of actually sitting down to play. It's looking multiple moves ahead, evaluating all the possible branching paths on the board, and trying to find the absolute winning sequence of moves. That captures the dynamic perfectly, I mean, really well. In modern natural language systems, the learning component relies on numerical optimization. We feed the machine vast data sets of text, and it adjusts millions of internal mathematical weights to build a probabilistic model of the language. That model dictates the rules of the game. Right, so the machine is staring at the board game, absorbing the patterns. Precisely.
Then comes the search. When you hand that trained model a brand new, never -before -seen sentence and ask it to parse the grammar, the model faces an exponentially large space of possible interpretations. Because language is ambiguous. Highly ambiguous. A complex sentence might have thousands of theoretically valid grammatical structures. The search algorithm is the engine that efficiently navigates that massive combinatorial explosion to find the single most probable interpretation based entirely on the probabilistic rules it established during the learning phase. Which introduces a huge tension, right? Yeah. If your linguistic model is too simplistic, your search is fast, but your results are absolute garbage. But if your model captures all the beautiful, nuanced complexity of human language, the search algorithm might take until the heat death of the universe just to evaluate every possible interpretation. That is the defining struggle of the field. Balancing the expressiveness of the model with the computational tractability of the search algorithm, you are always trading one for the other. So how do we even begin? We need to get a computer to look at a single word.
Let's step into the foundational methods of learning, starting with chapter two. The absolute simplest way a computer can process a document is something called the bag of words representation. Ah, yes. The bag of words takes a complex piece of literature and reduces it to a sheer mathematical vector. It is literally just a simple list of frequencies. It discards grammar, it discards narrative structure, and it completely discards word order. For you listening, picture making a smoothie out of a classic novel. Let's say you take Moby Dick and throw the entire book into a blender. You know the exact inventory of your smoothie. You know the word whale went in 1 ,200 times. You know Ahab went in 500 times. But you have... utterly lost the shape and structure of the ingredients.
The sequence is gone. Exactly. The sequence of events, the looming dread of the prose, it is completely obliterated. You just have a sludge of word counts. It sounds incredibly reductive, and honestly, it is. However, this representation is astonishingly effective for tasks like linear text classification. Consider a spam filter. Oh, right, because the structure doesn't matter there. Exactly. To determine if an incoming email is spam, the system rarely needs to parse the complex syntactic dependencies of the sentences.
It primarily needs to check if the frequencies of specific words like urgent, discount, wire, or lottery are abnormally high compared to a normal email. The machine doesn't care how you use the word lottery. It just cares that the lottery ingredient is dominating the smoothie. And to classify these texts, Eisenstein brings up the Naive Days classifier. I really need some help here, because the way this algorithm works feels totally backward to me. It relies on something called a generative process. I know, it is a bit counterintuitive. Naive Bayes solves a classification problem by inventing a probabilistic fiction about how the text was written in the first place.
A fiction? Yes. Imagine the computer assumes that before you type an email, you randomly pull a hidden label out of a hat. Let's say you pull out the label spam. Okay, I am a spammer. Holding my label. Based solely on the fact that you hold that S -spam label, the computer imagines you walk over to a giant physical bag filled with spam -related vocabulary. You reach in, pull out a word, write it down, put it back. Then you reach in, pull out another word, write it down. You repeat this until your email is finished. Wait, I have a massive problem with that. Humans do not vomit independent words onto a page like that. If I write the word sand, the very next word I write is overwhelmingly likely to be Francisco.
The words are intimately dependent on each other. your objection is entirely valid which is exactly why the algorithm explicitly includes the word naive in its name it makes the mathematically convenient though linguistically absurd assumption that every single word in the document is generated completely independently of every other word conditional only on the label if it's so absurd why build a system around it why force the computer to make such a dumb assumption We make that assumption to avoid computational paralysis. If you do not assume independence the probability mass becomes intractable. To calculate the exact probability of a 20 -word sentence without the independence assumption, you would need to calculate the joint probability of all 20 words appearing in that exact sequence. It's just rare. Extremely rare.
You would never have enough training data to reliably estimate that. By assuming independence, the math simplifies drastically. You simply calculate the individual probability of each word occurring in a spam email and you multiply them all together. Wow. Okay. It turns a massive impossible probability puzzle into just a long string of simple multiplication. Furthermore, it acts as a linear classifier. In a high -dimensional space where every word in the English language represents a different geometric dimension, Naive Bayes essentially draws a single flat hyperplane, like a straight sheet of glass, that separates the spam vectors on one side from the non -spam vectors on the other. That brings up an interesting historical quirk in Chapter 3. We hear so much about deep learning and neural networks today, but NLP relied on these simple linear models like naive Bayes or support vector machines for a really, really long time. Computer vision adopted deep, nonlinear neural networks way before text processing did.
Why was language so late to the deep learning revolution? That delay really stems from the fundamental difference between an image pixel and a word. In computer vision, a single pixel carries almost zero semantic meaning. A lone brown pixel does not tell you if you are looking at a dog, a tree, or, you know, a cup of coffee. Right, it's just brown. Exactly. You must use nonlinear neural networks to combine pixels into edges, combine edges into textures, and combine textures into recognizable shapes. You have to build the meaning up from nothing. But a word is different. A single word carries immense semantic weight right out of the gate. If a movie review contains the word horrendous, that single feature provides a massive signal about the sentiment of the text, regardless of the surrounding words.
Because text represents such a high dimensional space with hundreds of thousands of discrete vocabulary words acting as independent features, linear models were highly effective. They didn't need the deep layers to find the meaning. No, they didn't. In fact, simpler linear models are naturally resistant to overfitting in those massive dimensional spaces. whereas early neural networks struggled immensely with text. But eventually, the sheer predictive power of nonlinear models like feedforward and convolutional neural networks became too massive to ignore. What did neural networks offer that the linear sheet of glass couldn't? They offered the ability to learn intermediate representations. A linear model maps the input directly to the output. A neural network passes the input through hidden layers, mathematically transforming the data into entirely new geometric spaces. This allows the network to capture complex interactions between words. Give me an example of that. Okay, a linear model sees the word good and adds points to the positive sentiment score.
It sees the word not and adds a tiny bit to the negative score, just adds them up. But a neural network can learn that the specific combination not good operates as a single conceptual unit that wildly flips the sentiment, capturing a nonlinear interaction. Ah, I see. And building these networks introduces the concept of computation graphs. Eisenstein makes a huge point about the difference between static graphs and dynamic graphs, which seems to be a uniquely painful problem for language processing. It was a massive headache. A computation graph is essentially the architectural blueprint of the mathematical operations the neural network will perform. With a static graph, you define that blueprint once.
You compile it and you push thousands of examples through it. This works flawlessly for computer vision because every image can be resized to exactly 256 by 256 pixels. The input size never changes. But sentences refuse to conform to a fixed size. If you are analyzing a book, one sentence might be three words long. The very next sentence might be 45 words long with multiple nested clauses. And that variability breaks static architectures completely. Consequently, NLP engineers had to pioneer dynamic computation graphs. The architecture of the neural network, the actual mathematical flowchart, must be constructed dynamically, on the fly, for every single input sentence to accommodate its unique length and grammatical structure. It requires significantly more complex engineering. Let's actually look at how these classifiers perform in the real world. In Chapter 4, Eisenstein highlights a really fascinating study by Alm and colleagues regarding linguistic applications and emotion. They wanted to see if a machine could read a children's fairy tale, like a Grimm Brothers story, and map individual sentences to Ekman's six universal emotions.
You know, anger, disgust, fear, joy, sadness, and surprise. Yes, the practical application of this research was actually text -to -speech generation. If an automated system is reading a story to a child, you want the synthesizer to inject the appropriate emotional prosody rather than droning on in a flat robotic monotone. I have to express some deep skepticism here, though. Human emotion is incredibly subjective. If you hand a paragraph of a grim fairy tale to three different human adults, they will likely disagree on the underlying emotion. One might say the villain's dialogue shows anger, another might say disgust, and a third might argue it's actually fear. That's very true. If the human beings providing the training data cannot even agree on the emotional ground truth, how can we possibly expect a machine to classify it accurately? You have identified the exact theoretical ceiling of machine learning on subjective tasks. Eisenstein highlights the study specifically to demonstrate that limitation.
Even the most sophisticated classifiers in that study maxed out at roughly 60 to 70 % accuracy. When the training labels themselves are noisy and subjective, the algorithm's performance is permanently capped by that human ambiguity. Wow. You literally cannot optimize past the ambiguity of the human soul. A poetic way to frame it, but mathematically accurate. However... What makes the study remarkable is how the researchers managed to squeeze out that 70 % accuracy. They realized that the bag -of -words smoothie was totally insufficient. So they engineered new features based on metadata. Metadata like what?
Structural context. For example, they tracked the physical position of the sentence within the overall story. Oh, that makes so much sense. The climax of a fairy tale, which is usually situated near the end of the text, is statistically far more likely to contain expressions of fear or surprise than the opening once upon a time paragraph. Precisely. By injecting structural narrative knowledge into the statistical learning algorithm, they provided the machine with hints that exist outside the raw vocabulary. OK, but everything we have discussed so far. Naive Bayes' neural networks sentiment analysis relies on human beings sitting in a room and manually labeling thousands of emails as spam or thousands of sentences as angry. This is supervised learning. But Chapter 5 asks, what happens when we don't have labeled data? How does machine learn when we absolutely refuse to give it the answer key? That brings us to expectation maximization or the EM algorithm.
I need you to break this down for me because reading the math for this felt like looking at a chicken and egg paradox. It is a bit mind bending at first. Expectation maximization is widely considered one of the most elegant algorithms in statistical machine learning. We use it when dealing with hidden variables. Let's assume you have 10 ,000 news articles and you want the machine to cluster them into distinct topics, say sports, politics and finance. But you do not have any labels and you do not know which words indicate which topics. That's the paradox. If I knew what the topics were, I could easily find the words that represent them. And if I knew which words represented the topics, I could easily sort the articles. But I have zero information on either side. To break that deadlock, the EM algorithm performs an iterative two -step mathematical dance. The first phase is the E -step, or expectation step. Because you lack the parameters of the clusters, you simply formulate a guess. You initialize the model with entirely random... terrible parameters.
So the machine just randomly assumes that the word baseball belongs to the politics cluster. Yes. Initially, it is a completely uninformed guess. Using those terrible random guesses, the machine evaluates every single document. It calculates the probability of each hidden variable. It basically says, given my current flawed definition of what these topics look like, what is the probability that document A belongs to topic 1? It doesn't assign a hard label, though, right? It assigns a soft probability, like saying document A is 60 % topic 1 and 40 % topic 2. Correct. That soft assignment completes the E -step. Then we transition to the M -step, the maximization step.
The algorithm takes all of those newly generated soft probabilities and uses them to fundamentally update its parameters. It looks at the data and says, if document A is 60 % likely to be in topic 1, let me look at the actual words inside document A and adjust my mathematical definition of topic 1 to more closely resemble those words. And then it just feeds those updated definitions back into the beginning. It loops indefinitely. Armed with a slightly less terrible definition of the topics, it returns to the E -step and recalculates the soft probabilities for every document. Then back to the M -step to refine the topic definitions again. As this dance iterates, the mathematics guarantee that the model will continually climb upward, converging on a solution that maximizes the likelihood of the observed data. It discovers the hidden structure entirely on its own. It pulls itself up by its own statistical bootstraps.
That is so cool. But here's the major pivot as we move into part two of the book. Everything we have explored so far has fundamentally treated language as our smoothie. But true language is not a blender full of independent words. The sequence of the ingredients is the entire point. If I say the dog bit the man. That represents a very different reality than the man bit the dog, even though the bag of words contains the exact same frequency of ingredients. That realization marks the critical threshold in computational linguistics to capture actual linguistic phenomena, syntax, grammar, meaning we absolutely must abandon the bag of words and construct mathematical models that respect sequences. Which takes us into the realm of language models and engrams in Chapter 6. How does Eisenstein define a language model in this context? Because, you know, today we hear language model and immediately think of giant chatbots, but the mathematical definition is much narrower here. At its foundational level, a language model is simply a probability distribution over sequences of words. Its only job is to assign a probability score to a specific string of text answering the question, how likely is this exact sequence to occur in this specific language?
If you give the model the sequence, I would like a cup of coffee, it assigns a high mathematical probability. If you give it coffee cup, like what an eye of, it assigns a probability approaching zero. And practically, it achieves this by predicting the very next word in a sequence, right? Like the autocomplete function on a smartphone. Yes, exactly. By chaining together conditional probabilities, predicting the next word given the history of the previous words, you can calculate the score for an entire sentence. Historically, the most common way to do this was using engrams. An engram is simply a contiguous sequence of n items. A bigogram is a sequence of two words. A trigram is a sequence of three words. So if I want to predict the next word using a bigogram model, the machine is only allowed to look at the single preceding word. If I use a trigram model, it looks... The two preceding words. It's like dragging a tiny restrictive window across a sentence.
Why restrict the machine's vision so severely? Why not let it look at the previous 20 words to make a better guess? Because if you expand the window, you immediately crash into the problem of data sparsity. infinitely creative. If you want to calculate the probability of the word coffee based on the specific exact sequence of 20 words that preceded it, you must search your training database to find how many times that exact 20 -word sequence occurred. And even if your database is the entire internet, you will almost certainly never find that exact 20 -word sequence. People invent new sentences every second.
Exactly. The frequency count would be zero. That is the sparsity problem. So we intentionally restrict the context window to big grams or prigrams, ensuring we actually have historical data to count. But even with a trigram window, sparsity haunts us. What happens when your model encounters a valid three -word sequence it has never seen in its training data? Say the sequence walrus performing ballet. If it just counts frequencies, the count is zero. And in probability math, if you multiply a long chain of fractions and just one of them is zero, it wipes out the entire equation. The whole sentence gets a probability of absolute zero. To prevent that mathematical catastrophe, engineers utilize techniques known as smoothing and discounting. Smoothing conceptually involves taking a tiny fractional sliver of probability mass away from the common word sequences we have seen and redistributing it evenly across all the hypothetical word combinations we haven't seen. It ensures no sequence ever receives a hard zero. A more elegant solution discussed in the text is Katz -Bakoff. I really appreciate the intuition behind Katz -Bakoff. It operates the way a human might guess. The model says, I have never seen this specific three -word sequence before, so I have no data. Let me back off and just check my data for the two -word sequence.
If I haven't seen that either, I'll back off again and just look at the raw frequency of the single word. It systematically retreats to shorter, more abundant histories when the longer history is too sparse to trust. It is highly effective. However, the paradigm fundamentally shifted with the introduction of recurrent neural networks, or RNNs. Ngram models, even with cats back off, are ultimately just playing a massive game of counting occurrences and dividing them into fractions. RNNs approach the problem entirely differently. They treat word prediction as discriminative learning. Walk me through what that actually means for the machine. Instead of looking up a fraction in a massive table of counts, the RNN processes a sequence of words one at a time.
As it reads each word, it continually updates an internal mathematical vector called a hidden state. This hidden state acts as a compressed memory of everything the network has read up to that point. The network then uses that dense mathematical state to discriminate, to actively classify which word from the entire vocabulary should be generated next. So it's not just checking a lookup table anymore. Right. Because it is utilizing dense mathematical representations of context rather than rigid text matching, it can generalize to completely unseen combinations of words far more effectively than any n -gram model ever could. Okay, so language models predict the next word. But let's shift gears to Chapter 7. We also need to be able to analyze the words we already have. That brings us to sequence labeling.
We want to take a complete sentence and tag every single word. A classic example is part of speech tagging. We want the machine to label every word as a noun, verb, adjective, and so on. A foundational probabilistic framework for sequence labeling is the hidden Markov model, or HMM. It views language through a specific theoretical lens. The sequence of grammatical tags is the hidden process operating beneath the surface. You cannot physically see the tags. You can only see the emitted observations, which are the actual words printed on the page. So for you listening, imagine the computer is staring at the word fly. It has no idea if that word is functioning as a noun, like the annoying insect buzzing around. or a verb like boarding an airplane. To resolve that ambiguity, the HMM relies on two distinct sets of probabilities. The first are transition probabilities.
Structurally, how likely is it that a noun immediately follows an adjective? The second are emission probabilities. If the hidden stay is currently noun, how likely is it to omit the specific word fly compared to omitting the word apple? The algorithm balances the structural transitions against the specific vocabulary emissions to find the optimal path. But hold on. The math here seems to spiral out of control immediately. Let's say we have a short 10 -word sentence, and we have 40 possible grammatical tags. The number of possible tag sequences for that one short sentence is 40 to the power of 10. That is trillions of possible combinations. We surely cannot ask the computer to calculate the probability for every single one of those trillions of combinations just to find the highest score. You are correct.
Calculating every path would be computationally crippling. This is where we rely on an extraordinary piece of computer science known as the Viterbi algorithm. Viterbi employs a strategy called dynamic programming to bypass the combinatorial explosion. How does it navigate without checking everything? Instead of generating full sequences, Viterbi builds a mathematical structure called a trellis, moving from left to right across the sentence, one word at a time. I always pictured the trellis like a giant sports tournament bracket. That is an excellent visualization. Let's walk through it. At word number two, the algorithm calculates the most probable path to arrive at each possible tag from word number one. And here is the genius of dynamic programming. Once it finds the best path to a specific tag at word two, it completely and permanently deletes all the inferior paths that led there. It only leaves a small algorithmic breadcrumb pointing backward to the winning predecessor. So it aggressively prunes the tree at every single step, doesn't drag any dead weight forward. Exactly. When it moves to word three, it only evaluates connections from the surviving winners of word two. By the time it reaches the final word of the sentence, it simply selects the single highest scoring tag at the very end and follows the breadcrumb trail backward through the bracket. This yields the absolute most mathematically probable sequence for the entire sentence, while only computing a tiny fraction of the total possible paths.
It's brilliant. But I have to push back on the fundamental logic of the HMM. If the Viterbi algorithm is only looking at adjacent tags, like checking if a noun follows an adjective, how does it handle long -distance relationships? In English, I might have a plural noun at the very beginning of a sentence, and due to a bunch of intervening clauses, the plural verb that matches it might be 15 words away. You have pinpointed the fatal flaw of the basic hidden Markov model. It is bound by the Markov assumption, which dictates that the probability of the current state depends exclusively on the immediately preceding state.
It has absolute amnesia regarding anything further back. So it totally forgets the subject by the time it hits the verb. Yes. You can attempt to fix this by building higher -order HMMs, like a trigram tagger that looks at the two previous tags, but expanding the memory exponentially increases the computational complexity of the Viterbi trellis. The tournament bracket just gets too large to process. Yes. This limitation forced the field to evolve toward conditional random fields and neural sequence labelers. These advanced architectures evaluate the entire sequence of input words simultaneously when scoring the tags, shattering the rigid local -only constraints of the HMM, while still utilizing a Viterbi -like decoding process at the very end to ensure the final output sequence is coherent. Okay, so we have successfully tagged a flat sequence of words.
But sentences are not just flat strings of pearls. They have deep nested architecture. We are transitioning now in chapters 9 and 10 from flat sequences to hierarchical trees, moving into formal language theory. Formal language theory sits at the intersection of pure mathematics, computer science, and linguistics. It defines a language strictly as a mathematically defined set of strings generated by specific rules. And there's a rigid hierarchy of complexity, often called the Chomsky hierarchy. The simplest level is regular languages. Regular languages are basically patterns you can capture with simple regular expressions, and Eisenstein highlights Spanish morphology as a perfect use case for this simple level of computing. Morphology studies how individual words are constructed from smaller units. Take the Spanish word canto. Depending on the context, it can translate to a song, operating as a masculine singular noun. Alternatively, it can function as the first person present indicative verb, I sing. A computational system known as a finite state transducer, or FST, can efficiently map the surface string canto to these two distinct grammatical realities. How does it do that? It does this by transitioning through a series of simple linear states based on the letters. FSTs are incredibly lightweight and blazingly fast for this kind of linear word building. They're great for building words. But they completely collapse when trying to understand English syntax.
Eisenstein provides this wondrously brain -melting example of center embedding to prove exactly why a machine needs a more complex system than a regular language to read a book. Center embedding reveals the recursive nature of human grammar. A simple, linear FST can easily parse a sentence like, the dog chased the cat. It expects a noun, then a verb. Then a noun. But English allows you to embed a completely new relative clause right in the middle of that structure. The dog the cat kissed chased the goat. And theoretically, you can keep nesting them like Russian nesting dolls. The dog the cat goat chased kissed. It sounds like absolute nonsense to the human ear because our biological working memory fails.
But grammatically, the syntax is perfectly valid. The nouns and verbs are mathematically nested inside one another. And that nesting destroys the finite state transducer. The mechanism driving regular languages has no internal memory. As it reads the sequence of nouns dog, cat, goat, it has no capacity to remember how many nouns it has seen, which means it has no idea how many corresponding verbs it needs to expect later in the sentence to resolve the grammar. To capture those nested Russian dolls, we must ascend the complexity hierarchy to context -free grammars, or CFGs. A context -free grammar relies on explicit substitution rules. It dictates that a sentence can be broken down into a noun phrase and a verb phrase. And crucially, a noun phrase can contain an entirely new sentence inside of it. That recursive loop is what allows the machine to build the hierarchical tree. To process these trees algorithmically, computer scientists often force the grammar into Chomsky normal form. This is a mathematical restriction where every grammatical rule must branch into exactly two non -terminal categories or terminate into exactly one vocabulary word. It forces the messy syntax into a pristine binary branching tree. But how does the computer actually build that tree from a raw sentence? We talked about Viterbi for flat sequences, but building a hierarchical tree requires the CKY algorithm. How does this algorithm navigate the geometry of a sentence?
If Viterbi operates like a left -to -right tournament bracket, the Kot -Kasami -Younger or CKY algorithm operates as a bottom -up combinatorial grid search. It starts at the very bottom, looking only at the individual words. It asks the grammar rules, can the word the and the word dog combine to form a valid noun phrase? The rules say yes, so it builds a tiny subtree. Then it asks, can dog and chaste combine? The rules say no, so it ignores them. So it scans all the pairs, then it moves up a level and scans all the triplets of words, seeing if those underlying subtrees can be merged into bigger branches. Systematically.
It fills a massive triangular matrix, combining increasingly larger spans of words until it reaches the final cell at the top of the grid, which represents the entire length of the sentence. If that final cell contains a valid sentence root node, the algorithm has successfully parsed the grammatical tree. It is an exhaustive search of the syntactic space. But in chapter 11, Eisenstein points out that building these massive nested boxes of phrases isn't the only way to map a sentence. We also have dependency parsing. Phrase structure trees. The binary trees CKY builds focus on abstract constituent boxes. Dependency parsing takes a much more direct approach. Instead of abstract nodes, it draws a directed mathematical graph of relationships connecting the actual words themselves. In this framework, verbs act as the structural center of gravity pointing outward to their subjects and objects. So instead of abstractly declaring that the dog is a noun phrase sitting in a larger box, dependency parsing just draws a literal arrow. originating from the verb chased, pointing directly to the word dog, and ladles that arrow subject. It feels vastly more intuitive. It maps directly to how we actually think about action, who did what to whom. It is significantly lighter computationally, and because it explicitly defines the relationships between entities, it is often far more useful for downstream engineering tasks, regardless of how the words are physically ordered in the sentence. Which brings us to a massive philosophical pivot in our deep dive in part three. A perfectly constructed sentence diagram, whether it is a beautifully nested CKY tree or an elegant dependency graph, is a staggering technical achievement of search and learning. But syntax is not semantics.
Just because the computer knows that dog is the subject of the verb chased does not mean the computer has any idea what the sentence actually means, which leads us into the quest for meaning. Semantics forces the discipline to confront true comprehension. And the historical starting point for this in chapter 12 is logical semantics, which aims to translate the fluid ambiguity of human language into the rigid, unambiguous structure of formal mathematical logic. For those of you who code, I relate to this perfectly through programming. We want to translate English into something like Python or SQL. Eisenstein uses a great mathematical analogy. The text string 5 plus 3 and the text string 4, 3, 3 plus 1 look completely different. But they have the exact same denotation. If you evaluate them, they both equal 8. We want to do the exact same thing with English sentences. We want the sentence, the canine chased the feline, and the sentence, the cat was pursued by the dog, to compile down into the exact same logical reality. To achieve that denotation, logical semantics relies heavily on the principle of compositionality. This is the axiom that the meaning of a complex expression is entirely determined by the meanings of its constituent parts and the grammatical rules used to combine them. But how do you mathematically combine the meaning of a noun and a verb? The primary mechanism detailed in the text is the lambda calculus. Let us consider the simple sentence, Alex likes brick. The entities are straightforward constants, Alex and Brit. The complexity lies in the verb likes. In the lambda calculus, the verb phrase likes Brit is not a static object.
It is represented as a mathematical function waiting for an input. For the listener, imagine the verb phrase as a wooden puzzle piece with a very specifically shaped empty slot. The puzzle piece represents the concept blank likes Brit. That is an excellent visualization. Mathematically, it is a function that requires a single argument. When the syntactic tree combines the subject Alex with the verb phrase likes Brit, the math literally plugs the constant Alex into the empty slot of the function. The function executes, resulting in a final, unambiguous logical predicate.
Likes Alex Britt. And suddenly you have a discrete, true or false statement about the state of the world that a database can query and understand. It provides absolute precision. It's incredibly elegant on a whiteboard. But practically, it seems incredibly brittle. Someone has to sit in the lab and manually write the lambda calculus functions for every single verb, preposition, and adjective in the English language. And what happens when a human uses sarcasm? What happens if a word has a double meaning? The rigid rules of formal logic must shatter upon contact with real -world conversational data. They absolutely do. Logical semantics struggles immensely with ambiguity and scale. Which brings us to Chapter 14 and the counter -revolution in how machines process meaning, Distributional Semantics. If logical semantics is a rigid dictionary of rules, distributional semantics is fluid sociology.
It operates on the distributional hypothesis, best summarized by the famous linguist John Rupert Firth, who stated, I find this concept deeply fascinating. Under this theory, you don't define a word by giving it a rigid logical definition. You define it entirely by observing the other words that surround it in natural text. If I introduce a mystery word to you, let's say the word is Barty. And I tell you that people frequently say, I drank a glass of Barty, the Barty was fermented in oak, or I bought a bottle of red Barty. You instantly know exactly what Barty means without me ever explicitly defining wine.
The Conteld reveals the meaning. Computationally, this insight gave rise to neural word embeddings, most notably the word Tuvec models. Instead of treating words as discrete, isolated symbols, the neural network maps every single word into a dense, multidimensional geometric space. We are turning words into physical coordinates. Yes. And because the network trains by observing the surrounding context, words that frequently appear in similar contexts are physically pushed closer together in that geometric space. So the coordinate for coffee and the coordinate for tea end up geometrically right next to each other because they both frequently appear near words like cup, drink, and hot. Precisely. The text details the two primary neural architectures used to construct this space, continuous bag of words, or CBOW, and skip grams. In the CBOW architecture, the network looks at the surrounding context words and attempts to predict the missing target word in the middle. It operates like a massive fill -in -the -blank test. The Stipgram architecture inverts the process. You provide the network with the target word, and it must predict the context words that are statistically likely to surround it. But here is where we hit a massive computational wall. If you are running a skip gram model and you feed it the word whale, it has to calculate a probability distribution over the entire vocabulary of the English language to guess which words might be nearby. If your vocabulary contained 100 ,000 words computing the exact mathematical probability, specifically running the SoftBanks function, for all 100 ,000 words, every single time you process a single word in your training data would grind any supercomputer to a halt. it is an immense computational bottleneck evaluating the denominator of that probability function across a massive vocabulary is mathematically grueling to solve this eisenstein highlights two highly ingenious engineering shortcuts the first is hierarchical softmax how does that bypass the math Instead of treating the 100 ,000 word vocabulary as a flat linear list that must be calculated individually, Hierarchical Softmax arranges all the words into the terminal leaves of a massive binary tree. For you listening.
Imagine organizing the entire English language into a giant game of 20 questions. That perfectly describes the mechanism. To calculate the probability of the word blubber appearing near whale, the network no longer computes 100 ,000 separate probabilities. It simply navigates down the binary tree. Is the word on the left half or right half of the tree? Left, top half, or bottom? The network only has to make a short sequence of binary decisions. Oh, wow. Mathematically, the calculation time changes from scaling linearly with the size of the vocabulary to scaling logarithmically. It transforms an impossible calculation into something that runs in milliseconds. That is incredibly clever. But the second solution is even sneakier.
It's called negative sampling. Negative sampling is a brilliant evasion of the probability calculation entirely. Instead of attempting to predict the exact probability distribution across the whole vocabulary, the network frames it as a simple binary classification task. It takes the true pair of words, for example, whale and blubber, and pairs it with a handful of randomly generated negative pairs, like whale and calculator or whale and spaghetti. It just invents fake data. Yes. And it trains the neural network on a very simple objective. Mathematically increase the score for the true pair and decrease the score for the handful of fake pairs. By optimizing against just 5 or 10 negative samples instead of 100 ,000 vocabulary words, it completely sidesteps the massive computational bottleneck while still effectively pushing the word vectors into their correct geometric alignment. So we have successfully mapped individual words into this beautiful continuous geometric space. But human comprehension isn't limited to isolated words or single sentences.
We read entire novels. The machine has to learn how to keep track of a narrative over time. This introduces us to chapters 15 and 16 on discourse and reference resolution. Coreference resolution is the classic test of multi -sentence comprehension. If a text reads, Abigail dropped the fragile glass. She was deeply upset because it shattered. The machine must deduce that the pronoun she refers back to Abigail and the pronoun it refers to the glass. As humans, we resolve those pronouns flawlessly and instinctively without even noticing we are doing it. But for a machine, the text string Abigail, the string she, and the string her are completely different data points. How does it learn to mathematically link them together into a single identity? Eisenstein explains a fascinating structural approach called the Bell Tree. This model frames corference resolution not as static labeling, but as a dynamic sequential decision -making process. As the algorithm reads through a document left to right, every time it encounters a new mention, a noun or a pronoun, it faces a structural choice. Does it link this new mention to an existing cluster of entities it has already built, or does it branch off and establish a brand new cluster? So when it encounters the word she, It evaluates the Abigail cluster, the Glass cluster, and an empty new entity cluster and makes a choice. But how do you train a model to make a long chain of choices? You cannot easily train that with standard supervised learning.
Instead, modern NLP relies on reinforcement learning, specifically techniques like policy gradients. The system is not evaluating isolated classification decisions. It is attempting to learn an overarching policy for navigating the bell tree. The model plays through the document. making a sequence of clustering decisions. If the final resulting clusters at the end of the document are highly accurate, the system receives a mathematical reward and the specific neural pathways that led to those correct decisions are strengthened. We are back to the board game analogy. The machine is playing a game of entity clustering, evaluating its moves, and optimizing its strategy to maximize its final score. Exactly. It learns a policy of comprehension through trial, error, and optimization.
So if we step back, And look at the whole picture for a moment in part four. We have covered how a computer reduces text to numerical frequencies, how it discovers hidden structures, how it navigates the viterity bracket to assign grammar, how it builds massive syntactic trees, how it forces words into geometric spaces, and how it resolves narrative identities. What do we actually do with all this theoretical machinery? What are the grand applications? This is where the science transitions into applied engineering. One of the most vital applications is information extraction.
The primary objective here is taking the unstructured, chaotic prose of the internet, medical journals or corporate archives, and distilling it into clean, highly structured relational databases. For example, turning a massive rambling Wikipedia article about a film into a crisp spreadsheet that explicitly lists the director, the lead actor, and the release year. To accomplish that, the NLP pipeline executes multiple discrete steps. First, it performs entity linking, ensuring that the text string Washington in the document explicitly maps to the database entry for George Washington the person, rather than Washington the state.
Next, it performs relation extraction, predicting the specific logical relationship connecting two entities within a sentence. And how does it train that? I recall the text mentioning pairwise ranking loss functions, but that terminology sounds incredibly opaque. How does the math actually work to extract a fact? A pairwise ranking loss function operates conceptually like a mathematical scale. Imagine the machine is evaluating the entities George Washington and Virginia. It must determine their relationship. The model evaluates the true relationship born in and assigns it a score. It then evaluates a false relationship, say, employed by, and assigns it a score. The loss function simply demands that the score for the true relationship must remain significantly heavier ranked higher than the score for the false relationship. Like tipping a scale. Yes.
By constantly adjusting its internal weights to keep the true facts heavier on the scale, the model learns to identify and extract verifiable relationships directly from unstructured prose. That is a phenomenal way to visualize it. Moving to another massive application in Chapter 18, we have machine translation. This has famously been the holy grail of artificial intelligence since the Cold War. It has driven massive amounts of funding and research for decades. Eisenstein roots the discussion of translation by examining IBM Model 1, a truly foundational statistical model. What makes this model so conceptually important is how it utilizes the expectation maximization algorithm we discussed earlier.
The soft probability dance. How does clustering apply to translation? Imagine you possess a massive corpus of parallel texts, like the Canadian Parliament transcripts, where you have the exact same speeches in English and French. You know that sentence A in English corresponds to sentence B in French. However, you do not possess a bilingual dictionary. You have no idea which specific English word aligns with which specific French word. It's the chicken and egg paradox again. If I have a dictionary, I can align the words perfectly. If I have the words aligned perfectly, I can build the dictionary. But I have neither. So IBM Model 1 executes the EM dance. In the E step, the model generates entirely random, terrible guesses regarding word alignments. It might guess that house translates to bonjour. In the M step, it uses those terrible alignments to estimate the actual mathematical translation probabilities across the entire corpus. Then it iterates. And it fixes itself over time. Yes. Without any human supervision or hard -coded dictionaries, the mathematics eventually converge on the undeniable statistical reality that the English word house and the French word maison co -occur in parallel sentences with overwhelming frequency. The alignment resolves itself purely through statistical maximization.
That is awe -inspiring. It just mathematically inevitably discovers the translation. Finally, the text pivots to the ultimate frontier in Chapter 19, text generation and dialogue. Everything so far has been about ingesting data. Now we are going from data back into natural language output. If parsing syntax is like taking a car engine apart to understand how it works, generation is attempting to build a functioning engine from a pile of spare parts. And dialogue systems represent the absolute apex of that complexity. Because in a dialogue system, you are not simply generating text into a static void. You are actively interacting with an unpredictable human being. To model this mathematically, engineers frame the conversation as a Markov decision process, or MDP. Another Markov process. We talked about the hidden Markov model earlier for tagging. But this is a Markov decision process. How does the math differ here?
In an MDP, the machine is not merely labeling text. It is an active agent. The system occupies a specific state. For instance, it understands the user wants to book a flight but does not know the destination. The machine must choose an action from its available repertoire. It can generate text asking for the destination city, or it can generate text prematurely asking for payment. And how does it know which text to generate? It calculates the path to maximize a mathematical reward. The ultimate reward is successfully completing the transaction booking the flight. The machine uses transition probabilities to model the unpredictable nature of human responses, and it uses discounting to weigh immediate rewards against long -term success. The text generation is not just stringing words together. It is the execution of a mathematically optimized policy. The machine is making sequential strategic decisions to navigate the chaotic environment of human conversation toward a successful resolution.
It is playing the board game to win. The Learner, we have covered a staggering amount of ground in this deep dive. We started by throwing classic novels into a blender to make basic numerical smoothies with a bag of words. We learned how to discover hidden structures using the expectation maximization dance. We watched the Viterbi algorithm navigate its bracket to assign grammar and the CKY algorithm build massive nested trees of syntax. We embedded words into geometric space using the game of 20 questions. And finally, we explored systems that can automatically translate languages and hold strategic, mathematically optimized conversations. It is a remarkable conceptual journey from discrete, isolated symbols through complex, continuous mathematics and ultimately back to the generation of meaningful human symbols.
But I want to leave you, the listener, with a final thought to ponder, derived from the core tension that permeates Eisenstein's entire text. Throughout this exploration, we constantly contrasted two opposing philosophies. On one side, we have the structured, rule -based approach of formal linguistics, like the pristine logic of the lambda calculus and the rigid geometry of syntax trees. On the other side, we have the sheer brute force predictive power of modern statistical deep learning, like the geometric spaces of Word2Vec and neural sequence labelers. That dichotomy remains the defining philosophical debate of modern natural language processing. So I ask you to ponder this.
As our neural networks become unimaginably massive, training on literally the entirety of the Internet's text, they are becoming increasingly opaque and uninterpretable. We cannot open up a trillion parameter model and read its hidden states the way we can cleanly read a binary syntax tree. Are these statistical networks actually getting closer to replicating true cognitive human comprehension? Or are we simply building an unimaginably complex, high -dimensional mathematical mirror of our own statistical patterns? Does true meaning ultimately require a logical rulebook? Or is meaning just an emergent property of seeing enough data? We started today by acknowledging that human language isn't a smooth curve, it's messy and discrete.
But maybe in the end, if you pour enough data into the machine, the muddy discrete waters of human language finally start to look continuous again.