TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The finite-state CD-k gradient includes the chain-distribution derivative

Statement

Let $r$ be a positive integer, let $X$ be finite and nonempty, and let $Θ \subseteq R^{r}$ be open. For each $x, y \in X$ , assume the coordinate partial derivatives of $E_{θ} (x)$ and $K_{θ} (x, y)$ exist and are continuous on $Θ$ . Let $K_{θ}$ be strictly positive and row-stochastic, so $K_{θ} (x, y) > 0$ and $\sum_{y} K_{θ} (x, y) = 1$ . Use counting measure as the reference measure, set $Z_{θ} : = \sum_{x \in X} e^{- E_{θ} (x)}, p_{θ} (x) : = e^{- E_{θ} (x)} / Z_{θ},$ let $q_{0}$ be a fixed probability vector on $X$ , assume $p_{θ}$ is invariant for $K_{θ}$ , and fix an integer $k \geq 1$ . Define $K_{θ}^{0} = I$ , $K_{θ}^{s + 1} = K_{θ}^{s} K_{θ}$ , and $q_{k, θ} = q_{0} K_{θ}^{k}$ , where vectors are row vectors, and $L (θ) : = - \sum_{x} q_{0} (x) \log p_{θ} (x), {CD}_{k} (θ) : = D_{K L} (q_{0} ∥ p_{θ}) - D_{K L} (q_{k, θ} ∥ p_{θ}),$ where for finite probability mass functions $a, b$ with $b (x) > 0$ , $D_{K L} (a ∥ b) : = \sum_{x : a (x) > 0} a (x) \log \frac{a (x)}{b (x)}$ with $\log$ the natural logarithm and zero-mass terms contributing zero. For each parameter coordinate $j$ , $\partial_{j} L (θ) = \sum_{x} q_{0} (x) \partial_{j} E_{θ} (x) - \sum_{x} p_{θ} (x) \partial_{j} E_{θ} (x),$ while $\partial_{j} {CD}_{k} (θ) = \sum_{x} q_{0} (x) \partial_{j} E_{θ} (x) - \sum_{x} q_{k, θ} (x) \partial_{j} E_{θ} (x) - \sum_{x} \partial_{j} q_{k, θ} (x) \log \frac{q_{k, θ} (x)}{p_{θ} (x)} .$ The reconstruction-law derivative is $\partial_{j} q_{k, θ} = \sum_{s = 0}^{k - 1} q_{0} K_{θ}^{s} (\partial_{j} K_{θ}) K_{θ}^{k - 1 - s} .$ Thus the population direction used by stop-gradient CD- $k$ is the first two terms of the displayed $\partial_{j} {CD}_{k}$ formula and omits the explicit derivative through the $k$ transition kernels. It also replaces the model expectation in the exact negative log-likelihood gradient by the finite reconstruction law; no equality between these gradients is asserted.

For the finite-state path calculation, let $Ω : = X^{k + 1}$ with its full sigma-algebra, let $X_{s}$ be the $s$ th coordinate map, and define $P_{θ} (A) : = \sum_{(x_{0}, \dots, x_{k}) \in A} q_{0} (x_{0}) \prod_{s = 0}^{k - 1} K_{θ} (x_{s}, x_{s + 1}), A \subseteq Ω .$ This is a probability measure. For every real $f : X \to R$ , set $g_{f} (x) : = {\begin{cases} \sum_{y} K_{θ}^{k} (x, y) f (y), & q_{0} (x) > 0, \\ 0, & q_{0} (x) = 0. \end{cases}$ Then $g_{f} (X_{0})$ is a version of $E_{P_{θ}} [f (X_{k}) ∣ σ (X_{0})]$ .

Statement references

Geoffrey Hinton, Section 2 of the full technical report derives the likelihood and reconstruction updates and notes the omitted contrastive-divergence derivative.

Kevin P. Murphy, Chapter 24, Section 24.2.2 defines the finite-step difference-of-KL contrastive-divergence objective.

The measure definition used for finite path laws.

The probability-measure definition used for finite path laws.

The conditional-expectation definition supplies the event-integral criterion used for the path calculation.

Positivity of the exponential gives positive finite-state model weights.

Facts & Assumptions

Given: A finite nonempty state space, open parameter domain, finite energy model, fixed data probability vector, positive differentiable stochastic matrix with invariant model law, and integer $k \geq 1$ .

[A1]

For each state or state pair, the energy and transition entries have continuous coordinate partial derivatives on the open set $Θ$ ; every entry of $K_{θ}$ is positive and each row sums to one.

[F1]

Energy-based density and partition function: $p_{θ} (x) = e^{- E_{θ} (x)} / Z_{θ}$ for an admissibly normalized energy model.

[F2]

Contrastive divergence with k transitions: the reconstruction law obeys $Q_{j + 1, θ} (A) = \int K_{θ} (x, A) Q_{j, θ} (d x)$ ; on a finite state space this is row-vector multiplication by $K_{θ}$ .

[F3]

Contrastive divergence with k transitions: the population stop-gradient direction is $E_{q_{0}} \nabla_{θ} E_{θ} - E_{q_{k, θ}} \nabla_{θ} E_{θ}$ .

[F4]

Finite probability vectors: a finite probability vector has nonnegative coordinates summing to one.

[F5]

The derivative $f^{'} (c) = \lim_{x \to c} \frac{f (x) - f (c)}{x - c}$ of $f : A \to R$ at a point $c \in A$ that is a limit point of $A$ , and differentiability on a set: the derivative at a real coordinate point is defined by the limit of its difference quotient.

[F6]

Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : finite sums, scalar multiples, products, and quotients (where the denominator is nonzero) obey the stated derivative rules.

[F7]

The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ : the derivative of a composition of differentiable real functions is the product of the outer derivative at the image and the inner derivative.

[F8]

The exponential function is smooth and $(\exp)^{'} = \exp$ : $\exp^{'} (u) = \exp (u)$ for every real $u$ .

[F9]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: for $u > 0$ , $\log^{'} (u) = 1 / u$ for the natural logarithm.

[F10]

Measures on sigma-algebras: a measure vanishes on the empty set and is countably additive on pairwise disjoint sequences.

[F11]

Probability measures and probability spaces: a measure with total mass one is a probability measure.

[F12]

Conditional expectation given a sigma algebra: a conditional-expectation version is integrable, measurable with respect to the conditioning sigma-algebra, and has the same integral as the conditioned variable on every event in that sigma-algebra.

[F13]

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (u) > 0$ for every real $u$ .

Proof

1.1givenA1F1F4F5F6F7F8F9F13algebra

Fix a coordinate $j$ and vary only $θ_{j}$ in a small interval inside the open set $Θ$ . Since $X$ is finite and each energy is real, [F13] makes every $e^{- E_{θ} (x)}$ positive; hence [F1] gives $0 < Z_{θ} < \infty$ . The formula for $p_{θ}$ then gives positive coordinates summing to one, so it is a probability vector by [F4]. By [F6], [F7] and [F8], differentiating the finite sum gives $\partial_{j} Z_{θ} = - \sum_{x} e^{- E_{θ} (x)} \partial_{j} E_{θ} (x)$ . The same chain and quotient rules give $\partial_{j} p_{θ} (x) / p_{θ} (x) = - \partial_{j} E_{θ} (x) - \partial_{j} Z_{θ} / Z_{θ} = - \partial_{j} E_{θ} (x) + \sum_{y} p_{θ} (y) \partial_{j} E_{θ} (y)$ ; [F9] identifies the left side with $\partial_{j} \log p_{θ} (x)$ . Because $q_{0}$ is fixed and sums to one by [F4], differentiating $L = - \sum_{x} q_{0} (x) \log p_{θ} (x)$ and summing this identity yields the displayed likelihood-gradient formula.

1.2givenA1F2F4F5F6algebra

The recurrence in [F2] gives $q_{j + 1, θ} = q_{j, θ} K_{θ}$ , hence $q_{k, θ} = q_{0} K_{θ}^{k}$ and $\sum_{x} q_{k, θ} (x) = 1$ . For $k = 1$ the product rule [F6] gives $\partial_{j} (q_{0} K_{θ}) = q_{0} \partial_{j} K_{θ}$ . If $\partial_{j} (q_{0} K_{θ}^{k}) = \sum_{s = 0}^{k - 1} q_{0} K_{θ}^{s} (\partial_{j} K_{θ}) K_{θ}^{k - 1 - s}$ , then entrywise application of [F6] to $q_{0} K_{θ}^{k} K_{θ}$ yields $\sum_{s = 0}^{k - 1} q_{0} K_{θ}^{s} (\partial_{j} K_{θ}) K_{θ}^{k - s} + q_{0} K_{θ}^{k} (\partial_{j} K_{θ})$ , which is the same formula with $k + 1$ by appending the $s = k$ term. Thus the stated product derivative holds for every $k$ . Differentiating $\sum_{x} q_{k, θ} (x) = 1$ by [F6] gives $\sum_{x} \partial_{j} q_{k, θ} (x) = 0$ . Strict positivity of $K_{θ}$ and nonzero mass of $q_{0}$ imply $q_{k, θ} (x) > 0$ for every $x$ , so the following logarithms are finite.

1.3A1F4F10F11algebraconstruct

Put $w (x_{0}, \dots, x_{k}) : = q_{0} (x_{0}) \prod_{s = 0}^{k - 1} K_{θ} (x_{s}, x_{s + 1})$ . These weights are nonnegative. Summing successively over $x_{k}, \dots, x_{1}$ and using the row sums of $K_{θ}$ reduces $\sum_{ω \in Ω} w (ω)$ to $\sum_{x_{0}} q_{0} (x_{0}) = 1$ . The set function $P_{θ} (A) = \sum_{ω \in A} w (ω)$ vanishes on the empty set and is countably additive: a disjoint sequence of subsets of finite $Ω$ has only finitely many nonempty terms. Thus [F10] makes it a measure, and [F11] makes it a probability measure.

2.1givenA1F5F6F7F9step 1.1step 1.2algebra

By the quotient rule [F6], $\partial_{j} (q_{k, θ} (x) / p_{θ} (x)) = \partial_{j} q_{k, θ} (x) / p_{θ} (x) - q_{k, θ} (x) \partial_{j} p_{θ} (x) / p_{θ} (x)^{2}$ ; the chain and logarithm derivative rules [F7, F9] then give $\partial_{j} \log (q_{k, θ} (x) / p_{θ} (x)) = \partial_{j} q_{k, θ} (x) / q_{k, θ} (x) - \partial_{j} \log p_{θ} (x)$ . Applying the product rule [F6] to each summand of $D_{K L} (q_{k, θ} ∥ p_{θ})$ therefore gives $\partial_{j} q_{k, θ} (x) (\log (q_{k, θ} (x) / p_{θ} (x)) + 1) - q_{k, θ} (x) \partial_{j} \log p_{θ} (x)$ . Summing the finite terms, the $+ 1$ contribution vanishes by step 1.2. Substitution from step 1.1 yields $\partial_{j} D_{K L} (q_{k, θ} ∥ p_{θ}) = \sum_{x} \partial_{j} q_{k, θ} (x) \log (q_{k, θ} (x) / p_{θ} (x)) + \sum_{x} q_{k, θ} (x) \partial_{j} E_{θ} (x) - \sum_{x} p_{θ} (x) \partial_{j} E_{θ} (x)$ .

2.2A1F4step 1.3algebra

For $s = 0$ , $K_{θ}^{0} = I$ is row-stochastic and its entries are the length-zero path weights. If the entries of $K_{θ}^{s}$ sum the products along all length- $s$ paths, then $K_{θ}^{s + 1} (x, y) = \sum_{z} K_{θ}^{s} (x, z) K_{θ} (z, y)$ appends the final transition, so its entries sum the length- $(s + 1)$ path weights; also $\sum_{y} K_{θ}^{s + 1} (x, y) = \sum_{z} K_{θ}^{s} (x, z) \sum_{y} K_{θ} (z, y) = 1$ . Thus $P_{θ} (X_{0} = x, X_{k} = y) = q_{0} (x) K_{θ}^{k} (x, y)$ . The function $g_{f}$ is finite-valued; for each Borel $C \subseteq R$ , ${g_{f} (X_{0}) \in C} = X_{0}^{- 1} ({x : g_{f} (x) \in C})$ , so $g_{f} (X_{0})$ is $σ (X_{0})$ -measurable. Both $f (X_{k})$ and $g_{f} (X_{0})$ are integrable since $Ω$ is finite.

3.1givenF3F4F5F6F9step 1.1step 2.1algebra

Since $q_{0}$ is fixed, the terms $q_{0} (x) \log q_{0} (x)$ in $D_{K L} (q_{0} ∥ p_{θ})$ have zero derivative; applying the same product and logarithm rules [F6, F9] and using the log-density formula from step 1.1 and $\sum_{x} q_{0} (x) = 1$ gives $\partial_{j} D_{K L} (q_{0} ∥ p_{θ}) = \sum_{x} q_{0} (x) \partial_{j} E_{θ} (x) - \sum_{x} p_{θ} (x) \partial_{j} E_{θ} (x)$ . Subtracting step 2.1 cancels the model expectations and yields the stated $\partial_{j} {CD}_{k}$ formula. By [F3], the algorithm uses only its first two terms; the remaining sum is the derivative through $K_{θ}^{k}$ . Comparing with step 1.1 also shows that the algorithm replaces the exact likelihood negative phase $p_{θ}$ by $q_{k, θ}$ .

4.1F12step 2.2algebra∎

Every event in $σ (X_{0})$ has the form ${X_{0} \in B}$ for some $B \subseteq X$ , since these preimages form a sigma-algebra and generate $σ (X_{0})$ . For every such event, step 2.2 gives $\int 1_{{X_{0} \in B}} f (X_{k}) d P_{θ} = \sum_{x \in B} q_{0} (x) \sum_{y} K_{θ}^{k} (x, y) f (y) = \int 1_{{X_{0} \in B}} g_{f} (X_{0}) d P_{θ},$ where terms with $q_{0} (x) = 0$ vanish. The integrability and measurability from step 2.2 and this event-integral identity satisfy [F12], so $g_{f} (X_{0})$ is the asserted conditional-expectation version.

Depends on

Used by

A two-state witness to short-run contrastive-divergence bias Example

Dependency tree · two levels

55 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Geoffrey Hinton, A Practical Guide to Training Restricted Boltzmann Machines, Version 1, Section 2 (standard reference, not scraped)
Kevin P. Murphy, Probabilistic Machine Learning: Advanced Topics, Chapter 24, Section 24.2.2 (standard reference, not scraped)