5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Related question: cstheory.stackexchange.com/questions/2890/ranking-with-errors . $\endgroup$ Nov 15, 2010 at 17:38
  • $\begingroup$ With 3 player you might have A alwys beats B and B always beats C but C beats A 83% of the time. That said, I'd be tempted to take the matrix of observed probabilities ($a_{i,j}+a_{j,i}=1$) Find the eigenvector for the largest eigenvalue (maybe putting 1/2 on the diagonal.) Then take the ration of entries. Bot not for any good reason. $\endgroup$ Jan 10, 2011 at 21:25
  • $\begingroup$ Have you looked at the Elo rating system pioneered in chess, but used widely? You can assign ratings based on the games played, then use those to forecast the probabilities. $\endgroup$ Jan 11, 2011 at 0:45

3 Answers 3

1
$\begingroup$

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 !

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think you may have misunderstood the question, as that is effectively what I'm already doing (I'm taking the expected value of the posterior, which is cheating but useful). The question is about how to introduce the fact that the pairs are not independent and that we expect there to be a certain amount of consistency between them as evidence. $\endgroup$ May 27, 2010 at 17:30
  • $\begingroup$ ah i see. Interesting twist. $\endgroup$
    – vad
    May 27, 2010 at 17:39
0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ You could justify the logit by arguing that in any competition the items do not compete with true strength but with some error. Therefore, Prob(i wins over j) = Prob(S_i + e_i > S_j + e_j). If you then assume that the error terms are extreme value you get the logit function i.e., theta_j = exp(S_i) / (exp(S_i) + exp(S_j)) See the link en.wikipedia.org/wiki/… $\endgroup$
    – vad
    May 27, 2010 at 17:53
  • $\begingroup$ Hmm. That might work. It's not obvious how to assign a useful prior distribution to $S_i$ though, or am I missing something?. $\endgroup$ May 27, 2010 at 21:05
  • $\begingroup$ If you use the simpler functional form that I outlined above then choose S_i to be a truncated normal distribution with S_i > 0. If you choose the logit then choose the prior for S_i to be a normal distribution. You could also use maximum likelihood to estimate S_i in which case you do not need any priors. $\endgroup$
    – vad
    May 27, 2010 at 22:04
  • $\begingroup$ I'm not convinced by this solution for a couple reasons: * It doesn't appear to admit a nice solution (you end up with a very overconstrained and slightly thorny equation in the matrix $M_ij = \frac{s_i}{s_i + s_j}$) * It doesn't handle the case where there genuinely are inconsistent results (it's certainly possible for majorities to prefer A to B to C to A) * If it were computationally feasible to compute the MLE then rank aggregation would be essentially trivial, which it isn't. $\endgroup$ May 28, 2010 at 9:56
  • $\begingroup$ Well the formulation above and the logit in particular is a fairly standard way to capture preference structures. If you have inconsistent preferences then there are two possibilities: 1. True preferences are consistent and any inconsistency that you see is an observational error which is captured by the logit or 2. there exist some contextual details which can explain the inconsistency which are not presently known or captured in the model. MLE and bayesian techniques are widely used in context of the logit and more complicated models than the logit. $\endgroup$
    – vad
    May 28, 2010 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.