Stochastic Generative Hashing

1 Introduction

• Similarity search in large datasets is costly with brute-force linear search; partitioning and data coding are two orthogonal strategies used to reduce search time and storage.The introduction focuses on L2 nearest-neighbor search, while noting that the method also handles maximum inner-product search in supplementary material.Source: §1 · p. 1
• Binary hashing maps samples to short codes that support efficient Hamming-distance search, but learned hashing objectives are often heuristic and optimization relaxes binary constraints.The introduction contrasts binary-code search with quantization, which can give stronger empirical results but tends to be less efficient.Source: §1 · pp. 1–2
• SGH models both encoding binary codes from inputs and decoding inputs from codes, using the Minimum Description Length principle to learn codes that maximally compress the dataset.Its generative model also permits optimizing distributions over discrete hash codes without directly handling discrete variables.Source: §1 · p. 2

2 Stochastic Generative Hashing (SGH)

• SGH avoids relaxation-based binary optimization by learning distributions over binary variables and uses end-to-end distributional stochastic gradient descent instead of expensive integer programs.The paper also contrasts its training with ITQ's iterative steps and alternating optimization.Source: §2 · pp. 2–3

2.1 Generative Model p(x|h)

• The generative model defines p(x|h) as a decoder and derives the corresponding code distribution q(h|x); a Gaussian reconstruction model links reconstruction error to Euclidean neighborhood preservation.The additive model reconstructs x by summing selected codebook columns, with a Bernoulli prior on codes; other neighborhood-preserving generative models are also allowed.Source: §2.1 · pp. 3–4

2.2 Encoding Model q(h|x)

• The encoder approximates the intractable posterior p(h|x), whose MAP solution would require an expensive integer-programming subproblem.At training, codes are sampled from Bernoulli probabilities; at inference, the MAP encoder uses a linear projection followed by a sign operation.Source: §2.2 · p. 4

2.3 Training Objective

• The MDL objective minimizes expected information needed to communicate x by combining the description length of its hash with the cost of describing x given that hash.Because the objective does not include binary codes as parameters, it permits continuous optimization without directly optimizing discrete variables.Source: §2.3 · p. 4

2.4 Reparametrization via Stochastic Neuron

• The stochastic neuron reparameterizes Bernoulli bits with uniform noise, making them deterministic conditional on that noise and enabling a reformulated training objective.The paper then optimizes the reformulated objective using distributional stochastic gradient descent.Source: §2.4 · p. 5

3 Distributional Stochastic Gradient Descent

• The method uses distributional derivatives because reparameterization leaves the objective nondifferentiable with respect to W at the stochastic neuron’s discontinuity.For fixed ξ, the stochastic neuron’s distributional derivative with respect to z is the Dirac-δ function.Source: §3 · p. 5, §3.1 · p. 5

3.1 Distributional derivative of Stochastic Neuron

• Distributional SGD combines distributional derivative estimators with SGD, producing an unbiased stochastic estimator from sampled x and ξ that is simpler and amenable to online learning.The approximate estimator reduces computation to one pass per dimension and coincides with the heuristic pseudo-gradient of Raiko et al. (2014).Source: §3.1 · p. 6

3.2 Convergence of Distributional SGD

• The distributional derivative of the stochastic neuron’s objective with respect to W equals the traditional gradient, making it the true gradient for this hashing problem.The authors note that this equivalence resolves the general concern that a distributional derivative might not be a descent direction.Source: §3.2 · p. 6
• Distributional SGD has the same convergence property as traditional SGD when the objective is L-Lipschitz smooth and the stochastic distributional gradient has bounded variance.With the approximate gradient estimator, the algorithm also converges in terms of first-order conditions when its variance is bounded.Source: §3.2 · p. 7

Iterative Quantization (ITQ)

• Under the stated orthogonality and covariance-eigenvector conditions, the SGH objective reduces to iterative quantization (Gong and Lazebnik, 2011).The encoder distribution is fixed to δ_bi(h).Source: §4 · p. 7

Binary Autoencoder (BA)

• With a deterministic linear encoder and ρ > 0, the SGH objective reduces to the binary autoencoder objective of Carreira-Perpinán and Raziperchikolaei (2015).In BA, the encoding is deterministic, so the entropy term is zero.Source: §4 · p. 7

Connections to existing algorithms

• Without stochasticity, optimizing the binary-constrained objective becomes extremely difficult; the proposed algorithm uses stochasticity to bypass that difficulty.The paper also reports that stochasticity accelerates optimization.Source: §4 · p. 8

5 Experiments

• The experiments span MNIST, CIFAR-10, SIFT-1M, SIFT-1B, and GIST-1M, evaluating reconstruction, convergence, training time, retrieval, and image regeneration.The datasets include up to 10^9 SIFT vectors in SIFT-1B.Source: §5 · p. 8

5.1 Reconstruction loss

• SGH reaches lower L2 reconstruction loss than ITQ with comparable or sometimes less training time on SIFT-1M, MNIST, and GIST-1M.The authors attribute the lower loss to modeling flexibility from removing orthogonality constraints.Source: §5.1 · p. 9

5.2 Empirical study of Distributional SGD

• Distributional SGD converges quickly on SIFT-1M, GIST-1M, and MNIST from 8 to 64 bits, and more bits reduce reconstruction error.The reported convergence uses Adam and includes a biased gradient estimator.Source: §5.2 · p. 9
• BA takes significantly longer than SGH to train across the tested bit settings on SIFT-1M, GIST-1M, and MNIST.The paper attributes BA’s longer training to the cost of solving its integer-programming subproblem.Source: §5.2 · p. 9

5.3 Large scale nearest neighbor retrieval

• SGH performs best across all tested bit settings and datasets in large-scale nearest-neighbor retrieval.The comparisons use Recall10@N on MNIST, SIFT-1M, GIST-1M, and SIFT-1B; on SIFT-1B, only ITQ is compared because other competitors’ training costs are prohibitive.Source: §5.3 · pp. 9–10, Figure 2 · p. 10

5.4 Visualization of reconstruction

• SGH achieves similar visual reconstruction quality to PCA while using 32× fewer bits, and its reconstructions are more recognizable than ITQ’s on MNIST and less blurry on CIFAR-10.SGH and ITQ use 64-bit codes; PCA uses 64 components, or 2048 bits.Source: §5.4 · p. 11, Figure 3 · p. 11

• The proposed algorithm is theoretically justified as preserving Euclidean neighborhoods while enabling fast learning and retrieval.Source: §6 · p. 11
• Experiments on several benchmarks support the model's flexibility, especially its ability to reconstruct inputs from hash codes.Source: §6 · p. 11
• The conclusion identifies semi-supervised hashing and other learning-to-hash settings as possible extensions, and notes that distributional SGD may apply to integer programming more generally.Source: §6 · p. 11

A Distributional Derivative of Stochastic Neuron

• The supplement gives two chain rules for distributional derivatives of composed functions.One covers v = u ◦ f; the other covers v = f ◦ u when f′ is bounded.Source: A Distributional Derivative of… · p. 15
• The stochastic-neuron derivative approximation is developed using the mean value theorem and Taylor expansion, yielding a biased gradient estimator.Source: A Distributional Derivative of… · p. 15

B Convergence of Distributional SGD

• The convergence lemmas for distributional SGD and its approximate gradient state bounded-variance assumptions; the exact-gradient lemma also assumes L-Lipschitz smoothness.Source: B Convergence of Distributional SGD · p. 16

C.1 Convergence of Distributional SGD and Reconstruction Error Comparison

• The MNIST and GIST-1M reconstruction-error results are described as similar to those on SIFT-1M.Source: §C.1 · p. 16
• SGH finds lower reconstruction error than ITQ on MNIST and GIST-1M.The authors attribute this to SGH's more expressive objective without orthogonality constraints and its avoidance of alternating optimization.Source: §C.1 · p. 16, Figure 4 · p. 17
• Figure 4 compares L2 reconstruction-error convergence at 8, 16, 32, and 64 bits as the number of training examples seen increases.For ITQ, one iteration sees the training dataset once.Source: Figure 4 · p. 17

C.2 Training Time Comparison

• Figure 5 presents the training-time comparison between BA and SGH on MNIST and GIST-1M.Source: Figure 5 · p. 17
• The proposed distributional SGD learns the model much faster than BA on MNIST and GIST-1M.Source: §C.2 · p. 17, Figure 5 · p. 17
• The MNIST and GIST-1M training-time results are described as similar to the SIFT-1M trend.Source: §C.2 · p. 17

C.3 More Evaluation on L2NNS Retrieval Tasks

• SGH achieves state-of-the-art performance under Recall 1@N, an easier task than Recall 10@N.The comparison uses Figure 6.Source: §C.3 · p. 17
• The section tests retrieval performance with two distinct recall measures: Recall 1@N and Recall 100@100.The former is described as easier than Recall 10@N.Source: §C.3 · p. 17
• With K=N=100, SGH consistently achieves state-of-the-art performance under recall evaluation as bit length varies on MNIST, SIFT-1M, and GIST-1M.Source: §C.3 · p. 17

D Stochastic Generative Hashing For Maximum Inner Product Search

• For MIPS, Gaussian reconstruction error is a surrogate for preserving asymmetric inner products, although SGH is designed primarily for hashing.Quantization extensions are left for future work and are outside the paper’s scope.Source: D Stochastic Generative Hashing For… · p. 18

D.1 MIPS Retrieval Comparison

• On WORD2VEC MIPS retrieval, SGH significantly outperforms the competitors.The evaluation used 71,291 training samples, 10,000 queries, and 16-, 32-, and 64-bit codes, with ground truth from original inner-product retrieval.Source: §D.1 · p. 18

E.1 Translation and Scale Invariant Reduced-MRFs

• The translation- and scale-invariant extension adds a translation parameter and per-sample latent scale variables to model those effects explicitly.The authors state that distributional SGD remains applicable.Source: §E.1 · pp. 18–19

E.2 Semi-supervised Extension

• The semi-supervised extension adds a pairwise model for labeled data pairs alongside the Gaussian reconstruction model, and distributional SGD remains applicable.The provided labels may be partial.Source: §E.2 · p. 19

E.3 {±1}-Binary Coding

• The model and distributional SGD also support {-1, 1} codes with minor modifications.The supplementary figures cover Recall 1@M on four datasets, Recall 100@100 on three datasets, and WORD2VEC MIPS Recall 10@M.Source: §E.3 · p. 19, Figure 6 · p. 20, Figure 7 · p. 21