I'm reading the book by MacKay "Information theory, inference and learning algorithms" and I'm confused by how he introduces the decoding problem for LDPC codes (page 557).

given a channel output $\mathbf{r}$, we wish to find the codeword $\mathbf{t}$ that whose likelihood $P(\mathbf{r}|\mathbf{t})$ is biggest.

I can get on board with that, even if it seems a bit backwards since $\mathbf{r}$ is the evidence we have, so I would be more comfortable if we were trying to find $\mathbf{t}$ that maximizes $P(\mathbf{t}|\mathbf{r})$, and as a matter of fact, he goes on to say

there are two approaches to the decoding problem both of which lead to the generic problem 'find $\mathbf{x}$ that maximizes $$ P^*(\mathbf{x})=P(\mathbf{x})\mathbb{1}[\mathbf{Hx}=\mathbf{z}]$$

he exposes the two points of view in the following page, the first one especially confuses me

the codeword decoding point of view

First, we note the prior distribution over codewords $$ P(\mathbf{t})=\mathbb{1}[\mathbf{Ht}=\mathbf{0}]$$[...]. The posterior distribution over codewords is given by multiplying the prior by the likelihood [...] $$P(\mathbf{t}|\mathbf{r})\propto P(\mathbf{t})P(\mathbf{r}|\mathbf{t}) $$

from the generic decoding problem he gave, it looks like we're actually trying to maximize $P(\mathbf{x})=P(\mathbf{t}|\mathbf{r})$, instead of $P(\mathbf{r}|\mathbf{t})$.

Is it obvious that the two maxima are the same and with the same maximizer? It is not obvious to me since the maximizer $\mathbf{t_0}$ that maximizes $P(\mathbf{r}|\mathbf{t})$ might actually minimize $P(\mathbf{t})$, so the maximizer of $P(\mathbf{t})P(\mathbf{r}|\mathbf{t})$ might be different! I understand that in this case $P(\mathbf{t})$ is uniform, so this shouldn't be a problem, but it seems weird to me that this is simply not stated and I feel like I'm missing something.

Why should we start with the problem of maximizing $P(\mathbf{r}|\mathbf{t})$ and not $P(\mathbf{t}|\mathbf{r})$? Why does he seem to switch after a few sentences? Am I correct in thinking the algorithm presented actually maximizes $P(\mathbf{t}|\mathbf{r})$?

Thank you


Maximizing $P(r|t)$ is known as the Maximum Likelihood (ML) principle, while maximizing $P(t|r)$ is known as the Maximum A Posteriori probability (MAP) principle.

Here are some facts that answer your question:

  • Optimal decoding (minimizing the probability of error) is achieved by the MAP principle. See p. 152 of the book.
  • However, using MAP would require a different decoding algorithm for every distribution on $t$. I.e. you would have to adapt decoding to the statistical properties of the source. To avoid this, it is typical to assume a uniform distribution on $t$. In this case, MAP and ML are equivalent because $P(t|r)$ becomes proportional to $P(r|t)$ (see p. 152 again).
  • I agree with you he should have started with the MAP problem of maximizing $P(t|r)$, since that's the correct goal anyway. But I presume that he is assuming a uniform distribution on $t$, in which case the difference doesn't matter anyway.
| cite | improve this answer | |

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.