CONTRASTIVE DIVERGENCE LEARNING IS A TIME REVERSAL ADVERSARIAL GAME
Year: 2021

Abstract:
Contrastive divergence (CD) learning is a classical method for fitting unnormalized statistical models to data samples. Despite its wide-spread use, the convergence properties of this algorithm are still not well understood. The main source of difficulty is an unjustified approximation which has been used to derive the gradient of the loss. In this paper, we present an alternative derivation of CD that does not require any approximation and sheds new light on the objective that is actually being optimized by the algorithm. Specifically, we show that CD is an adversarial learning procedure, where a discriminator attempts to classify whether a Markov chain generated from the model has been time-reversed. Thus, although predating generative adversarial networks (GANs) by more than a decade, CD is, in fact, closely related to these techniques. Our derivation settles well with previous observations, which have concluded that CD’s update steps cannot be expressed as the gradients of any fixed objective function. In addition, as a byproduct, our derivation reveals a simple correction that can be used as an alternative to Metropolis-Hastings rejection, which is required when the underlying Markov chain is inexact (e.g., when using Langevin dynamics with a large step).

heading: 1 INTRODUCTION
text: Unnormalized probability models have drawn significant attention over the years. These models arise, for example, in energy based models, where the normalization constant is intractable to compute, and are thus relevant to numerous settings. Particularly, they have been extensively used in the context of restricted Boltzmann machines (Smolensky, 1986; Hinton, 2002), deep belief networks (Hinton et al., 2006; Salakhutdinov & Hinton, 2009), Markov random fields (Carreira-Perpinan & Hinton, 2005; Hinton & Salakhutdinov, 2006), and recently also with deep neural networks (Xie et al., 2016; Song & Ermon, 2019; Du & Mordatch, 2019; Grathwohl et al., 2019; Nijkamp et al., 2019).
Fitting an unnormalized density model to a dataset is challenging due to the missing normalization constant of the distribution. A naive approach is to employ approximate maximum likelihood estimation (MLE). This approach relies on the fact that the likelihood’s gradient can be approximated using samples from the model, generated using Markov Chain Monte Carlo (MCMC) techniques. However, a good approximation requires using very long chains and is thus impractical. This difficulty motivated the development of a plethora of more practical approaches, like score matching (Hyvärinen, 2005), noise contrastive estimation (NCE) (Gutmann & Hyvärinen, 2010), and conditional NCE (CNCE) (Ceylan & Gutmann, 2018), which replace the log-likelihood loss with objectives that do not require the computation of the normalization constant or its gradient.
Perhaps the most popular method for learning unnormalized models is contrastive divergence (CD) (Hinton, 2002). CD’s advantage over MLE stems from its use of short Markov chains initialized at the data samples. CD has been successfully used in a wide range of domains, including modeling images (Hinton et al., 2006), speech (Mohamed & Hinton, 2010), documents (Hinton & Salakhutdinov, 2009), and movie ratings (Salakhutdinov et al., 2007), and is continuing to attract significant research attention (Liu & Wang, 2017; Gao et al., 2018; Qiu et al., 2019).
Despite CD’s popularity and empirical success, there still remain open questions regarding its theoretical properties. The primary source of difficulty is an unjustified approximation used to derive its objective’s gradient, which biases its update steps (Carreira-Perpinan & Hinton, 2005; Bengio & Delalleau, 2009). The difficulty is exacerbated by the fact that CD’s update steps cannot be expressed as the gradients of any fixed objective (Tieleman, 2007; Sutskever & Tieleman, 2010).
In this paper, we present an alternative derivation of CD, which relies on completely different principles and requires no approximations. Specifically, we show that CD’s update steps are the gradients of an adversarial game in which a discriminator attempts to classify whether a Markov chain generated from the model is presented to it in its original or a time-reversed order (see Fig. 1). Thus, our derivation sheds new light on CD’s success: Similarly to modern generative adversarial methods (Goodfellow et al., 2014), CD’s discrimination task becomes more challenging as the model approaches the true distribution. This keeps the update steps effective throughout the entire training process and prevents early saturation as often happens in non-adaptive methods like NCE and CNCE. In fact, we derive CD as a natural extension of the CNCE method, replacing the fixed distribution of the contrastive examples with an adversarial adaptive distribution.
CD requires that the underlying MCMC be exact, which is not the case for popular methods like Langevin dynamics. This commonly requires using Metropolis-Hastings (MH) rejection, which ignores some of the generated samples. Interestingly, our derivation reveals an alternative correction method for inexact chains, which does not require rejection.

heading: 2 BACKGROUND

heading: 2.1 THE CLASSICAL DERIVATION OF CD
text: Assume we have an unnormalized distribution model pθ. Given a dataset of samples {xi} independently drawn from some unknown distribution p, CD attempts to determine the parameters θ with which pθ best explains the dataset. Rather than using the log-likelihood loss, CD’s objective involves distributions of samples along finite Markov chains initialized at {xi}. When based on chains of length k, the algorithm is usually referred to as CD-k.
Concretely, let qθ(x′|x) denote the transition rule of a Markov chain with stationary distribution pθ, and let rmθ denote the distribution of samples after m steps of the chain. As the Markov chain is initialized from the dataset distribution and converges to pθ, we have that r0θ = p and r ∞ θ = pθ. The CD algorithm then attempts to minimize the loss
`CD-k = DKL(r 0 θ ||r∞θ )−DKL(rkθ ||r∞θ )
= DKL(p||pθ)−DKL(rkθ ||pθ), (1)
where DKL is the Kullback-Leibler divergence. Under mild conditions on qθ (Cover & Halliwell, 1994) this loss is guaranteed to be positive, and it vanishes when pθ = p (in which case rkθ = pθ).
To allow the minimization of (1) using gradient-based methods, one can write
∇θ`CD-k =EX̃∼rkθ [∇θ log pθ(X̃)]− EX∼p[∇θ log pθ(X)] + dDKL(r
k θ ||pθ)
drkθ ∇θrkθ . (2)
Here, the first two terms can be approximated using two batches of samples, one drawn from p and one from rkθ . The third term is the derivative of the loss with respect only to the θ that appears in r k θ , ignoring the dependence of pθ on θ. This is the original notation from (Hinton, 2002); an alternative way to write this term would be ∇θ̃DKL(rkθ̃ ||pθ). This term turns out to be intractable and in the original derivation, it is argued to be small and thus neglected, leading to the approximation
∇θ`CD-k ≈ 1
n ∑ i (∇θ log pθ(x̃i)−∇θ log pθ(xi)) (3)
Here {xi} is a batch of n samples from the dataset and {x̃i} are n samples generated by applying k MCMC steps to each of the samples in that batch. The intuition behind the resulting algorithm (summarized in App. A) is therefore simple. In each gradient step θ ← θ− η∇θ`CD-k, the log-likelihood of samples from the dataset is increased on the expense of the log-likelihood of the contrastive samples {x̃i}, which are closer to the current learned distribution pθ. Despite the simple intuition, it has been shown that without the third term, CD’s update rule (2) generally cannot be the gradient of any fixed objective (Tieleman, 2007; Sutskever & Tieleman, 2010) except for some very specific cases. For example, Hyvärinen (2007) has shown that when the Markov chain is based on Langevin dynamics with a step size that approaches zero, the update rule of CD-1 coincides with that of score-matching Hyvärinen (2005). Similarly, the probability flow method of Sohl-Dickstein et al. (2011) has been shown to be equivalent to CD with a very unique Markov chain. Here, we show that regardless of the selection of the Markov chain, the update rule is in fact the exact gradient of a particular adversarial objective, which adapts to the current learned model in each step.

heading: 2.2 CONDITIONAL NOISE CONTRASTIVE ESTIMATION
text: Our derivation views CD as an extension of the CNCE method, which itself is an extension of NCE. We therefore start by briefly reviewing those two methods.
In NCE, the unsupervised density learning problem is transformed into a supervised one. This is done by training a discriminator Dθ(x) to distinguish between samples drawn from p and samples drawn from some preselected contrastive distribution pref. Specifically, let the random variable Y denote the label of the class from which the variable X has been drawn, so that X|(Y = 1) ∼ p and X|(Y = 0) ∼ pref. Then it is well known that the discriminator minimizing the binary cross-entropy (BCE) loss is given by
Dopt(x) = P(Y = 1|X = x) = p(x)
p(x) + pref(x) . (4)
Therefore, letting our parametric discriminator have the form
Dθ(x) = pθ(x)
pθ(x) + pref(x) , (5)
and training it with the BCE loss, should in theory lead to Dθ(x) = Dopt(x) and thus to pθ(x) = p(x). In practice, however, the convergence of NCE highly depends on the selection of pref. If it significantly deviates from p, then the two distributions can be easily discriminated even when the learned distribution pθ is still very far from p. At this point, the optimization essentially stops updating the model, which can result in a very inaccurate estimate for p. In the next section we provide a precise mathematical explanation for this behavior.
The CNCE method attempts to alleviate this problem by drawing the contrastive samples based on the dataset samples. Specifically, each dataset sample x is paired with a contrastive sample x̃ that is drawn conditioned on x from some predetermined conditional distribution q(x̃|x) (e.g. N (x, σ2I)). The pair is then concatenated in a random order, and a discriminator is trained to predict the correct
order. This is illustrated in Fig. 2a. Specifically, here the two classes are of pairs (A,B) corresponding to (A,B) = (X, X̃) for Y = 1, and (A,B) = (X̃,X) for Y = 0, and the discriminator minimizing the BCE loss is given by
Dopt(a, b) = P(Y = 1|A = a,B = b) = q(b|a)p(a)
q(b|a)p(a) + q(a|b)p(b) . (6)
Therefore, constructing a parametric discriminator of the form
Dθ(a, b) = q(b|a)pθ(a)
q(b|a)pθ(a) + q(a|b)pθ(b) =
( 1 +
q(a|b)pθ(b) q(b|a)pθ(a)
)−1 , (7)
and training it with the BCE loss, should lead to pθ ∝ p. Note that here Dθ is indifferent to a scaling of pθ, which is thus determined only up to an arbitrary multiplicative constant.
CNCE improves upon NCE, as it allows working with contrastive samples whose distribution is closer to p. However, it does not completely eliminate the problem, especially when p exhibits different scales of variation in different directions. This is the case, for example, with natural images, which are known to lie close to a low-dimensional manifold. Indeed if the conditional distribution q(·|·) is chosen to have a small variance, then CNCE fails to capture the global structure of p. And if q(·|·) is taken to have a large variance, then CNCE fails to capture the intricate features of p (see Fig. 3). The latter case can be easily understood in the context of images (see Fig. 2a). Here, the discriminator can easily distinguish which of its pair of input images is the noisy one, without having learned an accurate model for the distribution of natural images (e.g., simply by comparing their smoothness). When this point is reached, the optimization essentially stops.
In the next section we show that CD is in fact an adaptive version of CNCE, in which the contrastive distribution is constantly updated in order to keep the discrimination task hard. This explains why CD is less prone to early saturation than NCE and CNCE.

heading: 3 AN ALTERNATIVE DERIVATION OF CD
text: We now present our alternative derivation of CD. In Sec. 3.1 we identify a decomposition of the CNCE loss, which reveals the term that is responsible for early saturation. In Sec. 3.2, we then present a method for adapting the contrastive distribution in a way that provably keeps this term bounded away from zero. Surprisingly, the resulting update step turns out to precisely match that of CD-1, thus providing a new perspective on CD learning. In Sec. 3.3, we extend our derivation to include CD-k (with k ≥ 1).

heading: 3.1 REINTERPRETING CNCE
text: Let us denote
wθ(a, b) , q(a|b)pθ(b) q(b|a)pθ(a) , (8)
so that we can write CNCE’s discriminator (7) as
Dθ(a, b) = (1 + wθ(a, b)) −1 . (9)
Then we have the following observation (see proof in App. B).
Observation 1. The gradient of the CNCE loss can be expressed as
∇θ`CNCE = E X∼p X̃|X∼q
[ αθ(X, X̃) ( ∇θ log pθ(X̃)−∇θ log pθ(X) )] , (10)
where αθ(x, x̃) , (1 + wθ(x, x̃) −1)−1. (11)
Note that (10) is similar in nature to the (approximate) gradient of the CD loss (3). Particularly, as in CD, the term∇θ log pθ(X̃)−∇θ log pθ(X) causes each gradient step to increase the log-likelihood of samples from the dataset on the expense of the log-likelihood of the contrastive samples. However, as opposed to CD, here we also have the coefficient αθ(x, x̃), which assigns a weight between 0 and 1 to each pair of samples (x, x̃). To understand its effect, observe that
αθ(x, x̃) = 1−Dθ(x, x̃) = Dθ(x̃, x). (12)
Namely, this coefficient is precisely the probability that the discriminator assigns to the incorrect order of the pair. Therefore, this term gives a low weight to “easy” pairs (i.e., for which Dθ(x, x̃) is close to 1) and a high weight to “hard” ones.
This weighting coefficient is of course essential for ensuring convergence to p. For example, it prevents log pθ from diverging to ±∞ when the discriminator is presented with the same samples over and over again. The problem is that a discriminator can often correctly discriminate all training pairs, even with a pθ that is still far from p. In such cases, αθ becomes practically zero for all pairs and the model stops updating. This shows that a good contrastive distribution is one which keeps the discrimination task hard throughout the training. As we show next, there is a particular choice which provably prevents αθ from converging to zero, and that choice results in the CD method.
3.2 FROM CNCE TO CD-1
To bound αθ away from 0, and thus avoid the early stopping of the training process, we now extend the original CNCE algorithm by allowing the conditional distribution q to depend on pθ (and thus to change from one step to the next). Our next key observation is that in this setting there exists a particular choice that keeps αθ constant. Observation 2. If q is chosen to be the transition probability of a reversible Markov chain with stationary distribution pθ, then
αθ(x, x̃) = 1
2 , ∀x, x̃. (13)
Proof. A reversible chain with transition q and stationary distribution pθ, satisfies the detailed balance property q(x̃|x)pθ(x) = q(x|x̃)pθ(x̃), ∀x, x̃. (14) Substituting (14) into (8) leads to wθ(x, x̃) = 1, which from (11) implies αθ(x, x̃) = 12 .
This observation directly links CNCE to CD. First, the suggested method for generating the contrastive samples is precisely the one used in CD-1. Second, as this choice of q leads to αθ(x, x̃) = 12 , it causes the gradient of the CNCE loss (10) to become
∇θ`CNCE = 12E X∼p X̃|X∼q
[ ∇θ log pθ(X̃)−∇θ log pθ(X) ] , (15)
which is exactly proportional to the CD-1 update (3). We have thus obtained an alternative derivation of CD-1. Namely, rather than viewing CD-1 learning as an approximate gradient descent process for the loss (1), we can view each step as the exact gradient of the CNCE discrimination loss, where the reference distribution q is adapted to the current learned model pθ. This is illustrated in Fig. 2b.
Since q is chosen based on pθ, the overall process is in fact an adversarial game. Namely, the optimization alternates between updating q, which acts as a generator, and updating pθ, which defines the discriminator. As pθ approaches p, the distribution of samples generated from the MCMC also becomes closer to p, which makes the discriminator’s task harder and thus prevents early saturation.
It should be noted that formally, since q depends on pθ, it also indirectly depends on θ, so that a more appropriate notation would be qθ. However, during the update of pθ we fix qθ (and vise versa), so that the gradient in the discriminator update does not consider the dependence of qθ on θ. This is why (15) does not involve the gradient of X̃ which depends on qθ.
The reason for fixing qθ comes from the adversarial nature of the learning process. Being part of the chain generation process, the goal of the transition rule qθ is to generate chains that appear to be timereversible, while the goal of the classifier, which is based on the model pθ, is to correctly classify
whether the chains were reversed. Therefore, we do not want the optimization of the classifier to affect qθ. This is just like in GANs, where the generator and discriminator have different objectives, and so when updating the discriminator the generator is kept fixed.
3.3 FROM CD-1 TO CD-k
To extend our derivation to CD-k with an arbitrary k ≥ 1, let us now view the discrimination problem of the previous section as a special case of a more general setting. Specifically, the pairs of samples presented to the discriminator in Sec. 3.2, can be viewed as Markov chains of length two (comprising the initial sample from the dataset and one extra generated sample). It is therefore natural to consider also Markov chains of arbitrary lengths. That is, assume we initialize the MCMC at a sample xi from the dataset and run it for k steps to obtain a sequence (x(0), x(1), . . . , x(k)), where x(0) = xi. We can then present this sequence to a discriminator either in its original order, or time-reversed, and train the discriminator to classify the correct order. We coin this a time-reversal classification task. Interestingly, in this setting, we have the following. Observation 3. When using a reversible Markov chain of length k + 1 with stationary distribution pθ, the gradient of the BCE loss of the time-reversal classification task is given by
∇θ`CNCE = 12E [ ∇θ log pθ(X(k))−∇θ log pθ(X(0)) ] , (16)
which is exactly identical to the CD-k update (3) up to a multiplicative factor of 12 .
This constitutes an alternative interpretation of CD-k. That is, CD-k can be viewed as a time-reversal adversarial game, where in each step, the model pθ is updated so as to allow the discriminator to better distinguish MCMC chains from their time-reversed counterparts.
Two remarks are in order. First, it is interesting to note that although the discriminator’s task is to classify the order of the whole chain, its optimal strategy is to examine only the endpoints of the chain, x(0) and x(k). Second, it is insightful to recall that the original motivation behind the CD-k loss (1) was that when pθ equals p, the marginal probability of each individual step in the chain is also p. Our derivation, however, requires more than that. To make the chain indistinguishable from its time-reversed version, the joint probability of all samples in the chain must be invariant to a flip of the order. When pθ = p, this is indeed the case, due to the detailed balance property (14).
Proof of Observation 3. We provide the outline of the proof (see full derivation in App. C). Let (A(0), A(1), . . . , A(k)) denote the input to the discriminator and let Y indicate the order of the chain, with Y = 1 corresponding to (A(0), A(1), . . . , A(k)) = (X(0), X(1), . . . , X(k)) and Y = 0 to (A(0), A(1), . . . , A(k)) = (X(k), X(k−1), . . . , X(0)). The discriminator that minimizes the BCE loss is now given by
D(a0, a1, . . . , ak) = P(Y = 1|A(0) = a0, A(1) = a1, . . . , A(k) = ak)
= ( 1 +
q(a0|a1) · · · q(ak−1|ak)p(ak) q(ak|ak−1) · · · q(a1|a0)p(a0) )−1 = ( 1 +
k∏ i=1 wθ(ai−1, ai)
)−1 . (17)
The CNCE paradigm thus defines a discriminator Dθ having the form of (17) but with p replaced by pθ. Recall that despite the dependence of the transition probability q on the current learned model pθ, it is regarded as fixed within each discriminator update step. We therefore omit the subscript θ from q here. Similarly to the derivation of (10), explicitly writing the gradient of the BCE loss of our discriminatrion task, gives
∇θ`chain = E (1 + k∏ i=1 wθ(X (i−1), X(i))−1 )−1 ( ∇θ log pθ(X(k))−∇θ log pθ(X(0)) ) = E [ αθ(X (0), . . . , X(k)) ( ∇θ log pθ(X(k))−∇θ log pθ(X(0)) )] . (18)
where we now defined
αθ(a0, . . . , ak) ,
( 1 +
k∏ i=1 wθ(ai−1, ai) −1
)−1 . (19)
Note that (10) is a special case of (18) corresponding to k = 1, where X and X̃ in (10) are X(0) and X(1) in (18). As before, when q satisfies the detailed balance property (14), we obtain wθ = 1 and consequently the weighting term αθ again equals 12 . Thus, the gradient (18) reduces to (16), which is exactly proportional to the CD-k update (3).

heading: 3.4 MCMC PROCESSES THAT DO NOT HAVE DETAILED BALANCE
text: In our derivation, we assumed that the MCMC process is reversible, and thus exactly satisfies the detailed balance property (14). This assumption ensured that wθ = 1 and thus αθ = 12 . In practice, however, commonly used MCMC methods satisfy this property only approximately. For example, the popular discrete Langevin dynamics process obeys detailed balance only in the limit where the step size approaches zero. The common approach to overcome this is through Metropolis-Hastings (MH) rejection (Hastings, 1970), which guarantees detailed balance by accepting only a portion of the proposed MCMC transitions. In this approach, the probability of accepting a transition from x to x̃ is closely related to the weighing term wθ, and is given by
A(x, x̃) = min (1, wθ(x, x̃)) . (20)
Interestingly, our derivation reveals an alternative method for accounting for lack of detailed balance.
Concretely, we saw that the general expression for the gradient of the BCE loss (before assuming detailed balance) is given by (18). This expression differs from the original update step of CD-k only in the weighting term αθ(x(0), . . . , x(k)). Therefore, all that is required for maintaining correctness in the absence of detailed balance, is to weigh each chain by its “hardness” αθ(x(0), . . . , x(k)) (see Alg. 2 in App. A). Note that in this case, the update depends not only on the end-points of the chains, but rather also on their intermediate steps. As can be seen in Fig. 4, this method performs just as well as MH, and significantly better than vanilla CD without correction.

heading: 4 ILLUSTRATION THROUGH A TOY EXAMPLE
text: To illustrate our observations, we now conclude with a simple toy example (see Fig. 3). Our goal here is not to draw general conclusions regarding the performance of CNCE and CD, but rather merely to highlight the adversarial nature of CD and its importance when the data density exhibits different scales of variation along different directions.
We take data concentrated around a 2-dimensional manifold embedded in 10-dimensional space. Specifically, let e(1), . . . , e(10) denote the standard basis in R10. Then each data sample is generated by adding Gaussian noise to a random point along a 2D spiral lying in the e(1)-e(2) plane. The STD of the noise in the e(1) and e(2) directions is 5 times larger than that in the other 8 axes. Figure 3a shows the projections of the the data samples onto the the first 3 dimensions. Here, we use a
multi-layer perceptron (MLP) as our parametric model, log pθ, and train it using several different learning configurations (for the full details see App. D).
Figure 3b visualizes the training as well as the final result achieved by each configuration. The first two rows show CNCE with Gaussian contrastive distributions of two different STDs. The third row shows the adjusted CD described in Sec. 3.4 with Langevin Dynamics as its MCMC process. As can be seen, for CNCE with a large STD, the contrastive samples are able to explore large areas around the original samples, but this causes their majority to lie relatively far from the manifold (see their projections onto the e(1)-e(3) plane). In this case, αθ decreases quickly, causing the learning process to ignore most samples at a very early stage of the training. When using CNCE with a small STD, the samples remain relevant throughout the training, but this comes at the price of inability to capture the global structure of the distribution. CD, on the other hand, is able to enjoy the best of both worlds as it adapts the contrastive distribution over time. Indeed, as the learning progresses, the contrastive samples move closer to the manifold to maintain their relevance. Note that since we use the adjusted version of CD, the weights in this configuration are not precisely 1. We chose the step size of the Langevin Dynamics so that the median of the weights is approximately 10−2.
Figure 4 shows the results achieved by different variants of CD. As can be seen, without correcting for the lack of detailed balance, CD fails to estimate the density correctly. When using MH rejection to correct the MCMC, or our adaptive CD (ADC) to correct the update steps, the estimate is significantly improved.

heading: 5 CONCLUSION
text: The classical CD method has seen many uses and theoretical analyses over the years. The original derivation presented the algorithm as an approximate gradient descent process for a certain loss. However, the accuracy of the approximation has been a matter of much dispute, leaving it unclear what objective the algorithm minimizes in practice. Here, we presented an alternative derivation of CD’s update steps, which involves no approximations. Our analysis shows that CD is in essence an adversarial learning procedure, where a discriminator is trained to distinguish whether a Markov chain generated from the learned model has been time-flipped or not. Therefore, although predating GANs by more than a decade, CD in fact belongs to the same family of techniques. This provides a possible explanation for its empirical success.
Acknowledgement This research was supported by the Technion Ollendorff Minerva Center.

heading: A ALGORITHMS
text: Below we summarize the algorithms of the classical CD and the proposed adjusted version described in Sec. 3.4.
Algorithm 1: Contrastive Divergence - k Require: parametric model pθ, MCMC transition rule qθ(·|·) with stationary distribution pθ, step size η, chain length k. while not converged do Sample a batch {xi}ni=1 from the dataset Initialize {x̃i}ni=1 to be a copy of the batch for i=1 to n do
for j=1 to k do Draw a sample x′ from qθ(·|x̃i) x̃i ← x′ end gi ← ∇θ log pθ(x̃i)−∇θ log pθ(xi)
end θ ← θ − η 1n ∑ i gi
end
Algorithm 2: Adjusted Contrastive Divergence - k Require: parametric model pθ, MCMC transition rule qθ(·|·) whose stationary distribution is pθ, step size η, chain length k. while not converged do Sample a batch {xi}ni=1 from the dataset Initialize {x̃i}ni=1 to be a copy of the batch for i=1 to n do
wtoti ← 1 for j=1 to k do
Draw a sample x′ from qθ(·|x̃i) wtoti ← wtoti · q(xi|x′)pθ(x′) q(x′|xi)pθ(xi)
x̃i ← x′ end αi ← (1 + 1/wtoti )−1 gi ← ∇θ log pθ(x̃i)−∇θ log pθ(xi)
end θ ← θ − η 1n ∑ i αi · gi
end

heading: B DERIVATION OF CNCE’S GRADIENT
text: Proof of Observation 1. The BCE loss achieved by the CNCE discriminator (7) is given by
`CNCE = − 12E A∼p B|A∼q [log(Dθ(A,B))]− 12E B∼p A|B∼q [log(1−Dθ(A,B))] =
= −E X∼p X̃|X∼q
[ log(Dθ(X, X̃)) ] , (21)
where we used the fact that 1 −Dθ(a, b) = Dθ(b, a). Now, substituting the definition of Dθ form (9), the gradient of (21) can be expressed as
∇θ`CNCE = E X∼p X̃|X∼q
[ ∇θ log ( 1 + wθ(X, X̃) )] = E X∼p
X̃|X∼q
[( 1 + wθ(X, X̃) )−1 ∇θwθ(X, X̃) ]
= E X∼p X̃|X∼q
[( 1 + wθ(X, X̃) )−1 wθ(X, X̃) wθ(X, X̃) ∇θwθ(X, X̃) ]
= E X∼p X̃|X∼q (1 + wθ(X, X̃) wθ(X, X̃) )−1 ∇θwθ(X, X̃) wθ(X, X̃)  = E X∼p
X̃|X∼q
[( 1 + wθ(X, X̃) −1 )−1 ∇θ log(wθ(X, X̃)) ] = E X∼p
X̃|X∼q
[ αθ(X, X̃) ( ∇θ log pθ(X̃)−∇θ log pθ(X) )] , (22)
where we used the fact that∇θwθ = wθ∇θ log(wθ) and the definition of αθ from (11).

heading: C DERIVATION OF THE GRADIENT OF CNCE WITH MULTIPLE MC STEPS
text: We here describe the full derivation of the gradient in (18) following the same steps as in (22). The BCE loss achieved by the discriminator in (17) is given by
`chain = −E [ log(Dθ(X (0), X(1), . . . , X(k))) ] . (23)
where we again used the fact that 1−Dθ(a0, a1, . . . , ak) = Dθ(ak, ak−1, . . . , a0). Now, substituting the definition of Dθ form (17), the gradient of (23) can be expressed as
∇θ`chain = E [ ∇θ log ( 1 +
k∏ i=1 wθ(X (i−1), X(i))
)]
= E (1 + k∏ i=1 wθ(X (i−1), X(i)) )−1 ∇θ ( k∏ i=1 wθ(X (i−1), X(i)) ) = E
(1 +∏ki=1 wθ(X(i−1), X(i))∏k i=1 wθ(X (i−1), X(i)) )−1 ∇θ (∏ki=1 wθ(X(i−1), X(i)))∏k i=1 wθ(X (i−1), X(i))  = E
(1 + k∏ i=1 wθ(X (i−1), X(i))−1 )−1 ∇θ log ( k∏ i=1 wθ(X (i−1), X(i)) ) = E [ αθ(X (0), . . . , X(k)) ( ∇θ log pθ(X(k))−∇θ log pθ(X(0)) )] , (24)
where we used the definition of αθ from (19).

heading: D TOY EXPERIMENT AND TRAINING DETAILS
text: We here describe the full details of the toy model and learning configuration, which we used to produce the results in the paper. The code for reproducing the results is available at —- (for the blind review the code will be available in the supplementary material).
The toy model used in the paper consists of a distribution concentrated around a 2D spiral embedded in a 10 dimensional space. Denoting the 10 orthogonal axes of the standard basis in this space by
e(1), . . . , e(10), the spiral lies in the e(1)-e(2) plane and is confined to [−1, 1] in each of these two axes. The samples of the model are produced by selecting random points along the spiral and adding Gaussian noise to them. In order to keep the samples close to the e(1)-e(2) plane we used a nonisotropic noise with an STD of 0.05 in the e(1) and e(2) directions, and an STD of 0.01 in the directions e(3), . . . , e(10).
As a parametric model for log pθ(x), we used an 8-layer multi-layer perceptron (MLP) of width 512 with skip connections, as illustrated in Fig. 5.
Throughout the paper we referred to the results of five different learning configurations.
1. CNCE with an optimal (small) variance. This configuration uses additive Gaussian noise as its contrastive distribution. We found 0.0075 to be the STD of the Gaussian which produces the best results.
2. CNCE with a large variance. This configuration is similar to the previous one except for the STD of the Gaussian which was set to 0.3 in order to illustrate the problems of using a conditional distribution with a large variance.
3. CD without any MCMC correction. For the MCMC process we used 5 steps of Langevin dynamics, where we did not employ any correction for the inaccuracy which results from using Langavin dynamics with a finite step size. We found 0.0075 to be the step size (multiplying the standard Gaussian noise term) which produces the best results.
4. CD with MH correction. This configuration is similar to the previous one except for a MH rejection scheme which was used during the MCMC sampling. In this case we found the step size of 0.0125 to produce the best results.
5. Adjusted CD. This configuration is similar to the previous one except that we used the method from Sec. 3.4 instead of MH rejection. Similarly to the previous configuration, we found the step size of 0.0125 to produce the best results.
The optimization of all configurations was preformed using SGD with a momentum of 0.9 and an exponential decaying learning rate. Except for the training of the third configuration, the learning rate ran down from 10−2 to 10−4 over 100000 optimization steps. For the third configuration we had to reduce the learning rate by a factor of 10 in order to prevent the optimization from diverging.
In order to select the best step size / variance for each of the configurations we ran a parameter sweep around the relevant value range. The results of this sweep are shown in Fig. 6.
For the selection of the number of training steps, we have iteratively increased the number of steps until the results stopped improving for all configurations. These results are presented in Fig. 7.

Review summaries:
This paper presents a way to view contrastive divergence (CD) learning as an adversarial learning procedure where a discriminator is tasked with classifying whether or not a Markov chain, generated from the model, has been time-reversed. Beginning with the classic derivation of CD and its approximate gradient, noting relevant issues regarding this approximation, the authors present a way to view CD as an extension of the conditional noise contrastive estimation (CNCE) method where the contrastive distribution is continually updated to keep the discrimination task difficult. Specifically, when the contrastive distribution is chosen such that the detailed balance property is satisfied, then the CNCE loss becomes exactly proportional the CD-1 update with the derivation further extended to CD-k. Practical concerns regarding lack of detailed balance are mitigated through the use of Metropolis-Hastings rejection or an adaptive weighting that arises when deriving the gradient of their time-reversal classification loss.  A toy example providing empirical support for correcting the lack of detailed balance is included.

To implement the contrastive divergence (CD) algorithm in practice, an intractable term is typically omitted from the gradient. This leads to an approximation. This work shows that the resulting algorithm can in fact be viewed as an exact algorithm targeting a different, adversarial objective. The derivation in this paper also shows how Markov chains which are not reversible w.r.t. the posterior distribution of interest can be employed within the algorithm. Effectively, this assigns an importance weight to each sample which akin to the acceptance ratio which would be needed for a Metropolis--Hastings type correction.