Question

Recall the energy function and the partition function of a Restricted Boltzmann Machine are defined as

$E(v,h|\theta)\doteq -v^{T}Wh$

and

$Z(\theta)=\sum_{v} \sum_{h} exp(-E(v,h|\theta))$

respectively. Suppose the RBM has K binary hidden nodes and R binary visible nodes, and K<R.

(a)What is the time complexity for computing the partition function in a naive way?

(b) Ignoring the biases, can we reduce the time complexity of (a)?

Answer 1

Solution: . The partition function has two summations one that sums " times and other sums "h" times. Each computation of energy function takes constant time, where "v" and "h" values should be provided . To implement each summation, loops are needed. . The inner loop executes "h times. The outer loop executes "v" times. Hence, time complexity of partition function computation will be O(vh)