Frontispiece to Galileo’s Dialogue Concerning the Two Chief World Systems (Stefano della Bella 1632)

I. Elements of Networks

No different from learning another mathematical or programming language, they must transition from their finitely discrete structures and deterministic procedures they have grown acustomed to and make the transition to the infintely continuous structures and stochastic procedures. Back then, ancient greek mathematicians were only comfortable with the finiteness of natural numbers like $1$, $2$, and $3$, and had to grapple with the infinite nature of the real numbers such as $\sqrt{2}$, $\pi$, and $e$. Similarly, the programmers of today are being asked to transition from programming algorithms of sets, maps, lists, trees, and graphs on serial machines to optimizing the distributions of scalars, vectors, matrices, tensors, and neural networks on massively parallel machines. More coloquially, programmers interested in the deep learning approach to artificial intelligence must make the transition from software 1.0software 1.0 to software 2.0software 2.0 See (Karpathy 2017), a distinction used to differentiate the classical act of programming software line by line, and the newer approach of programming software by feeding a dataset to a neural net architecture that has a goal, and searching the space of programs with compute. How to exactly program with this approach will take the remainder of this book to explain.

While software 2.0 has increased the intelligence and autonomy of our devices throughout the past decade — to name a few, language understanding with Google Translate and Apple Siri, vision understanding with Tesla Autopilot — at the end of 2022 ChatGPT was released to the world marking the beginning of software 3.0software 3.0 See (Karpathy 2025), enabling the activity of programming with none other than the English language. What may be surprising to realize is that artificial intelligence like ChatGPT is “just” another computer program. However, rather than being implemented in a language like C, JAVA, or JAVASCRIPT, it’s implemented in one that goes by the name of PyTorch, a software 2.0 programming language centered around torch.Tensor, a multidimensional array humbly embedded within a Python package.

WeA modified excerpt from The Structure and Interpretation of Computer Programs §1: Building Abstractions with Procedures are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program parameters called a model. People create programs train models to direct processes. In effect, we conjure the spirits of the computer with our spells.

A computational process is indeed much like a sorcerer’s idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs models we use to conjure processes are like a sorcerer’s spells. They are carefully composed recovered from symbolic numerical expressions in arcane and esoteric parallel programming languages that prescribe the tasks losses we want our processes to perform minimize.

So in this whimsical whirlwind tour dubbed The Structure and Interpretation of Tensor Programs (SITP), we will embark on a quest to build from scratch our own deep neural network like ChatGPT by implementing nanochat and our own deep learning framework like torch by implementing borscht. Whether you’re an eager high school student, a rising college student, or a battle-tested industrial programmer, SITP has been meticulously designed so that the only prerequisite required is a basic familiarity with the elements of programming, and high school algebra. Any additional experience is helpful, not mandatory. If you’d like to revisit your programming fundamentals, we recommend A Data-Centric Introduction to Computing (Fisler et al. 2025) (DCIC) which is a great introduction to computing with a focus on data scienceSee (Krishnamurthi and Fisler 2020) that starts with the Pyret teaching language and the table data structure (the torch.Tensor in disguise!), and smoothly graduates to Python, the starting point of our adventure herein.

I. Table of Contents

La perspective curieuse (Jean-François Niceron 1638)

1. Self-Supervised Sequence Learning with Single-Layer Networks

In which we transition from the deterministic and discretely finite software 1.0 to the stochastic and infinitely continuous software 2.0 by rediscovering ngrams by Markov and Shannon as well as perceptrons by Rosenblatt using the languages of probability theory and linear algebra afforded by the borscht.Tensor. At the end, we will have rediscovered the early period where researchers in artificial intelligence were uncertain between methods of connectionism and logical symbolism.

1.1 From Certain to Uncertain Knowledge

$\uparrow$ Table of Contents §1.2 $\to$

In which we have our first encounter with the language modeling of GPT-2 via borscht; the primary notions from probability and linear algebra thus used in modeling next-token prediction, namely random variables, their distributions, and their computational equivalent of the multidimensional array.

1.1.1 From Software 1.0 to Software 2.0

$\hookleftarrow$ Table of Contents (§1.1 From Certain to Uncertain Knowledge)

Although ChatGPT, Claude and friends are relatively new to our cosmos, the idea of generating sentences with next token prediction is surprisingly not new and dates back to the work of Russian mathematician Andrey Andreyevich Markov in 1913, and shortly after Claude Shannon in 1948. So why is humanity’s so-called tech tree late to such technology? Predominantly for two reasons.

Philosophically, because of the eternal tension between the discretediscrete and continuouscontinuous methods in describing our reality. Programmers were reluctant to use stochastic and infinitely continuous techniques, favoring those that were logical and finitely discrete. However, … like a physicist position of every particle in a vacuum, even with a set of initial equations for position and momentum with equations for change, describing reality with too many parts to countbitter lesson. This created the need for statistical mechanics, describing particles with probability distributionsprobability distributions.

Practically, it’s because of the fossil-fuel like subsidy of datadata provided by the aforementioned intergalactic computer network we call the web, the computecompute provided by massively parallel processors originally designed for video games we call graphic processing units (henceforth GPUs), which can be used efficiently by a neural network architecturearchitecture called transformer. This is why ChatGPT and Claude are referred to as large language modelslarge language model.

Large Language Models explained briefly (3Blue1Brown 2024)

Large language models are trained using methods from the discipline of deep learningdeep learning, which in turn, are based in the statistical machine learningmachine learning approach to artificial intelligence. This means, in order to produce such a probability distribution over possible next words, ChatGPT, Claude and others use mathematical machinery from the areas of probability theory (clearly), linear algebra, and calculus.

That is, the testingtesting resulting from the evaluation of next-token prediction is stated using the stochasticitystochasticity of probability theory; the specificationspecification of an architecture’s parameterized inductive bias is stated using the dimensionalitydimensionality of linear algebra rather than the discreteness of combinatorics; the implementationimplementation of an architecture’s realized parameters is iteratively optimizedoptimized using the approximation of differential calculus rather than the control flow of structured programming; and the computationcomputation that carries out such an optimization is speed of light acceleration using the rooflines of processor pipelines and memory hierarchies rather than the more abstract cost model of worst case complexity. Put shortly, software 2.0 is built by programming continuous mathematics on highly parallelized and distributed machines — how to exactly program with this new approach will take the remainder of the book to iteratively deepen our understanding of evalsevals, architecturearchitecture, optimizersoptimizers, and systemssystems throughout SITP.

Starting with Part I. Elements of Networks, in §1. Self-Supervised Sequence Learning with Single-Layer Networks we introduce the goal or evaluation of next-token prediction and train our first architectures with linear models which correspond to a single layer of a neural net. This is followed by §2. The Massively Parallel Multidimensional Tensor where we start the implementation of our deep learning system borscht.

Then, in Part II. Neural Networks, particularly §3. Self-Supervised Sequence Learning with Deep Networks, we deepen our understanding of architecture by transitioning from linear models corresponding to single layer networks to non-linear models of multi layer networks, followed by §4. The Engine of Automatic Differentiation where we evolve the implementation of borscht to support automatic differentiation on gpu-accelerated neural network primitives. Finally, in Part III. Scaling Networks (expand).

We will introduce such mathematical primitives by keeping our language models simple at first in Part I. Elements of Networks — namely what is called the ngram model and linear models in which the aforementioned Markov and Shannon were working on around a century ago — before diving into the design of neural network architectures (including transformers with the attention operator) in Part II. Deep Neural NetworksPhysicists learn the standard model before general relativity. Similarly, we must learn the foundations of machine learning before deep learning..

1.1.2 From Variables to Random Variables

$\hookleftarrow$ Table of Contents (§1.1 From Certain to Uncertain Knowledge)

But rather than produce a distribution with two outcomes like a coin, six outcomes like a die, or fifty two outcomes like cards, it produces one for $|V|$ outcomes, where $V$ is the set of words in some vocabularyvocabulary. The size of GPT-2’s vocabulary is 50257, and the list of probabilities you see in Demo 1.1 are the top 10 most likely. As a first approximation, language models can be viewed as as an urn containing a ball labeled with each word in the vocabulary, where some balls are weighted heavier than others.

To be more precise, because we are passing an input sentence, such a distribution is a conditional distributionconditional distribution. That is, GPT-2 is producing the distribution of the next word conditioned on the sequence of words passed in as input, and is denoted by

$p(y\underset{\text{given}}{\underbrace{|}}\text{input sentence})$

and with Demo 1.1, evaluating GPT-2 is equivalent to $p(y|\text{Hello world, nice to})$. That is, language modelslanguage models are next-token predictors modeled by conditional distributions. More accurately, each number in that list of probabilities is the chance that GPT-2 assigns a random variablerandom variable taking on a specific outcome. A random variable is like a deterministic variable in that it can take on values, but rather than being assigned one specific value, it can possibly take on many with a certain degree of chance. A random variable’s distribution then corresponds to an array or list of values which we call a distribution because it distributes the truth or state of the random variable across many outcomes.

In the case of GPT-2, the conditional distribution $p(y|x^{(1)},\dots ,x^{(t)})$’s random variable is denoted as $Y|X^{(1)},\dots ,X^{(t)}$. To make random variables more explicit, some people will denote distributions with their random variables included, which in our case of a conditional distribution over next words, is $p(Y=y|X^{(1)}=x^{(1)},\dots ,X^{(t)}=x^{(t)})$. However, this brings us to our next point which is that with conditional distributions, the random variable being conditioned on is actually no longer random, because it is assumed that it has already taken on a value, in this case where $x^{(0)}=\text{Hello}$, $x^{(1)}=\text{world}$, $x^{(2)}=\text{nice},x^{(3)}=\text{to}$. So, with $p_{Y|X}(y|\mathbf{x})$ more generally, there is no randomness associated with the history $x^{(1)},\dots ,x^{(t)}$. Let us print the distribution over the next word that GPT-2 produces given the history $\text{Hello world, nice to}$ from Demo 1.1:

1.1_gpt2output_torch.ipynb

import torch

# The same GPT-2 output distribution p(w | "Hello world, nice to") from above, top 10 of 50257 words
# (renormalized so this top-10 slice sums to 1)
vocab = ["see", "meet", "hear", "have", "be", "know", "you", "talk", "say", "get"]
probs = torch.tensor([0.387361, 0.154993, 0.152304, 0.127857, 0.057572, 0.043027, 0.039115, 0.015646, 0.013935, 0.008190])

print("Asking GPT-2 what is p(y|Hello world, nice to):")
for i in torch.argsort(probs, descending=True):
    print(f"{vocab[i]} : {probs[i]:.4f}")
print(f"Total sum of p(y|Hello world, nice to): {probs.sum():.4f}")

Asking GPT-2 what is p(w|Hello world, nice to):
see : 0.3874
meet : 0.1550
hear : 0.1523
have : 0.1279
be : 0.0576
know : 0.0430
you : 0.0391
talk : 0.0156
say : 0.0139
get : 0.0082
Total sum of p(w|Hello world, nice to): 1.0000

1.1_gpt2output_torch.ipynb

import matplotlib.pyplot as plt

order = torch.argsort(probs, descending=True)
plt.figure(figsize=(6, 3))
plt.bar([vocab[i] for i in order], probs[order], color="#0072B2")
plt.ylabel("p(y|Hello world, nice to)")
plt.title("GPT-2 next-token distribution (top 10)")
plt.tight_layout()
plt.show()

Where the state of $Y|X$ is being spread across 50257 possible outcomes of GPT-2’s vocabulary. Each index i of the probs array corresponds to a value in the token outcomes tokens[i], with each probs[i] corresponding to the chance, or possibility, of the random variable taking on the value tokens[i]. That is, what connects the weighted array tokens and the state space probs is the index i. It is more accurate then, to describe a random variablerandom variable Stanford CS109 | Random Variables and Expectation | Lecture 6 as states represented by indices $i\in \mathbb{N}$, and the type of a distribution $p$ ends up being some function $p:\mathbb{N}\to [0,1]$ that sends states of indices to their probabilities, such that for all $n\in \mathbb{N},p(n)\ge 0$ and $\sum _{n\in \mathbb{N}}=1$. In general, any list of values between 0-1 and normalizes to 1 is a valid distribution. These properties are referred to as non-negativity and normalization respectively. We can validate that probs is a valid distribution by verifying that each probability is between 0-1 and the distribution normalizes to 1However, since we are only including the top 10 most likely words out of 50256, we’ve re-normalized probs so that the total sum of probs is 1. The original sum is 0.8181, with the other 1-0.8181=0.1819 spread across the other 50256-10=50246 unseen words.. Moreover, since the space of possible outcomes has size of 50257, the random variable $Y|X$ is said to be a discrete random variablediscrete random variable with a probability mass functionprobability mass function as opposed to a continuous random variable with a probability density functionprobability density function.

experimentexperiment trialtrial frequencyfrequency

g = torch.Generator()

n = 10_000_000
target_e = "see"

# p must normalize to 1, so we renormalize our top-10 slice of the distribution
p = probs / probs.sum()
# draw all n samples at once, according to p(y|"Hello world, nice to")
# (tensors hold numbers, not strings, so we sample vocab indices rather than words)
outcomes = torch.multinomial(p, n, replacement=True, generator=g)

i_e = vocab.index(target_e)
prob_e = p[i_e].item()
freq_e = (outcomes == i_e).float().mean().item()
print(f"the expected probability of \"{target_e}\" is {prob_e}")
print(f"the actual frequency of \"{target_e}\" in {n} trials is {freq_e}")

the expected probability of "see" is 0.38736099004745483
the actual frequency of "see" in 10000000 trials is 0.38721099495887756

1.1.3 Probability as Array Programming

$\hookleftarrow$ Table of Contents (§1.1 From Certain to Uncertain Knowledge)

1.1_gpt2output_torch.ipynb

print("gpt-2's output distribution is stored with a torch.Tensor rather than a vanilla python list")
print(f"probs.shape {type(probs.shape)}: {probs.shape}")
print(f"probs.dtype {type(probs.dtype)}: {probs.dtype}")

print("\ngpt-2's individual probabilities are accessed by indexing into")
print(f'0 ({vocab[0]}) -> {probs[0]}')
print(f'1 ({vocab[1]}) -> {probs[1]}')
print(f'2 ({vocab[2]}) -> {probs[2]}')

gpt-2's output distribution is stored with a torch.Tensor rather than a vanilla python list
probs.shape <class 'torch.Size'>: torch.Size([10])
probs.dtype <class 'torch.dtype'>: torch.float32
gpt-2's individual probabilities are accessed by indexing into
0 (see) -> 0.38736099004745483
1 (meet) -> 0.1549929976463318
2 (hear) -> 0.15230399370193481

The two primary properties of a borscht.Tensorborscht.Tensor is it’s .shapeborscht.Tensor.shape and .dtypeborscht.Tensor.dtype. evaluating to (10,) and dtype64 respectively means it’s a vector with support in ${\mathbb{R}}^{10}$ whose real values are being approximately represented with double precision floating point numbers.

Since distributions can be viewed as vectors which in turn can be viewed as lists, probability can be viewed as none other than array programming.

More generally, a borscht.Tensor with .shape of (V), corresponds to a vector with a support $\mathbf{x}\in {\mathbb{R}}^{|V|}$, where $V$ is the vocabulary. (todo: context-length is dimensionality of $\mathbf{h}$). For convenience sake, we analyzed the top 10 probabilities with a borscht.Tensor whose .shape was (10,), which corresponded to a vector $\mathbf{x}\in {\mathbb{R}}^{10}$.

The visual lecture from 3Blue1Brown’s mentions that vector can be viewed as a fancy word for a list — in the context of deep learning we use the term tensor rather than vector.

Vectors | Chapter 1, Essence of linear algebra (3Blue1Brown 2016)

Viewing tensors as lists is taking the data-oriented perspective — for instance probs being some vector $v\in {\mathbb{R}}^{10}$. However, if you squint your eyes and view the probs array from a more functional perspective, it is also a function $p:\mathbb{N}\to \mathbb{R}$statistical learningAlso, if you squint your eyes at the hashmap data structure (in Python a dict) with the functional perspective, it’s a function $map:\text{str}\to T$. In fact, there was a named tensor proposal, Tensor Considered Harmful (Rush 2019), for treating and viewing tensors more like dicts rather than tuples.. The notation ${\mathbb{R}}^{10}$ can be viewed as a function $f:\{1,\dots ,10\}\to \mathbb{R}$, or more generally for ${\mathbb{R}}^n$, the function $f:\mathbb{N}\to \mathbb{R}$. The two notations are equivalent!

missing notebook: /opt/build/repo/sitp/notebooks/1.1_gpt2output.ipynb

Important

Probability can be seen as array programming! Every valid distribution which is some function $p:\mathbb{N}\to [0,1]$ whose values are between 0 and 1 and normalizes to 1 has a corresponding borscht.Tensor with .shape of (todo).

outcomes -> events

• todo eventevent
• todo probability of ORprobability of OR
• todo sum rulesum rule

import numpy as np

# The same <span class="smallcaps">GPT-2</span> output distribution p(w | "Hello world, nice to") from above, top 10 of 50257 words
tokens = ["see", "meet", "hear", "have", "be", "know", "you", "talk", "say", "get"]
probs = np.array([0.3169, 0.1268, 0.1246, 0.1046, 0.0471, 0.0352, 0.0320, 0.0128, 0.0114, 0.0067])

tokens_start_with_h_or_s_and_contains_a_probs = []
for token, prob in zip(tokens, probs):
    stripped = token.strip()
    starts_with_h = stripped.startswith("h")
    starts_with_s = stripped.startswith("s")
    contains_a = "a" in stripped
    if (starts_with_h or starts_with_s) and contains_a:
        tokens_start_with_h_or_s_and_contains_a_probs.append(prob)

prob_starts_with_h_or_s_and_contains_a = sum(tokens_start_with_h_or_s_and_contains_a_probs)

print(f"probability that word starts with letter h: {prob_starts_with_h}")
print(f"probability that word starts with letter s: {prob_starts_with_s}")
print(f"probability that word starts with letter h or s: {prob_starts_with_h + prob_starts_with_s}")
print(f"probability that word starts with letter h or s, and contains letter a: {prob_starts_with_h_or_s_and_contains_a}")

• todo: numpy vectorization

So when you ask an LLM a question, it generates a full answer (with many sentences) word by word by repeating the following loop:

1. evaluating the probability of the next word conditioned on the input
2. selecting (or sampling) a word. halt if the word is the special END word.
3. appending it to the existing text, and evaluating the probability again with the modified input

Now that you understand the basics of language modeling, the trillion dollar question is how to produce such a conditional distribution $p(w|\mathbf{h})$? In some sense that’s all there is to large language models.

1.1.4 Are You Pythonic?

$\hookleftarrow$ Table of Contents (§1.1 From Certain to Uncertain Knowledge)

1.2 Next Token Prediction is Classification and Compression

$\leftarrow$ §1.1 $\uparrow$ Table of Contents §1.3 $\to$

In which The spelled-out intro to language modeling: building makemore (Karpathy) we introduce the terminology of software 2.0 in the context of language modeling; the joint, marginal, conditional with multidimensional arrays, reductions, and broadcasting; implement our first language model by maximizing the likelihood of biased ngrams; evaluate said model’s limits with information theoretical and probabilistic quantities such as perplexity, entropy, bias variance tradeoff, the curse of dimensionality; and finally, understand intelligence more generally as compression.

1.2.1 The Estimation of Software 2.0

$\hookleftarrow$ Table of Contents (§1.2 Next Token Prediction is Classification and Compression)

As mentioned in the previous chapter, large language models are trained using methods from the discipline of deep learningdeep learning, which in turn are based in machine learningmachine learning, which in turn are based in statistical learningstatistical learningActually, the implementation of learning is not just limited to the stochastic and infinitely continuous methods of software 2.0, more classically known as connectionism. It’s also possible to implement with logical and finitely discrete methods of software 1.0 (symbolism), albeit with much less success. See inductive logic programming also known as reverse deduction https://en.wikipedia.org/wiki/Inductive_logic_programming., which in turn are based in statistical inferencestatistical inference, which in turn employs the use of statistical estimationstatistical estimation. What are the meanings of all these terms? Roughly speaking, people in the business of estimation like AI researchers at frontier labs are given data (in statistical jargon, observe samples) such as the internet and would like to estimate distributions (of the population) from said data, namely a $p_{Y|X}(y|x)$ like GPT-2. Because distributions are functions, statistical estimation is also known as function approximationfunction approximation.

Estimation of distributions is one possible activity of making inferences from data — as opposed to simply describing data See https://en.wikipedia.org/wiki/Descriptive_statistics. — another useful form of inference is hypothesis testingSee https://en.wikipedia.org/wiki/Statistical_hypothesis_test., the process of deciding whether observed data provide sufficient evidence to reject a null hypothesis. Estimation however is the primary statistical tool used as opposed to hypothesis testing, and once a distribution like $p_{Y|X}(y|x)$ is estimated from data by research labs, users can use such a distribution in order to generate sentences — hence this most recent wave of statistical methods from software 2.0 being coloquially known as genaigenai, other previous monikers being big databig data, data miningdata mining, data sciencedata science, and pattern recognitionpattern recognition — with an inference loop, namely predicting a distribution over the next token, sampling and appending a token to the history and repeating.

Generally speaking, the difference in direction of estimating a distribution from data versus generating data from a distribution is the primary distinction between probability and statistics, although the line as we will soon see gets quite blurryIn the same way traditional data and function blurs with software 1.0, since functions are also data.. This distinction between the two is more broadly known as the difference between analysisanalysis and synthesissynthesisSee https://plato.stanford.edu/entries/analytic-synthetic/. Researchers analyze the observed data of the internet and recover an estimated distribution whereas users synthesize data and generate sentences. Sometimes they are referred to with direction in time: synthesis is the forward direction whereas analysis is the backward or inverse. Throughout the book, we will incrementally explore increasingly expressive languge models that can do a better job at recovering $p_{Y|X}(y|x)$ from data.

The availibility of said data determines the regime of statistical learning. That is, if sample data is available in the form of input-output pairs $d:=\{({\mathbf{x}}^{(i)},{\mathbf{y}}^{(i)}){\}}_{i=1}^n$, then the regime is known to be supervised learningsupervised learning or self-supervised learningself-supervised learning, for the machine that is attempting to learn a distribution via induction is being supervised with the expected outputs, whereas the regime where such data is unavailable is known as unsupervised learningunsupervised learning. Where in unsupervised learning the goal of inference is that of understanding like clustering or dimensionality reduction, in the regime of supervised learning the goal is the aforementioned statistical estimation of a function that predicts the expected output given the input. For instance, with the following self-supervised dataset

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

Moreover, the regime of supervised learning is further refined depending on the kind of output the estimated function $f:\mathcal{X}\to \mathcal{Y}$is predicting. In the case of a categorical output, the supervised learning is known as classificationclassification for the machine’s goal (the estimated function’s output) is trying to classify the input’s category. Modeling languagelanguage models as next-token prediction is in fact an instance of classification since it is classifying the next most likely token $y\in \mathcal{Y}=V$ given an input sentence $(x^{(1)},\dots ,x^{(t)})\in \mathcal{X}=V^{\ast }$ This stands in contrast to the case when the output that the estimated function is predicting is quantitative, which is known as regressionregression.

Somewhat more confusingly, depending on the domain or context of statistical modeling, the terminology for inputs $x$ and outputs $y$ might be further refined. That is, inputs and outputs are also respectively referred to as independent variableindependent variable and dependent variablesdependent variable, as well as predictorspredictors and responsesresponses in the context of experimental design. They can also be referred to as featuresfeatures and targetstargets. The difficulty of naming is not limited to the discipline of programmingSee https://martinfowler.com/bliki/TwoHardThings.html. Whatever you want to call them, at the heart of statistical learning, machine learning and deep learning is the activity of estimation, or the approximation of functions with inputs and outputs $f:\mathcal{X}\to \mathcal{Y}$. two cultures of statisticstwo cultures of statistics

Warning

Inference is an overloaded term, and hence ambiguous without context! In generative AI the term inference refers to the forward process of evaluating a population’s distribution $p_{Y|X}(y|x)$ in order to generate samples via prediction. In classical statistics the term inference refers to the backward process of inferring a population’s distribution from observed samples

But for the classification of language modeling, how do we reconcile the goal of estimating some function $f:V^{\ast }\to V$, when GPT-2 is the probability distribution $p_{Y|X}(y|x)$ which is a function of type $p_X:\mathbb{N}\to [0,1]$? The way we reconcile such a type mismatch is to map over words from their string representations in $V$ to their index representations in $\mathbb{N}$ with a dict[str, int] instantiated by {c:i for i,c in enumerate(v)}

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

However, note that the input type of a next-token classifier are sentences $(x^{(1)},x^{(2)},x^{(t)})\in V^{\ast }$. (todo: BTD)

$$V\stackrel{I}{\to }\mathbb{N}\stackrel{p}{\to }{\Delta }^{|V|}\stackrel{Q}{\to }\mathbb{N}\stackrel{I^{-1}}{\to }V$$

Let us now estimate our first language model $p:\mathbb{N}\to {\Delta }^{|V|}$

1.2.2 The Joint, Marginal, Conditional, and Chain Rule

$\hookleftarrow$ Table of Contents (§1.2 Next Token Prediction is Classification and Compression)

Let us first start by generalizing the notion of a distribution of a single random variable $p_X:\mathbb{N}\to \mathbb{R}$ which corresponds to a flat array of real-valued numbers satisfying non-negativity and normalization to that of a joint distributionjoint distribution Stanford CS109 Probability for Computer Scientists | Joint Distributions | Lecture 11, defined as a high dimensional function $p_{X_1,\dots ,X_t}$ with type $p_{X_1,\dots ,X_t}:\mathbb{R}\times \cdots \times \mathbb{R}\to [0,1]$ which corresponds to a multidimensional array. Both map the values of $t$ random variables to their probabilitiess. That is, evaluating

$$p_{X_1,\dots ,X_t}(x_1\underset{\text{and}}{\underbrace{,}}\dots ,x_t)$$

produces a single probability for random variable $X_1$ taking on the value $x_1$ and $X_2$ taking on the value $x_2$ and so on, up until the random variable $X_t$ taking on the value $x_t$. Because the joint can be a distribution of two random variables, three, up to an arbitrary t, it’s often vectorized as $p_{\mathbf{X}}(\mathbf{x})$.

In the case of (probabilistic) language modeling, the primary joint distribution of interest is the probability of a fixed t lengthed sentence occuring, which is $p_{X1,X2,\dots ,X_t}(x_1,x_2,\dots ,x_t)$ or $p(\mathbf{x})$ with $x\in {\mathbb{R}}^t$, where the $X_i$’th random variable represents the $i$’th word in the $t$-lengthed sentence. For instance, $p(x_1=\text{Hello},x_2=\text{nice},x_3=\text{to},x_4=\text{meet},x_5=\text{you})$ is the probability of the complete sentence "Hello nice to meet you" (todo, instead of distribution over words, it’s a distribtion over sentences).

Warning

Note with the random variables being modeled the way they are (that is, with order) that the joint $p(x_1,\dots ,x_t)$ is commutative. For instance, with $n:=2$, $p(x_1,x_2)=p(x_2,x_1)$. Semantically speaking, $p(x_1=\text{Hello},x_2=\text{world})=p(x_2=\text{world},x_1=\text{Hello})$ is saying that the probability of the first word being “hello” and the second word being “world” is equal to the probability of the second word being “world” and the first word being “hello”. This holds more generally for any permutation of $x_1,x_2,\dots ,x_t$.

With us defining the notion of a joint probability as a multidimensional array, it’s probably no surprise that the joint distribution $p_X(\mathbf{x})$ corresponds to a borscht.Tensor with .shape (V,...,V) where .ndim is t. That is, .shape is a t-lengthed tuple. Take a look at Figure 1.2.2 below:

Figure 1.2.2

In particular, let us consider the joint distribution of two random variables $p_{X,Y}$, whose 2 dimensional surface can be plotted. This distribution has type $p_{X,Y}:\mathbb{N}\times \mathbb{N}\to \mathbb{R}$, which corresponds to a borscht.Tensor with a .shape of (d1,d2) — a matrixmatrix supported in ${\mathbb{R}}^{d_1\times d_2}$, or in other words, a $d_1$ by $d_2$ rectangular array that maps indices in $\{0,1,\dots ,d_1\}\times \{0,1,\dots ,d_2\}$ to their values in $\mathbb{R}$. Because the array for a matrix can be visualized as a rectangle when taking the data-oriented perspective, the first dimension $d_1$ is usually referred to as the number of rowsrow, and the second dimension $d_2$ is referred to the number of columnscolumn. This naming of course breaks down for tensors with a higher number of dimensions. The code example initializes a matrix with borscht.zeros((n,m)), and plots the surface with ax.plot_surface().

import borscht
x = borscht.zeros((d1,d2))
print(x)

The joint of three random variables $p_{X,Y,Z}:\mathbb{N}\times \mathbb{N}\times \mathbb{N}\to \mathbb{R}$ is plotted as what is known as a voxel plot (it’s difficult to see 4 dimensions alltogether), which corresponds to a borscht.Tensor with a .shape of (d1,d2,d3) — a tensortensor supported in ${\mathbb{R}}^{d_1\times d_2}$, a cubic array that maps indices in $\{0,1,\dots ,d_1\}\times \{0,1,\dots ,d_2\}\times \{0,1,\dots ,d_3\}$ to their values in $\mathbb{R}$. (todo, remark on naming with tensor.) Similarly, the tensor is initialized with borscht.zeros((n,m,p)), is filled with values, and is plotted with ax.voxels(x).

import borscht
x = borscht.zeros((d1,d2,d3))
print(x)

Important

Once again, probability can be viewed as array programming!

(todo, warning on

With the notion of a joint distribution now defined, the actual joint of interest to language modeling is the probability of a sentence taking on specific words $p(W_1=v_i,W_2=v_i,\dots ,W_t=v_i)$ where $v_i\in V$, let $t:=2$ so that we can consider the joint of two random variables $p(W_1=v_i,W_2=v_j)$, which corresponds to a matrix represented by a borscht.Tensor with .shape of (V,V), in this case (5,5). In Figure 1.2.3, the surface on the left and the matrix on the right represent the same distribution $p_{W_1,W_2}(v_i,v_j)$. These values are one possible assignment to the function body $p_{W_1\times W_2}:\mathbb{N}\times \mathbb{N}\to \mathbb{R}$, or equally, one possible assignment to the borscht.Tensor. For instance, we see that $p_{W_1,W_2}(\text{to},\text{meet})=0.16$. (todo, it’s really $p(W_1=3,W_2=4)$. (todo, table is technically infinite. t is not fixed.). Note that the corresponding $v_i\in V$ is provided, even though the distribution is defined on $\mathbb{N}$.

Figure I.2.3

Note

In SITP, we will incrementally increase the expressivity of our next-token predictors or classifiers in order to model language more accurately. Throughout the book, we will maintain a visual language of color in addition to an algebraic one to indicate a consistent purpose or role regardless of what space an object is represented with. For instance, input sentences will be coded with blue whether they are strings $x\in V$ indices $i\in \mathbb{N}$ one hot vectors $\mathbf{x}\in {\mathbb{R}}^{|V|}$, or soon to be embeddings $\mathbf{x}\in {\mathbb{R}}^{|E|}$. Without loss of generality, the same holds for output tokens except coded with orange. More colors will also be introduced later on. This can be toggled at anytime by clicking the located in the top left corner next to the theme picker.

• modify left figure to highlight the 0.15 and 0.16s
• why is the marginal a uniform (0.2)?

For a single random variable $W_i$, we can see that the truth of it’s state is indeed distributed across the vocabulary $V$. For instance, scanning the blue arrow from top to bottom, we see that state of random variable $W_1$ is distributed across five words. In particular, for one of those values $i=3$ which corresponds to $\text{to}$, it’s state in of itself is distributed across $W_2$ with the orange arrow from left to right. For instance, the chance of "to meet"should be more likely than "to to". The code for this joint is the transliteration of the matrix from Figure I.2.3 into borscht.Tensor with .shapeof (5,5):

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

Warning

Let us digress on two technical aspects of borscht: shape suffixes and indexing.

Digression 1: Shape Suffixes

The first place to draw your attention to is in the particular choice of naming the joint distribution as p_VV. The _VV suffix is documentation-based coding brought back from the deadSee Hungarian notation https://en.wikipedia.org/wiki/Hungarian_notation. Also see Google’s C++ Style Guide — a somewhat representative and perhaps canonical standard of most source conventions — frown on Hungarian notation. Finally see Tensor Considered Harmful (Rush 2019) and Named Tensor Notation (Chiang et al. 2021). as a reading aid to humans and fellow LLMs to denote that the borscht.Tensor has a .shape of (V, V), where in this case V evaluates to 5. We even assert such fact with assert p_VV.shape == (V, V). Such judgement can actually be enforced by typechecking dynamically at runtime with the jaxtyping Python package, particularly Float[np.ndarray, "V V"] (expand on jaxtyping and python typechecking):

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

The function printp_VV takes a parameter p_VV with type Float[np.ndarray, "V V"], so the first invocation with the argument p_VV itself passes. Mutating p_VV to alias a borscht.Tensor with .shape (3,) and applying the function a second time results in a type error.

Digression 2: Indexing

Second, notice how the value of $p_{W_1,W_2}(\text{to},\text{meet})$ is retrieved with p_VV[toi, meeti]. (todo, curry by indexing into first or second):

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

Note

Digression is now over.

Now, with borscht technicalities of shape suffixes and indexing aside, let us move onto the next probabilistic concept of the marginal. From this joint distribution of two random variables $p_{W_1,W_2}$, we can recover both distributions of single random variables $p_{W_1}$ and $p_{W_2}$.

Consider again that second “level” of distribution. That is, the specific state of $W_1=\text{to}$ being distributed in of itself across the first row of the matrix according to $W_2$. We can “take out” the randomness of $W_2$ by summing all the entries in the first row, and no longer have this second level or axis of state being distributed, and are simply left with $p_{W_1}(\text{to})=0.2$. In general, for any $v_i$, we have that $p_{W_1}(v_i)=\sum _{v_j\in V}{p}_{W_1,W_2}(v_i,v_j)$. Note that $v_i$ is fixed! In the context of recovering a distribution of a single random variable from a joint distribution, such single random variable distribution is referred to as the marginal distributionmarginal distribution. Transliterating this to borscht, we use borscht.Tensor.sum()borscht.Tensor.sum reduce operationreduction (expand):

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

(todo: generalize for $t$ randvars) torch.sum

After generalizing the notion of a distribution into a joint distribution, and recovering marginals from said joint, we are now finally ready to backtrack to refining the notion of the conditional. $p_{W_1,W_2}(\text{to},\text{meet})=\frac{0.16}{0.2}=0.8$.

conditional distributionconditional distribution Stanford CS109 | Conditional Probability and Bayes | Lecture 4

$$\underset{\text{conditional}}{\underbrace{p_{Y|X}(y|x)}}\stackrel{△}{=}\frac{\stackrel{\text{joint}}{\overbrace{p_{Y,X}(y,x)}}}{\underset{\text{marginal}}{\underbrace{p_X(x)}}}$$

so, the conditional is defined as the joint over the marginal distribution that is being conditioned on. chain rulechain rule product ruleproduct rule (decomposing a joint of sentences with a chain of conditionals over words requires proof (ntermezzo).) with an inference loop, namely predicting a distribution over the next token, sampling and appending a token to the history and repeating.

We can further clarify our notion of language modelslanguage models to next-token predictors performing classification which then auto-regressively feeding such classifying prediction into the next evaluation via chain or product rule.

More generally, broadcastingbroadcasting broadcast divide

There is a rule you should learn at long last,
combination of tensors the task.
Dims right-aligned,
extra left 1s assigned,
match paired dimensions: Broadcast!

9 x 1 x 3 1 x 8 x 1 9 x 8 x 3

Tensor Puzzles (Sasha Rush, Marcos Treviso)

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

1.2.3 Estimating Markov Biased Histograms by Counting

$\hookleftarrow$ Table of Contents (§1.2 Next Token Prediction is Classification and Compression)

We know that $p_{X|Y}(y|x)$ denotes the conditional distribution of the next word given the history of sentence thus far, we know this distribution corresponds to a borscht.Tensor with .shape (V,), and we know the function type is $p_{Y|X}:V^{\ast }\to {\Delta }^{|V|}$ (todo: ${\Delta }^{|V|}$ can be viewed as $|V|\to \mathbb{R}$) which maps sentences to distributions over next words, but how do we go about estimating the distribution $p(y|x)$?

When initially describing the distribution of next possible tokens $p(y|x^{(1)},\dots ,x^{(t)})$ with the stochasticity of probability theory, we also mentioned other phenomena like coin flips, die rolls, and card draws that are modeled stochastically as well and thus with distributions. In the case where such physical objects are deemed to be fair — that is, no one has weighted the coin, die, nor rigged the deck — we can assume that all outcomes are equally likely and subsequently calculate the probability of any event (todo, go write that exposition) is total number of outcomes in the event over the number of outcomes in the sample space.

However, it’s clear that language is not a stochastic process with equally likely outcomes. For instance words “the”, “is, “a” are more likely than “quixotic” for instance. It is for this reason that the first idea to recover or estimate $p(y|x^{(1)},\dots ,x^{(t)})$ is by simply countingcounting the number of times the event of interest occurs from some dataset? sample? and dividing it by the total number of events in the event space, thereby calculating the relative frequency estimaterelative frequency estimate:

$$\frac{\text{\# "Hello world nice to meet you"}}{\text{\# "Hello world nice to meet"}}$$

Taking the internet as our dataset, this ratio is asking out of all the sentences that start with “Hello world nice to meet”, how many times does “Hello world nice to meet you” occur? (todo, define unbiased estimator. in the limit..) While the relative frequency estimate is an unbiased estimatorunbiased estimator, the problem is that language as a phenomena continually evolves, grows, and adapts itself. The fact that natural language can be easily modified and innovated on by new generations of our culture is a feature rather than a bug. While new slang is invented every day, the classic examplar for the problem of using a relative frequency estimate is the following sentence posed by Noam ChomskySee https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously:

$$\text{Colorless green ideas sleep furiously.}$$

Although such sentence now exists on the internet because of Noam Chomsky, the sentence shows one that is syntactically valid but perhaps not semantically meaningful, which, very much resembles the essence of slang. Now, since estimating $p(y|x^{(1)},\dots ,x^{(t)})$ with a relative frequency estimate is intractable, let us explore alternative ways. This motivates the need to dig deeper into the precise defintion of the conditional, what is what we explore here in 1.2.2 The Joint, Marginal, Conditional, and Chain Rule

$$\underset{\text{conditional}}{\underbrace{p_{Y|X}(y|x)}}\stackrel{△}{=}\frac{\stackrel{\text{joint}}{\overbrace{p_{Y,X}(y,x)}}}{\underset{\text{marginal}}{\underbrace{p_X(x)}}}$$

Rather than strive for perfection, we can achieve the good by introducing some biasbias, known as the Markov assumptionmarkov assumption.

• (todo, explain data d)
• counting is the maximum likelihood estimatemaximum likelihood estimate (MLE).
• simplest idea: unbiased estimator count the relative frequency (which is the MLE) $\frac{h,w}{h}$
• need chain/product rule here. but do not introduce bayes rule, for that will introduce discriminant vs generative modeling.
• intractable, so need to introduce bias. with markov assumption (truncated conditional in chain rule)

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

1.2.4 The Scoring of Software 2.0

$\hookleftarrow$ Table of Contents (§1.2 Next Token Prediction is Classification and Compression)

Scoringscore such estimation involves probabilities of probabilities.

maximum likelihood estimation Stanford CS109 Probability for Computer Scientists | M.L.E. | Lecture 21 (Piech)

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

Reinventing Entropy | Compression is Intelligence Part 1 (3Blue1Brown 2026)

1.2.5 The Evaluation of Software 2.0

$\hookleftarrow$ Table of Contents (§1.2 Next Token Prediction is Classification and Compression)

1.2.6 Summary and Further Reading

(Eisenstein 2019)’s Chapter 6. Language Models; (Jurafsky and Martin 2026)’s Chapter 3. N-gram Language Models;

(further reading for torch)

1.3 Parameterizing Classification with Discriminant Functions

$\leftarrow$ §1.2 $\uparrow$ Table of Contents §1.4 $\to$

In which we parameterize classification with a three step process of parameterization, scoring, and optimization; in particular, by directly optimizing the mean squared error of the perceptron; and understand the perceptron’s classifying by expanding our notion of vectors from vectors as lists to vectors as points, enabling not only array programming with distributions, but also with geometry

1.3.1 The Parameter Estimation of Software 2.0

$\hookleftarrow$ Table of Contents (§1.3 Parameterizing Classification with Discriminant Functions)

Whereas in §1.3 Parameterizing Classification with Discriminant Functions, we now change our approach to language modeling next-token prediction (and statistical machine learning more generally) from that of counting to parameterizingparameterization, meaning to define a function with parametersparameters $\theta$ in addition to it’s input $x$. The type of the function $f$ on the right is changed to take in a parameter $\theta$ and an input sentence $x$ in order to produce an output token $y$. However, passing in $\theta$ as an argument on every function evaluation is cumbersome since, after we find a good set of parameters $\theta$, they in fact do not changeUnlike the human brain, which is constantly being reconfigured and rewired!. Rather, what we would like is to instantiate the function with parameters once, and then evaluate such function whenever we needed to predict the next token. The solution to this is to change the type of $f$ to

$$f:\Theta \to (V^{\ast }\to V)$$

which we can partially applypartially apply by passing in $\theta$ as input, and receive the next-token predicting function $V^{\ast }\to V$ itself. In other words, we have curriedcurried the type into a higher order functionhigher order function which can return function themselves. Transliterating a toy parameterized model which multiplies an input $x$ with a parameter $\theta$ to borscht then looks like

import borscht
import borscht.nn as nn

class MyParameterizedModel(nn.Module):
  def __init__(self, theta):
    self.theta = theta

  def __call__(self, x):
    return x*self.theta

theta = 42
model = MyParameterizedModel(theta)
y = model(1)
print(y)

where $f^{\ast }\leftarrow f(\theta )$ is the first evaluation with $f^{\ast }$ denoting the next-token predictor $f:V^{\ast }\to V$, and $y\leftarrow f^{\ast }(x)$ is the second, These correspond to the Python’s class __init__ and __call__ methods respectively. When functions are parameterized, they are denoted as $f_{\theta }$ or $f(x;\theta )$ to reflect such.

Now, because the model is characterized or determined by said parameters $\theta$, such parameters must be estimatedparameter estimation, usually from the dataset $d:=\{({\mathbf{x}}^{(i)},y^{(i)}){\}}_{i=1}^n$. The way this is done is to score such parameters with an objective known as the loss functionloss function, and subsequently find the parameters that optimizeoptimization such loss function, a process denoted by $\mathrm{argmin}$. That is, the problem of finding a good model reduces to finding a good set of parameters according to the loss, which is comprised of a three step process:

todo. fri oct 2

1. risk
2. step zero?

The parameterization of functions and the subsequent parameter estimation are the primary workhorses in the function approximation of statistical learning. However with deep learning, we concern ourselves primarily with the class of models $f_{\theta }$ that are biologically inspired by the brain’s neuroanatomy. Although far from realistic, a neural network $f_{\theta }$ models the signals between the axon of one neuron to the dendrite of another with a set of weightsweights $w$ and biasesbias $b$ where $\theta :=\{w,b\}$. Such models $f_{w,b}(x)$ are referred to as deep neural networks, in which we start by training single layer networks comprised of perceptronsperceptrons Stanford CS229: Machine Learning | Lecture 5 - Perceptron and Logistic Regression. The computational circuit of a perceptron displayed on the left side of Figure 1.3.1, where a perceptron produces a real-valued scalar $y$ by taking the sum $\sum$ of $\mathbf{x}$ with parameters $w$ and $b$.

Figure 1.3.1

The perceptron $f_{w,b}$ is a weighted sum of $x_i$’s and $w_i$’s, which can be rewritten as the dot productdot product of the two vectors $x$ and $w$, and trivially transliterates to borscht.dot()

import borscht
import borscht.nn as nn

class Perceptron(nn.Module):
  def __init__(self):
    self.w = borscht.randn(d)

  def __call__(self, x: borscht.Tensor):
    return borscht.dot(self.w, x)

model = Perceptron()
y = model(x)
print(y)

where the bias term $b$ is folded by prepending $b$ and $1$ into $w_0$ and $x_0$ respectively, subsequently updating the dimension from $d$ to $d+1$. With respect to the three step process, we have completed the first one of parameterizing the architecture $f_{\theta }$. But before moving on to the second and third steps of scoring such parameters with $\ell (\theta )$ and optimizing them with $\mathrm{argmin}\mathcal{L}(\theta )$, you may have noticed that the domain of $f$ is ${\mathbb{R}}^d$ rather than sentences $x\in V^{\ast }$. While we are now familiar with high dimensional arrays, a matrix and it’s row vectors were being used to model the stochastic matrix $P\in {\mathbb{R}}^{|V|\times |V|}$ where discrete word indices were encoded into and out of such matrix with $I$. Moreover, how is it’s codomain of $\mathbb{R}$ classifying some category $y\in V$?

Warning

So how is the perceptron taking in vectors ${\mathbb{R}}^d$ directly,
and how does producing scalars $\mathbb{R}$ perform a classification?
To answer this we need to take the proverbial red pill,
let us go deeper into the rabbit hole of the borscht.Tensor.

1.3.2 Analytic Geometry as Array Programming

$\hookleftarrow$ Table of Contents (§1.3 Parameterizing Classification with Discriminant Functions)

For now, we reconcile how the real-valued output $y=f_{w,b}(x)$ is parameterizing classification with a direct decisiondecision without inferringinferring a probability distribution. We square the latter with the perceptron in §1.4 Parameterizing Classification with Probabilistic Models thereafter. The red pill needed for such reconciliation will deepen our understanding of vectors and matrices, both represented by the multidimensional array of the borscht.Tensor.

Important

The red pill is one which expands our previously conceived notion of vectors from the so-called computer scientist view of tensors as lists, to that of the geometrical view with vectorsvector as points in space. It is quite likely that you may have encountered vectors initially as geometrical points or lines, rather than as computational lists. Because of the inherent difficulty to visualize vectors $\mathbf{x}$ that have support in high dimensional spaces ${\mathbb{R}}^d$ where $d$ is greater than 3, we will start with an example of vectors in ${\mathbb{R}}^2$.

Let us consider a simplified language model setting where the goal is to perform binary classification with a context or history of length 1 on a vocabulary of length 2 where $V:=[new,york]$. And moreover, recall that we are parameterizing such next-token classification $f:V^{\ast }\to V$ with weights and biases via perceptron $f_{\theta }(\mathbf{x}):={\mathbf{w}}^{\top }\mathbf{x}$, corresponding to def __call__(self, x): borscht.dot(self.w, x).

Starting with reconciling the type mismatch of our classifier $h:V^{\ast }\to V$ with the perceptron’s domain of ${\mathbb{R}}^d$, we continue to map words from their string representation in $V$ to their positional indices in $\mathbb{N}$, however, there is an additional transformation of the input thereafter from $\mathbb{N}$ to ${\mathbb{R}}^d$. The simplest idea for such a transformation is to map or embedembedding the position index $i\in \mathbb{N}$ to a $|V|$-dimensional vector $x\in {\mathbb{R}}^{|V|}$ with all entries set to 0 except for the $i$’th dimension which is set to 1. Such a vector is referred to as a one-hot vectorone-hot vector and is known as a localist representationlocalist representation of a word, where each word’s meaning is represented by itself in isolation without a regard to the whole lanugage of English as a whole — for instance, adding two one-hot vectors is meaningless, since any vector with more than one non-zero entry is ill-defined. The final series of representational transformations of the input then looks like

where the corresponding function in borscht to map indices to their one hot vectors is borscht.nn.functional.one_hot(tensor, num_classes=-1) which takes a LongTensor with index values of shape (*) and returns a tensor of shape (*, num_classes).

import borscht
import borscht.nn.functional as F

X = borscht.Tensor([0, 1, 2, 3])
X_BV = F.one_hot(X)

When we map our words $v\in V$ to their one-hot vector representations $\mathbf{x}\in {\mathbb{R}}^2$ with the earlier constructed hashmap c2i, the point $(1,0{)}^{\top }$ for the word $\text{new}$ is located on the $x_1$-axis and the point $(1,0{)}^{\top }$ for the word $\text{york}$ on the $x_2$-axis. This is can seen in Figure 1.3.2

Figure I.3.2 On the left hand side the one hot vectors in ${\mathbb{R}}^2$ are displayed for the strings $\text{new},\text{york}\in V$. On the right hand side a decision boundary linearly separates ${\mathbb{R}}^2$ into decision regions ${\mathcal{R}}_1$ and ${\mathcal{R}}_2$.

Now that we’ve reconciled the type mismatch of our classifier $h:V^{\ast }\to V$ with the perceptron’s domain ${\mathbb{R}}^d$, let us clear our confusion for the perceptron’s codomain of $\mathbb{R}$. In terms of a desirata for the decision step — that is assigning the input $\mathbf{x}\in {\mathbb{R}}^2$ some outcome $y\in V$ — it would be nice if we could divide the plane into two decision regionsdecision regions ${\mathcal{R}}_1$ and ${\mathcal{R}}_2$ associated with the output categories of $y=\text{york}$ and $y=\text{new }$ respectively with some line acting as a decision boundarydecision boundary $l$ such that our classifier $\hat{f}$ assigned the next word $y=\text{york}$ given $(1,0{)}^{\top }$ for $\text{new}$, and perhaps $y=\text{new}$ given $(1,0{)}^{\top }$ for $\text{york}$Bear with the toy example, for although “york new” is non-sensical, it allows us to focus our attention on the mechanics of the perceptron itself..

Rather than define the decision boundary with an explicit equation for a line, another possible idea is to define it as the set of all points $\mathbf{x}$ that are perpendicularperpendicular to the weight vector $\mathbf{w}$.

length(norm) = sqrt[angle(inner/dot product)]

How do we define the notion of perpendicularity without using our eye balls?

• rotationrotation
• orthogonal projectionorthogonal projection

foobar

• distance with metricmetric
• length with normnorm
• length with Euclidean normEuclidean norm ${\ell }_2$
• length with Manhattan normManhattan norm ${\ell }_1$
• dot productdot product
• inner productinner product
• similarity with angleangle
• dot productdot product $\sum _{i=1}^{d+1}{w}_i{x}_i$ = ${\mathbf{w}}^{\top }\mathbf{x}$
• pendicularity with orthogonalityorthogonal

and the final classifier has the form $\hat{f}(\mathbf{x}):=g(\sum _{i=1}^d{w}_i{x}_i)$ where $g:\mathbb{R}\to V$ is some function

$$g(z):=\{\begin{array}{ll}\text{york}& \text{if }z>0\\ \text{new}& \text{if }z\le 0\end{array}$$

$\left[\begin{array}{c}1\\ 0\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\end{array}\right]=1\left[\begin{array}{c}0\\ 1\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\end{array}\right]=1$

$\left[\begin{array}{c}1\\ 0\end{array}\right]\cdot \left[\begin{array}{c}1\\ -1\end{array}\right]=1\left[\begin{array}{c}0\\ 1\end{array}\right]\cdot \left[\begin{array}{c}1\\ -1\end{array}\right]=-1$

Linear combinations, span, and basis vectors | Chapter 2, Essence of linear algebra (3Blue1Brown 2016)

Linear transformations and matrices | Chapter 3, Essence of linear algebra (3Blue1Brown 2016)

1.3.3 The Optimization of Scores in Software 2.0

$\hookleftarrow$ Table of Contents (§1.3 Parameterizing Classification with Discriminant Functions)

$$\mathrm{argmin}\mathcal{L}(\theta )$$

baz

• least squares lost per $x$ $\mathcal{L}(\mathbf{w}):=\sum _{i=1}^n(y^{(i)}-{\mathbf{w}}^{\top }{\mathbf{x}}^{(i)}{)}^2$
  • when d=1, this is finding the line of best fit? (with bias)
  • but then we use the line of best fit as a discriminator with $g$
• is a linear system on $X\mathbf{w}$=$\mathbf{y}$
• min $\Vert \mathbf{y}-X\mathbf{w}\Vert$

1.3.4 Evaluation with Bias Variance Tradeoff

$\hookleftarrow$ Table of Contents (§1.2 Next Token Prediction is Classification and Compression)

1.3.5 Summary and Further Reading

(Duda et al. 2001)’s Chapter 5. Linear Discriminant Functions; (Hastie et al. 2009)’s Chapter 3. Linear Methods for Regression; (Bishop 2006)’s Chapter 3. Linear Methods for Regression; (Murphy 2022)’s Chapter 11. Linear Regression

(Goodfellow et al. 2016)’s Chapter 2. Linear Algebra and Chapter 5. Machine Learning Basics; (Murphy 2022)’s Chapter 4: Statistics and Chapter 7. Linear Algebra

(Bishop 2006)’s Chapter 2. Probability Distributions; (Goodfellow et al. 2016)’s Chapter 3. Probability and Information Theory; (Murphy 2022)’s Chapter 2. Probability: Univariate Models, Chapter 3. Probability: Multivariate Models

(further reading for torch)

1.4 Parameterizing Classification with Probabilistic Models

$\hookleftarrow$ Table of Contents

In which we…

1.4.1 Probabilistic Architectures: Discriminative vs Generative

In machine learningmachine learning, there are actually three ways to estimate a classifier. Recall that the definition of the conditional distributionconditional distribution $p(y|x)$ is the joint $p(y,x)$ over the marginal $p(x)$, and decomposing such joint with the product or chain rule starting with $p(y)$ gives us a relationship of what is known as bayes rulebayes rule

$$\begin{array}{rl}\underset{\text{conditional}}{\underbrace{p_{Y|X}(y|x)}}& \stackrel{△}{=}\frac{\stackrel{\text{joint}}{\overbrace{p_{Y,X}(y,x)}}}{\underset{\text{marginal}}{\underbrace{p_X(x)}}}\\ & =\frac{\stackrel{\text{prior}}{\overbrace{p_Y(y)}}\stackrel{\text{likelihood}}{\overbrace{p_{X|Y}(x|y)}}}{\underset{\text{marginal}}{\underbrace{p_X(x)}}}\end{array}$$

Because the bigram model first produces an inferredinference conditional distribution $p(y|x^{(1)},\dots ,x^{(t)})$ which expresses it’s uncertainty of the next token followed by decidingdecision a specific token from such a distribution, the bigram classifier is an instance of a probabilistic architectureprobabilistic architecture. namely with a discriminative probabilistic modeldiscriminative probabilistic model

And so an alternative approach to modeling $p(y|x)$ directly by (expand), the conditional distribution can be modeled as $p(y|x)=\frac{p(y)p(x|y)}{p(x)}$ and is known as a generative probabilistic modelgenerative probabilistic model because it provides the opportunity to generate samples of the input space $\mathcal{X}$ with $p(x|y)$ where in the case of language modeling the input space is the set of all possible sentences $\mathcal{X}:=V^{\ast }$).

Finally, the inference stage can be skipped alltogether by simply discriminating a specific $y\in \mathcal{Y}$ in one step (in the case of language modeling, the output space is the set of all possible next tokens $\mathcal{Y}:=V$). Models that only consist of that one step are known as discriminant functionsdiscriminant functions and is where we actually begin our discussion of parametric models namely with linear regressionlinear regression corresponding to a single neuron, even though classification and regression were differentiated earlier as producing qualitative and quantitative outputs. We will revisit parameterizing the architecture of a discriminative probabilistic model with logistic regression in 1.4 Parameterizing Classification with Probabilistic Architectures.

which involves a two stage process of specification and implementation.

First, the distribution of $p(y|x)$ must first be specified as a family of distributions $\mathcal{P}$ parameterized by a set of parameters $p$, followed by modeling $p$ itself as some parameterized function class $f_{\theta }(x)$

$$\begin{array}{rl}{p}_{Y|X}(y|x)& =\stackrel{\text{step zero}}{\overbrace{\mathcal{P}(p)}}\\ & =\underset{\text{step one}}{\underbrace{\mathcal{P}(f_{\theta }(x))}}\end{array}$$

Our choice for $\mathcal{P}$ is the Gaussiangaussian distribution with a meanmean $\mu$ and variancevariance $\sigma$ where $\mathcal{P}(p):=\mathrm{Nor}(\mu ,\sigma )$. That is, we are assuming that the output words $y\in V$ are normally distributed conditioned on the input sentences $x\in V^{\ast }$.

whose parameters in turn are modeled as $f_{\theta }(x)$ which is chosen to be the perceptronperceptron, a single layer neural network of weightsweights $w$ and biasesbiases $b$ where $p:=f_{\theta =\{w,b\}}(x)$. That is, not only are we assuming that the outputs $y\in \mathcal{Y}$ are normally distributed conditioned on the outputs $x\in \mathcal{X}$, but also that the parameters to such a distribution can be modeled by a neural network $f_{\theta =\{w,b\}}(x)$.

where $f$ in turn is a function characterized or determined by it’s own set of parameters $\theta$ in addition to the input $x$, and is denoted as $f_{\theta }(x)$ or $f(x;\theta )$ to reflect such. That is, $f:\Theta \times \mathcal{X}\to \mathcal{Y}$ is some function that is curried with parameters $\theta$ and returns a map from inputs $x$ to outputs $y$, which is reflected in borscht.nn.Module where a model is first instantiated with Python’s builtin __init__, and subsequently evaluated with __call__.

With deep learning, $f_{\theta }(x)$ often takes the form of a neural network parameterized by weightsweights and biasesbiases such that $\theta :=\{w,b\}$. In §1.3 and §1.4 we will understand and train single layer networks for $f_{\theta }(x)$ to prepare us for the various network architectures explored in §3. Self-Supervised Sequence Learning with Deep Networks.

Figure 1.3.1

So, after the model family or class has been specified via parameterization, a specific model is implemented or instantiated by continuing to score the quality of the output with the likelihood (TODO) but rather as a function of parameters and moreover, optimizingoptimization said scoring function $\ell (\theta )$ and denoted by $\mathrm{argmin}$. This process is referred to as parameter estimationparameter estimation, or more specifically, maximum likelihood estimationmaximum likelihood estimation (MLE)

$$\begin{array}{rl}& \mathcal{L}(\theta ):=\stackrel{\text{step two}}{\overbrace{\ell (\theta )}}\circ {\hat{f}}_{\theta }(x)\\ \underset{\text{step three}}{\underbrace{\underset{\theta }{\mathrm{argmin}}}}& \mathcal{L}(\theta )\end{array}$$

Figure 1.3.2

1.4.1 Probabilistic Architecture with Logistic Regression (Old)

$\hookleftarrow$ Table of Contents (§1.3 Parameterizing Classification with Discriminant Functions)

In contrast, in this chapter and for deep nets more generally, we will estimate $\hat{f}:V\to V$ by parameterizingparameters probabilities $p(y^{(n+1)}|x^{(n+1)})$ rather than counting them, namely with the weightsweights $w_i$ and biasesbias $b$ of a logistic regressionlogistic regression modelPerhaps logistic classification serves as better terminology, but we will shortly see why it’s called regression which can also be viewed as a single neuronneuron Stanford CS109 Probability for Computer Scientists | Logistic Regression | Lecture 24 Stanford CS229: Machine Learning | Lecture 5 - Perceptron and Logistic Regression from a deep net. That is, some function $\hat{f}:=\text{todo}(\sigma (\sum _{i=1}^d{w}_i{x}_i))$, which we will take the remainder of §1.3.1 Architecture with Logistic Regression to better understand.

A circuit for the logistic regression model is shown on the right hand side of Figure 1.3.1. Rather than produce the orange output $p(y|\mathbf{x})$ with a stochastic matrix containing normalized relative frequency counts, the logistic regression model produces it by passing the blue input $\mathbf{x}$ into the green summing and squashing functions $\sum$ and $\sigma$ with the sum being configured — in this case weighted — with purple parameters $w$ and $b$. Intuitively speaking, by parameterizing $\hat{f}$ what we mean is that we will assume or model $\hat{f}$ as some function that has configurable parameters. You can view the logistic regression model on the right as adding some indirection between the blue input and orange output with green machinery configured by purple parameters. The problem of training a good language model then reduces to that of finding a good set of parameters, in this case $\theta :=\{\mathbf{w},b\}$. That is, the process of training is parameter estimation.

Scanning from left to right of the neuronal circuit depicted in Figure 1.3.1, we first see that the input word "to" to the conditional probability that the logistic regression is modeling is some column vector $\mathbf{x}$ with support in ${\mathbb{R}}^{|V|}$. So, starting from the string "to", we continue to map the string to it’s index $i$ in the vocabulary $V$ with some hash map $I:V\to \mathbb{N}$, but then we need an extra step that maps the index $i\in \mathbb{N}$ to some vector $\mathbf{x}\in {\mathbb{R}}^{|V|}$. If you pay closer attention to the circuit, you will see that only ${\mathbf{x}}_2:=1$ whereas all the other ${\mathbf{x}}_i:=0$. This is called a one-hot vectorone-hot vector, which semantically represents the same positional information within the vocabulary $V$ except vectorizes that information continuously with support in ${\mathbb{R}}^{|V|}$ rather than discretely in $\mathbb{N}$. Because of this, the conditional probability is denoted as $p(y|\mathbf{x})$. Like 1.2_bigram.ipynb, the first cell in 1.3_logistic_regression.ipynb performs the data processing, except with the additional step of tensorizing integer indices over to one-hot vectors with F.one_hot(torch.tensor(indices)):

missing notebook: /opt/build/repo/sitp/notebooks/1.3_logistic_regression.ipynb

missing notebook: /opt/build/repo/sitp/notebooks/1.2_bigram.ipynb

So far we in the logistic regression notebook we have the same dataset, vocab and c2i. But because logistic regression takes in continuous inputs rather than discrete, one more step must be perform in its data processing, namely mapping (tensorizing) integer indices to their one-hot vectors (local, however). We construct list[int] first and convert to tensor’s second, for tensor.append()… (todo)

missing notebook: /opt/build/repo/sitp/notebooks/1.3_logistic_regression.ipynb

Where first five ${\mathbf{x}}^{(i)}$’s are plotted as a heatmap with plt.imshow. Continuing our left to right scan of the logistic regression model depicted in Figure 1.3.1, the next aspect to the neuronal circuit is the core machinery which the one hot vectors are passed through, namely taking a weighted sum $\sum _{i=1}^{|V|}{w}_i{x}_i$ whose real-valued output is then mapped to a number between 0 and 1 with a squashing function $\sigma (\cdot )$. That is, the logistic regression assumption is $P(Y=1|X=\mathbf{x}):=\sigma ({\mathbf{w}}^{\top }\mathbf{x})$.

Figure I.2.3

$$\begin{array}{rlrl}{f}_{\text{sum}}:{\mathbb{R}}^d& \to & & \mathbb{R}\\ \mathbf{x}& \mapsto & & ({\mathbf{w}}_1{\mathbf{x}}_1+{\mathbf{w}}_2{\mathbf{x}}_2+\cdots +{\mathbf{w}}_n{\mathbf{x}}_n)+b\\ & & & =(\sum _{i=1}^d{\mathbf{w}}_i{\mathbf{x}}_i)+b\\ & & & ={\mathbf{w}}^{\top }\mathbf{x}+b\\ f_{\text{squash}}:\mathbb{R}& \to & & [0,1]\\ z& \mapsto & & \sigma (z)\\ & & & =\frac{1}{1+\exp (-z)}\end{array}$$

That is, we model $\hat{f}$ as follows:

$$\begin{array}{rlrl}{\hat{f}}_{\mathbf{w}}:{\mathbb{R}}^d& \to & & [0,1]\\ \mathbf{x}& \mapsto & & f_{\text{squash}}(f_{\text{sum}}(\mathbf{x}))\end{array}$$

One small adjustment we can make to $f$ is to fold the final bias term $b$ into the vector $\mathbf{w}$ as ${\mathbf{w}}_1$, increasing the total dimensionality so that $\mathbf{w}\in {\mathbb{R}}^{d+1}$, and adjusting $\mathbf{x}$ accordingly so that ${\mathbf{x}}_1:=1$ and $\mathbf{x}\in {\mathbb{R}}^{d+1}$. Then, the equation of our line with bias is simply parameterized as $f(\mathbf{x};\mathbf{w})$ $$\begin{array}{rl}{f}_{\text{sum}}:{\mathbb{R}}^{d+1}& \to \mathbb{R}\\ \mathbf{x}& \mapsto {\mathbf{w}}^{\top }\mathbf{x}\end{array}$$

$f(\mathbf{x};\mathbf{w},b)$

missing notebook: /opt/build/repo/sitp/notebooks/1.3_logistic_regression.ipynb

1.4.2 Optimizing Cross Entropy with Iterative Reweighted Least Squares

$\hookleftarrow$ Table of Contents (§1.3 Parameterizing Classification with Discriminant Functions)

But what is cross-entropy? | Compression is Intelligence Part 2 (3Blue1Brown 2026)

missing notebook: /opt/build/repo/sitp/notebooks/1.3_logistic_regression.ipynb

1.4.3 Evaluation with Bias Variance Tradeoff

1.4.4 Summary and Further Reading

(Eisenstein 2019)’s Chapter 2. Linear text classification; (Jurafsky and Martin 2026)’s Chapter 4. Logistic Regression

(Hastie et al. 2009)’s Chapter 4. Linear Methods for Classification; (Bishop 2006)’s Chapter 4. Linear Methods for Classification; (Goodfellow et al. 2016)’s Chapter 5. Machine Learning Basics; (Murphy 2022)’s Chapter 10. Logistic Regression and Chapter 12. Generalized Linear Models

(MacKay 2003)’s Chapter 1. Introduction to Information Theory and Chapter 2. Probability, Entropy, and Inference; (Murphy 2022)’s Chapter 6: Information Theory

(further reading for torch)

1.4.4 bogus below

1.4.4 Architecture with Linear Regression

Recall from §1.2.1 The Estimation of Software 2.0 that the regime of regression is when the function to be estimated is of the form $f:\mathcal{X}\to \mathcal{Y}$ where $\mathcal{Y}:=\mathbb{R}$.

Similarly to learning distributions $X$ from data, learning functions $f:\mathcal{X}\to \mathcal{Y}$ from data roughly follows the three step process of selecting a model for the task $T$, a performance measure $P$, and optimizing such measure on experience $E$. Let’s take a look at the linearly modeling regression with squared error loss, a problem which straddles tools from all three languages of probability theory, linear algebra, and calculus.

For the task of house price prediction, the input space $\mathcal{X}={\mathbb{R}}^d$ is the size in square feet, and the output space $\mathcal{Y}=\mathbb{R}$ is the price, meaning that the function which needs to be recovered has the type of $f:{\mathbb{R}}^d\to \mathbb{R}$. An assumption about the structure of the data needs to be made, referred to as the inductive bias. The simplest assumption to make is to assume that there exists some linear relationship between the data $\mathbf{x}$ and parameters $\mathbf{w}$ so that $f$ ends up being modeled as an inner product plus bias, parameterized as $f(\mathbf{x};\mathbf{w},b)$: $$\begin{array}{rl}f& :{\mathbb{R}}^d\to \mathbb{R}\\ f(\mathbf{x};\mathbf{w},b)& :=({\mathbf{w}}_1{\mathbf{x}}_1+{\mathbf{w}}_2{\mathbf{x}}_2+\cdots +{\mathbf{w}}_n{\mathbf{x}}_n)+b\\ & =(\sum _{i=1}^d{\mathbf{w}}_i{\mathbf{x}}_i)+b\\ & ={\mathbf{w}}^{\top }\mathbf{x}+b\end{array}$$

One small adjustment we can make to $f$ is to fold the final bias term $b$ into the vector $\mathbf{w}$ as ${\mathbf{w}}_1$, increasing the total dimensionality so that $\mathbf{w}\in {\mathbb{R}}^{d+1}$, and adjusting $\mathbf{x}$ accordingly so that ${\mathbf{x}}_1:=1$ and $\mathbf{x}\in {\mathbb{R}}^{d+1}$. Then, the equation of our line with bias is simply parameterized as $f(\mathbf{x};\mathbf{w})$ $$\begin{array}{rl}f& :{\mathbb{R}}^{d+1}\to \mathbb{R}\\ f(\mathbf{x};\mathbf{w})& :={\mathbf{w}}^{\top }\mathbf{x}\end{array}$$

Semantically speaking, each property of the input house ${\mathbf{x}}_i\in {\mathbb{R}}^d$ is weighted by some weight ${\mathbf{w}}_i$, adjusted accordingly during the learning process so that it accurately reflects the property’s influence on the output price $y\in \mathbb{R}$ when evaluating a prediction $\hat{y}$. We can evaluate $f$ on all ${\mathbf{x}}^{(i)}\in \mathcal{D}$ with a randomly intialized $\mathbf{w}$ to ensure we’ve wired everything up correctly.

However, while specifying the equation of the linear regression model on paper screen and subsequently evaluating the computation manually might have been sufficient for pre-computational mathematicians such as Gauss and Legendre, the discipline of statistical learning is entirely predicated on computational methods. Let’s continue to use PyTorch’s core n-dimensional array datastructure with torch.Tensor, this time modeling a function $f:\mathcal{X}\to \mathcal{Y}$ rather than some distribution $X$:

(todo: maybe change example to closure following torch.nn)

{{#include ../../teeny/examples/2.2-regression.py:1:4}}

in which we can update the names of our torch.Tensor variables with the ranks of their vector spacesReferred to as Shape Suffixes, described by Noam Shazeer, an engineer from Google to clarify what dimensions these operations are evaluated on:

{{#include ../../teeny/examples/2.2-regression.py:5:8}}

and finally, actually enforce them via runtime typechecking with the jaxtyping package (try swapping the return statements below to trigger a type error with the return type):

{{#include ../../teeny/examples/2.2-regression.py:9:19}}

Let’s now sanity-check that f_typechecked is wired up correctly by evaluating it on all ${\mathbf{x}}^{(i)}\in \mathcal{D}$ with random parameter w_D. (todo: use actual housing data)

{{#include ../../teeny/examples/2.2-regression.py:29:41}}

random weight vector: tensor([-0.3343,  0.0768,  2.7828, -0.1331])
expected: $500000.0, actual: $-492.46
expected: $800000.0, actual: $-690.89
expected: $250000.0, actual: $-258.08

Clearly, these outputs are unintelligible, and will only become intelligible with a “good” choice of parameter $\mathbf{w}$. Before we find such a parameter, let’s make one more modification to our function $f$ to increase it’s performance. Rather then evaluating f_typechecked on every input xi_D in the dataset zip(X_ND,Y_N) sequentially with a loop, we can evaluate all outputs with a single matrix-vector multiplication by updating $f$’s function definition to the following

$$\begin{array}{rl}{f}_{\text{batched}}& :{\mathbb{R}}^{n\times d}\to {\mathbb{R}}^n\\ f_{\text{batched}}(\mathbf{X};\mathbf{w})& :=\mathbf{Xw}\\ & =\left[\begin{array}{c}{\mathbf{x}}_1^{\top }\mathbf{w}\\ {\mathbf{x}}_2^{\top }\mathbf{w}\\ ⋮\\ {\mathbf{x}}_n^{\top }\mathbf{w}\end{array}\right]\end{array}$$

and the corresponding PyTorch updated to

{{#include ../../teeny/examples/2.2-regression.py:21:27}}

Now that we’ve selected our model for the task $T$, we can proceed with selecting our performance measure $P$ which the learner will improve on with experience $E$.

1.4.5 Loss Function with Least Squares

After the inductive bias on the family of functions has been made, the learning algorithm must find the function $\hat{f}$ with a good fit. Since artificial learning algorithms don’t have visual cortex like biological humans[], the notion of “good fit” needs to defined in a systematic fashion. This is done by selecting the parameter $\theta \in {\mathbb{R}}^m$ which maximizes the likelihood of the data $p(d;\theta )$. Returning to the linear regression inductive bias we’ve selected to model the house price data, we assume there exists noise ${ϵ}^{(i)}$ in both our model (epistemic uncertainty) and data (aleatoric uncertainty), so that $y^{(i)}={\theta }^{\top }{\mathbf{x}}^{(i)}+{ϵ}^i$ where ${ϵ}^{(i)}\sim \mathcal{N}(\mu ,{\sigma }^2)$

prices $y^i$ are normally distributed conditioned on seeing the features ${\mathbf{x}}^i$ with the mean being the equation of the line ${\theta }^{\top }{\mathbf{x}}^{(i)}$ where $y^{(i)}|{\mathbf{x}}^{(i)}\sim \mathcal{N}(\mu ={\theta }^{\top }{\mathbf{x}}^{(i)},{\sigma }^2)$, then we have that

$$\begin{array}{rl}p(y^{(i)}|{\mathbf{x}}^{(i)};\theta )& =\mathcal{N}({\theta }^{\top }{\mathbf{x}}^{(i)},{\sigma }^2)\\ & =\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left(-\frac{(y^{(i)}-{\theta }^{\top }{\mathbf{x}}^{(i)}{)}^2}{2{\sigma }^2}\right)\end{array}$$

Returning to the linear regression model, we can solve this optimization with a direct method using normal equations. QR factorization, or SVD.

def fhatbatched(X_n: np.ndarray, m: float, b: float) -> np.ndarray: return X_n*m+b

if __name__ == "__main__":
  X, Y = np.array([1500, 2100, 800]), np.array([500000, 800000, 250000]) #  data

  X_b = np.column_stack((np.ones_like(X), X))              # [1, x]
  bhat, mhat = np.linalg.solve(X_b.T @ X_b, X_b.T @ Y)   # w = [b, m]

  yhats = fhatbatched(X, mhat, bhat) # yhat
  for y, yhat in zip(Y, yhats):
    print(f"expected: ${y:.0f}, actual: ${yhat:.2f}")

To summarize, we have selected and computed

1. an inductive bias with the family of linear functions $f(\mathbf{X};\theta ):=\mathbf{X}@\theta$
2. an inductive principle with the least squared loss $\mathcal{L}(\theta ):={\sum }_{i=0}^n(y^{(i)}-\mathbf{X}@\theta {)}^2$
3. the parameters which minimze the empirical risk, denoted as $(\hat{\theta })=\mathrm{argmin}\mathcal{L}(\theta )$

Together, the inductive bias describes the relationship between the input and output spaces, the inductive principle is the loss function that measures prediction accuracy, and the minimization of the empirical risk finds the parameters for the best predictor.

Intermezzo One: The Language of Dimension and Stochasticity

$\hookleftarrow$ Table of Contents

Fixed-Size DataA modified excerpt from How to Design Programs (Felleisen et al. 2018)’s Intermezzo 1: Beginning Student Language §1. Self-Supervised Sequence Learning with Single-Layer Networks deals with BSL the NETSOR language implemented by borscht.Tensor as if it were a natural language. It introduces the “basic words” of the language, suggests how to compose “words” into “sentences,” and appeals to your knowledge of algebra for an intuitive understanding of these “sentences.” While this kind of introduction works to some extent, truly effective communication requires some formal study.

I1.1 From Computation to Mathematics

Can we say that a function is a rule that maps one input to a unique output?

Up until the 1900s, this was an acceptable definition!
For bettter and for worse (for us programmers, it’s often the latter), the mathematicians of the 20th century wanted a language that was more precise. Take for example the familiar quadratic from high school — it’s much simpler than a bigram’s stochastic matrix or a perceptron’s weighted sum. We can write down the algebraic equation of the quadratic with pen and paper (or rather $\text{LATEX}$ ($\text{LATEX}$ code \LaTeX)), computational code with borscht, and also it’s corresponding geometric curve with a plot

$$\begin{array}{rl}f:\mathbb{R}& \to \mathbb{R}\\ x& \mapsto x^2\end{array}$$

intermezzo1.ipynb

import torch
import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams["figure.figsize"] = (4, 3)

def f(x: torch.Tensor):
  return x ** 2

x = torch.linspace(-3, 3, 200)
y = f(x)
plt.plot(x, y)

Out[2]:

[<matplotlib.lines.Line2D at 0x117619400>]

To any mathematician whom lived before the 20th century, they would tell you that the quadratic is indeed a function. If you asked them why, they would respond, well, because it’s a rule that passes the vertical line test — there is a unique output for every input.

If you ask any mathematican who comes after, they would and will tell you that all of representations above describe a function — namely our long time friend the quadratic — and that the vertical line test indeed gets to the notion of the concept, but it does not precisely define the concept of function. To illustrate this, they would take the questioning one level further, and ask, well what does “rule” mean, and what does “unique” mean? (Notice how those two words have quotes now!) They are not satisfied by defining the concept of a function with a machine and pencil.

As programmers learning mathematics, we can view this transition of mathematics similar to different styles or paradigms of programming Even though those terms in of themselves are non-sensical!. The same way post 20th century mathematicians are uncomfortable defining the concept of a function with vague notions of a machine and pencil, functional programmers are uncomfortable evaluating expressions with mutation, objective oriented programmers on the other handA false dichotomy but useful one for our current purposes. For instance, Python has lambdas and classes, so what category is it considered as? Go take a programming language course to find out! We recommend the excellent https://www.plai.org/ can’t live without it. These two groups of mathematicians are describing the same objects, and the two groups of programmers are evalauting the same objects. They simply have different relationships to them. Specifically for mathematics, the post 20th century mathematician arguably has a deeper relationship with the notion of function. So, if they are uncomfortable defining the concept of a function with a machine and pencil, what do they want to define it with?

We know that good artists copy, while great artists steal. And these 20th century mathematicians were inspired by an Ancient Greek mathematician named Euclid who lived around two milleniums ago, who did to geometry what they were hoping to do for functions.

Start with some assumptions called axioms.
Define mathematical objects using a definitional language, precisely describing the what.
State beleifs about such objects,
and prove them using an assertion language, precisely describing the why.

The goal of this intermezzo is to do the same, formalizing the notions and beliefs of the mathematical objects we’ve been using all throughout §1. Self-Supervised Sequence Learning with Single Layer Networks. While we start with functions in §I1.1, Relations and Functions, we will be doing the same for the linear transformations of vector spaces over fields in §I1.2 Vector Spaces and Linear Maps, as well as probability distributions of random variables from probability spaces in §I1.3 Probability Spaces and Distributions.

This is going to be very frustrating for us programmers!
We are already familiar with the data structures and learning algorithms of such objects!

We know that a discriminative perceptron is a weighted sum that linearly separates space.
We know that assuming bernouilli results in the cross-entropy loss.
We know that batching them results in a linear system of equations that we can directly solve.
We know that a probabilistically discrminative perceptron squashes the weighted sum into a probability.

What’s the purpose of defining their definitions and proving their properties?
To transfer our understandingThe preface provides more motivation..

Before we deepen our relationship,
with the dimensionality provided by linear transformations of vector spaces
and the stochasticity provided by probability distributions of probability spaces,
let us first understand the language we use to describe these languages.

Deeper the rabbit hole we go.

I1.1.1 Sets and Built-in Numbers

$\hookleftarrow$ Table of Contents (I1.1 From Computation to Mathematics)

Mathematics and computation have a close relationship with one another. As programmers, we naturally gravitate towards the mathematical languages that overlap with the discrete algorithms and data structures we program on a daily basis. Graph theory is the prime example, where we can model relationships between objects with a graph $G$, which is defined as a set of vertices $V$, and a set of unordered edges $E$ that connect them.

A subtle thing just happened with the previous sentence.
We provided a general definition of a mathematical object, and you most likely imagined a graph of concrete objects. Perhaps you thought of a graph of web pages like a search engine, a graph of people like a social network, or even a graph of autonomous vehicles. Whatever the case may be, the concept of a graph was genericallyIf you are familiar with parametric polymorphism such as generics, it is quite similar. defined by using the notion of a set, which is an unordered collection of elements.

As programmers we nod along with passing familiarity. Indeed, all programming languages provide sets. In fact with Python all that is needed is set(). From the Python tutorial’s 5.4 Sets, we can construct a set of fruits with {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}In Python, set() expect’s at most 1 argument, and {} by itself creates an empty dictionary!.

A future update to this book will use type theoretic foundations with Lean.

Another subtle thing also just happened with the previous sentence.
The mathematician’s relationship with the set is to define or produce other mathematical objects.
The programmer’s relationship with the set is to use it model real world objects.
…
The more accurate analogy for the mathematician’s set is the programmer’s type.
As a programmer, if you were asked to define a graph data structure,
you would use a programming language’s type system.
This is why mathematics begins with set theory.A future update to this book will use type theoretic foundations with Lean. The hacker’s paradise.