# Decision Trees¶

class improb.decision.tree.Tree

Abstract base class for decision trees.

```>>> pspace = PSpace("AB", "XY")
>>> A = pspace.make_event("A", "XY", name="A")
>>> B = pspace.make_event("B", "XY", name="B")
>>> X = pspace.make_event("AB", "X", name="X")
>>> Y = pspace.make_event("AB", "Y", name="Y")
>>> t1 = Chance(pspace)
>>> t1[A] = '1' # using strings for fractions
>>> t1[B] = '2/11'
>>> t2 = Chance(pspace)
>>> t2[A] = '5/3'
>>> t2[B] = '6'
>>> t12 = Decision()
>>> t12["d1"] = t1
>>> t12["d2"] = t2
>>> t3 = Chance(pspace)
>>> t3[A] = '8'
>>> t3[B] = '4.5'
>>> t = Chance(pspace)
>>> t[X] = t12
>>> t[Y] = t3
>>> print(t)
O--X--#--d1--O--A--:1
|     |      |
|     |      B--:2/11
|     |
|     d2--O--A--:5/3
|            |
|            B--:6
|
Y--O--A--:8
|
B--:9/2
>>> t.pspace
PSpace([('A', 'X'), ('A', 'Y'), ('B', 'X'), ('B', 'Y')])
>>> for gamble, normal_tree in t.get_normal_form():
...     print(gamble)
...     print('')
('A', 'X') : 1
('A', 'Y') : 8
('B', 'X') : 2/11
('B', 'Y') : 9/2
<BLANKLINE>
('A', 'X') : 5/3
('A', 'Y') : 8
('B', 'X') : 6
('B', 'Y') : 9/2
<BLANKLINE>
>>> for gamble, normal_tree in t.get_normal_form():
...     print(normal_tree)
...     print('')
O--X--#--d1--O--A--:1
|            |
|            B--:2/11
|
Y--O--A--:8
|
B--:9/2
<BLANKLINE>
O--X--#--d2--O--A--:5/3
|            |
|            B--:6
|
Y--O--A--:8
|
B--:9/2
<BLANKLINE>
```
_get_norm_back_opt(opt=None, event=True)

Like get_norm_back_opt() but without applying opt at the root of the tree in the final stage.

All other normal form methods (get_normal_form(), get_norm_opt(), and get_norm_back_opt()) are defined in terms of this method, so subclasses only need to implement this one as far as normal form calculations are concerned.

Add a value to all final reward nodes.

Parameters: value (float or similar; see Values) – The value to add.
__sub__(value)

Subtract a value from all final reward nodes.

Parameters: value (float or similar; see Values) – The value to subtract.
check_pspace()

Check the possibility spaces.

Raise : ValueError on mismatch
get_norm_back_opt(opt=None, event=True)

Like get_norm_opt(), but uses normal form backward induction, which is more efficient.

Warning

If opt does not satisfy certain properties, the result can be different from get_norm_opt().

get_norm_opt(opt=None, event=True)

Get the optimal normal form decisions with respect to the optimality operator opt, conditional on event. This method does not use backward induction: it simply calculates all normal form decisions and then applies opt on them.

Parameters: opt (Opt) – The optimality operator (optional). event (list or similar; see Events) – The event to condition on (optional). Optimal normal form decisions. Yields (Gamble, Tree) pairs, where the tree is a normal form decision (i.e. a tree where each decision node has a single branch), and the gamble is the one induced by this tree.
get_normal_form()

Calculate all normal form decisions, and their corresponding gambles.

Returns: The normal form of the decision tree. Yields (Gamble, Tree) pairs, where the tree is a normal form decision (i.e. a tree where each decision node has a single branch), and the gamble is the one induced by this tree.
get_number_type()

Get the number type of the first reward node in the tree.

Returns: The number type. str
pspace

The possibility space, or None if there are no chance nodes in the tree.

class improb.decision.tree.Reward(reward, number_type=None)

A reward node.

Parameters: reward (float or similar; see Values) – The reward. number_type (str) – The number type (optional). If omitted, get_number_type_from_value() is used.
```>>> t = Reward(5)
>>> print(t.pspace)
None
>>> print(t)
:5.0
>>> list(t.get_normal_form())
[(5.0, Reward(5.0, number_type='float'))]
```
class improb.decision.tree.Decision(data=None)

A decision tree rooted at a decision node.

Parameters: data (collections.Mapping) – Mapping from decisions (i.e. strings, but any immutable object would work) to trees (optional).
```>>> t = Decision({"d1": 5,
...               "d2": 6})
>>> print(t.pspace)
None
>>> print(t) # dict can change ordering
#--d2--:6.0
|
d1--:5.0
>>> for gamble, normal_tree in sorted(t.get_normal_form()):
...     print(gamble)
5.0
6.0
>>> for gamble, normal_tree in sorted(t.get_normal_form()):
...     print(normal_tree)
#--d1--:5.0
#--d2--:6.0
```
class improb.decision.tree.Chance(pspace, data=None)

A decision tree rooted at a chance node.

Parameters: pspace (list or similar; see Possibility Spaces) – The possibility space. data (collections.Mapping) – Mapping from events to trees (optional).
```>>> t = Chance(pspace=(0, 1), data={(0,): 5, (1,): 6})
>>> t.pspace
PSpace(2)
>>> t.get_number_type()
'float'
>>> print(t)
O--(0)--:5.0
|
(1)--:6.0
>>> list(gamble for gamble, normal_tree in t.get_normal_form())
[Gamble(pspace=PSpace(2), mapping={0: 5.0, 1: 6.0})]
```
check_pspace()

Events of the chance nodes must form the possibility space.

```>>> t = Chance(pspace='ab', data={'a': 5, 'ab': 6})
>>> t.check_pspace()
Traceback (most recent call last):
...
ValueError: ...
>>> t = Chance(pspace='ab', data={'a': 5})
>>> t.check_pspace()
Traceback (most recent call last):
...
ValueError: ...
>>> t = Chance(pspace='ab', data={'a': 5, 'b': 6})
>>> t.check_pspace()
```

## Examples¶

Solving the decision tree for the oil wildcatter example in [1]:

```>>> # specify the decision tree
>>> pspace = PSpace('SWD', 'NOC') # soak, wet, dry; no, open, closed
>>> S = pspace.make_event('S', 'NOC', name="soak")
>>> W = pspace.make_event('W', 'NOC', name="wet")
>>> D = pspace.make_event('D', 'NOC', name="dry")
>>> N = pspace.make_event('SWD', 'N', name="no")
>>> O = pspace.make_event('SWD', 'O', name="open")
>>> C = pspace.make_event('SWD', 'C', name="closed")
>>> lpr = LowPoly(pspace)
>>> t0 = 0
>>> t1 = Chance(pspace)
>>> t1[S] = 20
>>> t1[W] = 5
>>> t1[D] = -7
>>> t = Decision()
>>> t["not drill"] = t0
>>> t["drill"] = t1
>>> ss = t - 1
>>> s = Chance(pspace)
>>> s[N] = ss
>>> s[O] = ss
>>> s[C] = ss
>>> u = Decision()
>>> u["sounding"] = s
>>> u["no sounding"] = t
>>> print(u)
#--sounding-----O--no------#--not drill--:-1.0
|               |          |
|               |          drill------O--soak--:19.0
|               |                        |
|               |                        wet---:4.0
|               |                        |
|               |                        dry---:-8.0
|               |
|               open----#--not drill--:-1.0
|               |          |
|               |          drill------O--soak--:19.0
|               |                        |
|               |                        wet---:4.0
|               |                        |
|               |                        dry---:-8.0
|               |
|               closed--#--not drill--:-1.0
|                          |
|                          drill------O--soak--:19.0
|                                        |
|                                        wet---:4.0
|                                        |
|                                        dry---:-8.0
|
no sounding--#--not drill--:0.0
|
drill------O--soak--:20.0
|
wet---:5.0
|
dry---:-7.0
>>> lpr = LowPoly(pspace)
>>> lpr[N, True] = (0.183, 0.222)
>>> lpr[O, True] = (0.333, 0.363)
>>> lpr[C, True] = (0.444, 0.454)
>>> lpr[D, N] = (0.500, 0.666)
>>> lpr[D, O] = (0.222, 0.333)
>>> lpr[D, C] = (0.111, 0.166)
>>> lpr[W, N] = (0.222, 0.272)
>>> lpr[W, O] = (0.363, 0.444)
>>> lpr[W, C] = (0.333, 0.363)
>>> lpr[S, N] = (0.125, 0.181)
>>> lpr[S, O] = (0.250, 0.363)
>>> lpr[S, C] = (0.454, 0.625)
>>> opt = OptLowPrevMax(lpr)
>>> for gamble, normal_tree in u.get_norm_back_opt(opt):
...     print(normal_tree)
#--no sounding--#--drill--O--soak--:20.0
|
wet---:5.0
|
dry---:-7.0
>>> # note: backopt should be normopt for maximality!! let's check...
>>> for gamble, normal_tree in u.get_norm_opt(opt):
...     print(normal_tree)
#--no sounding--#--drill--O--soak--:20.0
|
wet---:5.0
|
dry---:-7.0
```

Solving the lake district example:

```>>> c = 1 # cost of newspaper
>>> pspace = PSpace('rs','RS')
>>> R_ = pspace.make_event('r', 'RS', name='predict rain')
>>> S_ = pspace.make_event('s', 'RS', name='predict sunshine')
>>> R = pspace.make_event('rs', 'R', name='rain')
>>> S = pspace.make_event('rs', 'S', name='sunshine')
>>> t0 = Chance(pspace)
>>> t0[R] = 10
>>> t0[S] = 15
>>> t1 = Chance(pspace)
>>> t1[R] = 5
>>> t1[S] = 20
>>> t = Decision()
>>> t["take waterproof"] = t0
>>> t["no waterproof"] = t1
>>> s = Chance(pspace)
>>> s[R_] = t
>>> s[S_] = t
>>> u = Decision()
>>> u["buy newspaper"] = s - c
>>> u["do not buy"] = t
>>> print(u)
|                 |                    |                   |
|                 |                    |                   sunshine--:14.0
|                 |                    |
|                 |                    no waterproof----O--rain------:4.0
|                 |                                        |
|                 |                                        sunshine--:19.0
|                 |
|                 predict sunshine--#--take waterproof--O--rain------:9.0
|                                      |                   |
|                                      |                   sunshine--:14.0
|                                      |
|                                      no waterproof----O--rain------:4.0
|                                                          |
|                                                          sunshine--:19.0
|
|                   |
|                   sunshine--:15.0
|
no waterproof----O--rain------:5.0
|
sunshine--:20.0
>>> lpr = LowPoly(pspace)
>>> lpr[R_ & R, True] = (0.42 * 0.9, None)
>>> lpr[R_ & S, True] = (0.18 * 0.9, None)
>>> lpr[S_ & R, True] = (0.08 * 0.9, None)
>>> lpr[S_ & S, True] = (0.32 * 0.9, None)
>>> for c in [0.579, 0.581, 1.579, 1.581]:
...     print("newspaper cost = {0}".format(c))
...     u["buy newspaper"] = s - c
...     opt = OptLowPrevMax(lpr)
...     for gamble, normal_tree in u.get_norm_back_opt(opt):
...         print(normal_tree)
newspaper cost = 0.579
|                                        |
|                                        sunshine--:14.421
|
predict sunshine--#--no waterproof--O--rain------:4.421
|
sunshine--:19.421
newspaper cost = 0.581
|                                        |
|                                        sunshine--:14.419
|
predict sunshine--#--no waterproof--O--rain------:4.419
|
sunshine--:19.419
|
sunshine--:15.0
|
sunshine--:20.0
newspaper cost = 1.579
|                                        |
|                                        sunshine--:13.421
|
predict sunshine--#--no waterproof--O--rain------:3.421
|
sunshine--:18.421
|
sunshine--:15.0
|
sunshine--:20.0
newspaper cost = 1.581
|
sunshine--:15.0
|
sunshine--:20.0
```

Footnotes

 [1] Kikuti, D., Cozman, F., de Campos, C.: Partially ordered preferences in decision trees: Computing strategies with imprecision in probabilities. In: R. Brafman, U. Junker (eds.) IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, pp. 118–123, 2005.