On the margins

Quick, spot the miss in the following derivation:




It's not super obvious. And, truthfully, it doesn't actually make any difference worth noting. However, a PhD dissertation is your chance to get things really right, so being picky is in order.

The problem with this derivation is that we take as the probability that a block partition comes from partition m as the ratio of the rows in partition m to the total rows. That's not a bad approximation but, the rest of the formula is really specific, so approximating this term isn't appropriate.

It should be the marginal distribution, P(m|k), rather than just P(m). For a given value of m, that's quite different. In total it washes out a bit, but not completely.

This is the sort of semantic stuff that I'm not super good at. It's not that I don't think it's important; it's just that I tend to miss these things. I hope my adviser is good at catching them.

Anyway, I've updated the sampler to reflect the correct term.

A lotta work for nothing

Alert readers will recall that a week ago I spent the better part of two days sorting through derivations to find a term that almost always evaluated to zero unless you blended the estimators - then it was not anything like zero.

Well, it's back, but in reverse. Now, since I'm not blending estimators in my most general case, I do want the term. It still comes out to pretty much nothing, but I don't want reviewers pinging me for dropping terms just because I don't think they matter. I still do drop terms, but I'm being very careful about making sure they really are insignificant. I've wasted too much time chasing down bad assumptions.

FWIW, here's the term:




I do drop a couple terms in the third step because the hit rate and mean observation aren't supposed to change from one partition to the next so their variance should be very close to zero, especially with large row counts. That's an assumption and I could get called on it, but since I call it out myself in the paper, I'm OK with it.

My point is...

This is not the progress my adviser was likely hoping for today as I said I'd have actual results on Monday. But, while the morning has not produced any such results (or even done much to forward that effort), it has provided a significant revelation, that should help in wrapping all this up.

People have been asking me what my paper is about. I've been having a lot of trouble answering that because the topic has shifted so many times. Frankly, when I read the first part on the uniform sampling and then look at the second part with the generalizations, it looks a bit scattered. This was brought to my mind when my adviser suggested we just use the empirical distribution of the partition parameters to construct the sum directly and then get the variance of that rather than using the block sums. For reasons I couldn't put my finger on, that seemed horribly inconsistent with the rest of the paper. Not inconsistent in the sense that it contradicted anything; just that it didn't fit.

This morning, while making a few false starts on implementing the general block variance computation, I thought more about why I wasn't keen on using the total sum. There are some technical ramifications that I'd have to work through, but they aren't a big deal. I then realized why it doesn't fit.

This paper really isn't about the sum. It's about the block variance. If we know the block variance, we can always get the variance for an estimator for the population. More importantly, in the finite sampling case, this is true for any estimator. The sum is just a convenient choice to demonstrate the technique.

Viewing the paper through this lens, the title becomes a bit more obvious (something like: Estimating Query Values from Finite Multi-dimensional Populations using Blocked Sampling). The comparison with the BMH and BLB algorithms to estimate the block variance is suddenly a sane thing to do. The introduction explaining why one would even use blocks rather than true iid sampling fits. And, though I haven't written it yet, the conclusion can talk about future research where we don't just consider sums, but generic population parameters estimated by repeatedly sampling blocks.

Most importantly, this points the way for proceeding to the real problem I want to solve: self-tuning multi-dimensional data stores. The objective is the restructure the data so the block variances are minimized. A secondary objective would be to make them easy to compute. I've already got quite a bit of work done on both of those.

Back to earth

It's been a crazy few days at work (actually, normal by the crazy standards of my group this time of year, but crazy by any normal standard). Anyway, it's prevented me from acting on the previous post.

And, that's probably a good thing.

I had another meeting with my adviser today and we both agreed that the whole rx4-dimensional space was just a bit nutty. So, we're going to frame this in less grandiose terms. We'll still create a 4-dimensional kernel distribution, but we won't blow it out for every partition. Instead, we'll just sample from that and estimate the block variance. My adviser would like to go even beyond that and just directly sample the total sum variance, but I'm still lobbying for the block variance. I'm pretty sure I can show that it's equivalent, both theoretically and in terms of computational effort. Sticking with block variance gives us a consistent measure of spread throughout the paper.

I've got until Monday to make my case. It's time to wrap this thing up.

New method

Oh, brother, here I go again reframing things just when the finish line is in sight.

At my weekly meeting with my adviser, he was understandably skeptical of my plan to us an MCMC chain to generate a distribution across all the vectors for the partition parameters. Given 1000 partitions (which actually isn't very many), it is a 3000-dimensional space. I'll concede that's a heavy lift, though my thought was that even a very sparse approximation would still converge. I, of course, have nothing but gut feel to back that up.

Then, as I was staring at the blackboard, it hit me. There's no reason all these things need to be estimated at once. We've already said that in the general case we are assuming no direct correlation between partitions. They may exist, but we don't assume as much.

So, that means that we could partition the partition space and estimate the groups of partitions separately. Then, we just need a way to glue all those back together into one empirical distribution of the block variance. My adviser liked that idea and I left the meeting thinking that should be easy enough to do.

Then the revelation hit me: it's already been done! That's essentially what the Bag of Little Bootstraps algorithm does. All the theory has already been worked out. Better yet, I already have a section in my paper adapting the theory to my use case. It's not a slam dunk because I was showing how it operated in the uniform case and explicitly called out how it fails miserably in the correlated case. But, that's because we were measuring the wrong thing. Applied to the partition statistics rather than the individual rows, this should work.

It does mean I have some more proving to do. Simply showing that it works on simulated data sets won't cut it. But, the proof of correctness in the original paper is fairly straightforward. I should be able to follow the same path to show it works in this case.

The downside, of course, is that I just set myself back another week. This is the first time I've felt like it will be worth it.

Theory and practice

Agree! Finished up the empirical results for the correlated hit-rate sampler last night. (My observation of a day off each week is the traditional sundown-sundown, so it's OK to work Sunday night, even Easter Sunday.)

As you can see, even for small sample sizes, the rejection rate is very close to the desired 5%. On to the full general case.

John smokes Peter in the inaugural Ressurection 5K

I may get some angry emails for making light of the resurrection, but I figure everybody who cares about such things has already had time today for serious reflection on the paschal mysteries. Today's lectionary from John would seem to indicate that running is, indeed, a thing:

So Peter and the other disciple [that's John, who has a strange aversion to first-person narrative] went out and came to the tomb. They both ran, but the other disciple ran faster than Peter and arrived at the tomb first; he bend down and saw the burial cloths there, but did not go in. When Simon Peter arrived after him, he went into the tomb and saw the burial cloths there, and the cloth that had covered his head, not with the burial cloths rolled up in a separate place. Then the other disciple also went in, the one who had arrived first, and he saw and believed.

Those who study scripture know that the tradition is that when a point is really important, it gets stated three different ways. There's a good reason for that. If you tell something once and it's misheard (remember, we're talking oral tradition here, none of these folks had a bible at home), you've given them bad information. If you tell it twice and they mishear once, you've given them conflicting information. If you tell it three times, you've at least given them a preponderance of statements to sort it out. It's basically the ancient equivalent of a checksum bit.

So, it appears that in writing about the most important event in Christianity, John really wanted us all to know that he dusted Peter running to the tomb. John wrote his gospel sometime between AD 85 and 95, so this is basically a 90-year-old giving a race report from his 20's. As the saying goes, the older I get, the better I was.