1
$\begingroup$

I am reading the book (available for free from the author's website) "Information Theory, Inference, and Learning Algorithms" by David J.C. MacKay. On p. 328 (p. 340 of the pdf) maximum likelihood decoding of the (7,4) Hamming code is considered and solved by brute-force enumerating posterior probabilities of all codewords. However, I do not quite understand the problem statement which is in terms of "normalized likelihoods".

A codeword $\mathbf{x}$ (4 message bits and 3 parity bits for the (7,4) Hamming code) is sent over some noisy channel. The channel defines (and is defined by) all conditional probabilities $P(\mathbf{y}|\mathbf{x})$. (I am only really interested in symmetric memoryless channels.) When the noisy message $\mathbf{y}$ is received (which may have continuous values, as in the case of BIAWGN channel), it is decoded by finding the $\hat{\mathbf{x}}$ which maximizes the posterior probability, $\hat{\mathbf{x}} = \operatorname{argmax}_{\mathbf{x}}P(\mathbf{x}|\mathbf{y})$, where by Bayes' theorem $$ P(\mathbf{x}|\mathbf{y}) = \frac{P(\mathbf{y}|\mathbf{x})P(\mathbf{x})}{P(\mathbf{y})}. $$

In the setting of the book, the received codeword and the channel are both not given, but instead only "normalized likelihoods". I don't quite understand what these are. The prior distribution $P(\mathbf{x})$ is not mentioned, I guess it is implicitly assumed to be uniform.

The seven "normalized likelihoods" given are $(0.1, 0.4, 0.9, 0.1, 0.1, 0.1, 0.3)$. As illustration some ratios of likelihoods are also given (quote): $$ \frac{P(y_1|x_1=1)}{P(y_1|x_1=0)}=\frac{0.1}{0.9},\quad \frac{P(y_2|x_2=1)}{P(y_2|x_2=0)}=\frac{0.4}{0.6},\quad \text{etc.} $$

Afaik, there is no reason why $P(y_1|x_1=1) + P(y_1|x_1=0)$ should equal 1 for some given $y_1$. For example, in case of BIAWGN channel, $P(y_1|x_1=1)$ and $P(y_1|x_1=0)$ are normal distributions with same standard deviation, centered at (e.g.) $\pm 1$. They do not add to 1 for almost all values of $y_1$. Is this a consequence of this "normalization" of the likelihoods, whatever it means here? The author also writes: "from the point of view of decoding, all that matters is the likelihood ratio". While this seems intuitively plausible to me, is there a simple way to see that this is true in general from the formula of Bayes' theorem? In the book the likelihoods of all codewords are computed. E.g., for $[0000000]$ MacKay obtains the likelihood $P(\mathbf{y}|\mathbf{x}=[0000000]) = 0.0275562$, which is equal to the product of all single-bit likelihoods $\prod_n P(y_n|x_1=0)$. This works out numerically given above values and assuming $P(y_n|x_1=1) + P(y_n|x_1=0) = 1$ for all $n$ (why?) but it would depend on whatever weird "normalization" of the likelihoods is being used, right? How does one see that the posterior probability would not? (In the book, the posterior probability of a codeword is equal to the likelihood divided by the sum of all codeword likelihoods, consistent with the assumption that the prior is uniform.)

How does one obtain these likelihoods in practice? For the binary symmetric channel BSC(p), $y_1$ can only take values $\{0, 1\}$ and (correct me if I'm wrong) $\frac{P(y_1=1|x_1=1)}{P(y_1=1|x_1=0)}=\frac{1-p}{p}$ while $\frac{P(y_1=0|x_1=1)}{P(y_1=0|x_1=0)}=\frac{p}{1-p}$. In this case, the likelihoods for a given $y_1$ do add up to one. This need not be general though, right?

For BIAWGN($\sigma$), suppose (case 1) in one communication I received a fixed value $a_1$ for $y_1$. Alternatively, (more realistically) I know that my received value is in the interval $I_1$ (case 2) or even itself has a probability distribution due to measurement error, $P(a_1)$ (case 3). How to find the likelihoods in these cases ($\mathcal{N}(\mu, \sigma^2)$ is the gaussian distribution centered at $\mu$ with variance $\sigma^2$)? $$ \begin{align} P(y_1|x_1=1) &= \mathcal{N}(1, \sigma^2)(a_1) \qquad \text{(case 1, also cf. eqn. 25.3 in the book)}\\ P(y_1|x_1=1) &= \int_{I_{1}}\mathcal{N}(1, \sigma^2) \qquad \text{(case 2, wrong?)}\\ \qquad ??? \quad \text{(case 3)}\\ \end{align} $$

$\endgroup$
1
  • $\begingroup$ I suspect the likelihoods "in practice" are obtained from sample data. In any case for machine learning topics it might be worth looking at previous Questions posted to sister site CrossValidated and (for example) The ways to normalize the likelihood in EM algorithm. In addition to general statistics topics, CrossValidated stakes out machine learning topics for treatment. Your Question is also welcome here! $\endgroup$
    – hardmath
    Aug 4 '20 at 15:35
1
+50
$\begingroup$

Given a channel output $Y_i=y_i$, we compute $P_{X_i|Y_i}(x_i|y_i)$ for $x_i=0$ and $x_i=1$ via Bayes' rule, i.e., $$ P_{X_i|Y_i}(x_i|y_i)= \frac{P_{Y_i|X_i}(y_i|x_i)P_{X_i}(x_i)}{P_{Y_i}(y_i)}. $$ Since $P_{X_i}(0)=P_{X_i}(1)=\frac{1}{2}$ (the common assumption in this context), we have that $$P_{X_i|Y_i}(x_i|y_i)=c\cdot P_{Y_i|X_i}(y_i|x_i)$$ for $x_i=0, 1$, where $c$ is some constant. Since $P_{X_i|Y_i}(0|y_i)+P_{X_i|Y_i}(1|y_i)=1$ and the likelihood $P_{Y_i|X_i}(y_i|x_i)$ is specified by the channel (you can see more details in the last part of my reply), we can find $c$ without computing $P_{Y_i}(y_i)$. However, a more smarter choice of $c$ is $$c=(P_{Y_i|X_i}(y_i|0)+P_{Y_i|X_i}(y_i|1))^{-1}.$$ From here, you should be able to sense why the posterior probability $P_{X_i|Y_i}(x_i|y_i)$ is called the normalized likelihood. To end the first part, I would like to point out this fact: $$ \frac{P_{X_i|Y_i}(0|y_i)}{P_{X_i|Y_i}(1|y_i)}=\frac{P_{Y_i|X_i}(y_i|0)}{P_{Y_i|X_i}(y_i|1)}. $$

Regarding your second question:

The author also writes: "from the point of view of decoding, all that matters is >the likelihood ratio". While this seems intuitively plausible to me, is there a >simple way to see that this is true in general from the formula of Bayes' theorem?

Looking at the decoding problem, our goal is to find a codeword $\mathbf{x}$ in your codebook $\mathcal{C}$ such that $P_{\mathbf{X}|\mathbf{Y}}(\mathbf{x}|\mathbf{y})$ is maximized. For simplicity, I consider memoryless binary-input channels. As codeword are equally likely (by assumption), the decoding task for any given channel output $\mathbf{y}$ is $$ \arg\max_{\mathbf{x}\in\mathcal{C}}P_{\mathbf{X}|\mathbf{Y}}(\mathbf{x}|\mathbf{y}) =\arg\max_{\mathbf{x}\in\mathcal{C}}P_{\mathbf{Y}|\mathbf{X}}(\mathbf{y}|\mathbf{x})=\arg\max_{\mathbf{x}\in\mathcal{C}}\prod_{i=1}^n P_{Y_i|X_i}(y_i|x_i). $$ To solve the above optimization problem, we may compare $P_{\mathbf{Y}|\mathbf{X}}(\mathbf{y}|\mathbf{x})$ for all pairs of codewords $\mathbf{x}_1$ and $\mathbf{x}_2$: we know $\mathbf{x}_1$ is more likely to be transmitted if $$ \prod_{i=1}^n\frac{P_{Y_i|X_{1,i}}(y_i|x_{1,i})}{P_{Y_i|X_{2,i}}(y_i|x_{2,i})}\ge 1. $$ From this comparison, you should realize why the decoding only relies on the likelihood ratios.

Your last question should be no longer a question. Indeed, this equality $$P_{Y_i|X_i}(y_i|0)+P_{Y_i|X_i}(y_i|1)=1$$ is in general not true, and we really don't mean this (I know the name "normalized likelihood" might confuse you). So, forget about this equality.

Next, how do we compute the likelihood $P_{Y_i|X_i}(y_i|x_i)$? Well, it is given to you once the channel model is determined since $P_{Y_i|X_i}(y_i|x_i)$ is exactly the channel transition probability.

For a given channel output $Y_i=y_i$ of an AWGNC where $Y_i=X_i+N_i$ and $N_i\sim\mathcal{N}(0, \sigma^2)$, we have that $P_{Y_i|X_i}(y_i|x_i)=\mathcal{N}(x_i, \sigma^2)(y_i)$ for $X_i=x_i$. The other cases need to be more specific so that we can discuss further. I hope the above helps. :)

$\endgroup$
5
  • $\begingroup$ Thank you very much for your answer! Am I understanding correctly that the first given "normalized likelihood" from the book, which is $0.1$, could arise as follows? Given some received first message bit $y_1$ one derives from the channel model observed likelihoods $A := P(Y_1=y_1 | X_1=0)$ and $B := P(Y_1=y_1 | X_1=1)$. The normalization of these likelihoods, which can be done individually for each received bit and does not change comparisons of posterior probabilities, allows to state the value $\frac{B}{A+B}$, which in the example happens to be $0.1$. $\endgroup$ Sep 3 '20 at 7:33
  • $\begingroup$ Also, where you say "a more smarter choice of $c$ is ..." (sic), do you actually mean "the correct choice of $c$ is ..."? $\endgroup$ Sep 3 '20 at 7:39
  • $\begingroup$ Yes for both comments. :) $\endgroup$ Sep 3 '20 at 11:45
  • $\begingroup$ Thank you! The last remaining point (of perhaps secondary importance) would be how to deal with the case where the measured value (e.g. $y_1$) itself has an associated uncertainty. E.g., suppose the measurement device that measures the encoded "Gaussian channel"-outputs has a finite accuracy. Perhaps this question does not really make sense as the combined system of noisy channel and finite accuracy measurement should rather be considered together as a communication channel. In that case only the transition probability distribution of the channel should be changed. How is that to happen? $\endgroup$ Sep 3 '20 at 13:22
  • $\begingroup$ The measurement device is often included as a part of the channel (which is called the matched filter). In AWGNC, the noise $N_i$ models all possible noises of the transmission system; the noises are from the analog RF frontend and the transmission medium. So, we generally don't talk about the measurement noise on $Y_i$ in digital communications. However, you can quantize $Y_i$ and talk about the quantization error, e.g., $q_i=Q(y_i)+e_i$, where $e_i$ models the quantization error and is assumed to have a certain distribution. From this, you can compute the likelihood $P_{Q_i|X_i}(q_i|x_i)$. $\endgroup$ Sep 3 '20 at 14:38
1
$\begingroup$

I do not quite understand the problem statement which is in terms of "normalized likelihoods".

If the prior is not mentioned, as you supposed, it is assumed uniform (constant).

Thus the posterior is a density that is $\propto$ likelihood....

The symbol $\propto$ means that to ensure that your posterior is a nice density you have to normalize the likelihood....

Here is an example.

Draw a coin (we do not know if it is fair or not) 10 times getting 6 Heads and 4 Tails.

As we do not know anything about the "fair or not fair" parameter $\theta$ the posterior is

$$\pi(\theta|\mathbf{x}) \propto \theta^6 (1-\theta)^4$$

(in the likelihood we do not consider the constant $\binom{10}{6}$ because it is independent from $\theta$ so it doesn't give us any useful information)

It is understood that, to ensure that $\pi(\theta|\mathbf{x})$ is a density we have to normalize the likelihood (observed likelihood) finding

$$\pi(\theta|\mathbf{x})=2310\cdot \theta^6 \cdot(1-\theta)^4$$

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. Is it correct to summarize it as "If the prior is uniform the posterior is proportional to the likelihood. Hence multiplying all likelihoods by a constant does not change the posterior." ? This makes sense but I still don't understand how the computation in the book works, especially why the normalized likelihoods sum to 1 for each bit, and also how to obtain the likelihoods from measurements in the examples I mention. Could you perhaps address some of my remaining sub-questions? $\endgroup$ Sep 2 '20 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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