# Tracking the progress of a distribution

# Tracking the progress of a distribution

I've been super busy lately, with work, a baby, and house hunting. Fun projects will have to take a back seat for now.

But! I recently found an opportunity to exercise some basic linear algebra when working on a metrics problem. It's simple enough to write up in the moments between house showings and baby duties.

To anonymize the domain,
let's say we're working with
sheep colored white, green, or purple.
You start with a flock of `n`

sheep,
each of which may be any of the three colors.
You're given a target distribution
`(p_1, p_2, p_3)`

over colors `(white, green, purple)`

,
and you want to make your flock
have that distribution of colors.
You can paint your existing sheep,
and/or buy new pre-painted sheep
in a desired color,
or sell sheep.

However, the operations you make to improve the flock's distribution toward the target aren't your only task. You're a busy shepherd, after all, and you can't spend all your time painting sheep. Still, you want to track how much progress your making each day, and show a metric that describes how well you're directing the (possibly small) effort you're spending on improving the color distribution.

The problem is how to measure "progress" faithfully in this situation. On one hand, you could use a statistical measure like total variation, or KL-divergence, or Euclidean distance between the current distribution and the target distribution. But these measures are agnostic to the size of the underlying flock.

For example,
if you used total variation distance,
and started with a flock of `(10, 15, 24)`

which has distribution `(0.204, 0.306, 0.490)`

,
and your target distribution was `(0.3, 0.6, 0.1)`

,
then the total variation distance is `0.39`

.
If you add a white sheep and a green sheep to the flock,
you get a distribution of `(0.216, 0.314, 0.470)`

,
which has total variation distance `0.37`

from the target,
an improvement of `0.02`

.
We spent effort perfectly:
all the operations made had a maximal impact
on improving the distribution.

Now scale the flock up by 100,
and start with `(1000, 1500, 2400)`

.
Add one white and one green sheep,
and you only improve the total variation by `0.00019`

,
even though your effort was still spent perfectly.
The damn statistic makes us look bad!

All the statistical distance measures I'm aware of
have the same problem.
The reason is because these comparisons
are of *distributions*,
and so they are not allowed to know
about the underlying populations
that the distributions represent.

What we need instead
is some way to measure progress
toward the target distribution
relative to the amount of progress
that *could* have been made
if we theoretically directed our effort
as much as possible toward improving the ratio.

When I thought about this, at first I was stuck in "statistics" land, and came up with a bunch of crappy measurements that were various ratios of ratios. Some examples showed that they weren't easy to interpret.

Then I realized (embarrassingly late) that the population itself is a vector, and so I can use basic linear algebra to measure distances of population vectors. From there a sensible approach felt obvious.

Let `R, S`

be two length-n tuples
of positive integers
representing the population vectors
before and after some change is made.
Let `M_R`

and `M_S`

be the sum
of the entries in `R`

and `S`

, respectively,
representing the total flock size before and after.
Let `T = (t_1, ..., t_n)`

be the target distribution.

Then define the
*relative improvement of S from R toward T*
as follows,
where `norm()`

denotes the usual Euclidean (L2) norm
and `proj_T`

denotes the vector projection onto `T`

:

```
improvement =
(norm(proj_T(R) - R) - norm(proj_T(S) - S))
/ norm(S - R)
```

In lieu of a picture,
imagine the target distribution vector
spanning a line in n-dimensional Euclidean space.
This line represents all population states—for
all possible flock sizes (even non-integer)—that match
the target distribution perfectly.
Then `proj_T(R)`

describes
the closest ideal population state vector
for a given state vector `R`

.
Note the projection `proj_T(R)`

will always have
norm at most `norm(R)`

,
but may have a larger flock size (L1 norm).
Finally, `norm(proj_T(R) - R)`

is how far
a given state is from ideal (error),
and the improvement formula above
subtracts the error of the "after" state
from the error of the "before" state,
and divides by the distance between the before and after states.

Geometry makes analyzing this formula easy.
It must always be between -1 and 1,
because at best you can place `S`

on the line between `R`

and `proj_T(R)`

,
in which case the numerator is equal to `norm(R-S)`

and the improvement is 1.
Conversely, the worst you can do is move straight away
from the target, and the improvement is -1.

This hints that the improvement formula
actually computes the cosine of the angle
between `S-R`

and `R - proj_T(R)`

.
It's easy to prove.
View `S-R`

as the hypotenuse of a right triangle.
One base lies along `R - proj_T(R)`

and has length
`norm(proj_T(R) - R) - norm(proj_T(S) - S)`

.
The improvement ratio computes
the ratio of base length to hypotenuse length,
i.e., the cosine of the desired angle.

My intended application of this metric is boring. It has to do with computers in data centers. But it could be useful in more situations. Imagine a recommendation system with a target distribution over recommendation categories like "revenue gaining" and "exploratory." Progress is relative to the number of recommendation opportunities. Or imagine a hiring system in which you want to ensure you're receiving resumes from enough applicants from historically disadvantaged groups. Progress is relative to the amount of money you spend on recruiting efforts.

I haven't used this metric in practice yet, so I can't say whether it works well even for my intended application. There's the possibility that for state vectors starting close to the ideal line, progress will look wonky because you'll have no choice but to overshoot. You can alleviate that by adding error bars around the ideal, inside of which you don't track progress at all.

But mostly it *feels* right
compared to the less coherent formulations
that preceded it.
The geometry also provides a nice framework
with which to reason about its behavior.
This means I spend less effort justifying
the metric to skeptical stakeholders.