5.1 From Graph Theory to Boltzmann Machines
We provide here a short self-contained review of graph theory in order to introduce Boltzmann machines (or energy-based models), which one can view as particular types of connected graphs or networks.
A graph is a set of vertices (points or nodes) and edges that connect the vertices. A directed graph is a type of graph that contains ordered pairs of vertices, while an undirected graph is a type of graph that contains unordered pairs of vertices.
We consider a graph G = (V,E) characterised by a finite number of vertices V and undirected edges E. For a given vertex v ∈V, its neighbourhood is defined as the set of all vertices connected to it by some edge, or
Finally, a clique C is a subset of V such that all vertices in C are pairwise connected by some edge in E.
To each vertex v ∈V, we associate a random variable Xv taking values in some space X. The vector X ∈ X|V| is...
