# Using MAP inference in MRFs to estimate expectations

This question pertains to MRFs of the form $$p(y | \theta) = \frac{1}{Z(\theta)} \exp \left( \sum_c \theta_c^\top \phi_c(y) \right)$$ with notation and nomenclature taken from [1]. Suppose that these are binary MRFs with $$y \in \{0,1\}^n$$, and that all cliques $$c$$ are of size 2. Furthermore, suppose that we have an algorithm that can find the MAP configuration $$y^* = \arg \max_y p(y|\theta).$$ Our goal is to draw "good" samples in order to estimate expectations, in particular we wish to estimate $$$$\mathbb{E}_{p(y|\theta)}(\phi_c(y)) \approx \frac{1}{|S|} \sum_{y'\in S} \phi_c(y')$$$$ where $$S$$ is the set of "good" samples we obtained from $$p(y|\theta)$$.

Clearly, $$y^*$$ is a "good" sample as, by definition, it has the highest probability $$p(y|\theta)$$. However, to estimate the expectation, we would like to draw other high probability samples.

My question is this. In order to get a good estimate for the expectation of a given clique $$c$$, can we apply the following algorithm:

For all configurations $$x_i$$ in $$\phi_c(y)$$ (given the assumptions there are exactly 4 such $$x_i$$), compute $$y^*_i = \arg \max_y p_i(y|\theta)$$ where $$p_i$$ is identical to $$p$$ except for the variables in $$c$$ which are fixed to the configuration $$x_i$$. Is it then true that $$\frac{1} { \sum_i \exp \left( \sum_c \theta_c ^ \top \phi_c(y_i^*) \right) } \sum_i \exp \left( \sum_c \theta_c ^ \top \phi_c(y_i^*) \right) \phi_c(y_i^*)$$ is a good estimator of the expectation $$\mathbb{E}_{p(y|\theta)}(\phi_c(y))$$?