# Looking for “average” of two permutations

I am a computer programmer and I am building a search engine for a client. Right now I am puzzling myself about the order in which I should return search results. There are two obvious orderings:

• Relevancy - Documents that contain most overlap with the query text first.
• Popularity - Documents that are more popular first.

Both of these orderings are too extreme, I would rather have something that is "right in the middle of both of them". Is there any mathematically significant middle ground between these orderings?

Let's take a slightly more mathematically rigorous stab at it.

• Let $D$ be the set of all documents returned in a given search
• Define a relevancy function: $rel:D\rightarrow\mathbb{R}$ that imposes an ordering upon $D$
• Define a popularity function: $pop:D\rightarrow\mathbb{R}$ that imposes an ordering upon $D$
• Define a mixture function: $mix(d;\alpha)=\alpha\cdot rel(d)+(1-\alpha)\cdot pop(d)$

The goal, then, is to determine $\alpha$ such that the ordering imposed upon $D$ by $mix$ is at the "special, magically, just right point" between the ordering imposed by $rel$ and the ordering imposed by $pop$. (Admittedly, my mathematical rigor has broken down here just a bit.)

Thinking naïvely about this, $\alpha=\frac{1}{2}$ seemed to be a good choice, but then I realized that this doesn't take scaling into account at all. For instance, if $pop$ maps $D$ to a much broader range of values than $rel$, then it's possible that the $mix$ ordering will be identical to the $pop$ ordering!

So is there any "sweet-spot" for $\alpha$? Is there a way to determine it? The one I'm visualizing right now has to do with the permutation matrices that map the $rel$ ordering to the $mix$ ordering, (denoted $P_r$), and the permutation matrices that map the $pop$ ordering to the $mix$ ordering, (denoted $P_p$). If $\alpha=1$ then $P_r$ is the identity matrix and $P_p$ is "as scattered as possible". If $\alpha=0$ then $P_r$ is "as scattered as possible" and $P_p$ is the identity matrix. Is there some value for $\alpha$ that balances these two extremes, so that $P_r$ and $P_p$ reside as close as possible to the identity matrix without hurting the other? Is there any other notable points between the $rel$ and $pop$ ordering that I haven't considered?

-
"For instance, if pop maps D to a much broader range of values than rel, then it's possible that the mix ordering will be identical to the pop ordering!" This is perhaps desirable. If all your pages have basically the same relevance, then you ought to be basing your decision primarily on popularity. If, in general, you value popularity and relevance equally in deciding whether a page is "good", then $\alpha = \frac{1}{2}$ seems to be the only choice. – Austin Mohr Aug 13 '11 at 23:55
-@Austin Mohr - The problem, though, is that the scaling of the $pop$ function is arbitrary. You might be right, but I think that in general my "sweet-spot" described in the last paragraph is the best-bet. Of course, all rigor has gone out the window at this point, so perhaps what I want is an enumeration of all the "interesting" points between $\alpha=0$ and $\alpha=1$ - all the interesting points between these two orderings. – John Berryman Aug 14 '11 at 0:05
Perhaps you can first normalize your data so that all values from $pop$ and $rel$ are between 0 and 1, then average these two normalized scores. – Austin Mohr Aug 14 '11 at 0:15
This comment has very little to do with the math. Presumably your client is interested in certain kinds of searches. Pick a few of them. Try different ordering functions. Ask the client which ordering seems to be close to what the client wants. Probably the result will need fine tuning. – Jay Aug 14 '11 at 0:32
You may need to provide an override so that the "top $6$" (or whatever) in either category appear quite early on. – André Nicolas Aug 14 '11 at 1:21

One crude but possibly effective solution might be to rescale $rel$ and $pop$ so that, say, the most relevant/popular document gets the value $1$, the next on each scale gets the value $2$, and so on. Then do your averaging thing.
A slightly less brutal adjustment would be to linearly scale $rel$ and $pop$ so that they each have the same mean and variance. (Basically, you subtract the mean and divide by the standard deviation.) This can still fail if the higher moments of the distributions are very different, but it might work well if both $rel$ and $pop$ can be expected to be more or less similarly distributed after scaling.