liveBook · Manning

Structure learning algorithm

As explained in Machine Learning Algorithms in Depth

Structure learning is the process of inferring the structure of a graph or probabilistic model from observed data.

Structure learning infers a graph or probabilistic model structure from observed relational data. Given data D, it evaluates plausible graph structures G = (V, E), but general-graph search is NP-hard because the number of directed topologies grows exponentially. section 9.3

Approximate structure-learning methods specialize the search to two settings:

  • Chow–Liu constructs a tree-based graph by using mutual information between nodes as edge weights and selecting a maximum-weight spanning tree. section 9.6
  • Inverse covariance estimation targets general graphs; regularizing the inverse covariance matrix produces more interpretable topologies with fewer inferred edges. section 9.6

Choosing a tractable topology

When graph search is infeasible, a tree approximation limits the structure to a maximum-weight spanning tree; for a general graph, inverse-covariance regularization favors a sparser topology. section 9.8

How Machine Learning Algorithms in Depth covers it

How deep it goes
Defines the combinatorial challenge and identifies two approximate methods, but does not detail their derivations or implementations.
Examples
Uses tree graphs weighted by mutual information and sparse general graphs produced through regularized inverse covariance estimation.
What it assumes
Assumes observed relational data and graph notation, while treating the exponential search challenge as part of the explanation.
What you can do after
Apply Chow–Liu to construct tree graphs or use regularized inverse covariance estimation to obtain sparser general-graph topologies.
How it connects
Connects graph structure with mutual information, maximum-weight spanning trees, inverse covariance estimation, regularization, and causality.
Cover of Machine Learning Algorithms in Depth
liveBookmanning.com
Read Machine Learning Algorithms in Depth on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Machine Learning Algorithms in Depth. The section links point to the parts of the book it draws on.