2
$\begingroup$

I came across this library Choix. I want to do Pairwise Comparison on data that looks like this to output a ranking from best to worst.

Let's call this X:

      Impressions  Clicks       CTR   CPC    Cost  Conversions    CPA  ConvRate
1425         3564    57.0  0.015993  0.68   38.76          9.0   4.31  0.157895
3544         7683   519.0  0.067552  1.90  986.10         10.0  98.61  0.019268
4721           32     1.0  0.031250  3.54    3.54          0.0   0.00  0.000000

The author of Choix posted this answer showing how to do maximum likelihood estimate iteratively but his sample data is a square matrix. I'm not sure how to do it with my data (not square).

I've also spent the last week attempting to apply these concepts from his formulas (found here):

$p(i \succ j \succ \ldots \succ k) = \frac{e^{\theta_i}}{e^{\theta_i} + e^{\theta_j} + \cdots + e^{\theta_k}} \cdot \frac{e^{\theta_j}}{e^{\theta_j} + \cdots + e^{\theta_k}} \cdots.$

If I understand this formula, you just apply softmax to each column, then multiply the columns together. I'm subtracting max for numeric stability.

>>> softmax = np.exp(X - X.max(axis=0)) / np.sum(np.exp(X - X.max(axis=0)))
      Impressions         Clicks       CTR       CPC  Cost  Conversions           CPA  ConvRate
1425          0.0  2.269600e-201  0.325915  0.045769   0.0     0.268932  1.111809e-41  0.367041
3544          1.0   1.000000e+00  0.343160  0.155029   1.0     0.731034  1.000000e+00  0.319528
4721          0.0  1.085072e-225  0.330926  0.799202   0.0     0.000033  1.493555e-43  0.313431

>>> product = softmax.prod(axis=1)
# Prints Out:
1425    0.000000
3544    0.012427
4721    0.000000
dtype: float64

I've tried various scaling tactics (softmax, min/max scaling, standardization, sigmoid, rank with 0s and 1s).

Questions

  1. Is the Bradley–Terry model (or some derivation) the right model choice for my data? I believe this model is based on wins and losses which my raw data is not.
  2. Columns CPA and CPC are considered good when their values are lower, not higher like the other columns. What's the best way to handle this? I've tried negativing the columns but wondering if there's an inverse softmax or something?
  3. I would like to assign weights to the columns but I think if I assign flat weights (ex: 1.05, 0.55, 0.01, etc.) it has no effect because all values in the column are scaled by the same value. What I really want to do is weight the good performance more and weight the bad performance less in each column but not sure how to approach it mathematically.
  4. My data is heterogeneous. What is the best scaling method to preserve the difference (distance) between rows to make the math work best for pairwise comparison?
  5. (Bonus) I've tried classification algorithms but they did terrible because the results are all relative to the group, not the entire dataset. I have no idea if a Pairwise Classifier exists -- a classifier that trains only in the context of the samples of a small subset, relative to the other samples. Does this exist?

My tool of choice is Python so I use Numpy, Pandas, Scikit-learn. I really struggle reading math notation but I can easily read it if it's in Python. If you know Python and know how to answer this, Python code would go a long way in helping me bridge the gaps.

Resources

*Edit 1: What are the objects in this example?

The objects are ads. Each row is an ad. Each ad has a specific set of performance metrics associated to it. There can be several ads in a group. There can be many groups. It can be time-consuming to evaluate each group's ads individually.

An ad is only as good or bad when compared to the other existing ads in the group. Pairwise comparison.

A lot of people just guess. This is very error-prone. I want a mathematically sound approach / process / procedure. For example, one could just sort everything by the columns most-important to least, but then you miss out on things like an ad with 1 conversion vs an ad with 100 conversions but maybe ConvRate for the ad with 1 conversion has a 0.001 better ConvRate than the ad with 100 conversions.

$\endgroup$
  • $\begingroup$ Can you elaborate on why you want to run this model? You say you want a rank from best to worst - of what precisely? The Bradley Terry model implies paired comparisons between objects - what are the objects in this dataset you’d like to compare? $\endgroup$ – awhug Jul 15 '19 at 9:06
  • $\begingroup$ @awhug I made an "Edit 1" edit to answer this. $\endgroup$ – Jarad Jul 15 '19 at 17:28
1
+50
$\begingroup$

I'm not sure paired comparisons is the right analysis here, given your data. Moreover I think you're getting confused between the Bradley Terry and Plackett Luce Models. You'd likely need to transform your data to binary or rank outcomes if you want to proceed.

I've mainly addressed Question 1, because I don't think there are good answers for the rest once you understand what these models were designed to do. My examples don't use your data because it's easier to explain the traditional motivation behind paired comparison and ranking methodologies using experimental choice data. There is some MathJax, but I've laid out demos in Python too.


Bradley Terry Model

This assesses the probability that one object 'beats' another - traditionally this would be something like binary data for all pairwise comparisons.

The probability of Object $i$ beating Object $j$ is calculated as $\text{P(i>j)}=e^{\theta_i}/(e^{\theta_i}+e^{\theta_j})$. The $e^{\theta_i}$ values here must be estimated to determine the probability of a given object 'beating' another in the BT model. This typically simplifies to a logistic model on the pairs. You can't just run the MLE technique described in your linked post on raw data; the issue is not just that your data isn't square, but particularly that it is not a pairwise probability matrix.

How do we get that? I'll try to demonstrate.

Worked Example

Imagine you have four judges compare preferred holiday destinations out of Sydney, Brisbane and Melbourne. They make pairwise comparisons on which cities they prefer (e.g. "Would you rather travel to a) Brisbane, or b) Melbourne?" etc.)a.

You can use choix.lsr_pairwise() to analyse this type of data, arranged into a list of tuples denoting which is preferred, in combination with choix.probabilities().

import numpy as np
import pandas as pd
import choix

# CITY CODES:
# 0 = Sydney, 1 = Brisbane, 2 = Melbourne
# Each tuple represents an independent paired comparison
# In the data, a city is preferred if it is placed FIRST in the tuple

n_cities = 3
city_pairs = [
     (1, 0), (1, 0), (0, 1), (0, 1), #Syd > Bris: 2/(2+2) = 50%
     (0, 2), (2, 0), (0, 2), (0, 2), #Syd > Melb: 3/(1+3) = 75%
     (1, 2), (2, 1), (1, 2), (1, 2), #Bris > Melb: 3/(1+3) = 75% ]

city_BT = choix.lsr_pairwise(n_cities, city_pairs)
choix.probabilities([0,1,2], city_BT)

# Returns
array([0.42857143, 0.42857143, 0.14285714])

This array represents the probability any one city will be selected over the other two, and the values always sum to one. These are sometimes called the worth parameters, and will give you a rank of cities from least to most preferred directly if you simply run np.argsort() on it.

They also equate to the $e^{\theta_i}$ values, and can be used to make the pairwise comparison probabilities using the BT formula described above (I'm rounding here):

$$\text{P}(Sydney > Melbourne)=\frac{.429}{(.429+.143)}=.75$$

This is probably sufficient to meet your needs. We can however also use a list comprehension in Python to find all such comparisons, creating the pairwise probability matrix, which may (or may not) be handy.

#Create pairwise probability matrix using list comprehension
pmat = np.asmatrix([[choix.probabilities([x,y], city_BT)[0] for y in range(3)] for x in range(3)])

#Fill the diagonal with zeros - An object can't be compared against itself
np.fill_diagonal(pmat, 0)

#Present
print(pd.DataFrame(pmat, ["Sydney", "Brisbane", "Melbourne"], 
                   columns = ["Beats Sydney", "Beats Brisbane", "Beats Melbourne"]))

# Returns
           Beats Sydney  Beats Brisbane  Beats Melbourne
Sydney             0.00            0.50             0.75
Brisbane           0.50            0.00             0.75
Melbourne          0.25            0.25             0.00

In principle you could convert your data for paired comparison analysis - either binary or a pairwise probability matrix, based on wins vs. losses between ads within your performance metrics on each column (metrics are effectively treated as judges). But the issue should be obvious - you're losing information on how much 'better' one ad is on a given column by making a binary win/lose outcome between ads on each metric.

I'm not aware of a way around this - the Bradley Terry Model primarily deals with binary paired comparison data. There are methods for adding an ordinal graded preference to categorically reflect much more 'preferred' an ad is, but again you'd still be losing information.

Converting your heterogenous data types into consistent comparisons to derive the pairwise probability matrix whilst respecting the scales of each metric is likely to be impractical if not impossible, and is certainly not implemented (as far as I know) in Choix.


Plackett Luce Model

This can assess whether one object 'beats' another - but this time based on a probabilistic model of ranking data.

The reason I discuss this is because the formula you provide above is actually the Plackett-Luce. Again, this works with the probabilities of selecting a given option, but because the data is comprised of ranks, it needs to be handled differently.b The Plackett-Luce assumes a step-wise process usually working down from choices that determine the top to bottom ranksc, which is illustrated in your equation. Let me explain.

We first evaluate the probability of selecting one object from the entire set:

$$\frac{e^{\theta_i}}{e^{\theta_i}+e^{\theta_j}+\dots+e^{\theta_k}}$$

Then remove that object from consideration, and evaluate the probability of selecting the next object out of all those remaining (excluding the first):

$$\frac{e^{\theta_j}}{e^{\theta_j}+\dots+e^{\theta_k}}$$

You keep working down like this, until you're down to the last two, and the product of these probabilities forms the likelihood of the ranking for a single respondent (which gives your formula). Each step can actually be thought of as a conditional logit model, hence its alternative name: the Rank-Ordered Logit Model (Allison & Christakis, 1994). Your softmax approach described above is therefore incorrect - there's no sequential probabilistic process applied on ranking data.

Worked Example

This is fairly easy to in choix using choix.lsr_rankings() in tandem again with choix.probabilities().

# In the data, a rank is represented by ORDERING in the tuple
# E.g. Sydney > Melbourne > Brisbane = (0, 2, 1)

city_ranks = [
    (0, 1, 2), (1, 0, 2), (0, 1, 2), (0, 1, 2),
    (1, 2, 0), (0, 1, 2), (0, 2, 1), (2, 1, 0) ]

city_PL = choix.lsr_rankings(n_items = n_cities, data = city_ranks)
choix.probabilities([0,1,2], city_PL)

# Returns
array([0.47459893, 0.37834225, 0.14705882])

This is directly interpretable as the 'worths' of the 3 cities - We can see that Sydney is more likely to be ranked above Brisbane, and both above Melbourne (Poor Melbourne).

This is applicable to your problem if you're willing to convert each performance metric to rankings within each column - e.g. Impressions would be (1, 0, 2), Clicks would also be (1, 0, 2), etc. But once again, you're losing information. There is no straight-forward way of instantiating the distances between continuous variables in this model - it's designed for ranks.


aNote that comparisons need not be coherent in the Bradley Terry model - intransitive responses are allowed. For example, a judge could prefer Sydney > Brisbane, and Brisbane > Melbourne, but for whatever reason Melbourne > Sydney. This is not applicable in your case as inconsistencies will never arise.

bRankings have to be handled differently because the outcome must be transitive - if a judge says Sydney > Brisbane, and Brisbane > Melbourne, then by definition they must endorse Sydney > Melbourne

cOne can also rank from worst to best, but note that this will yield different ranking probabilities - the ranks are non-reversible. See Allison & Christakis (1994)

$\endgroup$
  • $\begingroup$ Thank you for straightening out my points of confusion and incorrect understanding of the Plackett Luce vs Bradley Terry model. $\endgroup$ – Jarad Jul 18 '19 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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