a decision tree is a function from assignments to values. More...

#include <DecisionTree.h>

Classes
struct	Choice

struct	Leaf

struct	Node

Public Types
using	Binary = std::function< Y(const Y &, const Y &)>

using	CompareFunc = std::function< bool(const Y &, const Y &)>

using	LabelC = std::pair< L, size_t >

using	LabelFormatter = std::function< std::string(L)>

using	NodePtr = typename Node::Ptr

using	Unary = std::function< Y(const Y &)>

using	UnaryAssignment = std::function< Y(const Assignment< L > &, const Y &)>

using	ValueFormatter = std::function< std::string(Y)>

Public Member Functions
Standard Constructors
	DecisionTree ()

	DecisionTree (const Y &y)

	DecisionTree (const L &label, const Y &y1, const Y &y2)
	Create tree with 2 assignments `y1`, `y2`, splitting on variable `label` More...

	DecisionTree (const LabelC &label, const Y &y1, const Y &y2)

	DecisionTree (const std::vector< LabelC > &labelCs, const std::vector< Y > &ys)

	DecisionTree (const std::vector< LabelC > &labelCs, const std::string &table)

template<typename Iterator >
	DecisionTree (Iterator begin, Iterator end, const L &label)

	DecisionTree (const L &label, const DecisionTree &f0, const DecisionTree &f1)

template<typename X , typename Func >
	DecisionTree (const DecisionTree< L, X > &other, Func Y_of_X)
	Convert from a different value type. More...

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. More...

Testable
void	print (const std::string &s, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter) const
	GTSAM-style print. More...

bool	equals (const DecisionTree &other, const CompareFunc &compare=&DefaultCompare) const

Standard Interface
virtual	~DecisionTree ()=default
	Make virtual. More...

bool	empty () const
	Check if tree is empty. More...

bool	operator== (const DecisionTree &q) const

const Y &	operator() (const Assignment< L > &x) const

template<typename Func >
void	visit (Func f) const
	Visit all leaves in depth-first fashion. More...

template<typename Func >
void	visitLeaf (Func f) const
	Visit all leaves in depth-first fashion. More...

template<typename Func >
void	visitWith (Func f) const
	Visit all leaves in depth-first fashion. More...

size_t	nrLeaves () const
	Return the number of leaves in the tree. More...

template<typename Func , typename X >
X	fold (Func f, X x0) const
	Fold a binary function over the tree, returning accumulator. More...

std::set< L >	labels () const

DecisionTree	apply (const Unary &op) const

DecisionTree	apply (const UnaryAssignment &op) const
	Apply Unary operation "op" to f while also providing the corresponding assignment. More...

DecisionTree	apply (const DecisionTree &g, const Binary &op) const

DecisionTree	choose (const L &label, size_t index) const

DecisionTree	combine (const L &label, size_t cardinality, const Binary &op) const

DecisionTree	combine (const LabelC &labelC, const Binary &op) const

void	dot (std::ostream &os, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const

void	dot (const std::string &name, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const

std::string	dot (const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const

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. More...

Protected Member Functions
template<typename It , typename ValueIt >
NodePtr	build (It begin, It end, ValueIt beginY, ValueIt endY) const

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>. More...

template<typename It , typename ValueIt >
NodePtr	create (It begin, It end, ValueIt beginY, ValueIt endY) const

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

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

Definition at line 63 of file DecisionTree.h.

Member Typedef Documentation

◆ Binary

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::Binary = std::function<Y(const Y&, const Y&)>

Definition at line 78 of file DecisionTree.h.

◆ CompareFunc

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::CompareFunc = std::function<bool(const Y&, const Y&)>

Definition at line 73 of file DecisionTree.h.

◆ LabelC

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::LabelC = std::pair<L, size_t>

A label annotated with cardinality

Definition at line 81 of file DecisionTree.h.

◆ LabelFormatter

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::LabelFormatter = std::function<std::string(L)>

Definition at line 71 of file DecisionTree.h.

◆ 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

Definition at line 147 of file DecisionTree.h.

◆ Unary

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::Unary = std::function<Y(const Y&)>

Handy typedefs for unary and binary function types

Definition at line 76 of file DecisionTree.h.

◆ UnaryAssignment

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::UnaryAssignment = std::function<Y(const Assignment<L>&, const Y&)>

Definition at line 77 of file DecisionTree.h.

◆ ValueFormatter

template<typename L , typename Y >

using gtsam::DecisionTree< L, Y >::ValueFormatter = std::function<std::string(Y)>

Definition at line 72 of file DecisionTree.h.

Constructor & Destructor Documentation

◆ DecisionTree() [1/11]

template<typename L , typename Y >

gtsam::DecisionTree< L, Y >::DecisionTree

Default constructor (for serialization)

Definition at line 482 of file DecisionTree-inl.h.

◆ DecisionTree() [2/11]

template<typename L , typename Y >

gtsam::DecisionTree< L, Y >::DecisionTree ( const Y & y )

explicit

Create a constant

Definition at line 490 of file DecisionTree-inl.h.

◆ DecisionTree() [3/11]

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.

Definition at line 496 of file DecisionTree-inl.h.

◆ DecisionTree() [4/11]

template<typename L , typename Y >

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

Allow Label+Cardinality for convenience

Definition at line 506 of file DecisionTree-inl.h.

◆ DecisionTree() [5/11]

template<typename L , typename Y >

gtsam::DecisionTree< L, Y >::DecisionTree	(	const std::vector< LabelC > &	labelCs,
		const std::vector< Y > &	ys
	)

Create from keys and a corresponding vector of values

Definition at line 519 of file DecisionTree-inl.h.

◆ DecisionTree() [6/11]

template<typename L , typename Y >

gtsam::DecisionTree< L, Y >::DecisionTree	(	const std::vector< LabelC > &	labelCs,
		const std::string &	table
	)

Create from keys and string table

Definition at line 527 of file DecisionTree-inl.h.

◆ DecisionTree() [7/11]

template<typename L , typename Y >

template<typename Iterator >

gtsam::DecisionTree< L, Y >::DecisionTree	(	Iterator	begin,
		Iterator	end,
		const L &	label
	)

Create DecisionTree from others

Definition at line 541 of file DecisionTree-inl.h.

◆ DecisionTree() [8/11]

template<typename L , typename Y >

gtsam::DecisionTree< L, Y >::DecisionTree	(	const L &	label,
		const DecisionTree< L, Y > &	f0,
		const DecisionTree< L, Y > &	f1
	)

Create DecisionTree from two others

Definition at line 548 of file DecisionTree-inl.h.

◆ DecisionTree() [9/11]

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.

Definition at line 557 of file DecisionTree-inl.h.

◆ DecisionTree() [10/11]

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.

Definition at line 567 of file DecisionTree-inl.h.

◆ ~DecisionTree()

template<typename L , typename Y >

virtual gtsam::DecisionTree< L, Y >::~DecisionTree ( )

virtualdefault

Make virtual.

◆ DecisionTree() [11/11]

template<typename L , typename Y >

gtsam::DecisionTree< L, Y >::DecisionTree ( const NodePtr & root )

explicit

Definition at line 485 of file DecisionTree-inl.h.

Member Function Documentation

◆ apply() [1/3]

template<typename L , typename Y >

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

apply binary operation "op" to f and g

Definition at line 945 of file DecisionTree-inl.h.

◆ apply() [2/3]

template<typename L , typename Y >

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

apply Unary operation "op" to f

Definition at line 921 of file DecisionTree-inl.h.

◆ apply() [3/3]

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

Definition at line 932 of file DecisionTree-inl.h.

◆ build()

template<typename L , typename Y >

template<typename It , typename ValueIt >

DecisionTree< L, Y >::NodePtr gtsam::DecisionTree< L, Y >::build	(	It	begin,
		It	end,
		ValueIt	beginY,
		ValueIt	endY
	)		const

protected

Internal recursive function to create from keys, cardinalities, and Y values

Definition at line 649 of file DecisionTree-inl.h.

◆ choose()

template<typename L , typename Y >

DecisionTree gtsam::DecisionTree< L, Y >::choose	(	const L &	label,
		size_t	index
	)		const

inline

create a new function where value(label)==index It's like "restrict" in Darwiche09book pg329, 330?

Definition at line 370 of file DecisionTree.h.

◆ combine() [1/2]

template<typename L , typename Y >

DecisionTree< L, Y > gtsam::DecisionTree< L, Y >::combine	(	const L &	label,
		size_t	cardinality,
		const Binary &	op
	)		const

combine subtrees on key with binary operation "op"

Definition at line 969 of file DecisionTree-inl.h.

◆ combine() [2/2]

template<typename L , typename Y >

DecisionTree gtsam::DecisionTree< L, Y >::combine	(	const LabelC &	labelC,
		const Binary &	op
	)		const

inline

combine with LabelC for convenience

Definition at line 380 of file DecisionTree.h.

◆ compose()

template<typename L , typename Y >

template<typename Iterator >

DecisionTree< L, Y >::NodePtr gtsam::DecisionTree< L, Y >::compose	(	Iterator	begin,
		Iterator	end,
		const L &	label
	)		const

Definition at line 581 of file DecisionTree-inl.h.

◆ 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

Definition at line 703 of file DecisionTree-inl.h.

◆ create()

template<typename L , typename Y >

template<typename It , typename ValueIt >

DecisionTree< L, Y >::NodePtr gtsam::DecisionTree< L, Y >::create	(	It	begin,
		It	end,
		ValueIt	beginY,
		ValueIt	endY
	)		const

protected

Internal helper function to create from keys, cardinalities, and Y values. Calls build which builds thetree bottom-up, before we prune in a top-down fashion.

Definition at line 690 of file DecisionTree-inl.h.

◆ DefaultCompare()

template<typename L , typename Y >

static bool gtsam::DecisionTree< L, Y >::DefaultCompare	(	const Y &	a,
		const Y &	b
	)

inlinestaticprotected

Default method for comparison of two objects of type Y.

Definition at line 66 of file DecisionTree.h.

◆ dot() [1/3]

template<typename L , typename Y >

std::string gtsam::DecisionTree< L, Y >::dot	(	const LabelFormatter &	labelFormatter,
		const ValueFormatter &	valueFormatter,
		bool	showZero = `true`
	)		const

output to graphviz format string

Definition at line 1005 of file DecisionTree-inl.h.

◆ dot() [2/3]

template<typename L , typename Y >

void gtsam::DecisionTree< L, Y >::dot	(	const std::string &	name,
		const LabelFormatter &	labelFormatter,
		const ValueFormatter &	valueFormatter,
		bool	showZero = `true`
	)		const

output to graphviz format, open a file

Definition at line 991 of file DecisionTree-inl.h.

◆ dot() [3/3]

template<typename L , typename Y >

void gtsam::DecisionTree< L, Y >::dot	(	std::ostream &	os,
		const LabelFormatter &	labelFormatter,
		const ValueFormatter &	valueFormatter,
		bool	showZero = `true`
	)		const

output to graphviz format, stream version

Definition at line 981 of file DecisionTree-inl.h.

◆ empty()

template<typename L , typename Y >

bool gtsam::DecisionTree< L, Y >::empty ( ) const

inline

Check if tree is empty.

Definition at line 269 of file DecisionTree.h.

◆ equals()

template<typename L , typename Y >

bool gtsam::DecisionTree< L, Y >::equals	(	const DecisionTree< L, Y > &	other,
		const CompareFunc &	compare = `&DefaultCompare`
	)		const

Definition at line 898 of file DecisionTree-inl.h.

◆ 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);

Definition at line 865 of file DecisionTree-inl.h.

◆ labels()

template<typename L , typename Y >

std::set< L > gtsam::DecisionTree< L, Y >::labels

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.

Definition at line 885 of file DecisionTree-inl.h.

◆ nrLeaves()

template<typename L , typename Y >

size_t gtsam::DecisionTree< L, Y >::nrLeaves

Return the number of leaves in the tree.

Definition at line 855 of file DecisionTree-inl.h.

◆ operator()()

template<typename L , typename Y >

const Y & gtsam::DecisionTree< L, Y >::operator() ( const Assignment< L > & x ) const

evaluate

Definition at line 916 of file DecisionTree-inl.h.

◆ operator==()

template<typename L , typename Y >

bool gtsam::DecisionTree< L, Y >::operator== ( const DecisionTree< L, Y > & q ) const

equality

Definition at line 911 of file DecisionTree-inl.h.

◆ 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.

Definition at line 904 of file DecisionTree-inl.h.

◆ 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);

Definition at line 768 of file DecisionTree-inl.h.

◆ 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);

Definition at line 805 of file DecisionTree-inl.h.

◆ 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);

Definition at line 848 of file DecisionTree-inl.h.

Member Data Documentation

◆ root_

template<typename L , typename Y >

NodePtr gtsam::DecisionTree< L, Y >::root_

A DecisionTree just contains the root. TODO(dellaert): make protected.

Definition at line 150 of file DecisionTree.h.

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

Classes

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Static Protected Member Functions

Detailed Description

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

Member Typedef Documentation

◆ Binary

◆ CompareFunc

◆ LabelC

◆ LabelFormatter

◆ NodePtr

◆ Unary

◆ UnaryAssignment

◆ ValueFormatter

Constructor & Destructor Documentation

◆ DecisionTree() [1/11]

◆ DecisionTree() [2/11]

◆ DecisionTree() [3/11]

◆ DecisionTree() [4/11]

◆ DecisionTree() [5/11]

◆ DecisionTree() [6/11]

◆ DecisionTree() [7/11]

◆ DecisionTree() [8/11]

◆ DecisionTree() [9/11]

◆ DecisionTree() [10/11]

◆ ~DecisionTree()

◆ DecisionTree() [11/11]

Member Function Documentation

◆ apply() [1/3]

◆ apply() [2/3]

◆ apply() [3/3]

◆ build()

◆ choose()

◆ combine() [1/2]

◆ combine() [2/2]

◆ compose()

◆ convertFrom()

◆ create()

◆ DefaultCompare()

◆ dot() [1/3]

◆ dot() [2/3]

◆ dot() [3/3]

◆ empty()

◆ equals()

◆ fold()

◆ labels()

◆ nrLeaves()

◆ operator()()

◆ operator==()

◆ print()

◆ visit()

◆ visitLeaf()

◆ visitWith()

Member Data Documentation

◆ root_

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