Probability estimates for pairwise majority votes

Question

This is related to the rank aggregation question I asked previously.

I have items $I_1, \ldots, I_N$ and the observations of a number of pairwise trials which pit pairs $I_i$ and $I_j$ against eachother and select a "winner". Let $W_{ij}$ be the number of times i beats j.

Note that the number of trials between i and j is very much dependent on i and j: In some cases there may be none, in some there may be very many.

I am trying to estimate a matrix $P_{ij}$ corresponding to the probability that i beats j in a trial (I consider $P_{ii} = \frac{1}{2}$ for convenience reasons). My current, somewhat unprincipled, approach is a bayesian average

\[ P_{ij} = \frac{ \frac{1}{2} S + W_{ij} }{S + W_{ij} + W_{ji}} \]

where S is some smoothing constant (I currently have S = 5). This corresponds to a bayesian approach with a prior for $P_{ij}$ of $\beta(\frac{1}{2}S, \frac{1}{2}S)$ and then taking the expected value of the posterior distribution.

My problem with this is the following:

This is effectively treating each pair i, j as independent, whereas in fact we "believe" that there is a consistency between them. In particular if i tends to beat j and j tends to beat k, this should count as evidence that i tends to beat k even in the absence of pairwise trials between i and k.

There may be circumstances where we have very many trials for i, j and j, k and conclude that both $P_{ij}$ and $P_{jk}$ are high, but we have very few trials for i, k and thus conclude that $P_{ik}$ is very close to $\frac{1}{2}$ (possibly even concluding it's less than $\frac{1}{2}$ if e.g. there was only one trial and it had a surprising result). This is non-optimal.

So I'd like some sort of reasonably principled way of introducing intermediate results as evidence that the majority prefers one to the other. There are various plausible sounding things I could try, but I'd like to do this "properly" if at all possible, and most of my ideas involve more hand waving than solid mathematics.

One example of something plausible but possibly nonsensical I'm considering trying is iterating an expand/collapse process of:

Expand: $P \to P^2$

Collapse: $P \to Q$, where $Q_{ij} = \frac{P_{ij}}{P_{ij} + P_{ji}}$

The idea being that we inflate probabilities where there are a lot of large intermediate results and then collapse down to the symmetry condition that $P_{ij} + P_{ji} = 1$.

This seems to produce semi-tolerable results (I've not tested extensively yet), but it's not actually clear to me that this process converges or why it should work.

Suggestions?

Edit:

On having thought about this a little more carefully, I think the following may capture what I am trying to achieve:

I want to assume that there is some distribution on the permutations of 1..N, with a strong prior belief that this distribution is close to uniform, and that each pairwise trial consists of sampling from this distribution and comparing the positions of i and j.

Answer 1

The way I would introduce dependency in the modeling of the process is using Markov random Field, i.e assuming that

$$P(W_{ij}=w_{ij}|W_{kl}=w_{kl}, \; (k,l)\neq (i,j) )=P(W_{ij}=w_{ij}|W_{kl}=w_{kl}, \; (k,l)\in \mathcal{V}(i,j) )$$ where $\mathcal{V}(i,j)$ is a neighborhood of "$(i,j)$" (seen as a point in the lattice $\mathbb{Z}^2$. In your problem, I don't know if there is a natural ordering of not, however, you can say that $\mathcal{V}^{(1)}(i,j)= ( (k,l): k=i \text{ or } l=j )$ I am sure you can do something that integrates more knowlegde on the topology of your questions... for example, if there is an ordering $\mathcal{V}^{(2)}(i,j)= ( (k,l): |k-i|+|l-j|\leq 1)$.

The nice thing about this modeling is that your prior (on the whole $W=(W_{ij}))$ can be written in terms of a gibbs distribution:

$$P(W=w)=\frac{1}{Z} e^{ U(w)/T } \;\;`\text{ with } U(w)=\sum_{c\in \mathcal{C} }V_c$$

\mathcal{C} denotes the set of cliques the graph modeling your topology, $U$ is called energy function, and each $V_c$ is an function with the property that $V_c(w)$ depends only on those coordinates $x_s$ of $w$ for which $s\in c$. If you use $\mathcal{V}^{(2)}$ thi will be the Ising model (if I am not mistaken ? )

If you are interest in this (in particular if you want a more rigorous detailed treatment of what I said), and in the associated estimation procedure, I suggest you reading the Paper of Geman and Geman that introduced that type of treatment http://portal.acm.org/citation.cfm?id=85346 . There are however thousands of book and paper about that, especially in image processing.

Hope this helps !

Answer 2

This is how I would approach the problem:

Let $\theta_{ij}$ be the probability that i beats j and let $w_{ij}$ be the number of times i wins over j in $n_{ij}$ trials. Then, the likelihood function is:

$P(w_{ij}|n_{ij}, \theta_{ij}) = B(n_{ij},w_{ij})$ $\theta_{ij}^{w_{ij}}$ $(1-\theta_{ij})^{n_{ij} -w_{ij}}$

Choose a beta prior for $\theta_{ij}$ and your posterior for $\theta_{ij}$ would be a beta distribution. Hope that helps.

Answer 3

Now that I understand your question better, here is another attempt:

Let $S_i$ be how strong item i is intrinsically. In a competition between items i and j the probability of i winning will depend on $S_i$ and $S_j$. For simplicity, let us assume that:

$\theta_{ij} = S_i / (S_i + S_j)$

Use the likelihood ideas as I outlined earlier but now estimate $S_i$ instead of $\theta_{ij}$. Obviously, you will now need to include all trials in which i participated to estimate $S_i$ which I think takes care of the non-dependent nature of your dataset.

You can of course take different functional forms that relate $\theta_{ij}$ to $S_i$ and $S_j$ (e.g., the logit).

Does that make sense?