inferlo.PairWiseFiniteModel

class inferlo.PairWiseFiniteModel

Pairwise finite graphical model.

Represents a graphical model in which all variables have the same discrete domain, all factor depends on at most two variables.

Model is represented by field F and interactions J. Probability of configuration X is proportional to exp(sum F[i][X_i] + 0.5*sum J[i][j][X[i]][X[j]]).

Field is stored explicitly as a matrix of shape (gr_size, al_size).

Interactions are stored only for those pairs of variables for which they are non-zero. So, interactions are represented by undirected graph, where for each edge (i,j) we store matrix J[i,j], which has shape (al_size, al_size).

Names

“Field” is called like that because in physical models (such as Ising model) these values correspond to local magnetic fields. They are also known as biases. “Interactions” are called like that because in physical models they correspond to strength of spin-spin interactions. The fact that all these terms enter the probability density function inside the exponent also refers to physical models, because fields and interactions are terms in energy and according to Bolzmann distribution probability of the state with energy E is proportional to exp(-E/(kT)).

__init__(size, al_size)

Initializes PairWiseFiniteModel.

Parameters:

• num_variables – Number of variables.

• al_size – Size of the alphabet (domain).

Domain will consist of integers in range 0, 1, … al_size - 1.

Methods

__init__(size, al_size)	Initializes PairWiseFiniteModel.
add_factor(factor)	Adds a factor.
add_interaction(u, v, interaction)	Adds factor corresponding to interaction between nodes u and v.
create(field, edges, interactions)	Creates PairwiseFiniteModel from compact representation.
decode_state(state)	Returns id of given state.
draw_factor_graph(ax)	Draws the factor graph.
draw_pairwise_graph(ax)	Draws pairwise graph.
encode_state(state)	Returns state represented by its integer id.
evaluate(x)	Returns value of non-normalized pdf in point.
from_model(original_model)	Constructs Pairwise Finite model which is equivalent to given model.
get_all_interactions()	Returns all interaction matrices in compact form.
get_dfs_result()	Performs DFS for interaction graph.
get_edges_array()	Returns edge list as np.array.
get_edges_connected()	Returns edges, ensuring that graph is connected.
get_factor_graph()	Builds factor graph for the model.
get_factors()	Generates explicit list of factors.
get_graph()	Returns interaction graph.
get_interaction_matrix(u, v)	Returns interaction matrix between nodes u and v.
get_interactions_for_edges(edges)	Returns interaction for given edges.
get_max_domain_size()	Returns the biggest domain size over all variables.
get_subgraph_factor_values(vars_idx[, vars_skip])	Calculates factor values for subgraph.
get_symbolic_variables()	Prepares variables for usage in expressions.
get_variable(idx)	Returns variable by its index.
get_variables()	Returns all variables.
has_edge(u, v)	Whether there is edge between vertices u and v.
infer([algorithm])	Performs inference.
is_graph_acyclic()	Whether interaction graph is acyclic.
max_likelihood([algorithm])	Finds the most probable state.
max_likelihood_bruteforce()	Evaluates most likely state in a very inefficient way.
part_func_bruteforce()	Evaluates partition function in very inefficient way.
sample([num_samples, algorithm])	Draws i.i.d.
set_field(field)	Sets values of field (biases) in all vertices.

add_factor(factor: Factor)

Adds a factor.

add_interaction(u, v, interaction)

Adds factor corresponding to interaction between nodes u and v.

Factor is f(x) = exp(interaction[x[u], x[v]]). If there already is interaction between these edges, this interaction will be added to it (old interaction isn’t discarded).

static create(field: ndarray, edges: ndarray | List, interactions: ndarray)

Creates PairwiseFiniteModel from compact representation.

Infers number of variables and size of alphabet from shape of field.

Parameters:

• field – Values of the field. np.array of shape (gr_size, al_size).

• edges – List of edges with interactions. np.array of integer dtype and shape (edge_num, 2). Edges can’t repeat. If there is edge (u,v), you can’t have edge (v,u).

• interactions – np.array of shape (edge_num, al_size, al_size), or Iterable which can be converted to such an array. interactons[i,:,:] is a matrix decribing interactions between variables edges[i, 0] and edges[i, `].

decode_state(state)

Returns id of given state.

State id is integer between 0 and al_size**gr_size-1.

draw_pairwise_graph(ax)

Draws pairwise graph.

encode_state(state)

Returns state represented by its integer id.

static from_model(original_model: GraphModel) → PairWiseFiniteModel

Constructs Pairwise Finite model which is equivalent to given model.

All variables must be discrete. All factors must depend on at most 2 variables.

New model will have the same number of variables and factors. If variables in original model have different domain sizes, in new model they will be extended to have the same domain size.

get_all_interactions() → ndarray

Returns all interaction matrices in compact form.

Returns:

np.array of shape (edge_num, al_size, al_size) with interaction matrix for every edge. Matrices correspond to edges in the same order as returned by get_edges.array.

get_dfs_result() → FastDfsResult

Performs DFS for interaction graph.

get_edges_array() → ndarray

Returns edge list as np.array.

get_edges_connected() → ndarray

Returns edges, ensuring that graph is connected.

If graph is already connected, equivalent to get_edges_array. If graph is not connected, adds minimal amount of edges to make it connected.

This is needed for algorithms which require connected graph to work correctly.

get_factors() → Iterable[Factor]

Generates explicit list of factors.

get_graph()

Returns interaction graph.

get_interaction_matrix(u, v)

Returns interaction matrix between nodes u and v.

Returns np.array of shape (al_size, al_size). If there is no interaction between these nodes, raises KeyError.

get_interactions_for_edges(edges) → ndarray

Returns interaction for given edges.

If some edges don’t exist, interaction matrix for them will be a zero matrix.

Parameters:

edges – Edge list. np.array of shape (x, 2).

Returns:

np.array of shape (x, al_size, al_size).

get_subgraph_factor_values(vars_idx: ndarray, vars_skip: Set = frozenset({})) → ndarray

Calculates factor values for subgraph.

Consider model on subgraph containing only variables with indices vars. That is, containing only factors which depend only on variables from vars. For every possible combination of those variable values, calculate product of all factors in the new model - that’s what this function returns.

This can also be described as “interactions within subgraph”. Or if we condense all variables in vars in single “supervariable”, this function returns field for the new supervariable.

Parameters:

• vars_idx – Indices of variables in subgraph.

• vars_skip_factors – Set. Indices of variables, which should be skipped for factor calculation. Field factors for these variables won’t be included in the result. Interaction factors oth arguments of which are in vars_skip_factors, won’t be included in the result. However, interaction factors where only one variable appears in vars_skip_factors, will be included in result. This parameter is useful when building junction tree, to avoid double-counting factors.

Returns:

np.array of length al_size ** len(vars). Each value is logarithm of product of all relevant factors for certain variable values. Correspondence between indices in this array and states is consistent with decode_state.

has_edge(u, v) → bool

Whether there is edge between vertices u and v.

infer(algorithm='auto', **kwargs) → InferenceResult

Performs inference.

Available algorithms

• auto - Automatic.

• bruteforce - Brute force (by definition). Exact

• mean_field - Naive Mean Field. Approximate.

• message_passing - Message passing. Approximate, exact only for trees.

• path_dp - Dynamic programming on path decomposition. Exact. Effective on graphs of small pathwidth.

• tree_dp - Dynamic programming on tree. Exact. Works only on trees.

• junction_tree - DP on junction tree. Exact. Effective on graphs of small treewidth.

Parameters:

algorithm – Which algorithm to use. String.

Returns:

InferenceResult object, which contains logarithm of partition function and matrix of marginal probabilities.

is_graph_acyclic()

Whether interaction graph is acyclic.

max_likelihood(algorithm='auto', **kwargs) → ndarray

Finds the most probable state.

Available algorithms

• auto - Automatic.

• bruteforce - Brute force (by definition).

• path_dp - Dynamic programming on path decomposition. Exact. Effective on graphs of small pathwidth.

• tree_dp - Dynamic programming on tree. Exact. Works only on trees.

• junction_tree - DP on junction tree. Exact. Effective on graphs of small treewidth.

Parameters:

algorithm – Which algorithm to use. String.

Returns:

The most probable state as numpy int array.

sample(num_samples: int = 1, algorithm='auto', **kwargs) → ndarray

Draws i.i.d. samples from the distribution.

Available algorithms

• auto - Automatic.

• bruteforce - Sampling from explicitly calculated probabilities for each state.

• tree_dp - Dynamic programming on tree. Works only on trees.

• junction_tree - DP on junction tree.

Parameters:

• num_samples – How many samples to generate.

• algorithm – Which algorithm to use.

Returns:

np.array of type np.int32 and shape (num_samples, gr_size). Every row is an independent sample.

set_field(field: ndarray)

Sets values of field (biases) in all vertices.