distributional complexity

I have been idly thinking about how to describe an algorithm such as triple-u sampling.

Although it may use randomness, I would imagine you could also use a low-discrepancy sequence to do at least as well. As I mentioned before, such an algorithm thinks explicitly about taking as input a distribution, making a number of decisions by reasoning probabilistically, and then trying to output a sort of probability distribution. And yet, just as the word random makes you focus only on the power of random choices, to me, "probabilistic" is not only tricky to say but focuses on the probabilities of a single event or set of events.

Instead, I wonder if "distributional" nicely draws attention to the algorithmic aspect of thinking of distributions of inputs, distributions of decision theoretic choices (hyperplanes and all that), and distributions of outputs as well.

More simply, it's easier for me to say than probabilistic and it doesn't rely on randomness, so why not :)

Another little win that comes from this verbal-conceptual frame is that it might make its users think about distributions of said distributions (besides suggesting the use of randomness and probability theory, through wording alone, which doesn't happen if you focus on random bits or probabilistic events/existence as your frame).

More specifically, I was thinking today that it seems reasonable to try to study the distribution of distributions output by a triple-u ranking.

Let's say a ranking algorithm outputs an ordinal ranking (web page A is the alpha hit when yoohoo searching for some term, and web page B is the beta hit, and so on). Given that ordinal ranking, users click on the alpha hit with some probability and the beta hit with some other probability, and so on.

This user behavior, then, leads to a kind of transfer function which distributes some abstract resource -- eyeballs, clickity counts -- according to some user-based probability distribution function. In other words, the supposed ordinal ranking scheme, when convolved with user preference, really leads to a cardinal ranking in our little search engine-that-could problem.

Stepping back, you might find this a bit academic, but let's remember that the search-engine-that-could pretty much always has its own notion of cardinal ranking, which is then converted to an ordinal ranking when shown to the users. Not a problem, but note that the cardinal ranking (let's call it R_user) induced by user behavior is generally not the same as the cardinal ranking that the search-engine-that-could has in mind.

Can we say, tragedy of the ecological-web-disaster waiting to happen? Is it just us, or is the web trashier than it was before the turn of the century? I think it took a while to see this happen, as search engines got good but the web got worse (here and there), and perhaps not so many people stopped to think about how much search engines contributed to these problems of comment/email/MyPeople spam and search engine gaming.

But, perhaps I exagerrate, who knows. Where are the HTTP web ecologists anyway?

Back to distributions over distributions. I think it ought to be possible to reason over a distribution of distributions, and argue that the resulting "expected" distribution (is there a formal term for this?) is better than any single, deterministic distribution.

In other words, a distributional algorithm that outputs a series of ordinal rankings should generally do better than a deterministic algorithm that outputs only a single ordinal ranking, when you consider a distribution over the outputs.

More specifically, let there be some function F which gives you a cardinal ranking given some ordinal ranking. When you apply F individually to each ordinal ranking in a distribution of rankings, the expected distribution of F should, in general, be somehow more "justly" distributed than any single distribution of F applied to a single ordinal ranking.

("Just" is determined by the distributional algorithm, but I suppose it's easier to just imagine that the distributional algorithm has some idea of what is "fair", but is constrained to output an ordinal ranking. By analyzing what happens "in the limit" over a number of ordinal rankings, I imagine that we could show that the algorithm can in general do much better in matching the expected cardinal ranking to the idealized one.)

Does that make sense? I think it does, but I'm still formalizing these ideas, and playing fast and loose with probability distribution functions versus cardinal rankings and ordinal rankings, but it seems to make sense.

Given a set of output probability distributions, we ought to be able to think of "layering" one distribution over another like area-preserving dough, and just normalize the resulting sum of distributions to some hypothetical, expected distribution of doughy goodness.