Multilevel Tree

mltree

Markov tree components.

This module implements the core functionalities for prefetching, which is realized through a binary decision tree (Markov tree).

Classes:

Name	Description
BaseNode	Markov tree node base class
MTNode	Markov tree node implementation based on Anytree
MLTreeSearchFunctions	Collection of functions for inspecting a Markov tree
MLTreeModifier	Routines for modification of Markov trees
MLTreeVisualizer	Component for rendering Markov trees to dot files

mtmlda.core.mltree.BaseNode

Markov tree node base class.

The class contains all MCMC-related information for a node in the Markov tree.

Attributes:

Name	Type	Description
probability_reached	float	The probability of reaching the node in the Markov tree
state	np.ndarray	The state of the Markov chain associated with the node
logposterior	float	The log-posterior probability of the state associated with the node
logposterior_coarse	float	The log-posterior of the node state, but on the next coarser level of the model hierarchy
computing	bool	Whether the log-posterior for the node's state is currently being computed
random_draw	float	The random number used to decide whether to accept or reject the MCMC move associated with the node
level	int	The level of the node in the multilevel hierarchy
subchain_index	int	The index of the node within the sub-chain of its level

mtmlda.core.mltree.MTNode

Bases: BaseNode, atree.NodeMixin

Markov tree node implementation.

The class inherits MCMC-related information from 'BaseNode' and is equipped with Anytree's node functionality via a mixin.

__init__

__init__(name: str, parent: Self | None = None, children: list[Self] | None = None) -> None

Node constructor.

Parameters:

Name	Type	Description	Default
name	str	Identifier of the node	required
parent	Self	Parent of the node. Defaults to None.	None
children	list[Self]	Children of the node. Defaults to None.	None

mtmlda.core.mltree.MLTreeSearchFunctions

Collection of functions for analyzing a Markov tree without modification.

This class is only a namespace for the contained functions, all methods are static. The search functions iterate over an existing Markov tree and find nodes that fulfill certain criteria.

Methods:

Name	Description
find_max_probability_node	Find the node with the maximum probability of being reached
get_same_level_parent	Find the parent node of the same level as the input node, if it exists
get_unique_same_subchain_child	Find the unique child of a node with the same level, if it exists (i.e. if all intermediate MCMC decisions have been carried out)
check_if_node_is_available_for_decision	Check if a node is available for an MCMC decision, depending on if its log-posterior and those of "adjacent nodes" have been computed

find_max_probability_node staticmethod

find_max_probability_node(root: MTNode) -> MTNode

Find node in the Markov tree with the maximum probability of being needed.

More precisely, the method looks for the node that is most likely to be needed in the progression of the Markov tree. This is the node whose parent has the highest probability of being reached. The method only checks for accept nodes whose log-posterior has not been computed yet.

Parameters:

Name	Type	Description	Default
root	MTNode	Current root node of the Markov tree	required

Returns:

Name	Type	Description
MTNode	MTNode	Maximum probable node

get_same_level_parent staticmethod

get_same_level_parent(node: MTNode) -> MTNode | None

Find next parent with same level in the MLDA hierarchy.

Parameters:

Name	Type	Description	Default
node	MTNode	Node to search parent for	required

Returns:

Name	Type	Description
MTNode	MTNode | None	Same level parent node, can be None

get_unique_same_level_child staticmethod

get_unique_same_level_child(node: MTNode) -> MTNode | None

Get the unique child on the the same level of the MLDA hierarchy.

Uniqueness refers to the path in the Markov tree, meaning that all MCMC decisions between a node and the same level child have to be carried out.

Parameters:

Name	Type	Description	Default
node	MTNode	Node to get unique child for	required

Returns:

Name	Type	Description
MTNode	MTNode | None	Unique same level child, can be None

check_if_node_is_available_for_decision staticmethod

check_if_node_is_available_for_decision(node: MTNode) -> tuple[bool, bool, bool]

Check if a node is available for MCMC descicion.

A node has to fulfill some general criteria to be available for an MCMC decision. These are checked with the decision_prerequisites_fulfilled conditional. After that, we distinguish two different cases. On the ground level of the MLDA hierarchy, the node's posterior and its immediate parent's posterior (which also has to be on the ground level) have to be computed. For the second case of a two-level decision, we require four posterior values to be available. Firstly, we need the values for the first and last node of the coarser sub-chain. Secondly, we need the values for the current finer level state and the proposal on that level. The method returns three booleans, indicating if the node is generally available for a decision, if it is a ground level decision, or if it is a two-level decision.

Parameters:

Name	Type	Description	Default
node	MTNode	Node to check	required

Returns:

Type	Description
tuple[bool, bool, bool]	tuple[bool, bool, bool]: Booleans indicating if node is available for decision, and which type of decision

check_if_leaf_is_available_for_computation staticmethod

check_if_leaf_is_available_for_computation(root: MTNode) -> bool

Check if a leaf node is ready for computation.

This means that the node has not been visited yet.

Parameters:

Name	Type	Description	Default
root	MTNode	Root node of the Markov tree	required

Returns:

Name	Type	Description
bool	bool	If any leaf is available for computation

mtmlda.core.mltree.MLTreeModifier

Class for the manipulation of Markov Trees.

This class is the counterpart to the MLTreeSearchFunctions class. It contains methods to modify a tree or specific nodes.

Methods:

Name	Description
expand_tree	Expand the Markov tree by adding new children to the nodes
compress_resolved_subchains	Remove nodes within sub-chain that are not required for subsequent MCMC decisions
update_descendants	Update the status of the descendants of a node
discard_rejected_nodes	Remove nodes from the tree that have been excluded by an MCMC decision
update_probability_reached	Update the probability of reaching a node in the Markov tree

rng property writable

rng: np.random.Generator

Getter for random number generator.

__init__

__init__(
    num_levels: int, ground_proposal: Any, subsampling_rates: Sequence[int], rng_seed: float
) -> None

Constructor.

Reads in the necessary parameters for the manipulation of the Markov tree.

Parameters:

Name	Type	Description	Default
num_levels	int	Number of levels in the model hierarchy	required
ground_proposal	Any	Proposal object for chain on coarsest level	required
subsampling_rates	Sequence[int]	Subchain lengths for each level	required
rng_seed	float	RNG seed for uniform number generation to be used in accept/reject decisions	required

Raises:

Type	Description
ValueError	Checks that correct number of sub-sampling rates is provided

expand_tree

expand_tree(root: MTNode) -> None

Expand Markov tree.

This is an interface method performing two steps: 1. Add new children to the leave nodes of the Markov tree 2. Update status of new nodes depending of the status of their parents The procedure is repeated as long as some accept nodes are still not computable, meaning they do not inherit the status of their parents.

Parameters:

Name	Type	Description	Default
root	MTNode	Root node of the Markov tree	required

compress_resolved_subchains

compress_resolved_subchains(root: MTNode) -> bool

Compress sub-chains by discarding irrelevant nodes.

Within a sub-chain of a given level, only the first and last node are relevant for a two-level decision to the next level. Accordingly, nodes in between can be removed as soon as a unique path is established between them.

Parameters:

Name	Type	Description	Default
root	MTNode	Root node of the Markov tree	required

update_descendants staticmethod

update_descendants(root: MTNode) -> None

Update all descendants of a given node.

If a descendent node has the same state and level as its parent, they share status regarding computations and posterior values. Transferring these values is important for evaluating which nodes still require posterior evaluations. It also helps to avoid redundant computations.

Parameters:

Name	Type	Description	Default
root	MTNode	Root node of the Markov tree	required

discard_rejected_nodes staticmethod

discard_rejected_nodes(node: MTNode, accepted: bool) -> None

Prune the Markov tree after an MCMC decision.

The branch of the tree that isn't chosen in the MCMC decision can be discarded.

Parameters:

Name	Type	Description	Default
node	MTNode	Node for which MCMC decision has been computed	required
accepted	bool	If MCMC decision was accepted	required

update_probability_reached staticmethod

update_probability_reached(root: MTNode, acceptance_rate_estimator: Any) -> None

Update probabilities for reaching nodes according to accept rate estimates.

Parameters:

Name	Type	Description	Default
root	MTNode	Root node of the Markov tree	required
acceptance_rate_estimator	Any	Object returning acceptance rate estimate for a given level	required

_add_new_children_to_node

_add_new_children_to_node(node: MTNode) -> None

Add accept and reject child to a given node.

Depending on the level and sub-chain index of the parent, the children are created with new level and sub-chain index properties. Also depending on their respective positions in the chain, the states of the children are transferred from previous nodes or newly created from a proposal distribution.

Parameters:

Name	Type	Description	Default
node	MTNode	Node to append children to	required

mtmlda.core.mltree.MLTreeVisualizer

Visualizer for Markov Trees.

This class utilizes Anytree's built-in exporter to create dot-file visualizations of a given Markov tree. This dot-files can then be converted into,e.g., PNG images during post-processing. The nodes are annotated with information on their name ('a' or 'r'), the probability of reaching them, their level in the MLDA hierarchy, and their subchain index. Their respective level is also indicated by the node size (higher level = larger node). In addition, coloring of the nodes indicates their computing status. Light blue nodes have not been visited yet, the posterior for orange nodes is currently being computed, and green nodes have been evaluated.

Methods:

Name	Description
export_to_dot	Export the given Markov tree to a dot-file, automatically indexed

__init__

__init__(result_directory: Path | None = None) -> None

Constructor.

Create directory for storing visualizations if desired, initialize counter for indexing.

Parameters:

Name	Type	Description	Default
result_directory	Path	Directory to store dot files in. Defaults to None. If no directory is provided, dot files are not stored.	None

export_to_dot

export_to_dot(mltree_root: MTNode) -> int

Export a given tree to dot file, interface method.

Parameters:

Name	Type	Description	Default
mltree_root	MTNode	Root node of the tree to export	required

Returns:

Name	Type	Description
int	int	description

_node_attr_func classmethod

_node_attr_func(node: MTNode) -> str

Generates a metadata string for dot-file export.

Parameters:

Name	Type	Description	Default
node	MTNode	Node to generate metadata for	required

Returns:

Name	Type	Description
str	str	metadata string

_name_from_parents staticmethod

_name_from_parents(node: MTNode) -> str

Create node name by appending current name to parent's name.

Parameters:

Name	Type	Description	Default
node	MTNode	Node to name	required

Returns:

Name	Type	Description
str	str	node name