Recovering a function from a set of approximations

Question

We assume that we have a finite set of agents with approximate knowledge about a certain function, and from this collection of approximations we want to recover the actual value of the function.

More precisely, suppose that there is a finite set $S$, a function $f:S \rightarrow \{ 0,1 \}$, and a finite set $A$ of agents such that for every $a \in A$ and every $s \in S$, $a$ has some opinion about the value of $f(s)$. We assume that for every agent $a \in A$, there is a probability $p_a>\frac{1}{2}$ such that for every $s \in S$ the probability that $a$'s opinion about the value of $f(s)$ is correct is $p_a$. Furthermore, we assume that $S$ and $A$ are both significantly large finite sets, and that $p_a$ is never equal to $1$, but that it is close to $1$ for a significant number of agents. So we have some agents with good knowledge of $f$, but we don't know in advance which of the agents are the ones with good knowledge.

Now the intuitive idea is that we can identify the agents with good knowledge of $f$ by realising that they agree about most values of $f$, since those with bad knowledge of $f$ vary in a random rather than in a systematic way from the actual value of $f$, and hence are not likely to contain a subset of agents that agrees on most values of $f$. Once we have identified the agents with good knowledge of $f$, we can recover $f$ with high confidence (certainly much higher than any of the agents individually can have) by identifying the values that most of the agents with good knowledge of $f$ agree on.

How can this intuitive solution be made mathematically precise with methods from probability theory and/or statistics? Is there some known algorithm for recovering $f$ from the input data? Or is it necessary to specify more precisely the distribution of $p_a$s in $(\frac{1}{2},1)$ in order to specify a solution?

Answer 1

Since the choices of $f_a(s)$ for different $s$ are independent, the only information one can get from considering them all simultaneously is an estimate on the reliability of the agents. Thus, if (1) all the $p_a$ are the same, or: (2) if the algorithm knows the values of $p_a$, the best we can do is to recover each $f(s)$ separately. Thus, in these cases, we can assume without loss of generality that $S=\{s\}$ is a singleton.

We thus have a value $x=f(s)\in\{0,1\}$, we sample independently random variables $X_a=f_a(s)\in\{0,1\}$ with $\Pr(X_a=x)=p_a$, and we want to estimate $x$ from the samples. This problem is well-known in the study of randomized algorithms, and specifically boosting the probability of success by repetition (we have an algorithm which gives the value $x$ with probability at least $p$, and we run it independently $n$ times to obtain samples $X_a$ for $|A|=n$). Such algorithms are usually analyzed using variants of the Chernoff–Hoeffding bound, one of its version reads as follows:

Theorem: Let $X_1,\dots,X_n$ be independent random variables taking values $X_i\in[u_i,v_i]$, and let $X=\sum_{i=1}^nX_i$ have expectation $EX=\mu$. Then

$$\Pr(X-\mu\ge a)\le e^{-2a^2/\sum_i(v_i-u_i)^2}$$

for any $a\ge0$.

If $p_a=p>1/2$ for every $a$, the best way to recover $x$ is to output the majority answer among the agents. By the Chernoff–Hoeffding bound, this answer is wrong with probability at most $e^{-2(p-1/2)^2n}$, where $n=|A|$.

If the $p_a$ may differ, but the recovering algorithm knows these values, we can use weighted majority: output $1$ if $\sum_{a\in A}w_a(X_a-\frac12)>0$, and output $0$ otherwise, where $w_a\ge0$ are fixed weights. Using the Chernoff–Hoeffding bound, the optimal setting of the weights is $w_a=p_a-\frac12$, which gives error at most $e^{-2\sum_a(p_a-1/2)^2}$.

If the $p_a$ may differ, but the recovering algorithm does not know $p_a$, we cannot do (for a single $s$) anything else than output the plain majority. This is not a bad strategy, it will have probability of error at most $e^{-2(p-1/2)^2n}$, where $n=|A|$, and $p=\frac1n\sum_ap_a$. However, in this case the assumption that the best algorithm treats all $s\in S$ independent of each other is no longer valid. (What follows is just my speculation.) We could do better by trying to figure out which agents are more reliable, and take this into account. Here’s an idea of an algorithm. First, for each $s$, let $g(s)$ be the majority answer among $f_a(s)$. Then, for each $a$, let $q_a$ be the fraction of $s$ where $g(s)=f_a(s)$ (this is an estimate of $p_a$), and $w_a=q_a-1/2$. Finally, for each $s$, output “$f(s)=1$” if $\sum_{a\in A}w_a(f_a(s)-\frac12)>0$, and “$f(s)=0$” otherwise. This should do better that the plain majority algorithm, but I do not really have an idea what is the probability of error, or whether this strategy is anywhere near to optimal.

Answer 2

A few thoughts. Looks like $f$ itself can be thought of as just a vector of digits $\lbrace 0, 1 \rbrace$, one digit for each element in $S$. Then $f \in \mathbb{Z}^N_2$ where $N = |S|$, the number of elements in $S$.

If we take the estimates $f_i$ and $f_j$ from two agents, $a_i$ and $a_j$, the hamming distance $d(f_i, f_j)$ would just be the number of elements in $S$ for which $f_i(s) \neq f_j(s)$. Now we have some structure to say how closely agents agree on the value of $f$.

The problem of recovering $f$ starts to look like a standard decoding problem. We could, for example, try to minimize the sum of the Hamming distances between some function $g$ and all of the agents values for $f$. That is, minimize $\sum d(g, f_i)$ where the $f_i$ are the estimates of $f$ for each agent. Note that I don't think this necessarily results in a $g$ that is equal to the estimate of $f$ held by any single agent.

The intuition presented in the question is that the estimates $f_i$ should be clustered in $\mathbb{Z}^N_2$. But there are pathological cases, what if $d(f_i, f_j)$ is equal for all $i \neq j$? This happens when the agents all disagree with each other but each agent disagrees on a different part of $f$. This might not be a problem in practice though, this might just be the case where all the agents have good knowledge of $f$. For example, if $|S| \gg |A|$, this can be a clustering in $\mathbb{Z}^N_2$ with the agents evenly distributed within the cluster.

I think that to argue the optimality of a value chosen using the consensus type approach suggested in the question (and above) requires an assumption about the independence of the estimates of $f$ between the agents. With this sort of assumption a probabilistic result should be available. A result that quantifies the likelyhood that the consensus result is better than the result from any one agent. This is the best I can see you getting since there is always the chance that you get a pathological case where the consensus result is no better than the result from any one agent. The problem is defending the independence assumption if your agents are working with similar data, observing the same events, or generally operating in a shared environment.

Answer 3

Since each $p_a$ is bigger than 1/2, all of the agents, even the ones with poor knowledge, are more likely to give the right answer than the wrong one. So the reasonable guess for $f(s)$ would be the value $f_a(s)$ given by the majority of the agents $a$.

Answer 4

This is a bit too long for a comment, so I post it as an "answer".

Let us crunch your numbers a bit. Suppose you just have 100 bad agents and use the simple majority rule. Then, on an easy value, the probability that you make an error is about $\frac 43{100\choose 50}(0.16)^{50}\approx 2\cdot 10^{-11}$.

On the other hand, on a hard value, the same 100 bad agents with the same majority rule (which is optimal for agents of equal value) err with the probability about $3{100\choose 50}(0.24)^{50}\approx 3\cdot 10^{-2}$. Ten good agents will err with about the same probability, so no matter how hard you try, $10^{-3}$ cannot be beaten (the probability that both groups err simultaneously). More good agents may change it a bit but we'll still be quite short of $10^{-11}$.

If you value recovering a hard value at least as as much as an easy one and the hard values exist at all, almost all your mistakes will come from hard values and it makes sense just to concentrate on them. If you know which values are easy in advance and they are the majority, it makes sense to use just them to extract the information about probabilities and we may think of how to do it in an optimal way.