1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You need to precisely define what counts as the solution. You have not provided any semantics for "confidence", and you have not told us what objective function we are supposed to optimize, so this problem is not yet well-defined. Since it is not well-defined, it cannot be meaningfully solved in its current form. I encourage you to edit the question to clarify these points. $\endgroup$ – D.W. Jul 3 '13 at 7:19
  • $\begingroup$ Confidence in this scenario is a measure of similarity between the respective characteristics that define novel and learned Stimuli. The confidence value is adjusted such that the sum of the absolute differences between those characteristics will range from 0 to 1, inclusive. The objective is to minimize the loss function defined as you have below: $L(d) = c \times |d - d_0|$ $\endgroup$ – Bob Davidson Jul 3 '13 at 13:34
  • $\begingroup$ I would consider it a bonus to see how this can be solved directly as opposed to using an optimization method or more complex solution. Thank you. $\endgroup$ – Bob Davidson Jul 3 '13 at 13:41
  • $\begingroup$ OK. Bob, I've edited my answer to provide a way to solve this directly (using linear programming) without requiring an optimization framework. P.S. Perhaps you could edit the equation to include the definition of the loss function and the objective function you are trying to minimize, to make your question self-contained and more likely to help others who may come across this? $\endgroup$ – D.W. Jul 3 '13 at 17:16
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

There are several possible ways to solve this problem. One way is to assume some measurement model (usually Gaussian noise) and then find the maximum likelihood solution.

That is, we start with some distribution of the measured distance given the actual distance and the noise level, for example if the actual distance is $d$ and the noise level is $\sigma$, then perhaps the measured distance is distributed $N(d,\sigma)$.

Given a sequence of measurements, for each potential list of positions (say with $a=0$ to break the symmetry), we can calculate the likelihood that we would get the actual measurements. In your case, we would get $$ L(a,b,c,d,e) = \frac{1}{\sqrt{2\pi} 0.4} e^{-(5-(b-a))^2/(2\cdot 0.4)} \cdot \frac{1}{\sqrt{2\pi} 0.7} e^{-(9-(c-a))^2/(2\cdot 0.7)} \cdots. $$ The idea is to find the setting of $a,b,c,d,e$ that maximizes $L(a,b,c,d,e)$. To that end, we can calculate $$ -\log L(a,b,c,d,e) = C + \frac{(5-(b-a))^2}{2\cdot 0.4} + \frac{(9-(c-a))^2}{2\cdot 0.7} + \cdots.$$ We want to minimize the latter. We can substitute $a = 0$, and then differentiate with respect to each of the other variables, and equate to zero. For example, differentiating with respect to $b$, we obtain $$ 0 = -\frac{\partial \log L}{\partial b} = \frac{b-5}{0.4} + \frac{b-c+6}{0.8} + \frac{b-d-10}{0.7} + \frac{b-e-2}{1.0}. $$ In this way, we get linear equations which we can solve for $b,c,d,e$. (This is the method of least squares.)

For other models of noise, we might have to use numerical optimization instead. You can find more examples in any machine learning textbook.

$\endgroup$

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.