Study notes: automatic differentiation (part 1)

A few months ago, I came across the microgpt post by Andrej Karpathy, where he implements a GPT model from scratch, in “a single file of 200 lines of pure Python with no dependencies”. This is a super nice post, and something I was looking for - a bare-bones GPT model where nothing is hidden by libraries. My understanding of GPT models is hand-wavy, so I was excited to be able to step through everything, and understand the mechanics better.

Unsurprisingly, a good part of microgpt is dedicated to an implementation of autograd, that is, a version of automatic differentiation. The topic is not new to me (I have used the awesome DiffSharp before), but, as I looked through microgpt, I realized that, beyond the fact that it relies on the chain rule to propagate derivatives in composite functions, I was not entirely clear on how exactly that worked.

I also took a look at the nice series MicroGPT in F#, by Jonas Lara. That series starts by mimicking the original Python closely, which from a certain angle is great, and helped me some. However, I realized I was more interested in understanding automatic differentiation than in how it is implemented in microgpt, so I figured it was time for another of my side-quests: taking a stab at implementing autodiff from scratch, in F#, as a learning exercise.

This is, of course, rather pointless. DiffSharp already exists, and it is both very impressive and very complete. My goal here is not to replace it. I want to attempt to write a library from zero, try out ideas, see what works and what doesn’t, and learn from the mistakes as I go, hopefully gaining a better understanding of automatic differentiation in the process.

With that preamble out of the way, let’s get this side quest started!

Correcting an additive correction model

As part of a project I am working on, I ran into a small issue that, while not of consequence, bothered me. Being prone to obsessing over details, I ended up digging into it to figure out if I could address the issue. In this post, I will go over the solution I ended up with.

In a nutshell, here is the problem. Suppose you are working on an application where you need information such as “how long does it take to go from point A to point B”. You have an external service available, which you can call to get estimates. So far, so good.

Now suppose that you look at the data, and realize that the time it takes to go from A to B depends on when the trip takes place. This is not entirely unexpected. Roads are typically busier at certain times of the day, or certain days of the week.

To avoid getting bogged down in unimportant details, let’s simplify a bit, and ignore the time of the day part. You look at the data, and notice that trips taking place on different days of the week behave differently.

As an example, you might observe something like “on Mondays, trips take 1 extra minute on average than what the service predicts; on Sundays, trips take 2 minutes less on average.”

An easy way to model this would be to layer a simple correction on top of the estimate you obtain from the service, adding an error correction value (a bias term), based on the day of the week, along these lines:

let driveTime (origin, destination, dateTime) =
    // use the external service to get a baseline
    let estimate = averageDriveTime(origin, destination)
    // get a correction for the day of the week
    let correction = dayCorrection dateTime
    // apply the correction
    estimate + correction

So for instance, a trip predicted to last 7 minutes taking place on a Sunday would end up being corrected to 7 minutes - 2 minutes = 5 minutes. Converserly, the same trip happening on a Monday would be predicted to take 7 minutes + 1 minute = 8 minutes. Simple enough.

Drawing mountains: shadows

After a couple of weeks of hiatus (sometimes, actual work needs to get done), we are back to our pointless but fun weekend project: drawing mountains in a style similar to topographic maps, using shadows to hint at the relief. We are pretty certain that this must be a solved problem. We aren’t particularly interested in the result: this is more of an excuse to understand lights, and do a bit of geometry.

As a recap and a teaser, we left off with a simple illumination model, where the tiles that represent our terrain were lighter or darker, depending on how much direct light they received:

This isn’t too bad, but it misses an important element: the shadow cast by the mountains. After our latest changes, this is how things look - much more satisfying:

Drawing mountains: direct light

Now that we have are setup to draw SVG on a page with Bolero, we can go back to our main quest: drawing mountains in a style similar to topographic maps, using shading to hint at the relief. In this post, I will go over how I approached computing the effect of light on a terrain.

This post will be heavy on geometry, so let’s start with a teaser, showing the result first:

Drawing mountains: setting up Bolero

With a return to dungeon master duties, making maps has made a come back in my weekend activities, and I started revisiting an old side-project of mine, drawing mountains in a style similar to topographic maps. The aspect I am mostly interested in is not the contour lines, but rather the usage of shadows to visualize the relief.

My goal here is as follows: given a grid of altitudes describing a terrain, can I draw it and suggest the relief by rendering the shadows of mountains?

I am pretty certain that there must exist solutions to this. I am less interested in the result than in understanding lights and shadows. In other words, this project is entirely pointless, except as an exploration exercise!

In aprevious series of posts, I used SVG to draw geometric figures and found it reasonably enjoyable, so that’s what I decided to use.

One aspect of that previous project wasn’t very pleasant, though: the process of generating documents by manually running a scripts to create a html file, and opening it it the browser to see the results. So I figured I would try something different, and use this as an excuse to give Bolero, the F# WebAssembly library, a spin.

Initial setup

The setup of Bolero was completely straightforward:

• install the template,
• create a project, using the --minimal option,
• start the server with dotnet watch run,
• go to the browser, a basic elmish app is running, with hot-reload.