Markov Chains
The great-grandparent of ChatGPT.
In nineteen thirteen, the Russian mathematician Andrey Markov sat down with a copy of a famous poem, and counted which letters followed which, by hand. Twenty thousand letters. He'd invented the first statistical model of language. And it's still the simplest way to generate text.
- 1913: counting letters by hand
- Twenty thousand letters
- The first language model
Generating text by counting
For each word, we store all of the words which followed it in our tickets. To generate, we start at the beginning, and pick a random next word from that list, again and again. Run it. The parcel. Ink is awful. Ink is broken. Short sentences, which sound a lot like our data, from pure counting. There's no understanding here at all. It only ever looks one word back. A large language model does the same job, of predicting the next token. The difference is that it looks at everything before, using billions of learned weights. It's the same goal, with vastly more context.
import random
from collections import defaultdict
from tickets import TICKETS
chain = defaultdict(list)
for text, _ in TICKETS:
w = ["<s>"] + text.split() + ["</s>"]
for a, b in zip(w, w[1:]):
chain[a].append(b)
random.seed(3)
for _ in range(3):
word, out = "<s>", []
while True:
word = random.choice(chain[word])
if word == "</s>" or len(out) > 12:
break
out.append(word)
print(" ".join(out))the parcel ink is awful ink is broken
Also uses tickets.py
TICKETS = [
("my order arrived late and the box was crushed", "delivery"),
("the parcel never came, where is my delivery", "delivery"),
("courier left the package in the rain", "delivery"),
("tracking has not moved for a week", "delivery"),
("shipping took three weeks, far too slow", "delivery"),
("delivery driver was rude and threw the parcel", "delivery"),
("package is lost, nobody knows where it went", "delivery"),
("the courier says delivered but nothing arrived", "delivery"),
("i want my money back for this book", "refund"),
("please refund the second copy you charged me for", "refund"),
("you took payment twice, return my money", "refund"),
("how long does a refund take to reach my card", "refund"),
("cancel my order and give me a refund", "refund"),
("i returned the book but got no money back", "refund"),
("charged the wrong price, want the difference back", "refund"),
("refund has not appeared on my statement", "refund"),
("the book has missing pages in chapter four", "quality"),
("cover is torn and the spine is broken", "quality"),
("pages are printed upside down in the middle", "quality"),
("ink is smudged on every page", "quality"),
("the binding fell apart after one read", "quality"),
("this copy has a coffee stain on the cover", "quality"),
("wrong edition, and the print quality is awful", "quality"),
("several pages are stuck together badly", "quality"),
]
QUERIES = [
("where is my parcel, it has not arrived", "delivery"),
("i need my money back please", "refund"),
("the pages are torn and the cover is bent", "quality"),
("courier lost my package", "delivery"),
("refund the payment to my card", "refund"),
("print is smudged and hard to read", "quality"),
]Also uses llm.py
from google import genai
from google.genai import types
client = genai.Client()
def ask(prompt, system=None, schema=None, temperature=0.1):
config = types.GenerateContentConfig(temperature=temperature, system_instruction=system)
if schema:
config.response_mime_type = "application/json"
config.response_schema = schema
r = client.models.generate_content(model="gemini-flash-latest", config=config, contents=prompt)
return r.parsed if schema else r.textSummary
Predict the next word. That's the job, from nineteen thirteen to today. Next, a problem that's harder than it looks. Where does a sentence end?
Key takeaways- Count what follows each word
- Sample the next word
- LLMs do this with more context