1
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ A Markov network can have latent variables. $\endgroup$
    – alto
    Dec 7 '12 at 22:00
  • $\begingroup$ Thanks Yann! I suspected this will be the case. I have two more questions: 1) Do you have any reference for conversion from (2) to (1)? 2) Is it known under what conditions on the underlying RBM/NN (i.e. degree restrictions and so on), they are equivalent? Thanks again! $\endgroup$
    – Rajhans
    Dec 8 '12 at 19:24
  • $\begingroup$ @alto Yes, I am comparing to the specific network in his post. $\endgroup$
    – ynd
    Dec 19 '12 at 20:11
  • $\begingroup$ @Rajhans I don't know of any work on converting (2) to (1) analytically. However, you can do this simply by minimizing the KL divergence between the two distributions. Running a program that does this is easy. You generate a bunch of samples from (2), and you use that to train (1) with maximum likelihood. $\endgroup$
    – ynd
    Dec 19 '12 at 20:17
2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Oh well, I actually meant equivalence in terms of only observed variables -- essentially "maxing" (or more commonly, "marginalizing") out latent variables and then establishing equivalence. $\endgroup$
    – Rajhans
    Dec 8 '12 at 19:23
  • $\begingroup$ @Rajhans, based on the discussion over at metaoptimize, metaoptimize.com/qa/questions/11593/…, I see I misinterpreted your question and you were only interested in MRFs with fully observed variables. $\endgroup$
    – alto
    Dec 9 '12 at 15:33

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.