Study notes: automatic differentiation (part 2)

In my last post, I began my side quest into automatic differentiation, trying to implement it from scratch as a learning exercise, in F#, to understand how it works.

In part 1, I decided to start with the smallest relevant problem I could think of, computing the derivative of a function of a single value. Once we get that figured out, we will move to bigger functions.

My first take was to model functions as expressions, using an F# discriminated union. This was a useful exercises. First, it worked! I ended up with a function diff that correctly evaluated the derivative of a function. Then, implementing it gave me a chance to refresh my mind on the mechanics of derivatives.

There are a few things I didn’t like about that take. First, it requires writing functions as expressions, essentially using a DSL, which is a bit awkward to use, and not ideal for extensibility. Then, it does not handle composition very well. Ideally, I would like to be able to compute the derivative of a derivative, and so on. I can achieve that by modifying my initial code a little, but that modification is essentially symbolic derivation, which is, as I understand it, not automatic differentiation.

So let’s go back to the drawing board, with take 2.

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: