Recovering Labels from Crowdsourced Data

An Optimal and Polynomial Time Method

Introduction

Thank you for having me here today.

For context, much of this work was conducted during my postdoctoral position at ENS Lyon, where was able to build upon my earlier PhD research in crowdsourcing.

So, let’s start with a scenario. Picture a group of workers, and each one is given binary classification tasks.

For each task, they need to make yes-or-no decisions.

There are many situations where this happens. Think of image classification, text moderation, or sentiment analysis

Workers are given binary tasks to which they have to give a response: YES or NO

Examples

• Image Classification: “Does this image contain a dog?”
• Text Moderation: “Is this comment toxic or offensive?”
• Sentiment Analysis: “Does this review express positive sentiment?”

Questions

Three natural questions emerge

• what are the actual true labels?
• Can we compare workers and identify who performs better or worse?
• How well do workers perform on a given task?

I will touch on all these issues during my talk, but my primary focus will be on the central question of recovering the true labels.

3 questions

• recover the true label?
• rank the workers?
• estimate their abilities?

Main Quetion: How can we accurately recover the labels?

This Talk

I will break down my presentation in 3 parts.

I’ll start by introducing isotonic model.

Next, I’ll review two existing methods.

In the final part, I’ll go over an optimal and computationnally feasible method for this problem.

1. Introducing the non-parametric isotonic model and main result
2. Presenting two already existing algorithms
3. Iterative Spectral Voting (ISV) algo and key insights

The Isotonic Model

Illustration

Let me start with an illustration.

Consider binary tasks where labels are either \(-1\) or \(+1\). There is a vector \(x^*\) of true labels that we do not know.

We observe a matrix \(Y\) where each entry \((i,k)\) represents the response of worker \(i\) to task \(k\).

We can have missing values. When a worker doesn’t respond to a particular task, we simply put \(0\) in that matrix position.

We write \(\lambda\) for the rate of partial observations .

• Two binary tasks with labels in \(\{\color{green}{-1},\color{blue}{+1}\}\)
• Unknown vector \(x^*\) of labels with \(d=9\) tasks \(x^*= (\color{blue}{+1},\color{blue}{+1},\color{green}{-1},\color{blue}{+1},\color{green}{-1},\color{blue}{+1},\color{blue}{+1},\color{blue}{+1},\color{blue}{+1})\)

\[ Y=\left(\begin{array}{ccccccccc} \color{green}{-1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} & \color{green}{-1} & \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} \\ \color{blue}{+1} & \color{blue}{+1} & \color{blue}{+1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} \\ \color{blue}{+1} & \color{green}{-1} & \color{green}{-1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} \\ \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} & \color{blue}{+1} & \color{blue}{+1} \end{array}\right) \]

\[ Y=\left(\begin{array}{ccccccccc} \color{red}{0} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{red}{0} & \color{green}{-1} & \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} \\ \color{red}{0} & \color{blue}{+1} & \color{red}{0} & \color{blue}{+1} & \color{green}{-1} & \color{red}{0} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} \\ \color{blue}{+1} & \color{green}{-1} & \color{green}{-1} & \color{blue}{+1} & \color{green}{-1} & \color{blue}{+1} & \color{red}{0} & \color{blue}{+1} & \color{blue}{+1} \\ \color{green}{-1} & \color{blue}{+1} & \color{blue}{+1} & \color{red}{0} & \color{green}{-1} & \color{blue}{+1} & \color{red}{0} & \color{red}{0} & \color{red}{0} \end{array}\right) \]

• Rate of observations: \(\color{red}{\lambda= 0.72}\)

Observation Model

We assume that the matrix of responses follows this model.

• \(x^*\) is the vector of unknown labels
• \(E\) is a matrix of independent sub-gaussian noise
• \(M \in [0,1]^{n \times d}\) is the unknown ability matrix. If \(M_{ik}=1\), it means that worker \(i\) is very good at question \(k\), and \(M_{ik}=0\) means that they answer randomly.
• This odot is a Hadamard Product so you can think of \(B\) as a Bernoulli mask matrix.

We observe

\[Y = B\odot(M\mathrm{diag}(x^*) + E) \in \mathbb R^{n \times d}\]

where \(\odot\) is the Hadamard product.

• \(x^*\in \{-1, 1\}^d\) is the vector of unknown labels
• \(E\) is a matrix of independent sub-gaussian noise
• \(M \in [0,1]^{n \times d}\) is the unknown ability matrix.
• \(B\) is a Bernoulli \(\mathcal B(\lambda)\) “mask” matrix, modelling partial observations

Shape Constraints

Until now, I have’nt assumed anything on the ability matrix \(M\) except that it has coef. in \([0,1]\).

From now on, we also assume that \(M\) is isotonic up to a permutation \(\pi^*\) of its rows, that is,

it has increasing columns, up to an unknown permutation \(\pi^*\)

It means that, on average, a worker \(i\) is either uniformly better or uniformly worse than another worker \(j\)

• \(M \in [0,1]^{n \times d}\) represents the ability matrix of worker/task pairs
• We assume that \(M\) is isotonic up to a permutation \(\pi^*\) , that is

\[ M_{\pi^*}=\left(\begin{array}{ccccccccc} \color{#000099}{0.9} & \color{#000099}{0.8} & \color{#000099}{0.9} & \color{#000099}{1\phantom{.0}} \\ \color{#4B0082}{0.8} & \color{#4B0082}{0.7} & \color{#4B0082}{0.9} & \color{#4B0082}{0.8} \\ \color{#990066}{0.6} & \color{#990066}{0.7} & \color{#990066}{0.7} & \color{#990066}{0.6} \\ \color{#CC0000}{0.5} & \color{#CC0000}{0.7} & \color{#CC0000}{0.5} & \color{#CC0000}{0.6} \end{array}\right) \]

\[ M_{\phantom{{\pi^*}}}=\left(\begin{array}{ccccccccc} \color{#990066}{0.6} & \color{#990066}{0.7} & \color{#990066}{0.7} & \color{#990066}{0.6} \\ \color{#CC0000}{0.5} & \color{#CC0000}{0.7} & \color{#CC0000}{0.5} & \color{#CC0000}{0.6} \\ \color{#000099}{0.9} & \color{#000099}{0.8} & \color{#000099}{0.9} & \color{#000099}{1\phantom{.0}} \\ \color{#4B0082}{0.8} & \color{#4B0082}{0.7} & \color{#4B0082}{0.9} & \color{#4B0082}{0.8} \end{array}\right) \]

Square Norm Loss VS Hamming Loss

A usual loss for an estimator \(\hat x\) is the Hamming loss. It simply consists in summing up all the mistakes we’ve made.

I do not consider Hamming Loss Here. Instead, we restrict \(M\) to incorrectly labeled task, and take the square frobenius norm.

• If workers are bad (\(M\) close to \(0\)), square norm loss is small but Hamming Loss can be of order \(d\)
• Hence, a very good feature of the square norm loss is that it evaluates the quality of the estimator \(\hat x\) instead of the performance of the workers!

Hamming Loss: \[ \sum_{k=1}^d \mathbf 1\{\hat x_k \neq x_k^*\}\]

Square Norm Loss: \[ \|M \mathrm{diag}(x^* \neq \hat x)\|_F^2\]

• If workers are bad (\(M \sim 0\)), \(M\) is small but Hamming Loss is large (\(\sim d\))
• Square norm loss evaluates the quality of \(\hat x\) rather than performances of workers

Crowdsourcing Problems

In addition to recovering labels, we can define the two other problems I mentioned earlier:

ranking the workers and estimating their abilities. Each objective corresponds to a similar square norm loss.

Setting

\[ Y = B\odot(M \mathrm{diag}(x^*) + E)\] Shape constraint: \(\exists \pi^*\) s.t. \(M_{\pi^*} \in [0,1]^{n \times d}\) is isotonic

Objectives

Recovering the labels (\(x^*\))

Ranking the workers (\(\pi^*\))

Estimating their abilities (\(M\))

Losses

\(\phantom{\color{purple}{\mathbb E}}\|M \mathrm{diag}(x^* \neq \hat x)\|_F^2\)

\(\phantom{\color{purple}{\mathbb E}}\|M_{\pi^*} - M_{\hat \pi}\|_F^2\)

\(\phantom{\color{purple}{\mathbb E}}\|M - \hat M\|_F^2\)

Crowdsourcing Problems

Setting

\[ Y = B\odot(M \mathrm{diag}(x^*) + E)\] Shape constraint: \(\exists \pi^*\) s.t. \(M_{\pi^*} \in [0,1]^{n \times d}\) is isotonic

Objectives

Recovering the labels (\(x^*\))

Ranking the workers (\(\pi^*\))

Estimating their abilities (\(M\))

Risks

\(\color{purple}{\mathbb E}[\|M \mathrm{diag}(x^* \neq \hat x)\|_F^2]\)

\(\color{purple}{\mathbb E}[\|M_{\pi^*} - M_{\hat \pi}\|_F^2]\)

\(\color{purple}{\mathbb E}[\|M - \hat M\|_F^2]\)

MiniMax Risk for Recovering Labels

This brings us to the minimax risk for recovering labels.

It is defined as the risk of the best estimator \(\hat x\) in the worst case.

\[\mathcal R^*_{\mathrm{reco}}(n,d,\lambda)=\min_{\hat x}\max_{M,\pi^*, x^*}{\mathbb E}[\|M \mathrm{diag}(x^* \neq \hat x)\|_F^2]\]

• minimize on all estimator \(\hat x\)
• maximize square norm loss on all \(M\), \(\pi^*\), \(x^*\) such that \(M_{\pi^*}\) is isotonic

Main Results

The main result I want to present, is that there is no computational-statistical gap here.

There is a polynomial-time methods which nearly achieves the minimax risk for recovering the labels.

Moreover, the minimax risk is of order \(d/\lambda\)

Theorem

If \(\tfrac{1}{\lambda} \leq n \leq d\), there exists a poly. time method \(\hat x\) achieving \(\mathcal R^*_{\mathrm{reco}}\) up to polylog factors, i.e. for all \(M\in[0,1]^{n\times d}\), \(\pi^*\) and \(x^* \in \{-1,1\}^d\), \[ \max_{M,\pi^*, x^*}{\mathbb E}[\|M \mathrm{diag}(x^* \neq \hat x)\|_F^2] \lesssim \mathcal R^*_{\mathrm{reco}}(n,d,\lambda) \enspace . \]

Moreover, up to polylogs,

\[ \mathcal R^*_{\mathrm{reco}}(n,d,\lambda) \asymp \frac{d}{\lambda} \enspace . \]

Already Existing Methods

Let me now shortly present two existing methods

Majority Voting

Majority voting is the simplest method you can think of. Sum each column of \(Y\) and take the sign to estimate each label.

Unfortunately, it does not achieve the optimal \(d/\lambda\) rate. So we have this additional \(\sqrt{n}\) compared to the minimax risk.

\(\hat x^{(maj)}_k = \mathrm{sign} \left( \sum_{i=1}^n Y_{ik} \right)\)

Maximum risk of \(\hat x^{(maj)}\):

\[\max_{M,\pi^*, x^*}\mathbb E\|M\mathrm{diag}(\hat x^{maj} \neq x^*)\|_F^2 \asymp \tfrac{d \sqrt{n}}{\lambda}\]

OBI-WAN (Shah et al., 2020)

In the Obi-Wan Method from Shah and co. The main idea is to use that \((M\mathrm{diag}(x^*))(M\mathrm{diag}(x^*))^T\) does not depend on \(x^*\).

and to exploit this fact by computing the leading left eigen vector of \(Y\)

Idea: Population term \((M\mathrm{diag}(x^*))(M\mathrm{diag}(x^*))^T= MM^T\) is independent of \(x^*\)

PCA Step:

\[\hat v = \underset{\|v\|=1}{\mathrm{argmax}}\|v^T Y\|^2\]

Result on Obi-Wan Method

It turns out that the Obi-Wan method is minimax optimal in a rank \(1\) model, it achieves the rate \(d/\lambda\).

However, it is not minimax optimal in the isotonic model. It only achieves a rate that is comparable to majority voting in the worst case.

Theorem 1 (Shah et al., 2020)

In submodel where \(\mathrm{rk}(M)= 1\), \(\hat x^{(\mathrm{Obi-Wan})}\) achieves minimax risk up to polylogs: \[\mathbb E\|M\mathrm{diag}(\hat x^{\text{Obi-Wan}} \neq x^*)\|_F^2 \lesssim \frac{d}{\lambda} \quad \textbf{(minimax)}\]

Theorem 2 (Shah et al., 2020)

In the model where \(M_{\pi^*\eta^*}\) is bi-isotonic up to polylogs: \[\mathbb E\|M\mathrm{diag}(\hat x^{\text{Obi-Wan}} \neq x^*)\|_F^2 \lesssim \frac{d\sqrt{n}}{\lambda} \quad \textbf{(not minimax)}\]

Iterative Spectral Voting

To achieve the \(d/\lambda\) rate in the isotonic model, let me now introduce iterative spectral voting

The core of the approach consists in iterating two steps: PCA and weighted voting.

PCA Step

First, we compute the leading eigenvector as Shah et al. did.

The insight is that since \(M\) is isotonic, then we can prove that \(M\) is close to low rank, so it makes sense to look for leading eigen vectors

\[\hat v = \underset{\|v\|=1}{\mathrm{argmax}}\|v^T Y\|^2\]

Main idea: Since \(M\) is isotonic, \(M\) is close to low rank

\[\|MM^T\|_{\mathrm{op}} \gtrsim \|M\|_F^2\]

Voting Step

Without going into too much details, the idea is then to do define weights and perform weighted votes.

Define the weighted vote vector (on second sample)

\[\hat w = \hat v^T Y\]

Define the estimated label as

\[\hat x_k^{(1)} = \mathrm{sign}(\hat w_k)\mathbf{1}\bigg\{|\hat w_k| \gg \sqrt{\sum_{i=1}^n \hat v_i B_{ik}}\bigg\}\]

Iterate these two Steps

We then iterate these PCA and voting steps on labels that are left uncertain,

until we get a final estimator.

Keep certain labels: if \(\hat x^{(t)}_k\neq 0\), set \(\hat x^{(t+1)}_k= \hat x^{(t)}_k\).

Restrict columns \(k\) of \(Y\) to uncertain labels \(\hat x^{(t)}_k=0\)

Repeat PCA Step + Voting Step on \(Y \mathrm{diag}(\hat x^{(t)} \neq 0)\) a polylogarithmic number of times.

Output last estimator \(\hat x^{(T)}\)

\(\newcommand{\and}{\quad \mathrm{and} \quad}\)

Ranking and Estimating Abilities

This approach allows us to recover some of the true labels.

Then, we can do ranking and ability estimation!

To do that, we first restrict matrix of responses \(Y\) to the labels for which we have a good guess

Then, we use previous work in the litterature to estimate \(\pi^*\) and \(M\)

1. Use ISV to recover some labels \(\hat x\)
2. Restrict to columns \(k\) such that \(\hat x_k \in \{-1, 1\}\)
3. Use methods from Pilliat et al. (2024) to estimate \(\pi^*\) and \(M\)

Conclusion

Let me wrap up my talk in three key points.

• First, there are three interconnected problems in crowdsourcing: recovering labels, ranking workers and estimating their abilities.
• Second, we use the isotonic model because it’s very flexible for tackling these problems.
• Most importantly, there is no computational statistical gap.

1. Three connected problems: recovering labels, ranking workers and estimating their abilities
2. Non parametric isotonic model very flexible in crowdsourcing problems
3. No computational-statistical gap recovering labels, ranking or estimating ability