Struct affinitree::pwl::afftree::AffTree

pub struct AffTree<const K: usize> {
    pub tree: Tree<AffContent, K>,
    pub in_dim: usize,
    /* private fields */
}

A corner stone of affinitree that can represent any (continuous or non-continuous) piece-wise linear function.

This structure is based on an oblique decision tree:

• Its inner nodes form a decision structure that partitions the input space similar to a BSP tree into convex regions.
• Its terminal nodes associate with each such region a linear function.

Technically, each decision node divides the space into two halfspace which are separated by a hyperplane. The outgoing edges of decision nodes have labels that uniquely associate the edge with a halfspace. A path over multiple edges then corresponds to the intersection of the associated halfspaces of each edge.

To encode a given piece-wise linear function as an AffTree, one first has to derive the decision structure based on the regions of the function. That is, each path from root to a terminal corresponds to exactly one region of the function. Then, the terminal stores the respective linear function that is active in this region.

Example

The piece-wise linear function f(x, y) = |max{x,y}| is represented as the AffTree

This tree is constructed in affinitree as follows:

use affinitree::{aff, poly, pwl::afftree::AffTree, pwl::dot::dot_str, linalg::affine::PolyRepr};

// construct a new AffTree instance with the given inequality as its root.
let mut dd = AffTree::<2>::from_aff(poly!([[1, 1]] < [0]).convert_to(PolyRepr::MatrixBiasGeqZero)); // node index 0

// add two additional decision nodes from inequalities
dd.add_decision(0, 0, poly!([[-1, 1]] < [0]).convert_to(PolyRepr::MatrixBiasGeqZero)); // node index 1
dd.add_decision(0, 1, poly!([[-1, 1]] < [0]).convert_to(PolyRepr::MatrixBiasGeqZero)); // node index 2

// add the terminal nodes with the given functions
// first argument is the parent node, second the label (true / false), and third the affine function
dd.add_terminal(1, 0, aff!([[0, 1]] + [0]));
dd.add_terminal(1, 1, aff!([[1, 0]] + [0]));
dd.add_terminal(2, 0, aff!([[-1, 0]] + [0]));
dd.add_terminal(2, 1, aff!([[0, -1]] + [0]));

// export the tree into the DOT format of graphviz
let mut str = String::new();
dot_str(&mut str, &dd).unwrap();
println!("{}", str);
// digraph dd {
// bgcolor=transparent;
// concentrate=true;
// margin=0;
// n0 [label=" $0 1.00 +$1 1.00 <= 0.00", shape=box];
// n1 [label="−$0 1.00 +$1 1.00 <= 0.00", shape=box];
// n2 [label="−$0 1.00 +$1 1.00 <= 0.00", shape=box];
// n3 [label=" $0 0.00 +$1 1.00 + 0.00", shape=ellipse];
// n4 [label=" $0 1.00 +$1 0.00 + 0.00", shape=ellipse];
// n5 [label="−$0 1.00 +$1 0.00 + 0.00", shape=ellipse];
// n6 [label=" $0 0.00 −$1 1.00 + 0.00", shape=ellipse];
// n0 -> n1 [label=0, style=dashed];
// n0 -> n2 [label=1, style=solid];
// n1 -> n3 [label=0, style=dashed];
// n1 -> n4 [label=1, style=solid];
// n2 -> n5 [label=0, style=dashed];
// n2 -> n6 [label=1, style=solid];
// }

Technical Overview

AffTrees are implemented over an arena provided by the slab crate. They have a compile time branching factor K (in most cases a binary tree is sufficient, i.e., K=2). Elements of the tree have a unique index during their lifetime.

Composition

AffTrees allow a modular construction by composition. The semantics of composition follow directly from the mathematical definition of function composition. Roughly speaking, the composition of two AffTree instances corresponds to an sequential evaluation of the two trees, as demonstrated by the following example.

use affinitree::{aff, pwl::afftree::AffTree};
use ndarray::arr1;

let mut tree0 = AffTree::<2>::from_aff(aff!([[1., 0.]] + [2.]));
tree0.add_child_node(0, 0, aff!([[2, 0], [0, 2]] + [1, 0]));
tree0.add_child_node(0, 1, aff!([[2, 0], [0, 2]] + [0, 1]));

let mut tree1 = AffTree::<2>::from_aff(aff!([[-0.5, 0.]] + [-1.]));
tree1.add_child_node(0, 0, aff!([[3, 0], [0, 3]] + [5, 0]));
tree1.add_child_node(0, 1, aff!([[-3, 0], [0, -3]] + [0, 5]));

let mut comp = tree0.clone();
comp.compose::<false>(&tree1);

// the sequential evaluation of tree0 and tree1 on the input vector (2, -7)
// yields the same result as evaluating the composition tree
assert_eq!(
    tree1.evaluate(&tree0.evaluate(&arr1(&[2., -7.])).unwrap()).unwrap(),
    comp.evaluate(&arr1(&[2., -7.])).unwrap()
);

Fields

tree: Tree<AffContent, K>

in_dim: usize

Implementations

impl<const K: usize> AffTree<K>

pub fn new(dim: usize) -> AffTree<K>

Creates an AffTree instance which represents the identity function for the given dim.

pub fn with_capacity(dim: usize, capacity: usize) -> AffTree<K>

Creates an AffTree instance which represents the identity function for the given dim. Allocates space for as many nodes as specified by capacity (minimum 1).

pub fn from_aff(func: AffFunc) -> AffTree<K>

Creates an AffTree instance which represents the given affine func.

pub fn from_poly(poly: Polytope, func: AffFunc) -> AffTree<K>

Crates an AffTree instance from the given polytope poly. The resulting AffTree is a partial function that only accepts inputs inside the given poly, for which it returns the input as is. In this capacity it can be used as a precondition.

pub fn from_slice(reference_point: &Array1<f64>) -> AffTree<K>

Creates a new AffTree instance which corresponds to the affine AffFunc::slice function.

pub fn from_tree(tree: Tree<AffContent, K>, dim: usize) -> AffTree<K>

Creates a new AffTree instance from a raw tree whose decisions are affine predicates and terminals are affine functions.

pub fn in_dim(&self) -> usize

Returns the input dimension of this tree.

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

Returns true if there are no values in this tree.

pub fn num_terminals(&self) -> usize

Returns the number of terminals in this tree.

pub fn depth(&self) -> usize

Returns the depth of this tree, that is, the length of its longest path.

Correspondingly, an empty tree has depth 0, and a tree with only a root node has depth 1.

pub fn reserve(&mut self, additional: usize)

Reserve capacity for at least additional more nodes to be stored.

See also Tree::reserve.

pub fn nodes(&self) -> impl Iterator<Item = &AffContent>

Returns an iterator over the nodes of this tree. Nodes are read in index order (continuous in memory) for increased efficiency.

pub fn terminals(&self) -> impl Iterator<Item = &AffContent>

Returns an iterator over the terminal nodes of this tree. Nodes are read in index order (continuous in memory) for increased efficiency.

pub fn decisions(&self) -> impl Iterator<Item = &AffContent>

Returns an iterator over the decision nodes of this tree. Nodes are read in index order (continuous in memory) for increased efficiency.

pub fn polyhedra(&self) -> PolyhedraGen

Returns an iterator like object that performs a depth-first search over this tree. For each node in the tree four entries are returned:

1. the current depth,
2. the index of the current node,
3. the number of siblings of the current node that have not been visited yet,
4. the halfspaces of the path leading to the current node

In contrast to polyhedra_iter this function allows mutual access to the tree during iteration.

Examples

use affinitree::pwl::afftree::AffTree;
use affinitree::linalg::affine::{AffFunc, Polytope};

let aff_tree = AffTree::<2>::from_aff(AffFunc::identity(2));
let mut poly_iter = aff_tree.polyhedra();

while let Some((dfs_data, poly)) = poly_iter.next(&aff_tree.tree) {
    println!("{}", Polytope::intersection_n(2, poly));
}

pub fn polyhedra_iter(&self) -> PolyhedraIter<'_, K>

Returns an iterator that performs a depth-first search over this tree. For each node in the tree four entries are returned:

1. the current depth,
2. the index of the current node,
3. the number of siblings of the current node that have not been vistied yet,
4. the halfspaces of the path leading to the current node

For mutual access during iteration see polyhedra_iter.

pub fn add_child_node( &mut self, node: TreeIndex, label: Label, aff: AffFunc ) -> TreeIndex

Adds a single node to the graph directly.

Use with caution: Caller is responsible to uphold invariants.

pub fn add_terminal( &mut self, node: TreeIndex, label: Label, aff: AffFunc ) -> TreeIndex

Adds a single terminal to the graph directly.

Use with caution: Caller is responsible to uphold invariants.

pub fn add_decision( &mut self, node: TreeIndex, label: Label, aff: AffFunc ) -> TreeIndex

Adds a single decision to the graph directly.

Use with caution: Caller is responsible to uphold invariants.

pub fn apply_func_at_node(&mut self, node: TreeIndex, aff: &AffFunc)

Applies given function to a single node of the graph. Updates the solution cache.

Use with caution: Caller is responsible to uphold invariants.

pub fn update_node(&mut self, node: TreeIndex, aff: AffFunc) -> Option<AffFunc>

Overwrite the currently stored function at node to aff and return the previously stored function. Does not reset the solution cache.

Use with caution: Caller is responsible to uphold invariants.

pub fn replace_node(&mut self, node_idx: TreeIndex, aff: AffFunc) -> TreeIndex

Sets given function of a single node of the graph and removes all descendants of original node.

Use with caution: Caller is responsible to uphold invariants.

pub fn apply_func(&mut self, aff_func: &AffFunc)

Combines this tree with the specified aff_func by composing aff_func to the left of all terminal nodes of this tree. This is semantically equivalent to first evaluating this tree and then applying aff_func to the output.

pub fn apply_partial_relu_at_node(&mut self, node: TreeIndex, relu_dim: usize)

pub fn evaluate(&self, input: &Array1<f64>) -> Option<Array1<f64>>

Evaluates this AffTree instance under the given input.

If a maximal iteration number is reached, this function returns None.

Panics

If the input does not evaluate to a terminal node of this tree.

pub fn evaluate_to_terminal<'a>( &'a self, node: &'a AffNode<K>, input: &Array1<f64>, max_iter: i32 ) -> Option<(&AffFunc, Vec<Label>)>

Evaluates this AffTree instance under the given input, returning the corresponding terminal node. The evaluation is started at the given node to a maximum depth of max_iter.

Panics

If the input does not evaluate to a terminal node of this tree.

pub fn evaluate_node(&self, node: &AffNode<K>, input: &Array1<f64>) -> Label

pub fn remove_axes(&mut self, mask: &Array1<bool>)

Removes the specified axes from this afftree.

Keeps the input axes where mask is True and removes all others in the whole tree.

Note: Marked axes are silently dropped, which alters the represented piece-wise linear function. Best used in combination with slicing.

pub fn compose<const PRUNE: bool>(&mut self, other: &AffTree<K>)

Extends self such that it represents the result of mathematical function composition of this tree and other.

Example

use affinitree::{aff, pwl::afftree::AffTree};
use ndarray::arr1;

let mut tree0 = AffTree::<2>::from_aff(aff!([[1., 0.]] + [2.]));
tree0.add_child_node(0, 0, aff!([[2, 0], [0, 2]] + [1, 0]));
tree0.add_child_node(0, 1, aff!([[2, 0], [0, 2]] + [0, 1]));

let mut tree1 = AffTree::<2>::from_aff(aff!([[-0.5, 0.]] + [-1.]));
tree1.add_child_node(0, 0, aff!([[3, 0], [0, 3]] + [5, 0]));
tree1.add_child_node(0, 1, aff!([[-3, 0], [0, -3]] + [0, 5]));

let mut comp = tree0.clone();
comp.compose::<false>(&tree1);

assert_eq!(
    tree1.evaluate(&tree0.evaluate(&arr1(&[2., -7.])).unwrap()).unwrap(),
    comp.evaluate(&arr1(&[2., -7.])).unwrap()
);

pub fn compose_trees(lhs: &AffTree<K>, rhs: &mut AffTree<K>)

pub fn lift_func<I, NFn, TFn, IFn>( lhs: &AffTree<K>, rhs: &mut AffTree<K>, terminals: I, nonterminal_func: NFn, terminal_func: TFn, is_feasible: IFn )

where I: IntoIterator<Item = TreeIndex>, NFn: Fn(&AffFunc, &AffFunc) -> AffFunc, TFn: Fn(&AffFunc, &AffFunc) -> AffFunc, IFn: Fn(&AffTree<K>, TreeIndex, TreeIndex) -> bool,

Apply the function f encoded by lhs to rhs. Technically, this is implemented by appending a copy of lhs to every terminal in rhs. Two callbacks are provided that can update nodes depending on the operation performed, thus allowing to encode a variety of functions.

Each inner node in lhs is updated with the callback nonterminal_func which receives the current inner node of lhs and the terminal node of rhs where this copy is appended. Each terminal node in lhs is updated with the callback terminal_func which receives the current terminal node of lhs and the terminal node of rhs where this copy is appended.

pub fn mirror_points( poly: &Polytope, points: &Array2<f64>, n_iterations: usize ) -> Option<Array2<f64>>

Tries to derive solutions for poly based on the given points.

This function iteratively maximizes the signed distance of each point to each of the supporting hyperplanes of poly. When all distances are positive, the point lies inside the polytope and is thus a solution. This is a heuristic that ignores the interaction between the hyperplanes for improved speed at the cost of completeness. If after n_iterations no solution is found, None is returned. Otherwise, if at any point a valid solution is found, the function returns all valid solutions up to that point.

The first iteration corresponds to a simple containment check.

The columns of points and of the return value represent the points.

pub fn merge_child_with_parent( &mut self, parent_idx: usize, label: Label ) -> Option<TreeNode<AffContent, K>>

pub fn forward_if_redundant( &mut self, parent_idx: usize ) -> Option<TreeNode<AffContent, K>>

Skips over redundant predicates in the tree.

Warning

This function can alter the semantics of tree by removing paths that would otherwise result in errors. It is up to the caller to ensure that this behavior is either impossible (e.g., when all such paths are infeasible) or that this is indeed the intended effect.

pub fn infeasible_elimination(&mut self)

Removes nodes from this tree that lie on infeasible paths.

In a decision structure a path is called infeasible when the conjunction of all decisions on that path is not satisfiable. As no input could ever take such a path, these can be safely removed from the decision structure without altering its semantics (i.e., without changing the represented piece-wise linear function).

pub fn is_edge_feasible(&self, parent_idx: usize, node_idx: usize) -> bool

Test if the edge from parent_idx to node_idx is feasible.

Deprecated: use AffTree::infeasible_elimination to prune infeasible paths instead.

Trait Implementations

impl<const K: usize> Clone for AffTree<K>

fn clone(&self) -> AffTree<K>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const K: usize> Debug for AffTree<K>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const K: usize> Display for AffTree<K>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.