World's most popular travel blog for travel bloggers.

# [Solved]: Pairwise comparisons with confidence

, ,
Problem Detail:

There is a lot of information available on the subject of Pairwise Comparisons but I haven't found any guidance on how to optimize pair measurements that have confidence values attached to them.

Imagine that an AI black box has been trained on many pairs of objects in order to predict the distance between the objects in novel pairs. All objects are colinear. The black box also provides a confidence level for each distance. Here is a simple example of outputs based on a set of 5 objects ($a$ to $e$):

Pair, Distance, Confidence  a-b,  5,        0.4 a-c,  9,        0.7 a-d,  -3,       0.9 a-e,  2,        0.6 b-c,  6,        0.8 b-d,  -10,      0.7 b-e,  -2,       1.0 c-d,  -6,       0.5 c-e,  -2,       0.6 d-e,  7,        0.9 

So, the distance between $a$ and $b$ is predicted to be 5 units ($b$ is to the right of $a$) and the black box's confidence in that measurement is 0.4 (0.0 = no confidence and 1.0 = perfect confidence). The distance between $a$ and $d$ is -3 units ($d$ is to the left of $a$) and the confidence is 0.9.

I would like to understand the process for deriving the solution, which is the optimization of the four distances between these objects given the predicted distances and their associated confidence levels.

###### Asked By : Bob Davidson

I suggest that you define a loss function, which characterizes how much a candidate solution is penalized if the true distance between (say) $a$ and $b$ differs a bit from your prediction.

For instance, one candidate loss function might be $L(d) = c \times |d - d_0|$, where $d$ is the actual distance in the candidate solution, $d_0$ is the predicted distance, and $c$ is the confidence in the prediction. Another candidate loss function could be $L(d) = c \times (d-d_0)^2$. There could be many other loss functions.

Suppose we let $L_{a,b}$ denote the loss function for the pair $a,b$, and so on. We might define the overall loss to be the sum of the losses for each pair:

$$L = L_{a,b}(|a-b|) + L_{a,c}(|a-c|) + L_{b,c}(|b-c|) + \dots$$

where $a,b,c,\dots$ denote the positions of the points in the candidate solution.

With this framework, one could then ask for the optimal solution, i.e., the values of $a,b,c,\dots$ that minimize this total loss $L$. That is an optimization problem that could be solved a variety of optimization methods (e.g., by differentiating and setting the derivatives to zero; by using numerical optimization methods, such as gradient descent; or by solving this particular optimization problem directly).

For the loss function $L(d) = c \times |d-d_0|$, this optimization problem can be solved using linear programming. Instead of using $a,b,c,\dots$ to represent the locations of the points, I'd like to use $x_1,x_2,x_3,\dots$, as that is more convenient. Also, let $d_{i,j}$ represent the predicted difference between $x_i$ and $x_j$, and $c_{i,j}$ represent the confidence of this prediction, for all $i,j$. We are given the $d_{i,j}$'s and the $c_{i,j}$'s, and we want to solve for the $x_i$'s. In particular, we want to find the $x_i$'s that minimize the overall loss

$$L = \sum_{i,j} c_{i,j} \times (|x_i-x_j-d_{i,j}|).$$

To find the optimal solution, we'll write a linear program, with $x_1,x_2,x_3,\dots$ as unknowns, where the solution to the linear program is the optimal solution to your problem. To make this work, we need to translate the optimization problem into one with linear inequalities. To facilitate that, I'll introduce variables $l_{i,j}$ for each $i,j$; intuitively, $l_{i,j}$ represents the loss associated with $x_i,x_j$, i.e., it represents the value $c_{i,j} \times (|x_i-x_j-d_{i,j}|)$. We can express these relationships as linear inequalities as follows. We want to have $c_{i,j} \times (|x_i-x_j-d_{i,j}|) \le l_{i,j}$, but unfortunately this is not the sort of inequality we can write directly in a linear program. Fortunately, if we just manipulate this a bit we can get two inequalities that are allowable in a linear program:

$$x_i-x_j \le d_{i,j} + \frac{1}{c_{i,j}} l_{i,j}$$ $$x_i-x_j \ge d_{i,j} - \frac{1}{c_{i,j}} l_{i,j}.$$

Since $d_{i,j}$ and $c_{i,j}$ are known values (constants), the above inequalities are linear in the unknowns $x_i,x_j,l_{i,j}$, so they are allowed to appear in linear programs. Thus, we minimize the function $\sum_{i,j} l_{i,j}$, subject to all of the above linear inequalities (we get two of them for each $i,j$). This is a linear program, and its best solution is the optimal set of locations $x_i$ for your points.

You can solve this linear program using any standard linear solver (e.g., lp_solve). There are $n(n-1)$ linear equations and $n(n-1)/2 + n$ unknowns, which is not too many: I would expect existing linear solvers to be able to handle this kind of linear programming problem without difficulty.

But before you can solve the problem, you must decide what are suitable loss functions and what is a suitable formalization. Then, and only then, can you construct an algorithm to solve this problem.