This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:dydaktyka:problog:intro [2017/05/15 03:09] msl [First-Order Logic For The Rescue] |
en:dydaktyka:problog:intro [2019/06/27 15:49] (current) |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| ===== Tools ===== | ===== Tools ===== | ||
| - | In this class we will use [[https://dtai.cs.kuleuven.be/problog/|ProbLog]] language, which is based on Prolog. If you haven't head of this language, read [[https://bernardopires.com/2013/10/try-logic-programming-a-gentle-introduction-to-prolog/|this short and gentle introduction]] and later do the [[http://lpn.swi-prolog.org/lpnpage.php?pageid=online|more comprehensive tutorial in your free time]]. | + | In this class we will use [[https://dtai.cs.kuleuven.be/problog/|ProbLog]] language, which is based on Prolog. If you haven't heard of this language, read [[https://bernardopires.com/2013/10/try-logic-programming-a-gentle-introduction-to-prolog/|this short and gentle introduction]] and later do the [[http://lpn.swi-prolog.org/lpnpage.php?pageid=online|more comprehensive tutorial in your free time]]. |
| For now, you should now that you can use ProbLog in two different ways: | For now, you should now that you can use ProbLog in two different ways: | ||
| - from command line: ''problog <path to file with model>'' | - from command line: ''problog <path to file with model>'' | ||
| - | - from [[https://dtai.cs.kuleuven.be/problog/editor.html''| interactive web environment]] | + | - from [[https://dtai.cs.kuleuven.be/problog/editor.html| interactive web environment]] |
| ===== First Model ===== | ===== First Model ===== | ||
| Line 29: | Line 29: | ||
| <code prolog> | <code prolog> | ||
| - | 0.5::head. | + | 0.5::heads. |
| </code> | </code> | ||
| - | And now we will write a first rule, that says: 'If the handwriting is illegible and I get head, the student pass the exam'. | + | And now we will write a first rule, that says: 'If the handwriting is illegible and I get heads, the student pass the exam'. |
| <code prolog> | <code prolog> | ||
| - | pass_exam :- illegible_handwriting, head. | + | pass_exam :- illegible_handwriting, heads. |
| </code> | </code> | ||
| Line 45: | Line 45: | ||
| 0.4::student_knows_the_answer. | 0.4::student_knows_the_answer. | ||
| - | pass_exam :- \+ illegible_handwriting, student_knows_the_answer. | + | pass_exam :- student_knows_the_answer, \+ illegible_handwriting. |
| </code> | </code> | ||
| Line 89: | Line 89: | ||
| <code prolog> | <code prolog> | ||
| - | evidence(student_knows_the_answer). | + | evidence(student_knows_the_answer, true). |
| </code> | </code> | ||
| Add this line to the model a re-evaulate it. What is the impact of knowledge on the probability of passing the exam. Isn't it motivating? | Add this line to the model a re-evaulate it. What is the impact of knowledge on the probability of passing the exam. Isn't it motivating? | ||
| - | Try to add different evidences, e.g. that student doesn't know the answer (use ''\+'' as negation). | + | Try to add different evidences, e.g. that student doesn't know the answer (use ''false'' instead of ''true''). |
| ===== Students Live In Groups ===== | ===== Students Live In Groups ===== | ||
| Line 104: | Line 104: | ||
| <code prolog> | <code prolog> | ||
| 0.9::joan_has_illegible_writing. | 0.9::joan_has_illegible_writing. | ||
| - | 0.9::marcus_has_illegible_writing. | + | 0.9::maxwell_has_illegible_writing. |
| - | 0.5::joan_tossed_head. | + | 0.5::joan_tossed_heads. |
| - | 0.5::marcus_tossed_head. | + | 0.5::maxwell_tossed_heads. |
| - | joan_pass_exam :- joan_has_illegible_writing, joan_tossed_head. | + | joan_pass_exam :- joan_has_illegible_writing, joan_tossed_heads. |
| - | marcus_pass_exam :- marcus_has_illegible_writing, marcus_tossed_head. | + | maxwell_pass_exam :- maxwell_has_illegible_writing, maxwell_tossed_heads. |
| query(joan_pass_exam). | query(joan_pass_exam). | ||
| - | query(marcus_pass_exam). | + | query(maxwell_pass_exam). |
| </code> | </code> | ||
| It could work, but it certainly wouldn't be a manageable solution for more than three students... In order to model bigger herds we will use power of first-order logic! | It could work, but it certainly wouldn't be a manageable solution for more than three students... In order to model bigger herds we will use power of first-order logic! | ||
| - | ==== First-Order Logic For The Rescue ==== | + | ==== First-Order Logic To The Rescue ==== |
| First things first --- we need to redefine our probabilistic facts. | First things first --- we need to redefine our probabilistic facts. | ||
| - | <code problog> | + | <code prolog> |
| - | 0.9::has_illegible_writing(marcus). | + | 0.9::has_illegible_writing(maxwell). |
| 0.9::has_illegible_writing(joan). | 0.9::has_illegible_writing(joan). | ||
| - | 0.5::heads(marcus). | + | 0.5::heads(maxwell). |
| 0.5::heads(joan). | 0.5::heads(joan). | ||
| - | 0.4::knows_the_answer(marcus). | + | 0.4::knows_the_answer(maxwell). |
| 0.4::knows_the_answer(joan). | 0.4::knows_the_answer(joan). | ||
| </code> | </code> | ||
| - | The facts now are //predicates// and therefore have arguments. It's neat, but in comparison to our previous approach, it doesn't save too much space... But let's focus on the rules --- we would like to say: "Student named ****** passes the exam if the student named ******* has illegible handwriting and when tossed the coin for him, we got heads. In ProbLog (and Prolog) ******* is represented by variable, which starts with a big letter. | + | The facts are //predicates// now and therefore have arguments. It's neat, but in comparison to our previous approach, it doesn't save too much space... But let's focus on the rules --- we would like to say: "Student passes the exam if he/she has illegible handwriting and when tossed the coin for him/her, we got heads. In ProbLog (and Prolog) an unspecified object is represented by a variable, which starts with a big letter. |
| - | <code problog> | + | <code prolog> |
| - | pass_exam(Student) :- has_illegible_writing(Student), heads(Student). | + | pass_exam(Student) :- heads(Student), has_illegible_writing(Student). |
| - | pass_exam(Student) :- \+ has_illegible_writing(Student), knows_the_answer(Student). | + | pass_exam(Student) :- knows_the_answer(Student), \+ has_illegible_writing(Student). |
| </code> | </code> | ||
| - | Try to ran the following model and check what is the probability of passing the exam by Joan. Try to add some evidence to the model. | + | <WRAP center round tip 95%> |
| + | Good advice: if you use negation (''\+'') together with variables in the rule body, be sure that the variable has been already used in the same rule body in a positive context, e.g. don't write | ||
| + | |||
| + | ''\+ has_illegible_writing(Student), knows_the_answer(Student)'', | ||
| + | |||
| + | because variable ''Student'' is used here first in the negative context. If you want to know details, learn more about Prolog ;) | ||
| + | </WRAP> | ||
| + | |||
| + | Try to run the following model and check what is the probability of passing the exam by Joan. Try to add some evidence to the model. | ||
| + | |||
| + | ==== Non-Deterministic Rules Save The Day ==== | ||
| + | |||
| + | Still, we have some redundancy in the code. Our probabilistic facts are simply duplicated and every programmer should instantly think of a way to get rid of the duplicates. In order to do that we should first extract somewhere the list of students. We will use plain deterministic (probability equal 100% can be omitted) facts. | ||
| + | |||
| + | <code prolog> | ||
| + | student(maxwell). student(joan). | ||
| + | </code> | ||
| + | |||
| + | Then we will rewrite our original probabilistic facts as probabilistic rules: | ||
| + | |||
| + | <code prolog> | ||
| + | 0.9::has_illegible_writing(Name) :- student(Name). | ||
| + | </code> | ||
| + | |||
| + | Do the same with the other fact and check the new model. Isn't it neat? | ||
| + | |||
| + | ===== Levels of illegibility ===== | ||
| + | |||
| + | Okay. We haven't be fair --- there is no way to simply classify all the handwriting in only two classes. There is at least third one: 'partly_legible'. In order to model that we will need to introduce a second argument to our probabilistic fact. | ||
| + | |||
| + | <code prolog> | ||
| + | 0.5::handwriting(Name, illegible) :- student(Name). | ||
| + | 0.4::handwriting(Name, partly_legible) :- student(Name). | ||
| + | 0.1::handwriting(Name, legible) :- student(Name). | ||
| + | </code> | ||
| + | |||
| + | We also have have to add a new rule, that takes care of what happens when teacher is able to read only a part of the answer. | ||
| + | |||
| + | <code prolog> | ||
| + | 0.3::pass_exam(Student) :- handwriting(Student, partly_legible), \+ knows_the_answer(Student). | ||
| + | 0.7::pass_exam(Student) :- handwriting(Student, partly_legible), knows_the_answer(student). | ||
| + | </code> | ||
| + | |||
| + | Update rest of the rules accordingly and check if the model still works. What is the chance of passing the exam by Maxwell, who knows the answer but his handwriting is only partly legible? | ||
| + | |||
| + | ==== Last Fixes ==== | ||
| + | |||
| + | There is one problem with the approach we've used with ''handwriting'' predicate. Have you noticed? All three facts ''handwriting(Student, illegible), handwriting(Student, partly_legible), handwriting(Student, legible)'' can be true at the same time. In other words, our model has a flaw we need to fix! | ||
| + | |||
| + | There are to ways to take care of that: | ||
| + | |||
| + | - (not recommended) we add additional rules that say that only one value can be true. | ||
| + | - (recommended) use so called //annotated disjunctions//, which will be explained briefly. | ||
| + | |||
| + | If we have three facts that only one of them can be true at the time, we can write them as: | ||
| + | |||
| + | <code prolog> | ||
| + | fact1; fact2; fact3. | ||
| + | </code> | ||
| + | |||
| + | The same we can due with a rule: | ||
| + | <code prolog> | ||
| + | fact1; fact2; fact3 :- rule_body. | ||
| + | </code> | ||
| + | |||
| + | Which in our case translates to: | ||
| + | <code prolog> | ||
| + | 0.5::handwriting(Name, illegible); | ||
| + | 0.4::handwriting(Name, partly_legible); | ||
| + | 0.1::handwriting(Name, legible ):- student(Name). | ||
| + | </code> | ||
| + | |||
| + | Try to use that instead of the previous notation. Is there any difference? | ||
| + | |||
| + | ===== First Assignment ===== | ||
| + | |||
| + | Based on the first ProbLog model you've just finished, you have to model a classical problem of //burglary vs earthquake//. The story is rather simple: | ||
| + | |||
| + | //You live in the Los Angeles, beautiful city where earthquakes are not uncommon. You've installed a new alarm system in your house that was meant to protect you from burglaries. Unfortunately alarm is too sensitive and sometimes it get startled by an earthquake. Because of that you've set the alarm to not call the police. Instead of that your neighbors Joan and Maxwell are calling you as soon as they hear the alarm (if they are around). Unfortunately both Joan and Maxwell love pranks and sometimes call you only for fun.// | ||
| + | |||
| + | Question: what is the probability of burglary, if you are called by Joan only and you didn't receive call from Maxwell? How much probable is that it was only an earthquake? | ||
| + | |||
| + | ==== Priors ==== | ||
| + | |||
| + | In order to create the model, you will need some [[https://en.wikipedia.org/wiki/Prior_probability|prior probabilities]]. So: | ||
| + | |||
| + | * probability of a burglary in your neighborhood is rather high and equal ''0.7''. | ||
| + | * heavy earthquakes are very rare, probability of such a earthquake equals ''0.01''. | ||
| + | * mild earthquakes are not uncommon, probability of a mild earthquake equals ''0.19''. | ||
| + | * your alarm's sensitivity is specified by five probabilities: | ||
| + | * there is ''0.90'' probability that alarm start when there both burglary and heavy earthquake occur at the same time | ||
| + | * ''0.85'' when there both burglary and mild earthquake occur at the same time | ||
| + | * ''0.80'' during a burglary when there is no earthquake | ||
| + | * ''0.30'' during a heavy earthquake without any burglars | ||
| + | * ''0.10'' during a mild eathhquake without any burglars | ||
| + | * if there is an alarm going on, neighbor will call you with ''0.8'' probability | ||
| + | * there is small probability (''0.1'') that neighbor calls you only to prank you | ||
