# Convergence Analysis of Contrastive Divergence Algorithm Based on Gradient Method with Errors

Authors: Xuesi Ma; Xiaojie Wang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Contrastive Divergence has become a common way to train Restricted Boltzmann Machines; however, its convergence has
not been made clear yet. This paper studies the convergence of Contrastive Divergence algorithm. We relate Contrastive
Divergence algorithm to gradient method with errors and derive convergence conditions of Contrastive Divergence algorithm
using the convergence theorem of gradient method with errors. We give specific convergence conditions of Contrastive
Divergence learning algorithm for Restricted Boltzmann Machines in which both visible units and hidden units can only take
a finite number of values. Two new convergence conditions are obtained by specifying the learning rate. Finally, we give
specific conditions that the step number of Gibbs sampling must be satisfied in order to guarantee the Contrastive Divergence
algorithm convergence.


---

## Body

## 1. Introduction

Deep belief networks have recently been successfully applied to resolve many problems [1–5]. Restricted Boltzmann Machines (RBMs), one of important blocks of deep belief networks, have also been widely applied in many fields [2, 6–11]. The learning of RBMs and deep belief network has been an important and hot topic in machine learning research. The learning process is a parameters estimating problem. The general parameters estimating method is challenging, Hinton proposed Contrastive Divergence (CD) learning algorithm [12]. Although it has been widely used for training deep belief networks, its convergence is still not clear. Recently, more and more researchers have studied theoretical characters of CD. Bengio and Delalleau [13] proved the use of a short Gibbs chain of length k to obtain a biased estimator of the log-likelihood gradient. Akoho and Takabatake [14] gave an information geometrical interpretation of the CD learning algorithm. Sutskever and Tieleman [15] gave proofs showing CD is not the gradient of any function. It is possible to construct regularization functions that cause it to fail to converge. Yuille [16] related CD to the stochastic approximation literature and derived elementary conditions which ensure convergence (with probability 1). However, convergence conditions are relatively strict; particularly, convergence conditions are related to the model parameter which minimize the Kullback-Leibler divergence D
(
P
0
(
x
)
∥
P
(
x
∣
w
)
) between the empirical distribution function of the observed data P
0
(
x
) and the model P
(
x
∣
w
).In this paper, we study the convergence of the CD learning algorithm. By exploring the relation between the CD algorithm and the gradient method with errors, we obtain convergence conditions of CD using the convergence theorem of gradient method with errors. Our convergence conditions are more practical than those given by Yuille [16]. We also give an analysis of convergence of the CD algorithm for RBMs, especially the convergence conditions of the CD algorithm for RBMs in which both visible units and hidden units only take a finite number of values. We give two new convergence conditions by specifying the learning rate. Finally, we give the theoretical analysis of convergence conditions of the CD algorithm for RBMs and the relationship which the learning rate and the step number of Gibbs sampling must satisfy in order to guarantee the CD algorithm convergence.The rest of the paper is organized as follows. In Section2, we give a brief overview of the CD algorithm. In Section 3, we firstly propose the gradient method with errors and convergence theorem of the gradient method with errors and then relate the CD algorithm to the gradient method with errors. Convergence conditions of the CD algorithm are derived. In Section 4, we give an analysis of convergence conditions of the CD algorithm for RBMs. We draw some conclusions in Section 5.


## 2. Contrastive Divergence Learning Algorithm

Given a probability distribution over a vectorx, (1)
p
x
,
h
;
w
=
1
Z
w
e
-
E
x
,
h
;
w
,where Z
(
w
)
=
∑
x
,
h
‍
e
-
E
(
x
,
h
;
w
) is a normalization constant or partition function, h is hidden variable, and E
(
x
,
h
;
w
) is an energy function. This class of random-field distribution has been used in many fields.The marginal likelihood is(2)
p
x
;
w
=
1
Z
w
∑
h
e
-
E
x
,
h
;
w
.The gradient of the marginal log-likelihood with respect to model parameterw is(3)
∂
log
⁡
p
x
;
w
∂
w
=
-
∑
h
p
h
;
w
∣
x
∂
E
x
,
h
;
w
∂
w
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
∂
E
x
~
,
h
~
;
w
∂
w
.The log-likelihood gradient algorithm can be expressed as(4)
w
t
+
1
-
w
t
=
γ
t
-
∑
h
p
h
;
w
t
∣
x
∂
E
x
,
h
;
w
t
∂
w
t
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
,where γ
t denotes the learning rate at tth update.The first term in the bracket of the right hand of (4) can be computed exactly; however, the second term (also called the expectation under the model distribution) is intractable because the calculation of Z
(
w
) is extremely difficult. In order to apply the log-likelihood gradient algorithm, we have to do alternating blocked-Gibbs sampling from the conditionals p
(
x
;
w
∣
h
) and p
(
h
;
w
∣
x
). This requires an infinite number of Gibbs transitions per update to fully characterize the expectation. Hinton [12] proposed a modification of the log-likelihood gradient algorithm known as Contrastive Divergence.The idea ofk-step Contrastive Divergence learning (CD-k) is simple: instead of approximating the second term in the log-likelihood gradient by a sample for RBM-distribution (which would require running a Markov chain until the stationary distribution is reached), a Gibbs chain is run for only k steps. The Gibbs is initialized with a training example x
(
0
) of the training set and yields the sample x
(
k
) after k steps. Each step t consists of sampling h
(
t
) from p
(
h
;
w
∣
x
(
t
)
) and subsequently sampling x
(
t
+
1
) from p
(
x
;
w
∣
h
(
t
)
). The gradient (3) with w of log-likelihood for one training example x
(
0
) is approximated by (5)
C
D
k
w
,
x
0
=
-
∑
h
p
h
;
w
∣
x
0
∂
E
x
0
,
h
;
w
∂
w
+
∑
h
p
h
;
w
∣
x
k
∂
E
x
k
,
h
;
w
∂
w
.The expectation of the CD algorithm can be ascribed by (6)
E
C
D
k
w
,
x
0
=
-
∑
h
p
h
;
w
∣
x
0
∂
E
x
0
,
h
;
w
∂
w
+
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
∂
E
x
~
,
h
~
;
w
∂
w
,where p
k
(
x
~
,
h
~
;
w
) is the empirical distribution function on the samples obtained by the data x
(
0
) and running the Markov chain forward for k steps, p
k
(
x
~
,
h
~
;
w
)
=
p
(
x
(
k
)
=
x
~
,
h
(
k
)
=
h
~
).The asymptotic unbiased estimator of the parameters can be obtained by using the log-likelihood gradient algorithm; asymptotic property of the estimator of the parameters in CD-k learning is discussed in the next section.


## 3. Convergence of Contrastive Divergence Algorithm

In this section, we will study the convergence of the CD learning algorithm. The CD algorithm has a similar form with the gradient method with errors. We try to relate the CD algorithm to the gradient method with errors and derive the convergence conditions of CD. For achieving it, we firstly propose the gradient method with errors and give the convergence theorem of the gradient method with errors.


### 3.1. Gradient Methods with Errors and Convergence Theorem

Given the optimization problem,(7)
m
i
n
f
w
,
w
∈
R
n
,where R
n denotes the n-dimensional Euclidean space and f
(
w
)
:
R
n
→
R is a continuously differentiable function, such that for a positive constant L we have (8)
∇
f
w
-
∇
f
w
-
≤
L
w
-
w
-
∀
w
,
w
-
∈
R
n
,where w
=
(
∑
i
=
1
n
‍
w
i
2
)
1
/
2, · stands for the Euclidean norm in R
n.The gradient method with errors is of the following form:(9)
w
t
+
1
=
w
t
+
γ
t
s
t
+
v
t
,where γ
t is a positive step-size sequence, s
t is a descent direction, and v
t is an error.The errorv
t could be deterministic or stochastic. In both cases, the gradient method has been studied in literature [17–20]. We consider that v
t is stochastic because of the CD algorithm in this paper. The gradient method with stochastic errors can be considered as stochastic approximation algorithm or stochastic approximation procedure [21, 22]. Younes [22] has analyzed the convergence of stochastic approximation procedure (SAP) and has given the almost sure convergence conditions of SAP using ODE (Ordinary Differential Equations) approach. He generated a persistent Markov chain and studied the recursion algorithm in which several iterations of the simulation procedures are performed before updating the current parameter, with the updating being done using the average of the obtained values. Bertsekas and Tsitsiklis [18] have studied the convergence of gradient method, in which the expectation of the stochastic error v
t is zero with probability 1. We present a gradient method with different stochastic errors; convergence of the gradient method is guaranteed by the following theorem. We will need a known lemma, which has been proved by Grimmett and Stirzaker [23].Lemma 1.
LetX
t
,
Y
t and Z
t be three nonnegative random variables such that ∑
t
=
0
∞
‍
Y
t
<
∞ with probability 1 and E
t
[
X
t
+
1
]
≤
X
t
+
Y
t
-
Z
t for all t; then, X
t converges with probability 1 and ∑
t
=
0
∞
‍
Z
t
<
∞.Theorem 2.
Letw
t be a sequence generated by the method(10)
w
t
+
1
=
w
t
+
γ
t
s
t
+
v
t
,where γ
t is a positive step size, s
t is a descent direction, and v
t is a stochastic error. Let F
t be an increasing sequence of σ-fields (F
t should be interpreted as the history of the algorithm up to time t). We assume the following:(1)
f
(
w
)
≥
0
,
w
∈
R
n
,
f
(
w
t
), and s
t are F
t-measurable.
(2)
There exist positive scalarsc
1 and c
2 such that(11)
c
1
f
w
t
2
≤
-
∇
f
w
t
T
s
t
,
s
t
≤
c
2
1
+
∇
f
w
t
.
(3)
We have, for allt, and with probability 1, (12)
E
v
t
∣
F
t
≤
γ
t
q
+
p
∇
f
w
t
,
E
v
t
2
∣
F
t
≤
A
1
+
∇
f
w
t
2
,where p
,
q and A are constants, p
≥
0
,
q
≥
0
,
A
≥
0.
(4)
We have(13)
∑
t
=
0
∞
γ
t
=
∞
,
∑
t
=
0
∞
γ
t
2
<
∞
.Then, f
(
w
t
) converges.Proof.
With fixed two vectorsw and z, let ξ be a scalar parameter, and let g
(
ξ
)
=
f
(
w
+
ξ
z
). The chain rule yields (
d
g
/
d
ξ
)
(
ξ
)
=
z
T
∇
f
(
w
+
ξ
z
). We have (14)
f
w
+
z
-
f
w
=
g
1
-
g
0
=
∫
0
1
d
g
d
ξ
ξ
d
ξ
=
∫
0
1
z
T
∇
f
w
+
ξ
z
d
ξ
≤
z
T
∇
f
w
+
∫
0
1
z
T
∇
f
w
+
ξ
z
-
z
T
∇
f
w
d
ξ
≤
z
T
∇
f
w
+
z
∫
0
1
L
ξ
z
d
ξ
=
z
T
∇
f
w
+
L
2
z
2
.We apply (14) with w
=
w
t and z
=
γ
t
(
s
t
+
v
t
). We obtain (15)
f
w
t
+
1
≤
f
w
t
+
γ
t
∇
f
w
t
T
s
t
+
v
t
+
γ
t
2
L
2
s
t
+
v
t
2
.Using our assumptions, the relations s
t
2
≤
2
c
2
2
(
1
+
∇
f
(
w
t
)
2
) and s
t
+
v
t
2
≤
2
(
s
t
2
+
v
t
2
), we have (16)
f
w
t
+
1
≤
f
w
t
-
c
1
γ
t
∇
f
w
t
2
+
γ
t
∇
f
w
t
T
v
t
+
2
c
2
2
γ
t
2
L
1
+
∇
f
w
t
2
+
γ
t
2
L
v
t
2
.Taking conditional expectations with respect to F
t and using conditions (
3
) and the relation ∇
f
(
w
t
)
≤
1
+
∇
f
(
w
t
)
2, we have(17)
E
f
w
t
+
1
∣
F
t
≤
E
f
w
t
∣
F
t
-
c
1
γ
t
∇
f
w
t
2
+
γ
t
∇
f
w
t
·
E
v
t
∣
F
t
+
2
c
2
2
γ
t
2
L
1
+
∇
f
w
t
2
+
γ
t
2
L
E
v
t
2
∣
F
t
≤
E
f
w
t
∣
F
t
-
c
1
γ
t
∇
f
w
t
2
+
γ
t
2
q
∇
f
w
t
+
γ
t
2
p
∇
f
w
t
2
+
2
c
2
2
γ
t
2
L
+
2
c
2
2
γ
t
2
L
∇
f
w
t
2
+
γ
t
2
L
A
1
+
∇
f
w
t
2
≤
E
f
w
t
∣
F
t
-
γ
t
c
1
-
q
γ
t
-
p
γ
t
-
2
γ
t
c
2
2
L
-
γ
t
L
A
∇
f
w
t
2
+
γ
t
2
q
+
2
c
2
2
L
+
L
A
,which for sufficiently large t can be written as(18)
E
f
w
t
+
1
∣
F
t
≤
E
f
w
t
∣
F
t
-
γ
t
β
1
∇
f
w
t
2
+
γ
t
2
β
2
,where β
1 and β
2 are positive scalars.
Using the assumption thatf
(
w
t
) is F
t-measurable, we have (19)
E
f
F
t
w
t
+
1
≤
f
w
t
-
γ
t
β
1
∇
f
w
t
2
+
γ
t
2
β
2
.By using Lemma 1 and the assumption ∑
t
=
0
∞
‍
γ
t
2
<
∞, we see that f
(
w
t
) converges.
The theorem is proved.Strictly speaking, the conclusion of the theorem only holds with probability 1. For simplicity, an explicit statement of this qualification often will be omitted. We will use the theorem to derive convergence conditions of CD based on the similarity between the CD algorithm and the gradient method with errors.


### 3.2. Convergence of CD

In order to derive convergence conditions of the CD learning algorithm using the convergence theorem of the gradient method with errors, we have to explore the relation between the CD algorithm and the gradient method with errors. We can reconstruct the CD algorithm in the form of gradient optimization problem.The theorem of the gradient method with errors involves four basic concepts. The first is an optimization functionf
(
w
), which must be a continuously differentiable function, such that, for some constant L, we have ∇
f
(
w
)
-
∇
f
(
w
-
)
≤
L
w
-
w
-. The second is the descent direction s
t. The third is the error vector v
t. The last concept is the step size γ
t; γ
t can be considered as the learning rate in the CD learning algorithm. The gradient method with errors will converge provided the conditions of Theorem 2 are satisfied.We firstly design an optimal function for CD. Let(20)
f
w
=
-
log
⁡
p
x
;
w
.We can derive convergence theorem for the CD learning algorithm through selecting appropriate s
t and v
t. Next, we give the convergence theorem of the CD learning algorithm using the convergence theorem of the gradient method with errors.Theorem 3.
The CD learning algorithm will converge providing(1)
∇
f
(
w
)
-
∇
f
(
w
-
)
≤
L
w
-
w
-
,
w
,
w
-
∈
R
n, where L is a positive constant,
(2)
∑
t
=
0
∞
‍
γ
t
=
∞
,
∑
t
=
0
∞
‍
γ
t
2
<
∞,
(3)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
)
≤
c
γ
t, where c is a positive constant and ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is bounded.Proof.
The CD algorithm can be described as the form of gradient optimization problem. The CD algorithm is(21)
w
t
+
1
=
w
t
+
γ
t
-
∑
h
p
h
;
w
t
∣
x
0
∂
E
x
0
,
h
;
w
t
∂
w
t
+
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
k
,
h
;
w
t
∂
w
t
.In (21), let (22)
-
∑
h
p
h
;
w
t
∣
x
0
∂
E
x
0
,
h
;
w
t
∂
w
t
+
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
k
,
h
;
w
t
∂
w
t
=
s
t
+
v
t
.The CD algorithm in the form of gradient optimization problem can be described as follows: (23)
w
t
+
1
=
w
t
+
γ
t
s
t
+
v
t
.In (23), let (24)
s
t
=
-
∇
f
w
t
=
-
∑
h
p
h
;
w
t
∣
x
0
∂
E
x
0
,
h
;
w
t
∂
w
t
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
,
(25)
v
t
=
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
k
,
h
;
w
t
∂
w
t
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
.Then, (23) can be considered as the gradient method with errors.
Sinces
t
=
-
∇
f
(
w
t
), then we have (26)
-
∇
f
w
t
T
s
t
=
∇
f
w
t
T
∇
f
w
t
=
∇
f
w
t
2
.Therefore, s
t satisfies for positive scalars c
1 and c
2: (27)
c
1
f
w
t
2
≤
-
∇
f
w
t
T
s
t
,
s
t
≤
c
2
1
+
∇
f
w
t
.Using (25), (28)
E
v
t
∣
F
t
=
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
,
≤
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
·
∂
E
x
~
,
h
~
;
w
t
∂
w
t
.And using the condition (
3
) of Theorem 3, we assume the upper bound of ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is G; then, we have (29)
E
v
t
∣
F
t
≤
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
·
∂
E
x
~
,
h
~
;
w
t
∂
w
t
≤
G
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
≤
c
G
γ
t
.So, v
t satisfies for positive scalars p and q: (30)
E
v
t
∣
F
t
≤
γ
t
q
+
p
∇
f
w
t
.Using the assumption that the upper bound of ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is G, we have(31)
v
t
=
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
~
,
h
~
;
w
t
∂
w
t
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
≤
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
~
,
h
~
;
w
t
∂
w
t
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
≤
G
∑
h
p
h
;
w
t
∣
x
k
+
G
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
=
2
G
.Then, E
[
v
t
2
∣
F
t
]
≤
4
G
2. We let A
=
4
G
2; then, we have (32)
E
v
t
2
∣
F
t
≤
A
1
+
∇
f
w
t
2
.By using Theorem 2, we have f
(
w
t
) converging; then, the CD learning algorithm will converge.
The theorem is proved.We derive convergence conditions of the CD algorithm in the above theorem. It is easy to find that convergence conditions mainly include three aspects of contents. The first is the functionlog
⁡
p
(
x
;
w
) of the parameter w. The second is the learning rate of the CD learning algorithm. The third includes two terms. The first term is about the error between the empirical distribution function p
k
(
x
~
,
h
~
;
w
t
) and the distribution function p
(
x
~
,
h
~
;
w
t
); this term can be controlled by the number of Gibbs sampling. The second term is the value related to the energy function E
(
x
~
,
h
~
;
w
t
).These convergence conditions derived here are different from conditions that were obtained by Yuille [16]; convergence conditions which were obtained by Yuille are related to the model parameter; our convergence conditions are not related to the model parameter. Because the task of learning is to estimate the model parameter, the model parameter is generally unknown; convergence conditions in this paper have more practical significance than convergence conditions that were obtained by Yuille.


### 3.3. The Learning Rate and Convergence Conditions

In convergence conditions of the CD algorithm, the condition whichγ
t must satisfy is a necessary condition; it is (33)
∑
t
=
0
∞
γ
t
=
∞
,
∑
t
=
0
∞
γ
t
2
<
∞
.Basing the fact that ∑
t
=
1
∞
1
/
t
=
∞ and ∑
t
=
1
∞
1
/
t
2
<
∞, we assume γ
t
=
1
/
t and γ
0
=
0; then, we have the following new convergence conditions derived from Theorem 3.Corollary 4.
The CD learning algorithm will converge providing(1)
∇
f
(
w
)
-
∇
f
(
w
-
)
≤
L
w
-
w
-
,
w
,
w
-
∈
R
n, where L is a positive constant,
(2)
γ
0
=
0, γ
t
=
1
/
t,
(3)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
t
)
≤
c
γ
t, where c is a positive constant and ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is bounded.


### 3.4. Consistency of CD

It is clear that CD is equivalent to the Monte Carlo version of the log-likelihood gradient descent as the number the MCMC stepk goes to infinity, because the empirical distribution p
k
(
x
,
h
;
w
) converges to the distribution p
(
x
,
h
;
w
). It is known that CD gives a good solution; even k is relatively small. Akoho and Takabatake [14] give an intuitive interpretation about the reason why CD can approximate well by means of information geometry. In the above sections, we study the convergence of the CD algorithm; now, we consider the consistency of the CD algorithm. If w
∗ is a limit point of w
t, then f
(
w
t
) converges to the finite value f
(
w
∗
) by Theorem 2; then, w
∗ is a stationary point of f (w
∗
=
a
r
g
m
i
n
f
(
w
)); furthermore, every limit point of w
t is a stationary point of f. It is known that CD is an approximation of the log-likelihood gradient, the convergence conditions of Theorem 3 assure the error of the approximation is small enough to make CD converging. If the convergence conditions of Theorem 3 are satisfied, CD will converge. We know the conclusions of Theorems 2 and 3 hold with probability 1. We can obtain the following conclusion: if the CD algorithm converges with probability 1, the convergence point is consistent with the stationary point of the optimal function log
⁡
p
(
x
;
w
), which is a local optimum in general.


## 3.1. Gradient Methods with Errors and Convergence Theorem

Given the optimization problem,(7)
m
i
n
f
w
,
w
∈
R
n
,where R
n denotes the n-dimensional Euclidean space and f
(
w
)
:
R
n
→
R is a continuously differentiable function, such that for a positive constant L we have (8)
∇
f
w
-
∇
f
w
-
≤
L
w
-
w
-
∀
w
,
w
-
∈
R
n
,where w
=
(
∑
i
=
1
n
‍
w
i
2
)
1
/
2, · stands for the Euclidean norm in R
n.The gradient method with errors is of the following form:(9)
w
t
+
1
=
w
t
+
γ
t
s
t
+
v
t
,where γ
t is a positive step-size sequence, s
t is a descent direction, and v
t is an error.The errorv
t could be deterministic or stochastic. In both cases, the gradient method has been studied in literature [17–20]. We consider that v
t is stochastic because of the CD algorithm in this paper. The gradient method with stochastic errors can be considered as stochastic approximation algorithm or stochastic approximation procedure [21, 22]. Younes [22] has analyzed the convergence of stochastic approximation procedure (SAP) and has given the almost sure convergence conditions of SAP using ODE (Ordinary Differential Equations) approach. He generated a persistent Markov chain and studied the recursion algorithm in which several iterations of the simulation procedures are performed before updating the current parameter, with the updating being done using the average of the obtained values. Bertsekas and Tsitsiklis [18] have studied the convergence of gradient method, in which the expectation of the stochastic error v
t is zero with probability 1. We present a gradient method with different stochastic errors; convergence of the gradient method is guaranteed by the following theorem. We will need a known lemma, which has been proved by Grimmett and Stirzaker [23].Lemma 1.
LetX
t
,
Y
t and Z
t be three nonnegative random variables such that ∑
t
=
0
∞
‍
Y
t
<
∞ with probability 1 and E
t
[
X
t
+
1
]
≤
X
t
+
Y
t
-
Z
t for all t; then, X
t converges with probability 1 and ∑
t
=
0
∞
‍
Z
t
<
∞.Theorem 2.
Letw
t be a sequence generated by the method(10)
w
t
+
1
=
w
t
+
γ
t
s
t
+
v
t
,where γ
t is a positive step size, s
t is a descent direction, and v
t is a stochastic error. Let F
t be an increasing sequence of σ-fields (F
t should be interpreted as the history of the algorithm up to time t). We assume the following:(1)
f
(
w
)
≥
0
,
w
∈
R
n
,
f
(
w
t
), and s
t are F
t-measurable.
(2)
There exist positive scalarsc
1 and c
2 such that(11)
c
1
f
w
t
2
≤
-
∇
f
w
t
T
s
t
,
s
t
≤
c
2
1
+
∇
f
w
t
.
(3)
We have, for allt, and with probability 1, (12)
E
v
t
∣
F
t
≤
γ
t
q
+
p
∇
f
w
t
,
E
v
t
2
∣
F
t
≤
A
1
+
∇
f
w
t
2
,where p
,
q and A are constants, p
≥
0
,
q
≥
0
,
A
≥
0.
(4)
We have(13)
∑
t
=
0
∞
γ
t
=
∞
,
∑
t
=
0
∞
γ
t
2
<
∞
.Then, f
(
w
t
) converges.Proof.
With fixed two vectorsw and z, let ξ be a scalar parameter, and let g
(
ξ
)
=
f
(
w
+
ξ
z
). The chain rule yields (
d
g
/
d
ξ
)
(
ξ
)
=
z
T
∇
f
(
w
+
ξ
z
). We have (14)
f
w
+
z
-
f
w
=
g
1
-
g
0
=
∫
0
1
d
g
d
ξ
ξ
d
ξ
=
∫
0
1
z
T
∇
f
w
+
ξ
z
d
ξ
≤
z
T
∇
f
w
+
∫
0
1
z
T
∇
f
w
+
ξ
z
-
z
T
∇
f
w
d
ξ
≤
z
T
∇
f
w
+
z
∫
0
1
L
ξ
z
d
ξ
=
z
T
∇
f
w
+
L
2
z
2
.We apply (14) with w
=
w
t and z
=
γ
t
(
s
t
+
v
t
). We obtain (15)
f
w
t
+
1
≤
f
w
t
+
γ
t
∇
f
w
t
T
s
t
+
v
t
+
γ
t
2
L
2
s
t
+
v
t
2
.Using our assumptions, the relations s
t
2
≤
2
c
2
2
(
1
+
∇
f
(
w
t
)
2
) and s
t
+
v
t
2
≤
2
(
s
t
2
+
v
t
2
), we have (16)
f
w
t
+
1
≤
f
w
t
-
c
1
γ
t
∇
f
w
t
2
+
γ
t
∇
f
w
t
T
v
t
+
2
c
2
2
γ
t
2
L
1
+
∇
f
w
t
2
+
γ
t
2
L
v
t
2
.Taking conditional expectations with respect to F
t and using conditions (
3
) and the relation ∇
f
(
w
t
)
≤
1
+
∇
f
(
w
t
)
2, we have(17)
E
f
w
t
+
1
∣
F
t
≤
E
f
w
t
∣
F
t
-
c
1
γ
t
∇
f
w
t
2
+
γ
t
∇
f
w
t
·
E
v
t
∣
F
t
+
2
c
2
2
γ
t
2
L
1
+
∇
f
w
t
2
+
γ
t
2
L
E
v
t
2
∣
F
t
≤
E
f
w
t
∣
F
t
-
c
1
γ
t
∇
f
w
t
2
+
γ
t
2
q
∇
f
w
t
+
γ
t
2
p
∇
f
w
t
2
+
2
c
2
2
γ
t
2
L
+
2
c
2
2
γ
t
2
L
∇
f
w
t
2
+
γ
t
2
L
A
1
+
∇
f
w
t
2
≤
E
f
w
t
∣
F
t
-
γ
t
c
1
-
q
γ
t
-
p
γ
t
-
2
γ
t
c
2
2
L
-
γ
t
L
A
∇
f
w
t
2
+
γ
t
2
q
+
2
c
2
2
L
+
L
A
,which for sufficiently large t can be written as(18)
E
f
w
t
+
1
∣
F
t
≤
E
f
w
t
∣
F
t
-
γ
t
β
1
∇
f
w
t
2
+
γ
t
2
β
2
,where β
1 and β
2 are positive scalars.
Using the assumption thatf
(
w
t
) is F
t-measurable, we have (19)
E
f
F
t
w
t
+
1
≤
f
w
t
-
γ
t
β
1
∇
f
w
t
2
+
γ
t
2
β
2
.By using Lemma 1 and the assumption ∑
t
=
0
∞
‍
γ
t
2
<
∞, we see that f
(
w
t
) converges.
The theorem is proved.Strictly speaking, the conclusion of the theorem only holds with probability 1. For simplicity, an explicit statement of this qualification often will be omitted. We will use the theorem to derive convergence conditions of CD based on the similarity between the CD algorithm and the gradient method with errors.


## 3.2. Convergence of CD

In order to derive convergence conditions of the CD learning algorithm using the convergence theorem of the gradient method with errors, we have to explore the relation between the CD algorithm and the gradient method with errors. We can reconstruct the CD algorithm in the form of gradient optimization problem.The theorem of the gradient method with errors involves four basic concepts. The first is an optimization functionf
(
w
), which must be a continuously differentiable function, such that, for some constant L, we have ∇
f
(
w
)
-
∇
f
(
w
-
)
≤
L
w
-
w
-. The second is the descent direction s
t. The third is the error vector v
t. The last concept is the step size γ
t; γ
t can be considered as the learning rate in the CD learning algorithm. The gradient method with errors will converge provided the conditions of Theorem 2 are satisfied.We firstly design an optimal function for CD. Let(20)
f
w
=
-
log
⁡
p
x
;
w
.We can derive convergence theorem for the CD learning algorithm through selecting appropriate s
t and v
t. Next, we give the convergence theorem of the CD learning algorithm using the convergence theorem of the gradient method with errors.Theorem 3.
The CD learning algorithm will converge providing(1)
∇
f
(
w
)
-
∇
f
(
w
-
)
≤
L
w
-
w
-
,
w
,
w
-
∈
R
n, where L is a positive constant,
(2)
∑
t
=
0
∞
‍
γ
t
=
∞
,
∑
t
=
0
∞
‍
γ
t
2
<
∞,
(3)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
)
≤
c
γ
t, where c is a positive constant and ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is bounded.Proof.
The CD algorithm can be described as the form of gradient optimization problem. The CD algorithm is(21)
w
t
+
1
=
w
t
+
γ
t
-
∑
h
p
h
;
w
t
∣
x
0
∂
E
x
0
,
h
;
w
t
∂
w
t
+
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
k
,
h
;
w
t
∂
w
t
.In (21), let (22)
-
∑
h
p
h
;
w
t
∣
x
0
∂
E
x
0
,
h
;
w
t
∂
w
t
+
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
k
,
h
;
w
t
∂
w
t
=
s
t
+
v
t
.The CD algorithm in the form of gradient optimization problem can be described as follows: (23)
w
t
+
1
=
w
t
+
γ
t
s
t
+
v
t
.In (23), let (24)
s
t
=
-
∇
f
w
t
=
-
∑
h
p
h
;
w
t
∣
x
0
∂
E
x
0
,
h
;
w
t
∂
w
t
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
,
(25)
v
t
=
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
k
,
h
;
w
t
∂
w
t
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
.Then, (23) can be considered as the gradient method with errors.
Sinces
t
=
-
∇
f
(
w
t
), then we have (26)
-
∇
f
w
t
T
s
t
=
∇
f
w
t
T
∇
f
w
t
=
∇
f
w
t
2
.Therefore, s
t satisfies for positive scalars c
1 and c
2: (27)
c
1
f
w
t
2
≤
-
∇
f
w
t
T
s
t
,
s
t
≤
c
2
1
+
∇
f
w
t
.Using (25), (28)
E
v
t
∣
F
t
=
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
,
≤
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
·
∂
E
x
~
,
h
~
;
w
t
∂
w
t
.And using the condition (
3
) of Theorem 3, we assume the upper bound of ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is G; then, we have (29)
E
v
t
∣
F
t
≤
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
·
∂
E
x
~
,
h
~
;
w
t
∂
w
t
≤
G
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
≤
c
G
γ
t
.So, v
t satisfies for positive scalars p and q: (30)
E
v
t
∣
F
t
≤
γ
t
q
+
p
∇
f
w
t
.Using the assumption that the upper bound of ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is G, we have(31)
v
t
=
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
~
,
h
~
;
w
t
∂
w
t
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
≤
∑
h
p
h
;
w
t
∣
x
k
∂
E
x
~
,
h
~
;
w
t
∂
w
t
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
∂
E
x
~
,
h
~
;
w
t
∂
w
t
≤
G
∑
h
p
h
;
w
t
∣
x
k
+
G
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
t
=
2
G
.Then, E
[
v
t
2
∣
F
t
]
≤
4
G
2. We let A
=
4
G
2; then, we have (32)
E
v
t
2
∣
F
t
≤
A
1
+
∇
f
w
t
2
.By using Theorem 2, we have f
(
w
t
) converging; then, the CD learning algorithm will converge.
The theorem is proved.We derive convergence conditions of the CD algorithm in the above theorem. It is easy to find that convergence conditions mainly include three aspects of contents. The first is the functionlog
⁡
p
(
x
;
w
) of the parameter w. The second is the learning rate of the CD learning algorithm. The third includes two terms. The first term is about the error between the empirical distribution function p
k
(
x
~
,
h
~
;
w
t
) and the distribution function p
(
x
~
,
h
~
;
w
t
); this term can be controlled by the number of Gibbs sampling. The second term is the value related to the energy function E
(
x
~
,
h
~
;
w
t
).These convergence conditions derived here are different from conditions that were obtained by Yuille [16]; convergence conditions which were obtained by Yuille are related to the model parameter; our convergence conditions are not related to the model parameter. Because the task of learning is to estimate the model parameter, the model parameter is generally unknown; convergence conditions in this paper have more practical significance than convergence conditions that were obtained by Yuille.


## 3.3. The Learning Rate and Convergence Conditions

In convergence conditions of the CD algorithm, the condition whichγ
t must satisfy is a necessary condition; it is (33)
∑
t
=
0
∞
γ
t
=
∞
,
∑
t
=
0
∞
γ
t
2
<
∞
.Basing the fact that ∑
t
=
1
∞
1
/
t
=
∞ and ∑
t
=
1
∞
1
/
t
2
<
∞, we assume γ
t
=
1
/
t and γ
0
=
0; then, we have the following new convergence conditions derived from Theorem 3.Corollary 4.
The CD learning algorithm will converge providing(1)
∇
f
(
w
)
-
∇
f
(
w
-
)
≤
L
w
-
w
-
,
w
,
w
-
∈
R
n, where L is a positive constant,
(2)
γ
0
=
0, γ
t
=
1
/
t,
(3)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
t
)
≤
c
γ
t, where c is a positive constant and ∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t is bounded.


## 3.4. Consistency of CD

It is clear that CD is equivalent to the Monte Carlo version of the log-likelihood gradient descent as the number the MCMC stepk goes to infinity, because the empirical distribution p
k
(
x
,
h
;
w
) converges to the distribution p
(
x
,
h
;
w
). It is known that CD gives a good solution; even k is relatively small. Akoho and Takabatake [14] give an intuitive interpretation about the reason why CD can approximate well by means of information geometry. In the above sections, we study the convergence of the CD algorithm; now, we consider the consistency of the CD algorithm. If w
∗ is a limit point of w
t, then f
(
w
t
) converges to the finite value f
(
w
∗
) by Theorem 2; then, w
∗ is a stationary point of f (w
∗
=
a
r
g
m
i
n
f
(
w
)); furthermore, every limit point of w
t is a stationary point of f. It is known that CD is an approximation of the log-likelihood gradient, the convergence conditions of Theorem 3 assure the error of the approximation is small enough to make CD converging. If the convergence conditions of Theorem 3 are satisfied, CD will converge. We know the conclusions of Theorems 2 and 3 hold with probability 1. We can obtain the following conclusion: if the CD algorithm converges with probability 1, the convergence point is consistent with the stationary point of the optimal function log
⁡
p
(
x
;
w
), which is a local optimum in general.


## 4. Convergence of CD Algorithm for RBMs

In this section, we consider the convergence of the CD algorithm for RBMs. In the following, we consider the case where both visible unitsx and hidden units h only take a finite number of values.


### 4.1. Convergence Conditions of CD Algorithm for RBMs

The RBMs structure is a bipartite graph consisting of one layer of visible variablesX
=
(
X
1
,
…
,
X
m
) and one layer of hidden variables H
=
(
H
1
,
…
,
H
n
). The model distribution is given by p
(
x
,
h
;
w
)
=
e
-
E
(
x
,
h
;
w
)
/
Z
(
w
), where Z
(
w
)
=
∑
x
,
h
‍
e
-
E
(
x
,
h
;
w
), and the energy function is given by (34)
E
x
,
h
;
w
=
-
∑
i
=
1
n
∑
j
=
1
m
w
i
j
h
i
x
j
-
∑
j
=
1
m
b
j
x
j
-
∑
i
=
1
n
c
i
h
iwith w
i
j
,
c
i
,
b
j are real-valued parameters which are denoted by w.In Section3, we have already considered convergence of the CD algorithm and derived convergence theorem for the CD learning algorithm based on the convergence theorem of gradient method with errors. Now, we give the convergence theorem of the CD learning algorithm for RBMs.Theorem 5.
The CD learning algorithms for RBMs will converge providing(1)
∑
t
=
0
∞
‍
γ
t
=
∞
,
∑
t
=
0
∞
‍
γ
t
2
<
∞,
(2)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
t
)
≤
c
γ
t, where c is a positive constant.Proof.
To prove the convergence of the CD learning algorithm for RBMs, we have to prove the CD algorithm satisfying three conditions of Theorem3. Obviously, we can obtain the second condition of Theorem 3 from the first condition. Next, we prove the CD algorithm satisfying other two conditions of Theorem 3.
Firstly, we provef
(
w
) satisfying the first condition of Theorem 3.
Sincef
(
w
)
=
-
log
⁡
p
(
x
;
w
), then (35)
∇
f
w
-
∇
f
w
-
≤
∑
h
p
h
;
w
∣
x
∂
E
x
,
h
;
w
∂
w
-
∑
h
p
h
;
w
-
∣
x
∂
E
x
,
h
;
w
-
∂
w
-
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
∂
E
x
~
,
h
~
;
w
∂
w
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
-
∂
E
x
~
,
h
~
;
w
-
∂
w
-
.Using (34), ∂
E
(
x
,
h
;
w
)
/
∂
w is an independent variable with w since E
(
x
,
h
;
w
) is affine with w. For convenience, let (36)
∂
E
x
,
h
;
w
∂
w
=
g
x
,
h
.Then,(37)
∑
h
p
h
;
w
∣
x
∂
E
x
,
h
;
w
∂
w
-
∑
h
p
h
;
w
-
∣
x
∂
E
x
,
h
;
w
-
∂
w
-
≤
∑
h
g
x
,
h
∂
p
h
;
w
′
∣
x
∂
w
′
·
w
-
w
-
≤
∑
h
g
x
,
h
·
∂
p
h
;
w
′
∣
x
∂
w
′
·
w
-
w
-
,where w
′
=
w
-
+
θ
(
w
-
w
-
)
,
0
<
θ
<
1, and(38)
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
∂
E
x
~
,
h
~
;
w
∂
w
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
-
∂
E
x
~
,
h
~
;
w
-
∂
w
-
≤
∑
x
~
,
h
~
g
x
~
,
h
~
·
∂
p
x
~
,
h
~
;
w
′
′
∂
w
′
′
·
w
-
w
-
,where w
′
′
=
w
-
+
η
(
w
-
w
-
)
,
0
<
η
<
1
.
Sincex and h only take a finite number of values, then g
(
x
,
h
) has the upper bound; we assume the upper bound is G.
Sincep
(
x
,
h
;
w
)
=
1
/
Z
(
w
)
e
-
E
(
x
,
h
;
w
)
=
e
-
E
(
x
,
h
;
w
)
/
∑
x
,
h
‍
e
-
E
(
x
,
h
;
w
), we have (39)
∂
p
x
,
h
;
w
∂
w
=
-
e
-
E
x
,
h
;
w
Z
w
∂
E
x
,
h
;
w
∂
w
+
e
-
E
x
,
h
;
w
Z
w
∑
x
,
h
e
-
E
x
,
h
;
w
∂
E
x
,
h
;
w
/
∂
w
Z
w
=
-
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
+
p
x
,
h
;
w
∑
x
,
h
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
≤
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
+
p
x
,
h
;
w
∑
x
,
h
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
≤
G
p
x
,
h
;
w
+
G
∑
x
,
h
p
x
,
h
;
w
≤
2
G
.Let G
′
′
=
2
G; then, ∂
p
(
x
,
h
;
w
′
′
)
/
∂
w
′
′ has the upper bound G
′
′.
Since(40)
p
h
;
w
∣
x
=
p
x
,
h
;
w
p
x
;
w
=
e
-
E
x
,
h
;
w
Z
w
Z
w
∑
h
e
-
E
x
,
h
;
w
,for a similar reason, ∂
p
(
h
;
w
′
∣
x
)
/
∂
w
′ has the upper bound G
′. Using inequalities (35), (37), and (38), we have (41)
∇
f
w
-
∇
f
w
-
≤
∑
h
G
·
G
′
·
w
-
w
-
+
∑
x
,
~
h
~
G
·
G
′
′
·
w
-
w
-
≤
∑
h
G
·
G
′
+
∑
x
~
,
h
~
G
·
G
′
′
w
-
w
-
.Let ∑
h
G
·
G
′
+
∑
x
~
,
h
~
G
·
G
′
′
=
L; then, we have (42)
∇
f
w
-
∇
f
w
-
≤
L
w
-
w
-
.Secondly, since∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t has the upper bound, then the condition (
3
) of Theorem 3 is satisfied.By using the Theorem3, we see that the CD learning algorithm converges.The theorem is proved.We obtain convergence conditions of the CD learning algorithm for RBMs. Next, we study the relationship between the learning rate and convergence conditions. Basing the fact that∑
t
=
1
∞
1
/
t
=
∞ and ∑
t
=
1
∞
1
/
t
2
<
∞, we also assume γ
t
=
1
/
t and γ
0
=
0; then, we have the following new convergence conditions derived from Theorem 5.Corollary 6.
The CD learning algorithm will converge providing(1)
γ
0
=
0, γ
t
=
1
/
t,
(2)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
)
≤
c
γ
t, where c is a positive constant.
The result of Corollary6 shows that the convergence of the CD algorithm is related to the errors between the empirical distribution function p
k
(
x
~
,
h
~
) and the distribution function p
(
x
~
,
h
~
)  providing the learning rate is deterministic; the error can be controlled by the number of Gibbs sampling.


### 4.2. Theoretical Analysis of Convergence Conditions

In Section4.1, we have given the convergence conditions of the CD algorithm for RBMs; the most important term is the error between the empirical distribution function p
k
(
x
~
,
h
~
;
w
t
) and the distribution function p
(
x
~
,
h
~
;
w
t
); the empirical distribution function p
k
(
x
~
,
h
~
;
w
t
) is the empirical distribution function on the samples obtained by the data x and running the Markov chain forward for k steps, the distribution function p
(
x
~
,
h
~
;
w
t
) is the limit distribution of the empirical distribution. Fischer and Igel [24] have given the bound of the bias of p
k
(
x
~
,
h
~
;
w
t
) and p
(
x
~
,
h
~
;
w
t
): (43)
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
≤
1
-
e
-
m
+
n
a
k
,where k is the step number of Gibbs sampling in tth update, m
,
n are the number of visible and hidden variables, and(44)
a
=
max
⁡
m
a
x
l
∈
1
,
…
,
m
ϑ
l
,
m
a
x
l
∈
1
,
…
,
n
ζ
l
,where(45)
ϑ
l
=
max
⁡
∑
i
=
1
n
I
w
i
l
>
0
w
i
l
+
b
l
,
∑
i
=
1
n
I
w
i
l
<
0
w
i
l
+
b
l
,
ζ
l
=
max
⁡
∑
j
=
1
m
I
w
l
j
>
0
w
l
j
+
c
l
,
∑
j
=
1
m
I
w
l
j
<
0
w
l
j
+
c
l
.Then, we can draw new convergence conditions of the CD algorithm using the conclusion.Theorem 7.
The CD learning algorithm for RBMs will converge providing(1)
∑
t
=
0
∞
‍
γ
t
=
∞
,
∑
t
=
0
∞
‍
γ
t
2
<
∞,
(2)
k
≥
log
⁡
(
c
γ
t
)
/
log
⁡
(
1
-
e
-
(
m
+
n
)
a
), where m
,
n are the number of visible and hidden variables and a is defined in equality (43), k is the step number of Gibbs sampling in tth update (k
∈
N
+), and c is a positive constant.Proof.
In order to prove Theorem7, we have to prove that we can derive the condition (
2
) of Theorem 5 from the condition (
2
) of Theorem 7. Now, we prove it.
Using the inequality (43), we have (46)
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
≤
1
-
e
-
m
+
n
a
k
.By the condition (
2
) of Theorem 7, we have c
γ
t
≥
(
1
-
e
-
(
m
+
n
)
a
)
k; using the above the inequality, we have(47)
c
γ
t
≥
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
.The proof of the theorem is completed.Theorem7 gives new convergence conditions; the second condition of the theorem is the relationship which the step number of Gibbs sampling and the learning rate must satisfy in every step of parameter updating in order to guarantee the CD algorithm convergence.


## 4.1. Convergence Conditions of CD Algorithm for RBMs

The RBMs structure is a bipartite graph consisting of one layer of visible variablesX
=
(
X
1
,
…
,
X
m
) and one layer of hidden variables H
=
(
H
1
,
…
,
H
n
). The model distribution is given by p
(
x
,
h
;
w
)
=
e
-
E
(
x
,
h
;
w
)
/
Z
(
w
), where Z
(
w
)
=
∑
x
,
h
‍
e
-
E
(
x
,
h
;
w
), and the energy function is given by (34)
E
x
,
h
;
w
=
-
∑
i
=
1
n
∑
j
=
1
m
w
i
j
h
i
x
j
-
∑
j
=
1
m
b
j
x
j
-
∑
i
=
1
n
c
i
h
iwith w
i
j
,
c
i
,
b
j are real-valued parameters which are denoted by w.In Section3, we have already considered convergence of the CD algorithm and derived convergence theorem for the CD learning algorithm based on the convergence theorem of gradient method with errors. Now, we give the convergence theorem of the CD learning algorithm for RBMs.Theorem 5.
The CD learning algorithms for RBMs will converge providing(1)
∑
t
=
0
∞
‍
γ
t
=
∞
,
∑
t
=
0
∞
‍
γ
t
2
<
∞,
(2)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
t
)
≤
c
γ
t, where c is a positive constant.Proof.
To prove the convergence of the CD learning algorithm for RBMs, we have to prove the CD algorithm satisfying three conditions of Theorem3. Obviously, we can obtain the second condition of Theorem 3 from the first condition. Next, we prove the CD algorithm satisfying other two conditions of Theorem 3.
Firstly, we provef
(
w
) satisfying the first condition of Theorem 3.
Sincef
(
w
)
=
-
log
⁡
p
(
x
;
w
), then (35)
∇
f
w
-
∇
f
w
-
≤
∑
h
p
h
;
w
∣
x
∂
E
x
,
h
;
w
∂
w
-
∑
h
p
h
;
w
-
∣
x
∂
E
x
,
h
;
w
-
∂
w
-
+
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
∂
E
x
~
,
h
~
;
w
∂
w
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
-
∂
E
x
~
,
h
~
;
w
-
∂
w
-
.Using (34), ∂
E
(
x
,
h
;
w
)
/
∂
w is an independent variable with w since E
(
x
,
h
;
w
) is affine with w. For convenience, let (36)
∂
E
x
,
h
;
w
∂
w
=
g
x
,
h
.Then,(37)
∑
h
p
h
;
w
∣
x
∂
E
x
,
h
;
w
∂
w
-
∑
h
p
h
;
w
-
∣
x
∂
E
x
,
h
;
w
-
∂
w
-
≤
∑
h
g
x
,
h
∂
p
h
;
w
′
∣
x
∂
w
′
·
w
-
w
-
≤
∑
h
g
x
,
h
·
∂
p
h
;
w
′
∣
x
∂
w
′
·
w
-
w
-
,where w
′
=
w
-
+
θ
(
w
-
w
-
)
,
0
<
θ
<
1, and(38)
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
∂
E
x
~
,
h
~
;
w
∂
w
-
∑
x
~
,
h
~
p
x
~
,
h
~
;
w
-
∂
E
x
~
,
h
~
;
w
-
∂
w
-
≤
∑
x
~
,
h
~
g
x
~
,
h
~
·
∂
p
x
~
,
h
~
;
w
′
′
∂
w
′
′
·
w
-
w
-
,where w
′
′
=
w
-
+
η
(
w
-
w
-
)
,
0
<
η
<
1
.
Sincex and h only take a finite number of values, then g
(
x
,
h
) has the upper bound; we assume the upper bound is G.
Sincep
(
x
,
h
;
w
)
=
1
/
Z
(
w
)
e
-
E
(
x
,
h
;
w
)
=
e
-
E
(
x
,
h
;
w
)
/
∑
x
,
h
‍
e
-
E
(
x
,
h
;
w
), we have (39)
∂
p
x
,
h
;
w
∂
w
=
-
e
-
E
x
,
h
;
w
Z
w
∂
E
x
,
h
;
w
∂
w
+
e
-
E
x
,
h
;
w
Z
w
∑
x
,
h
e
-
E
x
,
h
;
w
∂
E
x
,
h
;
w
/
∂
w
Z
w
=
-
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
+
p
x
,
h
;
w
∑
x
,
h
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
≤
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
+
p
x
,
h
;
w
∑
x
,
h
p
x
,
h
;
w
∂
E
x
,
h
;
w
∂
w
≤
G
p
x
,
h
;
w
+
G
∑
x
,
h
p
x
,
h
;
w
≤
2
G
.Let G
′
′
=
2
G; then, ∂
p
(
x
,
h
;
w
′
′
)
/
∂
w
′
′ has the upper bound G
′
′.
Since(40)
p
h
;
w
∣
x
=
p
x
,
h
;
w
p
x
;
w
=
e
-
E
x
,
h
;
w
Z
w
Z
w
∑
h
e
-
E
x
,
h
;
w
,for a similar reason, ∂
p
(
h
;
w
′
∣
x
)
/
∂
w
′ has the upper bound G
′. Using inequalities (35), (37), and (38), we have (41)
∇
f
w
-
∇
f
w
-
≤
∑
h
G
·
G
′
·
w
-
w
-
+
∑
x
,
~
h
~
G
·
G
′
′
·
w
-
w
-
≤
∑
h
G
·
G
′
+
∑
x
~
,
h
~
G
·
G
′
′
w
-
w
-
.Let ∑
h
G
·
G
′
+
∑
x
~
,
h
~
G
·
G
′
′
=
L; then, we have (42)
∇
f
w
-
∇
f
w
-
≤
L
w
-
w
-
.Secondly, since∂
E
(
x
~
,
h
~
;
w
t
)
/
∂
w
t has the upper bound, then the condition (
3
) of Theorem 3 is satisfied.By using the Theorem3, we see that the CD learning algorithm converges.The theorem is proved.We obtain convergence conditions of the CD learning algorithm for RBMs. Next, we study the relationship between the learning rate and convergence conditions. Basing the fact that∑
t
=
1
∞
1
/
t
=
∞ and ∑
t
=
1
∞
1
/
t
2
<
∞, we also assume γ
t
=
1
/
t and γ
0
=
0; then, we have the following new convergence conditions derived from Theorem 5.Corollary 6.
The CD learning algorithm will converge providing(1)
γ
0
=
0, γ
t
=
1
/
t,
(2)
∑
x
~
,
h
~
‍
p
k
(
x
~
,
h
~
;
w
t
)
-
p
(
x
~
,
h
~
;
w
)
≤
c
γ
t, where c is a positive constant.
The result of Corollary6 shows that the convergence of the CD algorithm is related to the errors between the empirical distribution function p
k
(
x
~
,
h
~
) and the distribution function p
(
x
~
,
h
~
)  providing the learning rate is deterministic; the error can be controlled by the number of Gibbs sampling.


## 4.2. Theoretical Analysis of Convergence Conditions

In Section4.1, we have given the convergence conditions of the CD algorithm for RBMs; the most important term is the error between the empirical distribution function p
k
(
x
~
,
h
~
;
w
t
) and the distribution function p
(
x
~
,
h
~
;
w
t
); the empirical distribution function p
k
(
x
~
,
h
~
;
w
t
) is the empirical distribution function on the samples obtained by the data x and running the Markov chain forward for k steps, the distribution function p
(
x
~
,
h
~
;
w
t
) is the limit distribution of the empirical distribution. Fischer and Igel [24] have given the bound of the bias of p
k
(
x
~
,
h
~
;
w
t
) and p
(
x
~
,
h
~
;
w
t
): (43)
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
≤
1
-
e
-
m
+
n
a
k
,where k is the step number of Gibbs sampling in tth update, m
,
n are the number of visible and hidden variables, and(44)
a
=
max
⁡
m
a
x
l
∈
1
,
…
,
m
ϑ
l
,
m
a
x
l
∈
1
,
…
,
n
ζ
l
,where(45)
ϑ
l
=
max
⁡
∑
i
=
1
n
I
w
i
l
>
0
w
i
l
+
b
l
,
∑
i
=
1
n
I
w
i
l
<
0
w
i
l
+
b
l
,
ζ
l
=
max
⁡
∑
j
=
1
m
I
w
l
j
>
0
w
l
j
+
c
l
,
∑
j
=
1
m
I
w
l
j
<
0
w
l
j
+
c
l
.Then, we can draw new convergence conditions of the CD algorithm using the conclusion.Theorem 7.
The CD learning algorithm for RBMs will converge providing(1)
∑
t
=
0
∞
‍
γ
t
=
∞
,
∑
t
=
0
∞
‍
γ
t
2
<
∞,
(2)
k
≥
log
⁡
(
c
γ
t
)
/
log
⁡
(
1
-
e
-
(
m
+
n
)
a
), where m
,
n are the number of visible and hidden variables and a is defined in equality (43), k is the step number of Gibbs sampling in tth update (k
∈
N
+), and c is a positive constant.Proof.
In order to prove Theorem7, we have to prove that we can derive the condition (
2
) of Theorem 5 from the condition (
2
) of Theorem 7. Now, we prove it.
Using the inequality (43), we have (46)
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
≤
1
-
e
-
m
+
n
a
k
.By the condition (
2
) of Theorem 7, we have c
γ
t
≥
(
1
-
e
-
(
m
+
n
)
a
)
k; using the above the inequality, we have(47)
c
γ
t
≥
∑
x
~
,
h
~
p
k
x
~
,
h
~
;
w
t
-
p
x
~
,
h
~
;
w
t
.The proof of the theorem is completed.Theorem7 gives new convergence conditions; the second condition of the theorem is the relationship which the step number of Gibbs sampling and the learning rate must satisfy in every step of parameter updating in order to guarantee the CD algorithm convergence.


## 5. Conclusions

In this paper, we have studied the convergence of the CD learning algorithm. Firstly, we relate the CD learning algorithm to the gradient method with errors and give convergence conditions which ensure that the CD learning algorithm converges. Convergence conditions mainly include three aspects of contents. Our convergence conditions are different from conditions that were obtained by Yuille [16]; our convergence conditions have more practical value. Moreover, we have studied convergence of the CD algorithm for RBMs; particularly, we give convergence conditions of the CD algorithm for RBMs in which both visible units and hidden units only take a finite number of values. We give the analysis of the consistency of the CD algorithm; meanwhile, we also give two new convergence conditions by specifying the learning rate.



---

*Source: 350102-2015-07-12.xml*