Detailed Description

template<typename L, typename Y>
class gtsam::DecisionTree< L, Y >

a decision tree is a function from assignments to values.

Template Parameters

L	label for variables
Y	function range (any algebra), e.g., bool, int, double

After creating a decision tree on some variables, the tree can be evaluated on an assignment to those variables. Example:

// Create a decision stump one one variable 'a' with values 10 and 20.
DecisionTree<char, int> tree('a', 10, 20);
 
// Evaluate the tree on an assignment to the variable.
int value0 = tree({{'a', 0}}); // value0 = 10
int value1 = tree({{'a', 1}}); // value1 = 20

More examples can be found in testDecisionTree.cpp

Inheritance diagram for gtsam::DecisionTree< L, Y >:

Public Member Functions
Standard Constructors
	DecisionTree ()
	Default constructor (for serialization).
	DecisionTree (const Y &y)
	Create a constant.
	DecisionTree (const L &label, const Y &y1, const Y &y2)
	Create tree with 2 assignments y1, y2, splitting on variable label.
	DecisionTree (const LabelC &label, const Y &y1, const Y &y2)
	Allow Label+Cardinality for convenience.
	DecisionTree (const std::vector< LabelC > &labelCs, const std::vector< Y > &ys)
	Create from keys and a corresponding vector of values.
	DecisionTree (const std::vector< LabelC > &labelCs, const std::string &table)
	Create from keys and string table.
template<typename Iterator>
	DecisionTree (Iterator begin, Iterator end, const L &label)
	Create DecisionTree from others.
	DecisionTree (const L &label, const DecisionTree &f0, const DecisionTree &f1)
	Create DecisionTree from two others.
template<typename X, typename Func>
	DecisionTree (const DecisionTree< L, X > &other, Func Y_of_X)
	Convert from a different value type.
template<typename M, typename X, typename Func>
	DecisionTree (const DecisionTree< M, X > &other, const std::map< M, L > &map, Func Y_of_X)
	Convert from a different value type X to value type Y, also transate labels via map from type M to L.
Testable
void	print (const std::string &s, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter) const
	GTSAM-style print.
bool	equals (const DecisionTree &other, const CompareFunc &compare=&DefaultCompare) const
Standard Interface
virtual	~DecisionTree ()=default
	Make virtual.
bool	empty () const
	Check if tree is empty.
bool	operator== (const DecisionTree &q) const
	equality
const Y &	operator() (const Assignment< L > &x) const
	evaluate
template<typename Func>
void	visit (Func f) const
	Visit all leaves in depth-first fashion.
template<typename Func>
void	visitLeaf (Func f) const
	Visit all leaves in depth-first fashion.
template<typename Func>
void	visitWith (Func f) const
	Visit all leaves in depth-first fashion.
size_t	nrLeaves () const
	Return the number of leaves in the tree.
template<typename Func, typename X>
X	fold (Func f, X x0) const
	Fold a binary function over the tree, returning accumulator.
std::set< L >	labels () const
	Retrieve all unique labels as a set.
DecisionTree	apply (const Unary &op) const
	apply Unary operation "op" to f
DecisionTree	apply (const UnaryAssignment &op) const
	Apply Unary operation "op" to f while also providing the corresponding assignment.
DecisionTree	apply (const DecisionTree &g, const Binary &op) const
	apply binary operation "op" to f and g
DecisionTree	choose (const L &label, size_t index) const
	create a new function where value(label)==index It's like "restrict" in Darwiche09book pg329, 330?
DecisionTree	combine (const L &label, size_t cardinality, const Binary &op) const
	combine subtrees on key with binary operation "op"
DecisionTree	combine (const LabelC &labelC, const Binary &op) const
	combine with LabelC for convenience
void	dot (std::ostream &os, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
	output to graphviz format, stream version
void	dot (const std::string &name, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
	output to graphviz format, open a file
std::string	dot (const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
	output to graphviz format string
Advanced Interface
	DecisionTree (const NodePtr &root)
template<typename Iterator>
NodePtr	compose (Iterator begin, Iterator end, const L &label) const

Public Attributes
NodePtr	root_
	A DecisionTree just contains the root. TODO(dellaert): make protected.

Public Types
using	LabelFormatter = std::function<std::string(L)>
using	ValueFormatter = std::function<std::string(Y)>
using	CompareFunc = std::function<bool(const Y&, const Y&)>
using	Unary = std::function<Y(const Y&)>
	Handy typedefs for unary and binary function types.
using	UnaryAssignment = std::function<Y(const Assignment<L>&, const Y&)>
using	Binary = std::function<Y(const Y&, const Y&)>
using	LabelC = std::pair<L, size_t>
	A label annotated with cardinality.
using	NodePtr = typename Node::Ptr
	---------------------— Node base class ------------------------—

Classes
struct	Node
	---------------------— Node base class ------------------------— More...
struct	Leaf
struct	Choice

Protected Member Functions
template<typename It, typename ValueIt>
NodePtr	create (It begin, It end, ValueIt beginY, ValueIt endY) const
	Internal recursive function to create from keys, cardinalities, and Y values.
template<typename M, typename X>
NodePtr	convertFrom (const typename DecisionTree< M, X >::NodePtr &f, std::function< L(const M &)> L_of_M, std::function< Y(const X &)> Y_of_X) const
	Convert from a DecisionTree<M, X> to DecisionTree<L, Y>.

Static Protected Member Functions
static bool	DefaultCompare (const Y &a, const Y &b)
	Default method for comparison of two objects of type Y.

Friends
class	boost::serialization::access
	Serialization function.

Member Typedef Documentation

◆ NodePtr

template<typename L, typename Y>

using gtsam::DecisionTree< L, Y >::NodePtr = typename Node::Ptr

---------------------— Node base class ------------------------—

A function is a shared pointer to the root of a DT

Constructor & Destructor Documentation

◆ DecisionTree() [1/3]

template<typename L, typename Y>

gtsam::DecisionTree< L, Y >::DecisionTree	(	const L &	label,
		const Y &	y1,
		const Y &	y2 )

Create tree with 2 assignments y1, y2, splitting on variable label.

Parameters

label	The variable to split on.
y1	The value for the first assignment.
y2	The value for the second assignment.

◆ DecisionTree() [2/3]

template<typename L, typename Y>

template<typename X, typename Func>

gtsam::DecisionTree< L, Y >::DecisionTree	(	const DecisionTree< L, X > &	other,
		Func	Y_of_X )

Convert from a different value type.

Template Parameters

X	The previous value type.

Parameters

other	The DecisionTree to convert from.
Y_of_X	Functor to convert from value type X to type Y.

◆ DecisionTree() [3/3]

template<typename L, typename Y>

template<typename M, typename X, typename Func>

gtsam::DecisionTree< L, Y >::DecisionTree	(	const DecisionTree< M, X > &	other,
		const std::map< M, L > &	map,
		Func	Y_of_X )

Convert from a different value type X to value type Y, also transate labels via map from type M to L.

Template Parameters

M	Previous label type.
X	Previous value type.

Parameters

other	The decision tree to convert.
L_of_M	Map from label type M to type L.
Y_of_X	Functor to convert from type X to type Y.

Member Function Documentation

◆ apply()

template<typename L, typename Y>

DecisionTree< L, Y > gtsam::DecisionTree< L, Y >::apply ( const UnaryAssignment & op ) const

Apply Unary operation "op" to f while also providing the corresponding assignment.

Apply unary operator with assignment.

Parameters

op	Function which takes Assignment<L> and Y as input and returns object of type Y.

Returns: DecisionTree

◆ convertFrom()

template<typename L, typename Y>

template<typename M, typename X>

DecisionTree< L, Y >::NodePtr gtsam::DecisionTree< L, Y >::convertFrom	(	const typename DecisionTree< M, X >::NodePtr &	f,
		std::function< L(const M &)>	L_of_M,
		std::function< Y(const X &)>	Y_of_X ) const

protected

Convert from a DecisionTree<M, X> to DecisionTree<L, Y>.

Template Parameters

M	The previous label type.
X	The previous value type.

Parameters

f	The node pointer to the root of the previous DecisionTree.
L_of_M	Functor to convert from label type M to type L.
Y_of_X	Functor to convert from value type X to type Y.

Returns: NodePtr

◆ fold()

template<typename L, typename Y>

template<typename Func, typename X>

X gtsam::DecisionTree< L, Y >::fold	(	Func	f,
		X	x0 ) const

Fold a binary function over the tree, returning accumulator.

Template Parameters

X	type for accumulator.

Parameters

f	binary function: Y * X -> X returning an updated accumulator.
x0	initial value for accumulator.

Returns: X final value for accumulator.

Note: X is always passed by value.; Due to pruning, leaves might not exhaust choices.

Example: auto add = [](const double& y, double x) { return y + x; }; double sum = tree.fold(add, 0.0);

◆ labels()

template<typename L, typename Y>

std::set< L > gtsam::DecisionTree< L, Y >::labels ( ) const

Retrieve all unique labels as a set.

Get (partial) labels by performing a visit.

This method performs a depth-first search to go to every leaf and records the keys assignment which leads to that leaf. Since the tree can be pruned, there might be a leaf at a lower depth which results in a partial assignment (i.e. not all keys are specified).

E.g. given a tree with 3 keys, there may be a branch where the 3rd key has the same values for all the leaves. This leads to the branch being pruned so we get a leaf which is arrived at by just the first 2 keys and their assignments.

◆ print()

template<typename L, typename Y>

void gtsam::DecisionTree< L, Y >::print	(	const std::string &	s,
		const LabelFormatter &	labelFormatter,
		const ValueFormatter &	valueFormatter ) const

GTSAM-style print.

Parameters

s	Prefix string.
labelFormatter	Functor to format the node label.
valueFormatter	Functor to format the node value.

◆ visit()

template<typename L, typename Y>

template<typename Func>

void gtsam::DecisionTree< L, Y >::visit ( Func f ) const

Visit all leaves in depth-first fashion.

Parameters

f	(side-effect) Function taking the value of the leaf node.

Note: Due to pruning, the number of leaves may not be the same as the number of assignments. E.g. if we have a tree on 2 binary variables with all values being 1, then there are 2^2=4 assignments, but only 1 leaf.

Example: int sum = 0; auto visitor = [&](int y) { sum += y; }; tree.visit(visitor);

◆ visitLeaf()

template<typename L, typename Y>

template<typename Func>

void gtsam::DecisionTree< L, Y >::visitLeaf ( Func f ) const

Visit all leaves in depth-first fashion.

Parameters

f	(side-effect) Function taking the leaf node pointer.

Note: Due to pruning, the number of leaves may not be the same as the number of assignments. E.g. if we have a tree on 2 binary variables with all values being 1, then there are 2^2=4 assignments, but only 1 leaf.

Example: int sum = 0; auto visitor = [&](const Leaf& leaf) { sum += leaf.constant(); }; tree.visitLeaf(visitor);

◆ visitWith()

template<typename L, typename Y>

template<typename Func>

void gtsam::DecisionTree< L, Y >::visitWith ( Func f ) const

Visit all leaves in depth-first fashion.

Parameters

f	(side-effect) Function taking an assignment and a value.

Note: Due to pruning, the number of leaves may not be the same as the number of assignments. E.g. if we have a tree on 2 binary variables with all values being 1, then there are 2^2=4 assignments, but only 1 leaf.

Example: int sum = 0; auto visitor = [&](const Assignment<L>& assignment, int y) { sum += y; }; tree.visitWith(visitor);

The documentation for this class was generated from the following files:

/tmp/gtsam-4.2-docs.H5EUbA/src/gtsam/discrete/DecisionTree.h
/tmp/gtsam-4.2-docs.H5EUbA/src/gtsam/discrete/DecisionTree-inl.h

Detailed Description

Public Member Functions

Public Attributes

Public Types

Classes

Protected Member Functions

Static Protected Member Functions

Friends

Member Typedef Documentation

◆ NodePtr

Constructor & Destructor Documentation

◆ DecisionTree() [1/3]

◆ DecisionTree() [2/3]

◆ DecisionTree() [3/3]

Member Function Documentation

◆ apply()

◆ convertFrom()

◆ fold()

◆ labels()

◆ print()

◆ visit()

◆ visitLeaf()

◆ visitWith()