2
$\begingroup$

To help me understand some concepts I'm learning in my first exposition to machine learning, I'm trying to tackle the following "simple" problem

The setup of the problem is as follows:

  • My friend has a coin and two 6-sided dice (all possibly biased)
  • He first tosses a coin, if the result is heads, he throws dice A, otherwise he throws dice B
  • He repeats this $n$ times and gives me the results of each die throw (without telling me which die generated which result)

How can I estimate the bias of the coin and the bias of each die using only the data he gives me?


My work so far:

  • Bias of the coin: $\theta$
  • Bias of die $k$: $\theta^k$ (6-dimensional vector)
  • Bias of side $i$ of die $k$: $\theta_i^k$ (e.g. the probability of landing a 3 with die A is $\theta_3^A$)
  • $i$'th unobserved coin toss result (with value either A or B): $z_i$
  • All the coin tosses results: $\mathbf{z}$
  • $i$'th dice throw result: $w_i$
  • All the dice throws results: $\mathbf{w}$
  • I want to compute $P(\theta,\theta^A,\theta^B~|~\mathbf{w})$. To do that, I use bayes' rule:

$$ P(\theta,\theta^A,\theta^B~|~\mathbf{w}) = \frac{P(\mathbf{w}~|~\theta,\theta^A,\theta^B)\cdot P(\theta,\theta^A,\theta^B)}{P(\mathbf{w})}$$

  • To compute $P(\mathbf{w}~|~\theta,\theta^A,\theta^B)$ I first note that the throws are independent of each other, so

$$P(\mathbf{w}~|~\theta,\theta^A,\theta^B)=\prod_{i=1}^nP(w_i~|~\theta,\theta^A,\theta^B)$$ and then I apply the law of total probability

$$ P(w_i~|~\theta,\theta^A,\theta^B) = P(w_i~|~z_i=A,\theta,\theta^A,\theta^B)\cdot P(z_i=A~|~\theta,\theta^A,\theta^B) + P(w_i~|~z_i=B,\theta,\theta^A,\theta^B)\cdot P(z_i=B~|~\theta,\theta^A,\theta^B)$$

These terms can now be directly computed as

$$P(w_i~|~\theta,\theta^A,\theta^B)= \left( \prod_{j=1}^6 \theta_j^{A[w_i=j]}\right)\theta + \left( \prod_{j=1}^6 \theta_j^{B[w_i=j]}\right)(1-\theta)$$ (where $[x=i]$ is the Iverson Bracket)

  • Now, in order to compute $P(\theta,\theta^A,\theta^B)$, I assume three independent priors, so $P(\theta,\theta^A,\theta^B) = P(\theta)\cdot P(\theta^A)\cdot P(\theta^B) $. For the coin I'll use a uniform Beta distribution and for the dice a uniform Dirichlet distribution (one for each).

  • Finally, I could use the law of total probability again to compute $P(\mathbf{w})$, but I believe this to be intractable. Instead, I'm trying to understand how I can apply Gibbs sampling to this problem and estimate the bias parameters without computing $P(\mathbf{w})$.


If anything needs clarification, please say so. Any help would be appreciated, thanks in advance.

$\endgroup$

2 Answers 2

2
$\begingroup$

How can I estimate the bias of the coin and the bias of each die using only the data he gives me?

You cannot.

Let the chances of the six outcomes of the first die be $p_1, p_2, \ldots, p_6$ and those of the second die be $q_1, q_2, \ldots, q_6$. Let the chance of selecting the first die be $r$. Then the expected frequency of observing the outcome $X$ for $X=i$, $i=1, 2, \ldots, 6$, in your experiment is

$$\Pr(X=i) = r p_i + (1-r) q_i = t_i.$$

You can estimate the $t_i$ from the data, but that is all, because the $t_i$ completely determine all properties of the random variable $X$. In particular, except in unusual circumstances (such as having at least one of $p_i$ and $q_i$ equal zero), you cannot even estimate $r$.

$\endgroup$
2
  • $\begingroup$ I didn't fully understand your answer, whuber. Maybe I can agree that merely looking at the observable data can't lead us to an unique solution. But depending on the throw outcomes we observe, some combinations of parameters become more likely than others, so there should be a way to obtain at least a bit of information about them (and then perhaps choose the most probable given the data, for instance). What do you think? $\endgroup$
    – JLagana
    Mar 14, 2016 at 17:39
  • $\begingroup$ The problem is that for every combination of the parameters there is a six-dimensional family of other combinations that leads to exactly the same answers. This is the sense in which your parameters are not identifiable. So you definitely get some information, but you get almost no information about the coin and you don't get information about the dice separately. $\endgroup$
    – whuber
    Mar 14, 2016 at 19:20
0
$\begingroup$

This problem is a typical latent variable problem, where you have unobserved data (the outcome of the coin). In this cases the parameters are usually estimated through the EM algorithm, which can deals with latent variables. Once the parameters are estimated you can evaluate the bias of the two distributions.

This paper will probably help you, you will just need to change the form of the likelihood as he is using two other coins instead of two dices.

http://www.cs.columbia.edu/~mcollins/6864/slides/em1.4up.pdf

$\endgroup$
3
  • $\begingroup$ You are proposing to estimate 11 independent parameters based on observing only six possible distinct outcomes. Since that is hardly plausible, perhaps you should be a little more specific about how this EM algorithm would work. $\endgroup$
    – whuber
    Mar 14, 2016 at 16:50
  • $\begingroup$ It doesn't matter if they are distinct or not, it is just about writing a likelihood. Writing the entire EM algorithm here is a little bit tricky $\endgroup$
    – adaien
    Mar 14, 2016 at 16:58
  • $\begingroup$ The likelihood can be written in terms of just five parameters. It's impossible, therefore, to estimate 11 independent numbers: at least six will be unidentifiable. Even if the EM algorithm managed to converge--which seems unlikely--it would not give a unique result. $\endgroup$
    – whuber
    Mar 14, 2016 at 17:01

Your Answer

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

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