Newer
Older
6001
6002
6003
6004
6005
6006
6007
6008
6009
6010
6011
6012
6013
6014
6015
6016
6017
6018
6019
6020
6021
6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
6052
6053
6054
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
6082
6083
6084
6085
6086
6087
6088
6089
6090
6091
6092
6093
6094
6095
6096
6097
6098
6099
6100
6101
6102
6103
6104
6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
6125
6126
6127
6128
6129
6130
6131
6132
6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143
"An agent is said to be _rational_ if and only if it chooses the action that yields the highest expected utility, averaged over all the possible outcomes of the action."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we'll see how a decision-theoretic agent is implemented in the module."
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">DTAgentProgram</span><span class=\"p\">(</span><span class=\"n\">belief_state</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""A decision-theoretic agent. [Figure 13.1]"""</span>\n",
" <span class=\"k\">def</span> <span class=\"nf\">program</span><span class=\"p\">(</span><span class=\"n\">percept</span><span class=\"p\">):</span>\n",
" <span class=\"n\">belief_state</span><span class=\"o\">.</span><span class=\"n\">observe</span><span class=\"p\">(</span><span class=\"n\">program</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">percept</span><span class=\"p\">)</span>\n",
" <span class=\"n\">program</span><span class=\"o\">.</span><span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"n\">argmax</span><span class=\"p\">(</span><span class=\"n\">belief_state</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">(),</span>\n",
" <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"n\">belief_state</span><span class=\"o\">.</span><span class=\"n\">expected_outcome_utility</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">program</span><span class=\"o\">.</span><span class=\"n\">action</span>\n",
" <span class=\"n\">program</span><span class=\"o\">.</span><span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"bp\">None</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">program</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(DTAgentProgram)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `DTAgentProgram` function is pretty self-explanatory.\n",
"<br>\n",
"It encapsulates a function `program` that takes in an observation or a `percept`, updates its `belief_state` and returns the action that maximizes the `expected_outcome_utility`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## INFORMATION GATHERING AGENT\n",
"Before we discuss what an information gathering agent is, we'll need to know what decision networks are.\n",
"For an agent in an environment, a decision network represents information about the agent's current state, its possible actions, the state that will result from the agent's action, and the utility of that state.\n",
"Decision networks have three primary kinds of nodes which are:\n",
"1. __Chance nodes__: These represent random variables, just like in Bayesian networks.\n",
"2. __Decision nodes__: These represent points where the decision-makes has a choice between different actions and the decision maker tries to find the optimal decision at these nodes with regard to the cost, safety and resulting utility.\n",
"3. __Utility nodes__: These represent the agent's utility function.\n",
"A description of the agent's utility as a function is associated with a utility node.\n",
"<br>\n",
"<br>\n",
"To evaluate a decision network, we do the following:\n",
"1. Initialize the evidence variables according to the current state.\n",
"2. Calculate posterior probabilities for each possible value of the decision node and calculate the utility resulting from that action.\n",
"3. Return the action with the highest utility.\n",
"<br>\n",
"Let's have a look at the implementation of the `DecisionNetwork` class."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"data": {
6168
6169
6170
6171
6172
6173
6174
6175
6176
6177
6178
6179
6180
6181
6182
6183
6184
6185
6186
6187
6188
6189
6190
6191
6192
6193
6194
6195
6196
6197
6198
6199
6200
6201
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
6213
6214
6215
6216
6217
6218
6219
6220
6221
6222
6223
6224
6225
6226
6227
6228
6229
6230
6231
6232
6233
6234
6235
6236
6237
6238
6239
6240
6241
6242
6243
6244
6245
6246
6247
6248
6249
6250
6251
6252
6253
6254
6255
6256
6257
6258
6259
6260
6261
6262
6263
6264
6265
6266
6267
6268
6269
6270
6271
6272
6273
6274
6275
6276
6277
6278
6279
6280
6281
6282
6283
6284
6285
6286
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">DecisionNetwork</span><span class=\"p\">(</span><span class=\"n\">BayesNet</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""An abstract class for a decision network as a wrapper for a BayesNet.</span>\n",
"<span class=\"sd\"> Represents an agent's current state, its possible actions, reachable states</span>\n",
"<span class=\"sd\"> and utilities of those states."""</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">infer</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""action: a single action node</span>\n",
"<span class=\"sd\"> infer: the preferred method to carry out inference on the given BayesNet"""</span>\n",
" <span class=\"nb\">super</span><span class=\"p\">(</span><span class=\"n\">DecisionNetwork</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"fm\">__init__</span><span class=\"p\">()</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"n\">action</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">infer</span> <span class=\"o\">=</span> <span class=\"n\">infer</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">best_action</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the best action in the network"""</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">action</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">get_utility</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the utility for a particular action and state in the network"""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">get_expected_utility</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">evidence</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Compute the expected utility given an action and evidence"""</span>\n",
" <span class=\"n\">u</span> <span class=\"o\">=</span> <span class=\"mf\">0.0</span>\n",
" <span class=\"n\">prob_dist</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">infer</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">evidence</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">prob</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">item</span><span class=\"p\">,</span> <span class=\"n\">_</span> <span class=\"ow\">in</span> <span class=\"n\">prob_dist</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
" <span class=\"n\">u</span> <span class=\"o\">+=</span> <span class=\"n\">prob_dist</span><span class=\"p\">[</span><span class=\"n\">item</span><span class=\"p\">]</span> <span class=\"o\">*</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">get_utility</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">item</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">return</span> <span class=\"n\">u</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(DecisionNetwork)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `DecisionNetwork` class inherits from `BayesNet` and has a few extra helper methods.\n",
"<br>\n",
"`best_action` returns the best action in the network.\n",
"<br>\n",
"`get_utility` is an abstract method which is supposed to return the utility of a particular action and state in the network.\n",
"<br>\n",
"`get_expected_utility` computes the expected utility, given an action and evidence.\n",
"<br>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before we proceed, we need to know a few more terms.\n",
"<br>\n",
"Having __perfect information__ refers to a state of being fully aware of the current state, the cost functions and the outcomes of actions.\n",
"This in turn allows an agent to find the exact utility value of each state.\n",
"If an agent has perfect information about the environment, maximum expected utility calculations are exact and can be computed with absolute certainty.\n",
"<br>\n",
"In decision theory, the __value of perfect information__ (VPI) is the price that an agent would be willing to pay in order to gain access to _perfect information_.\n",
"VPI calculations are extensively used to calculate expected utilities for nodes in a decision network.\n",
"<br>\n",
"For a random variable $E_j$ whose value is currently unknown, the value of discovering $E_j$, given current information $e$ must average over all possible values $e_{jk}$ that we might discover for $E_j$, using our _current_ beliefs about its value.\n",
"The VPI of $E_j$ is then given by:\n",
"<br>\n",
"<br>\n",
"$$VPI_e(E_j) = \\left(\\sum_{k}P(E_j=e_{jk}\\ |\\ e) EU(\\alpha_{e_{jk}}\\ |\\ e, E_j=e_{jk})\\right) - EU(\\alpha\\ |\\ e)$$\n",
"<br>\n",
"VPI is _non-negative_, _non-additive_ and _order-indepentent_."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"An information gathering agent is an agent with certain properties that explores decision networks as and when required with heuristics driven by VPI calculations of nodes.\n",
"A sensible agent should ask questions in a reasonable order, should avoid asking irrelevant questions, should take into account the importance of each piece of information in relation to its cost and should stop asking questions when that is appropriate.\n",
"_VPI_ is used as the primary heuristic to consider all these points in an information gathering agent as the agent ultimately wants to maximize the utility and needs to find the optimal cost and extent of finding the required information.\n",
"<br>\n",
"As an overview, an information gathering agent works by repeatedly selecting the observations with the highest information value, until the cost of the next observation is greater than its expected benefit.\n",
"<br>\n",
"The `InformationGatheringAgent` class is an abstract class that inherits from `Agent` and works on the principles discussed above.\n",
"Let's have a look.\n",
"<br>"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"data": {
6357
6358
6359
6360
6361
6362
6363
6364
6365
6366
6367
6368
6369
6370
6371
6372
6373
6374
6375
6376
6377
6378
6379
6380
6381
6382
6383
6384
6385
6386
6387
6388
6389
6390
6391
6392
6393
6394
6395
6396
6397
6398
6399
6400
6401
6402
6403
6404
6405
6406
6407
6408
6409
6410
6411
6412
6413
6414
6415
6416
6417
6418
6419
6420
6421
6422
6423
6424
6425
6426
6427
6428
6429
6430
6431
6432
6433
6434
6435
6436
6437
6438
6439
6440
6441
6442
6443
6444
6445
6446
6447
6448
6449
6450
6451
6452
6453
6454
6455
6456
6457
6458
6459
6460
6461
6462
6463
6464
6465
6466
6467
6468
6469
6470
6471
6472
6473
6474
6475
6476
6477
6478
6479
6480
6481
6482
6483
6484
6485
6486
6487
6488
6489
6490
6491
6492
6493
6494
6495
6496
6497
6498
6499
6500
6501
6502
6503
6504
6505
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">InformationGatheringAgent</span><span class=\"p\">(</span><span class=\"n\">Agent</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""A simple information gathering agent. The agent works by repeatedly selecting</span>\n",
"<span class=\"sd\"> the observation with the highest information value, until the cost of the next</span>\n",
"<span class=\"sd\"> observation is greater than its expected benefit. [Figure 16.9]"""</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">decnet</span><span class=\"p\">,</span> <span class=\"n\">infer</span><span class=\"p\">,</span> <span class=\"n\">initial_evidence</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""decnet: a decision network</span>\n",
"<span class=\"sd\"> infer: the preferred method to carry out inference on the given decision network</span>\n",
"<span class=\"sd\"> initial_evidence: initial evidence"""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">decnet</span> <span class=\"o\">=</span> <span class=\"n\">decnet</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">infer</span> <span class=\"o\">=</span> <span class=\"n\">infer</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">observation</span> <span class=\"o\">=</span> <span class=\"n\">initial_evidence</span> <span class=\"ow\">or</span> <span class=\"p\">[]</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">decnet</span><span class=\"o\">.</span><span class=\"n\">nodes</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">integrate_percept</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">percept</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Integrate the given percept into the decision network"""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">execute</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">percept</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Execute the information gathering algorithm"""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">observation</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">integrate_percept</span><span class=\"p\">(</span><span class=\"n\">percept</span><span class=\"p\">)</span>\n",
" <span class=\"n\">vpis</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">vpi_cost_ratio</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
" <span class=\"n\">j</span> <span class=\"o\">=</span> <span class=\"n\">argmax</span><span class=\"p\">(</span><span class=\"n\">vpis</span><span class=\"p\">)</span>\n",
" <span class=\"n\">variable</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">[</span><span class=\"n\">j</span><span class=\"p\">]</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">vpi</span><span class=\"p\">(</span><span class=\"n\">variable</span><span class=\"p\">)</span> <span class=\"o\">></span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">cost</span><span class=\"p\">(</span><span class=\"n\">variable</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">request</span><span class=\"p\">(</span><span class=\"n\">variable</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">decnet</span><span class=\"o\">.</span><span class=\"n\">best_action</span><span class=\"p\">()</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">request</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">variable</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the value of the given random variable as the next percept"""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">cost</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the cost of obtaining evidence through tests, consultants or questions"""</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">NotImplementedError</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">vpi_cost_ratio</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">variables</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return the VPI to cost ratio for the given variables"""</span>\n",
" <span class=\"n\">v_by_c</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"n\">variables</span><span class=\"p\">:</span>\n",
" <span class=\"n\">v_by_c</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">vpi</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">)</span> <span class=\"o\">/</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">cost</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">))</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">v_by_c</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">vpi</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">variable</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Return VPI for a given variable"""</span>\n",
" <span class=\"n\">vpi</span> <span class=\"o\">=</span> <span class=\"mf\">0.0</span>\n",
" <span class=\"n\">prob_dist</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">infer</span><span class=\"p\">(</span><span class=\"n\">variable</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">observation</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">decnet</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">prob</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">item</span><span class=\"p\">,</span> <span class=\"n\">_</span> <span class=\"ow\">in</span> <span class=\"n\">prob_dist</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
" <span class=\"n\">post_prob</span> <span class=\"o\">=</span> <span class=\"n\">prob_dist</span><span class=\"p\">[</span><span class=\"n\">item</span><span class=\"p\">]</span>\n",
" <span class=\"n\">new_observation</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">observation</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_observation</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">item</span><span class=\"p\">)</span>\n",
" <span class=\"n\">expected_utility</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">decnet</span><span class=\"o\">.</span><span class=\"n\">get_expected_utility</span><span class=\"p\">(</span><span class=\"n\">variable</span><span class=\"p\">,</span> <span class=\"n\">new_observation</span><span class=\"p\">)</span>\n",
" <span class=\"n\">vpi</span> <span class=\"o\">+=</span> <span class=\"n\">post_prob</span> <span class=\"o\">*</span> <span class=\"n\">expected_utility</span>\n",
"\n",
" <span class=\"n\">vpi</span> <span class=\"o\">-=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">decnet</span><span class=\"o\">.</span><span class=\"n\">get_expected_utility</span><span class=\"p\">(</span><span class=\"n\">variable</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">observation</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">vpi</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(InformationGatheringAgent)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `cost` method is an abstract method that returns the cost of obtaining the evidence through tests, consultants, questions or any other means.\n",
"<br>\n",
"The `request` method returns the value of the given random variable as the next percept.\n",
"<br>\n",
"The `vpi_cost_ratio` method returns a list of VPI divided by cost for each variable in the `variables` list provided to it.\n",
"<br>\n",
"The `vpi` method calculates the VPI for a given variable\n",
"<br>\n",
"And finally, the `execute` method executes the general information gathering algorithm, as described in __figure 16.9__ in the book.\n",
"<br>\n",
"Our agent implements a form of information gathering that is called __myopic__ as the VPI formula is used shortsightedly here.\n",
"It calculates the value of information as if only a single evidence variable will be acquired.\n",
"This is similar to greedy search, where we do not look at the bigger picture and aim for local optimizations to hopefully reach the global optimum.\n",
"This often works well in practice but a myopic agent might hastily take an action when it would have been better to request more variables before taking an action.\n",
"A _conditional plan_, on the other hand might work better for some scenarios.\n",
"<br>\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With this we conclude this notebook."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
}
},
"nbformat": 4,
"nbformat_minor": 2