1
$\begingroup$

There are a number of possible criteria to use in making decisions. Can someone elaborate on the difference between ML and MAP for a sequence of BPSK symbols impaired by Gaussian noise ?

$\endgroup$
4
$\begingroup$

You have a set of message set $m_i$, $0 \le i \le N-1$. (For example, QPSK will be $N=4$). For the transmitted message $m_i$, the corresponding symbol vector is $\textbf{x}_i$, and the received symbol vector is $\textbf{y} = \textbf{x} + \textbf{w}$, where $\textbf{w}$ is the AWGN at the receiver. The above is a simplified baseband model assuming a simple Line-Of-Sight(LOS) channel without any delay.

At the receiver, after observing $\textbf{y}$ you arrive at a decision for the transmitted symbols, $\tilde{\textbf{x}}_i$. The decision you make is such that the probability of error $P_e = P(\tilde{m_i} \ne m_i)$ is minimum. In other words, the Probability of being correct $P_c = 1 - P_e$ has to be maximized. Using a hypothetical rule you have made a decision $\tilde{m}_i$ based on $\textbf{y}$, so $$ P_c(\tilde{m} = m_i;\textbf{y}) = P(\tilde{\textbf{x}} = \textbf{x}_i;\textbf{y}) = P(\textbf{x}_i|\textbf{y})P(\textbf{y}) $$ Here I have made use of formula $P(AB) = P(A|B)P(B)$. Event A is the event that $x_i$ was transmitted. Our decision is correct if $\tilde{x_i}$ is interpreted as $x_i$. We are trying to maximize the probability of getting this decision correct. In order to maximize the above term among all message set $0 \le i \le N-1$, the term $P(\textbf{y})$ can be ignored since it does not depend on $i$. Hence

$$ \tilde{m_i} = argmax_i\,\, P(\textbf{x}_i|\textbf{y}) $$ You are deciding the $i$ which maximizes the above probability after observing $\textbf{y}$. Hence the whole method above is called Maximum A-posteriori Probability decision because you are maximizing a-posteriori probability $P(\textbf{x}_i|\textbf{y})P(\textbf{y})$

The term above can be re-written as $P(\textbf{x}_i|\textbf{y}) = P(\textbf{y}|\textbf{x}_i)P(\textbf{x}_i)/P(\textbf{y})$.

If we assume equal probability for all messages in the set $\textbf{m}$ then we can ignore the term $P(\textbf{x}_i)$ since they are equal for all values of $i$. Hence $$ \tilde{m_i} = argmax_i\,\, P(\textbf{y}|\textbf{x}_i) $$ This is the Maximum Likelihood detection rule. We are maximizing the likelihood probability $P(\textbf{y}|\textbf{x}_i)$.

|improve this answer|||||
$\endgroup$
2
$\begingroup$

Maximium A Posteriori (MAP) and Maximum Likelihood (ML) are both approaches for making decisions from some observation or evidence.

MAP takes into account the prior probability of the considered hypotheses. ML does not. This set of probabilities, known as "a priori" probabilities or simply "priors", is often known imperfectly, but even rough approximations are often better than nothing.

The approaches are the same in the case where the prior probability is truly uniform. For example in the roll of a single fair die, or deciding a bit in a random binary message.

MAP and ML can be quite different. For an anecdote on how the obvious answer can be exactly wrong, search for "Abraham Wald and the Missing Bullet Holes" from the excellent book "How Not to be Wrong" by Jordan Ellenberg.

A simpler case of imbalanced priors is found in the old saying,

When you hear hooves, think 'horses' not 'zebras'

One can think of MAP decision/estimation as a rigorous version of Occam's razor.

Let's say we observed event

  • $A$ := Audible hooves

goal: Decide what animal is thundering towards us.

and we live in world with only 3 ungulate (hooved) species:

  • $Z$ebras,
  • $H$orses,
  • $C$hevrotain

(such worlds are common in post-apocalyptic fiction and math problems)

Let's say we know when each of these animals is present, their chance of making $A$udible hoof sounds is as follows

  • P(A | Z) = .91 ( read as probability of event A, given that Z is true)
  • P(A | H) = .9
  • P(A | C) = .2

These are known as likelihoods on $Z,H,C$ when $A$ is true.

ML: an easy answer

The above is all the info we need to make the ML decision = Zebras. The zebras have a higher likelihood of generating the observation when they are present.

MAP: a better answer

What we really want to decide is: which is highest in {P(Z|A),P(H|A),P(C|A)} i.e. what is the chance a particular animal is present, given that we observed $A$?

To decide that, we need to know more about the abundance of the different animals. In the state where you live there are 100 wild chevrotain , 100 zebras, and 800 horses. These are the prior probabilities (scaled by a constant).

We can order our posterior probabilities (Omitting common factors in the posterior probabilities found via Bayes' Rule) in the following order

$$ P(H|A) \propto P(A|H)P(H) = .9 \times 800 = 720 $$ $$ P(Z|A) \propto P(A|Z)P(Z) = .91 \times 100 = 91 $$ $$ P(C|A) \propto P(A|C)P(C) = .2 \times 100 = 20 $$

So the MAP decision is overwhelmingly $H$orses. In fact, by using the law of total probability, we can say that there is an 86% chance it is horses (= 720/(720+91+20))

Of course, by the time you've done all this math, you've probably been trampled.
Sometimes an easy answer gives you what you need to act.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Great answer Mark! Thanks!! (including realizing that I've already been trampled by the time I got to the end, good point). $\endgroup$ – Dan Boschen Apr 1 at 3:59
1
$\begingroup$

A brief, non-mathy explanation:

ML assumes that all hypothesis are equally likely. MAP does not make this assumption. MAP is the optimum criterion, but under some conditions ML is optimum too.

When using BPSK, if the bits are independent and equally likely, then ML and MAP are equivalent and ML is optimum.

If the bits are not equally likely, then you should use MAP in order to minimize the probability of error. You can also use ML (to simplify the receiver), but since it's no longer optimum, your error rate will be larger than the minimum.

|improve this answer|||||
$\endgroup$

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.