Why is the most probable assignment for all variables in MRFs called MAP assignment?

I am new to graphical model, especially Markov Random Fields. I have a question about MAP assignment. Let say we have the graph structure and all the potential functions. MAP assignment in MRFs is defined as the most probable assignment for all variables (no given evidence in this case). My question is why it is called MAP (why not MLE or anything else). What is the connection between them? I know MAP and MLE share a lot in common except for one thing that MAP uses the prior distribution of the parameters. But I cannot figure out the connection between the most probable assignment in MRF and MAP.

MLE is a point estimate $\hat{\theta}_{\text{MLE}}$ that resides at a mode of the likelihood density. That is, $$L(\theta; X) = \Pr(X | \theta)\\ \hat{\theta}_{\text{MLE}} = \arg \max_{\theta} \Pr(X | \theta)$$

MAP stands for maximum a-posteriori. It is a point estimate $\hat{\theta}_{\text{MAP}}$ that resides at a mode of the posterior distribution (the distribution over the parameters themselves conditioned on our observed data). We can perform MAP estimation by incorporating a prior distribution for our parameters.

$$\Pr(\theta | X) = \frac{\Pr(X | \theta) \Pr(\theta)}{\Pr(X)} \\ \Pr(\theta | X) \propto \Pr(X | \theta) \Pr(\theta) \\ \hat{\theta}_{\text{MAP}} = \arg \max_{\theta} \Pr(X |\theta)\Pr(\theta)$$

This is a simple application of Bayes' Theorem. The reason we use "proportional to" is that we don't care about the marginal likelihood constant. Since it is only a constant our point estimate for this "psuedo-MAP" still corresponds to a point-estimate for the true MAP. By definition $\hat{\theta}_{\text{MAP}}$ is the (at least locally) most-probable estimate under the posterior distribution.

The key take-away is that the Maximum Likelihood estimate is the point estimate that maximizes the probability of observing your data. The MAP estimate is the point estimate that is the (at least locally) most probable under your posterior distribution of parameters. In the end deciding whether to use the MLE or MAP estimate is up to you and your model. It really depends on what you are more interested in.

To stress the difference one last time, look at the difference between the two definitions for the distributions being maximized over. In ML estimation we are maximizing over the distribution of observing our data; in MAP estimation we are maximizing over the distribution of parameters themselves. Hence why we can say MAP estimates are the most-probable estimate whereas we cannot for the ML estimate.

• One difference between MAP and MLE is MAP uses the prior distribution of the parameter while MLE assume it is uniformly distributed. But why the most probable configuration in Markov Random Field is called MAP assignment, but not MLE? – Khoi Hoang Jan 29 '15 at 21:23
• @KhoiHoang I've added a clarification. Let me know if it still is unclear. – Nicholas Mancuso Jan 29 '15 at 21:28
• Could you relate MAP and MLE to the inference problem in Markov Random Fields? – Khoi Hoang Jan 29 '15 at 21:39
• A MRF is just a way of structuring the relationship between variables (ie, model). These models are parameterized based on their underlying distributions (specified by the model-creator). We often do not know the parameters to this complex distribution and would like to estimate them from the data (MLE) or from the data and prior knowledge of what they should be (MAP). Understanding MLE and MAP in general will make it "fall into place" for MRFs... – Nicholas Mancuso Jan 30 '15 at 1:07
• @KhoiHoang, I added one last paragraph that should clarify it for you a bit better. Again the terminology and approaches to inference span all areas of ML/Stats, not just MRF specifically. – Nicholas Mancuso Feb 2 '15 at 21:47