Greedy Structure Search

In 2006 a simple strategy — build a complex model one piece at a time — showed that deep neural networks could be trained after all, and opened the deep-learning era. The same year, the same strategy was used to find explicit interactions among variables. This report contrasts the two algorithms — Hinton, Osindero & Teh’s deep belief net and Jakulin & Rish’s Markov-network interaction search — traces them to their roots, and places them in the longer evolution of structure search.

Prepared for Aleks Jakulin · · Revised · Reader’s edition

Research synthesis prepared for Aleks Jakulin and edited with AI assistance. Authors of the underlying research are credited in the references. Editorial attribution updated .

Revised from the original, retaining its structural comparisons and genealogies. Revision record · Previous edition · Read the original report (uncorrected).

In brief Deep neural networks became trainable in 2006 through a greedy strategy: add one layer at a time, each layer learning features of the one below. This report sets that algorithm beside a contemporary one that adds, one at a time, explicit interactions among variables. It asks what the two have in common, where each came from, and what mathematics describes both. The answer is a single old idea — build a model from simpler pieces, test what each addition contributes, continue — applied to two different kinds of piece.

Why this matters: the idea that made deep learning work

Almost every artificial-intelligence system in use today — speech recognition, machine translation, image generation, protein-structure prediction, large language models — is a deep neural network: a stack of many layers, each computing features of the layer below. It is easy to forget that around the year 2000 this design was widely regarded as a dead end. Networks with one hidden layer could be trained. General-purpose networks with several could not, at least not reliably: the learning signal faded as it was passed down through the layers, training stalled, and most of the field turned to methods with cleaner mathematics, such as support vector machines and probabilistic graphical models. Convolutional networks for images and LSTM networks for sequences were the notable exceptions, and stayed outside the mainstream. [LeCun, Bengio & Hinton]

The first paper examined here changed that. In 2006 Geoffrey Hinton, Simon Osindero and Yee-Whye Teh showed how to train a deep network by not training it all at once. Train one layer to model the data. Freeze it, and treat its output as a new data set. Train the next layer on that. Repeat. Each step is a small, tractable problem, and each is greedy: it commits to the best layer it can find now and does not go back. The resulting “deep belief net” read handwritten digits more accurately than the best general-purpose methods of the day — 1.25% errors on the standard MNIST test, against 1.4% for support vector machines and 1.5% for conventionally trained networks — and it could also be run in reverse, to generate digits of its own. [Hinton et al.]

Companion papers the same year by Hinton & Salakhutdinov, by Bengio and colleagues, and by Ranzato and colleagues showed that the strategy was general, and the field regrouped around it under a new name: deep learning. Networks initialized layer by layer produced the first large gains in speech recognition between 2009 and 2012. Deep networks then won the ImageNet image-recognition contest in 2012, and translation, game playing, protein folding and language models followed. The 2018 Turing Award went to Bengio, Hinton and LeCun; the 2024 Nobel Prize in Physics went to Hopfield and Hinton “for foundational discoveries and inventions that enable machine learning with artificial neural networks.” [Hinton & Salakhutdinov] [Hinton et al. 2012] [Nobel Prize]

What lasted, and what did not

The specific recipe had a short life. By about 2012, better activation functions and initialization, graphics processors and much larger labelled data sets made it possible to train deep networks directly, and layer-by-layer pre-training with restricted Boltzmann machines dropped out of everyday practice. What lasted was the demonstration that depth can be trained at all, and two ideas the demonstration carried: that a model can be built in stages, each stage re-describing the data for the next; and that a model can learn from unlabelled data first and be adjusted to a task afterwards. The “pre-trained” in the name GPT refers to that second idea, realized by entirely different means. [Glorot et al.] [LeCun, Bengio & Hinton]

So what, exactly, was the idea — and how new was it? Stripped of neural-network vocabulary, the 2006 algorithm is a greedy structure search: grow a model by adding one component at a time, keeping what helps. That pattern is much older than deep learning, and it was already at work in a quite different research tradition. In a technical report of May 2005, dated a month before the deep-belief-net manuscript was submitted and following an earlier report of August 2004, Aleks Jakulin and Irina Rish built classifiers by adding, one at a time, explicit interactions — named groups of variables that matter jointly — to a probabilistic model. One algorithm adds hidden layers; the other adds visible interactions.

Setting the two side by side does three things. It shows which parts of the breakthrough were new and which were inherited: the genealogy in sections 4 and 7 reaches back to the 1960s. It isolates a choice that still divides the field: let a model learn its own internal features, which is powerful but hard to inspect, or name its structure explicitly, which is readable but limited. And it reveals a shared mathematical skeleton, set out in sections 8 and 9, in which claims that two methods are “really the same” can be tested rather than asserted.

Two cautions. Credit for the individual ingredients is disputed, as section 4 discusses; what is not in doubt is that 2006 is where the revival is conventionally dated, including by its protagonists. And the two papers differ greatly in influence: one became among the most cited in machine learning, the other is a specialist contribution to probabilistic classification, co-written by the person for whom this report was prepared. They are paired because their structure is comparable, not because their impact was.

WhenWhat happened
1965–71Ivakhnenko & Lapa’s GMDH grows networks layer by layer from small interaction terms, keeping units that validate well (section 4).
1985–86The Boltzmann machine and its restricted form, later called the RBM; backpropagation is popularized.
1991Schmidhuber’s history compressor pre-trains a hierarchy of sequence predictors one level at a time, without labels.
late 1990sNeural networks fall out of favour; support vector machines and graphical models dominate.
Aug 2002Contrastive divergence makes RBMs practical to train.
Aug 2004Jakulin, Rish & Bratko: first Kikuchi-Bayes report (RC23314). Classifiers built from explicit interactions, using an earlier selection procedure.
May 2005Jakulin & Rish: report RC23602. Greedy search over interactions in a Markov network, with model averaging.
Jun 2005Hinton, Osindero & Teh submit the deep-belief-net manuscript: deep networks trained greedily, layer by layer. Accepted November 2005.
Nov 2005Jakulin presents the interaction search in a talk at the Gatsby Unit, UCL (date from his recollection).
Jul 2006The deep-belief-net paper appears in Neural Computation; Hinton & Salakhutdinov’s companion paper appears in Science.
Sep 2006Jakulin & Rish’s interaction search is published at ECML.
Dec 2006Bengio et al. and Ranzato et al. present related layer-wise methods at NIPS.
2009–12Pre-trained deep networks transform speech recognition.
Oct 2012A deep convolutional network wins ImageNet, trained end to end with no layer-wise pre-training.
Jun–Oct 2018Pre-train-then-fine-tune returns for language (GPT in June, BERT in October). The Turing Award for 2018 goes to Bengio, Hinton and LeCun.
Oct 2024Nobel Prize in Physics to Hopfield and Hinton.

Timeline. The two algorithms compared in this report (shaded: green for interaction search, purple for deep belief nets) against what came before and after. The dates for the two papers are discussed under “On chronology” in section 6.

Background: five ideas the report relies on

1. Structure versus parameters. A statistical model has two kinds of ingredient. Its structure says which pieces exist: which variables are connected, how many layers there are, which groups of variables are allowed to act together. Its parameters are the numbers attached to those pieces. Fitting the numbers for a fixed structure is ordinary training. Choosing the structure itself is structure search, and it is the harder problem, because the choices are discrete and there are astronomically many of them.

2. Why the search is greedy. With only 20 input variables there are more than a million possible groups of variables, and the number of ways to choose a set of groups is a number with over 300,000 digits. No algorithm can try them all. A greedy search does the simplest sensible thing: start with a minimal model, look at every way of adding one piece, keep the best, and repeat. It never reconsiders, so it can miss the best overall design; but it is fast, and often good enough.

3. Interactions. Two variables interact when the effect of one depends on the other. On the Titanic, how much being a woman improved the chance of survival depended on the class of ticket. In the extreme case, a light controlled by two switches is on exactly when the switches differ: neither switch alone tells you anything about the light, and the pair tells you everything. A model that examines variables one at a time, such as naive Bayes, cannot see this. A model that includes an interaction between the two can. Interactions among three or more variables are called higher-order or multi-way. The variables an interaction involves are its scope; in the graph vocabulary used below, a scope is a hyperedge.

4. Hidden variables and depth. Instead of naming interactions among the observed variables, a model can invent new variables — latent or hidden ones — that stand for patterns in the data: “there is a vertical stroke here,” “this shape is a loop.” Inputs that tend to act together are then explained by one hidden unit. A layer is a set of such features, and a deep model stacks layers, so that features are built from features. This is how a neural network represents interactions: implicitly, through learned features, rather than by listing them.

5. The two kinds of model. Jakulin & Rish use a Markov network: a probabilistic model that multiplies together one factor for each chosen group of variables, with no direction of cause and effect. Choosing the groups is their structure search. Hinton, Osindero & Teh use the restricted Boltzmann machine (RBM), a small Markov network of a special shape: one layer of visible units for the data, one layer of hidden units for features, and connections only between the two layers. An RBM is trained by an approximate procedure called contrastive divergence (CD). Stacking RBMs, each trained on the features of the one below, gives a deep belief net (DBN); adding the layers one at a time is their structure search. Both kinds of model share a nuisance: the normalizing constant, or partition function, that turns a product of factors into probabilities is usually far too expensive to compute. Each paper sidesteps it in its own way (sections 5 and 9).

How to read this report

Sections 1–4 are the core, and need nothing beyond the background above. Sections 5–7 go one level down into the machinery, for readers comfortable with machine learning. Sections 8 and 9 restate the comparison in the language of ordered sets, logic and category theory; they are written for the mathematically curious and can be skipped without losing the story. Every section opens with a short summary marked In plain terms, and technical words are collected in the glossary. The many qualifications of the form “this is an analogy, not an equivalence” are deliberate: the report is about resemblances between ideas, and tries not to overstate them.

1. The core duality

In plain termsBoth algorithms build a model piece by piece. The deep belief net’s pieces are layers of invented features: each new layer describes the data in a new vocabulary. Interaction search’s pieces are named groups of the original variables. One hides its structure inside learned features; the other writes it down. “Duality” is used loosely, to mean two complementary ways of organizing the same kind of construction.

These two algorithms suggest a useful structural duality: one builds a hierarchy of learned representations; the other builds a collection of explicit interactions. Hinton’s grows a latent vocabulary in which further dependencies can be represented. Jakulin & Rish search among named groups of observed variables, reusing estimated submodels. The central question is what mathematical space represents the possibilities, and how does an algorithm traverse it?

One grows depth; the other grows and combines interaction scopes. Both construct a model incrementally, but they move through different spaces: a sequence of latent representation spaces on one side, a partially ordered family of explicit structures on the other. “Duality” here names this complementary organization, not a theorem asserting equivalent model classes. That distinction lets us follow the connections to lattices, logic, and category theory without reducing the comparison to training speed.

2. What each greedy search does

In plain termsHinton’s algorithm: learn a layer of features; treat those features as the new data; repeat; then polish the whole stack together. Jakulin & Rish’s algorithm: start from a model that knows only how common each class is; repeatedly add the one group of variables that most improves prediction; then, rather than trusting the last model alone, average the predictions of the models met along the way.

Hinton, Osindero & Teh — greedy layer-wise learning

The architecture fixes the available layer sizes; learning constructs its representation one layer at a time. Train an RBM, use its hidden activities as data for the next RBM, and repeat before global up–down fine-tuning. Structurally, the important move is re-representation: the next model operates on learned features rather than the original variables. Hinton, Osindero & Teh explicitly compare this stagewise construction with boosting, but replace reweighting examples with re-representing them. Their variational improvement argument applies to the idealized learning construction; practical contrastive divergence does not retain the guarantee. [Hinton et al.]

Example: reading handwritten digits

The 2006 network learned from the MNIST collection: 60,000 images of handwritten digits, each 28 × 28 pixels. The first layer learns 500 features of the pixels. The second learns 500 features of those features. A third, larger layer of 2,000 units learns which combinations of second-layer features go with which of the ten digit labels. No layer below the top is told what to look for; each simply learns to model what the layer beneath it produces. Only after all the layers are in place is the whole stack adjusted together, the step called fine-tuning.

Jakulin & Rish — greedy interaction search

The model is an undirected Markov network over attributes and class, represented as a hypergraph: a collection of hyperedges, including higher-order and non-maximal ones. Each contributes a potential built from reusable Dirichlet–multinomial submodels through the Kikuchi region construction. Adding an interaction changes the model and may change its overlap corrections, but does not require relearning every submodel. The structural move is explicit: extend the collection of variable groups whose dependencies are represented.

The search starts with the class-only hyperedge {Y}, considers extensions by attributes, and chooses the candidate with the best model score: forward selection with one-step look-ahead.

Candidates are scored by conditional likelihood and a degrees-of-freedom structure prior. The important change from marginal interaction filtering is that a candidate is evaluated in the context of the current model: useful interactions need not be useful independently. Prediction then averages over evaluated structures using approximate Bayesian model averaging. Search therefore constructs both a path and a collection of alternatives, not merely a final winning graph. [Jakulin & Rish]

Example: who survived the Titanic

Given a table of passengers — sex, status (ticket class or crew), age group — and whether each survived, the search begins with a model that knows only the overall survival rate. It first adds the single most informative attribute, sex. Then status, then age. Having used each attribute on its own, it finds that two combinations add more: status together with sex, and status together with age. The result is a short, readable list of what mattered and what mattered jointly. On tic-tac-toe positions the same procedure, in a fraction of a second, picks out the groups of squares a human player watches: the corners and centre, then the diagonals and edges. [Jakulin & Rish]

3. Contrast: efficiency, depth, speed, pros and cons

In plain termsThe table lines the two algorithms up on eleven counts. The short version: the deep belief net is costly to train, hard to read, and suited to raw, high-dimensional data such as images; interaction search is quick, readable, and suited to small tables of discrete data. “Depth” means different things on the two sides: layers of abstraction for one, how far the search has gone for the other. The two were never benchmarked against each other; they solve different problems.

The deepest contrast is where structure is made explicit. A DBN learns intermediate coordinates and composes them; interaction search keeps the original coordinates and selects groups of them. Computational tradeoffs matter because they make these traversals feasible, but they do not define the structural analogy.

 Hinton, Osindero & Teh — greedy layer-wise DBNJakulin & Rish — greedy interaction search
What is exploredWeights of a fixed, fully-connected deep netDiscrete hypergraph of interactions (which cliques to include)
Unit of greedy growthOne latent layer at a timeOne interaction (hyperedge) at a time
Cost per greedy stepExpensive: train an RBM by contrastive divergence (Gibbs sampling + gradient, many epochs); no closed formReuse submodels; score candidate hyperedges and update overlap corrections
Overall speedIterative training; fast approximate bottom-up recognitionReported search on 46 datasets in <9 min, vs >686 min for BN classifiers; not exhaustive or a DBN benchmark
“Depth”Depth of latent abstraction — the point; this is what made deep nets trainableDepth of search (number of interactions, hyperedge cardinality k); representationally flat
Justification for greedVariational improvement for the idealized construction, not practical CDHeuristic hill-climb; no global guarantee, but a df-based prior controls complexity
ApproximationCD approximates weight updates; bottom-up recognition approximates the posteriorKikuchi / cluster-variation region graph for the joint
InterpretabilityDistributed latent features; interpretation requires examining learned representationsExplicit, named variable groups; interaction information can help interpret dependencies
Data regimeHigh-dimensional, perceptual, lots of dataDiscrete tabular data, tens of attributes, small-sample-friendly
Main strengthLearns a hierarchy of features from raw input; scalesReusable submodels + explicit interactions + class probabilities; k-way and cyclic structure
Main weaknessCostly, hyperparameter-heavy, opaque, no explicit structure discoveryMyopic (one-step look-ahead), shallow, candidate set explodes with many attributes / high k

Exhibit 1. Side-by-side contrast. Hinton grows depth (latent representation layers); Jakulin & Rish grow a collection of interactions, potentially increasing their order. Number of selected interactions and interaction cardinality are distinct.

4. A genealogy of the idea

In plain termsNeither algorithm came from nowhere. One descends from physics-inspired neural networks, the Boltzmann machine and its relatives. The other descends from statistical methods for choosing which interactions to include in a model. Both lines draw on the same older mathematics, and both have a conceptual ancestor in GMDH, a 1960s method that already grew networks layer by layer from small interaction terms. The arrows in the diagram mean “resembles, and came later,” not “was directly inspired by.”

Both 2006 algorithms belong to a broader family of greedy, stagewise, constructive learning. Their representations connect to statistical mechanics and information theory, while their growth rules connect to older work on feature construction and model selection. The genealogy below follows these ideas through two research traditions. Its arrows indicate conceptual development and methodological resemblance; they do not, by themselves, claim documented direct influence between every adjacent pair.

Open figure 1 at full size

How to read it. Time runs downward. The left column is the neural-network line; the right column is the statistical line. Dashed boxes are earlier precedents. Stars mark the two 2006 papers.

neural / energy-based graphical-model / info-theoretic Schmidhuber-flagged precedent
Genealogy of two greedy structure-search algorithms, with earlier precedents A shared statistical-mechanics and information-theory substrate at top; GMDH (Ivakhnenko and Lapa 1965-71) as a dashed cross-cutting precedent that did greedy layer-wise growth and interaction selection, feeding both branches; a neural branch (Boltzmann machine, RBM, an unsupervised pre-training precedent, contrastive divergence) ending in Hinton, Osindero and Teh 2006; a graphical-model branch (log-linear stepwise selection, semi-naive Bayes/TAN, random-field feature induction, region graphs) ending in Jakulin and Rish 2006. Greedy structure search: a genealogy of representations and moves Neural / energy-based Graphical-model / info-theoretic Schmidhuber-flagged precedent Shared substrate — Gibbs / Ising free energy + information theory Lenz–Ising (1920s) · Amari adaptive net (1972) · Kikuchi CVM (1951) · Shannon (1948) GMDH — greedy layer-wise nets built from interaction terms pruned by validation · Ivakhnenko & Lapa · 1965–71 (8 layers) · prefigures both greedy + stagewise Boltzmann machine Ackley, Hinton & Sejnowski · 1985 RBM (Harmonium) Smolensky · 1986 Unsupervised layer-wise pre-training history compressor · Schmidhuber 1991 Contrastive divergence Hinton · 2002 ★ Greedy layer-wise DBN Hinton, Osindero & Teh · 2006 Log-linear stepwise selection Bishop·Fienberg·Holland · 1975 Semi-naïve Bayes · TAN Kononenko 1991 · Friedman 1997 Feature induction, random fields Della Pietra et al. · 1997 Region graphs / GBP Yedidia–Freeman–Weiss · 2005 ★ Greedy interaction search Jakulin & Rish · 2006 Both 2006 · greedy-constructive structure search GMDH did layer-wise growth + interaction selection 40 years earlier Cousins by method: forward stagewise modelling / boosting · cascade-correlation
Exhibit 2. Two research traditions and their shared mathematical background. Solid boxes identify central methods; dashed boxes highlight earlier constructive-learning precedents. Connections organize ideas, not a complete citation or priority history.

The two lineages

The neural / energy-based branch connects Ising-style interactions and adaptive networks with learnable energy models: the Boltzmann machine (Ackley, Hinton & Sejnowski 1985), Smolensky’s Harmonium (1986, later the RBM), contrastive divergence (Hinton 2002), and the 2006 DBN. The representational changes are the thread: introduce latent variables, restrict within-layer connections, then compose learned layers. An RBM is also related to an infinite directed network with tied weights; untying successive layers is part of Hinton et al.’s construction. The resulting DBN has an undirected top pair and directed connections below.

The graphical-model / information-theoretic branch connects hierarchical log-linear interaction selection (Bishop, Fienberg & Holland 1975), naive-Bayes extensions (Kononenko 1991; Friedman, Geiger & Goldszmidt 1997), feature induction in random fields (Della Pietra et al. 1997), and Kikuchi region constructions. Here the vocabulary is explicit: terms, edges, hyperedges, and overlaps. Jakulin & Rish share the greedy-feature-induction pattern, while using reusable closed-form submodels to make higher-order candidates practical. This is a relationship between construction methods, not a claim that all these models are the same family.

The precedents that matter

GMDH (Ivakhnenko & Lapa 1965; Ivakhnenko 1971) is an especially revealing common precedent. It grows layers of polynomial units, combines a small number of inputs at each unit, and selects candidates by an external validation criterion. Composition builds more complex interactions from simpler ones. It therefore brings together three ideas central to this comparison: layer-wise growth, interaction construction, and selection among candidate components. Calling it a conceptual ancestor preserves that insight without assigning exclusive invention or asserting a direct historical transmission. [Ivakhnenko]

Unsupervised layer-wise pre-training (Schmidhuber 1991) provides another precedent: the neural history compressor builds a hierarchy of temporal predictors, passing information not predicted at one level to the next. Its higher levels operate on transformed representations of a sequence. The connection to DBNs is stagewise representation learning, not identity between recurrent prediction and stacked RBMs. Compression also links this branch to complexity-sensitive model selection on the explicit-interaction side. [Neural Sequence Chunkers]

The energy-based root is mathematical, not merely metaphorical. Kikuchi cluster variation and energy-based neural models share the language of interactions and free energy. Yedidia, Freeman & Weiss connect belief-propagation fixed points to stationary points of Bethe free energy, and develop generalized belief propagation for region-based approximations. This is a precise bridge between a representation, an objective, and a traversal procedure, rather than an identity between a free-energy function and an algorithm. [Yedidia et al.]

A note on genealogy: Schmidhuber’s historical essays help locate these precedents. The report uses the technical connections, rather than adopting the accompanying credit disputes. Similarity, historical precedence, and documented influence are different relations; a useful genealogy can display the first two without pretending to establish the third.

5. Contrastive divergence and structure search

In plain termsContrastive divergence is the procedure that tunes an RBM’s weights. It adjusts the numbers inside a fixed design; it does not choose the design. It still belongs in a story about structure search, for three reasons: it is the kind of inner loop a structure search has to call; the error it corrects points at structure the model is missing; and tuning weights lets hidden units specialize, which organizes a network without changing its wiring.

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?” Its relation to structure search is still instructive:

Thus continuous fitting and discrete search are not rival definitions of learning. They are different ways of moving within and between representations: adjust coordinates inside a family, or change which components the family contains.

6. Stacking RBMs ≈ multi-way interaction search

In plain termsThis is the technical heart of the comparison. If the hidden units of an RBM are summed out, what remains is a model of the visible variables alone, and in it each hidden unit has turned into a bundle of interactions among the visible variables it connects to: pairs, triples and beyond. A hidden unit is thus a compact, indirect way of encoding many interactions at once, where a hyperedge is a direct way of naming one. The two algorithms are doing related things in different notations — related, not identical, as the qualifications below spell out.

The analogy between stacking RBMs and multi-way interaction search is deeper than their shared incremental style. For binary visible and hidden units, marginalizing the hidden units of an RBM gives a product-of-experts representation:

log P(v) = Σi aivi + Σj softplus(bj + Σi wijvi) − log Z

Each softplus term is a function of the binary visibles in one hidden unit’s receptive field. Its multilinear expansion can contain interactions of every order up to the size of that field: vi, vivk, vivkvl, and so on. A hidden unit therefore encodes a coupled collection of interaction coefficients. Adding hidden units adds factors; another layer models relations among learned features. This provides a concrete bridge between latent feature composition and explicit interaction selection. [Montúfar & Rauh]

The two descriptions expose different structure. A hyperedge names a scope and permits a potential on that scope; an RBM factor gives a compact, parameter-constrained potential through a hidden variable. Fixed-size RBMs are not arbitrary higher-order models in different coordinates, and another layer need not strictly raise interaction order. The valuable analogy survives these qualifications: explicit search chooses which interaction scopes to represent; latent learning discovers features whose induced interactions need not be listed individually.

On chronology

RBMs (Smolensky 1986) and contrastive divergence (Hinton 2002) predate both main papers. Kikuchi-Bayes RC23314 is dated August 30, 2004; RC23602 is dated May 6, 2005. The DBN manuscript was submitted June 8 and accepted November 8, 2005, before its 2006 journal issue; Jakulin & Rish appeared at ECML 2006. These are different kinds of dates, not a uniform measure of research priority. The 2004 report also used an earlier interaction-selection procedure. What matters here is the convergence of representational ideas, against the much older background of constructive learning. [2004 report] [2005 report]

7. The evolution of structure search

In plain termsA family tree of algorithms that build models piece by piece, from 1960s statistics to 2006. Each box is a method. Each arrow is labelled with the one idea that was added on the way from the method above to the method below. Whatever the method, the routine is the same: add a piece, check whether it helps, keep it or drop it.

Read the diagram’s edges as the payload: each labels a representational move, a change in scoring, or a methodological connection. Top-to-bottom is roughly chronological; purple follows energy-based implicit structure, teal follows explicit graphical models, and GMDH is a dashed common precedent. The recurring move is add or construct a piece, evaluate it, keep or discard. What changes is the piece: regression term, tree edge, DAG edge, undirected feature, hyperedge, or learned layer. Not every arrow is a direct derivation; tree optimization, for example, has a different traversal from greedy DAG search.

Open figure 2 at full size

How to read it. Start at the top and follow the arrows down. Teal boxes are explicit, statistical methods; purple boxes are neural ones; the dashed grey box is GMDH. The two starred boxes are the 2006 papers. The diagram is wide: scroll sideways, or open it at full size.

G A Forward stepwise selection statistics · ~1960 G GMDH Ivakhnenko & Lapa · 1965 A->G depth + interaction units + validation pruning L Log-linear stepwise selection Bishop·Fienberg·Holland · 1975 A->L select interaction terms K Greedy Bayes-net search / K2 Cooper–Herskovits 1992 · Heckerman 1995 A->K + Bayesian score over DAGs KB Kikuchi-Bayes interaction search Jakulin, Rish & Bratko · 2004 G->KB interaction units, selected HN ★ Greedy layer-wise DBN Hinton, Osindero & Teh · 2006 G->HN polynomial units → RBMs C Chow–Liu trees 1968 C->K from optimal trees to searched DAGs T Tree-augmented naive Bayes Friedman et al. · 1997 C->T condition the tree on the class D Feature induction, random fields Della Pietra et al. · 1997 L->D undirected max-ent; gain = ΔKL BM Boltzmann machine Ackley, Hinton & Sejnowski · 1985 R RBM + contrastive divergence Hinton · 2002 BM->R restrict graph; short-chain gradient (CD) F Being Bayesian about structure Friedman–Koller · 2003 K->F average structures, stop picking one GD Discriminative BN classifiers Grossman–Domingos · 2004 T->GD score by conditional likelihood D->KB closed-form Kikuchi; k-way hyperedges R->HN stack RBMs greedily JR ★ Greedy interaction search Jakulin & Rish · 2006 F->JR average along the hill-climb GD->JR + degrees-of-freedom prior KB->JR score whole structures, not one-by-one HN->JR convergent: implicit vs explicit multi-way interactions
Exhibit 3. Evolution of structure search: representations and methods in the nodes, conceptual moves on the edges. The brown dashed link highlights implicit versus explicit multi-way structure. It expresses the analogy in section 6, not model equivalence or documented influence.

8. Foundations: structure search as search over a lattice

In plain termsThis section and the next are the most abstract, and can be skipped. The idea is that the possible structures of a model can be arranged by “contains”: a model with interactions A and B sits above the models that have only A or only B. Mathematicians call such an arrangement a partially ordered set, or a lattice when it is well behaved. Searching for a structure is then a walk through this arrangement, and several classical tools apply: Möbius inversion, a systematic form of inclusion–exclusion that prevents double counting where interactions overlap; logic, in which adding a piece is like adding a condition to a statement; and category theory, a general language for composition. Throughout, the section separates what is a theorem from what is only an analogy.

Lattices make the comparison productive because they describe how representations can be assembled, refined, or related by inclusion. But there is more than one lattice in play. Keeping their elements distinct reveals the bridges to logic and category theory, and tells us which traversal algorithms can be compared.

8.1 Interaction scopes, model collections, and hierarchical closure

Gist: three different orderings are in play — of single interactions, of whole models, and of the overlaps between interactions — and they should not be confused.

Let A be the attributes, with the class Y included in every candidate interaction. The scope lattice is 2A: a subset S represents S ∪ {Y}, so its bottom ∅ represents the class-only scope {Y}. Join is union and meet is intersection. An upward edge adds an attribute to one interaction.

A model, however, contains a collection of interactions. For a fixed candidate vocabulary E, the unconstrained collections form 2E, with the class-only component understood as always present. Adding an interaction moves in this model lattice, not necessarily upward along a single chain of scopes. For example, {{a,Y},{b,Y}} contains two interactions and differs from the single scope {a,b,Y}. Actual search rules select which moves through these spaces are admissible.

When a representation requires every selected interaction’s predecessors, its structures are order ideals of the prerequisite poset. These form a distributive lattice under union and intersection; Birkhoff’s theorem supplies the converse representation for finite distributive lattices. The ideals are also an accessible, union-closed family, hence a poset antimatroid: a maximal selected element can be removed while preserving feasibility. This makes legal build orders mathematically explicit. It is not the same as simplicial shelling, nor an automatic description of every Jakulin–Rish move or a guarantee for its score.

Open figure 3 at full size

How to read it. Each box is a possible interaction among three attributes a, b, c (always together with the class Y). Moving up a line adds one attribute. The +1, +1, −1 badges show the correction for overlap: two selected groups that share {c} would count that shared part twice, so it is subtracted once.

growth of one interaction scope Möbius-derived region counts
The scope lattice, an example growth path, and region counting weights Boolean lattice of attribute scopes. Teal marks the growth of one scope. Purple independently overlays two selected maximal regions, acY and bcY, with weights one, and their cY overlap with weight minus one. The interaction lattice (subsets of {a, b, c}, each ∪ {Y}) one scope grows upward Möbius-derived region counts {a,b,c} {a,b} {a,c} {b,c} {a} {b} {c} ∅ ↦ {Y} +1 +1 −1 c₍c₎ = 1 − (1+1) interaction order →
Exhibit 4. Two views on the same attribute diagram. Teal grows one interaction scope; a whole model may contain several scopes. Purple separately shows the region poset generated by {a,c,Y} and {b,c,Y}: both have count +1 and their shared {c,Y} has count −1. These weights are derived by Möbius inversion, not individual values of its kernel.

8.2 Möbius inversion connects representations

Gist: one piece of arithmetic, Möbius inversion, separates “what this group adds” from “what its parts already contributed.” It appears on both sides of the comparison, applied to different quantities.

Möbius inversion is the common arithmetic behind several ways of separating higher-order structure from lower-order contributions. On a specified finite region poset, a recursive factorization PR = ∏S≤R ΦS gives, for positive factors, [Rota]

log ΦR = ΣR′ ⊆ R μ(R′, R) · log P(vR′),

The counting-number recursion c(R) = 1 − ΣS>R c(S) has the solution c(R) = ΣS≥R μ(R,S). Thus region counts are derived from the Möbius kernel. Interaction information is an alternating transform of subset entropies, with sign conventions varying between authors. Moments and cumulants are connected by Möbius inversion on a partition lattice; derivatives of a log-partition function produce cumulants. [Speed]

The connection is substantial: inclusion–exclusion isolates what belongs to a combination beyond its component parts. The functions and posets differ, so the predictive score, region counts, and global partition function are not all the same transform. The shared tool is incidence algebra, not an identity between the quantities it acts on.

8.3 Traversal geometry and the role of the score

Gist: the ordering says which moves are possible; the score says which is best. Greedy search comes with a guarantee only for scores with diminishing returns, and prediction scores are not automatically of that kind — the two-switch example from the background shows why.

For discrete variables, joint entropy is a monotone submodular function on the subset lattice, giving a polymatroid. This makes submodular optimization a natural neighbor of structure search. The lattice tells us which moves exist; an antimatroid can specify which build orders are legal; the objective tells us which move is preferred.

Those roles must not be collapsed. The familiar 1 − 1/e bound concerns normalized monotone submodular maximization under a cardinality constraint, not arbitrary forward selection. Target information can exhibit increasing returns: if Y = A XOR B for independent fair bits, neither attribute alone reveals Y but the pair does. A conditional model score therefore needs its own analysis, and a degrees-of-freedom penalty need not be modular in the chosen model representation. The useful bridge is to a family of traversal methods, not an inherited guarantee. [Krause & Guestrin]

8.4 The bridge to category theory

Gist: category theory restates “refine,” “combine” and “compose” in one language, and gives a precise way to ask whether locally fitted pieces can be extended to one consistent whole.

A poset is a thin category: there is one morphism x → y whenever x ≤ y. Covering relations generate these morphisms by composition. A bounded lattice has products (meet), coproducts (join), an initial object (bottom), and a terminal object (top). This translates refinement and combination directly into categorical language. Monotone maps compare ordered representations; Galois connections are adjunctions between such poset categories.

There is a second bridge through local information. Assign to each region R the space of distributions on its variables, with marginalization maps from larger regions to smaller ones. This is a contravariant functor, a presheaf; choosing compatible submodels gives local data whose global extension can be studied. In the sheaf-theoretic contextuality framework, failure to extend compatible empirical data becomes a precise obstruction. Existence of an extension is not the sheaf axiom of unique gluing, and a joint distribution need not be unique. When submodels are consistent marginals of one common joint distribution, extension is already witnessed. The connection supplies a way to ask the local-to-global question, not a claim that this classifier is contextual. [Abramsky & Brandenburger]

Region counting also has a categorical reading. Order regions by inclusion and orient morphisms toward larger regions; the c(R) satisfying ΣS≥R c(S) = 1 form a weighting. Their sum is the Euler characteristic of this finite poset category, not each individual count. For two maximal overlapping regions the weights are 1, 1, −1, whose sum is 1. [Leinster]

Finally, Markov categories provide a language for composing stochastic maps. Learned recognition layers can be viewed as kernels from one representation space to the next, with composition summing out intermediate states. This describes the passage between representations, not the whole undirected top-level DBN model or its training rule. Conditioning needs further structure; it is not automatically an adjoint to marginalization. [Fritz]

8.5 The bridge to logic

Gist: choosing a structure resembles choosing a hypothesis in logic — a model with more interactions asserts more — and summing out a variable resembles the quantifier “there exists.” Both are analogies with stated limits.

Explicit structures also admit a logical reading. Give each candidate interaction an atom meaning “this interaction is included.” Adding selected atoms strengthens a conjunction: M ⊆ N implies that the conjunction for N entails the conjunction for M. This reverses inclusion when read as entailment. Collections of selected atoms are not the entire Lindenbaum–Tarski algebra of formulas, but they make refinement tangible.

The learning-theoretic relatives are version spaces (Mitchell 1977) and ILP refinement operators (Plotkin 1970; Muggleton 1991): search through hypotheses ordered by generality or subsumption. Where a least general generalization exists, it is a least upper bound in the order running from specific to general. Such hypothesis spaces need not all be lattices. Formal concept analysis gives a more literal bridge: the object–attribute Galois connection generates a concept lattice, linking descriptions to the objects satisfying them.

Three broader correspondences explain why these bridges recur. Curry–Howard–Lambek relates suitable logics, typed calculi, and categorical models; Stone duality relates Boolean algebras contravariantly to Stone spaces; Lawvere’s quantifiers-as-adjoints relates existential and universal quantification to substitution. These are precise correspondences with specified domains, not a theorem that all logics, lattices, and categories are identical. [Lawvere]

Marginalization provides a particularly useful analogy with ∃: both eliminate a variable along a projection. Existential quantification aggregates truth values by disjunction; marginalization aggregates probability mass by summation. For finite spaces, pushforward of mass and pullback of functions are adjoint under the sum pairing, ⟨π*p, f⟩ = ⟨p, f ∘ π⟩. This is not the same adjunction as direct image and inverse image in the order of predicates. It is a bridge between calculi of elimination, not an identification of truth and probability.

Open figure 4 at full size

How to read it. Four colour-coded strands of mathematics flow down to structure search, the gold box at the bottom. The label on each arrow names the idea that links the two boxes it joins. The diagram is wide: scroll sideways, or open it at full size.

G BOOL Boolean algebra Boole 1854 · propositional logic HEY Heyting algebra intuitionistic logic · 1930 BOOL->HEY drop excluded middle STONE Stone duality Stone · 1936 BOOL->STONE algebra ⇄ space LAT Lattice theory Birkhoff · 1933–40 BOOL->LAT order abstraction CHL Curry–Howard–Lambek propositions ≈ types ≈ objects HEY->CHL proofs as programs TOPOS Topos & sheaves internal logic · Lawvere–Tierney 1970 STONE->TOPOS Boolean / Stone duality LAWQ Quantifiers as adjoints Lawvere · 1969 LAWQ->TOPOS internal logic MARKOV Markov categories categorical probability · Fritz 2020 LAWQ->MARKOV ∃ and marginalization CHL->TOPOS categorical logic GAL Galois connections / closure Ore 1944 · Tarski consequence LAT->GAL closure operators MOB Möbius inversion incidence algebra · Rota 1964 LAT->MOB incidence algebra VSILP Version spaces · ILP generality order · Mitchell 1977 / Plotkin 1970 LAT->VSILP generality order GAL->TOPOS Galois connection = adjunction FCA Formal concept analysis concept lattice · Ganter–Wille 1982 GAL->FCA intension / extension SS ★ Structure search Jakulin–Rish · Hinton · 2006 MOB->SS Möbius-derived counts TOPOS->MARKOV copy–discard categories TOPOS->SS local-to-global extension MARKOV->SS stacking = composition VSILP->SS refinement-guided search FCA->SS concept lattice
Exhibit 5. Four threads: logic (amber), lattice (teal), category (purple), and inductive learning (green). The graph connects refinement, closure, local-to-global extension, and composition. Solid arrows organize the conceptual strands; dashed links cross between them. Some links are theorems in specified settings, others are structural analogies explained above; neither arrow style asserts direct historical influence.

8.6 Related algorithms for lattices and partial orders

Gist: where interaction search sits among classical algorithms that work on ordered sets — what it shares with each, and how it differs.

(“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:

Related algorithmShared lattice/poset ideaHow Jakulin–Rish differs
Apriori / levelwise mininganti-monotone search of the subset latticegreedy score-guided path, not full border
Version spaces / ILP refinementrefinement in a generality / subsumption orderprobabilistic score, not logical consistency
Greedy submodular / greedoidfeasible extensions and score propertiesone-step look-ahead; separate hypotheses needed for guarantees
Fast Möbius/zeta; subset convolutioninclusion–exclusion over the latticeregion corrections reuse submodels, not a full subset transform
Koivisto–Sood exact discovery (2004)subset DP and transforms for directed structureslocal search over a different model family and score
Junction tree (1988)message passing on a separator posetoverlapping regions need not have a junction-tree factorization
Generalized belief propagation (2005)region-graph counting numbersclosed-form prediction construction, not GBP fixed-point iteration
Iterative proportional fitting (1940)fit potentials on the margin latticereuses estimated marginals instead of iteratively fitting all constraints

The comparison has two independent axes: how a representation is assembled and how information is combined within it. A greedy walk, border enumeration, and subset dynamic programming answer different traversal questions. Clique separators, Möbius corrections, and fitted marginal constraints answer different composition questions. Locating Jakulin–Rish at their intersection is more informative than assigning it a single closest relative.

9. The two algorithms through the lattice lens

In plain termsSeen through the mathematics of section 8, the two algorithms are complementary. One moves through a space of explicit, named interactions; the other builds a sequence of learned vocabularies. They are not one algorithm in two disguises, but each makes the other easier to understand.

The same lenses can now be applied to both algorithms. Explicit interaction search exposes the combinatorics of its representation. A DBN learns intermediate coordinates, so much of its interaction structure appears only after latent variables are marginalized. Depth forms an ordered sequence, but the maps between layers matter at least as much as that sequence.

Lattice-algorithm familyJakulin & RishHinton (deep belief net)
Representation spaceCollections of explicit interaction scopes; overlap regions derived from themA sequence of latent spaces with learned maps between adjacent layers
TraversalExtend a structure, evaluate candidate interactions, retain and average evaluated modelsLearn one representation, use it as the input vocabulary for the next, then fine-tune
Combination ruleMultiply local factors with corrections for their overlapping scopesCompose directed stochastic layers beneath an undirected top-level model
Interaction latticeSelected hyperedges name scopes explicitlyMarginalized hidden units induce coupled coefficients across subsets of visibles
Incremental growth (shared)Add one component, or enlarge a candidate scope, according to the search rulesAdd a learned stage that represents relations among the preceding features
Closest structural languageSet systems, refinement orders, incidence algebra, and local-to-global assemblyCompositional representations, latent-variable models, and stochastic maps

So the two algorithms are complementary ways of constructing representations. One traverses a vocabulary of named interactions; the other learns a vocabulary and then learns over it. The interaction lattice connects them because latent factors can encode multi-way dependencies that explicit hyperedges name directly. The genealogy connects them because both extend an older constructive pattern: build from simpler components, evaluate what the composition adds, and continue.

The mathematical lesson is to distinguish objects, relations, and moves. Subsets represent scopes; collections represent models; region posets organize overlaps; stochastic maps connect learned spaces. Greedy paths, levelwise traversal, dynamic programming, and layer-wise composition exploit different parts of those structures. That is the point of bringing the traditions together: not that their algorithms are identical, but that their representational choices become intelligible in a shared mathematical vocabulary.

A technical qualification

For classification with observed attributes, P(y|x) = Φ(x,y) / Σy′ Φ(x,y′): the global partition function cancels rather than being computed by region counting. Compatible junction-tree factorizations permit exact local assembly; cyclic region constructions are more general but need not be normalized. A junction tree can always be constructed after triangulation, possibly at prohibitive cost. These facts delimit computational claims; they do not change the representation-and-traversal connections above.

What to take away

Four points are worth carrying away. First, the 2006 breakthrough was a search strategy as much as a new model: deep networks became trainable when the problem was cut into stages and each stage was solved greedily. Second, the strategy was inherited. Stagewise construction runs from 1960s statistics and GMDH through both 2006 papers, and precedents exist for nearly every ingredient; what changed in 2006 was the piece being added — a layer of features learned without labels — and a demonstration convincing enough to redirect a field. Third, learned features and explicit interactions are two encodings of related structure. A hidden unit packs many interactions into one device; a hyperedge names one. That is why deep models are powerful and hard to inspect while explicit models are the reverse, a trade-off that work on interpretability is still negotiating. Fourth, the shared mathematics of orders, inclusion–exclusion and composition gives a common vocabulary in which claims of similarity can be made exact, and overstated ones caught.

Glossary

Antimatroid
A family of sets describing legal build orders: every legal set can be reached by adding one element at a time, and the union of two legal sets is legal.
Boltzmann machine
A network of binary units with symmetric connections that assigns a probability to every pattern of activity; learning adjusts the connections so that patterns seen in the data become probable.
Category theory
The mathematics of objects and the composable maps between them, used here as a common language for refinement and composition.
Contrastive divergence (CD)
A shortcut for training an RBM: compare statistics of the data with statistics after the model has briefly “reconstructed” the data, and adjust the weights to shrink the difference.
Deep belief net (DBN)
A multi-layer probabilistic model built by stacking RBMs, trained greedily one layer at a time and then fine-tuned as a whole.
Energy-based model
A model that assigns each configuration a number, its energy; lower energy means higher probability.
Fine-tuning
Adjusting all the parameters of an already-built model together, after greedy construction or pre-training.
GMDH
Group Method of Data Handling (Ivakhnenko, 1960s): grows a network layer by layer from small polynomial units, keeping those that perform well on held-out data.
Greedy search
Repeatedly making the change that looks best now, without undoing earlier choices.
Hyperedge
A group of variables treated as a unit; here, the scope of one interaction.
Interaction
A dependence among variables that cannot be reduced to their separate effects.
Kikuchi approximation, region graph
A way of assembling a joint model from overlapping local pieces, with counting numbers that correct for the overlaps.
Latent (hidden) variable
A variable that is not in the data, introduced by the model to explain patterns in it.
Lattice, partially ordered set (poset)
A set whose elements are arranged by an ordering such as “contains.” In a lattice, any two elements have a least element above both (their join) and a greatest element below both (their meet).
Markov network
A probabilistic model defined as a normalized product of factors over groups of variables; also called a Markov random field or undirected graphical model.
Model averaging
Predicting with a weighted combination of several models instead of a single chosen one.
Möbius inversion
The general form of inclusion–exclusion on an ordered set: it recovers what each element contributes on its own from running totals.
Naive Bayes
A classifier that treats the attributes as independent given the class; the baseline with no interactions.
Partition function
The normalizing constant that makes a model’s probabilities sum to one; usually too expensive to compute exactly.
Pre-training
Training a model, or part of one, on a preliminary task — typically without labels — before training it on the task of interest.
Restricted Boltzmann machine (RBM)
A Boltzmann machine with one visible and one hidden layer and no connections within a layer.
Structure search (structure learning)
Choosing which components a model has, as opposed to fitting the numbers attached to them.
Submodular
Having diminishing returns: adding an element helps less the more you already have. Greedy selection has performance guarantees for such objectives.
Variational bound
A computable lower limit on how well a model fits the data; the DBN paper shows that idealized layer-wise training does not lower one.

Revision record: November 14, 2026

This reader’s edition adds material for first-time readers without altering the technical argument: an opening section on why the 2006 result matters, a background primer, a reading guide and timeline, two worked examples, a plain-language summary at the head of each section, reading notes for the figures, a closing summary, and a glossary. Sections 1–9 are otherwise as in the September edition, with one correction: the description of Exhibit 3 now says that time runs top-to-bottom, matching the diagram.

The previous published edition is preserved unchanged. Publication adjustments restore the site navigation, existing section links, accessible diagrams, and mobile table and figure scrolling; remove the draft review controls; and update sharing metadata. The reader’s-edition text and all four diagrams are retained.

Revision record: September 22, 2026

This edition was rebuilt from the original, preserving its conceptual structure and diagrams, with substantial explanatory rewriting and targeted mathematical corrections. It returns to the original report’s purpose: understanding mathematical representations and algorithms for traversing them, including its genealogies, structural analogies, lattice analysis, and logic and category-theory connections. The four diagrams retain their original node and edge geometry, with corrected labels and presentation adjustments. The three-table structure is retained, but table contents and most paragraphs have been rewritten. This supersedes an intervening revision that narrowed the report too far toward computational qualifications; it is not a verbatim restoration or a light copyedit. The original report is preserved unchanged for comparison.


References

The 2006 revival and what followed

Mathematical connections and further reading