For background on the Yellow Brick Half-Plane that a normal human could conceivably care about, see our previous post on how we’re killing the custom lane widths feature. This post is strictly for abnormal humans, and/or, more realistically, for ourselves, because math is fun, and for our future selves, as documentation of how we (i.e., Uluc) worked this all out.
Let’s dive in with some terminology. In the Yellow Brick Half-Plane New World Order, yellow brick roads have no thickness. We call them razor roads.
The Days-To-Derail (DTD) function takes a yellow brick road and a (time, value) datapoint and gives the amount of safety buffer AKA the number of safe days. Every point on the good side of the road maps to an integer number of days greater than or equal to 1. (Shortly we’ll generalize that to the reals but bear with us.) Every point exactly on the razor road maps to 1. You will derail tomorrow if you’re exactly on the road today (and don’t report new data). Any point on the wrong side of the road maps to 0. You will derail today at your deadline if you are still on the wrong side of the road.
Level curves (AKA isolines) refer to curves along which a function has the same value. The boundaries between color-coded regions on the graph indicating how much safety buffer you have are coincident with level curves of the DTD function. The level curve for DTD=0 is the razor road itself — the boundary between 0 and 1 days of safety buffer.
Pessimistic Presumptive Reports (PPRs) normally refer to a specific Beeminder feature for do-less goals but here we’re generalizing the concept. Conceptually, a do-more goal has PPRs of zero because if you don’t report data on a do-more goal then your graph flatlines. So here when talking about PPRs we mean them in the general sense that applies to all Beeminder graphs.
Yellow Brick Roads are defined as piecewise-linear functions and we need a name for the points where the slope changes. The mathematical term “inflection point” is commonly abused to mean any sudden change in slope of a graph. The actual mathematical term we want is “second-order discontinuity” or “critical point”. As is also common in math, we’re using the word “kink” since its primary definition — “a sharp twist or curve in something that is otherwise straight” — captures intuitively what we mean. (Yes, we feel slightly weird about it.) If the kink is a transition from positive to negative slope we call it a peak and for negative to positive, a valley. Most kinks are just sudden changes in slope, neither a peak nor valley.
Finally, we refer to do-more and do-less goals here but everything we say about do-more goals generalizes straightforwardly to weight-loss goals where the sign of everything is reversed.
And everything we say about do-less goals generalizes to rationing goals where the road goes down and you need to stay above it.
More technically, when referring to do-more goals we really mean goals with yaw*dir > 0 (Platonic types MOAR and PHAT) and everything we say about do-less goals generalizes to yaw*dir < 0 (Platonic types WEEN and RASH).
More on that in
the API documentation.
The Mathy Meat
In principle, you can compute days to derailment by simply stepping forward day-by-day along the PPR direction until you reach the road. This works fine for figuring out the current safety buffer for the user’s current datapoint. But in the Yellow Brick Half-Plane New World Order we’ve replaced the concept of lanes of the road with color-coded regions for how much safety buffer you have. (Again, DTD=0 is red, DTD=1 is orange, DTD=2 is blue, DTD≥3 is green, and DTD≥7 is… we’re not sure yet but in the examples below we’ve gone with dark green.) So we need a much more efficient, elegant, and continuous algorithm. You can’t do the step-forward algorithm again and again for every point in the (half-)plane!
The idea for this algorithm comes from the observation that just like we can move forward along the PPR direction from any given point on the graph, we can also move backwards along the PPR for points on the road. Doing this would yield a mechanism for pre-computing the DTD value for every point on the graph. That’s not practical but at least lets us visualize the DTD field. In particular, we define the DTD function as follows:
DTD: R2 → R+
such that for any [t,v] in R2, DTD([t,v]) yields days to derail as a positive real number.
The following image illustrates how this backward propagation is done for a do-less goal where the daily PPR rate is twice the road slope. The black line is the razor road, red lines are along the PPR vector, and crosses indicate increasing integer steps for the PPR.
Here is a more complex do-less road with both negative slopes (for which PPR=0), and flat segments (for which PPR=2 per current Beeminder convention).
An important observation in these graphs is that the line below each kink in the road is divided into segments, each of which result in derailment by hitting one of the road segments that come afterwards. The first region derails in the road segment that immediately follows. The second region derails two segments ahead, the third three segments ahead, and so forth. This is illustrated with the blue ellipses and arrows in the above graph.
This suggests an efficient representation for these back-propagated PPR lines as simple piecewise uniform regions below every kink in the road. We call this the DTD array, which stores, for every kink in the road, a sequence of vertical coordinates and associated DTD values corresponding to the boundaries of these uniform regions. For the second example above, the DTD array looks like this:
[
[x=30, [y=10, dtd=0], [y=8, dtd=1]]
[x=20, [y=5, dtd=0], [y=0, dtd=10], [y=-2, dtd=11]]
[x=15, [y=7, dtd=0], [y=5, dtd=5], [y=0, dtd=15], [y=-2, dtd=16] ]
[x=7, [y=1, dtd=0], [y=-5, dtd=8], [y=-7, dtd=13], [y=-12, dtd=23], [y=-14, dtd=24] ]
[x=0, [y=0, dtd=0], [y=-1, dtd=7], [y=-7, dtd=15], [y=-9, dtd=20], [y=-14, dtd=30], [y=-16, dtd=31] ]
]
The array starts from the last kink in the road since that makes it easier to generate the array. Also note that since the last road segment is considered to extend indefinitely into the future, only one day ahead of the kink is recorded. The remaining days can be inferred linearly from the slope.
A similar construction works for do-more goals, where PPR is always zero, with the PPR extensions going back in time towards the left as shown here:
It’s interesting that do-less goals always end up with all backward PPR extensions remaining on the good side of the road, with no intersections between them since the PPR slope is always below the road slope by construction. This is, however, not true for do-more goals. For example:
The PPR extensions for parts of the road with negative slope both traverse the wrong side of the road and overlap earlier regions of the PPR extensions. This poses substantial problems for efficiently constructing the level curves for the DTD function.
For do-less goals, simply connecting points along these lines with the same DTD value yields level curves for the DTD function:
We still need a computationally efficient way to construct these level curves though. Fortunately this is possible by seeing that these level curves are piecewise linear, and their kinks occur either at the same horizontal coordinate as the kinks in the road, or sideways connections between successive DTD array components. In the figure above, the black circles indicate components of the DTD array along each road kink. Notice that the kinks of the piecewise linear curves occur either along the vertical lines aligned with the road kinks, or along the lines connecting the ith DTD array to the corresponding segment of the i+1st DTD array. Starting from the rightmost road segment, this lets us go iteratively leftwards, back in time, to construct the level curve associated with a particular choice of DTD =some constant. An example of this construction is illustrated by the green circles in the figure above for DTD=3, following the ranges within the DTD array containing DTD=3.
Applying the same algorithm to do-more goals works similarly, but only when there are no segments with negative slope:
(Why would a do-more goal have negative slope? Hush, we’re doing math here. Also, it totally does happen and we’re pretty sure if we didn’t get this right in its full generality it would bite us hard.)
The resulting level curves are much simpler than do-less goals, being simply left-shifted versions of the road itself. That’s because the back-propagated DTD lines are all parallel and extend leftwards. Unfortunately, this does not yield correct results for do-more goals with negative slopes:
The Home Stretch, with Garish Graphs
Even if we hide the parts of these level curves that fall below the road, the peaks mess up the colored regions:
Aside! Don’t panic about how weird these graphs look! At least for the initial launch of Yellow Brick Half-Plane we’re mimicking the existing yellow brick roads as closely as possible by just drawing thin lines at the boundaries of these colored regions. Shading the whole regions makes a ton of sense conceptually and we may do that later, especially if we can find a way to make it look less garish than these examples!
Colored regions to the left of the peaks in the road should not also have peaks but should be smoothed out like so:
We solve this by filtering the level curves after running the above algorithm for do-more goals. Namely, for each peak in the road, we enforce a flat section on the level curves before and after the peak, terminating after DTD days (whatever the DTD value is for the level curve we’re computing) or at the next valley, whichever comes first. After that, it falls back to the unfiltered level curve and continues. We think of it as a monotonicity filter even though the level curves can have negative slope after peaks, as seen above.
We have to be especially careful when these flat regions overlap, handling various edge cases. The following figure illustrates some of these special cases, particularly for the light green region which corresponds to DTD=6:
Phew! That was way more than you wanted to know but, well, correction, that was way more than almost everyone wanted to know and so they didn’t read it. But you did so you must’ve wanted to know and we sure are touched! But in case you skimmed over all this and are just now rejoining us, let us reemphasize that the graphs won’t actually look like above when we ship this. This is the theory behind it. And it’s going to be amazing! Well, from our perspective it will be amazing. From your perspective, as a normal user, it will almost seem like nothing happened. Rest assured that a ridiculous amount of work is going in to make it seem that way! In fact, this whole post is just one small piece of it.
Image credit: Faire Soule-Reeves