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__(value)

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

Returns:

Optimal normal form decisions.

Return type:

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. Return type: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. Return 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)

Bases: improb.decision.tree.Tree, cdd.NumberTypeable

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)

Bases: improb.decision.tree.Tree

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)

Bases: improb.decision.tree.Tree

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)
#--buy newspaper--O--predict rain------#--take waterproof--O--rain------:9.0
   |                 |                    |                   |
   |                 |                    |                   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
   |
   do not buy-----#--take waterproof--O--rain------:10.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
#--buy newspaper--O--predict rain------#--take waterproof--O--rain------:9.421
                     |                                        |
                     |                                        sunshine--:14.421
                     |
                     predict sunshine--#--no waterproof--O--rain------:4.421
                                                            |
                                                            sunshine--:19.421
newspaper cost = 0.581
#--buy newspaper--O--predict rain------#--take waterproof--O--rain------:9.419
                     |                                        |
                     |                                        sunshine--:14.419
                     |
                     predict sunshine--#--no waterproof--O--rain------:4.419
                                                            |
                                                            sunshine--:19.419
#--do not buy--#--take waterproof--O--rain------:10.0
                                      |
                                      sunshine--:15.0
#--do not buy--#--no waterproof--O--rain------:5.0
                                    |
                                    sunshine--:20.0
newspaper cost = 1.579
#--buy newspaper--O--predict rain------#--take waterproof--O--rain------:8.421
                     |                                        |
                     |                                        sunshine--:13.421
                     |
                     predict sunshine--#--no waterproof--O--rain------:3.421
                                                            |
                                                            sunshine--:18.421
#--do not buy--#--take waterproof--O--rain------:10.0
                                      |
                                      sunshine--:15.0
#--do not buy--#--no waterproof--O--rain------:5.0
                                    |
                                    sunshine--:20.0
newspaper cost = 1.581
#--do not buy--#--take waterproof--O--rain------:10.0
                                      |
                                      sunshine--:15.0
#--do not buy--#--no waterproof--O--rain------:5.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.