Greedy Structure Search
Two algorithms from 2006 — Hinton, Osindero & Teh’s deep belief net and Jakulin & Rish’s Markov-network interaction search — contrasted, traced to their roots, and placed in the longer evolution of structure search.
1. The core duality
These two algorithms are almost duals of each other. Hinton’s puts the hard work in continuous parameter optimization inside a fixed, dense architecture and treats “structure” (the layers) as trivial bookkeeping. Jakulin & Rish put the hard work in discrete structure search and keep the parameters trivial — closed-form, computed once, independent of structure.
One grows depth by grinding gradients; the other grows interaction-order by searching combinatorially over near-free model evaluations. Both face an intractable object — a non-convex deep likelihood with a partition function on one side, a super-exponential space of structures on the other — and both pay it down by being greedy: add one piece at a time. What differs is which half of the problem they declare easy.
2. What each greedy search does
Hinton, Osindero & Teh — greedy layer-wise learning
The search is over the parameters of a fixed-depth architecture, optimized one layer at a time. Treat the bottom two layers as a Restricted Boltzmann Machine, learn its weights with contrastive divergence, freeze them, push the data up through that layer, and treat the resulting activations as “data” for the next RBM. Stack repeatedly. The greedy move is “add and train one more layer.” It is justified: because of complementary priors (initializing the new layer with the transpose of the layer below), each greedy step provably does not decrease a variational lower bound on the data log-likelihood. A separate global fine-tuning pass (the up–down algorithm) follows.
Jakulin & Rish — greedy interaction search
The model is an undirected Markov network over the attributes and the class, represented as a hypergraph: a set of hyperedges (cliques, allowed to be non-maximal and of cardinality >2), each carrying a closed-form potential built from Dirichlet–multinomial submodels via the cluster-variation / Kikuchi region-graph construction. Because the submodels are estimated independently of the structure, adding a hyperedge is just “multiplying the predictions for an instance with one more term and renormalizing.” On top of that cheap-to-extend representation sits a plain search:
“Our initial structure will have a single initial hyperedge of cardinality 1, {Y}. In the successive step, we will consider all possible attributes Xᵢ creating hyperedges {Xᵢ}∪{Y}, and pick the one that yields the highest posterior probability: this corresponds to step-wise forward selection with one-step look-ahead.”
Candidates are scored by a conditional (discriminative) likelihood times a structure prior P(M) ∝ e−df, where df is a degrees-of-freedom complexity penalty adjusted for conditional modelling. The headline novelty is a correction to how interactions had been selected before: rather than scoring each interaction marginally and in isolation (a filter, as in the earlier interaction-information work), each candidate is judged by what it contributes to the conditional posterior of the model as it currently stands — because, in the authors’ words, “inclusions of individual interactions for the model structure are not independent decisions.”
3. Contrast: efficiency, depth, speed, pros and cons
The deepest contrast is where intractability is paid down. Hinton makes structure trivial and spends everything on learning parameters, buying a variational guarantee but paying in iterative contrastive-divergence training. Jakulin & Rish make parameters trivial and spend everything on searching structure, giving up the guarantee but gaining orders-of-magnitude speed and a fully interpretable result.
| Hinton, Osindero & Teh — greedy layer-wise DBN | Jakulin & Rish — greedy interaction search | |
|---|---|---|
| What is explored | Weights of a fixed, fully-connected deep net | Discrete hypergraph of interactions (which cliques to include) |
| Unit of greedy growth | One latent layer at a time | One interaction (hyperedge) at a time |
| Cost per greedy step | Expensive: train an RBM by contrastive divergence (Gibbs sampling + gradient, many epochs); no closed form | Near-free: multiply one potential term and renormalize; submodels precomputed once |
| Overall speed | Slow training, fast inference (single bottom-up pass via complementary priors) | Blazing: 46 datasets fully searched in <9 min (vs 686 min for BN classifiers); a tic-tac-toe net in 0.03 s |
| “Depth” | Depth of latent abstraction — the point; this is what made deep nets trainable | Depth of search (number of interactions, hyperedge cardinality k); representationally flat |
| Justification for greed | Each layer provably does not lower a variational bound | Heuristic hill-climb; no global guarantee, but a df-based prior controls complexity |
| Approximation | CD (biased gradient) for the partition function; complementary priors for inference | Kikuchi / cluster-variation region graph for the joint |
| Interpretability | Distributed latent features — opaque | Explicit, named interactions (synergy / redundancy via interaction information) |
| Data regime | High-dimensional, perceptual, lots of data | Discrete tabular data, tens of attributes, small-sample-friendly |
| Main strength | Learns a hierarchy of features from raw input; scales | Speed + interpretability + calibrated class probabilities; k-way and even cyclic structure |
| Main weakness | Costly, hyperparameter-heavy, opaque, no explicit structure discovery | Myopic (one-step look-ahead), shallow, candidate set explodes with many attributes / high k |
4. A genealogy of the idea
Both 2006 algorithms are the same species — greedy, stagewise, constructive learning — and descend from a shared root in statistical mechanics and information theory: both models are Gibbs distributions wrestling the same partition function. From there the lineage splits into a neural / energy-based branch and a graphical-model / information-theoretic branch. Folding in the prior art documented by Schmidhuber sharpens the picture in three places.
The two lineages
The neural / energy-based branch begins in statistical physics — the Lenz–Ising model, made adaptive by Amari (1972) and turned into a learnable Gibbs distribution as the Boltzmann machine (Hinton & Sejnowski 1985). Smolensky’s Harmonium (1986), later the RBM, removes intra-layer connections to make it tractable; contrastive divergence (Hinton 2002) makes a single RBM cheap to train; and the 2006 paper stacks those trainable RBMs greedily, with complementary priors supplying the variational guarantee.
The graphical-model / information-theoretic branch runs through Kikuchi’s cluster-variation method (1951, later region graphs and generalized belief propagation, Yedidia–Freeman–Weiss 2005); stepwise selection of interaction terms in hierarchical log-linear models (Bishop, Fienberg & Holland 1975); the naive-Bayes extensions (semi-naive Bayes, Kononenko 1991; TAN, Friedman, Geiger & Goldszmidt 1997); and most directly, feature induction in random fields (Della Pietra, Della Pietra & Lafferty 1997). Jakulin & Rish keep Della Pietra’s greedy-feature-induction skeleton but swap the expensive iterative-scaling refit for closed-form Kikuchi potentials — which is exactly what lets them lift the pairwise/treewidth caps and run a full best-hyperedge search at every step.
The precedents that matter
GMDH (Ivakhnenko & Lapa 1965; Ivakhnenko 1971) is the unifying ancestor, because the structure-search idea the two papers share is its idea. GMDH grows a network one layer at a time; each unit is a low-order polynomial over a pair of inputs (so the unit is an interaction, and depth composes higher-order interactions); and it selects structure, keeping only the units that improve a held-out criterion and pruning the rest. All three primitives are present in 1965–71: greedy layer-wise growth (the Hinton primitive), construction from interaction terms (the Jakulin–Rish primitive), and model-selection-by-criterion (the one both rely on). The 1971 net was already eight layers deep.
Unsupervised greedy layer-wise pre-training (Schmidhuber 1991) — the “neural history compressor,” a stack of self-supervised predictors trained one level at a time, where each higher level reduces the description length (negative log-probability) of the level below. That MDL framing rhymes with the degrees-of-freedom prior on the other branch.
The energy-based root is specific, not metaphorical: the Kikuchi cluster-variation method Jakulin & Rish use is itself a statistical-mechanics free-energy approximation to exactly the Ising / spin-glass systems the neural branch learns — which is why Yedidia–Freeman–Weiss could later show Kikuchi free energy and belief propagation are the same object. The two branches share the same free-energy machinery.
A fairness note: these pointers come from Schmidhuber’s priority arguments, and several of his credit verdicts (notably Amari-vs-Hopfield, and the “plagiarism” framing) are contested. The prior-art pointers — GMDH especially — are verifiable and belong in this genealogy regardless of how the credit question is settled.
5. Contrastive divergence and structure search
Contrastive divergence is not a structure-search algorithm; it is the parameter-fitting inner loop. For an RBM it estimates the maximum-likelihood gradient ⟨vᵢhⱼ⟩data − ⟨vᵢhⱼ⟩model, approximating the intractable model term by a short Gibbs chain started at the data. It answers “given this fixed graph, what weights fit?” — not “which graph?” Yet it sits exactly at the seam between the two strategies:
- By contrast. CD is precisely the expensive thing explicit structure search over undirected models would otherwise have to call per candidate (to fit parameters and evaluate likelihood, which needs the partition function). Jakulin & Rish’s whole speed advantage comes from deleting that loop via closed-form Kikuchi potentials.
- As a structure signal. The quantity
⟨f⟩data − ⟨f⟩modelis large for exactly the correlations the current model fails to reproduce — the same criterion a greedy feature-induction step uses to decide which interaction to add (Della Pietra et al. 1997; McCallum 2003). Search on the outside, CD on the inside. - As implicit structure learning. In a dense energy-based net, CD performs structure learning implicitly: hidden units specialize and irrelevant correlations get small weight, so effective structure emerges inside parameter learning. Add an L1 penalty and it becomes near-explicit edge selection.
So CD is the emblem of the first half of the duality: make structure trivial and let gradient learning discover it softly, rather than searching a discrete space explicitly.
6. Stacking RBMs ≈ multi-way interaction search
The analogy between stacking RBMs and multi-way interaction search is closer than the surface, and the mechanism makes it precise. Marginalize the hidden units of an RBM and the visible distribution is a product of experts:
Each softplus term is a smooth function of a weighted sum of the visibles in hidden unit j’s receptive field, and expanding it in the 0/1 visibles produces terms of every order — vi, vivk, vivkvl, … So a single hidden unit is a soft, weighted superposition of multi-way interactions over the variables it touches; adding hidden units adds interaction factors; and stacking a second RBM models interactions among the first layer’s features — still-higher-order interactions back in the original variables. An RBM hidden unit is, in effect, a compressed low-rank encoding of exactly the kind of multi-way clique potential one adds explicitly as a hyperedge. (This is also why a higher-order Boltzmann machine, Sejnowski 1986, with explicit k-way weights, and an RBM are reparameterizations of each other.) The difference: the interaction search enumerates the tensor sparsely and names the cliques; the RBM encodes it implicitly and names nothing.
On chronology
RBMs (Smolensky 1986) and contrastive divergence (Hinton 2002) predate the IBM reports, but the move that stacks RBMs into a deep belief net is Hinton, Osindero & Teh (Neural Computation, 2006) — after Kikuchi-Bayes (RC23314, deposited Oct 2004) and RC23602 (2005), and contemporaneous with the ECML 2006 paper. So as published artifacts, the multi-way interaction search predates the RBM-stacking construction by roughly a year and a half. Two cautions keep that from hardening into a priority claim: the core idea — greedily growing layers whose units are higher-order interactions and keeping the useful ones — predates both by decades (GMDH 1965; Schmidhuber’s 1991 layer-wise stacking); and there is no sign of influence in either direction. What remains is genuine convergence: an explicit, observed-variable interaction search and an implicit, latent RBM encoding of the same multi-way structure, reaching print within months of each other — and the explicit one happened to land first.
7. The evolution of structure search
Read the diagram’s edges as the payload: each arrow is the new idea that turns the parent algorithm into the child. Left-to-right is roughly chronological; the purple lane is the energy-based / implicit-structure thread, the teal lane is explicit graphical-model structure search, and GMDH is the dashed common precedent. The spine of the whole story is one move repeated with variations — add one piece to the model, score it, keep or discard — where what evolves is what the “piece” is (a regression term → a tree edge → a DAG edge → an undirected feature → a k-way hyperedge) and how it is scored.
8. Foundations: structure search as search over a lattice
Almost every moving part of the interaction search is already lattice arithmetic in disguise. Making that explicit grounds the algorithm, bridges it to logic and category theory, and lets us locate it precisely among the classical algorithms for partial orders — and then re-read Hinton’s algorithm in the same language.
8.1 The search space is a lattice
The candidate hyperedges generate the Boolean lattice 2E ordered by inclusion (join = union, meet = intersection, ⊥ = {Y}). The hierarchical models — a face present only if all its sub-faces are — are the down-closed sets of the subset poset, which by Birkhoff’s representation theorem form a distributive lattice. Forward selection from {Y} is a monotone ascent in that lattice; the “sub-faces first” rule makes the reachable build-sequences a shelling of a simplicial complex, i.e. an antimatroid (a greedoid) — exactly the structure on which greedy is provably well-behaved (Korte–Lovász).
8.2 The score is Möbius inversion
Three different-looking pieces of the paper are one operation — Möbius inversion (Rota 1964) — on three functions over the lattice. The recursive potentials solve to a Möbius transform of the log-marginals,
the counting numbers cR = 1 − ΣR′ ⊃ R cR′ are the Möbius function of the region poset, and interaction information is the Möbius transform of entropy. The energy-based branch is not exempt: a Boltzmann machine’s log-partition cumulant expansion is Möbius inversion over the partition lattice (Speed 1983). Same operation, different functions and different lattices.
8.3 Why greedy is justified: submodularity
Entropy is monotone and submodular on the Boolean lattice — the rank function of a polymatroid (Fujishige 1978) — so information has diminishing returns and greedy maximization carries the (1−1/e) guarantee (Nemhauser–Wolsey–Fisher 1978). The degrees-of-freedom prior is a modular valuation subtracted off. “Submodular minus modular, climbed greedily on a lattice” is the principled core of forward selection.
8.4 The bridge to category theory
A poset is a thin category; a lattice has finite products (meet) and coproducts (join); ⊥/⊤ are initial/terminal. So the search space is a category and the covering relations are its morphisms. The assignment of a submodel P(vR) to each region with marginalization as restriction maps is a presheaf; the requirement that a global P(V) exists whose marginals are the submodels is the sheaf gluing condition (a global section), and its failure is contextuality (Abramsky–Brandenburger 2011). The counting numbers are the Euler characteristic of the region category (Leinster 2008); Galois connections are adjunctions; and stacking layers is composition in a Markov category (Fritz 2020), with conditioning/marginalization as adjoint operations.
8.5 The bridge to logic
Read one way the same lattice is an algebra of propositions: structures are conjunctions of “interaction present” atoms, and the lattice is their Lindenbaum–Tarski algebra. The logical twin of structure search predates it — version spaces (Mitchell 1977) and ILP refinement operators (Plotkin 1970; Muggleton 1991) are inductive inference as search of a subsumption lattice, with the least general generalization as the lattice join. Three theorems make logic, lattice and category the same object: Curry–Howard–Lambek (propositions ≈ types ≈ objects), Stone duality (algebra ⇄ space), and Lawvere’s quantifiers-as-adjoints (1969), under which marginalization is the measure-theoretic image of ∃ — summing along a projection, the left adjoint to substitution. Consistency/contextuality is then a logical obstruction in the spirit of Kochen–Specker.
8.6 Related algorithms for lattices and partial orders
(“Lattice” here is order-theoretic, not the integer lattices of LLL/SVP, which share only the word.) The interaction search sits at the intersection of three families:
- Lattice traversal. Levelwise / Apriori mining (Agrawal–Srikant 1994; Mannila–Toivonen 1997) exploits downward closure on the subset lattice, its positive border being a version-space boundary; version spaces and ILP refinement traverse a subsumption lattice; greedoid and submodular greedy (Edmonds; Korte–Lovász; NWF) give the optimization guarantees. J&R is a score-guided greedy path up this lattice, not a full border enumeration.
- Möbius / zeta-transform scoring. Fast zeta/Möbius transforms (Yates; Kennes 1992) and subset convolution (Björklund et al. 2007) compute lattice sums fast; exact Bayesian structure discovery (Koivisto–Sood 2004) sums over the subset lattice by Möbius transform. J&R uses the same Möbius kernel but greedily, not exhaustively.
- Region-poset inference. The junction tree (Lauritzen–Spiegelhalter 1988), generalized belief propagation on region graphs (Yedidia–Freeman–Weiss 2005), and iterative proportional fitting (Deming–Stephan 1940) all operate on a separator/region poset. J&R generalizes the junction tree to cyclic region graphs and replaces IPF/GBP iteration with closed-form Möbius potentials.
| Related algorithm | Shared lattice/poset idea | How Jakulin–Rish differs |
|---|---|---|
| Apriori / levelwise mining | anti-monotone search of the subset lattice | greedy score-guided path, not full border |
| Version spaces / ILP refinement | refinement on a subsumption lattice | probabilistic score, not logical consistency |
| Greedy submodular / greedoid | greedy ascent on an antimatroid | adds a modular df penalty; one-step look-ahead |
| Fast Möbius/zeta; subset convolution | inclusion–exclusion over the lattice | kernel used locally per candidate |
| Koivisto–Sood exact discovery (2004) | Möbius transform over the subset lattice | greedy hill-climb of the same sum |
| Junction tree (1988) | message passing on a separator poset | generalized to cyclic region graphs (Kikuchi) |
| Generalized belief propagation (2005) | region-graph counting numbers | closed-form forward product, no iteration |
| Iterative proportional fitting (1940) | fit potentials on the margin lattice | closed-form Möbius potentials, no iteration |
Its two closest individual relatives are Koivisto–Sood exact structure discovery (same lattice and Möbius machinery, exhaustive DP where J&R is greedy) and the junction tree (same region poset, which J&R generalizes from chordal trees to cyclic region graphs). Compactly: it replaces the exact DP over the structure lattice with a greedy walk, and the iterative fit on the region poset with closed-form Möbius potentials — two lattice approximations stacked for speed.
9. The two algorithms through the lattice lens
The lattice families above are essentially the exact / structured tradition. Jakulin–Rish is a fast approximate member of it. Hinton’s greedy layer-wise DBN belongs to the opposite tradition — Monte-Carlo / variational gradient on dense models — which is exactly what one reaches for when the lattice is too dense to exploit. Reading both through the three families makes the contrast sharp.
| Lattice-algorithm family | Jakulin & Rish | Hinton (deep belief net) |
|---|---|---|
| Structure-lattice search | explicit, score-guided greedy ascent of the clique/face lattice | none — architecture fixed and dense; ascends only the trivial chain of depths |
| The normalizer (a lattice sum) | computed in closed form via Möbius / Kikuchi over the region poset (exact if chordal) | refused — partition function left intractable; gradient estimated by sampling (contrastive divergence) |
| Region-poset inference | CVM region graph; generalizes the junction tree to cyclic graphs | complementary priors flatten the poset to one feed-forward pass; the dense bipartite graph (high treewidth) makes the poset route hopeless |
| Interaction lattice | selects specific join-irreducible elements (named hyperedges) | places weight implicitly across the whole lattice (softplus expansion); never selects |
| Incremental growth (shared) | adds a lattice atom — one hyperedge | adds a chain step — one layer (interactions among learned features) |
| Tradition | exact/structured lattice algorithms (Möbius DP, junction tree, IPF, levelwise), as a fast approximation | Monte-Carlo / variational gradient on dense models |
So the two algorithms are complementary responses to the same lattice obstruction — the partition function is an inclusion–exclusion sum over a lattice, and the structure space is a super-exponential lattice. Jakulin–Rish stays where that arithmetic is tractable: sparse, low-cardinality hyperedges and near-chordal region graphs, where the Möbius sum is closed-form and the structure lattice can be walked explicitly. Hinton goes where it is hopeless: a dense bipartite graph of high treewidth, where no junction tree or closed-form Möbius sum exists — so the structure lattice is abandoned (only depth is grown), the normalizer is never summed (contrastive divergence samples its gradient), and the inference poset is engineered flat by complementary priors. The single point of contact is incremental growth: J&R climbs the structure lattice one atom at a time; Hinton climbs the depth chain one layer at a time. One computes the lattice; the other escapes it.
References
- G. E. Hinton, S. Osindero & Y.-W. Teh. A Fast Learning Algorithm for Deep Belief Nets. Neural Computation 18(7):1527–1554, 2006. PDF
- A. Jakulin & I. Rish. Bayesian Learning of Markov Network Structure. ECML 2006 (LNCS 4212, pp. 198–209). eprint
- A. Jakulin, I. Rish & I. Bratko. Kikuchi-Bayes: Factorized Models for Approximate Classification in Closed Form. IBM Tech. Report RC23314, 2004. eprint
- S. Della Pietra, V. Della Pietra & J. Lafferty. Inducing Features of Random Fields. 1997. arXiv
- G. E. Hinton. Training Products of Experts by Minimizing Contrastive Divergence. Neural Computation, 2002.
- A. G. Ivakhnenko & V. G. Lapa. Cybernetic Predicting Devices. 1965. — A. G. Ivakhnenko, Polynomial Theory of Complex Systems, IEEE Trans. SMC, 1971.
- J. Schmidhuber. Critique of Honda Prize for Dr. Hinton (2020). link — Physics Nobel 2024 critique. link
- P. Smolensky (Harmonium, 1986) · T. Sejnowski (Higher-order Boltzmann machines, 1986) · S. Amari (1972) · C. Chow & C. Liu (1968) · Y. Bishop, S. Fienberg & P. Holland (1975) · I. Kononenko (1991) · N. Friedman, D. Geiger & M. Goldszmidt (TAN, 1997) · G. Cooper & E. Herskovits (K2, 1992) · D. Heckerman, D. Geiger & D. Chickering (1995) · N. Friedman & D. Koller (2003) · D. Grossman & P. Domingos (2004) · J. Yedidia, W. Freeman & Y. Weiss (2005) · A. McCallum (2003).