This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:dydaktyka:problog:lab2 [2017/06/04 13:39] msl created |
en:dydaktyka:problog:lab2 [2019/06/27 15:49] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Probabilistic Programming — Probabilistic Graphs ====== | + | ====== Probabilistic Programming — Probabilistic Graphs and Decision Theory ====== |
| Graph structures are commonly used to represent knowledge across various domains and problems. It shouldn't be surprising that they are also present in many probabilistic models. In this class we will introduce probabilistic graphs --- weighted graphs with weights representing probabilities. Next, there will be very short introduction to decision theory in Problog. Finally we will try to escape from zombies which clearly shows usefulness of this class. | Graph structures are commonly used to represent knowledge across various domains and problems. It shouldn't be surprising that they are also present in many probabilistic models. In this class we will introduce probabilistic graphs --- weighted graphs with weights representing probabilities. Next, there will be very short introduction to decision theory in Problog. Finally we will try to escape from zombies which clearly shows usefulness of this class. | ||
| Line 9: | Line 9: | ||
| {{ :en:dydaktyka:problog:probabilistic_graph.png?direct&500 |}} | {{ :en:dydaktyka:problog:probabilistic_graph.png?direct&500 |}} | ||
| + | You can easily represent this graph in Problog as a list of edges: | ||
| + | <code prolog> | ||
| + | 0.8::edge(1,2). | ||
| + | 0.2::edge(1,3). | ||
| + | 0.2::edge(1,4). | ||
| + | 0.2::edge(2,3). | ||
| + | 0.7::edge(3,5). | ||
| + | 0.3::edge(4,5). | ||
| + | </code> | ||
| + | The weight should be interpreted as a probability that transition from node to node (from state to state?) succeeds. | ||
| + | |||
| + | We can now write a rule (the same as in classical Prolog) to check if there is a path in a graph, i.e. | ||
| + | <code prolog> | ||
| + | % there is a direct path between the nodes, if there is an edge between those nodes | ||
| + | path(A,B) :- edge(A,B). | ||
| + | % there is a indirect path between the nodes, if there is an intermediate node | ||
| + | % that can be reached directly from the first node, and from which you can reach the second node | ||
| + | path(A,C) :- edge(A,B), | ||
| + | B \= C, | ||
| + | path(B,C). | ||
| + | </code> | ||
| + | |||
| + | Now you can ask Problog, what is the probability of reaching ''5'' from ''1''. | ||
| + | |||
| + | <code prolog> | ||
| + | query(path(1,5)). | ||
| + | </code> | ||
| + | |||
| + | Test it! | ||
| + | |||
| + | ==== Zombie Epidemics ==== | ||
| + | |||
| + | {{ :en:dydaktyka:problog:zombie_epidemic.png?direct&600 |}} | ||
| + | |||
| + | One of the most popular use cases for graphs in probabilistic programming is to model social networks, where people interact with other people, leading to spread of information or... zombies. We will model here a simplified case of zombie epidemics. More serious (also probabilistic) approach can be found in a great article: [[https://arxiv.org/abs/1311.6376|"Bayesian Analysis of Epidemics — Zombies, Influenza, and other Diseases"]]. Here we will focus on an early phase of the zombie epidemics in a shopping mall. Here goes the story: | ||
| + | |||
| + | //Someone very evil and mischievous leaked a zombie virus in a shopping mall air conditioning system. This way of spreading the virus isn't very efficient, but there is 0.1 probability that somebody will get ill just from breathing the bad air. What makes situation worse is that the virus attracts the already infected people. There is a high chance (0.6), that the healthy people will get infected if they get in a physical contact with already infected ones.// | ||
| + | |||
| + | So, the situation is clear. We have some people in the mall, to save computing time let's say there are eight friend. In order to make your life easier, we will generate them using a built-in Problog predicate ''between/3''. | ||
| + | |||
| + | <code prolog> | ||
| + | human(X) :- between(1, 8, X). | ||
| + | </code> | ||
| + | |||
| + | Now, some of them (let's say first 2) are already infected. | ||
| + | |||
| + | <code prolog> | ||
| + | initially_infected(X) :- human(X), X < 3. | ||
| + | </code> | ||
| + | |||
| + | And finally our probabilistic graph! We will say that two people can get in a physical contact with 0.1 probability. It's a very dense graph (clique) with quite weak edges. | ||
| + | |||
| + | <code prolog> | ||
| + | % X \= Y, because you can't meet yourself | ||
| + | 0.1::contact(X,Y) :- human(X), human(Y), X \= Y. | ||
| + | </code> | ||
| + | |||
| + | === Assignments === | ||
| + | |||
| + | - add missing rules for the virus spread: | ||
| + | * you can be already infected | ||
| + | * you can get infected because of the bad air | ||
| + | * you can get infected via contacting an infected person | ||
| + | - check what is the probability that any human gets infected | ||
| + | * how would it change if there was only one infected person in the beginning? | ||
| + | * how would it change if one couldn't get infected via air? | ||
| + | - introduce a new element to the model: some people are naturally resistant to the virus | ||
| + | * if you are resistant, you can't get infected by air | ||
| + | * the probability that a resistant person will get infected via physical contact is halved | ||
| + | * hint: [[http://ai.ia.agh.edu.pl/wiki/en:dydaktyka:problog:lab1#predicting_treatment_s_effects|previous class]] | ||
| + | - make third and fourth people resistant to the virus | ||
| + | * what is the impact of the resistant people on the whole population? | ||
| + | |||
| + | ==== Left 4 Dead ==== | ||
| + | |||
| + | {{ :en:dydaktyka:problog:left4dead.jpg?direct&200|}} | ||
| + | OK. The epidemics started and unfortunately you and your three friend are the only ones who remained human in the whole shopping mall. Now you have to escape. After the initial disbelief and inevitable panic, you start planning your escape. You are aware of only two viable escape routes: you have a car in the parking lot and there is a helicopter pad on the roof of the mall. | ||
| + | |||
| + | Despite the high risk of meeting zombies on every route, both targets have additional sets of problems: | ||
| + | * you have to get gas from the nearby gas station if you want to use the car | ||
| + | * the cellular network is dead (what happened?!) and you have to get to the only radio station (security room) in the mall to contact the army so the can send the helicopter; what's more you're not sure if the helicopter will be here soon enough to save you. | ||
| + | |||
| + | The graph below shows both plans --- graph weights represent probability that your team will survive the travel. | ||
| + | |||
| + | {{ :en:dydaktyka:problog:escape_plan_1.png?direct&600 |}} | ||
| + | |||
| + | === Assignments === | ||
| + | |||
| + | - model the escape plan as a program in Problog | ||
| + | - which escape route is more probable according to the Problog query engine? | ||
| + | |||
| + | ==== Decision Theory for the Rescue ==== | ||
| + | |||
| + | OK, you have two possible plans, but there is no agreement which one should be pursued. You start arguing with other, screams of the zombies attacking the door don't help at all. Finally one of you knows a little of mathematics that could help. Decision theory is a branch of mathematics connected to the game theory --- the idea is to compare different actions according to some axioms that people believe to be rational. If you want to know more, read a [[http://www2.stat.duke.edu/~scs/Courses/STAT102/DecisionTheoryTutorial.pdf|qucik introduction]], but for now it will be enough to know that: | ||
| + | |||
| + | - we have to formalize what decisions can we make, in Problog is it enough to put question mark in place of a probability to mark that we are dealing with a decision, e.g. if we have to decide if we should sell the house, we can model it in Problog using one line: <code prolog>?::sell_house.</code> | ||
| + | - we have to define utility/cost function that describes how much we value a certain outcome and how much it will cost us. In Problog there exists a built-in predicate ''utility'', e.g. to say that death is a very unwanted situation, you could write: <code prolog>utility(death, -100)</code> and to say that getting a job is very valued: <code problog>utility(got_job, 50)</code> | ||
| + | |||
| + | Then we calculate the estimated outcome based on the probability theory and voila, we find which decision is the best at the moment. In the Problog online editor just choose ''DTProblog'' from the available actions. | ||
| + | |||
| + | === Assignments === | ||
| + | |||
| + | - Analyze and run the basic umbrella/raincoat decision problem: <code prolog>% probabilistic facts | ||
| + | 0.3::rain. | ||
| + | 0.5::wind. | ||
| + | |||
| + | % decision facts | ||
| + | ?::umbrella. | ||
| + | ?::raincoat. | ||
| + | |||
| + | broken_umbrella :- umbrella, rain, wind. | ||
| + | dry :- rain, raincoat. | ||
| + | dry :- rain, umbrella, not broken_umbrella. | ||
| + | dry :- not(rain). | ||
| + | |||
| + | % utilities | ||
| + | utility(broken_umbrella, -40). | ||
| + | utility(raincoat, -20). | ||
| + | utility(umbrella, -2). | ||
| + | utility(dry, 60).</code> | ||
| + | - Use decision theory to select the best of the escape routes from zombies | ||
| + | * there are two actions: ''go(highway)'', ''go(helicopter)'' | ||
| + | * getting to the highway has quite high utility value (i.e. ''50'') but getting to the flying military fortress is much better (i.e. ''100'') | ||
| + | * you have to say that you go the gas station only if you decide to try the highway; analogically for the helicopter | ||
| + | - the escape plan got a bit more complicated... there are two cars near the mall: one close to the mall (but very old and already destroyed a bit by the zombies, it may not work) and second one, more far away, but in much better condition. There is a new decision to make: to which car will you go first after getting the gas (you can always try to switch car later)? | ||
| + | * now you can make three possible decisions; update the model and repeat calculations | ||
| + | * the graph representing the new problem is presented below | ||
| + | |||
| + | {{ :en:dydaktyka:problog:escape_plan_2.png?direct&400 |}} | ||
| + | |||
| + | |||
