2
$\begingroup$

Suppose we have $m$ sources, each of which noisily observe the same set of $n$ independent events from the outcome set $\{A,B,C\}$. Each source has a confusion matrix, for example for source $i$:

$$C_i = \begin{bmatrix} 0.98 & 0.01 & 0.07 \\ 0.01 & 0.97 & 0.00 \\0.01 & 0.02 & 0.93\end{bmatrix} $$

where each column relates to the truth, and each row relates to the observation. Eg. if the true event is $B$ then source $i$ will get it right 97% of the time, and observe $A$ 1% of the time and $C$ 2% of the time. We can assume the diagonals are >95%

Given a sequence of $n$ events, where each event $j$ was observed by source $i$ as $O_{i,j}$, it is trivial to estimate the pmf of the truth $T_j$ by solving $P(T_j | O_{1,j},\dots,O_{m,j})$ using Bayesian formula (given some reasonable priors about the probabilities of the events themselves, say, uniform).

However suppose we didn't have the confusion matrices, nor the ground truth, and instead wanted to estimate them both. One algorithm is:

  • Start with some reasonable confusion matrix for each source $C_{i,0}$
  • Fixing the confusion matrices $C_{i,k}$, estimate the most likely truths $T_{j,k}$ using Bayes formula
  • Fixing truths $T_{j,k}$, estimate new confusion matrices $C_{i,k+1}$ based on how often each source got it "wrong" (allegedly)
  • Repeat the last two steps incrementing $k$ until convergence

This seems like the EM algorithm but I don't know how to show this formally. (No this is not homework.)

1) Is this EM, or some other standard algorithm in data fusion?

2) Does it have convergence guarantees?

3) Does it have any guarantees about the quality of the solution and how well the final confusion matrices will approximate the true confusion matrices?

4) Are there issues about the number of parameters being estimated vs. the number of samples? Eg. it seems there are $n + 6m$ parameters being estimated - the $n$ truths and the $6m$ elements across all confusion matrices (last cell of each column is determined by the others).

EDIT

These two papers describes exactly the problem and how to use EM to solve it:

Maximum Likelihood Estimation of Observer Error-Rates Using the EM Algorithm http://crowdsourcing-class.org/readings/downloads/ml/EM.pdf

LEARNING FROM NOISY SINGLY-LABELED DATA https://openreview.net/pdf?id=H1sUHgb0Z

So the answers are:

1) Properly interpreted yes this is EM

2) EM in general converges to local optimum

3) Not really. In this problem though since the sources are 97%+ accurate, I expect the estimates to be pretty good

4) I don't think this is an issue - this is a "non-parametric" EM algorithm as the confusion matrices are not parameterized in anyway way. The sample sizes I deal with are in the 100000's+ so shouldn't be an issue

$\endgroup$
2
  • $\begingroup$ I'm not sure but I think it's impossible to do this without making some assumptions. For example, if every confusion matrix interchanged the labels $B$ and $A$, you would never know that the 'truths' are actually flipped for $A$ and $B$. Given the fact that there is no prior on the confusion matrices, it's not possible to assign probabilities to the case that I described above. My suggestion is that you make assumptions (perhaps like, the diagonal values will always be the highest 3 values in the matrix), etc. which would help narrow down the logic. $\endgroup$
    – adityar
    Nov 5, 2018 at 12:23
  • $\begingroup$ Yes I agree. In this domain we know the diagonals are >95% so we have a strong starting point. $\endgroup$ Nov 6, 2018 at 22:55

1 Answer 1

1
$\begingroup$

This doesn't fully answer your question, but I hope this helps create an argument for/against your question.

I'm not too familiar with the EM algorithm and so the (3rd) step in your proposed algorithm seems a bit hazy to me - I don't understand how the proposal is happening. The way I understand the EM, we propose a set of points, then choose the next set of points based on an expected log-posterior given the current state, which isn't really what's happening here (I don't see how the posterior comes into your proposal in step 3).

I may be missing something but, if you fix the $T_j$ and you know the $O_{ij}$, I don't see how anything would change after the first iteration.


Deriving the Log-Posterior:

Given the fact that the events and the confusion matrices are independent, it appears reasonable to make the assumption here that the noisy readings $O_{ij}$ are all independent for every $i, j$. Let $M_{ab}$, $a, b \in \{A,B,C\}$ be the confusion matrix.

Furthermore, given that the confusion matrix is essentially a matrix of probabilities with $P(O_{ij}|T_j)$ along one axis and $P(T_j|O_{ij})$ along the other, we could probably use a Dirichlet prior on them.

The posterior is:

$$P(T_j,M|O_{ij}) = P(T_j|M,O_{ij})P(M|O_{ij})$$

The first term in the posterior is:

$$P(T_j|O_{1j}, ..., O_{mj}, M) = \frac{P(T_j,O_{1j}, ..., O_{mj}|M)}{\prod_i^m P(O_{ij}|M)}$$

$$ = \frac{ P(T_j|M) \prod_i^m P(O_{ij}|T_j, M)}{\sum_l P(T_j = l| M) \prod_i^m P(O_{ij}|T_j = l, M)}$$

Given the uniform prior on the events, this is equal to:

$$ = \frac{ \prod_i^m P(O_{ij}|T_j, M)}{\sum_l \prod_i^m P(O_{ij}|T_j = l, M)}$$

$$ = \frac{ \prod_i^m M_{T_jO_{ij}}}{\sum_l \prod_i^m M_{lO_{ij}}}$$

The second term in the posterior however - $P(M|O_{ij})$, makes a difference, and honestly, I'm not sure how to write it down. If I hazard a guess, I'd say that $P(M|O_{ij}) = P(M)$ by independence. $P(M)$ is hard to write down but one attempt would be:

To go from a confusion matrix to a joint probability table, we can multiply every element in the confusion matrix by $1/3$ which is the probability $P(T_j)$ and also $P(O_{ij})$. Then, the sum of all elements will have to be 1, on which we could place a dirichlet prior:

$$P(M) = P_{dirichlet\;of\;dimension\;9\;with\;sensible\;priors}(M_{ab})$$

Which, if I've not made glaring mistakes, should be enough to construct a posterior, and optimizing it should result in the MAP.

If you need to construct the EM, step (3) I think should be replaced with the expectation of the log-posterior described here.


Notes:

  1. $T_j$ and elements of $M$ are variables, $O_{ij}$ is data.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.