Greedy Structure Search

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” 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

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.]

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]

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.

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; they do not, by themselves, claim documented direct influence between every adjacent pair.

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

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 a useful representational sense of “structure learning,” not a claim that unpenalized CD deletes graph edges. 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: v_i, v_iv_k, v_iv_kv_l, 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

Read the diagram’s edges as the payload: each labels a representational move, a change in scoring, or a methodological connection. Left-to-right 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.

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

Let A be the attributes, with the class Y included in every candidate interaction. The scope lattice is 2^A: 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 2^E, 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.

8.2 Möbius inversion connects representations

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 P_R = ∏_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

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

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

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.

8.6 Related algorithms for lattices and partial orders

(“Lattice” here is order-theoretic, not the integer lattices of LLL/SVP, which share only the word.) The interaction search sits at the intersection of three families:

• Lattice traversal. Levelwise / Apriori mining 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.

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.

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.

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).

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.