Prolog backtracking VS Rete backtracking

Question

In my class I have been taught the Prolog backtracking algorithm and the Rete forprop algorithm, but I have also been told that Rete can be used to do backprop.

How does that work? In which ways is it similar / different to Prolog backtracking?

---

For example, this is one of the exercises I have been given:

(R1) 24fingers and antennas => origin(mars)
(R2) shy and 5feet => origin(mars)
(R3) shy and 4arms => origin(venus)
(R4) looksDownWhenTalking => shy
(R5) fleesWhenSeen => shy

The goal is given the following facts find the origin of the alien:

(F1) fleesWhenSeen
(F2) 4arms

In Prolog, we would solve it by pattern matching the goal origin(X) against the RHS of the rules. The rule matches against R1, R2 and R3, so first R1 will be triggered, and we would try to resolve the subgoals 24fingers and antennas which would fail.

Then we would go backtrack to the beginning and trigger R2, which eventually will fail, and finally backtrack and trigger R3, which succeeds.

So X ends up binded to venus in a successful query, and the algorithm ends.

---

Now, how would we solve the same exercise using the rete backprop algorithm?

I naively assume that we would use a list of subgoals, starting with origin(X), to start triggering rules whose RHS matches the subgoals.

But it isn't clear to me how the Rete algorithm would take care of backtracking when some subgoals fail, or how would it know that it has succeed once it resolves a certain subset of goals.

Sophrosyne

The rete algorithm is strictly forward-chaining. Maybe some engines primarily based on rete, do also support backward-chaining, yet the used algorithm cannot be the rete algorithm. Can you add some links to resources that claim to use rete and backward chaining? – Mairamaire

@Mairamaire this was in my college exercises, when I asked my teacher how to the exercises she went on to resolve them using Prolog-like backtracking, which only confused me further. If you are confident backtracking with rete is not a thing that is an answer I am satisfied with. – Sophrosyne

Prolog is highly specialized in DEDUCTIVE reasoning. It has a knowledge base from which it can infer whether something is true, or it can do a depth first search to find all possible solutions for a question with a variable. I imagine other languages are better at INDUCTIVE reasoning, which deals with calculating the probabilities of something occurring, which is not what Prolog was primarily designed for. It tries to give you answers based on known facts, through back chaining, while other languages would be better at forward chaining to give you a probability tree. Deduction vs Prediction. – Yowl

@Jsevillamol: I think that most RETE-based systems support queries that are backward chaining, but these queries are not processed with the RETE-Algorithm, but others (SLD-Resolution as in Prolog, Semi-Naive-Bottom-Up-Evaluation or Magic-Sets-Evaluation like in Deductive Databases) – Mairamaire

@G_V: The RETE-Algorithm and SLD-Resolution both are deductive algorithms. Backward-Chaining and Forward-Chaining are both deductive. Inductive reasoning is a subject beyond Rete and Prolog. All facts derived with inductive reasoning may be wrong (which is not the case for deductive reasoning). – Mairamaire

@Mairamaire - I think the forward chaining wiki says it well. You give facts and then based on those facts the program starts giving you all the possible outcomes. Yes, frogs eat flies and croak, but not all frogs are green. Forward chaining allows you to use data to guess the most likely color of a frog based on its known attributes. Backward chaining would be asking whether a frog can be green. It's mainly used to check whether something is true or false. Deductive reasoning deals in certainties. – Yowl

@G_V: Forward chaining allows you to derive facts from other facts. Inductive reasoning allows you to guess facts. Thats completely different. A rule frog => green means that all frogs are green. In this world there are no brown frogs. Inductive reasoning on this rule would propose that a given object that is green may (!) be a frog. Yet in this world there may be also other objects that are green and a green object that is not a frog is perfectly consistent with a world based on this rule. – Mairamaire

@Mairamaire - Yes, forward chaining allows you to guess the likelihood of what kind of frog you're dealing with based on its diet, color, geographical location etc. It gives you options for your known facts, which you can weigh based on actual results to give you a high probability of the program guessing correctly based on historical data. Someone searches for a search term on youtube. Other users who searched this term watched several videos, clicked away and watched 1 entirely. The longer watch-time means it's more likely to be relevant to this search, so it ranks higher in the results. – Yowl

Answer 1

There is no standard implementation for supporting backward chaining in a forward chaining system. Hybrid tools have implemented this functionality using different techniques. One technique, data-driven backward chaining, is described here: http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/. Some additional information: JESS vs DROOLS : Backward chaining and http://herzberg.ca.sandia.gov/docs/70/rules.html.

Claytonclaytonia

Answer 2

Explanation of the Rete algorithm is provided here: http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218 .

In Prolog the unificaton algorithm is used that unlike of pattern-matching has patterns on both sides (goal / rule head).

Edit

here is a lots of info about Rete and Prolog.

Building Expert Systems in Prolog

http://www.amzi.com/distribution/files/xsip_book.pdf

http://www.oopweb.com/Prolog/Documents/XSIP/Volume/08performance.htm

THE THEORETICAL FRAMEWORK AND IMPLEMENTATION OF A PROLOG INTERPRETER

http://staff.um.edu.mt/mcam1/Files/Dissertation.pdf

Alto

Good resources, but this does not answer my question – Sophrosyne