Grandfather example

From Dyna
Jump to: navigation, search

Grandfather example

Dyna can do a lot of things that Prolog can do -- and more! So, let's proceed with a typical Prolog toy example. It will show you more about Dyna and some of its differences to Prolog.

To describe a grandfather - grandchild relationship in Prolog, you would probably write something like this:

% Prolog code
grandfather(F, G) :- father(F, C), father(C, G).
grandfather(F, G) :- father(F, C), mother(C, G).

Then, you could assert in Prolog that Kaspar's father is Karl, and Karl's father is Wilhelm. Asked who Kaspar's grandfather is, Prolog would output: Wilhelm.

Now, let's do the same in Dyna. Here's the Dyna code (call it kaspar.dyna):

% Dyna code
:- item(item,double,0).                             % double-precision real number variables
grandfather(F, G) += father(F, C) * father(C, G).  
grandfather(F, G) += father(F, C) * mother(C, G).  
goal += grandfather(F, G).                         % the goal is to find a grandfather

And in the C++ driver code, you can assert the relationships between them:

 // C++ driver program
 #include <iostream>
 #include "kaspar.h"        
 using namespace kaspar;

 int main(int argc, char** argv) {
    chart c;
    c.assert( father("Karl", "Kaspar")  , 1.0);
    c.assert( father("Wilhelm", "Karl") , 1.0);    
    cout << "Kaspar's grandfather: " << c[goal] << endl;
 }

Jason: In this syntax, how do I actually get the answer string "Wilhelm"?

Assert uncertain knowledge

But there is an additional thing in Dyna that Prolog cannot do: Dyna can still give you an answer if you don't know exactly who is whose father!

Maybe we don't know exactly who Kaspar's father is. It could be Karl, but there is a certain probability that it's someone else, say, Ludwig. Kaspar Hauser didn't even know himself who his parents were. And then, suppose you have again only partial knowledge about their fathers. Who is Kaspar's grandfather now? Dyna can tell you who the most likely grandfather is if you can assert some probabilities.

Don't change anything in kaspar.dyna. In the C++ driver code, you can now state the partial knowledge that you have about the father relationships:

// C++ driver program
 #include <iostream>
 #include "kaspar.h"        
 using namespace kaspar;
 
 int main(int argc, char** argv) {
    chart c;
    c.assert(father("Karl", "Kaspar"), 0.7);   // Most likely Karl is the father
    c.assert(father("Ludwig", "Kaspar"), 0.3); // ... but it could maybe be Ludwig

    c.assert(father("Wilhelm", "Karl"), 0.6);  // Karl's father is Wilhelm
    c.assert(father("Georg", "Karl"), 0.4);    // ... or was it Georg?

    c.assert(father("Hans", "Ludwig"), 1);     // Say, we know that Hans is Ludwig's father.
    
    cout << "Kaspar's most likely grandfather: " << c[goal] << endl;
 }

In the driver code, we stated that we are not sure about Kaspar's father: It could be Karl (p=0.7) or Ludwig (p=0.3). Karl's father again could be Wilhelm (p=0.6) or Georg (p=0.4). We are not sure. We just know for sure that Hans is Ludwig's father. Then, we ask Dyna who, most likely, Kaspar's grandfather is. The answer is Wilhelm, with probability 0.6 * 0.7 = 0.42.

In this example, we used Dyna for a typical Prolog problem. Dyna enabled us to take a prolog-related problem formulation and turn it into a probabilistic model. If this makes you already think of probabilistic parsing, see here.

If you wonder why we wrote

 grandfather(F, G) += father(F, C) * father(C, G).  

with the plusequals (+=) and the star (*) operators, read GrandfatherNotation.

Personal tools
Namespaces

Variants
Actions
Navigation
Tools