How to construct a decision tree.ppt

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,