Natural Language for AI Agents

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.¹ 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 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.² 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$),

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 <UNK> for words never seen in training.

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,

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.³ 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,

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 lesson.

A bigram model on a toy corpus

For example, take a three-sentence corpus, each sentence wrapped in a start marker <s> and an end marker </s> so the model can score where a sentence begins and ends:

<s> the cat sat </s><s> the cat ran </s><s> the dog sat </s>

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.

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 \text{<s>})=1$, $P(\text{sat}\mid \text{dog})=1$. Now score the held-out sentence <s> the cat sat </s> as a product of conditionals:

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, <s> the dog ran </s>. Every word is in the vocabulary, yet the bigram dog ran never occurred in training, so $C(\text{dog},\text{ran})=0$ and

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,

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.

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.⁴ 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,

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.

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$.

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:

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 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.⁵ 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:

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.

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 $T{F}_1=1$ time.
• $d_2$: a $20$-word paragraph that mentions farming $T{F}_2=3$ times.

First the shared inverse document frequency, with the BM25 smoothing offsets:

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

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

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.

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,

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.⁶ Each in-link is a vote, weighted by the voter's own rank, which makes the definition recursive but convergent:

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=(\frac{1}{3},\frac{1}{3},\frac{1}{3})\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$:

Iteration 1, plugging the uniform start ($0.333$) into every right-hand term:

Iteration 2, feeding those values back in:

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.

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 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.⁷ 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.

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: in2  VG: said                      8  NG: Taiwan3  NG: Friday                    9  PR: with4  NG: it                       10  NG: a local concern5  VG: had set up               11  CJ: and6  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. 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.

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 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.