Classes | Public Types | Public Attributes | Static Protected Member Functions | List of all members
gtsam::DecisionTree< L, Y > Class Template Reference

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)
 
 DecisionTree (const Unary &op, DecisionTree &&other) noexcept
 Move constructor for DecisionTree. Very efficient as does not allocate anything, just changes in-place. But other is consumed. More...
 
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 translate 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 Yoperator() (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< Llabels () 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
 
template<typename A , typename B >
std::pair< DecisionTree< L, A >, DecisionTree< L, B > > split (std::function< std::pair< A, B >(const Y &)> AB_of_Y) const
 Convert into two trees with value types A and B. More...
 

Public Attributes

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

Static Protected Member Functions

template<typename It , typename ValueIt >
static NodePtr build (It begin, It end, ValueIt beginY, ValueIt endY)
 
template<typename X >
static NodePtr convertFrom (const typename DecisionTree< L, X >::NodePtr &f, std::function< Y(const X &)> Y_of_X)
 Convert from a DecisionTree<L, X> to DecisionTree<L, Y>. More...
 
template<typename M , typename X >
static 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)
 Convert from a DecisionTree<M, X> to DecisionTree<L, Y>. More...
 
template<typename It , typename ValueIt >
static NodePtr create (It begin, It end, ValueIt beginY, ValueIt endY)
 
static bool DefaultCompare (const Y &a, const Y &b)
 Default method for comparison of two objects of type Y. More...
 

Advanced Interface

 DecisionTree (const NodePtr &root)
 
template<typename Iterator >
static NodePtr compose (Iterator begin, Iterator end, const L &label)
 

Detailed Description

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

a decision tree is a function from assignments to values.

Template Parameters
Llabel for variables
Yfunction 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 62 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 77 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 72 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 80 of file DecisionTree.h.

◆ LabelFormatter

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

Definition at line 70 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 146 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 75 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 76 of file DecisionTree.h.

◆ ValueFormatter

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

Definition at line 71 of file DecisionTree.h.

Constructor & Destructor Documentation

◆ DecisionTree() [1/12]

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

Default constructor (for serialization)

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

◆ DecisionTree() [2/12]

template<typename L , typename Y >
gtsam::DecisionTree< L, Y >::DecisionTree ( const Y y)
explicit

Create a constant

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

◆ DecisionTree() [3/12]

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
labelThe variable to split on.
y1The value for the first assignment.
y2The value for the second assignment.

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

◆ DecisionTree() [4/12]

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 515 of file DecisionTree-inl.h.

◆ DecisionTree() [5/12]

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 527 of file DecisionTree-inl.h.

◆ DecisionTree() [6/12]

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 535 of file DecisionTree-inl.h.

◆ DecisionTree() [7/12]

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 549 of file DecisionTree-inl.h.

◆ DecisionTree() [8/12]

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 556 of file DecisionTree-inl.h.

◆ DecisionTree() [9/12]

template<typename L , typename Y >
gtsam::DecisionTree< L, Y >::DecisionTree ( const Unary op,
DecisionTree< L, Y > &&  other 
)
noexcept

Move constructor for DecisionTree. Very efficient as does not allocate anything, just changes in-place. But other is consumed.

Parameters
opThe unary operation to apply to the moved DecisionTree.
otherThe DecisionTree to move from, will be empty afterwards.

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

◆ DecisionTree() [10/12]

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
XThe previous value type.
Parameters
otherThe DecisionTree to convert from.
Y_of_XFunctor to convert from value type X to type Y.

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

◆ DecisionTree() [11/12]

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 translate labels via map from type M to L.

Template Parameters
MPrevious label type.
XPrevious value type.
Parameters
otherThe decision tree to convert.
L_of_MMap from label type M to type L.
Y_of_XFunctor to convert from type X to type Y.

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

◆ ~DecisionTree()

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

Make virtual.

◆ DecisionTree() [12/12]

template<typename L , typename Y >
gtsam::DecisionTree< L, Y >::DecisionTree ( const NodePtr root)
explicit

Definition at line 494 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 1025 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 1000 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
opFunction which takes Assignment<L> and Y as input and returns object of type Y.
Returns
DecisionTree

Definition at line 1012 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 
)
staticprotected

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

Definition at line 687 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 391 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 1049 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 401 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 
)
static

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

◆ convertFrom() [1/2]

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

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

Template Parameters
MThe previous label type.
XThe previous value type.
Parameters
fThe node pointer to the root of the previous DecisionTree.
Y_of_XFunctor to convert from value type X to type Y.
Returns
NodePtr

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

◆ convertFrom() [2/2]

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 
)
staticprotected

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

Template Parameters
MThe previous label type.
XThe previous value type.
Parameters
fThe node pointer to the root of the previous DecisionTree.
L_of_MFunctor to convert from label type M to type L.
Y_of_XFunctor to convert from value type X to type Y.
Returns
NodePtr

Definition at line 772 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 
)
staticprotected

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

Definition at line 729 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 65 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 1085 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 1071 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 1061 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 290 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 972 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
Xtype for accumulator.
Parameters
fbinary function: Y * X -> X returning an updated accumulator.
x0initial 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 939 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 959 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 929 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 991 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 985 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
sPrefix string.
labelFormatterFunctor to format the node label.
valueFormatterFunctor to format the node value.

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

◆ split()

template<typename L , typename Y >
template<typename A , typename B >
std::pair< DecisionTree< L, A >, DecisionTree< L, B > > gtsam::DecisionTree< L, Y >::split ( std::function< std::pair< A, B >(const Y &)>  AB_of_Y) const

Convert into two trees with value types A and B.

Template Parameters
AFirst new value type.
BSecond new value type.
Parameters
AB_of_YFunctor to convert from type X to std::pair<A, B>.
Returns
A pair of DecisionTrees with value types A and B respectively.

Definition at line 1096 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 842 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 879 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 922 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 149 of file DecisionTree.h.


The documentation for this class was generated from the following files:
tree
Definition: testExpression.cpp:212


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:15:21