The Function That Has No Formula

Unit 2 builds the language the rest of the course speaks, and its very first word is “function.” Almost everyone arrives with a version that is too small: a formula, a rule with an \(x\) in it. This class trades it for the one a lookup table, a trained network, and a coin flip all share. Underneath, a function is a single promise, and the recipe that keeps it does not matter.

A task you have already done

You have a brightness value, an integer from 0 to 255, and you need to correct it for the way eyes perceive light. This is gamma correction, and the textbook way is a formula: scale into the range 0 to 1, raise to a power, scale back.

On a laptop, fine. On the ESP32-C3 from Unit 1 it is a problem, for a reason you already know: that chip has no floating-point unit, so powf is not one instruction but a slow software routine. Run it on every pixel of a stream and you fall behind. So you do what embedded programmers always do. There are only 256 possible inputs, so you compute all 256 answers once, before the program ever runs, and store them.

Two ways to the same corrected brightness. One computes the answer when asked; the other looks it up from a table filled in ahead of time. One question separates them, and the answer quietly reorganizes how you read a great deal of code, and later a great deal of machine learning.

The powf version is obviously a function. Is the table a function too, or is it “just data”?

Most people’s gut says the table is just data. A function, surely, has an \(x\) in it, a rule you carry out, and the table has no rule anywhere, only a frozen list of answers. That instinct is wrong, and its wrongness is exactly what makes a neural network look like sorcery when it should not. The fix is one idea, and the whole class is that idea pressed from five sides.

The promise underneath

Drop the definitions and ask the only question that matters to whoever calls these two things: what do you get back?

Call powf(...) with raw = 100 and you get one specific number, the same one tomorrow, never “it depends.” Read gamma[100] and you get one specific number, the same one every time. From the call site the two are indistinguishable: same input in, same single answer out. The only difference is when and how the answer was produced, computed on the spot or computed in advance and remembered. That is a question about speed and memory, a Unit 1 question. It says nothing about what kind of object you are holding.

So strip away the recipe, and what both versions truly provide is this:

Look at \(f(x) = x^{2}\) again. The squaring is a recipe, the method this function uses to work out which output goes with an input. But the recipe is not the function. The function is the full set of pairings, every input tied to its one output, and \(x^{2}\) is just a compact way to write them down. Replace the recipe with a giant table of precomputed squares and you have thrown away the formula while keeping every pairing intact. The function is exactly as real as before. It never lived in the formula; it lived in the pairings.

So the picture to carry is not a little machine grinding \(x\) into \(x^{2}\). It is two collections of things with arrows between them: on the left every input, on the right every output, and exactly one arrow leaving each input. The function is that bundle of arrows. We name the two collections and write it compactly:

\(A\) is the domain, the set of inputs the function must handle. \(B\) is the codomain, the set its outputs are drawn from. For our gamma function both are the bytes 0 to 255, so its signature is \(\text{gamma} : \{0,\ldots,255\} \to \{0,\ldots,255\}\). The powf version draws those 256 arrows by computing them; the table draws the identical arrows by storing them.

This is the picture every machine-learning object is built on, and the gamma table is the doorway to it. The embedding layer that begins almost every language model is, literally, a lookup table: hand it a token’s id and it returns the stored row of numbers, embedding[id], no formula in sight. It is gamma[ ] wearing a different hat. And a whole trained network is a function too, taking an input vector to an output vector with no formula a human could write, defined entirely by a pile of learned numbers, exactly as the gamma table is defined by stored ones. Insist that a function must be a formula and all of this looks mysterious. Accept that it is a committed map and it becomes readable: some maps are computed, some stored, some learned, and they are all the same kind of thing.

The one rule, and the one freedom

“Exactly one output per input” quietly grants one freedom and forbids one thing, and people routinely swap which is which. The most literal function a programmer owns shows both at a glance: a dictionary.

Here is a tiny image classifier, written by hand as a dictionary from filename to label:

Its domain is the four filenames, its codomain the two labels. Two facts read straight off it.

The freedom: many inputs may share one output. Both "img1.jpg" and "img2.jpg" map to "cat", and nobody blinks. This pattern is many-to-one, and you have seen it all over Unit 1: gamma[0], gamma[1], and gamma[2] are often all 0, and sign(x) sends every negative number to the single value \(-1\).

The prohibition: one input may never have two outputs. Try to write the opposite and the language refuses. You cannot list "img1.jpg" twice with two values; a key holds exactly one value, and a second assignment just overwrites the first. There is no way to say “img1 is both cat and dog,” and there is no such function either. That is the single rule a function cannot break, and your data structures enforce it for free.

So the test for “is this a function” is never “does it have a formula” and never “is each output unique.” It is only this: does every input land on exactly one output. Here is that dictionary as a map; click a key to see its one arrow, and use the button to try to break the rule.

Many-to-one is not a flaw to tolerate. It is the job. A classifier takes millions of distinct cat photos, each a separate input, and sends them all to the single output "cat", and that collapse, dropping the pose and the lighting and the background while keeping only the label, is exactly what you want. The argmax at the end of a network does the same: many score vectors, one winning class. The prohibition, meanwhile, is why a trained model is deterministic at inference: feed it the same input and you get the same answer every time, because one input aimed at two outputs would not be a function at all. At this level, “a model generalizes” is many-to-one said in plainer words.

Sets: what is even possible

Every arrow starts in a collection on the left and lands in one on the right. We have named those collections loosely, “the inputs,” “the labels.” Loose is dangerous, and here is a bug you could ship this week to prove it.

You read a sensor that reports a status, and the datasheet lists the possible values. You write the handler:

This bug is not in your logic. It is that you never wrote down, exactly and completely, the collection of values status is allowed to take. You kept a fuzzy copy in your head, it was missing one, and nothing checked you. The fix is to name that collection precisely, every value, no duplicates, nothing left out. That precise collection is a set:

Once the possibilities are nailed down as a set, three questions you ask constantly stop being guesses.

Membership: is a value in the set, or not? Strictly yes or no, written \(\text{FAULT} \in S\) and \(99 \notin S\). That is exactly what your switch is meant to answer for every element, and the bug was one membership case you never handled. A good compiler warns you on a non-exhaustive switch over an enum for this reason: the enum is the set, and the compiler is checking that your function covers all of it.

Cardinality: how many values are in it? The count of distinct elements is written \(|S|\), and here \(|S| = 4\). This sounds trivial until it reaches back and grabs Unit 1: a uint8, as a set, is the values 0 to 255, so \(|\text{uint8}| = 2^{8} = 256\). That is not a new fact; it is the same 256 patterns from the wrap-around clock of Class 5, now named as the size of a set. A 12-bit ADC reading is a set of size \(2^{12} = 4096\).

Subset: does one set sit inside another? This is the useful one. The small set is your four valid statuses; the big set is every value a byte can physically hold, all 256. Every valid status is a byte, so the small set sits entirely inside the big one. We call that a subset and write \(S \subseteq \{0,\ldots,255\}\). Now the danger is precise: the hardware can hand you any value from the big set, but your code handled only some of them. A bug strikes whenever a value arrives from the big set that your small handled-set left out, whether that is the legitimate FAULT you forgot or a garbage byte off a glitchy wire. Every “unhandled value” bug has this one shape.

That subset gap is the deepest idea in all of learning, under a different name. Your training data is a tiny subset of every input the world could ever present. Training teaches the model to behave on that subset; in production, inputs arrive from the big set, almost none of which it ever saw. Performing well on the part of the big set you never trained on is exactly what generalization means. It is the FAULT-fell-through gap, promoted to the central problem of the field. And cardinality is on the first slide too: MNIST has a label set of size 10, ImageNet 1000, and a language model’s vocabulary \(V\) is a set whose size \(|V|\), often above fifty thousand, fixes how big the embedding table and the output layer must be.

Reading a function by its signature

Open an unfamiliar codebase and land on a function you have never seen. Before you read a single line of its body, what tells you how to use it?

Its signature: what it takes in, and what it gives back. int parse(const char *) already names the input set and the output set, and you can wire it in correctly before understanding one thing about how it works inside. A mathematical function carries the very same label, the one we have been writing:

Reading a component by its signature, domain to codomain, is the fastest way to navigate machine learning, because the signature tells you what plugs into what. The pieces you meet constantly are each just a map from one set to another:

That last signature, the embedding \(V \to \mathbb{R}^{d}\), is worth watching run, because it closes the loop of the whole class: a function with no formula, mapping a member of a set to a vector by pure lookup. Pick a word. Watch it become an index, which is just a position in the vocabulary set shown as a one-hot vector, and then the stored row of numbers that index points at.

Chaining maps, and why the shapes must line up

One function is rarely the whole story; you feed the output of one straight into the next. In code you have written this a thousand times:

That is composition, written \(g \circ f\) and read “g after f.” It is the move a neural network is built from. But it holds under exactly one condition, and that condition is this section’s question:

When is chaining two functions even allowed?

Exactly when the output of the first lands in the set the second takes as input. The arrows leaving \(f\) must arrive in the set that \(g\)’s arrows start from, or \(g\) has nothing to act on. Said with signatures: if \(f : A \to B\) and \(g : B \to C\), then the chain is \(g \circ f : A \to C\), and the shared \(B\) sitting in the middle, the codomain of the first equal to the domain of the second, is the entire reason it holds together.

A neural network is a composition of functions. Each layer is a map, and the network is layers chained nose to tail, out = f3(f2(f1(x))). That one line is the architecture. And the shared-set rule is the very first error every practitioner meets: a shape mismatch. If layer one outputs a vector in \(\mathbb{R}^{128}\) but layer two expects \(\mathbb{R}^{256}\), the middle set does not match, the codomain of one is not the domain of the next, and the framework refuses to run. Drag the two dials and watch the seam meet and break.

Zoom all the way out and the payoff of the class is one picture: a real model is just a row of maps, each with a clean signature, each handing its codomain to the next one’s domain.

What to carry out of Class 6

We started with one honest question, is a lookup table a function, and the answer reorganized everything else.

The next class keeps the language going: summation and products, the notation for adding and multiplying a whole set at once, and the first place a long product quietly underflows to zero on the chip.

See if it stuck

Eight questions, all answerable from this post. Tap an answer for an immediate verdict and the reason.