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

#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 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
 
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 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 >

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

Definition at line 49 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 64 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 59 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 67 of file DecisionTree.h.

◆ LabelFormatter

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

Definition at line 57 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 133 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 62 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 63 of file DecisionTree.h.

◆ ValueFormatter

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

Definition at line 58 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 466 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 476 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

Definition at line 482 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 492 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 505 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 513 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 527 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 534 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
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 543 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
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 553 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 470 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 Unary op) const

apply Unary operation "op" to f

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

◆ apply() [2/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 901 of file DecisionTree-inl.h.

◆ apply() [3/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 914 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 341 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 938 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 351 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 567 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
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 672 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 recursive function to create from keys, cardinalities, and Y values

Definition at line 634 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 52 of file DecisionTree.h.

◆ dot() [1/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 950 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 960 of file DecisionTree-inl.h.

◆ dot() [3/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 974 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 240 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 867 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 834 of file DecisionTree-inl.h.

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

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

◆ nrLeaves()

template<typename L , typename Y >
size_t gtsam::DecisionTree< L, Y >::nrLeaves ( ) const

Return the number of leaves in the tree.

Definition at line 824 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 885 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 880 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 873 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 737 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 774 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 817 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 136 of file DecisionTree.h.


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


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:46:16