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 \begin{equation} \mathbb{E}_{p(y|\theta)}(\phi_c(y)) \approx \frac{1}{|S|} \sum_{y'\in S} \phi_c(y') \end{equation} 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))$?

[1] https://www.cs.ubc.ca/~murphyk/MLbook/pml-print3-ch19.pdf


Your Answer

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

Browse other questions tagged or ask your own question.