--- title: Natural Language for AI Agents module: Frontiers moduleNumber: 6 lessonNumber: 5 order: 605 summary: > Language is how agents acquire the knowledge already written down and how they communicate with the humans they serve. This lesson gives the classical AI account of language as a source of information: n-gram language models and the information-seeking tasks built on them — text classification, information retrieval (BM25, the inverted index, PageRank), and information extraction with finite-state templates and hidden Markov models. Throughout, we point to the dedicated NLP subject for the modern deep-learning treatment; the companion lesson takes up grammar, translation, and speech. topics: [Frontiers] sources: - book: AIMA ref: "Ch. 22 — Natural Language Processing; §22.1 Language Models, §22.2 Text Classification, §22.3 Information Retrieval, §22.4 Information Extraction" --- Two facts drive a rational agent toward language. First, most of what humans know is written down: over a trillion pages on the web, almost all of it in natural language, so an agent that wants to **acquire knowledge** must read the ambiguous, messy prose people actually write.[^aima-intro] Second, an agent that acts on our behalf has to **communicate** — take instructions, ask questions, report results — and the shared system of signs we use for that is language. Chapter 22 of AIMA treats the first (language as a source of information); Chapter 23 treats the second (language as communication). This lesson gives that classical account in one pass. It is a _classical_ account on purpose. The models here are n-gram counts, context-free grammars, and hidden Markov models — the tools AI had before the deep-learning turn. They are worth knowing exactly because they name the problems cleanly: what a language model is, what parsing computes, why translation is a search. The modern treatment of every one of these tasks, with neural networks and transformers, lives in the dedicated [natural language processing](/natural-language-processing/foundations/what-is-nlp) subject; we link to the relevant lesson as each task comes up. ## Language models: predicting the next symbol A **formal language** like Python can be defined as a set of strings, generated by an exact grammar. Natural languages cannot be defined this way. Everyone agrees "Not to be invited is sad" is English, but grammaticality judgments blur at the edges, and the same string carries many meanings — "He saw her duck" is either a waterfowl or an act of evasion.[^aima-lm] So instead of a crisp membership test, a natural **language model** is a _probability distribution_ over strings: rather than asking whether a string is in the language, we ask $P(S = \text{words})$, how probable that sentence is. The simplest such model works over **characters**. Writing $P(c_{1:N})$ for the probability of a sequence of $N$ characters, an **n-gram model** assumes each character depends only on the $n-1$ before it — a Markov chain of order $n-1$. For a trigram model ($n = 3$), $$ P(c_i \mid c_{1:i-1}) = P(c_i \mid c_{i-2:i-1}), \qquad P(c_{1:N}) = \prod_{i=1}^{N} P(c_i \mid c_{i-2:i-1}). $$ The conditional table is estimated by counting: how often does each three-letter sequence appear in a **corpus** of text. The same machinery runs over **words** instead of characters; the only change is that the vocabulary jumps from ~100 symbols to tens of thousands, and we must reserve a symbol `` for words never seen in training. $$ % caption: An n-gram model factors the probability of a sequence into a product of % conditionals, each looking back a fixed window of $n-1$ symbols (a trigram, $n=3$, % shown). The Markov assumption is what makes the table finite. \begin{tikzpicture}[>=stealth, font=\small, tok/.style={draw, minimum width=11mm, minimum height=8mm, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[tok] (a) at (0,0) {the}; \node[tok] (b) at (1.7,0) {cat}; \node[tok, draw=acc, text=acc] (c) at (3.4,0) {sat}; \node[tok] (d) at (5.1,0) {on}; \node[tok] (e) at (6.8,0) {the}; % window arrows into c \draw[->, acc] (a.north) to[bend left=30] (c.north); \draw[->, acc] (b.north) to[bend left=25] (c.north); \node[acc, font=\scriptsize, anchor=south] at (1.7,1.15) {context window (n-1 = 2)}; \node[font=\scriptsize, anchor=north] at (3.4,-0.75) {predict P(sat given the, cat)}; \end{tikzpicture} $$ **What character models are good for.** One clean task is **language identification**: given a text, which of English, German, Spanish, ... is it? Build a trigram model $P(c_i \mid c_{i-2:i-1}, \ell)$ for each candidate language $\ell$, then apply Bayes' rule to pick the most probable language given the text, $$ \ell^\ast = \argmax_{\ell} P(\ell) \prod_{i=1}^{N} P(c_i \mid c_{i-2:i-1}, \ell). $$ Computer systems do this with greater than 99% accuracy. The same character-level approach handles spelling correction, genre classification, and named-entity recognition, because it can associate a substring like "ex " with drug names and generalize to words it has never seen. ### Smoothing The trouble with counting is that a corpus is only a _sample_ of the true distribution. Common sequences like " th" are well estimated (about 1.5% of English trigrams), but a legitimate sequence like " ht" (as in "http") may have count zero in the training text, and a zero count assigns $P = 0$ to any sentence containing it — clearly wrong. **Smoothing** reallocates a little probability mass to unseen sequences.[^aima-smooth] The oldest fix is Laplace (add-one) smoothing; it works poorly. A **backoff model** does better: estimate n-gram counts, but for any sequence with a low or zero count, back off to the $(n-1)$-gram. **Linear interpolation** blends the trigram, bigram, and unigram estimates, $$ \widehat{P}(c_i \mid c_{i-2:i-1}) = \lambda_3\,P(c_i \mid c_{i-2:i-1}) + \lambda_2\,P(c_i \mid c_{i-1}) + \lambda_1\,P(c_i), \qquad \lambda_3 + \lambda_2 + \lambda_1 = 1, $$ with the mixing weights $\lambda_i$ tuned on held-out data. A model is chosen by cross-validation and scored by **perplexity**, $\text{Perplexity}(c_{1:N}) = P(c_{1:N})^{-1/N}$, the weighted average branching factor: a lower perplexity is a better model. All of this — n-gram counts, smoothing, perplexity — is developed with worked numbers in the NLP subject's [n-gram language models](/natural-language-processing/foundations/n-gram-language-models) lesson. ### A bigram model on a toy corpus For example, take a three-sentence corpus, each sentence wrapped in a start marker `` and an end marker `` so the model can score where a sentence begins and ends: ``` the cat sat the cat ran the dog sat ``` A **bigram** word model estimates $P(w_i \mid w_{i-1})$ by the maximum-likelihood count ratio $C(w_{i-1}\,w_i) / C(w_{i-1})$. Tallying adjacent pairs gives the counts below; the context word $w_{i-1}$ runs down the left, the predicted word $w_i$ across the top. | $C(w_{i-1}, w_i)$ | the | cat | dog | sat | ran | `` | row total $C(w_{i-1})$ | | --- | --- | --- | --- | --- | --- | --- | --- | | `` | 3 | 0 | 0 | 0 | 0 | 0 | 3 | | the | 0 | 2 | 1 | 0 | 0 | 0 | 3 | | cat | 0 | 0 | 0 | 1 | 1 | 0 | 2 | | dog | 0 | 0 | 0 | 1 | 0 | 0 | 1 | | sat | 0 | 0 | 0 | 0 | 0 | 2 | 2 | | ran | 0 | 0 | 0 | 0 | 0 | 1 | 1 | Dividing each row by its total gives the conditional table: $P(\text{cat} \mid \text{the}) = 2/3$, $P(\text{dog} \mid \text{the}) = 1/3$, $P(\text{sat} \mid \text{cat}) = 1/2$, $P(\text{ran} \mid \text{cat}) = 1/2$, and the deterministic $P(\text{the} \mid \texttt{}) = 1$, $P(\text{sat} \mid \text{dog}) = 1$. Now score the held-out sentence ` the cat sat ` as a product of conditionals: $$ P(\text{the cat sat}) = \underbrace{1}_{\texttt{} \to \text{the}} \cdot \underbrace{\tfrac{2}{3}}_{\text{the} \to \text{cat}} \cdot \underbrace{\tfrac{1}{2}}_{\text{cat} \to \text{sat}} \cdot \underbrace{1}_{\text{sat} \to \texttt{}} = \frac{1}{3} \approx 0.333. $$ The sentence has $N = 4$ transitions, so its **perplexity** is $P^{-1/N} = (1/3)^{-1/4} = 3^{1/4} \approx 1.316$ — a model this confident on this sentence branches, on average, as if choosing among only ~1.3 words at each step. ### Where a zero count kills the sentence, and interpolation rescues it Now score a different held-out sentence, ` the dog ran `. Every word is in the vocabulary, yet the bigram _dog ran_ never occurred in training, so $C(\text{dog}, \text{ran}) = 0$ and $$ P(\text{the dog ran}) = 1 \cdot \tfrac{1}{3} \cdot \underbrace{0}_{\text{dog} \to \text{ran}} \cdot 1 = 0. $$ A single unseen bigram sets the whole product to zero and the perplexity to infinity — the model assigns zero probability to a reasonable sentence. **Linear interpolation** repairs this by blending the bigram estimate with a unigram estimate that _is_ nonzero. With $\lambda_2 = 0.7$ for the bigram and $\lambda_1 = 0.3$ for the unigram (weights summing to 1), and the unigram $P(\text{ran}) = C(\text{ran})/\!\sum C = 1/9 \approx 0.111$ over the 9 word tokens in the corpus, $$ \widehat{P}(\text{ran} \mid \text{dog}) = \lambda_2\,\underbrace{P(\text{ran} \mid \text{dog})}_{0} + \lambda_1\,\underbrace{P(\text{ran})}_{1/9} = 0.7 \cdot 0 + 0.3 \cdot \tfrac{1}{9} \approx 0.0333, $$ which is small but positive, so the sentence probability is nonzero and its perplexity is finite. The mixing weight $\lambda_1$ guarantees that any in-vocabulary word keeps a floor of probability even when its bigram was never seen. $$ % caption: Linear interpolation as a mixture. The bigram estimate P(ran given dog) % is zero (unseen), but the unigram P(ran) is positive; the weighted blend % lambda_2 * bigram + lambda_1 * unigram lands at a small nonzero value, so the % sentence probability escapes zero. \begin{tikzpicture}[>=stealth, font=\small, box/.style={draw, minimum width=30mm, minimum height=9mm, font=\footnotesize, align=center}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \node[box, draw=red, text=red] (bi) at (0,1.1) {bigram P(ran given dog)\\= 0 (unseen)}; \node[box, draw=acc, text=acc] (uni) at (0,-1.1) {unigram P(ran)\\= 1/9 = 0.111}; \node[box] (mix) at (5.6,0) {blend\\0.7(0) + 0.3(0.111)\\= 0.0333}; \draw[->, red] (bi.east) to[out=0,in=140] (mix.north west); \draw[->, acc] (uni.east) to[out=0,in=220] (mix.south west); \node[font=\scriptsize, anchor=west] at (8.4,0) {nonzero: sentence survives}; \draw[->, black] (7.7,0) -- (8.35,0); \end{tikzpicture} $$ ## Text classification The first information-seeking task is **text classification** (also categorization): given a document, assign it to one of a fixed set of classes.[^aima-tc] Language identification was an instance; so is **spam detection**, where the classes are spam and ham (not-spam), and **sentiment analysis**, where a review is positive or negative. Spam detection is a supervised problem with a training set ready to hand: the spam folder supplies positive examples, the inbox supplies negative ones. There are two complementary ways to frame it. In the **language-modeling** view, train one n-gram model $\mathbf{P}(\text{message} \mid \text{spam})$ on the spam folder and another $\mathbf{P}(\text{message} \mid \text{ham})$ on the inbox, then classify by Bayes' rule, $$ \argmax_{c \in \{\text{spam}, \text{ham}\}} P(c \mid \text{message}) = \argmax_{c \in \{\text{spam}, \text{ham}\}} P(\text{message} \mid c)\, P(c), $$ with the priors $P(c)$ estimated by counting messages of each class. In the **machine-learning** view, represent the message as a feature vector and apply any classifier. The simplest representation is **bag of words**: features are the vocabulary words, values are their counts, and word order is discarded. Add the assumption that the features are conditionally independent given the class, and this becomes the naive Bayes model. $$ % caption: Naive Bayes for spam. Each word is a feature that depends only on the % class; the class prior times the per-word likelihoods gives the posterior, and we % pick the larger. The independence assumption is the "naive" part. \begin{tikzpicture}[>=stealth, font=\small, cls/.style={circle, draw=acc, text=acc, thick, minimum size=10mm}, wd/.style={draw, minimum width=13mm, minimum height=7mm, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[cls] (c) at (0,1.6) {class}; \node[wd] (w1) at (-3,-0.4) {free}; \node[wd] (w2) at (-1,-0.4) {money}; \node[wd] (w3) at (1,-0.4) {meeting}; \node[wd] (w4) at (3,-0.4) {report}; \draw[->, acc] (c) -- (w1); \draw[->, acc] (c) -- (w2); \draw[->, acc] (c) -- (w3); \draw[->, acc] (c) -- (w4); \node[font=\scriptsize, anchor=north] at (0,-1.1) {each word depends on the class, not on other words}; \end{tikzpicture} $$ ### Classifying one message by hand For example, suppose a training set of $10$ spam messages and $10$ ham messages gives the per-class word counts below, over a four-word vocabulary. $N_c$ is the total number of word tokens in class $c$; the maximum-likelihood likelihood of a word is $P(w \mid c) = C(w, c) / N_c$. To keep any unseen word from zeroing the product, add-one (Laplace) smoothing uses $P(w \mid c) = (C(w, c) + 1) / (N_c + |V|)$ with vocabulary size $|V| = 4$. | word | count in spam | count in ham | $P(w \mid \text{spam})$ | $P(w \mid \text{ham})$ | | --- | --- | --- | --- | --- | | free | 8 | 1 | $(8{+}1)/(20{+}4) = 9/24$ | $(1{+}1)/(20{+}4) = 2/24$ | | money | 6 | 2 | $7/24$ | $3/24$ | | meeting | 1 | 7 | $2/24$ | $8/24$ | | report | 5 | 10 | $6/24$ | $11/24$ | | total $N_c$ | 20 | 20 | | | The priors are $P(\text{spam}) = P(\text{ham}) = 10/20 = 0.5$. Classify the new message **"free money meeting"** by comparing the posteriors up to the shared normalizer, i.e. comparing $P(c)\prod_i P(w_i \mid c)$ for each class: $$ \begin{aligned} P(\text{spam})\,\textstyle\prod_i P(w_i \mid \text{spam}) &= 0.5 \cdot \tfrac{9}{24} \cdot \tfrac{7}{24} \cdot \tfrac{2}{24} = 0.5 \cdot 0.375 \cdot 0.2917 \cdot 0.0833 \approx 4.56 \times 10^{-3}, \\ P(\text{ham})\,\textstyle\prod_i P(w_i \mid \text{ham}) &= 0.5 \cdot \tfrac{2}{24} \cdot \tfrac{3}{24} \cdot \tfrac{8}{24} = 0.5 \cdot 0.0833 \cdot 0.125 \cdot 0.3333 \approx 1.74 \times 10^{-3}. \end{aligned} $$ Spam wins, $4.56 \times 10^{-3}$ against $1.74 \times 10^{-3}$. Normalizing gives a posterior $P(\text{spam} \mid \text{message}) = 4.56/(4.56 + 1.74) \approx 0.72$. The verdict tracks intuition: "free" and "money" pull hard toward spam, and "meeting" pulls toward ham, but not hard enough to overturn the other two. Notice that a single strongly-skewed word — had "meeting" appeared $0$ times in spam without smoothing — would have driven the spam score to exactly $0$ and forced a ham verdict on the strength of one absent word; the add-one floor is what keeps the decision to the _product_ of evidence rather than its weakest link. Feature choice matters more than the choice of algorithm: with enough training data, a good feature (a suspicious bigram, whether the message contains a URL, the sender's history) determines accuracy more than whether one runs naive Bayes, logistic regression, an SVM, or $k$-nearest-neighbors — all of which reach the 98–99% range on spam, and above 99.9% with a careful feature set. Because spam is an **adversarial task** — spammers rewrite "you deserve" as "yo,u d-eserve" to dodge the filter — features must be updated continually. The naive Bayes classifier and its use in sentiment analysis are worked through in the NLP subject's [naive Bayes and sentiment](/natural-language-processing/classification/naive-bayes-and-sentiment) lesson. ## Information retrieval **Information retrieval** (IR) is the task of finding documents relevant to a user's information need — the job of a web search engine.[^aima-ir] An IR system has four parts: a **corpus** of documents, **queries** in some query language, a **result set** of documents judged relevant, and a **presentation** of that set, usually a ranked list. The earliest systems used a **Boolean keyword model**: each word is a Boolean feature, and a query like `[information AND retrieval]` returns exactly the documents where the expression is true. This is simple but crude — relevance is a single bit, so there is no way to rank, and Boolean queries are unintuitive for ordinary users. Modern systems abandon it for scoring functions over word counts. ### Scoring: TF-IDF and BM25 A **scoring function** takes a document and a query and returns a number; the highest-scoring documents rank first. Three factors set the weight of a query term: - **Term frequency** $TF(q_i, d_j)$ — how often term $q_i$ appears in document $d_j$. A document that mentions "farming" often is more about farming. - **Inverse document frequency** $IDF(q_i)$ — terms that appear in almost every document (like "in") are uninformative and should count for little. - **Document length** — a very long document mentions everything; a short document that mentions all the query words is a better match. The **BM25** function, from the Okapi project and used in Lucene, combines all three: $$ BM25(d_j, q_{1:N}) = \sum_{i=1}^{N} IDF(q_i) \cdot \frac{TF(q_i, d_j)\,(k+1)}{TF(q_i, d_j) + k \cdot \left(1 - b + b \cdot \dfrac{|d_j|}{L}\right)}, \qquad IDF(q_i) = \log \frac{N - DF(q_i) + 0.5}{DF(q_i) + 0.5}, $$ where $|d_j|$ is the document length, $L$ the average length, $DF(q_i)$ the number of documents containing $q_i$, and $k \approx 2.0$, $b \approx 0.75$ are tuned constants. To avoid scoring every document, systems build an **index** ahead of time — for each vocabulary word, the **hit list** of documents that contain it — and only score documents in the intersection of the query words' hit lists. $$ % caption: An inverted index maps each term to its hit list of documents. A query % intersects the hit lists of its terms, and only the surviving documents are scored % by BM25 and ranked. \begin{tikzpicture}[>=stealth, font=\small, term/.style={draw=acc, text=acc, minimum width=20mm, minimum height=7mm, font=\footnotesize}, post/.style={draw, minimum width=42mm, minimum height=7mm, font=\footnotesize}, res/.style={draw, minimum width=20mm, minimum height=7mm, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[term] (t1) at (0,1) {farming}; \node[term] (t2) at (0,0) {Kansas}; \node[post] (p1) at (3.6,1) {d2, d5, d7, d9}; \node[post] (p2) at (3.6,0) {d1, d5, d9}; \draw[->, acc] (t1) -- (p1); \draw[->, acc] (t2) -- (p2); \node[res] (r) at (8.4,0.5) {score d5, d9}; \draw[->, black] (6.05,1) to[out=0,in=150] (r.north west); \draw[->, black] (5.35,0) to[out=0,in=210] (r.south west); \node[font=\scriptsize, anchor=south] at (8.4,1.05) {intersect, then rank}; \end{tikzpicture} $$ The intersection is what makes the index efficient. If the hit lists are stored sorted by document id, intersecting two lists of lengths $\ell_1$ and $\ell_2$ is a merge: walk two pointers forward, advancing whichever points to the smaller id, and emit a document only when both pointers agree. That is $O(\ell_1 + \ell_2)$ time, not the $O(\ell_1 \cdot \ell_2)$ of comparing every pair, and for a rare-plus-common term combination one can do better still by _galloping_ the short list's members through the long list with binary search, at $O(\ell_1 \log \ell_2)$. Either way the scorer touches only documents that contain _every_ query word, so a two-word query against a billion-document web scores a few thousand candidates rather than a billion. ### BM25 on two toy documents Rank two short documents against the single-word query `[farming]`. Suppose the corpus has $N = 10$ documents, the average length is $L = 12$ words, and "farming" appears in $DF = 2$ of them. The two candidates: - $d_1$: "farming in Kansas grows corn" — length $|d_1| = 5$, and "farming" occurs $TF_1 = 1$ time. - $d_2$: a $20$-word paragraph that mentions "farming" $TF_2 = 3$ times. First the shared inverse document frequency, with the BM25 smoothing offsets: $$ IDF(\text{farming}) = \log \frac{N - DF + 0.5}{DF + 0.5} = \log \frac{10 - 2 + 0.5}{2 + 0.5} = \log \frac{8.5}{2.5} = \log 3.4 \approx 1.224. $$ Now the term-frequency factor with $k = 2$, $b = 0.75$. The length-normalization term is $K(d) = k\,(1 - b + b \cdot |d|/L)$. For $d_1$, $|d_1|/L = 5/12 = 0.417$, so $K(d_1) = 2\,(0.25 + 0.75 \cdot 0.417) = 2\,(0.25 + 0.3125) = 1.125$, and $$ BM25(d_1) = IDF \cdot \frac{TF_1\,(k+1)}{TF_1 + K(d_1)} = 1.224 \cdot \frac{1 \cdot 3}{1 + 1.125} = 1.224 \cdot \frac{3}{2.125} \approx 1.728. $$ For $d_2$, $|d_2|/L = 20/12 = 1.667$, so $K(d_2) = 2\,(0.25 + 0.75 \cdot 1.667) = 2\,(0.25 + 1.25) = 3.0$, and $$ BM25(d_2) = 1.224 \cdot \frac{3 \cdot 3}{3 + 3.0} = 1.224 \cdot \frac{9}{6} \approx 1.836. $$ So $d_2$ ranks first, $1.836$ to $1.728$ — its three mentions outweigh $d_1$'s single mention even after $d_2$ is penalized for being longer than average. The penalty is real, though: had length normalization been switched off ($b = 0$), $d_2$ would score $1.224 \cdot 3(3)/(3+2) = 2.203$ and $d_1$ would score $1.224 \cdot 3/(1+2) = 1.224$, a much wider gap. Length normalization is precisely the $b$ term pulling the long document back toward the short, focused one. ### Evaluation: precision and recall How well is an IR system doing? Run it on a set of queries whose relevant documents are known, and count the four cells of the outcome table. | | In result set | Not in result set | | --- | --- | --- | | Relevant | 30 | 20 | | Not relevant | 10 | 40 | **Precision** is the fraction of returned documents that are actually relevant, here $P = 30 / (30 + 10) = 0.75$. **Recall** is the fraction of all relevant documents that were returned, here $R = 30 / (30 + 20) = 0.60$. On the web, recall is impractical to measure (no one can examine every page), so search engines report precision-at-$k$ such as `P@10`. The two trade off — returning everything gives recall $1$ but low precision — and the **F1 score**, the harmonic mean $2PR / (P + R)$, summarizes both in one number. For this table, $$ F_1 = \frac{2PR}{P + R} = \frac{2 \cdot 0.75 \cdot 0.60}{0.75 + 0.60} = \frac{0.90}{1.35} \approx 0.667, $$ closer to the smaller of the two (recall $0.60$) than the arithmetic mean $0.675$ would be — the harmonic mean penalizes a large gap between precision and recall, so a system cannot get a high F1 by sacrificing one for the other. ### Link analysis: PageRank Counting words is not enough on the web, because the highest-$TF$ page for "IBM" need not be IBM's home page. **PageRank** adds a signal from the link graph: a page is important if many important pages link to it.[^aima-pr] Each in-link is a vote, weighted by the voter's own rank, which makes the definition recursive but convergent: $$ PR(p) = \frac{1 - d}{N} + d \sum_{i} \frac{PR(\text{in}_i)}{C(\text{in}_i)}, $$ where $\text{in}_i$ are the pages linking to $p$, $C(\text{in}_i)$ is the number of out-links on page $\text{in}_i$, $N$ is the corpus size, and $d \approx 0.85$ is a damping factor. It has an interpretation as the **random surfer model**: with probability $d$ a surfer follows a random link, and with probability $1 - d$ jumps to a random page; $PR(p)$ is the long-run fraction of time spent at $p$. PageRank is computed by iterating the equation to a fixed point. **Two iterations on a three-node web.** Take the link graph $A \to B$, $A \to C$, $B \to C$, $C \to A$. Here $N = 3$, $d = 0.85$, so the teleport term is $(1-d)/N = 0.15/3 = 0.05$. The out-degrees are $C(A) = 2$, $C(B) = 1$, $C(C) = 1$. Start from the uniform vector $PR = (\tfrac13, \tfrac13, \tfrac13) \approx (0.333, 0.333, 0.333)$ and apply the update. $A$ is linked from $C$ only; $B$ from $A$ only; $C$ from $A$ and $B$: $$ \begin{aligned} PR(A) &= 0.05 + 0.85 \cdot \frac{PR(C)}{1}, \\ PR(B) &= 0.05 + 0.85 \cdot \frac{PR(A)}{2}, \\ PR(C) &= 0.05 + 0.85 \cdot \left(\frac{PR(A)}{2} + \frac{PR(B)}{1}\right). \end{aligned} $$ Iteration 1, plugging the uniform start ($0.333$) into every right-hand term: $$ PR(A) = 0.05 + 0.85(0.333) = 0.333, \quad PR(B) = 0.05 + 0.85\tfrac{0.333}{2} = 0.192, \quad PR(C) = 0.05 + 0.85(0.167 + 0.333) = 0.475. $$ Iteration 2, feeding those values back in: $$ PR(A) = 0.05 + 0.85(0.475) = 0.454, \quad PR(B) = 0.05 + 0.85\tfrac{0.333}{2} = 0.192, \quad PR(C) = 0.05 + 0.85(0.227 + 0.192) = 0.406. $$ The ordering has already settled on $A$ and $C$ near the top with $B$ trailing, and further iterations converge toward the stationary distribution (about $A = 0.39$, $B = 0.20$, $C = 0.41$). $C$ scores high because both other pages link to it; $A$ recovers because the one page that links to it, $C$, is itself important — the recursion at work. $$ % caption: A three-node link graph for PageRank. Arrows are hyperlinks; each page % splits its rank equally among its out-links. After two iterations from a uniform % start (d = 0.85), C and A lead and B trails, matching PR(A) = 0.454, PR(B) = 0.192, % PR(C) = 0.406. \begin{tikzpicture}[>=stealth, font=\small, pg/.style={circle, draw=acc, text=acc, thick, minimum size=13mm, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[pg] (A) at (0,0) {A}; \node[pg] (B) at (3.4,1.4) {B}; \node[pg] (C) at (3.4,-1.4) {C}; \draw[->, acc] (A) -- (B); \draw[->, acc] (A) -- (C); \draw[->, acc] (B) -- (C); \draw[->, acc] (C) to[bend left=25] (A); \node[font=\scriptsize, anchor=east] at (-0.5,0) {PR = 0.454}; \node[font=\scriptsize, anchor=west] at (4.0,1.4) {PR = 0.192}; \node[font=\scriptsize, anchor=west] at (4.0,-1.4) {PR = 0.406}; \end{tikzpicture} $$ The related HITS algorithm splits importance into hubs and authorities. When the query is a question and the desired output is a short answer rather than a ranked list, the task becomes **question answering**, covered in the NLP subject's [question answering](/natural-language-processing/applications/question-answering) lesson. ## Information extraction **Information extraction** (IE) skims text for instances of a class of object and the relations among them — pulling structured records out of prose.[^aima-ie] A typical task is to read "IBM ThinkBook 970. Our price: $399.00" and produce the attributes {Manufacturer = IBM, Model = ThinkBook970, Price = 399.00}. AIMA presents six approaches spanning deterministic to stochastic; two matter most. ### Finite-state extraction The simplest system is **attribute-based**: assume the whole text describes one object and pull out its attributes with a **template** — a **regular expression** per attribute. A price template pairs a target regex for a dollar amount with a prefix regex looking for "price:" nearby, on the idea that some clues come from the value itself and some from the surrounding text. $$ % caption: A finite-state template for prices: a prefix pattern locates the field, % the target pattern captures the value. Each box is a regex fragment; matching % left-to-right pulls the value out of running text. \begin{tikzpicture}[>=stealth, font=\small, st/.style={draw, minimum width=26mm, minimum height=8mm, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} \node[st] (pre) at (0,0) {pre-pattern: price:}; \node[st, draw=acc, text=acc] (tar) at (3.6,0) {target: [0-9]+.[0-9][0-9]}; \node[st] (post) at (7.6,0) {post-pattern: none}; \draw[->, acc] (pre) -- (tar); \draw[->, acc] (tar) -- (post); \node[font=\scriptsize, anchor=north] at (3.8,-0.75) {captures 399.00 from "Our price: 399.00"}; \end{tikzpicture} $$ **Relational** extraction goes one step up, recovering multiple objects and their relations. The FASTUS system reads corporate-merger news through **cascaded finite-state transducers**: a chain of small automata, each transducing the text into a richer format and passing it on. Its five stages are tokenization, complex-word handling, basic-group handling (chunking noun and verb groups), complex-phrase handling, and structure merging. Running the sentence "Bridgestone Sports Co. said Friday it has set up a joint venture ..." through the chunker yields a tagged sequence: ``` 1 NG: Bridgestone Sports Co. 7 PR: in 2 VG: said 8 NG: Taiwan 3 NG: Friday 9 PR: with 4 NG: it 10 NG: a local concern 5 VG: had set up 11 CJ: and 6 NG: a joint venture 12 NG: a Japanese trading house ``` where NG is a noun group, VG a verb group, PR a preposition, and CJ a conjunction. Later stages combine these into a `JointVenture` record. Finite-state IE works well on restricted, regularly formatted domains — especially reverse-engineering text a program generated — and poorly on free human prose. ### Probabilistic extraction with HMMs When the input is noisy or varied, getting every rule and its priority right is hopeless, and a probabilistic model does better. The simplest is the **hidden Markov model** (HMM), the same temporal model used for [reasoning over time](/artificial-intelligence/uncertainty/reasoning-over-time). For extraction, the observations are the words of the text and the hidden states label whether each word is in the **target**, **prefix**, or **postfix** part of an attribute, or in the **background**. Running Viterbi finds the most probable labeling. $$ % caption: An HMM tags each word with a hidden role. Trained on talk announcements, % it labels "Andrew McCallum" as the speaker's name; PRE and POST are the context % words around the target, and dash is background. \begin{tikzpicture}[>=stealth, font=\small, wd/.style={font=\footnotesize}, tg/.style={draw=acc, text=acc, minimum width=15mm, minimum height=6mm, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[wd] (w1) at (0,0) {seminar}; \node[wd] (w2) at (1.9,0) {by}; \node[wd] (w3) at (3.4,0) {Andrew}; \node[wd] (w4) at (5.4,0) {McCallum}; \node[wd] (w5) at (7.5,0) {on}; \node[tg] (t1) at (0,-1) {-}; \node[tg] (t2) at (1.9,-1) {PRE}; \node[tg] (t3) at (3.4,-1) {TARGET}; \node[tg] (t4) at (5.4,-1) {TARGET}; \node[tg] (t5) at (7.5,-1) {POST}; \foreach \i in {1,...,5} \draw[->, black] (w\i) -- (t\i); \draw[->, acc] (t1) -- (t2); \draw[->, acc] (t2) -- (t3); \draw[->, acc] (t3) -- (t4); \draw[->, acc] (t4) -- (t5); \end{tikzpicture} $$ HMMs beat finite-state templates on two counts: they are probabilistic, so a missing word degrades the match gracefully instead of failing outright, and their parameters can be learned from a corpus rather than hand-coded. Modern IE frames the same task as sequence labeling over semantic roles — the NLP subject's [semantic roles and information extraction](/natural-language-processing/linguistic-structure/semantic-roles-and-information-extraction) lesson carries it forward with neural taggers. The tasks so far — classification, retrieval, extraction — treat text as a bag or a sequence of symbols and ask what it is _about_. None of them look at how the words are _arranged_: that "black dog" is well-formed English while "dog black" is not, because grammar is about structure, not adjacency. Capturing that structure, and using it to parse, translate, and transcribe, is the second half of the classical account. This continues in [Language for AI Agents: Grammar, Translation, and Speech](/artificial-intelligence/frontiers/nlp-grammar-translation-and-speech). [^aima-intro]: **AIMA**, Ch. 22 — Natural Language Processing, chapter introduction: the two motivations for language processing (communication with humans and knowledge acquisition from written text) and the role of language models across information-seeking tasks. [^aima-lm]: **AIMA**, §22.1 — Language Models: natural languages defined as probability distributions over strings rather than definitive sets, and the n-gram (Markov chain of order $n-1$) character and word models. [^aima-smooth]: **AIMA**, §22.1.2–22.1.3 — Smoothing and Model Evaluation: Laplace smoothing, backoff and linear-interpolation models, and perplexity as a task-independent measure of model quality. [^aima-tc]: **AIMA**, §22.2 — Text Classification: spam detection and sentiment as supervised classification, the language-modeling versus machine-learning (bag-of-words / naive Bayes) framings, feature selection, and the adversarial nature of spam. [^aima-ir]: **AIMA**, §22.3 — Information Retrieval: the IR problem's four components, the Boolean keyword model, the BM25 scoring function with TF, IDF, and length normalization, the inverted index, and precision/recall/F1 evaluation. [^aima-pr]: **AIMA**, §22.3.4 — The PageRank algorithm: link analysis, the recursive PageRank equation, the damping factor, and the random-surfer interpretation; the HITS hubs-and-authorities variant. [^aima-ie]: **AIMA**, §22.4 — Information Extraction: attribute-based and relational extraction with finite-state templates and cascaded transducers (FASTUS), and probabilistic extraction with hidden Markov models over target/prefix/postfix/background states.