# Unsupervised Opinion Aggregation – A Statistical Perspective

Noyan C. Sevüktekin and Andrew C. Singer
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>
###### Abstract

Complex decision-making systems rarely have direct access to the current state
of the world and they instead rely on opinions to form an understanding of
what the ground truth could be. Even in problems where experts provide
opinions without any intention to manipulate the decision maker, it is
challenging to decide which expert’s opinion is more reliable – a challenge
that is further amplified when decision-maker has limited, delayed, or no
access to the ground truth after the fact. This paper explores a statistical
approach to infer the competence of each expert based on their opinions
without any need for the ground truth. Echoing the logic behind what is
commonly referred to as the wisdom of crowds, we propose measuring the
competence of each expert by their likeliness to agree with their peers. We
further show that the more reliable an expert is the more likely it is that
they agree with their peers. We leverage this fact to propose a completely
unsupervised version of the naïve Bayes classifier and show that the proposed
technique is asymptotically optimal for a large class of problems. In addition
to aggregating a large block of opinions, we further apply our technique for
online opinion aggregation and for decision-making based on a limited the
number of opinions.

###### Index Terms:

Unsupervised opinion aggregation, statistical inference, stochastic experts.

##  I Introduction

Many modern engineering systems have access to extrinsic information in the
form of opinions – subjective evaluations of the current state of the world.
Contrary to the conventional models of information flow capturing the
uncertainty in tasks with quantifiable objectives such as measuring a physical
quantity or transmitting information through a medium, opinions are generated
for tasks with inherent subjectivity, thus providing limited insight on the
underlying rationale or the proficiency of the opinion source.

Albeit a more unforgiving form of information for decision making, opinions
are critical in high-risk applications including autonomous driving [1],
personalized medicine [2], and disaster detection [3], where information is
readily available from highly heterogeneous opinion sources, or experts, while
the true state of the world remains hidden, or unachievable. The internet of
things is conjectured to be particularly rich in subjective information as
highly localized processing units under power, circuit area, and latency
constraints are designed to collectively address global computational tasks
[4]. Complicated physico-chemical processes, such as genomic data sequencing
[5], are often subject to high-dimensional uncertainty, while the target
efficiency is remarkably high. Similarly, human integration into labeling data
exhibits a similar, difficult-to-model, behavior [6].

Decision-making by consulting experts, or opinion aggregation, has far-
reaching roots: Bayesian hypothesis testing sets the fundamental limits of
opinion aggregation provided that the complete probability law governing the
experts exists and is known to the decision maker [7]. Nonetheless, it is
difficult, if at all possible, to model reliably, over the entire application
space, the probability law that underlies highly-specialized processing units,
which are often trained on limited data. The modeling error and the
concomitant performance degradation in opinion aggregation might prove to be
uncontrollable in such cases. The uncertainty in modeling, however, does not
necessarily render statistical inference of the underlying probability law
implausible. Dempster-Schafer theory addresses the Bayesian inference problem
under model uncertainty by incorporating belief and plausibility functions to
substitute direct application of the probability law [8, 9]. In general, use
of approximate models for reasoning is called fuzzy logic [10] and it has a
wide range of applications in control theory [11].

In the absence of approximate or complete probability laws, feedback is often
used to learn and mitigate the reliability of each source and the concomitant
probability distribution over opinions. The mixture of experts setup
successfully aggregates opinions from potentially adversarial experts by the
use of reliable past information [12]. Similarly, boosting and the associated
meta-learning concepts use feedback, often at the expense of additional
training data, to learn and use the reliability of different strategies, or
classifiers [13]. The use of feedback is both the strength and the fundamental
limitation of such strategies, as feedback is often expensive even when it is
feasible to generate. The Bayesian ideas are called to action and a prior
distribution on the underlying probability law is often assumed when feedback
is not feasible. Bayesian approach enables the rather powerful toolbox of
iterative algorithms including belief propagation, expectation-maximization,
and mean-field methods [14, 15, 16, 17, 18]. Bayesian decision-aggregation
methods are powerful to the extent with which the prior successfully captures
reality.

The existence of reliable or approximate models, feedback, or prior
information fundamentally defines the application space on which the
associated ideas can be employed, and thus, are limited to such applications.
As such, we may consider opinion-aggregation techniques that use some form of
side information as supervised rules. Conceptually, the presence of such side
information renders an otherwise vital fact obsolete: Experts aim to achieve a
common task, not to fail it, as long as a fixed probability law exists. The
opinion-aggregation rules that rely solely on the existence of a probability
law can therefore be considered unsupervised rules. Often a community of
experts is less subjective than its individual constituents, motivating
statistical inference to compensate the lack of supervision. The fundamental
challenge is to design unsupervised decision rules that reliably aggregate
opinions without using any side information on the hidden-yet-fixed
probability law governing the experts.

This paper addresses this challenge from an inherently statistical
perspective. Section II provides the formal background for opinion aggregation
and identify different regimes of operation. Section III introduces a novel
technique for estimating, dynamically in real-time, the reliability of each
expert from a set of opinions and discusses the properties of the proposed
method. The purpose of such reliability estimation is made clear by using
these estimates to infer the unknown probability law. Section IV introduces
the a sharp upper-bound on the minimum probability of error achievable when
the probability law is known, improving upon the state-of-the-art. Section V
proposes an unsupervised opinion aggregation rule based on the minimum
probability of error rule that uses the unsupervised reliability estimates and
investigate its fundamental limits. Section VI addresses empirical extensions
that aggregate a fixed block of opinions as well as doing so adaptively in
real-time. Experiments are given in Section VII. Proofs are deferred to the
appendix.

##  II Notation, Background, and Problem Definition

We first discuss the notation used in this paper, then formally define the
concepts of opinions, experts, tasks, and opinion aggregation. We address
different modes of unsupervised opinion aggregation separately.

###  II-A Notation

A probability space is a triplet $\left(\Omega,\mathscr{F},\mathbb{P}\right)$,
where $\Omega$ is the event space, $\mathscr{F}$ is the sigma-field defined on
$\Omega$, and $\mathbb{P}$ is the probability measure. Random variables are
denoted by capital letters and the corresponding samples are denoted by
lowercase letters: $(X,x)$. Independent random variables
$\left(X_{1},X_{2}\right)$ are denoted by $X_{1}\perp X_{2}$ and conditionally
independent random variables $\left(X_{1},X_{2}\right)$ conditioned on $Y$ are
denoted by $X_{1}-Y-X_{2}$. A random process is an indexed collection of
random variables $\left\\{X(t):t\in\mathbb{T}\right\\}$, where $\mathbb{T}$ is
the index set with cardinality $\left|\mathbb{T}\right|=T$. Expectation,
conditional expectation, and conditional probability operators are
$\mathbb{E}\left[\cdot\right]$,
$\mathbb{E}\left[\cdot\;\middle|\;\cdot\right]$, and
$\mathbb{P}\left(\cdot\;\middle|\;\cdot\right)$ respectively. Random vectors
and corresponding samples are column vectors, denoted by bold letters:
$\bm{X}=\left[X_{1},\cdots,X_{N}\right]^{\top}$,
$\bm{x}=\left[x_{1},\cdots,x_{N}\right]^{\top}$. A vector that excludes a
specific element $\left(X_{j},x_{j}\right)$ is denoted by
$\left(\mathbf{X}_{\setminus{j}},\mathbf{x}_{\setminus{j}}\right)$. When a
random process takes vector values, we use the notation
$\left(\bm{X}\left(t\right),\bm{x}\left(t\right)\right)$, $t\in\mathbb{T}$.
The corresponding random matrices are constructed explicitly:
$\left[\bm{X}(1),\cdots,\bm{X}(T)\right]$. The indicator function is denoted
by $\mathds{1}\left(\cdot\right)$, where the domain is to be understood from
context. We use $[N]\triangleq\left\\{1,\cdots,N\right\\}$ to denote the
natural numbers up to a finite limit. Standard Hilbert space notation applies,
specifically $\left|\cdot\right|$ denotes absolute value and
$\left\|\cdot\right\|_{p}$ denotes $p$-norm.

###  II-B Background

Let a set of tasks $\mathbb{T}$ for identifying hidden binary states
$Y(t)\in\left\\{-1,1\right\\}$, $\forall t\in\mathbb{T}$ (in the context of
classification, $Y(t)$ is often called label or ground-truth instead) be
generated independently, $Y(t)\perp Y(\tau)$, $\forall t\neq\tau$, with a
uniform prior:

$\mathbb{P}\left(Y(t)=1\right)=\mathbb{P}\left(Y(t)=-1\right)=\nicefrac{{1}}{{2}},\forall
t\in\mathbb{T}.$ (1)

Even though there exists applications that do not admit the uniform prior,
such as group testing [19], where populations are severely skewed, (1) is a
common assumption in opinion aggregation problems [20]. If a non-uniform prior
on $Y$ exists, standard Bayesian decision-making principles can be used to
adapt the results presented in this paper [7].

Experts generate binary opinions $X_{i}\in\left\\{-1,1\right\\}$, $\forall
i\in[N]$, that identify the true state $Y(t)$ with some probability:

$p_{i}\triangleq\mathbb{P}\left(X_{i}(t)=Y(t)\right),\forall t\in\mathbb{T}.$
(2)

The true competence $p_{i}$ of an expert is considered fixed across tasks. Let
there be $N$ experts and assume that opinions are generated independently,
which amounts to:

$X_{i}(t)-Y(t)-X_{j}(t),\forall i\neq j\in[N],$ (3)

for every task $t\in\mathbb{T}$. One should note that (3) does not indicate
that opinions are independent. Indeed, it is conceptually clear that opinions
should be dependent for meaningful inference as an opinion is a subjective
evaluation of the current state, not an arbitrary input.

Experts that can reliably be defined by a stochastic law, as done here via
$\eqref{uniform_prior}-\eqref{opinion_gen}$, are sometimes called stochastic
experts to separate them from the more game-theoretic framework of adversarial
experts [12], a similar distinction exists for multi-armed bandits [21].
Furthermore, when $p_{i}$ is a function of the underlying task space
$\mathbb{T}$, different from how it is defined here, experts exhibit task-
dependent competences. Neyman-Pearson formulation of binary hypothesis testing
[22] and the two-coin Dawid-Skene model [17], are examples of expert
competences changing over the task space $\mathbb{T}$.

Opinion-based systems are sometimes referred to as semi-supervised systems due
to the availability of experts and the concomitant subjective information
[23]. However, in the context of opinion aggregation, one may consider
supervision as any form of side-information that yields inference of the
underlying probability law beyond the extent that opinions alone would allow.
Formally, a supervised opinion-aggregation rule refers to a function
$f\left(\cdot\right)$ mapping a set of opinions $\bm{X}\left(t\right)$ to an
estimate of the true state $Y(t)$:

$\hat{Y}\left(t\right)=f\left(\bm{X}\left(t\right);\mathcal{S}\right),$ (4)

where $\hat{Y}(t)\in\left\\{-1,1\right\\}$ and $\mathcal{S}$ denotes some form
of side information. Supervised opinion-aggregation methods require different
forms of side-information $\mathcal{S}$: $\left\\{p_{1},\cdots,p_{N}\right\\}$
for Binary hypothesis testing [7], subsets of
$\left\\{y_{1},\cdots,y_{t-1}\right\\}$ for boosting and mixture of experts
[12, 13], or a priori distribution $p_{P_{1},\cdots,P_{N}}\left(\cdot\right)$
on competences for Bayesian techniques; [14, 15, 16, 17, 18] are some of the
prominent examples.

Unsupervised opinion aggregation, on the other hand, refers to functions that
only rely on the existence of the underlying probability law, here, for
instance, characterized by (1)-(3). As such, they assume the form:

$\hat{Y}\left(t\right)=f\left(\bm{X}\left(t\right)\right).$ (5)

The most prominent example of unsupervised decision aggregation is majority
voting, which is commonly accepted as the baseline for unsupervised
techniques. A modern unsupervised technique is called spectral meta learner
and it relies on the singular values of the empirical covariance matrix of a
collection of opinions [24].

Binary opinion-aggregation techniques often aim to minimize the probability of
error:

$\min_{f\in\mathcal{D}}\mathbb{P}\left(f\left(\bm{X}\left(t\right)\right)\neq
Y\left(t\right)\right),$ (6)

where $\mathcal{D}$ is the family of admissible opinion-aggregation rules that
depend on the problem setup. For instance, the admissible rules comprise all,
potentially randomized, decision rules when competences are known, past-
measurable decision rules when feedback from past tasks is available, and
functions that directly map available opinions to decisions on the
corresponding tasks in the absence of all side information.

Opinion-aggregation rules (4)-(5), and the corresponding performance metric
(6), are written in the form of single-task opinion aggregation, where a set
of opinions $\left\\{X_{1}(t),\cdots,X_{N}(t)\right\\}$ are used to make a
decision $\hat{Y}(t)$. Next, we discuss different modes of operation for
unsupervised opinion aggregation.

###  II-C Unsupervised Opinion Aggregation

Unsupervised opinion aggregation refers to employing a function $f(\cdot)$ of
opinions
$\left\\{X_{i}\left(t\right):\left(i,t\right)\in\mathcal{N}\times\mathcal{T}\right\\}$
for some subset $\mathcal{N}\times\mathcal{T}\subset\mathbb{T}\times[N]$ to
identify a set of hidden states $\left\\{Y(t):t\in\mathcal{T}\right\\}$,
directly:

$\left\\{Y(t):t\in\mathcal{T}\right\\}=f\left(\left\\{X_{i}\left(t\right):\left(i,t\right)\in\mathcal{N}\times\mathcal{T}\right\\}\right)$
(7)

Note that there is no side information $\mathcal{S}$ as an input to the
decision rule and that the subset $\mathcal{N}\times\mathcal{T}$ determines
the operational meaning of the opinion-aggregation rule: The function
$f\left(\cdot\right)$ might be fixed for all tasks $\mathbb{T}$, such as
majority voting [25], or it might change adaptively in tasks. Furthermore,
$f\left(\cdot\right)$ might process blocks of opinions (often iteratively and
non-adaptively) [14, 15, 18, 17, 16]. The formal definitions of unsupervised
opinion-aggregation rules are discussed below.

####  II-C1 Instantaneous Opinion Aggregation

A fixed function directly applicable to opinions
$\left\\{X_{i}(t):i\in[N]\right\\}$ on any task $t\in\mathbb{T}$, is an
instantaneous opinion-aggregation strategy. Conceptually, these rules do not
require additional memory to store past opinions. Formally, they take form
$\hat{Y}(t)=f\left(\bm{X}\left(t\right)\right)$, as illustrated in figure 1.

$Y(t)$ Consulting Experts $\begin{bmatrix}X_{1}(t)\\\ \vdots\\\
X_{N}\left(t\right)\end{bmatrix}$ Aggregating Opinions $f(\cdot)$ $\hat{Y}(t)$
Figure 1: Instantaneous Opinion Aggregation

It is often difficult to find meaningful unsupervised rules that are
instantaneous, with a notable exception: Majority voting, denoted by
$V\left(\bm{X}(t)\right)$, is a commonly-accepted baseline for unsupervised
rules:

$V\left(\bm{X}(t)\right)=\operatorname{sign}\left(\sum_{i=1}^{N}X_{i}(t)\right),$
(8)

where ties are broken arbitrarily. It is often taken for granted that ties
being broken arbitrarily is a direct consequence of Assumption 1. Indeed, if a
prior $p_{Y}\left(y\right)$ on $Y(t)$ were known,

$\hat{Y}=\operatorname*{arg\,max}_{y\in\left\\{-1,1\right\\}}\mathbb{P}\left(Y=y\right)$

should be chosen in the event of a tie [7].

Conjectures of Marquis de Condorcét, [25], has long been debated in the social
choice literature i.a. [26, 27, 28], revealing that majority voting is not
reliable when heterogeneous ($p_{i}\in[0,1]$) or arbitrarily weak
($p_{i}\rightarrow\nicefrac{{1}}{{2}}$) populations of experts are concerned.

####  II-C2 Block(-Iterative) Opinion Aggregation

A strategy that processes a collection of opinions
$\left\\{X_{i}\left(t\right):\left(i,t\right)\in\mathcal{N}\times\mathcal{T}\right\\}$
to estimate the corresponding states
$\left\\{\hat{Y}(t):t\in\mathcal{T}\right\\}$ is a block opinion-aggregation
rule. Conceptually, these rules, often iteratively, process past opinions to
decide for the respective block of tasks. We focus on block rules that
leverage all the available opinions with $\mathcal{N}=[N]$ and
$\mathcal{T}=\mathbb{T}$, as illustrated in figure 2.

$\begin{matrix}Y(1)&\cdots&Y(T)\end{matrix}$ Consulting Experts
$\begin{bmatrix}X_{1}(1)&\cdots&X_{1}(T)\\\ \vdots&\ddots&\vdots\\\
X_{N}(1)&\cdots&X_{N}(T)\end{bmatrix}$ Aggregating Opinions $f(\cdot)$
$\begin{matrix}\hat{Y}(1)&\cdots&\hat{Y}(T)\end{matrix}$Block Inference Figure
2: Block(-iterative) Opinion Aggregation

Often, off-line techniques such as expectation maximization, belief
propagation, or spectral decomposition methods are used iteratively on a
collection of opinions [14, 15, 18, 17, 16]. Specifically, belief propagation
has been shown to asymptotically minimize the probability of error for
specific sparse subsets $\mathcal{N}\subset[N]$, often referred to as task-
assignment [14]. The singular value distribution of the empirical covariance
matrix of opinions has also been investigated for opinion aggregation [16,
24]. Adaptations of expectation maximization algorithm have been proposed for
adaptive block-processing and task-dependent modeling of competences [15, 17].
These methods are generally computationally expensive and they seldom yield
provable guarantees for their performance.

####  II-C3 Adaptive Opinion Aggregation

A strategy that infers the underlying probability law sequentially from past
observations is an adaptive opinion-aggregation strategy. Formally, they have
the form $\hat{Y}(t)=f_{t}\left(\mathbf{X}(t)\right)$, as illustrated in
figure 3.

$Y(t)$ Consulting Experts $\begin{bmatrix}X_{1}(t)\\\ \vdots\\\
X_{N}\left(t\right)\end{bmatrix}$ Aggregating Opinions $f_{t}(\cdot)$
$\hat{Y}(t)$$\begin{matrix}Y(t-1)\\\ \vdots\\\
Y(1)\end{matrix}$$\begin{bmatrix}X_{1}(1)&\cdots&X_{1}(t-1)\\\
\vdots&\ddots&\vdots\\\ X_{N}(1)&\cdots&X_{N}(t-1)\end{bmatrix}$ Memory or
Inference Figure 3: Adaptive Opinion Aggregation

These strategies often estimate and employ empirical competence estimates
$\left\\{\hat{p}_{1},\cdots,\hat{p}_{N}\right\\}$ in the decision making
process and, traditionally, they are almost exclusively formulated as
supervised opinion-aggregation strategies that have access to state feedback
or additional “meta”-training [12, 13, 20].

This paper proposes a set of non-iterative, unsupervised decision-aggregation
strategies with quantifiable performance guarantees. Inspired from the naïve
Bayes decision rule, which is the likelihood ratio test for known competences
$\left\\{p_{1},\cdots,p_{N}\right\\}$, [20, 7], we propose block-decision
aggregation rules and discuss its adaptive extension. The proposed rules
employ biased estimates of expert competences, called pseudo competences,
directly.

##  III Unsupervised Estimation of Competences

Let the experts $\left\\{X_{1},\cdots,X_{N}\right\\}$ be characterized by the
probability law (1)-(3). Then, the true competence $p_{i}$ of an expert can
objectively be measured by the frequency with which the expert successfully
identifies the true state:

$\hat{p}_{i}(T)=\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(X_{i}(t)=Y(t)\right).$
(9)

The ergodicity of the process $\mathds{1}\left(X_{i}(t)=Y(t)\right)$, which
follows from (1)-(3), yields that $\hat{p}_{i}(T)\rightarrow p_{i}$ as the
number of tasks increases. However, an unsupervised decision maker does not
have access to $Y\left(t\right)$ and therefore, cannot make use of these
reliable competence estimates $\hat{p}_{i}(T)$ for decision making.

Conceptually, measuring the quality of an opinion without knowing the true
state, or the ground-truth, is a commonly-encountered challenge in human
decision-making: One might accept the consensus of extrinsic opinions on a
task as the truth to the best of one’s knowledge. We define a form of opinion-
based reliability, or the pseudo competence of an expert, as the likelihood of
an expert agreeing with independently-generated opinions from other experts:

$\tilde{p}_{i}\triangleq\mathbb{P}\left(X_{i}(t)=V\left(\mathbf{X}_{\setminus{i}}(t)\right)\right),\forall
t\in\mathbb{T}.$ (10)

As discussed in Section II, majority vote is an intuitive decision rule that
is often accepted as the baseline and it leads to the notion of agreeing with
peers. Formally, the subset $\mathbf{X}_{\setminus{i}}$ are the peers of the
expert $X_{i}$ and their collective competence under majority vote is denoted
by:

$p_{\setminus i}\triangleq\mathbb{P}\left(Y(t)=V\left(\mathbf{X}_{\setminus
i}(t)\right)\right),\forall t\in\mathbb{T}.$

It follows from the law of total probability that pseudo competence is a
function of the entire committee $\left\\{p_{1},\cdots,p_{N}\right\\}$ [29]:

$\tilde{p}_{i}=p_{i}p_{\setminus i}+q_{i}q_{\setminus i},$ (11)

where, $q_{\setminus i}=1-p_{\setminus i}$. If one chooses to accept the
frequency with which an expert agrees with peers as the empirical competence
estimate for that expert:

$\hat{\rho}_{i}\left(T\right)=\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(x_{i}(t)=V\left(\mathbf{x}_{\setminus
i}(t)\right)\right)$ (12)

then, it is possible to infer competences, in the form of pseudo competences,
in real-time. Similar to the true competence estimates, the ergodicity of the
process $\mathds{1}\left(X_{i}(t)=V\left(\mathbf{X}_{\setminus
i}(t)\right)\right)$, which follows (1)-(3), yields that
$\hat{\rho}_{i}\left(T\right)\rightarrow\tilde{p}_{i}$ as the number of tasks
increases. Furthermore, (12) enables distributed estimation and ranking of
competences on strongly connected networks [30].

The key aspects of the pseudo competence are the exclusion of self-opinions
$\mathbf{X}_{\setminus{i}}$ and the concomitant competence of the peers
$p_{\setminus i}$. Exclusion of self-opinions is rather intuitive as an expert
always agrees with itself, hence including self-opinions would bias the pseudo
competence towards the expert that is being measured. The collective expertise
of the peers on the other hand, is critical for pseudo competence to make
sense. Conceptually, as one should not measure the competence of an expert
with the likeliness of failure, one should not measure it by the likelihood of
agreement with those who fail often.

Nonetheless, it is clear from (11) that $p_{\setminus i}>\nicefrac{{1}}{{2}}$,
$\forall i\in[N]$ would ensure meaningful inference in the sense that pseudo
competence preserves ordering and the sign of $p_{i}-\nicefrac{{1}}{{2}}$. If
in addition, $p_{\setminus i}\approx p_{\setminus j}$, $\forall i\neq j$, one
could also expect $\left|\tilde{p}_{i}-p_{i}\right|$ to scale similarly. It
is, however, not clear whether an arbitrary committee would satisfy either of
these conditions. Next, we address what we call good committees
$(p_{i}>\nicefrac{{1}}{{2}},\forall i\in[N])$ and mixed committees
$(p_{i}\in[0,1],\forall i\in[N])$ and explore the conditions that would yield
reliable and meaningful inference.

###  III-A Properties of Pseudo Competence for Good Committees

We call a committee good when every expert is sufficiently competent,
$p_{i}>\nicefrac{{1}}{{2}}$, $\forall i\in[N]$ for a finite $N$, and
consequently, when every expert has collectively competent peers,
$p_{\setminus i}>\nicefrac{{1}}{{2}}$, $\forall i\in[N]$. It is often mistaken
that for countably-infinite committees $\left\\{p_{i}:i\in\mathbb{N}\right\\}$
that $p_{i}>\nicefrac{{1}}{{2}},\forall i$, is sufficient for $p_{\setminus
i}>\nicefrac{{1}}{{2}}$, $\forall i$; a counter example is given in [26, pg.
17]. Therefore, for countably-infinite good committees, we allow that
$p_{i}>\nicefrac{{1}}{{2}}+\varepsilon$ for some
$\varepsilon\in\left(0,\nicefrac{{1}}{{2}}\right)$ for every expert.
Proposition 1 summarizes the key properties of pseudo competence for a good
committee.

######  Proposition 1.

For every good committee of size $N>2$ pseudo competences satisfy:

  1. 1.

Ordering: $p_{i}>p_{j}\iff\tilde{p}_{i}>\tilde{p}_{j}$,

  2. 2.

Under-estimation: $\nicefrac{{1}}{{2}}<\tilde{p}_{i}<p_{i}$.

The pseudo competences preserve the ordering of the true competences and they
are strictly greater than $\nicefrac{{1}}{{2}}$ for good committees – proof is
given in appendix A. On the other hand, pseudo competence penalizes the most
competent experts while evaluating lower-competence experts relatively more
accurately as illustrated in fig. 4(a) for $N=10$ experts with competences
uniformly spaced over $[0.5,0.9]$. Even though a good committee is sufficient
to ensure that committee as a whole is sufficient in the absence of any
individual expert $\left(p_{\setminus i}>\nicefrac{{1}}{{2}},\forall
i\right)$, it is not necessary. Therefore, we discuss the conditions that
ensure reliable peers for every expert for mixed committees next.

((a)) A Good Committee

((b)) A Mixed Committee

Figure 4: A Comparison of Pseudo Competences $\tilde{p}_{i}$ to True
Competences $p_{i}$, Self-Excluding Majority $p_{\setminus i}$ as Reference

###  III-B Properties of Pseudo Competence for Mixed Committees

Pseudo competence relies on the notion that the committee, as a whole, is a
sufficiently competent reference point that it is robust to the absence of any
individual expert. Certainly, this notion is not valid for all mixed
committees: Reliable unsupervised opinion aggregation is unattainable when
many experts are unreliable, for instance,
$\left(\left|i:p_{i}\leq\nicefrac{{1}}{{2}}\right|\rightarrow N\right)$.
Nonetheless, it is of practical interest to investigate mixed committees that
are competent as a whole.

Often, a notion of consistency arise in various supervised or unsupervised
learning, inference, and decision rules i.a. [12]. Consistency under majority
vote, also known as Condorcet’s Jury Theorem [27, 26, 25], is defined as
follows.

######  Definition 1 (Consistency).

A committee of experts $\left\\{X_{i}\right\\}_{i\in\mathbb{N}}$ with
competences $\left\\{p_{i}\right\\}_{i\in\mathbb{N}}$ is consistent under
majority voting if:

$\lim_{N\rightarrow\infty}\mathbb{P}\left(V\left(X_{1},\cdots,X_{N}\right)=Y\right)=1.$

An explicit characterization of consistent mixed committees is non-trivial and
addressed in [26, 27, 28]. One should note that the sequence
$\mathbb{P}\left(V\left(X_{1},\cdots,X_{N}\right)=Y\right)$ is not necessarily
monotonically increasing in $N$ for a consistent committee, even when
$p_{i+1}>p_{i}$, $\forall i$. However, for every consistent committee, there
exists a monotonically increasing, tight lower bound $a_{N}\leq v_{N}$ that we
call the rate of consistency:

$a_{N}=\inf_{n\geq
N}\mathbb{P}\left(V\left(X_{1},\cdots,X_{n}\right)=Y\right).$ (13)

The rate of consistency determines the asymptotic performance of decision
aggregation rules that use pseudo competences. Proposition 2 extends the
notion of under-estimation in proposition 1 to what we call pessimistic
estimation for mixed committees:

######  Proposition 2.

For every consistent committee $\left\\{p_{i}\right\\}_{i\in\mathbb{N}}$,
there exists a committee size $n^{*}$ such that $\forall N>n^{*}$ pseudo
competences satisfy:

  1. 1.

Ordering: $p_{i}\geq p_{j}\iff\tilde{p}_{i}\geq\tilde{p}_{j}$

  2. 2.

Pessimism:
$\min\left\\{\tilde{p}_{i},1-\tilde{p}_{i}\right\\}\geq\min\left\\{p_{i},1-p_{i}\right\\}$.

Conceptually, it indicates that good experts
$\left(p_{i}>\nicefrac{{1}}{{2}}\right)$ are underestimated and bad ones
$\left(p_{j}<\nicefrac{{1}}{{2}}\right)$ are overestimated – proof given in
appendix B. Figure 4(b) illustrates proposition 2 for $N=10$ experts with
competences uniformly spaced over $\left[0.3,0.9\right]$, where pessimism
property is illustrated visually. This property arises as more competent
experts in a fixed committee are compared to the relatively weaker subsets of
peers that exclude those competent experts. A condition for finite mixed
committees to satisfy proposition 2 is given by (22) in appendix A.

The pseudo competence (10) provides a metric that can be estimated in real-
time via (12) and that requires no side-information beyond the existence of a
probability law characterized by (1)-(3). It preserves the ordering of the
true competences and it neither mistakes a bad expert for a good one nor it
does the opposite. Therefore, it provides a reliable unsupervised metric for
estimating the underlying probability law directly. Section IV investigates
the minimum probability of error achieving opinion-aggregation strategy, then
section V substitutes the true probability law with the pseudo probability
law.

##  IV Naïve Bayes Decision Rule and Its Performance Guarantees

Consider the family $\mathcal{D}$ of possibly randomized decision rules that
aggregate $N$ opinions $\mathbf{X}\left(t\right)$ to decide on a state $Y(t)$.
The minimum probability of error (MPE)-achieving strategy is an instantaneous
opinion-aggregation rule:

$f^{MPE}=\operatorname*{arg\,min}_{f\in\mathcal{D}}\mathbb{P}\left(f\left(\mathbf{X}\right)\neq
Y\right).$

Note that the competences $\left\\{p_{1},\cdots,p_{N}\right\\}$ being fixed
across all tasks $t\in\mathbb{T}$ allows task-dependency of opinions
$\mathbf{X}\left(t\right)$ and states $Y(t)$ to be dropped. It is well known
that the maximum a posteriori rule achieves the minimum probability of error
[7]. Therefore, the MPE-achieving supervised opinion-aggregation strategy is
given by:

$f^{MPE}\left(\mathbf{X}\right)=\operatorname*{arg\,max}_{y\in\left\\{\pm
1\right\\}}\mathbb{P}\left(y\;\middle|\;\mathbf{X}\right),$

with the corresponding likelihood-ratio test:

$f^{MPE}(\mathbf{X})=\operatorname{sign}\left(\sum_{i=1}^{N}X_{i}\log\frac{p_{i}}{q_{i}}\right)\equiv
f^{NB}(\mathbf{X}).$ (14)

The decision rule in (14) is often referred to as naïve Bayes decision rule
(NB) [20]. The existence of the probability law defined by (1)-(3) ensures
that NB decision rule is instantaneous and that it has no bias term in the
sign function.

As a direct consequence of being the maximum a posteriori rule, the
probability of error of the naïve Bayes decision rule can be written
explicitly as:

$\displaystyle\mathbb{P}\left(f^{NB}(\mathbf{X})\neq Y\right)$
$\displaystyle=\frac{1}{2}\sum_{\bm{x}\in\left\\{\pm
1\right\\}^{N}}\min_{y\in\left\\{\pm
1\right\\}}\mathbb{P}\left(\mathbf{X}=\bm{x}\;\middle|\;Y=y\right).$

Even though $\min_{y\in\left\\{\pm
1\right\\}}\mathbb{P}\left(\mathbf{X}=\bm{x}\;\middle|\;Y=y\right)$ is easy to
compute $\forall\bm{x}$ when $\left\\{p_{1},\cdots,p_{N}\right\\}$ is known,
the sum is still intractable for large $N$, which motivates research for lower
and upper bounds. It has been shown that a set of lower and upper bounds can
be found in the form [20, Theorem 1]:

$-\log\mathbb{P}\left(f^{NB}(\mathbf{X})\neq Y\right)\asymp\Phi,$

where $\asymp$ denotes upper and lower bounds within a constant factor. As a
function of the true competences $\left\\{p_{1},\cdots,p_{N}\right\\}$, $\Phi$
is called the committee potential, [20, 31, 32] and it is given by:

$\Phi\left(\bm{p}\right)=\sum_{i=1}^{N}\left(p_{i}-\frac{1}{2}\right)\log\frac{p_{i}}{q_{i}}.$
(15)

The upper-bound given in [20, Theorem 1(i)] makes a clever use of the Chernoff
bounding technique, see, for instance, [33, Chapter 2.2.1], and Kearns-Saul
inequality [32, Lemma 1]. A detailed discussion on Kearns-Saul and Berend-
Kontorovich concentration inequalities for mixtures of independent, bounded
random variables is given in [33, Chapter 2.2.4].

Figure 5: A Comparison of Upper-Bounds for Naïve Bayes Probability of Error

Interestingly, in the case of naïve Bayes decision rule, the subsequent use of
Kearns-Saul inequality appears unnecessary. As shown in appendix C, a direct
consequence of the Chernoff bounding technique is as follows:

######  Theorem 1.

The following tight upper-bound holds:

$\mathbb{P}\left(f^{NB}\left(\mathbf{X}\right)\neq
Y\right)\leq\prod_{i=1}^{N}\sqrt{4p_{i}q_{i}}.$

Theorem 1 is the sharpest bound attainable by the use of Chernoff bounding
technique and it is tight, as evidenced by, $\exists i:p_{i}=1$, in addition
to the regimes discussed in [20]. Figure 5 provides a comparison of bounds
between that given in theorem 1 and that in [20, Theorem 1] for
$N\in\left[10,50\right]$ experts with equally-spaced competences chosen from
the interval $\left[0.3,0.9\right]$.

Observe that $w(p)=\log\frac{p}{1-p}\in\left(-\infty,\infty\right)$ is an
unbounded function that monotonically increases over $p\in[0,1]$. On one hand,
when competences are known reliably, $w(p)$ ensures that highly competent
experts are almost exclusively relied upon. On the other hand, in empirical
setups, where competences are to be estimated, direct use of $w(\hat{p})$
would jeopardize the robustness of opinion-aggregation rule: An expert with
arbitrary competence $p_{i}<1$ could be assigned, with non-negligible
probability, a competence estimate $\hat{p}_{i}\approx 1$ and thus, an
unbounded weight when the number of labeled tasks is limited. In such cases, a
linearized naïve Bayes (LNB) decision rule could be considered:

$f^{LNB}(\mathbf{X})=\operatorname{sign}\left(\sum_{i=1}^{N}X_{i}\left(p_{i}-\nicefrac{{1}}{{2}}\right)\right).$
(16)

Alternatively, one might focus on a practical subset of committees, one that
we call absolutely balanced committees, that excludes almost-all-knowing
$\left(p\approx 1\right)$ and almost-ever-lying $\left(p\approx 0\right)$
experts.

######  Definition 2 (Absolute Balance).

A committee $\left\\{p_{i}\right\\}_{i\in\mathbb{N}}$ is absolutely-balanced
if $\exists\gamma\in\left(0,\nicefrac{{1}}{{2}}\right)$ such that
$p_{i}\in(\gamma,1-\gamma)$, $\forall i$. The factor $\gamma$ is called the
balancing parameter of the committee.

For an absolutely-balanced committee, not only the true competence estimates
$\left\\{\hat{p}_{1}(T),\cdots,\hat{p}_{N}(T)\right\\}$, defined in (9), yield
robust empirical implementation of the NB rule through direct substitution
into (14) but they also enable the empirical use of LNB rule by substitution
into (16) that exhibit similar performance with NB.

Section III shows that a set of opinions can be used to estimate true
competences $\left\\{p_{1},\cdots,p_{N}\right\\}$ in the form of pseudo
competences $\left\\{\tilde{p}_{1},\cdots,\tilde{p}_{N}\right\\}$. Section V
shows that for an absolutely balanced committee, one could indeed achieve an
unsupervised opinion-aggregation performance that scales with the committee
potential, therefore, with the performance of MPE-achieving rule, while
suffering from error due to bias between pseudo and true competences that
diminishes in the number of experts consulted.

##  V The Pseudo Naïve Bayes Decision Rule

In the unsupervised problem setup, true competence estimates
$\left\\{\hat{p}_{1},\cdots,\hat{p}_{N}\right\\}$ are not achievable, where,
over $T$ tasks, the pseudo competence estimates
$\left\\{\hat{\rho}_{1}\left(T\right),\cdots,\hat{\rho}_{N}\left(T\right)\right\\}$
can be inferred. An opinion-aggregation rule that use pseudo competence
estimates does not only suffer performance degradation due to empirical
estimation error but due to the bias $\left|p_{i}-\tilde{p}_{i}\right|$ as
well. The goal of this section is to first propose fundamental limits for a
decision rule that has access to pseudo competences
$\left\\{\tilde{p}_{1},\cdots,\tilde{p}_{N}\right\\}$ directly.

Let us call the following opinion aggregation rule the pseudo naïve Bayes
(PNB) rule:

$f^{PNB}(\mathbf{X})=\operatorname{sign}\left(\sum_{i=1}^{N}X_{i}\log\frac{\tilde{p}_{i}}{\tilde{q}_{i}}\right).$
(17)

The PNB rule corresponds to assuming that the underlying probability law is
characterized by the pseudo competences
$\left\\{\tilde{p}_{1},\cdots,\tilde{p}_{N}\right\\}$, where it is actually
characterized by the true competences $\left\\{p_{1},\cdots,p_{N}\right\\}$.
PNB rule, similar to NB rule, is an instantaneous decision rule. Different
from NB rule, PNB rule is empirically achievable without supervision.

Formally, we show that the performance of PNB rule scales with the underlying
true committee potential $\Phi\left(\bm{p}\right)$, as defined in (15), and
the performance degradation due to the use of pseudo competences is quantified
as follows:

$-\log\mathbb{P}\left(f^{PNB}(\mathbf{X})\neq
Y\right)\asymp(1-\delta(a_{N},\gamma))\Phi.$

Here, $\delta(\cdot)$ represents the performance degradation due to lack of
supervision and it is a bounded function of the rate of consistency $a_{N}$
from (13) and the balancing parameter $\gamma$ from definition 2. The variable
$\delta(\cdot)$ diminishes both in $a_{N}$ and $\gamma$ due to the difference
between pseudo competences and true competences diminishing in $a_{N}$ and
$\gamma$ limiting the maximum difference between pseudo competences and true
competences.

Let us note that the performance of the PNB decision rule exhibits a similar
scaling to that of NB, as long as exclusion of any expert leaves committee
reliable ($p_{\setminus i}>\nicefrac{{1}}{{2}}$, $\forall i$):

$-\log\mathbb{P}\left(f^{PNB}(\mathbf{X})\neq Y\right)\asymp\tilde{\Phi}.$
(18)

Here, we call the term $\tilde{\Phi}$ pseudo committee potential:

$\tilde{\Phi}=\sum_{i=1}^{N}\left(p_{i}-\frac{1}{2}\right)\log\frac{\tilde{p}_{i}}{1-\tilde{p}_{i}}.$

The relation in (18) follows algebraically from the proof of [20, Theorem 1]
by the use of property 2, and it is outlined in appendix D.

The pseudo committee potential $\tilde{\Phi}$ and true committee potential
$\Phi$ converge at a rate that is determined by the rate at which the
underlying committee becomes consistent in the majority vote. Theorem 2
quantifies the rate at which the performance of the PNB decision rule scales
with that of NB.

######  Theorem 2.

Every absolutely balanced, consistent committee with rate $a_{N}$ and
balancing parameter $\gamma$ satisfies:

$\frac{\tilde{\Phi}}{\Phi}\geq
1-C(\nicefrac{{1}}{{2}}-\gamma)\rho_{N}\longrightarrow_{N}1.$

Here,
$\rho_{N}=\nicefrac{{\left(1-a_{N}\right)}}{{\left(a_{N}-\nicefrac{{1}}{{2}}\right)}}$
and $C(x)$ is a positive function supported on
$x\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$.

Theorem 2 indicates that PNB rule is not only asymptotically optimal, but it
approaches to the performance of the optimal (supervised) decision rule that
becomes consistent at a rate that is faster than that of majority vote,
$a_{N}$. A dual of this result can be formulated as follows:

######  Corollary 1.

A sufficient condition for any absolutely balanced committee of size $N$ to
ensure that $1-\delta\leq\frac{\tilde{\Phi}}{\Phi}$ is as follows:

$\frac{1-p_{\setminus i}}{p_{\setminus
i}-\nicefrac{{1}}{{2}}}\leq\frac{\delta}{C(\nicefrac{{1}}{{2}}-\gamma)},\forall
i\in[N].$

Decision rules that employ some relevant statistics in a functional form that
is known to perform well are often called “plug-in” decision rules. Plug-in
rules are often difficult to analyze and are often suboptimal [34, Chapter 1].
Interestingly, despite being a plug-in rule, PNB rule achieves minimum
probability of error asymptotically, thanks to the construction of the pseudo
competences.

PNB rule, as defined in (17), is instantaneous because it uses pseudo
competences directly, which, in practice, should be estimated from the
opinions empirically. The manner in which pseudo competence estimates are
updated gives rise to the operational meaning of the corresponding decision
aggregation rule, as addressed in Section VI.

##  VI Empirical Rules that Use Pseudo-Competences

A block-processing, empirical, and unsupervised opinion-aggregation rule can
be constructed from pseudo competence estimates via:

$f^{B}(\mathbf{X}(t))=\operatorname{sign}\left(\sum_{i=1}^{N}\bm{X}_{i}(t)w(\hat{\rho}_{i}\left(T\right))\right).$
(19)

Note that (19) first estimates pseudo competences over $T$ tasks then
aggregates the available opinions. With this understanding, one might drop the
time-dependence for a block-processing rule. The weight function $w(\cdot)$
can be picked based on the number of tasks. The adaptive extension of (19) is
as follows:

$f^{A}_{t}(\mathbf{X}(t))=\operatorname{sign}\left(\sum_{i=1}^{N}X_{i}(t)w(\hat{\rho}_{i}\left(t\right))\right).$
(20)

Asymptotically, both of the empirical rules should achieve optimality at a
rate close to that of NB rule, as Theorem 2 indicates. The objective is to
quantify the impact of empirical estimation error.

###  VI-A Block Opinion Aggregation

Pseudo competences can be estimated dynamically in real-time or over a block
of opinions. When a block of opinions is processed, the performance of the
corresponding empirical PNB decision rule $f^{B}\left(\cdot\right)$ is
determined by:

  1. 1.

Pseudo Competence Bias: $\left\|\tilde{\bm{p}}-\bm{p}\right\|_{1}$,

  2. 2.

Empirical Estimation Error:
$\left\|\hat{\bm{\rho}}\left(T\right)-\tilde{\bm{p}}\right\|_{1}$.

Note that pseudo competence bias is the cost of operating in an unsupervised
setup and it is a hidden-yet-fixed function of $\bm{p}$ for every committee.
Empirical estimation error, on the other hand, introduces a non-linear
distortion that propagates through the weights
$w\left(\hat{\bm{\rho}}\left(T\right)\right)$ of the decision rule.

When each expert can only be consulted for a small number $T$ of tasks, a
rather coarse, high-variance, estimate, $\tilde{p}_{i}(T)$, is achievable, and
hence the corresponding weights
$w(\tilde{p})=\log\frac{\tilde{p}}{1-\tilde{p}}$ might be arbitrarily large.
In order to rectify this non-robust behavior, a linearized version of the
weights $\ell(\tilde{p})=\tilde{p}-\nicefrac{{1}}{{2}}$, which follows from
the first order Taylor series expansion of $w\left(\tilde{p}\right)$ around
$\tilde{p}=\nicefrac{{1}}{{2}}$, can be used:

$f^{L}(\mathbf{X})=\operatorname{sign}\left(\sum_{i=1}^{N}X_{i}(\hat{\rho}_{i}\left(T\right)-\nicefrac{{1}}{{2}})\right).$
(21)

It is clear that (21) should not suffer from estimation error as much as
empirical PNB rule with $w(\tilde{p})=\log\nicefrac{{\tilde{p}}}{{\tilde{q}}}$
(19). The main challenge for such a rule is to achieve consistency, as
addressed next.

######  Proposition 3.

If a committee satisfies:

  1. 1.

(Naïve Bayes)
$\lim_{N\rightarrow\infty}\frac{1}{\sqrt{N}}\sum_{i=1}^{N}(p_{i}-\nicefrac{{1}}{{2}})^{2}=\infty$,

  2. 2.

(Majority)
$\lim_{N\rightarrow\infty}\frac{1}{\sqrt{N}}\sum_{i=1}^{N}(p_{i}-\nicefrac{{1}}{{2}})\geq\sqrt{\frac{\log
2}{8}}$,

then $f^{L}(\cdot)$ is consistent:
$\lim\limits_{N\rightarrow\infty}\mathbb{P}\left(f^{L}(\mathbf{X})\neq
Y\right)=0$.

Proposition 3 shows that when arbitrarily large number of experts are
consulted for a small number of tasks each, the unsupervised empirical PNB
rule becomes reliable.

The first condition of proposition 3 is a direct consequence of the
Hoeffding’s inequality ans it is sufficient for consistency when each expert
is tested with a small number of labeled tasks and competences are estimated
via (9) [20, Theorem 7]. Interestingly, pseudo competences can facilitate this
consistency without the need for labeled data but at the expense of the second
condition, which is by no means restrictive: As discussed in appendix E, it
amounts to
$\lim_{N\rightarrow\infty}\mathbb{P}\left(V\left(\bm{X}\right)=Y\right)>\nicefrac{{1}}{{2}}$.
Similar requirements exist in the Bayesian framework as well [14].

When there are sufficiently many tasks to be processed, the error due to
empirically estimating $\tilde{\bm{p}}$ diminishes and pseudo competence bias
becomes the dominant factor of performance degradation. Thus, the PNB rule
given in (17) naturally extends to a decision rule (19) that empirically
estimates the pseudo competence of each expert over $T$ tasks and applies to
$w\left(\tilde{p}_{i}\right)=\log\nicefrac{{\tilde{p}_{i}}}{{\tilde{q}_{i}}}$.

For an arbitrary committee $\bm{p}\in\left[0,1\right]^{N}$, the difference
between pseudo competences and true competences become unbounded for experts
with $p_{i}\approx\left\\{0,1\right\\}$. However, for absolutely balanced
committees, pseudo competence bias is necessarily bounded. Lemma 1 quantifies
the committees that limit the difference between PNB and NB weights.

######  Lemma 1.

Let $R(\gamma)=\frac{2\gamma(1-\gamma)}{1-2\gamma}$, if an absolutely balanced
committee satisfies for some $\epsilon>0$

$\min_{i\in[N]}p_{\setminus i}\geq\frac{1}{2}+\frac{1}{2+\epsilon R(\gamma)},$

then $\left\|\bm{w}-\tilde{\bm{w}}\right\|_{1}\leq\frac{\epsilon N}{2}$.

Observe $R(\gamma)$ increases in $\gamma$, equivalently, committees  that
concentrate towards the center of the cube $\left[0,1\right]^{N}$ yield closer
weights. Conceptually, this amounts to discussion on weak classifiers; it is
often easier to boost weak classifiers to form a stronger one [13]. The next
theorem jointly addresses the empirical estimation error and pseudo competence
bias:

######  Theorem 3.

Let a committee be consistent with rate $a_{N}$,
$\forall\delta\in\left(0,1\right)$ define
$C(\delta;N,T)\triangleq\frac{12}{T}\log\frac{8N}{\delta}$. Then,

$\forall\epsilon\in\left(\left(\rho_{N}C(\delta;N,T)\right)^{\nicefrac{{1}}{{3}}},\min\left\\{5,\frac{2\Phi}{N}\right\\}\right),$

and for all absolutely balanced committees with parameter
$\gamma>C(\delta;N,T)\left(\frac{2}{\sqrt{4\epsilon+1}-1}\right)^{2}$:

$\mathbb{P}\left(f^{B}(\mathbf{X})\neq\mathbf{Y}\right)\leq\delta+\exp\left[-\frac{\left(2\Phi-\epsilon
N\right)^{2}}{8\Phi}\right].$

Property 2 along with Lemma 1 allows $f^{B}(\cdot)$ to scale similar to an
empirical NB as long as the underlying worker committee is sufficiently
strong, which is captured by $\delta$. Theorem 3 borrows its empirical
analysis from that of [20, Theorem 11], which quantifies the performance of
empirical NB under sufficiently long training.

Albeit insightful, Proposition 3 and Theorem 3 analyze the performance of
empirical PNB decisions rules for a block of opinions. An adaptive and
instantaneous opinion aggregation rule is addressed next.

###  VI-B Adaptive Opinion Aggregation

Let $f^{A}_{\tau}(\cdot)$ denote the empirical pseudo naïve Bayes decision
rule defined by the weights $\tilde{\bm{w}}(\tau)$ as given in (20). We call
the probability that the decision rule $f^{A}_{\tau}(\cdot)$ makes the correct
decision based on $X(t)$, that is,
$\mathbb{P}\left(f^{A}_{\tau}(\mathbf{X}(t))=Y\right)$, for $\forall t>\tau$,
the confidence of the real-time decision rule. Theorem 4 characterizes this
notion of confidence:

######  Theorem 4.

Let
$\delta\geq\sum_{i=1}^{N}\left|p_{i}-\tilde{p}_{i}\right|+\frac{N}{\sqrt{\tau}}$
and define the event $R(\tau)$ as follows:

$\exp\left(-\frac{1}{2}\sum_{i=1}^{N}\left(\tilde{p}_{i}(\tau)-\frac{1}{2}\right)\log\frac{\tilde{p}_{i}(\tau)}{1-\tilde{p}_{i}(\tau)}\right)\leq\frac{\delta}{2}.$

Then $\forall t>\tau$,
$\mathbb{P}\left(R(\tau)\cap\left\\{f^{A}_{\tau}\left(\mathbf{X}(t)\right)\neq
Y\right\\}\right)\leq\delta$.

The term
$\sum_{i=1}^{N}\left|p_{i}-\tilde{p}_{i}\right|\leq\sum_{i=1}^{N}(1-p_{\setminus
i})$, diminishes with the committee potential, which can be seen from Kearns-
Saul or Berend-Kontorovich inequalities.

The analysis of [20] on the adaptive empirical naïve Bayes decision rule is
based on the committee potential being empirically estimated from some labeled
data to control the worst case performance on the test data. Theorem 4 extends
this analysis to use empirical pseudo competences instead, resulting in a
real-time algorithm where the player builds an empirical pseudo committee
potential and makes decisions with dynamic confidence.

The adaptive decision aggregation rule $f^{A}_{\tau}(\cdot)$ is a sequential
decision making mechanism: at any given time $t\in[T]$ the algorithm makes a
decision with confidence $\delta$ if $R(\tau)$ has happened for some $\tau<t$
otherwise, it assigns the majority vote. This allows the algorithm to a make
decisions with dynamic confidence; once a confidence level is achieved at
$t=\tau$, there is no need to keep updating the weights as the decision rule
is finalized and algorithm uses that fixed decision rule on the incoming data.

##  VII Experiments

((a)) A Good Committee

((b)) A Mixed Committee

Figure 6: A Performance Comparison between Naïve Bayes Rules and Their
Unsupervised Counterparts

We briefly illustrate through synthetic data the impact of mixed/good
committees of varying sizes $N$ and balancing parameters $\gamma$ on the
performance of pseudo naïve Bayes decision rule.

In our experiments, pseudo-random tasks and experts that satisfy (1)-(3) are
generated on MATLAB. In order to compare the performance of naïve Bayes
decision rule to its linearized and unsupervised counterparts, we consider a
committee of experts with sizes varying from $N=10$ to $N=75$ with competences
equally spaced in the intervals $[0.15,0.9]$ for the mixed-committee case and
from $[0.5,0.9]$ for the good-committee case. Figure 6 compares the
performance of NB to that of PNB, as defined in (17), where pseudo competences
are estimated over $T=1e+6$ tasks.

The objective is to observe the fundamental operational tendencies: In the
case good committees, illustrated in fig. 6(a), with the majority vote
probability of error starting at the level of $0.1$, the performance
difference between PNB and NB are negligible, which is to be expected since
$p_{i}>\nicefrac{{1}}{{2}}$ for every expert. In the case of a mixed
committee, illustrated in fig. 6(b), where the majority vote probability of
error varies in the interval $\left(0.4,0.37\right)$ for every committee size,
the performance difference with PNB and NB rules is evident. Furthermore, in
the case of a mixed committee the performance PNB converges to that of NB due
to the robustness of the performance of majority vote over large populations
against individual expert exclusions.

((a)) NB vs. LNB

((b)) NB vs. PNB

((c)) PNB vs. Linearized PNB

((d)) LNB vs. Linearized PNB

Figure 7: Impact of Balancing Parameter $\gamma$ on Performance Degradation

Figure 7 illustrates the impact of the balancing parameter $\gamma=1e-n$ for
$n\in\left\\{1,\cdots,5\right\\}$. We allow competences to be picked equally
spaced from $\left[0.5,1-\gamma\right]$ for committee sizes
$N\in\left\\{2,\cdots,50\right\\}$. The performance degradation with respect
to that of NB rule, for LNB, as seen in fig. 7(a), and for PNB, as seen in
fig. 7(b), increases as $\gamma$ decreases. This is to be expected as the
probability of error for NB decision rule is necessarily bounded by $\gamma$,
which is unattainable by other rules due to weight-linearization and pseudo
competence estimation.

##  Appendix A Proof of Proposition 1

###### Proof of Part (1)-Ordering.

Consider any pairs of experts $(X_{i},X_{j})$ for $i\neq j$, and allow
$\eta_{i}=\mathds{1}\left(X_{i}=Y\right)$. Observe that
$\eta_{i}\perp\eta_{j},\forall i\neq j$ are Bernoulli random variables with
parameter $p_{i}$, denoted by $\mathcal{B}(p_{i})$. Successive application of
the law of total probability yields that:

$\displaystyle\tilde{p}_{i}$
$\displaystyle=\mathbb{P}\left(X_{i}=V\left(\mathbf{X}_{\setminus{i}}\right)\right)=\sum_{\eta_{i}}\mathbb{P}\left(X_{i}=V\left(\mathbf{X}_{\setminus{i}}\right)\;\middle|\;\eta_{i}\right)\mathbb{P}\left(\eta_{i}\right)$
$\displaystyle=\sum_{\eta_{i},\eta_{j}}\mathbb{P}\left(X_{i}=V\left(\mathbf{X}_{\setminus{i}}\right)\;\middle|\;\eta_{i},\eta_{j}\right)\mathbb{P}\left(\eta_{j}\;\middle|\;\eta_{i}\right)\mathbb{P}\left(\eta_{i}\right).$

Observe that
$\mathbb{P}\left(\eta_{j}\;\middle|\;\eta_{i}\right)=\mathbb{P}\left(\eta_{j}\right)$
due to the conditional independence of opinions (hence the independence of
opinion generation $\eta_{i}$). A similar extension of $\tilde{p}_{j}$ yields
that:

$\displaystyle\tilde{p}_{j}=\sum_{\eta_{i},\eta_{j}}\mathbb{P}\left(X_{j}=V\left(\mathbf{X}_{\setminus{j}}\right)\;\middle|\;\eta_{i},\eta_{j}\right)\mathbb{P}\left(\eta_{i}\right)\mathbb{P}\left(\eta_{j}\right).$

Since the rest of the committee is arbitrary, yet fixed, the following
conditional probabilities are equal:

$\displaystyle\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{i}}\right)=Y\;\middle|\;X_{j}=Y\right)$
$\displaystyle=\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)=Y\;\middle|\;X_{i}=Y\right),$
$\displaystyle\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{i}}\right)\neq
Y\;\middle|\;X_{j}\neq Y\right)$
$\displaystyle=\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)\neq
Y\;\middle|\;X_{i}\neq Y\right),$

and $p_{i}q_{j}-p_{j}q_{i}=(p_{i}-p_{j})$. Therefore, the ratio between the
differences between pseudo competences and true competences are given by:

/~pi-~pjpi-pj$=$ (22)
$\displaystyle\left[\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)=Y\\!\;\middle|\;X_{i}\neq
Y\right)-\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)\neq
Y\\!\;\middle|\;\\!X_{i}=Y\right)\right].$

As long as (22) is positive, pseudo competence preserves ordering. We now show
that (22) is monotonically increasing in
$p_{i}\in\left(\nicefrac{{1}}{{2}},1\right)$, $\forall i$ and the minimum is
zero. Observe that total law of probability yields by (23) that $\forall
n\in[N]$:

$\frac{\partial}{\partial p_{k}}\mathbb{P}\left(\sum_{i=1}^{N}\eta_{i}\geq
n\right)=\frac{\partial}{\partial
p_{k}}\\!\left[p_{k}\mathbb{P}\left(\sum_{i\neq k}\eta_{i}\geq
n-1\right)\\!+q_{k}\mathbb{P}\left(\sum_{i\neq k}\eta_{i}\geq
n\right)\right]\\!=\mathbb{P}\left(\sum_{i\neq k}\eta_{i}\geq
n-1\right)\\!-\mathbb{P}\left(\sum_{i\neq k}\eta_{i}\geq n\right)$ (23)

$\displaystyle\frac{\partial}{\partial
p_{k}}\mathbb{P}\left(\sum_{i=1}^{N}\eta_{i}\geq n\right)$
$\displaystyle=\mathbb{P}\left(\sum_{i\neq k}\eta_{i}=n-1\right)\geq 0$ (24)
$\displaystyle\frac{\partial}{\partial
p_{k}}\mathbb{P}\left(\sum_{i=1}^{N}\eta_{i}\leq n\right)$
$\displaystyle=-\mathbb{P}\left(\sum_{i\neq k}\eta_{i}=n\right)\leq 0$ (25)

Consequently,
$\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)=Y\;\middle|\;X_{i}\neq
Y\right)$ decreases in $p_{i}$, where
$\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)\neq
Y\;\middle|\;X_{i}=Y\right)$ increases, $\forall i$. Therefore,

$\displaystyle\min_{\begin{subarray}{c}\mathbf{p}\\\
p_{i}>\nicefrac{{1}}{{2}}\end{subarray}}\frac{\tilde{p}_{i}-\tilde{p}_{j}}{p_{i}-p_{j}}=\lim_{\mathbf{p}\rightarrow\nicefrac{{\mathbf{1}}}{{2}}}\frac{\tilde{p}_{i}-\tilde{p}_{j}}{p_{i}-p_{j}}=0,$

which yields that $\tilde{p}_{i}>\tilde{p}_{j}\iff p_{i}>p_{j}$, if
$p_{i}>\nicefrac{{1}}{{2}}$, $\forall i$. ∎

Conceptually, (24)-(25) dictate that increasing the competence of an expert
necessarily decreases the probability of error for majority vote. One should
note that this does not contradict the discussion in Section III as the
consistency of majority vote is concerned with adding a new expert, which does
not ensure any monotonicity, instead of increasing the competence of an
expert, which, as shown, does ensure monotonicity.

###### Proof of Part (2).

Observe that $p_{\setminus i}>\nicefrac{{1}}{{2}}$ for all finite good
committees with $p_{i}>\nicefrac{{1}}{{2}}$, $\forall i$. Then, equation (11)
yields that:

$\displaystyle\tilde{p}_{i}-p_{i}$ $\displaystyle=p_{i}p_{\setminus
i}+(1-p_{i})(1-p_{\setminus i})-p_{i}$
$\displaystyle=(1-2p_{i})(1-p_{\setminus i})<0,$ (26)
$\displaystyle\tilde{p}_{i}-\nicefrac{{1}}{{2}}$
$\displaystyle=(p_{i}-\nicefrac{{1}}{{2}})p_{\setminus
i}+(\nicefrac{{1}}{{2}}-p_{i})(1-p_{\setminus i})$
$\displaystyle=(p_{i}-\nicefrac{{1}}{{2}})(2p_{\setminus i}-1)>0,.$ (27)

Hence, if $p_{i}>\nicefrac{{1}}{{2}}$, $\forall i$, then
$\nicefrac{{1}}{{2}}<\tilde{p}_{i}<p_{i}$. ∎

##  Appendix B Proof of Proposition 2

###### Proof of Part (1).

Equation (22) indicates that any committee satisfying

$\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)=Y\;\middle|\;X_{i}\neq
Y\right)>\mathbb{P}\left(V\left(\mathbf{X}_{\setminus{j}}\right)\neq
Y\;\middle|\;X_{i}=Y\right)$

preserves ordering. For every consistent committee, $\exists N^{*}$ such that
$\forall N>N^{*}$

$\mathbb{P}\left(\sum_{k\neq
i,j}\eta_{k}>\left\lfloor\frac{N-2}{2}\right\rfloor\right)>\mathbb{P}\left(\sum_{k\neq
i,j}\eta_{k}<\left\lceil\frac{N-2}{2}\right\rceil\right),$

which yields that pseudo competence preserves ordering for consistent mixed
committees. ∎

###### Proof of Part (2).

For every consistent committee, $\exists N^{*}$ such that $\forall N>N^{*}$,
$p_{\setminus i}>\nicefrac{{1}}{{2}}$. Recall equations (26)-(27), which yield
that:

/12 $\displaystyle<\tilde{p}_{i}<p_{i}\hskip 7.00002pt\text{if}\hskip
7.00002ptp_{i}>\nicefrac{{1}}{{2}},$ /12
$\displaystyle>\tilde{p}_{i}>p_{i}\hskip 7.00002pt\text{if}\hskip
7.00002ptp_{i}<\nicefrac{{1}}{{2}},$ /12
$\displaystyle=p_{i}=\tilde{p}_{i}\hskip 7.00002pt\text{if}\hskip
7.00002ptp_{i}=\nicefrac{{1}}{{2}}.$

Therefore,
$\min\left\\{\tilde{p}_{i},1-\tilde{p}_{i}\right\\}\geq\min\left\\{p_{i},1-p_{i}\right\\}$
for consistent mixed committees. ∎

##  Appendix C Proof Theorem 1

###### Proof Theorem 1.

Let $w_{i}=\log\nicefrac{{p_{i}}}{{q_{i}}}$. Chernoff bounding technique
yields that [33, Chapter 2.2.1]:

$\mathbb{P}\left(f^{NB}\left(\mathbf{X}\right)\neq Y\right)\leq
e^{-t\Phi}\mathbb{E}\left[\exp\left(-t\sum_{i=1}^{N}w_{i}\left(\eta_{i}-p_{i}\right)\right)\right].$

Observe that the expectation is with respect to
$\eta_{i}\sim\mathcal{B}\left(p_{i}\right)$:

$\mathbb{E}\left[e^{-t\sum\limits_{i}w_{i}\left(\eta_{i}-p_{i}\right)}\right]=p_{i}e^{-q_{i}w_{i}t}+q_{i}e^{p_{i}w_{i}t}.$

Therefore, the probability of error for the NB rule:

$\displaystyle\mathbb{P}\left(f^{NB}\left(\mathbf{X}\right)\neq Y\right)$
$\displaystyle\leq
e^{-t\Phi}\prod_{i}\left(p_{i}e^{-q_{i}w_{i}t}+q_{i}e^{p_{i}w_{i}t}\right)$
$\displaystyle=\exp\underbrace{\left(\textstyle-t\Phi+\sum_{i}\log\left(p_{i}e^{-q_{i}w_{i}t}+q_{i}e^{p_{i}w_{i}t}\right)\right)}_{\triangleq-t\Phi+\phi(t;\bm{p})}.$
(28)

The derivative of $-t\Phi+\phi(t;\bm{p})$ is given in (29), which yields that
(28) is minimized when $t=1$. Hence,

$\frac{\partial}{\partial
t}\left(\phi(t;\bm{p})-t\Phi\right)=\sum_{i}w_{i}\left[\frac{-p_{i}q_{i}e^{-q_{i}w_{i}t}+p_{i}q_{i}e^{p_{i}w_{i}t}}{p_{i}e^{-q_{i}w_{i}t}+q_{i}e^{p_{i}w_{i}t}}-\left(p_{i}-\nicefrac{{1}}{{2}}\right)\right]=\sum_{i}\frac{w_{i}}{2}\left[\frac{-p_{i}e^{-q_{i}w_{i}t}+q_{i}e^{p_{i}w_{i}t}}{p_{i}e^{-q_{i}w_{i}t}+q_{i}e^{p_{i}w_{i}t}}\right]$
(29)

$\displaystyle\mathbb{P}\left(f^{NB}\left(\mathbf{X}\right)\neq Y\right)$
$\displaystyle\leq\exp\left(-\Phi+\phi(1;\bm{p})\right)$
$\displaystyle=\exp\left(-\Phi+\sum_{i}\log
2q_{i}\left(\frac{p_{i}}{q_{i}}\right)^{p_{i}}\right)$
$\displaystyle=\exp\left(\sum_{i}\log 2\sqrt{q_{i}p_{i}}\right),$

yielding the asserted bound. ∎

It is important to note that this bound is the sharpest possible using
Chernoff bounding technique and it is a direct consequence of the weight
function $w(p)=\log\nicefrac{{p}}{{q}}$.

##  Appendix D Proof of Theorem 2

###### Proof of Theorem 2.

Let $\varepsilon_{i}=p_{i}-\nicefrac{{1}}{{2}}$, hence
$\tilde{p}_{i}=\nicefrac{{1}}{{2}}+2\varepsilon_{i}\varepsilon_{\setminus i}$
and observe that

$\frac{\tilde{p}_{i}}{1-\tilde{p}_{i}}=\frac{4\varepsilon_{i}\varepsilon_{\setminus
i}+1}{1-4\varepsilon_{i}\varepsilon_{\setminus
i}}=\frac{1+2\varepsilon_{i}+\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)}{1-2\varepsilon_{i}+\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)}.$

Then, the ratio of the weights of PNB and NB decision rules are as follows:

$\displaystyle 1$
$\displaystyle\geq\frac{\log\frac{4\varepsilon_{i}\varepsilon_{\setminus
i}+1}{1-4\varepsilon_{i}\varepsilon_{\setminus
i}}}{\log\frac{2\varepsilon_{i}+1}{1-2\varepsilon_{i}}}=\frac{\log\frac{1+2\varepsilon_{i}+\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)}{1-2\varepsilon_{i}+\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)}}{\log\frac{1+2\varepsilon_{i}}{1-2\varepsilon_{i}}}$
$\displaystyle\geq 1-\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)\underbrace{\frac{4\varepsilon_{i}}{\left(1-4\varepsilon_{i}^{2}\right)\log\frac{1+2\varepsilon_{i}}{1-2\varepsilon_{i}}}}_{C(\left|\varepsilon_{i}\right|)}$

The inequality follows from the Taylor series expansion of
$\log\frac{1+a+x}{1-a+x}$ with respect to variable $x$ around $x=0$, which
corresponds to $\varepsilon_{\setminus i}\approx\nicefrac{{1}}{{2}}$.
Observing that $\varepsilon_{\setminus i}\geq a(N)-\nicefrac{{1}}{{2}}$,
$\forall N,i$ and $C(\varepsilon_{i})\equiv C(\left|\varepsilon_{i}\right|)$
is monotonic in $\left|\varepsilon_{i}\right|$ yield that:

$\frac{\tilde{\Phi}}{\Phi}=\frac{\sum_{i=1}^{N}\left(\varepsilon_{i}\log\frac{4\varepsilon_{i}\varepsilon_{\setminus
i}+1}{1-4\varepsilon_{i}\varepsilon_{\setminus
i}}\right)}{\sum_{i=1}^{N}\varepsilon_{i}\log\frac{2\varepsilon_{i}+1}{1-2\varepsilon_{i}}}\geq
1-C(\nicefrac{{1}}{{2}}-\gamma)\frac{1-a(n)}{a(n)-\nicefrac{{1}}{{2}}}.$ (30)

∎

###  D-A Proof of Corollary 1

###### Proof of Corollary 1.

Similar to the proof of Theorem 2, consider the ratio in (30) and observe
that:

$C(\nicefrac{{1}}{{2}}-\gamma)\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)\leq\delta,\forall i,$

ensures that $\frac{\tilde{\Phi}}{\Phi}\geq 1-\delta$. Change of variables
$\varepsilon_{\setminus i}=p_{\setminus i}-\nicefrac{{1}}{{2}}$ concludes
proof. ∎

###  D-B Proof of Equation (18)

The following proof is based on [20, Theorem 1]. We go over the algebraic
manipulations necessary in order to prove (18). We first show that:

$\mathbb{P}\left(f^{PNB}(\mathbf{X})\neq
Y\right)\leq\exp\left(-\frac{\tilde{\Phi}}{2}\right)$ (31)

Observe that allowing
$w(\tilde{p}_{i})\triangleq\frac{\tilde{p}_{i}}{1-\tilde{p}_{i}}$ and
$\xi\triangleq\mathds{1}\left(X_{i}=Y\right)\sim\mathcal{B}(p_{i})$:

$\displaystyle\mathbb{P}\left(f^{PNB}(\mathbf{X})\neq Y\right)=$
$\displaystyle\mathbb{P}\left(\sum\xi_{i}w(\tilde{p}_{i})-\mathbb{E}\left[\sum\xi_{i}w(\tilde{p}_{i})\right]\leq-\sum\left(\frac{1}{2}-p_{i}\right)w(\tilde{p}_{i})\right)$

Subsequent application of Kearns-Saul inequality yields (31). The use of
Kearns-Saul inequality yields sufficiently sharp bounds for the performance of
NB (and PNB) decision rules and it is discussed in detail [20]. Next, a lower
bound is needed:

$\mathbb{P}\left(f^{PNB}(\mathbf{X})\neq
Y\right)\geq\frac{\nicefrac{{3}}{{4}}}{1+\exp\left(2\tilde{\Phi}+4\sqrt{\tilde{\Phi}}\right)}.$

Let $\eta_{i}\triangleq 2\mathds{1}\left(X_{i}=Y\right)-1$ and observe that:

$\displaystyle\mathbb{E}\left[\sum\eta_{i}w(\tilde{p}_{i})\right]$
$\displaystyle=\sum(p_{i}-q_{i})w(\tilde{p}_{i})=2\tilde{\Phi}$
$\displaystyle\operatorname{Var}\left(\sum\eta_{i}w(\tilde{p}_{i})\right)$
$\displaystyle=\sum p_{i}q_{i}w(\tilde{p}_{i})^{2}\leq 4\tilde{\Phi}$

The upper bound on the variance is not straightforward. It follows from
$w(\tilde{p}_{i})\leq w(p_{i})$ (which holds $\forall i$ such that
$p_{\setminus i}>\nicefrac{{1}}{{2}}$ and from consistency $\forall N>N^{*}$
for some $N^{*}$ it holds $\forall i$) and [20, Lemma 4]. The rest follows
from observing that:

$\exp(\sum\eta_{i}w(\tilde{p}_{i}))=\prod_{i:\eta_{i}=1}\frac{\tilde{p}_{i}}{1-\tilde{p}_{i}}\prod_{i:\eta_{i}=-1}\frac{1-\tilde{p}_{i}}{\tilde{p}_{i}},$

and repeating the exact same steps as the proof of [20, Theorem 1(ii)], which
we will not repeat here (the fact that
$\min\left\\{\tilde{p}_{i},1-\tilde{p}_{i}\right\\}\geq\min\left\\{p_{i},1-p_{i}\right\\}$
is useful).

##  Appendix E Proof of Proposition 3

###### Proof of Proposition 3.

The proof follows from the Hoeffding’s inequality, since for any weighted
mixture:

$\mathbb{P}\left(\sum_{i=1}^{N}w_{i}\eta_{i}<0\right)\leq\exp\left(-\frac{8}{N}\left(\sum_{i=1}^{N}\varepsilon_{i}w_{i}\right)^{2}\right)$

The definition of the pseudo-competence (10) and
$w_{i}=\left(\tilde{p}_{i}-\nicefrac{{1}}{{2}}\right)$ yield that the
following is sufficient for the consistency of the rule (21):

$\frac{1}{\sqrt{N}}\sum_{i=1}^{N}2\varepsilon_{i}^{2}\varepsilon_{\setminus
i}\rightarrow\infty\Rightarrow\mathbb{P}\left(f^{L}(\mathbf{X})\neq
Y\right)\rightarrow 0.$

Similarly by allowing $w_{i}=1$, $\forall i$, the following is sufficient for
a committee to be not asymptotically weak under majority vote:

$\frac{1}{\sqrt{N}}\sum_{i=1}^{N}\varepsilon_{i}\geq\sqrt{\frac{\log
2}{8}}\Rightarrow\exp\left(-\frac{8}{N}\left(\sum_{i=1}^{N}\varepsilon_{i}\right)^{2}\right)\leq\frac{1}{2},$

which ensures that $\exists N^{*}$ such that $\forall N>N^{*}$,
$\varepsilon_{\setminus i}\geq\delta>0$, $\forall i$, yielding that:

$\sum_{i=1}^{N}2\varepsilon_{i}^{2}\varepsilon_{\setminus
i}\geq\delta\sum_{i=1}^{N}2\varepsilon_{i}^{2}\rightarrow\infty,$

as long as
$\lim_{N\rightarrow\infty}\frac{1}{\sqrt{N}}\sum_{i=1}^{N}(p_{i}-\nicefrac{{1}}{{2}})^{2}=\infty$,
which concludes that empirical PNB decision rule is consistent. ∎

##  Appendix F Proof of Theorem 3

###### Proof of Lemma 1.

Consider $\left|w_{i}-\tilde{w}_{i}\right|$ for an absolutely balanced
committee; the following holds $\forall p_{i}\in\left(\gamma,1-\gamma\right)$:

$\displaystyle\left|\log\frac{1+2\varepsilon_{i}}{1-2\varepsilon_{i}}-\log\frac{4\varepsilon_{i}\varepsilon_{\setminus
i}+1}{1-4\varepsilon_{i}\varepsilon_{\setminus i}}\right|$
$\displaystyle\leq\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)\frac{4\varepsilon_{i}}{\left(1-4\varepsilon_{i}^{2}\right)}\leq\left(\nicefrac{{1}}{{2\varepsilon_{\setminus
i}}}-1\right)\frac{\nicefrac{{1}}{{2}}-\gamma}{\gamma(1-\gamma)}$

As long as the right hand side is upper bounded by $\frac{\epsilon}{2}$,
$\left\|\mathbf{w}-\tilde{\mathbf{w}}\right\|_{1}<\frac{\epsilon N}{2}$. ∎

###### Proof of Theorem 3.

This proof is an extension of [20, Theorem 11]. Consider the following:

$\displaystyle\left|\mathbf{w}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right|$
$\displaystyle=\left|\mathbf{w}\cdot\bm{\eta}-\mathbf{\tilde{w}}\cdot\bm{\eta}+\mathbf{\tilde{w}}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right|$
$\displaystyle\leq\left|\mathbf{w}\cdot\bm{\eta}-\mathbf{\tilde{w}}\cdot\bm{\eta}\right|+\left|\mathbf{\tilde{w}}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right|$
$\displaystyle\leq\left\|\mathbf{w}\cdot\bm{\eta}-\mathbf{\tilde{w}}\cdot\bm{\eta}\right\|_{1}+\left\|\mathbf{\tilde{w}}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right\|_{1}$

The first inequality follows from the triangle inequality and the second
inequality follows from the Hölder’s inequality, then, [20, eqn. (41)] yields
that:

$\displaystyle\mathbb{P}\left(\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\leq
0\right)\leq\mathbb{P}\left(\mathbf{w}\cdot\bm{\eta}\leq\epsilon N\right)$
$\displaystyle+\mathbb{P}\left(\left\|\mathbf{w}\cdot\bm{\eta}-\mathbf{\tilde{w}}\cdot\bm{\eta}\right\|_{1}+\left\|\mathbf{\tilde{w}}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right\|_{1}>\epsilon
N\right)$

As long as a committee satisfies the condition in Lemma 1, this upper-bound
boils down to:

$\displaystyle\mathbb{P}\left(\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\leq
0\right)$
$\displaystyle\leq\mathbb{P}\left(\mathbf{w}\cdot\bm{\eta}\leq\epsilon
N\right)$
$\displaystyle+\mathbb{P}\left(\left\|\mathbf{\tilde{w}}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right\|_{1}>\nicefrac{{\epsilon
N}}{{2}}\right)$

Now, [20, Corollary 10] yields that $\forall\delta\in(0,1)$ and $\forall
i\in[N]$ as long as

$T\min\left\\{\tilde{p}_{i},(1-\tilde{p}_{i})\right\\}\geq
3\left(\frac{4}{\sqrt{4\epsilon+1}-1}\right)^{2}\log\frac{8N}{\delta},$ (32)

The probability that empirical pseudo weights deviate from pseudo weights are
bounded:

$\mathbb{P}\left(\left\|\mathbf{\tilde{w}}\cdot\bm{\eta}-\mathbf{\tilde{w}}(T)\cdot\bm{\eta}\right\|_{1}>\frac{\epsilon
N}{2}\right)<\delta$

Finally, by Property 2, $\min\left\\{p_{i},(1-p_{i})\right\\}$ satisfying (32)
yields that:

$\mathbb{P}\left(f^{H}(\mathbf{X})\neq
Y\right)\leq\delta+\exp\left[-\frac{\left(2\Phi-\epsilon
N\right)^{2}}{8\Phi}\right].$

Observe that Lemma 1 and eqn. (32) are connected to consistency and absolute
balance conditions respectively. Therefore, consider a consistent committee
with rate $a(N)$ and observe that Lemma 1 holds as long as:

$\frac{\epsilon R(\gamma)}{2}>\rho(N).$ (33)

Observing that (32) is merely absolute balance condition with
$\gamma=\frac{3}{T}\log\frac{8N}{\delta}\left(\frac{4}{\sqrt{4\epsilon+1}-1}\right)^{2}$,
plugging into (33), and taking Taylor series expansion yields (a long
algebraic manipulation that we skip here) yields that Lemma 1 holds as long
as:

$\epsilon>\left(\rho(N)\frac{12}{T}\log\frac{8N}{\delta}\right)^{\nicefrac{{1}}{{3}}}.$

Defining $C(\delta;N,T)=\frac{12}{T}\log\frac{8N}{\delta}$ concludes the
proof. ∎

##  Appendix G Proof of Theorem 4

###### Proof of Theorem 4.

Due inter-worker and inter-task independence, the empirical pseudo naïve Bayes
decision rule at any given time, $\tau\in[T]$ evolves in a well-defined
filtration. Hence, $f^{H}_{\tau}$, the empirical decision rule using weights
$\tilde{w}(\tau)$, obeys $\forall t\in(\tau+1,...,T)$:

$\displaystyle\mathbb{P}\left(R(\tau)\cap\left\\{f^{H}(\mathbf{X}(t>\tau)\neq
Y)\right\\}\right)$ $\displaystyle\hskip
56.9055pt=\mathbb{P}_{\mathbf{X}_{1}^{\tau},\bm{\eta}}\left(R(\tau)\cap\left\\{\tilde{\mathbf{w}}(\tau)\cdot\bm{\eta}\leq
0\right\\}\right)$ $\displaystyle\hskip
56.9055pt=\mathbb{E}_{\mathbf{X}_{1}^{\tau}}\left[\mathds{1}\left(R(\tau)\right)\mathbb{P}_{\bm{\eta}}\left(\tilde{\mathbf{w}}(\tau)\cdot\bm{\eta}\leq
0\right)\right]$

It is important to observe that as long as the tasks are static, these
probabilities are a function of $\tau$ and the committee profile $\mathbf{p}$.
Let $\tilde{\bm{\eta}}_{\tau}$ be a random vector with elements distributed
independently with Bernoulli $\tilde{p}_{i}(\tau)$ and denote
$\Delta(\tau)\triangleq\sum_{i=1}^{N}\left|p_{i}-\tilde{p}_{i}(\tau)\right|$
In other words, it is a random vector with a pseudo committee profile. A
standard tensorization result from [35, 20] yields:

$\left|\mathbb{P}_{\bm{\eta}}\left(\tilde{\mathbf{w}}(\tau)\cdot\bm{\eta}\leq
0\right)-\mathbb{P}_{\tilde{\bm{\eta}}_{\tau}}\left(\tilde{\mathbf{w}}(\tau)\cdot\tilde{\bm{\eta}}_{\tau}\leq
0\right)\right|\leq\Delta(\tau)$

Then $\forall\tau\in[T]$,
$\mathbb{P}_{\tilde{\bm{\eta}}_{\tau}}\left(\tilde{\mathbf{w}}(\tau)\cdot\tilde{\bm{\eta}}_{\tau}\leq
0\right)$ is the probability of error for the naïve Bayes decision rule of
committee strength
$\tilde{\Phi}(\tau)\triangleq\sum_{i=1}^{N}\left(\tilde{p}_{i}(\tau)-\frac{1}{2}\right)\log\frac{\tilde{p}_{i}(\tau)}{1-\tilde{p}_{i}(\tau)}$.
Therefore, from [20]:

$\mathbb{P}_{\tilde{\bm{\eta}}_{\tau}}\left(\tilde{\mathbf{w}}(\tau)\cdot\tilde{\bm{\eta}}_{\tau}\leq
0\right)\leq\exp\left(-\frac{1}{2}\tilde{\Phi}\left(\tau\right)\right)$

Hence,
$\mathbb{P}_{\bm{\eta}}\left(\tilde{\mathbf{w}}^{HS}(\tau)\cdot\bm{\eta}\leq
0\right)\leq\Delta(\tau)+\exp\left(-\frac{1}{2}\tilde{\Phi}\left(\tau\right)\right)$.
Then, by the triangle inequality with a mean absolute deviation estimate from
[31, 20], we see that:

$\mathbb{E}_{\mathbf{X}_{1}^{\tau}}\left[\Delta(\tau)\right]\leq\sum_{i=1}^{N}\left|p_{i}-\tilde{p}_{i}\right|+\frac{N}{\sqrt{T}}$

This concludes the proof. ∎

## References

  * [1] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in _2012 IEEE Conference on Computer Vision and Pattern Recognition_. IEEE, 2012, pp. 3354–3361.
  * [2] M. A. Hamburg and F. S. Collins, “The path to personalized medicine,” _New England Journal of Medicine_ , vol. 363, no. 4, pp. 301–304, 2010.
  * [3] M. Bahrepour, N. Meratnia, M. Poel, Z. Taghikhaki, and P. J. Havinga, “Distributed event detection in wireless sensor networks for disaster management,” in _2010 international conference on intelligent networking and collaborative systems_. IEEE, 2010, pp. 507–512.
  * [4] J. Zhang, R. S. Blum, and H. V. Poor, “Approaches to secure inference in the internet of things: Performance bounds, algorithms, and effective attacks on iot sensor networks,” _IEEE Signal Processing Magazine_ , vol. 35, no. 5, pp. 50–63, 2018.
  * [5] I. Ochoa-Alvarez, “Genomic data compression and processing: theory, models, algorithms, and experiments,” Ph.D. dissertation, Stanford University, 2016.
  * [6] R. Snow, B. O’Connor, D. Jurafsky, and A. Y. Ng, “Cheap and fast—but is it good?: evaluating non-expert annotations for natural language tasks,” in _Proceedings of the conference on empirical methods in natural language processing_. Association for Computational Linguistics, 2008, pp. 254–263.
  * [7] H. V. Poor, _An introduction to signal detection and estimation_. Springer Science & Business Media, 2013.
  * [8] A. P. Dempster, “A generalization of bayesian inference,” _Journal of the Royal Statistical Society: Series B (Methodological)_ , vol. 30, no. 2, pp. 205–232, 1968.
  * [9] G. Shafer, _A mathematical theory of evidence_. Princeton university press, 1976, vol. 42.
  * [10] L. A. Zadeh, “Fuzzy logic,” _Computer_ , vol. 21, no. 4, pp. 83–93, 1988\.
  * [11] C.-C. Lee, “Fuzzy logic in control systems: fuzzy logic controller. i,” _IEEE Transactions on systems, man, and cybernetics_ , vol. 20, no. 2, pp. 404–418, 1990.
  * [12] N. Cesa-Bianchi and G. Lugosi, _Prediction, learning, and games_. Cambridge university press, 2006.
  * [13] R. E. Schapire and Y. Freund, _Boosting: Foundations and algorithms_. MIT press, 2012.
  * [14] J. Ok, S. Oh, J. Shin, and Y. Yi, “Optimality of belief propagation for crowdsourced classification,” in _International Conference on Machine Learning_ , 2016, pp. 535–544.
  * [15] P. Welinder and P. Perona, “Online crowdsourcing: rating annotators and obtaining cost-effective labels,” in _2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition-Workshops_. IEEE, 2010, pp. 25–32.
  * [16] Y. Zhang, X. Chen, D. Zhou, and M. I. Jordan, “Spectral methods meet em: A provably optimal algorithm for crowdsourcing,” in _Advances in neural information processing systems_ , 2014, pp. 1260–1268.
  * [17] A. P. Dawid and A. M. Skene, “Maximum likelihood estimation of observer error-rates using the em algorithm,” _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , vol. 28, no. 1, pp. 20–28, 1979.
  * [18] E. Baharad, J. Goldberger, M. Koppel, and S. Nitzan, “Distilling the wisdom of crowds: weighted aggregation of decisions on multiple issues,” _Autonomous Agents and Multi-Agent Systems_ , vol. 22, no. 1, pp. 31–42, 2011\.
  * [19] R. Dorfman, “The detection of defective members of large populations,” _Ann. Math. Statist._ , vol. 14, no. 4, pp. 436–440, 12 1943. [Online]. Available: https://doi.org/10.1214/aoms/1177731363
  * [20] D. Berend and A. Kontorovich, “A finite sample analysis of the naive bayes classifier.” _Journal of Machine Learning Research_ , vol. 16, pp. 1519–1545, 2015.
  * [21] S. Bubeck, N. Cesa-Bianchi et al., “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” _Foundations and Trends® in Machine Learning_ , vol. 5, no. 1, pp. 1–122, 2012\.
  * [22] J. Neyman and E. S. Pearson, “Ix. on the problem of the most efficient tests of statistical hypotheses,” _Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character_ , vol. 231, no. 694-706, pp. 289–337, 1933.
  * [23] K. P. Murphy, _Machine learning: a probabilistic perspective_. MIT press, 2012.
  * [24] F. Parisi, F. Strino, B. Nadler, and Y. Kluger, “Ranking and combining multiple predictors without labeled data,” _Proceedings of the National Academy of Sciences_ , vol. 111, no. 4, pp. 1253–1258, 2014.
  * [25] M. J. A. marquis de Condorcet, _Essai sur l’application de l’analyse a la probabilite des decisions: rendues a la pluralite de voix_. De l’Imprimerie royale, 1785.
  * [26] J. Paroush, “Stay away from fair coins: A condorcet jury theorem,” _Social Choice and Welfare_ , vol. 15, no. 1, pp. 15–20, 1997.
  * [27] D. Berend and J. Paroush, “When is condorcet’s jury theorem valid?” _Social Choice and Welfare_ , vol. 15, no. 4, pp. 481–488, 1998.
  * [28] R. Ben-Yashar and J. Paroush, “A nonasymptotic condorcet jury theorem,” _Social Choice and Welfare_ , vol. 17, no. 2, pp. 189–199, 2000.
  * [29] B. Hajek, _Random processes for engineers_. Cambridge university press, 2015.
  * [30] N. C. Sevüktekin, A. G. Schwing, and A. C. Singer, “Distributed estimation via opinion dynamics,” in _2019 IEEE 62nd International Midwest Symposium on Circuits and Systems (MWSCAS)_. IEEE, 2019, pp. 476–480.
  * [31] D. Berend and A. Kontorovich, “A sharp estimate of the binomial mean absolute deviation with applications,” _Statistics & Probability Letters_, vol. 83, no. 4, pp. 1254–1259, 2013.
  * [32] M. Kearns and L. Saul, “Large deviation methods for approximate probabilistic inference,” in _Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence_ , 1998, pp. 311–319.
  * [33] M. Raginsky, I. Sason et al., “Concentration of measure inequalities in information theory, communications, and coding,” _Foundations and Trends® in Communications and Information Theory_ , vol. 10, no. 1-2, pp. 1–246, 2013.
  * [34] S. S. Haykin, _Adaptive filter theory_. Prentice Hall, 2005.
  * [35] A. Kontorovich, “Obtaining measure concentration from markov contraction,” _Markov Processes and Related Fields_ , vol. 18, pp. 613–638, 2012.