Skip to main content
Posts tagged:

machine learning

Handwiring the Future

A very cool new compiler trick may point to a much bigger idea: a new way to think about how programs and learning fit together. In fact, this may actually be a new way to think about computation itself. The core idea is that programs can be both specified and trained.

How? Cheng Lou released a project called Handwired that takes ordinary JavaScript (conditionals, loops, state) and transforms it into the kinds of mathematical operations we associate with neural networks. This turns a program you explicitly write into something that can potentially be improved using the same learning machinery behind modern AI. That means software no longer has to be only written or only learned, it can start as a precise program and then become trainable.

You could get code started and let the real world finish it for you, picking and choosing what bits stay fixed and what parts get better.

Ok, this probably makes no sense. Let’s break it down. We have traditionally had two ways to tell computers what we want: you tell the machine what to do step by step (programming), or you show it examples and let it learn the behavior for itself (machine learning). Let’s explore these to show exactly what is new here.

For most of computing history, if you wanted a computer to do something, you wrote a program. You wrote:

if this happens:
    do this
else:
    do that

The great virtue of software is precision. A compiler takes your intent and progressively lowers it into another representation while trying very hard to preserve its semantics.

Machine learning approaches the problem from almost the opposite direction. Instead of specifying the mechanism and getting the behavior, we specify the behavior we want (through data, examples, and an objective) and let optimization discover the mechanism. With a neural network, we generally don’t know the program. We define an architecture, provide examples or an objective, initialize a huge set of parameters, calculate an error, and use gradient descent to modify those parameters until useful behavior emerges.

Programming gives us control. Machine learning gives us adaptability. What if we could have both?

Handwired starts with a program, not a training set or model that learns an approximation of the behavior. Take:

if a > 4:
    return 10
else:
    return 12

Handwired can transform this kind of control flow into arithmetic constructed from ReLU1 operations and weighted values. Those operations can then be collected into the matrix-oriented representation used by neural networks.

So we get something like:

The question mark is important. We can’t assume that gradient descent magically improves any software, but the question can fundamentally change: Can I compile the program I already know into a representation that learning can subsequently modify?

I can’t tell if this has more potential to change programming or machine learning. Modern neural networks generally begin ignorant and get smarter with better data. But imagine reversing that. Suppose we start with a system that already contains substantial amounts of human knowledge: physical laws, constraints, safety rules, existing software, engineering tools, etc.

Those things don’t have to be rediscovered through training, they can be compiled in. We can then make only the places where uncertainty or optimization actually exists learnable.

Instead of data driving the system performance, you can encode what you know about the world.

Learning becomes a refinement mechanism instead of the mechanism by which the entire system comes into existence.

This might eventually give us a very different way to build software. Imagine writing systems in which the compiler understands that different portions have different semantics with different options.

Now the compiler isn’t merely generating executable code. It is generating an optimization space. Some of the resulting representation is frozen. Some of it is trainable. Some is governed by constraints.

The boundary between “program” and “model” becomes much less rigid.

I thought about how to make this more clear interactively. Suppose we want a function that turns 0 into 1, 1 into 3, and 2 into 5, continuing the same pattern. Choose an input above and watch it travel through the box. The answer is already specified; the question mark is there because we haven’t said how the machine will produce it.

Change different input values below to set the stage for how this more complicated idea works.

Input

Choose a number.

This distinction is the starting point. A task describes the behavior we want: for a given input, what should the output be? The example above doesn’t yet tell us how to build that behavior. Most of us would go into SAT math problem mode and see that there is a linear equation that you can pull out of this and we would do the algebra and get:

f(x)=2x+1f(x) = 2\,x+1

But what if we just fed a bunch of examples to a machine learning system? It’s just another way to get a functional system. To get some intuition for this, let’s extend this basic example. Click “learn” below to see a cartoon of how a system arrives at the same capability through these two different ideas.

Input

Programming

3 → 7

Machine learning

3 → 1.50

● Prediction○ Target

Training error4.25

That is pretty basic description of the difference between a program and a machine learning model, but it sets the stage to get what is going on with Handwired.

Here we take a working program and give it a few adjustable knobs. Handwired does this by translating the program’s rules into the arithmetic of a neural network, with weights chosen to reproduce its behavior from the start.

To get this, consider a trivial program. If the input is greater than 4, return 10; otherwise, return 12. Compilation preserves those answers. But! What if we wanted to adjust this? We could re-compile a new one, or we can “unlock” one weight and introduce examples asking for 8 instead of 10.

Watch the blue dots move toward their targets as learning adjusts that answer, while the decision and the other answer stay fixed. The program supplies the starting knowledge; learning refines the part we allow to change.

Try different input values and then click “compile” below, followed by “learn” to watch the system adapt.

Input
x > 4 ? 10 : 12Written rule

A decision picks one of two answers.

● Output○ Target

Inside the gateg = max(0, x − 4) − max(0, x − 5)

For these whole-number inputs, g is 0 or 1. The compiled output is g × 10 + (1 − g) × 12.

This illustration follows Handwired’s published arithmetic. It is a small explanatory model, not the Handwired compiler itself.

Input 5 produces 10.

So with some understanding of this. What could this actually do?

First, this capability could give us a very different way to make ordinary code run faster. Handwired takes control flow that looks sequential, loops, conditionals, state, and lowers it into a small vocabulary of fast math operations. GPUs and modern ML infrastructure are extraordinarily good at executing and optimizing exactly those kinds of operations. Cheng Lou's JSON-search demo, for example, takes traditionally written JavaScript and runs the resulting computation over 100,000 documents on WebGPU in milliseconds. He also points out that once the program has been reduced to these primitives, techniques such as fusion, sparsity, and reordering become available to the compiler. This does not mean arbitrary JavaScript suddenly becomes faster on a GPU, but it raises an intriguing possibility: can we write code in a familiar sequential way and let the compiler discover a massively parallel way to execute it.

Second, a differentiable program gives us a new way to ask questions and gain deeper understanding about what the program is doing. Traditional debugging can tell us how a value flowed through a program; differentiation can potentially tell us how sensitive the final result is to values and parameters throughout that computation. In other words, instead of merely asking, “Why did I get this output?” we can sometimes ask, “Which things would most change this output, and in which direction?” This is already the basic power of automatic differentiation systems such as JAX: grad transforms a function into another function that calculates its gradient, while reverse-mode differentiation propagates information backward through a computation. Handwired's contribution is interesting because it tries to bring ordinary program structures into that same differentiable world. This isn't human-like understanding of code, but it could give software something extremely useful: a map of its own sensitivities.

Third, once you have those gradients, parts of the program can potentially optimize themselves. This is where the idea moves beyond an unusual execution strategy. Handwired's weights are initially produced by the compiler rather than learned, so the network begins by implementing the program that was written. But Cheng explicitly proposes unfreezing those compiler-created weights and training them. One of the project's demos already does this: its “Learned Gallery” compiles a photo-layout program, exposes adjustable weights, defines a loss based on the desired layout, and updates those weights live until the result better matches what the user drew. The important conceptual shift is that optimization does not have to start from random parameters and somehow rediscover the program. It can start from the program we already know and improve from there.

Fourth, this makes it possible for software to adapt differently to different people. Imagine that the fundamental rules of an application remain frozen, but particular parameters (layout, thresholds, ranking behavior, defaults, perhaps even pieces of a workflow) are allowed to adapt against an objective derived from how an individual uses it. Handwired does not yet demonstrate a general-purpose self-personalizing application, so this part is a direction rather than a result. But the mechanism is visible: the Learned Gallery changes its parameters in response to a user's desired layout, and Cheng explicitly suggests attaching a specific frozen program to a generic neural network and training the combined system end-to-end. That suggests an interesting alternative to today's personalization systems: instead of putting an AI model beside the application, parts of the application itself could become trainable while the rest remains fixed.

Finally, the biggest implication may be a new way of deciding what software actually is. We have traditionally separated programs, where humans specify behavior, from machine-learning models, where optimization discovers behavior. Handwired suggests a middle ground. A future program might contain things that are immutable, things that are differentiable, things that can be optimized, and things that can be learned from data, all inside the same computational object. Other systems such as JAX already show how compilation, vectorization, and differentiation can be composed as transformations of programs; Handwired makes the provocative move of starting with familiar imperative program structures and compiling them into that world. The result points toward software where we can specify what we know, preserve what must remain true, and optimize what we are willing to change.

These are really incredible days to be a builder. I hope this helped make some recent research accessible.

  1. A ReLU is just a very simple mathematical function:
    \( \text{ReLU}(x)=\max(0,x) \) ReLUs are useful because they are extremely simple, fast, and add the nonlinearity neural networks need to learn complex patterns. They also preserve useful gradients for positive inputs, which makes deep networks much easier to train. ↩︎
By 0 Comments

The Hierarchical Dirichlet Process Hidden Semi-Markov Model

In my work at DARPA, I’ve been exposed to hidden Markov models in applications as diverse as temporal pattern recognition such as speech, handwriting, gesture recognition, musical score following, and bioinformatics. My background is in stochastic modeling and optimization, and hidden Markov models are a fascinating intersection between my background and my more recent work with machine learning. Recently, I’ve come across a new twist on the Markov model: the Hierarchical Dirichlet Process Hidden Markov Model.

What is a Markov model?

Say in DC, we have three types of weather: (1) sunny, (2) rainy and (3) foggy. Lets assume for the moment that the doesnt change from rainy to sunny in the middle of the day. Weather prediction is all about trying to guess what the weather will be like tomorrow based on a history of observations of weather. If we assume the days preceding today will give you a good weather prediction for today we need the probability for each state change:

$$ P(w_n | w_{n-1}, w_{n-2},\ldots, w_1) $$

So, if the last three days were sunny, sunny, foggy, we know that the probability that tomorrow would be rainy is given by:

$$ P(w_4 = \text{rainy}| w_3 = \text{foggy}, w_2 = \text{sunny}, w_1 = \text{sunny}) $$

This all works very well, but the state space grows very quickly. Just based on the above, we would need $3^4$ histories. So fix this we make the Markov Assumption that everything really depends on the previous state alone, or:

$$ P(w_n | w_{n-1}, w_{n-2},\ldots, w_1) \approx P(w_n| w_{n-1}) $$

which allows us to calculate the joint probability of weather in one day given we know the weather of the previous day:

$$ P(w_1, \ldots, w_n) = \prod_{i=1}^n P(w_i| w_{i-1})$$

and now we only have nine numbers to characterize statistically.

What is a hidden Markov model?

In keeping with the example above, suppose you were locked in a room and asked about the weather outside and the only evidence you have is that that ceiling drips or not from the rain outside. We are still in the same world with the same assumptions and the probability of each state is still given by:

$$ P(w_1, \ldots, w_n) = \prod_{i=1}^n P(w_i| w_{i-1})$$

but we have to factor that the actual weather is hidden from you. We can do that using Bayes’ rule where $u_i$ is true if the ceiling drips on day $i$ and false otherwise:

$$P(w_1, \ldots, w_n)| u_1,\ldots,u_n)=\frac{P(u_1,\ldots,u_n | w_1, \ldots, w_n))}{P(u_1,\ldots,u_n)}$$

Here the probability $P(u_1,\ldots,u_n)$ is the prior probability of seeing a particular sequence of ceiling leak events ${True,False,True}$. With this, you can answer questions like:

Suppose the day you were locked in it was sunny. The next day the ceiling leaked. Assuming that the prior probability of the caretaker carrying an umbrella on any day is 0.5, what is the probability that the second day was rainy?

So if Markov models consider states that are directly visible to the observer, the state transition probabilities are the only parameters. By contrast, in hidden Markov models (HMMs) the state is not directly visible, but the output, dependent on the state, is visible. A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (or hidden) states. Each state has a probability distribution over the possible output tokens. Therefore the sequence of tokens generated by an HMM gives some information about the sequence of states. In this context, ‘hidden’ refers to the state sequence through which the model passes, not to the parameters of the model; the model is still referred to as a ‘hidden’ Markov model even if these parameters are known exactly.

OK, so what is a Hierarchical Dirichlet Process Hidden Semi-Markov Model?

Hidden Markov models are generative models where the joint distribution of observations and hidden states, or equivalently both the prior distribution of hidden states (the transition probabilities) and conditional distribution of observations given states (the emission probabilities) are modeled. Instead of implicitly assuming a uniform prior distribution over the transition probabilities, it is also possible to create hidden Markov models with other types of prior distributions. An obvious candidate, given the categorical distribution of the transition probabilities, is the Dirichlet distribution, which is the conjugate prior distribution of the categorical distribution.

In fact, it is possible to use a Dirichlet process in place of a Dirichlet distribution. This type of model allows for an unknown and potentially infinite number of states. It is common to use a two-level Dirichlet process, similar to the previously described model with two levels of Dirichlet distributions. Such a model is called a hierarchical Dirichlet process hidden Markov model, or HDP-HMM for short or it is also called the “Infinite Hidden Markov Model”.

The Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) is a natural Bayesian nonparametric extension of the traditional HMM. The single parameter of this distribution (termed the concentration parameter) controls the relative density or sparseness of the resulting transition matrix. By using the theory of Dirichlet processes it is possible to integrate out the infinitely many transition parameters, leaving only three hyperparameters which can be learned from data. These three hyperparameters define a hierarchical Dirichlet process capable of capturing a rich set of transition dynamics. The three hyperparameters control the time scale of the dynamics, the sparsity of the underlying state-transition matrix, and the expected number of distinct hidden states in a finite sequence.

This is really cool. If you formulate a HMMs with a countably infinite number of hidden states,
you would have infinitely many parameters in the state transition matrix. The key idea is that the theory of Dirichlet processes can implicitly integrate out all but the three parameters which define the prior over transition dynamics. It is also possible to use a two-level prior Dirichlet distribution, in which one Dirichlet distribution (the upper distribution) governs the parameters of another Dirichlet distribution (the lower distribution), which in turn governs the transition probabilities. The upper distribution governs the overall distribution of states, determining how likely each state is to occur; its concentration parameter determines the density or sparseness of states. Such a two-level prior distribution, where both concentration parameters are set to produce sparse distributions, might be useful for example in unsupervised part-of-speech tagging, where some parts of speech occur much more commonly than others; learning algorithms that assume a uniform prior distribution generally perform poorly on this task. The parameters of models of this sort, with non-uniform prior distributions, can be learned using Gibbs sampling or extended versions of the expectation-maximization algorithm.

So how can we use this?

A common problem in speech recognition is segmenting an audio recording of a meeting into temporal segments corresponding to individual speakers. This problem is often called speaker diarization. This is particularly challenging since you don’t know the number of people participating in the meeting and modified HDP-HMMs have been very effective at achieving state-of-the-art speaker diarization results.

Other interesting applications of HDP-HMMs have been modeling otherwise intractable linear dynamical systems which describing dynamical phenomena as diverse as human motion, financial time-series, maneuvering targets, and the dance of honey bees. (See this paper for more details. Results have shown that HDP-HMM can identify periods of higher volatility in the daily returns on the IBOVESPA stock index (Sao Paulo Stock Exchange). Most interesting to me was the application to using HDP-HMMs on a set of six dancing honey bee sequences aiming to segment the sequences into distinct dances.

You can see some other cool motion capture examples here.

By 0 Comments

Gradient Descent

[mathjax]

It has been awhile since I’ve studied optimization, but gradient descent is always good to brush up on. Most optimization involves derivatives. Often known as the method of steepest descent, gradient descent works by taking steps proportional to the negative of the gradient of the function at the current point.

Mathematically, gradient descent is defined by an algorithm for two variables, say \theta_0, \theta_1 as repeated updates of:

$$ \theta_j := \theta_j – \alpha \frac{\partial J (\theta_0 , \theta_1) }{\partial \theta_j } $$

from the hypothesis:

$$ \begin{aligned}
h_\theta(x) = \sum_{i=1}^n \theta_i x_i = \theta^{T}x.
\end{aligned} $$

The \alpha is the learning rate. If \alpha is very large, we will take some huge steps downhill, small \alpha would mean baby steps downhill. If \alpha is too small, it might take too long to get our answer. If alpha is too large, we might step past our solution and never converge. Besides the pitfall of picking an  \alpha , you have to have a cost function with existing derivatives (continuous) and a convex function.

Often for linear regression, we use batch gradient descent. In machine learning terminology, batch gradient descent uses all training examples. This means that for every step of gradient descent, we compare all residuals in the final least squares calculation.

Why is this relevant to machine learning? Of course there is always an analytical solution to any model, but this might involve a very large matrix inversion and be computationally infeasible.

$$ \theta = (X^T X)^{-1} X^T y $$

Gradient descent gets used because it is a numerical method that generally works and is easy to implement and a is very generic optimization technique. Also, analytical solutions are strongly connected to the model, so implementing them can be inefficient if you plan to generalize/change your models in the future. They are sometimes less efficient then their numerical approximations, and sometimes there are simply harder to implement.

To sum up, gradient descent is preferable over an analytical solution if:

  • you are considering changes in the model, generalizations, adding some more complex terms/regularization/modifications
  • you need a generic method because you do not know much about the future of the code and the model
  • analytical solution is more expensive computationaly, and you need efficiency
  • analytical solution requires more memory or processing power/time than you have or want to use
  • analytical solution is hard to implement and you need easy simple code
By 0 Comments