Anyone can drive a car. Most people even know what the engine looks like. But when you need to fix it, you need to figure out how it works.
Anyone can chat with a chatbot. Most people know that there is a Large Language Model (LLM) under the hood. There are lots and lots and lots of articles describing what an LLM looks like. Lots of colorful pictures. Complicated meshes of small components, as if both mathematical abstraction and modular programming still wait to be invented. YouTube channels with fresh scoops on LLM celebrities. We get to know their parts and how they are connected, we know their performance, we even see how each of them changes a heat map of inputs to a heat map of outputs. One hotter than the other. But do we understand how they work? Experts say that they do, but they don’t seem to be able to explain it even to each other, as they continue to disagree about pretty much everything.
Every child, of course, knows that it can be hard to explain what you just built. Our great civilization built lots of stuff that it couldn’t explain. Steam engines have been engineered for nearly 2000 years before scientists explained how they extract work from heat. There aren’t many steam engines around anymore, but there are lots of language engines and a whole industry of scientific explanations how they extract sense from references. The leading theory is that Santa Claus descended from the mountain and gave us the transformer architecture carved in a stone tablet.
Transformers changed the world, spawned offspring and competitors. . . Just like steam engines. Which may be a good thing, since steam engines did not exterminate their creators just because the creators didn’t understand them.
I wasn’t around in the times of steam engines, but I was around in the times of bulky computers, and when the web emerged and everything changed, and when the web giants emerged and changed the web. Throughout that time, AI research seemed like an effort towards the intelligent design of intelligence. It didn’t change anything, because intelligence, like life, is an evolutionary process, not a product of intelligent design¹. But now some friendly learning machines and chatbot AIs evolved and everything is changing again. Having survived and processed the paradigm shifts of the past, I am trying to figure out the present one. Hence this course and these writings. On one hand, I probably stand no chance to say anything that hasn’t been said before. Even after a lot of honest work, I remain a short-sighted non-expert. On the other hand, there are some powerful tools and ideas that evolved in the neighborhood of AI that AI experts don’t seem to be aware of. People clump into research communities, focus on the same things, and ignore the same things. Looking over the fences, neighbors sometimes understand neighbors better than they understand themselves. This sometimes leads to trouble. An ongoing temptation. Here is a view over the fence.
Spiders are primed to build spider nets. Their engineering skills to weave nets are programmed in their genes. They are preprogrammed builders and even their capability to choose and remember a good place for a net is automated.
Dogs and pigeons are primed to seek food. Their capabilities to learn sources and actions that bring food are automated. In a famous experiment, physiologist Pavlov studied one of the simplest forms of learning, usually called conditioning.
Continuing in the same vein, psychologist Skinner showed that pigeons could even develop a form of superstition, also by trying to learn where the food comes from.
Skinner fed pigeons at completely random times, with no correlation with their behaviors. About 70% of them developed beliefs that they could conjure food. If a pigeon happened to be pecking on the ground, or ruffling feathers just before the food arrived, this would make them engage in this action more frequently, which increased the chance that the food would arrive while they were performing that action. If one of the random associations, say of food and pecking, after a while prevails, then it gets promoted into a ritual dance for food. Each time, the food eventually arrives and confirms that the ritual works.
Humans are primed to seek causes and predict effects. Like pigeons, they associate coinciding events as correlated and develop superstitions, promoting coincidences into causal theories. While pigeons end up pecking empty surfaces to conjure grains, humans build monumental systems of false beliefs, attributing their fortunes and misfortunes, say, to the influence of stars millions of light years away, or to their neighbor’s evil eye, or to pretty much anything that can be seen, felt, or counted².
But while our causal beliefs are shared with pigeons, our capabilities to build houses and span bridges are not shared with spiders. Unlike spiders, we are not primed to build but have to learn our engineering skills. We are primed to learn.
2.2. General learning framework
A bird’s eye view of the scene of learning looks something like this:
The inputs come from the left. The main characters are:
- a process F, the supervisor in supervised learning (Turing called it a “teacher”) processing input data x of type X to produce output classes or parameters y of type Y;
- an a-indexed family of functions 𝒰(−)a, where 𝒰 is a learning machine or interpreter (Turing called it a “pupil”) and the indices a are the models, usually expressed as programs; lastly, there is
- a function ℒ, usually called the loss, comparing the outputs y = F(x) with the predictions ỹ = 𝒰(x)a and delivering a real number ℒ(y,ỹ) that measures their difference.
The learner overseeing the learning framework is given a finite set
where the xs are samples from a source X and the ys are the corresponding samples from the random variable Y = F(X). Learner’s task is to build a model a that minimizes the losses
where yi = F(xi) and ỹi = 𝒰(xi)a for i = 1,2,…,n. Since some of the losses may increase when the others decrease, the learning algorithm is required to minimize the average guessing risk
where [𝒰(xi)a] denotes the frequency with which the guesses 𝒰(xi)a are tried. Once a model a is found for which the risk is minimal, the function F is approximated by running the machine 𝒰 on a program implementing the model a and we write
Potato, potahto, tomato, tomahto. What are the outcomes of learning? We just called the outcome a of a round of supervised learning a model of the supervisor F. Since a is an attempt to present F, most logicians would call it a theory of F. If the interpretations 𝒰(X)a present F(X) truthfully, they would say that F is actually a model of the theory a under the semantical interpretation by 𝒰. Statisticians, on the other hand, would say that a is a hypothesis about F. If a hypothesis or a theory is believed to be true, then it is a part of the learner’s belief state. In the final section, we will arrive at a curious construction illustrating a need for studying the belief logic of machine learning³. We stick with calling the learning outcomes a models since that seems to be the common usage. An important wrinkle, is, however, that a model a of F needs to be executable in order to allow computing the predictions 𝒰(X)a of the values F(X). But if you think about it, executable models are what we normally call programs. In summary, the outcome of a learning process is an executable model. The cumulative outcome of learning is the learner’s belief state. The process of learning is the search for learnable programs.
All learning is language learning. In general, the process F to be learned is given as a channel, which means that the outputs are context-dependent. The story from Sec. 3.2 of the Semantics part applies. The channel inputs xj depend on the earlier inputs xi, i < j. When there is feedback, xj also depends on the earlier outputs yi, i < j. To be able to learn F’s behavior, the learning machine 𝒰 must also be a channel. Since capturing channel dependencies requires syntactic and semantic references, there is a language behind every learner, whether it is apparent or not. The semiotic analyses of the languages of film, music, or images, etc., describe genuine syntactic and semantic structures. Different organisms learn in different ways, but for humans and their machines, all learning is language learning.
2.3. From pigeons to perceptrons
Pigeon superstition. The function F that a pigeon learns to predict is a source of food. It can be viewed as a channel [X ⊢ Y], where the values x1, x2, . . . of type X are moments in time and Y = F(X) is a random variable, delivering seeds with a fixed probability. Suppose that Y = 1 means “food” and Y = 0 means “no food”. If we take the possible models (programs, beliefs) a to correspond to the elements of a set of actions available to the pigeon, then the pigeon is trying to learn for which actions a and at which moments x to output 𝒰(x)a = 1 and when to output 0. The loss ℒ(y, 𝒰(x)a) = |y-𝒰(x)a| is 0 if the food is delivered just when the pigeon takes the action a. After a sufficient amount of time, the random output Y = 1 will almost surely coincide with a prediction 𝒰(X)a = 1 for some a. The pigeon will then learn to do a more often and increase the chance of such coincidences. If one a prevails, the pigeon will learn that it causes food.
Statistical testing. Science is a family of methods designed to overcome superstition and prejudice. The idea is to prevent pigeon-style confirmations by systematically testing hypotheses and only accepting significant correlations. The mathematical foundations of statistical hypothesis testing were developed in the 1920s by Ronald Fisher, and have remained the bread and butter of scientific practices. The crucial assumption is that the interpretation 𝒰 for any hypothesis a is given together with its probability density pa(x) = d𝒰(x)a . The loss ℒ is then estimated by the length of the description of this probability. If the value of pa(x) is described by a string of digits, its description length is proportional to −log pa(x). The guessing risk is thus ℛ(a) = ∫− log pa(x)d𝒰(x)a. Values of this kind are studied in information theory as the measures of uncertainty. Minimizing ℛ(a) thus boils down to choosing the hypothesis a that minimizes the uncertainty of sampling 𝒰 for a. Fisher thus recommended the learning algorithm that selects the hypothesis with a maximal likelihood.
The basic shortcoming of statistical testing is that the densities pa must be known. They are presumed to arise from scientists’ minds, together with their hypotheses parametrized by a. Statistics thus provides a testing service, but the actual process of learning the hypotheses a is out of scope and left to the magic of insight and creativity. While Kolmogorov and his students were pondering this problem for decades and eventually solved it, a central part of the solution emerged inadvertently, and from an unexpected direction.
Perceptrons. In 1943, McCulloch and Pitts proposed a mathematical model of the neuron. It boiled down to a state machine, like Turing’s original 1936 computer, just simpler, since it didn’t have the external memory. In the late 1950s, Frank Rosenblatt was working on expanding the model of a neuron into a model of the brain. It was a very ambitious project.
Rosenblatt, however, arrived at a component simpler than the McCulloch-Pitts neuron. He called it perceptron, to emphasize the difference of his project from the “various engineering projects concerned with automatic pattern recognition and ‘artificial intelligence’ ”. Nevertheless, the project generated news reports with titles like “Frankenstein Monster Designed by Navy Robot That Thinks”, as Rosenblatt duly reports in his book⁴.
Mathematical neurons were defined as pairs a = (b, ⟨w |), where⁵
and b is a scalar. It is meant to be a very simple program intepreted by the interpreter 𝒰. To evaluate a = (b, ⟨w |) on an input vector input vector | x ⟩, the interpreter 𝒰 applies the projection ⟨w | on | x ⟩ to get the inner product ⟨w | x⟩, which measures the length of the projection of either of the vectors on the other, and then it outputs the sign of the difference ⟨w | x⟩ − b:
For a more succinct view, the pair a = (b, ⟨w |) and the input | x ⟩ are often modified to
so that the interpretation of a neuron boils down to
Perceptrons are compositions of such neurons. If a neuron is presented as a single row vector, then a perceptron is an (n + 1)-tuple of row vectors
On an input | x⟩, the interpretation of a perceptron a computes
For a more succinct view, the n-tuple of vectors ⟨w1 |, . . . , ⟨wn | can be arranged into the matrix
so that the perceptron a = (⟨v|, ⟨w1 |,…,⟨wn |) boils down to a = (⟨v|, W) and its interpretation becomes
To summarize in diagrams, here are the two presentations of a neuron on the left and the two presentations of a perceptron on the right.
The first row shows the neuron and the perceptron in the original form, with the thresholds bj. The second row shows the versions where each bj is absorbed as the 0-th component of in the weight vector ⟨wj |.
Perceptrons were a breakthrough into machine learning and inductive inference as two sides of the same coin. Statistics provided the formal methods for hypothesis testing but left the task of learning and inferring hypotheses to informal methods and the magic of creativity. Perceptron training was the first formal method for inductive inference. Nowadays, this method looks obvious. The learner initiates the weights | w ⟩ and the thresholds b to arbitrary values, runs the interpreter 𝒰 to generate predictions, compares them with the training data supplied by the supervisor F, and updates the weights proportionally to the losses ℒ. This didn’t seem like a big deal even to Frank Rosenblatt, who wrote that
the perceptron program [was] not primarily concerned with the invention of devices for “artificial intelligence”, but rather with investigating the physical structures and neurodynamic principles which underlie “natural intelligence”.
Rosenblatt laid the stepping stone into machine learning while attempting to model the learning process in human brains. Even the very first learning machine was not purposefully designed but evolved spontaneously.
It is often said that airplanes were not built by studying how the birds fly and that intelligent machines will not be built by looking inside people’s heads. But there is more at hand. Perceptrons opened an alley into learning as a universal computational process. Machine learning and human learning are particular implementations of the universal process of learning, which is a natural process that evolves and diversifies. Machine learning models offer insights into a common de- nominator of all avatars of learning. The pattern of perceptron computation will be repeated on each of the models presented in the rest of this note.
3.1. Why learning is possible
To understand why learning is possible, we first consider the special case when the channel F is memoryless and deterministic: an ordinary function.
Learnable functions are continuous. What can be learned about a function F:X⟶Y from a finite set of pairs (x1,y1), (x2,y2),…,(xn,yn), where F(xi) = yi? Generally nothing. Knowing F(x) does not tell anything about F(x′), unless x and x′ are related in some way, and F preserves their relation. To generalize the observed sample (x1, y1), . . . , (xn, yn) and predict a classification F(x′) = y′ for an unobserved data item x′, it is necessary that
- x′ is related to x1,…,xn,
- y′ is related to y1,…,yn, where yi = F(xi) for i = 1,…,n, and
- F preserves the relations.
If the sets of the xs and the ys in such relationships are viewed as neighborhoods, then the datatype X and the classifier type Y become topological spaces. The neighborhoods form topologies. Don’t worry if you don’t know the formal definition of a topology. It is just an abstract way to say that x and x′ live in the same neighborhood. A function F:X⟶Y is continuous when it maps neighbors to neighbors. And the neighborhoods don’t have to be physical proximities. Two words with similar meanings live in a semantical neighborhood. Any kind of relation can be expressed in terms of neighborhoods. So if x′ is related with x1 and x2, and F is continuous, then y′ = F(x′) is related with y1 = F(x1) and y2 = F(x2). That allows us to learn from a set of pairs (x1, y1), . . . , (xn, yn) where F(xi) = yi that F(x′) = y′ also holds. Then we can add the pair (x′, y′) to the list as a prediction. Without the neighborhoods and the continuity, we cannot make such predictions. To be learnable a function must be continuous.
There are many ways in which this is used, and many details to work out. For the moment, just note that learning is based on associations. You associate a set of names X with a set of faces Y along a continuous function F:X ⟶Y. You remember the face F(Allison) by searching through the pairs (x1, y1), . . . , (xn, yn) where the names xi are associated with Allison’s. Since F is continuous, the faces yi = F(xi) must be associated with Allison’s. Therefore, if you find a face of a neighbor of Allison’s name, then you can find Allison’s face in the neighborhood of the face of Allison’s neighbor. This is how associative memory works: as a family of continuous functions. The key-value associations in databases work similarly. Both in human memory and in databases, associative memory is implemented using referential neighborhoods. Functions are learnable when they preserve associations. They preserve associations when they are continuous.
Continuous functions can be partially evaluated and linearly approximated. The Fundamental Theorem of Calculus says, roughly, that the derivative and the integral, as operations on functions, are each other’s inverses. The integral approximates any differentiable function, with arbitrary precision, by linear combinations of step functions that approximate the derivative of the function. Any derivable function is linearly approximable by piecewise linear functions.
A function that is just continuous (not differentiable) may not be approximable by piecewise linear functions — but it turns out that it can always be approximated by linear combinations of pieces of a continuous function (not linear or polynomial), usually called actuation. The approximating linear combinations of this nonlinear function are learnable. Hence machine learning.
On the other hand, the approximability of continuous functions has remained one of the big secrets of calculus. The fact that all continuous functions can be decomposed into sums of single-variable continuous functions defies most people’s intutions. It says that, as far as computations are concerned, there are no genuine multi-dimensional phenomena among continuous functions. All those complicated multi-variable functions you may have seen in a vector calculus textbook, or encountered in practice if you are an engineer or a scientist — they can all be partially evaluated, each variable separately. Which is why they can be learned.
3.2 Decomposing continuous functions: Kolmogorov-Arnold⁶
Hilbert’s 13th Problem. Back in 1900, the famous mathematician David Hilbert offered his famous list of 23 mathematical problems for the next century. Number 13 on the list was the question if all functions with 3 variables can be expressed by composing functions of 2 variables. Hilbert conjectured that a specific function, the formula for the solutions of the equation x⁷ + ax³ + bx² + cx + 1 = 0 expressed in terms of the coefficients a, b, and c, could not be decomposed into functions of pairs of the coefficients. More than half way through the century, 19-year-old Vladimir Arnold proved that all continuous functions with 3 variables can be decomposed into continuous functions with 2 variables and disproved Hilbert’s conjecture. Next year, Arnold’s thesis advisor Andrey Kolmogorov proved a stunning generalization. The theorem has been strengthened and simplified ever since. Early simplifications were based on the following embedding of the d-dimensional cube into the (2d+1)-dimensional cube, constructed to allow separating the d variables in any continuous function.
Together with a fixed (2d+1)-dimensional vector ⟨v | , the embedding⁷ W, yields the claimed decomposition.
Comments and explanations. Unfolding the decomposition yields
Only 𝜑 depends on f, whereas W and v are given globally, for all functions of d variables. They are not unique and W can be chosen so that ⟨v| is a vector of 1s, as it is assumed in this unfolded version. The constructions not only disproved Hilbert’s conjecture, but still defy most people’s geometric intuitions. The reason may be that we tend to think in terms of smooth functions, whereas the funcions 𝜓 and 𝜑 are heavily fractal. They are constructed using copies of the Devil Staircase or space-filling curves. The geometric interpretation of the embedding W is that the (2d+1)-tuple of 𝜓s draws a curve in the (2d+1)-dimensional cube and copies of that curve span a homeomorphic image of the d-dimensional cube:
This is the first component of W in the diagram above. The projections on ⟨w| of vectors from within the d-cube determine the linear combinations of copies of 𝜓 whose inverse images iteratively fill the d-cube. Kolmogorov’s original construction partitioned the mapping f along the edges of the d-cube and combined d different functions 𝜑 to represent f . Sprecher and Lorentz later noticed that additional stretching allows capturing all parts of f by a single 𝜑. This is possible because the dependency of f on each of its d variables can be approximated with arbitrary precision on a null-subset of its domain, and the null-subsets of [0,1] can be made disjoint. The upshot is that the only genuinely multi-variable continuous function is the addition. The multiple inputs for multi-variable continuous functions can always be preprocessed in such a way that each input is processed separately, by a single-variable function. The output of the original multi-variable function is then obtained by adding up the outputs of the single-variable components. Continuous functions are thus partially evaluated, each input separately.
The price to be paid is that the single-variable continuous functions that perform the preprocessing and the processing are complicated, ineffective, and constructed through iterative approximations. For a long time, the iterative fugue of Kolmogorov’s proof was viewed as a glimpse from the darkness of a world of complexities beyond any our our imagination or utility. Then in the late 1980s, Hecht-Nielsen noticed that the Kolmogorov-Arnold decomposition seemed related to the perceptron architecture, as the diagrams above also suggest. What is going on?
3.3 Wide learning
So far we studied a theoretic construction providing
- an exact representation of f using
- a projection-embedding pair (⟨v|,W) independent on f and
- an approximate construction 𝜑 dependent on f.
Now we turn to a practical construction providing
- an approximate representation of f using
- a projection-embedding pair (⟨v|,W) dependent on f and
- an exact construction σ independent on f.
The step from the Continuous Decomposition above to the Neural Approximation below is illustrated by comparing the diagram of the KA representation above with the following diagrams of the CHSW representation:
Letting W vary with f allows omitting the deformations 𝜓. Letting ⟨v| vary with f allows replacing 𝜑 with a fixed activation function, independent on f.
3.4. Approximating continuous functions: Cybenko et al
Activation functions. The Neural Approximation theorem below states that any continuous function can be approximated by linear combinations of a fixed activation function σ. All we need from this function is that it restricts to a homeomorphism between two closed real intervals not representable by a polynomial. The construction can be set up to only use the part that establishes this continuous, monotonic bijection of intervals. That part can be conveniently renormalized to a sigmoid: a homeomorphism of the extended real line and the interval [0,1]. Early neural networks used the logistic sigmoid, which readily establishes that homeomorphism. The hyperbolic tangent and arcus tangent were also used, suitably renormalized. Nowadays the function max(0, x) is preferred. Its original designation as “Rectified Linear Unit” got mellowed down to ReLU, a nickname shared with small pets. The Neural Approximation construction fails if the activation function is representable by a polynomial. This obviously precludes all linear functions — but already a continuous combination of two linear functions works fine, as ReLU shows, combining the constant 0 below 0 and the identity above 0.
Since both f and 𝒰(-)f are continuous, the approximation claim is equivalent to saying that for every ε > 0 there is δ=δ(ε) >0 such that
Neurons with activation functions are thus universal approximators of continuous functions, in the sense that for every continuous f on a cube there is a neuron f=(W,⟨v|) such that f|x⟩≈ 𝒰| x ⟩f, with arbitrarily precision.
The proofs of different versions of the Neural Approximation Theorem were published by Cybenko and by Harnik-Stinchcombe-White independently, both in 1989. In the meantime, the neural approximations have been widely used, and various other versions, views, and overviews have been provided. The overarching insight links the CHSW-approximation and the KA-decomposition in a computational framework that seems to have taken both beyond the original motivations.
Continuous functions can be approximated because their variables can be separated. In computational terms, this means that continuous functions can be partially evaluated. That makes them learnable. Unfolding the CHSW-approximation in parallel with the KA-decomposition displays the common pattern:
The corresponding diagrams after the statements show the analogy yet again. But note the differences. The first difference is that w and v on the left depend on f , whereas on the right only 𝜑 depends on it. The second difference is that the number of separate variables that allow partial evaluation, for a fixed input d, is fixed at (2d + 1) in the case of decomposition on the right, whereas in the case of approximation on the left, n = n(ε) depends on the approximation error ε. This is an important point.
The dimension n of the space on on which a given function is approximable by a σ-neuron up to a required precision is the width of the neuron. The Neural Approximation Theorem says that for any continuous function there is a wide enough neuron that will approximate it up to a required precision. This is the essence of wide learning. The idea of approximating continuous functions by a linear combination of copies of σ is similar to Lebesgue’s idea to approximate an integrable function by a linear combination of step functions. In both cases, the arbitrarily close approximations are achieved by increasing the number n of approximants.
Wide neural networks. Everything stated for continuous real functions lifts without much ado to continuous vector functions, which are in finite dimensions just tuples of continuous real functions. The approximations by σ-neurons lift to tuples of σ-neurons, a.k.a. the single-layer neural networks. The tupling step the step from left to right in the following diagram.
A q-tuple of neurons (W, ⟨v1|), (W, ⟨v2|),…,(W, ⟨vq|), bundled together, gives a single-layer neural network a = (W,⟨v1 |,⟨v2 |,…,⟨vq |), more succinctly written a = (W,V), where V is the matrix with the ⟨vj| vectors as rows, like before. The Neural Approximation Theorem implies that every continuous vector function can be approximates with arbitrary precision by a sufficiantly wide single-layer neural network. The term wide neural network usually refers to a single-layer network. The circuit view in the top row of the last figure is aligned with the format where the layers of variables are enclosed in boxes. This will become necessary when the networks become deep.
3.4. Deep learning
Scaling up. The trouble with wide learning is that there are simple functions where separating variables is hard, and the number n of variables that need to be separated increases exponentially with the dimension d. E.g., separating variables in function presenting a hemisphere in any dimension is hard. Although any continuous real function on a cube is approximable by a wide σ-neuron, and any continuous vector function by a single-layer network, the approximations are in the worst case intractable. The amounts of training data needed to extrapolate predictions also explode exponentially with the width⁸.
Narrowing by deepening. The general idea of approximating a function f is to find an algorithm to transform the data
and determine an approximator with
for a desired precision ε. The exponential growth of the width n of single-layer neural networks is thus tempered by descending through layers of deep neural networks, which look something like this:
At each inner layer, composing the input transformation W with the output transformation V of the preceding layer gives a composite H.
As a composite of linear operators, H is linear itself, and can be trained directly, forgetting about the Ws and the Vs. Deep neural networks are thus programs in the form a=(W, H1, H2, . . . , HL, V).
Neural networks are learnable programs. The general learning process can be viewed as the process of program development. To learn a function F means to converge to a program a whose executions 𝒰(x)a approximate F(x). Learners are programmers. It is true that the goal of programming is not just to approximate a function, but to precisely implement it. Ideally, a program a for a function F should satisfy 𝒰(x)a=F(x). In reality, a program implements a function only up to a correctness gauge ℒ(𝒰(x)a,F(x)), realized through program testing or software assurance methodologies. Programming can be viewed as a special case of learning.
We have already seen many of the main features of the syntax of neural networks as a programming language. A single neuron a = ⟨w | is an atomic program expression. A single-layer network a = (W,V) is a single-instruction program. A deep network a = (W, H1, H2, . . . , HL, V) is a general program. Its inner layers are the program instructions. For simplicity, the inner layers are often bundled under a common name, say h = (H1,H2,…,HL). A general neural program is in the form a = (W,h,V).
The trouble with applying function learning to language is that language is context-sensitive: the word “up”, for instance, means one thing in “shut up” and another thing in “cheer up”. We talked about this in the Beyond sintax section of the Syntax part. A function is required to assign to each input the same unique output in all contexts. Meaning is not a function but a communication channel, assigning to each context a probability distribution over the concepts y:
In the Semantics part, we saw how concepts are modeled as vectors, usually linear combinations of words. Meaning is thus a random variable Y, sampled over the concept vectors y. There is an overview of the channel formalism in the Dynamic semantics section of the Semantics part. When there is no channel feedback, the context is the channel source
and the channel outputs are sampled according to the probabilities
You can think of the source X as a text and of the channel F as the process of translating the text to a text Y in another language:
Similar interpretations subsume meaning, syntactic typing, classification, and generation under the channel model. The common denominator is the context dependency, be it syntactic or semantic, deterministic or stochastic. Semantic references can be remote. The meaning of a sentence in a novel may depend on a context from 800 pages earlier. The meaning that you assign to something that an old friend says may be based on a model of their personality from years ago. To make it more complicated, remote references and long established channel models may change from context to context, whenever new information becomes available.
4.1 Channeling through concepts
In different languages, semantical references are mapped to syntactic references in different ways. Mapping a Mandarin phrase to a French phrase requires deviating from the syntactic dependency mechanisms of the two languages. Good translators first understand the phrase in one language and then express what they understood in the other language. It is a two-stage process:
E is a concept encoding map, whereas D is concept decoding. Similar pattern came up in the Semantics part, as instances of concept mining through Singular Value Decomposition (SVD).
The concepts that are latent in a given data matrix M are mined as its singular values λi. Now compare the diagrams of 𝜎-neurons and single-layer networks with the corresponding diagram of the SVD:
A neural network approximates a continuous function by separating its variables and approximating the impact of each of them by a separate copy of the activation function 𝜎. The SVD algorithm decomposes a data matrix through a canonical basis eigenspaces, corresponding to the singular values of the matrix, viewed as the dominant concepts, spanning the concept space. The eigenspaces in the SVD are mutually orthogonal. The action of the data matrix boils down to multiplying each of them separately by the corresponding singular value. Both the neural network approximation and the SVD mine the latent concepts as the minimally correlated subspaces, preferrably orthogonal at each other. The diagrams display the same three-step pattern:
- encoding of inputs in terms of concepts,
- separate processing of each concept,
- decoding of the concepts into the output terms.
The three steps serve different purposes in different ways:
But difference (1) causes differences (2–3). When the function F happens to be linear and difference (1) disappears, the neural network converges to the SVD and differences (2–3) also disappear. Neural networks also mine latent concepts, like the SVD. They just learn them from arbitrary continuous functions.
4.2 Static channel learning
A network of neural networks is static if it processes its inputs by applying the same neural network h on all channel inputs.
n-grams of concepts. As a warmup, suppose that we want to make a static network of networks slightly context-sensitive by taking into account at the j-th step not only Xj but also Xj−1, for all j ≥ 2.
The weights T are updated in the same way as W, by minimizing the losses and propagating the updates back from layer to layer. They just add one training step per layer. This is not a big deal structurally, but it is a significant slowdown computationally. If the inner layers are viewed as latent concept spaces, then this architecture can be thought of as a lifting of the idea of 2-grams (capturing the dependencies of contests of length 2) from words to concepts. Generalizing to n-grams for larger ns causes further slowdown.
Recurrent Neural Networks (RNNs). The RNNs also apply the same neural network on all input tokens and also pass to the j-th module not only Xj but also the information from Xj−1 — but they pass it after the previous network module was applied to Xj−1, not before.
Note that information from Xj−1 is this time forwarded by S not only to the j-th module, but with the output of the j-th module by the next copy of S also to the (j+1)-st module, and so on. The information propagation is thus in principle unbounded, and not truncated like in the n-gram model. The matrices S that propagate important information further are promoted in training. However, the weights assigned to all input entries are all packed in S. Propagating longer contexts requires exponentially wider network modules. So we are back to square one, the problem of width.
Long Short-Term Memory (LSTM). The LSTM networks address the problem of the cost of forwarding the context information between the iterations of the same neural network module by forwarding the information from the (j−1)-th input token to the j-th module both before it was processed by the (j−1)-th module, and after. The former makes passing the information from each input more efficient, the latter makes the propagation easier.
The idea of passing around the information at different stages of processing is simple enough, but optimizing the benefits is a conundrum, as already the “long short” name may be suggesting. The implementation details are many. Different activation functions are applied on different mixtures of the same inputs and remixed in different ways for the outputs. Expressing the concepts learned from the same data in multiple bases requires multiple matrices and provides more opportunities for training. Hence for improvements. But further steps require further ideas.
4.3 Dynamic channel learning
Just like the function learner, the channel learner seeks to learn how the inputs are transformed into the outputs. The difference is that the channel transformations are context-dependent. Not only are the outputs always dependent on the input contexts, but there may be feedforward dependencies of outputs on outputs, and feedback dependencies of inputs on outputs, as discussed in the channel section of the Semantics part. A dynamic network of neural networks learns a channel by adaptively updating the “key” subnetworks k, processing the channel inputs, and the “value” subnetworks v, delivering the corresponding channel outputs.
Encoder-Decoder Procedures. An important programming concept is the idea of a procedure. While the earliest programs were just sequences of program instructions, procedures enabled programmers to invoke within programs not just instructions but also entire programs, encapsulated in procedures as generalized instructions. Since procedures can be used inside most program control structures, this enabled programming over programs, and gave rise to software engineering. The later programming paradigms, modular, object-oriented, component and connector-oriented, extend this basic idea.
The encoder-decoder architecture is a network of neural networks. If neural networks are thought of as programs, it is a program over programs. The encoder-decoder architecture A = (e, d) lifts the structure a = (W, V) of a wide neural network to a network of networks.
The input remixing matrix W is replaced by an encoder network e, the output remixing matrix V by a decoder network d. Both the wide network a and its lifting A follow the architectural pattern of concept mining. Just like procedural programming allowed lifting control structures from programs to software systems, the encoder-decoder architecture allows lifting the concept mining structures from neural networks to neural architectures. The problem with the basic form of the encoder-decoder architecture as a concept mining framework is that a concept space induced by a static dataset is static whereas channels are dynamic. To genuinely learn concepts from a channel, a neural network architecture needs dynamic components.
Idea of attention. A natural step towards enabling neural networks to predict the outputs of a channel
is to generalize the basic 𝜎-neuron from the CHSW construction
In this format, a component of an Encoder-Decoder procedure output would be something like
where
are basic encoder and decoder matrices from a channel concept mining framework. But now we need to take into account the concepts learned at inner layers of a deep network. The impacts on the (n+1)-st output value of the input vectors |xj⟩ are therefore weighed by their projections ⟨ej | xj⟩ on the input concepts ⟨ej| and the projections ⟨yn | dj⟩ of the row vector ⟨yn| of the previous outputs on the output concepts |dj ⟩. The relationship between the corresponding concepts ⟨ej| and |dj ⟩ are trained to align the channel inputs and the channel outputs. This is the basic idea of the attention architecture. It can be drawn as a common generalization of the 𝜎-neuron and the SVD-schema, with dynamic singular values. (This is an instructive exercise.) For string outputs, the obvious extension is
But it is not obvious how to train the matrix V whose rows are the output mixtures ⟨vi |. The issue is solved by approaching the task from a slightly different direction.
Dynamic concept decomposition. A set of vectors |1⟩,|2⟩,…,|n⟩ is said to span the vector space if every vector |y⟩ can be expressed in the form
The decomposition is unique if and only if the vectors |1⟩,…,|n⟩ are orthogonal, in the sense that ⟨i|j⟩ = 0 as soon as i≠j. If the spanning vectors are not orthogonal, but there is an orthogonal set |c1⟩,|c2⟩,…,|cn⟩, then there is a unique decomposition
As discussed earlier, concept analysis is the quest for concept bases with minimal interferences between the basic concepts. The basic concept vectors do not interfere at all when they are mutually orthogonal. If a channel is implemented by a neural network, the above concept decomposition becomes
The first difference is that the activation function σ allows approximating nonlinearities. The second is that the components are not projected on the original basis vectors ⟨i| anymore but on the output mixtures ⟨vi|. Lastly and most importantly, the concept decomposition was unique because the concept basis |c1⟩,…,|cn⟩ was orthogonal, whereas here the output is projected on the inputs |x1⟩,…,|xn⟩, which are not orthogonal. But if an orthogonal concept basis |c1⟩,…,|cn⟩ exists, we can play the same trick again, and get a unique concept decomposition
What does this abstract decomposition mean for a concrete channel? The projections on the concept basis vectors measure their weights in the inputs |xj⟩ and in the outputs |yn⟩. The sum of the products of the projections measures the impact of the input |xj⟩ on the output |yn⟩. This measurement, activated by σ, then impacts the i-th component of the channel output | yn ⟩ according to the projection ⟨vi | xj⟩.
The only problem is that the projection of |yn⟩ on the right is unknown since |yn⟩ is what we are trying to predict. What other value can be used to approximate the impact of a concept in the output |yn⟩? — Two answers have been proposed.
- Translator’s attention: If the channel F : [X ⊢ Y] is a translation, say from Mandarin to French through concepts |c⟩, then the summands ⟨xj|c⟩⟨c|yn⟩ can be thought of as distributing translator’s attention over the concepts |c⟩, latent in the Mandarin input tokens |xj⟩ after the French output token |yn⟩ is produced. That is the attention that effectively impacts the (n+1)-st output, and the above decomposition should be updated to
- Speaker’s self-attention: If the channel F: [X ⊢ Y] is not a translation to another language but a continuation Y in the same language, then it is not feedback-free, since Xn+1 is not independent of Yn, but identical to it. To capture feedback, the concept base splits into an encoding base and a decoding base as above, expressing the inputs as mixtures of concepts, and the concepts as mixtures of outputs. But since each output is promoted into the next input, the encoder-decoder view got replaced by the key-query-value terminology and intuitions, leading to
The self-attention modules in the form a = (K, Q, V), with
are the central component of the transformer architecture, the “T” of the GPTs, with the channel flows combining the feedback and the feedforward flows:
Reconciling the intuitions for attention as a mental process with the database terminology for key-query-value may feel awkward for a moment. Yet the time seems ripe to expand our intuitions and recognize the natural processes unfurling in our heads and in computers.
5.1 Parametric learning framework
Staring back at the general learning framework, after a while you realize that the transformer architecture uncovered a feature that was not visible in the learning diagram there. The feature is parametricity. Models and their programs can be parametrized.
A model can learn the dependencies of a channel F on the values on the first n inputs and leave the (n+1)-st input a program parameter. The outcome of such learning process is a model in the form a(X). When the (n+1)-st input becomes available, it is substituted for X in a(X). The model then instantiates to a program whose interpretation yields a prediction of the next channel output:
Transformers are parametric programs in the form a(X) = (K, Q(X),V). Parametricity is an important feature of machine learning which, like all of the main advances, evolved in practice and awaits theoretic research. In the rest of this note, I sketch some preliminary ideas⁹.
5.2 Self-learning
The parametric learning framework captures learning scenarios where the learners interact and learn to predict each other’s behaviors. This includes not only the conversations between different learning machines, or different instances of the same machine but also a self-learning process similar to the partial evaluation of programs, where a learning machine learns to predict its own behaviors modulo a parameter. A framework for such self-learning can be obtained by instantiating the parametric learning framework to
The obtained model s, called self, approximates the learner in the form
The self-learning framework also captures the unintended self-reflections, where learning machines get trained on corpora filled their own products.
Predicting effects of predictions. Learning impacts what we do and what we do often impacts the processes that we learn. To make effective predictions, the learner must take into account the effects of their own predictions. Parametric learning provides a framework for that. The learner’s capability to predict the effects of their predictions allows them to moreover adjust the predictions towards desired goals, or to avoid the undesired: to generate self-fulfilling prophecies, self-validating or self-invalidating theories, or even adaptive theories that will pass all tests. Such logical phenomena are ubiquitous in history, culture, and in religions¹⁰. Learning machines seem likely to produce more of them, more methodically. The method to produce them is based on learner’s model s of self.
5.3 Self-confirming beliefs
Learning is believing. A model a of a process F expresses a belief held by the learner 𝒰 about F. The learner updates the belief as they learn learn more. Learning is belief updating.
Beliefs impact their own truth values. Our beliefs have impacts on what we do, and what we do changes some aspects of reality: we change the world by moving things around. Since the reality determines whether our beliefs are true or false, and our beliefs, through our actions, change some aspects of reality, it follows that our beliefs may change their own truth values. Accusing an honest person of being a criminal may drive them into crime. Entrusting a poor but honest person with a lot of money may transform them into a rich and dishonest person.
Making self-confirming predictions. If Bob uses a learning machine 𝒰riel to decide what to do, then 𝒰riel can learn a model b that will always move Bob to behave as predicted by b. If Bob shares 𝒰riel’s beliefs, then those beliefs will be confirmed by Bob’s actions.
To spell out the learning process that 𝒰riel can use to construct the self-confirming belief b, suppose that Bob’s behavior is expressed through a channel B. The assumption that Bob uses 𝒰riel to decide what to do can be formalized by taking the outputs of the channel to be in the form
meaning that Bob consults 𝒰riel and believes that the model a(X) explains the input X. The claim is that 𝒰riel can then find a model b(X) that will cause Bob to act as b(X) predicts:
To learn b(X), 𝒰riel first learns a model 𝛽 of B instantiated to 𝒰riel’s model of self:
Processing the 𝛽-explanation of the (2n+1)-th input as the (2n+2)-th input, the definition of 𝛽 yields
The claimed self-confirming model is now defined:
It satisfies the claim because
From learnable programs to unfalsifiable theories and self-fulfilling prophecies. The insight that learning is like programming opens up a wide range of program fixpoint constructions. Applied on learning, such constructions produce models that steer their own truth, whether into self-confirmations or paradoxes, along the lines of logical completeness or incompleteness proofs. The above construction is one of the simplest examples from that range⁹. They prepare models and theories that absorb all future evidence, explain away counterexamples, and confirm their predictions.
