EM-algorithm for two clusters (when one of the distributions is uniform)

Question

I am having a hard time with the EM-algorithm. Here's the problem that I am trying to solve.

Dealing with noisy annotations is a common problem in computer vision, especially when using crowdsourcing tools, like Amazon’s Mechanical Turk. For this problem, you’ve collected photo aesthetic ratings for 150 images. Each image is labeled 5 times by a total of 25 annotators (each annotator provided 30 labels). Each label consists of a continuous score from 0 (unattractive) to 10 (attractive). The problem is that some users do not understand instructions or are trying to get paid without attending to the image. These “bad” annotators assign a label uniformly at random from 0 to 10. Other “good” annotators assign a label to the i-th image with mean µi and standard deviation σ (σ is the same for all images). Your goal is to solve for the most likely image scores and to figure out which annotators are trying to cheat you.

Derive the EM algorithm to solve for each $\mu_i$ , each $\mu_j$ , $\sigma$, and $\beta$. Show the major steps of the derivation and make it clear how to compute each variable in the update step.

https://courses.engr.illinois.edu/cs543/sp2012/hw/hw4_assignment.pdf (here's a link to the complete task, see p.2)

I know that mixtures of Gaussians are often used where you first initialize $k$ Gaussian distributions the parameters of which it is necessary to optimize.

With regard to this problem, I cannot understand how to work with the two distributions. Apparently, we have some prior knowledge that the behavior of bad annotators follows the uniform distribution. On the other hand, it seems that all books and articles I have seen so far consider mixtures of Gaussians.

I would appreciate any kind of guidance and advice with this problem.

Answer 1

Since this is a homework problem, I will provide hints and relevant resources to get you started.

For your problem you have the following variables,

$$ x_{ij} \in [0, 10] \: [ \text{available data, annotation for image (i) by annotator (j)} ] \\ m_j \in \{0, 1\} \: [\text{indicates good or bad annotator}] \\ p(x_{ij} \mid m_j=0) = \frac{1}{10} \: [\text{distribution for bad annotator data}] \\ p(x_{ij} \mid m_j=1) \sim \mathcal{N}(\mu_i, \sigma) \: [\text{distribution for good annotator data}] \\ \beta: [\text{prior probability for good annotator}] $$

Based on this information you can formulate the log-likelihood for your problem as follows,

$$ \text{ln}\:p(\textbf{X} \mid \mu , \sigma , \beta ) = \sum_{i=1}^{N}\:\text{ln}\:[\:p(x_{ij}\mid m_j=0) \times p(m_j=0) + p(x_{ij}\mid m_j=1) \times p(m_j=1)\:] \\ = \sum_{i=1}^{N}\:\text{ln}\: [ \frac{1}{10}\times(1-\beta)\: + \: \mathcal{N}(\mu_i, \sigma) \times \beta \:] $$

The EM algorithm is a maximum likelihood solution, which means you need to find expressions for $\mu_i, \sigma, \beta$ by taking the derivative of above equation and setting it to zero.

Pattern recognition and Machine learning [ pages 435 - 439 ] by Bishop gives very detailed steps on how to derive the relevant equations for the EM algorithm. Once you derive the equations you can use the chart on pages. 438-439 of the book to estimate the parameters.

Hope this helps!

Answer 2

You likely don't want to cluster, but rather test for uniformity.

There are many tests for that, such as KS tests.

But I doubt that "cheaters" will exhibit anything like uniform behavior. Humans are notoriously bad at this.