Dialogue and Chatbots

Conversation is the first kind of language a child learns and the kind adults use most: ordering lunch, booking a flight, arguing about the weather. For a machine it is one of the hardest interfaces to build. A dialogue system — a conversational agent — communicates with a person in natural language, and the field splits its programs into two kinds by what they are trying to do.¹ Task-oriented agents use conversation to complete something: the assistants in Siri, Alexa, and Google Assistant that set alarms, find restaurants, and book flights. Chatbots are built for the open-ended talk itself — mimicking the unstructured chat of informal human interaction, mostly for entertainment but also to make task agents feel less mechanical. The two goals require different machinery; the modern LLM assistant collapses the split.

Building either kind of system requires understanding what is being imitated. Human conversation is a joint activity with more structure than it appears to have, and every property of it is a design constraint on the machine.

Properties of human conversation

Consider a fragment of an actual phone call between a human travel agent (A) and a human client (C), the running example throughout Jurafsky and Martin's treatment:²

C₁: … I need to travel in May.
A₂: And, what day in May did you want to travel?
C₃: OK, uh, I need to be there for a meeting that's from the 12th to the 15th.
A₄: And you're flying into what city?
C₅: Seattle.
A₆: And what time would you like to leave Pittsburgh?

Every feature of this ordinary exchange is a problem for a machine. Four properties matter most.

Turns and turn-taking

A dialogue is a sequence of turns — C₁, A₂, C₃, and so on — each a single contribution from one speaker. A turn can be a word (Seattle) or several sentences. The timing is precise: speakers hand the floor back and forth with almost no gap and almost no overlap, because a listener can predict when the current speaker is about to finish.

For a spoken system this predictive handoff becomes two hard problems. The machine must know when to stop talking — the user may interrupt, or begin a correction mid-sentence — and it must know when to start, detecting that the user has finished so it can process and reply. That second problem, endpointing or endpoint detection, is genuinely difficult: people pause in the middle of turns, and background noise blurs the boundary between a pause and an ending.²

Speech acts

The central observation, due originally to Wittgenstein and worked out by Austin, is that each utterance in a dialogue is an action performed by the speaker — a speech act (or dialogue act). One common taxonomy has four classes:

A user asking a machine to do something (Turn up the music) issues a directive; a question that expects an answer (A₂) is also a directive, a very polite command to answer. Stating a constraint (C₁) is a constative. The speech act names the intention behind the words, and recovering it — not just the surface string — is what a dialogue system must do.

Grounding

A dialogue is not a stack of independent speech acts but a collective act, and partners in a collective act must keep track of what they mutually agree on, the common ground. They build it by grounding: acknowledging that the hearer has understood the speaker, the conversational equivalent of an ACK confirming receipt on a data channel.²

Humans ground constantly. A₆ (And what time would you like to leave Pittsburgh?) repeats Pittsburgh to show it was heard; the And that opens so many of the agent's turns signals that the new question is in addition to the last, implying the previous answer was understood. A dialogue system that never grounds — that answers questions without any signal of understanding — feels broken even when it is technically correct, which is why the choice between explicit and implicit confirmation, later in this lesson, matters.

Dialogue structure: adjacency pairs

Conversation has local structure. Certain speech acts set up an expectation for a particular next act: a QUESTION sets up an expectation for an ANSWER, a PROPOSAL for an ACCEPTANCE or REJECTION, a COMPLIMENT for a DOWNPLAYER. These two-part templates are adjacency pairs, a first pair part raising the expectation and a second pair part satisfying it.³ The expectations help a system decide what to do: after it asks a question, the next user turn is supposed to be an answer.

The two halves need not be adjacent. A side sequence — a subdialogue — can open between them; the common case is a clarification question when the machine mis-hears part of the user's turn.

These properties — turns, speech acts, grounding, dialogue structure, and the inferences a speaker expects the hearer to draw — are what make natural conversation hard to build, and most of them are still open research problems. The two traditions below each attack a different subset.

Chatbots

The simplest dialogue systems are chatbots: systems that carry on extended conversations meant to mimic the unstructured chat of informal human interaction. Their goals are entertainment and engagement rather than task completion, and their architectures fall into two classes — rule-based systems, the early influential ELIZA and PARRY, and corpus-based systems, which mine large datasets of human-human conversation.⁴

The rule-based tradition: ELIZA

ELIZA, written by Joseph Weizenbaum in 1966, is the most important chatbot in the history of the field, and it works by nothing more than pattern matching.⁵ It simulates a Rogerian psychologist — a style of therapy in which the therapist reflects the patient's statements back as questions, and can, as Weizenbaum noted, assume the pose of knowing almost nothing of the real world. That pose lets a machine with no world model sustain a conversation.

ELIZA is built from pattern/transform rules, the same regular-expression machinery introduced at the start of the course. A rule pairs a pattern with a transform:

(0 YOU 0 ME)                       [pattern]->(WHAT MAKES YOU THINK I 3 YOU)     [transform]

Here 0 is a Kleene star (match anything) and the digits in the transform index the matched constituents, so 3 refers to the material captured by the second 0. The rule turns You hate me into WHAT MAKES YOU THINK I HATE YOU. Each rule is attached to a keyword that might appear in the user's sentence, and keywords carry a rank: specific words (everybody) outrank general ones (I), because someone using a universal like everybody is usually referring to something quite specific worth probing. The algorithm finds the highest-ranked keyword in the input and fires its best-matching rule; if nothing matches, it falls back to a non-committal PLEASE GO ON or THAT'S VERY INTERESTING. One trick gives the illusion of memory: whenever my is the top keyword, ELIZA stores a transform of the sentence on a queue and, later, if nothing else matches, returns the oldest stored entry — so it seems to circle back to something the user said turns ago.

ELIZA understands nothing, yet it fooled people — the enduring lesson.⁵ Users confided in it, Weizenbaum's own secretary asked him to leave the room while she talked to it, and some kept believing it understood them after being shown the rules. A few years later PARRY added a model of mental state — affect variables for fear and anger — and became the first program to pass a Turing test, when psychiatrists could not distinguish its transcripts from those of real patients. ELIZA's pattern/action framework survives today in tools like ALICE, and it is the baseline for everything that follows.

Corpus-based chatbots

Instead of hand-built rules, corpus-based chatbots mine conversations — hundreds of millions or billions of words of them.⁶ Sources include transcribed telephone speech (the Switchboard corpus), movie dialogue, and crowdsourced conversation sets, supplemented by pseudo-conversations scraped from Twitter, Reddit, and Weibo. Given the user's turn in context, these systems produce a response in one of two ways.

Response by retrieval treats the user's turn as a query $q$ and returns the most appropriate turn $r$ from a corpus $C$ of conversations, scoring each candidate by similarity and picking the best. The classic form uses tf-idf cosine; the neural form is a bi-encoder, two separately trained encoders — one for the query, one for the candidate — whose dot product is the score, the same dense-retrieval idea question answering uses:

Response by generation instead casts response production as an encoder-decoder task — transducing the user's turn (plus context) into the system's turn, a machine learning version of ELIZA. It is the same sequence-to-sequence transduction used for translation, generating each response token $r_t$ by conditioning on the encoded query $q$ and the response so far:

Generation has a characteristic failure. A basic encoder-decoder, trained to maximize response likelihood, learns that safe, generic replies fit almost any context, so it converges on bland, repetitive turns — I'm OK, I don't know — that are fluent but shut the exchange down.⁷ The dullness is a consequence of the objective, not the data: the most probable response is the least informative one. Remedies include diversity-promoting beam search and training objectives, minimum-length constraints, and, because encoder-decoders optimize a single turn at a time and ignore the long-term shape of the conversation, reinforcement learning and adversarial training that reward turns making the whole dialogue more natural.

Task-oriented dialogue: the GUS architecture

The other tradition helps a user get something done — reserve a flight, book a hotel — and almost all of it, from the 1977 GUS travel planner to today's commercial assistants, is built around a frame.⁸ A frame is a knowledge structure representing a kind of intention the system can extract from user sentences. It is a set of slots, each with a semantic type and a set of possible values, and a question template used to fill it.

The control architecture is frame-filling. The system asks the question attached to each empty slot, records whatever the user supplies, and skips questions for slots already filled. Because one user utterance can fill several slots at once —

I want a flight from San Francisco to Denver one way leaving after five p.m. on Tuesday.

— the system fills all of them and then asks only for what remains. Condition-action rules attached to slots handle defaults (fill the hotel-booking city from the flight destination), and because different inputs must switch control among multiple frames (a fares frame, a route-information frame), GUS is at bottom a production-rule system: different inputs fire different productions that fill different frames.

Filling a slot from a sentence means extracting three things: the domain (is this about airlines or alarm clocks?), the user's intent (SHOW-FLIGHTS, SET-ALARM), and the slot fillers themselves. From Show me morning flights from Boston to San Francisco on Tuesday a system builds a representation like

DOMAIN:      AIR-TRAVELINTENT:      SHOW-FLIGHTSORIGIN-CITY: BostonDEST-CITY:   San FranciscoDEPART-DATE: TuesdayDEPART-TIME: morning

The original GUS did this extraction with handwritten rules — a semantic grammar whose non-terminals are slot names — and rule-based slot-filling, prized for high precision, is still common in industry. It has the usual weaknesses of hand-built systems: the grammars are expensive to write and suffer from recall problems, missing the phrasings the designer did not anticipate.

The dialogue-state architecture

Modern research systems replace the rules with a more sophisticated, machine-learned version of the same frame idea: the dialogue-state (or belief-state) architecture.⁹ It keeps the frame but wraps it in four learned components, a pipeline that runs on every user turn.

Natural language understanding (NLU) extracts the slot fillers and the user's dialogue act from the turn. Dialogue acts fuse the speech-act idea with grounding: a tag like inform, request, confirm, or bye, carried together with its slot-value content. So a user might inform(food=Italian, near=museum), and the system later confirm(pricerange=moderate).¹⁰ Slot-filling itself is sequence labeling: pass the words through a contextual encoder like BERT and tag each with a BIO label ($2n+1$ tags for $n$ slots — a B- and I- per slot plus a single O).

The dialogue-state tracker determines the current state of the frame and the user's most recent act; its main job is accumulation. The state is not just the slots named in the latest sentence; it is the entire frame so far, summarizing every constraint the user has expressed across all turns:

User: I'm looking for a cheaper restaurant
    inform(price = cheap)
User: Thai food, somewhere downtown
    inform(price = cheap, food = Thai, area = centre)

Notice the tracker carries price = cheap forward into the second turn even though the user did not repeat it. A subtle special case is the user correction act — when a user re-states a mis-heard value (I said BAL-ti-more, not Boston), often with exaggerated hyperarticulation. Corrections are harder to recognize than ordinary turns, and detecting them is its own classification problem.

To see the accumulation and a correction in one place, trace the frame across four turns of the air-travel task. The NLU tags each turn with a dialogue act and its slot-value content; the tracker folds that into the running frame — adding new slots, overwriting on a correction, and carrying the rest forward untouched.

Turn 2 adds dest without disturbing orig. Turn 3 is the correction case: the act is correct, not inform, so the tracker overwrites orig from Boston to Austin rather than opening a second origin slot — the recognized correct act is what tells it to replace rather than append. Turn 4 fills the last two slots, and the frame is now complete enough for the policy to execute the flight query. Every slot the user did not mention on a given turn is inherited unchanged; that inheritance is the whole job of the tracker.

The dialogue policy decides what the system should do next — which dialogue act to generate. Formally, given the state at turn $i$, it predicts the best next act ${\hat{A}}_i$; a practical policy conditions on the current frame and the last exchange:

The GUS policy was trivial — ask questions until the frame is full, then query the database. A learned policy is richer: it can decide when to answer, when to ask a clarification question, when to make a suggestion. The most consequential decisions concern confirmation and rejection, where grounding becomes an engineering choice. Under explicit confirmation the system asks a direct yes-no question (Do you want to leave from Baltimore?), which is easy for a user to correct but stilted and long-winded. Under implicit confirmation it grounds by repeating understanding inside the next question (When do you want to travel to Berlin?), which is far more natural. Sophisticated policies can be trained with reinforcement learning: a small action space (execute, confirm, elicit) earns a large reward for finishing with the correct slots, a large penalty for wrong ones, and a small penalty per confirmation to stop the system re-confirming everything.

Finally, natural language generation (NLG) turns the chosen act into text. GUS used fixed templates (Hello, how can I help you?) with variables filled in; the dialogue-state version models generation as content planning (what to say, handled by the policy) then sentence realization (how to say it), often trained with delexicalization — replacing specific slot values with placeholders so the model generalizes across restaurants and cities, then relexicalizing the real values back in.

This lesson covered two traditions: chatbots that chat and frame systems that complete tasks. Until recently a system had to choose between them, and each had to be evaluated and designed on its own terms. A large language model removes the choice. This continues in Dialogue Systems: LLM Assistants, Evaluation, and Design, which folds both traditions into one aligned model and takes up evaluation, design, and ethics.