Loading...
Searching...
No Matches
gtsam::DecisionTree< L, Y > Class Template Reference
Discrete

## 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
gtsam::DecisionTree::DecisionTree
DecisionTree()
Default constructor (for serialization).
Definition DecisionTree-inl.h:462

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:

- /build/gtsam-Xg031d/gtsam-4.2.0+dfsg/gtsam/discrete/DecisionTree.h
- /build/gtsam-Xg031d/gtsam-4.2.0+dfsg/gtsam/discrete/DecisionTree-inl.h