Functions, Prediction, and Autoregression
August 30, 2023
Prediction takes several computational forms. A function maps arguments to values, autoregression maps recent history to future values, and a state machine carries explicit memory through events.
Transformers add a learned generative mapping whose continuation can cross domains and produce a structure that no programmer explicitly enumerated.
Functions Become Machines Through State
Boolean functions compose into datapaths, and registers add memory. Harel statecharts organize events and hierarchy, producing parallel reactive systems with enough structure to host conventional von Neumann computation.
Autoregressive models carry state implicitly through prior samples. Their prediction depends on both the representation and the selected history window.
Generation Extends the Reach of Prediction
A Transformer maps context into a distribution over continuations, then sampling turns that distribution into a new sequence. Learned representations let the continuation connect distant patterns across language and data.
Brian compares that generative reach with the creative function embodied by a human software engineer. Researchers can study the relationship between formal computation, learned prediction, and authored meaning.
Run Functions, Prediction, and Autoregression in a Four-Layer Transformer
The complete training run connects this mathematical argument to executable code, data flow, and a working small model.
LinkedIn status when archived: Visible to anyone on or off LinkedIn.
Computer scientists and mathematicians use functions to make predictions: give me input arguments, I'll tell you the value of that function in simple regression models. Give me values of your function at previous few arguments, and I'll tell you its values at next arguments in the autoregressive models. I can also write a Boolean function, implement a finite state machine, or event-driven datapath based on UML Statecharts, that provides the computational power of parallel reactive programming, the same that runs your CPU and GPU. You can run von Neumann architecture code on it, proved Turing complete.
What's new about Transformer is it's not "just a function that for given input returns a computed output." It's something NEW. Computation-power wise, it can GENERATE unexpected end of the ceiling you're staring at and tell you that's where exactly the street starts!
I only know another mathematical concept that's capable behaving the same way: a function, implemented by a Human Software Engineer.
#LLM #selfattention #computerscience #Turingcomplete