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 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 |
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) |
a decision tree is a function from assignments to values.
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:
More examples can be found in testDecisionTree.cpp
Definition at line 62 of file DecisionTree.h.
using gtsam::DecisionTree< L, Y >::Binary = std::function<Y(const Y&, const Y&)> |
Definition at line 77 of file DecisionTree.h.
using gtsam::DecisionTree< L, Y >::CompareFunc = std::function<bool(const Y&, const Y&)> |
Definition at line 72 of file DecisionTree.h.
A label annotated with cardinality
Definition at line 80 of file DecisionTree.h.
using gtsam::DecisionTree< L, Y >::LabelFormatter = std::function<std::string(L)> |
Definition at line 70 of file DecisionTree.h.
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.
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.
using gtsam::DecisionTree< L, Y >::UnaryAssignment = std::function<Y(const Assignment<L>&, const Y&)> |
Definition at line 76 of file DecisionTree.h.
using gtsam::DecisionTree< L, Y >::ValueFormatter = std::function<std::string(Y)> |
Definition at line 71 of file DecisionTree.h.
gtsam::DecisionTree< L, Y >::DecisionTree |
Default constructor (for serialization)
Definition at line 491 of file DecisionTree-inl.h.
|
explicit |
Create a constant
Definition at line 499 of file DecisionTree-inl.h.
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
label | The variable to split on. |
y1 | The value for the first assignment. |
y2 | The value for the second assignment. |
Definition at line 505 of file DecisionTree-inl.h.
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.
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.
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.
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.
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.
|
noexcept |
Move constructor for DecisionTree. Very efficient as does not allocate anything, just changes in-place. But other
is consumed.
op | The unary operation to apply to the moved DecisionTree. |
other | The DecisionTree to move from, will be empty afterwards. |
Definition at line 564 of file DecisionTree-inl.h.
gtsam::DecisionTree< L, Y >::DecisionTree | ( | const DecisionTree< L, X > & | other, |
Func | Y_of_X | ||
) |
Convert from a different value type.
X | The previous value type. |
other | The DecisionTree to convert from. |
Y_of_X | Functor to convert from value type X to type Y. |
Definition at line 595 of file DecisionTree-inl.h.
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.
M | Previous label type. |
X | Previous value type. |
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 603 of file DecisionTree-inl.h.
|
virtualdefault |
Make virtual.
|
explicit |
Definition at line 494 of file DecisionTree-inl.h.
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.
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.
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.
op | Function which takes Assignment<L> and Y as input and returns object of type Y. |
Definition at line 1012 of file DecisionTree-inl.h.
|
staticprotected |
Internal recursive function to create from keys, cardinalities, and Y values
Definition at line 687 of file DecisionTree-inl.h.
|
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.
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.
|
inline |
combine with LabelC for convenience
Definition at line 401 of file DecisionTree.h.
|
static |
Definition at line 617 of file DecisionTree-inl.h.
|
staticprotected |
Convert from a DecisionTree<L, X> to DecisionTree<L, Y>.
M | The previous label type. |
X | The previous value type. |
f | The node pointer to the root of the previous DecisionTree. |
Y_of_X | Functor to convert from value type X to type Y. |
Definition at line 742 of file DecisionTree-inl.h.
|
staticprotected |
Convert from a DecisionTree<M, X> to DecisionTree<L, Y>.
M | The previous label type. |
X | The previous value type. |
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. |
Definition at line 772 of file DecisionTree-inl.h.
|
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.
|
inlinestaticprotected |
Default method for comparison of two objects of type Y.
Definition at line 65 of file DecisionTree.h.
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.
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.
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.
|
inline |
Check if tree is empty.
Definition at line 290 of file DecisionTree.h.
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.
X gtsam::DecisionTree< L, Y >::fold | ( | Func | f, |
X | x0 | ||
) | const |
Fold a binary function over the tree, returning accumulator.
X | type for accumulator. |
f | binary function: Y * X -> X returning an updated accumulator. |
x0 | initial value for accumulator. |
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.
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.
size_t gtsam::DecisionTree< L, Y >::nrLeaves |
Return the number of leaves in the tree.
Definition at line 929 of file DecisionTree-inl.h.
const Y & gtsam::DecisionTree< L, Y >::operator() | ( | const Assignment< L > & | x | ) | const |
evaluate
Definition at line 991 of file DecisionTree-inl.h.
bool gtsam::DecisionTree< L, Y >::operator== | ( | const DecisionTree< L, Y > & | q | ) | const |
equality
Definition at line 985 of file DecisionTree-inl.h.
void gtsam::DecisionTree< L, Y >::print | ( | const std::string & | s, |
const LabelFormatter & | labelFormatter, | ||
const ValueFormatter & | valueFormatter | ||
) | const |
GTSAM-style print.
s | Prefix string. |
labelFormatter | Functor to format the node label. |
valueFormatter | Functor to format the node value. |
Definition at line 978 of file DecisionTree-inl.h.
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.
AB_of_Y | Functor to convert from type X to std::pair<A, B>. |
Definition at line 1096 of file DecisionTree-inl.h.
void gtsam::DecisionTree< L, Y >::visit | ( | Func | f | ) | const |
Visit all leaves in depth-first fashion.
f | (side-effect) Function taking the value of the leaf node. |
Example: int sum = 0; auto visitor = [&](int y) { sum += y; }; tree.visit(visitor);
Definition at line 842 of file DecisionTree-inl.h.
void gtsam::DecisionTree< L, Y >::visitLeaf | ( | Func | f | ) | const |
Visit all leaves in depth-first fashion.
f | (side-effect) Function taking the leaf node pointer. |
Example: int sum = 0; auto visitor = [&](const Leaf& leaf) { sum += leaf.constant(); }; tree.visitLeaf(visitor);
Definition at line 879 of file DecisionTree-inl.h.
void gtsam::DecisionTree< L, Y >::visitWith | ( | Func | f | ) | const |
Visit all leaves in depth-first fashion.
f | (side-effect) Function taking an assignment and a value. |
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.
NodePtr gtsam::DecisionTree< L, Y >::root_ |
A DecisionTree just contains the root. TODO(dellaert): make protected.
Definition at line 149 of file DecisionTree.h.