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, and opened the deep-learning era. The same strategy, applied to interactions among many variables, had been under development since 1999 in Aleks Jakulin’s research on attribute interactions, and was on record as a complete algorithm before the deep-belief-net paper was submitted. This report entertains the hypothesis that this was the foundational work on deep structure induction. It sets Jakulin & Rish’s interaction search beside Hinton, Osindero & Teh’s deep belief net, traces both to their roots, and shows the structure they share.
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]
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? 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, until it represents dependencies among many variables at once. This report calls that deep structure induction, and asks where its foundations were laid.
The hypothesis, and the record behind it
The hypothesis entertained here is that the foundational work on deep structure induction was done in Aleks Jakulin’s research on attribute interactions, begun in 1999 and complete by the spring of 2005, and that the deep belief net of 2006 reaches the same construction by a different route, through hidden units. Three kinds of evidence bear on it.
The record. The work leaves a public trail. In October 1999 a diploma thesis, Machine Learning with Simplicial Complexes, builds classifiers as simplicial complexes over the whole attribute space, so that all the attributes act jointly: the deepest interaction a data set allows. It also meets the obstacle that shapes everything after, the exponential growth of complexity with the number of attributes, and turns to subproblems and decomposition. The later work answers that obstacle with interactions among small groups of attributes, found and assembled efficiently. In December 2002 a master’s thesis, Attribute Interactions in Machine Learning, treats interactions as the irreducible dependencies among attributes, and the programme’s governing principle follows: attributes should be connected in a model if and only if they interact. Papers of 2003 and 2004 measure interactions among three attributes, display the interaction structure of a data set as graphs, and test whether an interaction is real by comparing a model of the whole with its reconstruction from parts. A working paper of about 2004 notes that in a mixture model “it is only due to the latent attribute that any dependencies between different attributes can be represented,” tying hidden variables to interactions. In August 2004 the first Kikuchi-Bayes report assembles overlapping higher-order interactions into one probabilistic classifier in closed form. In May 2005 the second adds the search: interactions are added greedily, each judged in the context of the whole model, and the models visited are averaged for prediction, with results on 46 data sets. The doctoral dissertation, Machine Learning Based on Attribute Interactions, is dated June 13, 2005. It defines a k-way interaction as what cannot be reconstructed from interactions among fewer attributes, and it received the European Association for Artificial Intelligence’s dissertation award for 2005. The deep-belief-net manuscript was submitted on June 8, 2005. [The trail]
The structure. Section 6 shows that when the hidden units of a restricted Boltzmann machine are summed out, each becomes a bundle of interactions among the visible variables it touches: pairs, triples and beyond. A hidden unit encodes many multi-way interactions at once, in compressed form; a hyperedge states one explicitly. Stacking RBMs and adding hyperedges are two ways of growing multi-way interaction structure, and the mathematics of sections 8 and 9 describes both. The explicit form is the more general of the two. Every distribution that a stack of hidden layers defines over discrete visible variables is a hierarchical interaction model whose coefficients are tied together by the weights, whereas an explicit interaction model may set its coefficients freely. Hidden layers buy economy, many interactions from few parameters; they do not extend what can be represented.
The citations. The deep-belief-net manuscript, as posted by its authors, lists 22 references. Nine are from Hinton’s own group, on training energy-based and layered generative models; the rest include comparison methods for digit recognition and background on belief networks. Among stagewise methods it cites boosting and projection pursuit. Within the neural line, Hinton’s group had trained layers of feature detectors in sequence as early as 2000; the argument for why stacking should improve a model first appears in 2005, with this manuscript. [Mayraz & Hinton] It cites nothing on structure search, feature induction, constructive induction or the selection of interactions: not the statistical line that runs from log-linear models to interaction search, not GMDH, not Schmidhuber’s 1991 hierarchy. [Hinton et al.]
Models that combine several variables at once are old: multivariate polynomials long predate both GMDH and the log-linear models of statistics. What was missing was a workable way to choose among them. The number of candidate terms explodes combinatorially. GMDH contains the explosion only by limiting each unit to two inputs and discarding most candidates at every layer; a log-linear model with overlapping interactions has to be refitted iteratively for every candidate, and in statistical practice the interaction terms were usually chosen by the analyst, by hand. The interaction programme supplied an efficient, automatic procedure: the interaction as the unit of learning, defined for any number of attributes, measured, tested, assembled in closed form from reusable parts, and searched for in the context of the whole model, fast enough to cover dozens of data sets in minutes. On the hypothesis, that procedure is the foundation of deep structure induction. The rest of this report sets out the comparison on which the hypothesis rests.
| When | What happened |
|---|---|
| 1965–71 | Ivakhnenko & Lapa’s GMDH grows networks layer by layer from small interaction terms, keeping units that validate well (section 4). |
| 1985–86 | The Boltzmann machine and its restricted form, later called the RBM; backpropagation is popularized. |
| 1991 | Schmidhuber’s history compressor pre-trains a hierarchy of sequence predictors one level at a time, without labels. |
| late 1990s | Neural networks fall out of favour; support vector machines and graphical models dominate. |
| Oct 1999 | Jakulin: diploma thesis, Machine Learning with Simplicial Complexes. |
| Late 2000 | Mayraz & Hinton, at the Gatsby Unit, train layers of feature detectors in sequence, each modelling the activity of the layer below. |
| Aug 2002 | Contrastive divergence makes RBMs practical to train. |
| Dec 2002 | Jakulin: master’s thesis, Attribute Interactions in Machine Learning. |
| Sep 2003 | Jakulin & Bratko at PKDD: measuring interactions among attributes and displaying them as graphs. |
| Jul 2004 | Jakulin & Bratko at ICML: testing whether an interaction is significant. |
| Aug 2004 | Jakulin, Rish & Bratko: first Kikuchi-Bayes report (RC23314). Classifiers assembled from overlapping higher-order interactions in closed form. |
| May 2005 | Jakulin & Rish: report RC23602. Greedy search over interactions in a Markov network, with model averaging. |
| Jun 2005 | Hinton, Osindero & Teh submit the deep-belief-net manuscript (June 8): deep networks trained greedily, layer by layer. Accepted November 2005. |
| Jun 2005 | Jakulin’s doctoral dissertation, Machine Learning Based on Attribute Interactions (June 13); European dissertation award in artificial intelligence for 2005. |
| Nov 2005 | Early in the month, Jakulin presents the interaction search at the Gatsby Computational Neuroscience Unit, UCL, which Hinton founded and directed from 1998 to 2001. |
| Jul 2006 | The deep-belief-net paper appears in Neural Computation; Hinton & Salakhutdinov’s companion paper appears in Science. |
| Sep 2006 | Jakulin & Rish’s interaction search is published at ECML. |
| Dec 2006 | Bengio et al. and Ranzato et al. present related layer-wise methods at NIPS. |
| 2009–12 | Pre-trained deep networks transform speech recognition. |
| Oct 2012 | A deep convolutional network wins ImageNet, trained end to end with no layer-wise pre-training. |
| Jun–Oct 2018 | Pre-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 2024 | Nobel Prize in Physics to Hopfield and Hinton. |
Timeline. The interaction programme (green) and the deep belief net (purple) against what came before and after.
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.
1. The core duality
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” names this complementary organization, and the connections to lattices, logic, and category theory make it precise.
2. What each greedy search does
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.]
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]
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
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 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 | Reuse submodels; score candidate hyperedges and update overlap corrections |
| Overall speed | Iterative training; fast approximate bottom-up recognition | Reported search on 46 datasets in <9 min, vs >686 min for BN classifiers |
| “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 | Variational improvement for the idealized construction, not practical CD | Heuristic hill-climb; no global guarantee, but a df-based prior controls complexity |
| Approximation | CD approximates weight updates; bottom-up recognition approximates the posterior | Kikuchi / cluster-variation region graph for the joint |
| Interpretability | Distributed latent features; interpretation requires examining learned representations | Explicit, named variable groups; interaction information can help interpret dependencies |
| 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 | Reusable submodels + explicit interactions + class probabilities; k-way and 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 |
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
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.
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.
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.
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. It is a conceptual ancestor of both. [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. 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. [Yedidia et al.]
A note on genealogy: Schmidhuber’s historical essays document these precedents and argue that the 2006 paper does not credit them. The deep-belief-net paper cites neither GMDH nor the history compressor, and nothing from the graphical-model branch traced here.
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?” Its relation to structure search is still instructive:
- By contrast. A parameter-fitting loop can be nested inside a discrete search over candidate structures. Reusing closed-form submodels changes the cost of that outer traversal; CD is one possible fitting method for energy models, not a required inner loop for every undirected model.
- As a structure signal. Differences between empirical and modeled feature expectations reveal dependencies that the current representation misses. Feature induction uses such discrepancies and candidate gains to expand its vocabulary; a CD update instead adjusts weights in the existing vocabulary. The signals are related, while the moves differ.
- As implicit structure learning. Hidden units can specialize as their weights change, producing an effective organization inside a fixed graph. This is structure learning in a representational sense. Sparsity penalties can make the connection to explicit selection closer.
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
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:
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. In an RBM the interaction coefficients are tied together through the weights rather than set freely, and that is the essential difference between the two representations: explicit search chooses which interaction scopes to represent; latent learning discovers features whose induced interactions need not be listed individually. It follows that the explicit formulation is the more general one: every distribution an RBM or a deep belief net defines over discrete visible variables is a hierarchical interaction model with constrained coefficients, while an interaction model may choose its coefficients freely. What hidden units contribute is economy, many interactions from few parameters, rather than additional reach. [Montúfar & Rauh]
On chronology
RBMs (Smolensky 1986) and contrastive divergence (Hinton 2002) predate both main papers. On the interaction side the record runs from the 1999 diploma thesis through the 2002 master’s thesis and the papers of 2003–04 to the two Kikuchi-Bayes reports: RC23314, dated August 30, 2004, which selects interactions one at a time, and RC23602, dated May 6, 2005, which contains the greedy search over whole structures. The doctoral dissertation is dated June 13, 2005. The DBN manuscript was submitted June 8 and accepted November 8, 2005, before its 2006 journal issue; Jakulin & Rish appeared at ECML in September 2006. The interaction search was therefore on record a month before the deep-belief-net manuscript was submitted, and the work it rests on years before. [2004 report] [2005 report] [The trail]
7. The evolution of structure search
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.
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.
8. Foundations: structure search as search over a lattice
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.
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.
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]
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.”
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.
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.
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:
- Lattice traversal. Levelwise / Apriori mining uses anti-monotone constraints to prune the subset lattice. Version spaces maintain boundaries in a generality order; ILP uses refinement operators. Greedy search follows a score-guided path, while beam search retains several partial structures. Antimatroids describe feasible construction orders, and submodularity can justify particular greedy objectives. These are distinct uses of order structure, not one universal search algorithm.
- Möbius / zeta-transform scoring. Fast transforms and subset convolution reuse sums across related subsets. Koivisto–Sood exact Bayesian-network discovery uses subset dynamic programming and transform machinery under specific priors. This is a valuable comparison with local greedy exploration, but it sums a different object: directed-model scores rather than the Jakulin–Rish conditional hypergraph posterior. [Koivisto & Sood]
- Region-poset inference. Junction trees organize compatible clique and separator marginals; generalized belief propagation uses overlapping regions and counting numbers; iterative proportional fitting adjusts distributions to satisfy marginal constraints. They share local-to-global bookkeeping, while solving different fitting or inference problems. Jakulin & Rish use a closed-form region construction for prediction, not a general exact substitute for all three procedures.
| 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 in a generality / subsumption order | probabilistic score, not logical consistency |
| Greedy submodular / greedoid | feasible extensions and score properties | one-step look-ahead; separate hypotheses needed for guarantees |
| Fast Möbius/zeta; subset convolution | inclusion–exclusion over the lattice | region corrections reuse submodels, not a full subset transform |
| Koivisto–Sood exact discovery (2004) | subset DP and transforms for directed structures | local search over a different model family and score |
| Junction tree (1988) | message passing on a separator poset | overlapping regions need not have a junction-tree factorization |
| Generalized belief propagation (2005) | region-graph counting numbers | closed-form prediction construction, not GBP fixed-point iteration |
| Iterative proportional fitting (1940) | fit potentials on the margin lattice | reuses 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
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 family | Jakulin & Rish | Hinton (deep belief net) |
|---|---|---|
| Representation space | Collections of explicit interaction scopes; overlap regions derived from them | A sequence of latent spaces with learned maps between adjacent layers |
| Traversal | Extend a structure, evaluate candidate interactions, retain and average evaluated models | Learn one representation, use it as the input vocabulary for the next, then fine-tune |
| Combination rule | Multiply local factors with corrections for their overlapping scopes | Compose directed stochastic layers beneath an undirected top-level model |
| Interaction lattice | Selected hyperedges name scopes explicitly | Marginalized hidden units induce coupled coefficients across subsets of visibles |
| Incremental growth (shared) | Add one component, or enlarge a candidate scope, according to the search rules | Add a learned stage that represents relations among the preceding features |
| Closest structural language | Set systems, refinement orders, incidence algebra, and local-to-global assembly | Compositional 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: 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, that strategy, together with a theory of what is being searched for, was already on record. The interaction programme defined the multi-way interaction, measured and tested it, assembled overlapping interactions into one model, and searched for them greedily in the context of the whole: a trail that runs from 1999 to a complete algorithm in May 2005, a month before the deep-belief-net manuscript was submitted. Third, the two constructions correspond. A hidden unit packs many interactions into one device; a hyperedge names one; stacking layers and adding hyperedges grow the same kind of structure. The explicit form is the more general: whatever hidden layers represent about the observed variables can be written out as interactions. That is also why deep models are powerful and hard to inspect while explicit models are the reverse. Fourth, the deep-belief-net paper cites none of this literature. The record, the correspondence and the citations together are the case for the hypothesis that the foundations of deep structure induction were laid in the study of interactions.
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 edition restates the report around a hypothesis: that the foundational work on deep structure induction was done in research on attribute interactions between 1999 and 2005. It adds the documented trail of that work, a month-by-month timeline, and an account of what the deep-belief-net paper cites, and it removes qualifications about credit and influence that the September edition had introduced. Mathematical corrections from the September edition are retained. For first-time readers it also adds an opening section on why the 2006 result matters, a background primer, a reading guide, two worked examples, a plain-language summary at the head of each section, reading notes for the figures, a closing summary, and a glossary. The description of Exhibit 3 now says that time runs top-to-bottom, matching the diagram.
Earlier versions remain available: the first reader’s edition and the pre-reader’s edition. The original uncorrected report is linked above and in the September revision record.
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.
- Distinguished conceptual genealogy from documented influence and mixed publication dates from research priority.
- Kept latent/explicit interaction analogies while removing fixed-size model equivalence and automatic higher-order-growth claims.
- Separated scope lattices, model collections, and region posets; retained order ideals and antimatroids without conflating them with simplicial shelling or score guarantees.
- Corrected the distinction between a Möbius kernel, derived region weights, and their Euler-characteristic sum.
- Retained the category-theory and logic connections while specifying their objects, maps, directions, and hypotheses.
- Qualified practical CD, expanded the prose explanation of model averaging already present in the original diagram, and corrected normalization and benchmark claims without making them the report’s organizing theme.
- Retained the related-algorithm taxonomy without claiming that distinct dynamic programs and greedy searches compute the same posterior sum.
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) · D. Ackley, G. Hinton & T. Sejnowski (1985) · 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).
The trail of work on interactions, 1999–2005
- A. Jakulin. Strojno učenje s simplicialnimi kompleksi (Machine Learning with Simplicial Complexes). Diploma thesis, University of Ljubljana, October 1999. In Slovene.
- A. Jakulin. Attribute Interactions in Machine Learning. Master’s thesis, University of Ljubljana, December 2002.
- A. Jakulin, I. Bratko, D. Smrke, J. Demšar & B. Zupan. Attribute Interactions in Medical Data Analysis. AIME 2003 (LNAI 2780, pp. 229–238).
- A. Jakulin & I. Bratko. Analyzing Attribute Dependencies. PKDD 2003 (LNAI 2838, pp. 229–240). — Quantifying and Visualizing Attribute Interactions. Working paper, 2003.
- A. Jakulin & I. Bratko. Testing the Significance of Attribute Interactions. ICML 2004, pp. 409–416.
- A. Jakulin. Qualitative Aspects in Numerical Data: Structure, Interaction, and Correlation. Working paper, c. 2004.
- A. Jakulin. Machine Learning Based on Attribute Interactions. PhD dissertation, University of Ljubljana, June 13, 2005. EurAI Dissertation Award, 2005.
- The two Kikuchi-Bayes reports (2004, 2005) and the ECML 2006 paper are listed with the main references. A project page collects the papers and slides.
The 2006 revival and what followed
- Y. LeCun, Y. Bengio & G. Hinton. Deep Learning. Nature 521:436–444, 2015. The protagonists’ own account: neural networks out of favour in the late 1990s, interest revived around 2006, speech recognition as the first major application, and pre-training later needed only for small data sets.
- G. Mayraz & G. E. Hinton. Recognizing Hand-written Digits Using Hierarchical Products of Experts. Advances in Neural Information Processing Systems 13, 2000.
- G. E. Hinton & R. R. Salakhutdinov. Reducing the Dimensionality of Data with Neural Networks. Science 313:504–507, 2006.
- Y. Bengio, P. Lamblin, D. Popovici & H. Larochelle. Greedy Layer-Wise Training of Deep Networks. Advances in Neural Information Processing Systems 19, 2006. — M. Ranzato, C. Poultney, S. Chopra & Y. LeCun. Efficient Learning of Sparse Representations with an Energy-Based Model. Same volume.
- G. Hinton, L. Deng, D. Yu, G. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. Sainath & B. Kingsbury. Deep Neural Networks for Acoustic Modeling in Speech Recognition: The Shared Views of Four Research Groups. IEEE Signal Processing Magazine 29(6):82–97, 2012.
- A. Krizhevsky, I. Sutskever & G. E. Hinton. ImageNet Classification with Deep Convolutional Neural Networks. Advances in Neural Information Processing Systems 25, 2012.
- X. Glorot, A. Bordes & Y. Bengio. Deep Sparse Rectifier Neural Networks. AISTATS 2011 (PMLR 15:315–323). Deep networks with rectifier units reach their best performance without unsupervised pre-training.
- The Royal Swedish Academy of Sciences. Press release: The Nobel Prize in Physics 2024. — ACM. Fathers of the Deep Learning Revolution Receive ACM A.M. Turing Award, 2019.
Mathematical connections and further reading
- J. Schmidhuber. Neural Sequence Chunkers. FKI-148-91, 1991.
- A. Jakulin & I. Rish. Kikuchi-Bayes: Markov Networks for Classification. RC23602, May 6, 2005.
- G. Montúfar & J. Rauh. Hierarchical Models as Marginals of Hierarchical Models. 2016 version.
- J. Yedidia, W. Freeman & Y. Weiss. Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms. IEEE Transactions on Information Theory, 2005.
- G.-C. Rota. On the Foundations of Combinatorial Theory I: Theory of Möbius Functions. 1964.
- T. P. Speed. Cumulants and Partition Lattices. 1983.
- A. Krause & C. Guestrin. Near-optimal Nonmyopic Value of Information in Graphical Models. UAI 2005; section 3 discusses the XOR example.
- T. Leinster. The Euler Characteristic of a Category. Documenta Mathematica 13, 2008.
- S. Abramsky & A. Brandenburger. The Sheaf-Theoretic Structure of Non-Locality and Contextuality. 2011.
- T. Fritz. A Synthetic Approach to Markov Kernels, Conditional Independence and Theorems on Sufficient Statistics. 2020.
- F. W. Lawvere. Adjointness in Foundations. Dialectica 23, 1969.
- M. Koivisto & K. Sood. Exact Bayesian Structure Discovery in Bayesian Networks. JMLR 5, 2004.