Restricted Boltzmann Machines and Markov Networks: relationship in inference?

Question

I am wondering if there is some equivalence between retricted Boltzmann machines and pairwise Markov networks in terms of MAP inference.

More specifically, let $y \in \{0,1\}^m$ be the output/visible layer and $h\in \{0,1\}^k$ be the hidden layer. Specifically $k < n$ (may be $\ll$.)

The MAP estimate over RBMs can be written as \begin{equation} \text{arg}\max_{y \in \{0,1\}^n ,h \in \{0,1\}^k} y^T A h + u^t y + v^t h ~~~(1). \end{equation} for some given $A, y,$ and $v$.

Now, a consider a pairwise Markov network defined only over $y$ where the inference is given by \begin{equation} \text{arg}\max_{y \in \{0,1\}^n} y^T B y + w^t y ~~~(2), \end{equation}

for some given $B$ and $w$.

My question is that, given an RBM with matrix $A$ and vectors $u$ and $v$, do there exist $B$ and $w$ such that (1) and (2) are maximized for the same $y$? If not generally, is this true under some conditions? Is the vice-versa (i.e. given $B$ and $w$, come up with equivalent RBM) true with $k < n$?

Answer 1

This Markov network can only model pairwise correlations, whereas the RBM can model higher order correlations thanks to the latent variables. The RBM is a universal approximator of distributions, (2) is not.

To answer you questions, given an RBM in general you can't come up with an equivalent (2). In the same way that in general you can't approximate a kernel SVM with a linear SVM.

Given (2), you can always come up with the equivalent RBM.

Answer 2

Sure. RBMs are just a specific type of undirected graphical model aka Markov Random Field aka Markov Network. In particular, one that has a specific bipartite structure such that observed (visible) variables are conditionally independent given the latent (hidden) variables and vice versa.

Normally I'm used to seeing equation (2) include a factor of $\frac{1}{2}$, i.e. $$ \text{arg}\max_{y \in \{0,1\}^n} \frac{1}{2}y^TBy + w^Ty. $$ The $\frac{1}{2}$ factor comes in since Markov Networks are undirected, and the way you've written your equation essentially double counts the interaction between $i$ and $j$.

Anyway, assuming the form I've written above we can certainly get equivalence of the 2 equations. Let $h \in \{0, 1\}^n$, $v \in \{0, 1\}^m$ and $d = m + n$. Then define $B \in M_{d \times d}(\mathbb{R})$, $w \in \mathbb{R}^d$, and $y \in \{0, 1\}^d$ as $$ B_{i + m,j} = B_{j, i + m} = \begin{cases} A_{i,j} & i \le n,\;j \le m\\ 0 & \text{otherwise} \end{cases} $$

$$ w = b\|c $$ $$ y = v\|h $$ where $\|$ is concatenation of vectors.

Hopefully the substitutions of variable names I've made to avoid conflicts are clear. I've kept all the names in equation (2) the same but substituted $v = y$, $b = u$ and $c = v$ in (1).