1、How to construct a decision tree,List each decision nodes & its alternatives. List each chances nodes& its alternatives. Draw the nodes and links. Add costs & probabilities along links Calculate utilities for utility (leftmost) nodes Calculate expected utilities,Example,You need to decide whether to
2、 do a fancy project or a mundane project. Either project can succeed or fail. There is a 10% chance of success for the fancy project, and 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane
3、 project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project should you do?,1. List each decision nodes & its alternatives.,Which project? Fancy Mundane,You need to decide whether to do a fancy project or a mundane project. Either project can succeed
4、 or fail. There is a 10% chance of success for the fancy project, and 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. I
5、f it fails, you get nothing. Which project should you do?,2. List each chance nodes & its alternatives.,Outcome? Success Failure,You need to decide whether to do a fancy project or a mundane project. Either project can succeed or fail. There is a 10% chance of success for the fancy project, and 80%
6、chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project should you do?,3. Draw nodes as
7、 tree,Project?,Fancy,Mundane,Success,Success,Failure,Failure,Decision nodes are square,Chance nodes are oval,Utility nodes are like diamonds,You need to decide whether to do a fancy project or a mundane project. Either project can succeed or fail. There is a 10% chance of success for the fancy proje
8、ct, and 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project should you do?,4. A
9、dd costs and probabilities to links,Project?,Fancy cost 1M$,Mundane cost 0.5M$,Successp=0.1,Success p=0.8,Failure p=0.2,Failure p= 0.9,You need to decide whether to do a fancy project or a mundane project. Either project can succeed or fail. There is a 10% chance of success for the fancy project, an
10、d 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project should you do?,5. Calcula
11、te utility values for utility nodes,Project?,Fancy cost 1M$,Mundane cost 0.5M$,Successp=0.1,Success p=0.8,Failure p=0.2,Failure p= 0.9,Benefit: 0 Cost: 0.5M$,You need to decide whether to do a fancy project or a mundane project. Either project can succeed or fail. There is a 10% chance of success fo
12、r the fancy project, and 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project sh
13、ould you do?,Benefit: 11M$ Cost: 1M$,6. Calculate expected utilities, moving leftward,Project?,Fancy cost 1M$,Mundane cost 0.5M$,Successp=0.1,Success p=0.8,Failure p=0.2,Failure p= 0.9,You need to decide whether to do a fancy project or a mundane project. Either project can succeed or fail. There is
14、 a 10% chance of success for the fancy project, and 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you ge
15、t nothing. Which project should you do?,EU = 0.1*10=1.0,EU = 0.9*(-1)=-0.9,EU = 0.8*1=0.8,EU = 0.2*(-0.5)=-0.1,6. Calculate expected utilities moving leftward,Project?,Fancy cost 1M$,Mundane cost 0.5M$,Successp=0.1,Success p=0.8,Failure p=0.2,Failure p= 0.9,You need to decide whether to do a fancy p
16、roject or a mundane project. Either project can succeed or fail. There is a 10% chance of success for the fancy project, and 80% chance of success for the mundane project. The fancy project costs 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project cost
17、s 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project should you do?,EU = 0.1*10=1.0,EU = 0.9*(-1)=-0.9,EU = 0.8*1=0.8,EU = 0.2*(-0.5)=-0.1,EU = 1.0-0.9= 0.1,EU = 0.8-0.1=0.7,6. Calculate expected utilities moving leftward,Project?,Fancy cost 1M$,Mundane c
18、ost 0.5M$,Successp=0.1,Success p=0.8,Failure p=0.2,Failure p= 0.9,You need to decide whether to do a fancy project or a mundane project. Either project can succeed or fail. There is a 10% chance of success for the fancy project, and 80% chance of success for the mundane project. The fancy project co
19、sts 1M$ to execute, and if it succeeds, you get 11M$. If you lose, you get nothing. The mundane project costs 0.5M$ to execute, and you get 1.5M$ if it succeeds. If it fails, you get nothing. Which project should you do?,EU = 0.1*10=1.0,EU = 0.9*(-1)=-0.9,EU = 0.8*1=0.8,EU = 0.2*(-0.5)=-0.1,EU = 1.0
20、-0.9= 0.1,EU = 0.8-0.1=0.7,Best choice,A more complex example,Your show dog has cancer. If you do nothing, there is a 90% chance she will die. If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying from the surgery, and a 50% chance that the cancer will survive, in which
21、 case, she has the usual 90% chance of dying. If she gets chemo, there is a 20% chance of curing the cancer, and an 80% that the cancer will remain, in which surgery can be performed, with the same risks and outcomes as mentioned above. Chemo cannot be done after surgery, by the way. The dog is wort
22、h 900K$ if she is alive, and nothing if she is dead. Surgery costs $10K and chemo costs 4K$. What should you do?,1. List each decision nodes & its alternatives.,Which treatment? surgery chemo Nothing After chemo fails, which treatment? surgery nothing,Your show dog has cancer. If you do nothing, the
23、re is a 90% chance she will die. If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying from the surgery, and a 50% chance that the cancer will survive, in which case, she has the usual 90% chance of dying. If she gets chemo, there is a 20% chance of curing the cancer, a
24、nd an 80% that the cancer will remain, in which surgery can be performed, with the same risks and outcomes as mentioned above. Chemo cannot be done after surgery, by the way. The dog is worth 900K$ if she is alive, and nothing if she is dead. Surgery costs $10K and chemo costs 4K$. What should you d
25、o?,2. List each chance nodes & its alternatives.,Outcome? Cancer cured Died due to surgery (only for surgery node) Cancer not cured,Your show dog has cancer. If you do nothing, there is a 90% chance she will die. If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying fro
26、m the surgery, and a 50% chance that the cancer will survive, in which case, she has the usual 90% chance of dying. If she gets chemo, there is a 20% chance of curing the cancer, and an 80% that the cancer will remain, in which surgery can be performed, with the same risks and outcomes as mentioned
27、above. Chemo cannot be done after surgery, by the way. The dog is worth 900K$ if she is alive, and nothing if she is dead. Surgery costs $10K and chemo costs 4K$. What should you do?,3. Draw nodes,Treatment?,Surgery,chemo,Cured,Cured ?,Uncured,Surgery kills,Your show dog has cancer. If you do nothin
28、g, there is a 90% chance she will die. If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying from the surgery, and a 50% chance that the cancer will survive, in which case, she has the usual 90% chance of dying. If she gets chemo, there is a 20% chance of curing the can
29、cer, and an 80% that the cancer will remain, in which surgery can be performed, with the same risks and outcomes as mentioned above. Chemo cannot be done after surgery, by the way. The dog is worth 900K$ if she is alive, and nothing if she is dead. Surgery costs $10K and chemo costs 4K$. What should
30、 you do?,Nothing cost 0$,uncured,Die,Live,Die,Live,Die,Live,Treatment?,Surgery,Nothing,4. Add costs & probabilities,Treatment?,Surgery cost 10K$,chemo cost 4K$,Cured p=0.4,Cured p=0.2,Uncured p=0.8,Surgery kills p= 0.1,Your show dog has cancer. If you do nothing, there is a 90% chance she will die.
31、If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying from the surgery, and a 50% chance that the cancer will survive, in which case, she has the usual 90% chance of dying. If she gets chemo, there is a 20% chance of curing the cancer, and an 80% that the cancer will re
32、main, in which surgery can be performed, with the same risks and outcomes as mentioned above. Chemo cannot be done after surgery, by the way. The dog is worth 900K$ if she is alive, and nothing if she is dead. Surgery costs $10K and chemo costs 4K$. What should you do?,Nothing cost 0$,uncured p=0.5,
33、Die p=0.9,Live p=0.1,Die p=0.9,Live p=0.1,Die p=0.9,Live p=0.1,Treatment?,Surgery cost 10K$,Nothing,5. Calculate utility values for utility nodes,Treatment?,Surgery cost 10K$,chemo cost 4K$,Cured p=0.4,Cured p=0.2,Uncured p=0.8,Surgery kills p= 0.1,Your show dog has cancer. If you do nothing, there
34、is a 90% chance she will die. If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying from the surgery, and a 50% chance that the cancer will survive, in which case, she has the usual 90% chance of dying. If she gets chemo, there is a 20% chance of curing the cancer, and
35、an 80% that the cancer will remain, in which surgery can be performed, with the same risks and outcomes as mentioned above. Chemo cannot be done after surgery, by the way. The dog is worth 900K$ if she is alive, and nothing if she is dead. Surgery costs $10K and chemo costs 4K$. What should you do?,
36、Nothing cost 0$,uncured p=0.5,Die p=0.9,Live p=0.1,Die p=0.9,Live p=0.1,Die p=0.9,Live p=0.1,Treatment?,Surgery cost 10K$,Nothing,6. Calculate expected utilities,Treatment?,Surgery cost 10K$ EU=444,chemo cost 4K$ EU=619.2,Cured p=0.4 EU=365,Cured p=0.2 EU=179.2,Uncured p=0.8 EU=440,Surgery kills p=
37、0.1 EU=-1,Your show dog has cancer. If you do nothing, there is a 90% chance she will die. If she has surgery, there is a 40% chance of curing the cancer, 10% chance of dying from the surgery, and a 50% chance that the cancer will survive, in which case, she has the usual 90% chance of dying. If she
38、 gets chemo, there is a 20% chance of curing the cancer, and an 80% that the cancer will remain, in which surgery can be performed, with the same risks and outcomes as mentioned above. Chemo cannot be done after surgery, by the way. The dog is worth 900K$ if she is alive, and nothing if she is dead.
39、 Surgery costs $10K and chemo costs 4K$. What should you do?,Nothing cost 0$ EU=90,uncured p=0.5 EU=80,Die p=0.9 EU= -9,Live p=0.1 EU=89,Die p=0.9 EU=0,Live p=0.1 EU=90,Die p=0.9 EU=-3.6,Live p=0.1 EU=89.6,Treatment?,Surgery cost 10K$ EU=440,Nothing EU=86,My disk drive is flakey. Tech says that ther
40、e is a 10% chance it will crash in the next week, and replacing the disk and data will cost me $200. If I replace the disk, it will cost me $70 and it will not crash. If I save its contents to DVD, reformat and restore it, then it costs me 4 hours (equivalent to $40) but reduces the chance of crashi
41、ng to 3%.,Save, reformat, restore?,No,Yes,Yes p=0.03,Yes p=0.1,No p=0.9,No p= 0.97,Replace disk?,Yes,No,EU = 0.03*(-240)+0.97*(-40) = -46,EU = 0.10*(-200)+0.90*(0) = -20,EU = -70,Quiz question,You will be drilling a water well in your backyard, and you have to decide where to dig it. If you just dig
42、 where you think it is best, there is a 40% chance youll hit water. If you hire a seismologist, the chances increase to 60% but it costs you 10K$. If you hire a water witch, the chance of hitting water is 50% and the cost is 1K$. If you get 50K$ for hitting water, what should you do Draw the decisio
43、n tree Evaluate alternatives Indicate best choice Put your name on the paper and hand it in.,You will be drilling a water well in your backyard, and you have to decide where to dig it. If you just dig where you think it is best, there is a 40% chance youll hit water. If you hire a seismologist, the
44、chances increase to 60% but it costs you 10K$. If you hire a water witch, the chance of hitting water is 50% and the cost is 1K$. If you get 50K$ for hitting water, what should you do?,Seismologist Cost 10K EU=20,Nothing Cost 0$ EU=20,Yes p=0.4 EU=20,Yes p=0.6 EU=24,No p=0.4 EU=-4,No p= 0.5 EU=-0.5,Detector?,Water witch cost 1K$ EU=24,No p= 0.6 EU=0,Yes p=0.5 EU=24.5,
