Recovering a function from a set of approximations

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?

• I don’t understand the model. The way you described it, we have a bunch of deterministic data ($S$, $f$, $A$, and opinions of the agents), and then you suddenly start talking about probability of some event based on this data. This does not make sense. Do you mean that $f$, or agents’ opinions, or both, are chosen randomly? If so, what distribution are they drawn from? Are they independent? Is the algorithm supposed to know the distribution? – Emil Jeřábek Aug 17 '11 at 14:49
• The statement that "those with bad knowledge of $f$ vary in a random manner" seems to come from thin air. The description of the situation (second paragraph of the question) said nothing about the opinions of the agents with bad knowledge except that they have low relatively probability of being right; they might all agree on a wrong answer. I agree with Emil that the model needs to be described more carefully. – Andreas Blass Aug 17 '11 at 16:29
• Assume I fix a function $f:S\rightarrow \{0,1\}$ and a set $A$. For every $a\in A$, I choose a probability $p_a\in(\frac{1}{2},1)$, making sure that for a significant number of elements $a\in A$, $p_a$ is very close to $1$. Now for every $a\in A$ and every $s\in S$, $f_a(s)$ is chosen randomly: With probability $p_a$ it is chosen to be $f(s)$ and with proability $1-p_a$ it is chosen to be $1-f(s)$. Finally, I tell you the value of all $f_a(s)$s. Now based on this information, you have to make a reasonable judgement about the value of $f$ at any $s\in S$. – Marcos Cramer Aug 17 '11 at 17:09
• Can you give us some idea of how large $S$ and $A$ are and which one (if any) is larger? Also, it would be nice to know how good your best agents are. – fedja Aug 18 '11 at 14:20
• The real-world situation I am trying to model is actually a bit more complicated than the model above. I was hoping that a solution to the above problem would help me with solving my actual problem. The main additional complication in the real-world problem is that for some values of $s\in S$, $f(s)$ is harder to know than for other values. $S$ will have size around 150, and $A$ around 100. I presume that a handful of agents will have $p_a$ around 0.8 for the hard problems and 0.95 for the remaining problems. The rest will have $p_a$ around 0.6 for the hard and 0.8 for the remaining problems. – Marcos Cramer Aug 18 '11 at 15:36

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.

• Actually, if you know the probabilities exactly, the best weight is $w_a=\log\frac{p_a}{1-p_a}$ (the maximum likelihood estimate). However, you are right that unless we have some agents with really good knowledge, it is pretty much the same as the weight $p_a-\frac 12$. The problem with the majority estimate is that if we have a swarm of agents with 0 knowledge, (i.e., if $\sum_a(1-q_a^2)$ is comparable with $(\sum_a q_a)^2$ where $q_a=2p_a-1$), then the noise may dominate the signal and we can be much better off with using a few preselected reliable agents. – fedja Aug 18 '11 at 14:31
• The $p_a$ may differ and the recovering algorithm does not know them, so your last paragraph is the only one that's about the problem I had in mind. The algorithm you describe at the end seems a good start, and made me think about a possible improvement, namely iterating your algorithm: We set $f_0$ to be your $g$, and we derive $f_{i+1}$ from $f_i$ in the way you derived $f$ from $g$. We iterate this process long enough until no more changes occur. Now the question becomes whether we can prove that (outside certain pathologthical cases) this process terminates and yields an optimal solution. – Marcos Cramer Aug 18 '11 at 14:54

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.

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$.

• One can certainly do better than this, in the way I informally described in my question. The question is how this informal idea can be formalised. – Marcos Cramer Aug 18 '11 at 11:47

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.

• I do not know in advance, which ones are the hard and which ones the easy values. – Marcos Cramer Aug 19 '11 at 8:57