Re: [RIF] backward vs forward chaining [was some other subject]

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [RIF] backward vs forward chaining [was some other subject]

Francois Bry

Peter F. Patel-Schneider wrote:

>From: Francois Bry <[hidden email]>
>Date: Thu, 02 Feb 2006 08:51:58 +0100
>
>  
>
>>Peter F. Patel-Schneider wrote:
>>
>>    
>>
>>>From: Michael Kifer <[hidden email]>
>>>Date: Wed, 01 Feb 2006 15:03:06 -0500
>>>
>>>      
>>>
>>>>Francois Bry <[hidden email]> wrote:
>>>>
>>>>        
>>>>
>>>>>I agree that RIF should have (1) a clear declarative semantics and (2)
>>>>>in addition support conveying *some* *limited* specifications of
>>>>>procedural semantics (eg backward chaining is intended because with
>>>>>forward chaining the considered rules would require to process all/too
>>>>>many nodes on the Web).
>>>>>
>>>>>          
>>>>>
>>>>I disagree with that, especially with the statement that "with forward
>>>>chaining the considered rules would require to process all/too many nodes
>>>>on the Web".
>>>>        
>>>>
>>>+[some very large number]
>>>
>>>What makes "forward chaining" a particularly bad method, even if you think of
>>>forward chaining as a way to perform saturation?  Forward chaining (including
>>>saturation, or not) works exceedingly well in some situations (and exceedingly
>>>poorly in others).  Standard backward chaining has exactly the same
>>>characteristics, by the way.  It all depends on the situation, and the
>>>parameters used to control the chaining.
>>>
>>>      
>>>
>>My point was that forward chaining inherently requires to start
>>computing from all web sites that might be involved. Either those web
>>sites are known and limited in number -- and this is fine -- or not --
>>and forward chaining is impracticable.
>>
>>--
>>Francois
>>    
>>
>
>I don't follow this.  Why would anyone want to start with "all web sites that
>might be involved"?  This seems to be a recipe for disaster no matter what
>reasoning methodology is used.
>
>In any case, what is it about "forward chaining" that requires this universal
>reach more than any other evaluation methodology?  Couldn't I just say the same
>thing about "backward chaining"?  What makes
>
> My point was that backward chaining inherently requires to start
> computing from all web sites that might be involved.
>
>any less true than what you said?
>
>Peter F. Patel-Schneider
>  
>
Think of rule specifying interesting web pages as follows, with

interesting(A) :- computer-science(A).
interesting(A) :- link(A, B), interesting(B).

meaning, a web page ist interesting if it has a Computer Science content
or a link to an "interesting" page.

Assume one asks whether www.example.ex is interesting. With backward
chaining, the evaluation starts with the query
"interesting(www.example.ex)" and propagate backwards the
binding,yielding the intermediate queries:

link(www.example.ex, B), interesting(B)
interesting(www.mycom.com) if A has a link to www.mycom.com
etc.

With forwards chaining, the evaluation starts with the queries
"computer-science(A)"  ie checking all web pages for Computer Science
content, then following the links from all web page with CS contents, etc.

Thus, backward or forward chaining make a difference, as far as the
number of pages accessed is concerned.

Francois


Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [RIF] backward vs forward chaining [was some other subject]

doug foxvog

Francois Bry wrote:
> Peter F. Patel-Schneider wrote:
>> From: Francois Bry <[hidden email]>
>> Date: Thu, 02 Feb 2006 08:51:58 +0100
>>> Peter F. Patel-Schneider wrote:
>>>> From: Michael Kifer <[hidden email]>
>>>> Date: Wed, 01 Feb 2006 15:03:06 -0500
>>>>> Francois Bry <[hidden email]> wrote:

>>>>>> I agree that RIF should have (1) a clear declarative semantics and
>>>>>> (2) in addition support conveying *some* *limited* specifications
>>>>>> of procedural semantics (eg backward chaining is intended because
>>>>>> with forward chaining the considered rules would require to
>>>>>> process all/too many nodes on the Web).

Do you mean the procedural semantics should be defined for each rule, or
that one procedural semantics (backward chaining) should be defined for
all rules?

>>>>> I disagree with that, especially with the statement that "with forward
>>>>> chaining the considered rules would require to process all/too many
>>>>> nodes
>>>>> on the Web".

>>>> +[some very large number]

Aren't we considering contexts here?  Parts of the web that are not in
the context in which the question is asked are not applicable for the
answer.  A context would include that of the included knowledge bases
and that of all (recursively) referenced ontologies as well as specified
other areas of the web.  Someone's knowledge base using my ontology
doesn't necessatate my access to that knowledge base.

What forward chaining would mean is that forward rules fire when they
are asserted or when an outside ontology or knowledge base accesses an
ontology with a forward rule.  The conclusions are then available
whenever a question is asked.  Backward chaining requires the execution
of backward rules when the question is asked.

>>>> What makes "forward chaining" a particularly bad method, even if you
>>>> think of
>>>> forward chaining as a way to perform saturation?  Forward chaining
>>>> (including
>>>> saturation, or not) works exceedingly well in some situations (and
>>>> exceedingly
>>>> poorly in others).  Standard backward chaining has exactly the same
>>>> characteristics, by the way.  It all depends on the situation, and the
>>>> parameters used to control the chaining.

Agreed.

>>> My point was that forward chaining inherently requires to start
>>> computing from all web sites that might be involved.   Either those web
>>> sites are known and limited in number -- and this is fine -- or not
>>> -- and forward chaining is impracticable.

True, but backward chaining also impracticable if the number of sites to
chain over are not known or unlimited in number for queries that are not
answered completely within a more limited context.

>>> --
>>> Francois

>> I don't follow this.  Why would anyone want to start with "all web
>> sites that
>> might be involved"?  This seems to be a recipe for disaster no matter
>> what
>> reasoning methodology is used.

>> In any case, what is it about "forward chaining" that requires this
>> universal
>> reach more than any other evaluation methodology?  Couldn't I just say
>> the same
>> thing about "backward chaining"?  What makes

>>     My point was that backward chaining inherently requires to start
>>     computing from all web sites that might be involved.

>> any less true than what you said?

>> Peter F. Patel-Schneider

> Think of rule specifying interesting web pages as follows, with

> interesting(A) :- computer-science(A).
> interesting(A) :- link(A, B), interesting(B).

> meaning, a web page ist interesting if it has a Computer Science content
> or a link to an "interesting" page.

> Assume one asks whether www.example.ex is interesting. With backward
> chaining, the evaluation starts with the query
> "interesting(www.example.ex)" and propagate backwards the
> binding,yielding the intermediate queries:

> link(www.example.ex, B), interesting(B)
> interesting(www.mycom.com) if A has a link to www.mycom.com
> etc.

Here, the system needs to know that "link" is an evaluatable predicate
for its second argument and to bind B before asking "interesting(B)".
If the system searched the web to prove "link(www.example.ex, B)" or
searched for "interesting(B)" before proving "link(www.example.ex, B)"
you wouldn't have the efficiency noted.

> With forwards chaining, the evaluation starts with the queries
> "computer-science(A)"  ie checking all web pages for Computer Science
> content, then following the links from all web page with CS contents, etc.

Actually, this happens long before the query.  If the rules are forward,
then when the query is made the answer is just extracted from an already
generated set (effectively table) of interesting pages.

And "all web pages" are not necessarily checked at assert time.  The
extent of the "computer-science" class/unary predicate is checked.  If
a forward rule exists for "computer-science(C)" that searches the whole
web and performs natural language proccesing on each page, then that
rule being forward with that method is a problem, not the forward rule
that you gave.

Note that if the definition of interesting was that anything that linked
to a "computer-science" page was interesting, then backward chaining
would not be efficient, because "link(A, www.example.ex)" cannot be
efficiently determined in a backward fashion.

   interesting(A) :- computer-science(A).
   interesting(A) :- link(B, A), interesting(B).

> Thus, backward or forward chaining make a difference, as far as the
> number of pages accessed is concerned.

It does make a difference.  And which requires more page accesses
depends upon the rule.

> Francois

==========================================================
douglas foxvog  [hidden email] +353 (91) 495 150
Digital Enterprise Research Institute (DERI)
National University of Ireland, Galway
Galway, Ireland http://www.deri.ie
==========================================================

Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [RIF] backward vs forward chaining [was some other subject]

Adrian Walker
In reply to this post by Francois Bry

Bonjour Francois and All --

Good to see that the backward and forward debate continues... (:-)

It's been known for quite a while that one can get the best of both worlds,
_and_ a more declarative treatment of the rules, by combining both methods
automatically in one engine.

Backchaining then keeps the focus on results (and in future, on web data
items) that are actually needed, while forward chaining with asserted
lemmas stops the engine from deriving the same sub-result more than once.

XSB takes a step in this direction, with 'tabling'.  Magic Sets, and
Backchain Iteration [1],  exploit the approach more fully**.

                       Cheers,   -- Adrian


[1] Backchain Iteration: Towards a Practical Inference Method that is
Simple Enough to be Proved Terminating, Sound and Complete. Journal of
Automated Reasoning, 11:1-22.

** I'm guessing that Euler does this too. Right Jos ?



Internet Business Logic (R)
Executable open vocabulary English
Online at www.reengineeringllc.com
Shared use is free

Adrian Walker
Reengineering
PO Box 1412
Bristol
CT 06011-1412 USA

Phone: USA 860 583 9677
Cell:    USA  860 830 2085
Fax:    USA  860 314 1029



At 03:02 PM 2/2/2006 +0100, you wrote:

>Peter F. Patel-Schneider wrote:
>
>>From: Francois Bry <[hidden email]>
>>Date: Thu, 02 Feb 2006 08:51:58 +0100
>>
>>
>>
>>>Peter F. Patel-Schneider wrote:
>>>
>>>
>>>
>>>>From: Michael Kifer <[hidden email]>
>>>>Date: Wed, 01 Feb 2006 15:03:06 -0500
>>>>
>>>>
>>>>
>>>>>Francois Bry <[hidden email]> wrote:
>>>>>
>>>>>
>>>>>
>>>>>>I agree that RIF should have (1) a clear declarative semantics and
>>>>>>(2) in addition support conveying *some* *limited* specifications of
>>>>>>procedural semantics (eg backward chaining is intended because with
>>>>>>forward chaining the considered rules would require to process
>>>>>>all/too many nodes on the Web).
>>>>>>
>>>>>>
>>>>>I disagree with that, especially with the statement that "with forward
>>>>>chaining the considered rules would require to process all/too many nodes
>>>>>on the Web".
>>>>>
>>>>+[some very large number]
>>>>
>>>>What makes "forward chaining" a particularly bad method, even if you
>>>>think of
>>>>forward chaining as a way to perform saturation?  Forward chaining
>>>>(including
>>>>saturation, or not) works exceedingly well in some situations (and
>>>>exceedingly
>>>>poorly in others).  Standard backward chaining has exactly the same
>>>>characteristics, by the way.  It all depends on the situation, and the
>>>>parameters used to control the chaining.
>>>>
>>>>
>>>My point was that forward chaining inherently requires to start
>>>computing from all web sites that might be involved. Either those web
>>>sites are known and limited in number -- and this is fine -- or not --
>>>and forward chaining is impracticable.
>>>
>>>-- Francois
>>>
>>
>>I don't follow this.  Why would anyone want to start with "all web sites that
>>might be involved"?  This seems to be a recipe for disaster no matter what
>>reasoning methodology is used.
>>
>>In any case, what is it about "forward chaining" that requires this universal
>>reach more than any other evaluation methodology?  Couldn't I just say
>>the same
>>thing about "backward chaining"?  What makes
>>
>>         My point was that backward chaining inherently requires to start
>>         computing from all web sites that might be involved.
>>
>>any less true than what you said?
>>
>>Peter F. Patel-Schneider
>>
>Think of rule specifying interesting web pages as follows, with
>
>interesting(A) :- computer-science(A).
>interesting(A) :- link(A, B), interesting(B).
>
>meaning, a web page ist interesting if it has a Computer Science content
>or a link to an "interesting" page.
>
>Assume one asks whether www.example.ex is interesting. With backward
>chaining, the evaluation starts with the query
>"interesting(www.example.ex)" and propagate backwards the binding,yielding
>the intermediate queries:
>
>link(www.example.ex, B), interesting(B)
>interesting(www.mycom.com) if A has a link to www.mycom.com
>etc.
>
>With forwards chaining, the evaluation starts with the queries
>"computer-science(A)"  ie checking all web pages for Computer Science
>content, then following the links from all web page with CS contents, etc.
>
>Thus, backward or forward chaining make a difference, as far as the number
>of pages accessed is concerned.
>
>Francois
>
>



Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [RIF] backward vs forward chaining [was some other subject]

jos.deroo
In reply to this post by Francois Bry

[...]

> XSB takes a step in this direction, with 'tabling'.  Magic Sets, and
> Backchain Iteration [1],  exploit the approach more fully**.
>
>                       Cheers,   -- Adrian
>
>
> [1] Backchain Iteration: Towards a Practical Inference Method that is
> Simple Enough to be Proved Terminating, Sound and Complete. Journal of
> Automated Reasoning, 11:1-22.
>
> ** I'm guessing that Euler does this too. Right Jos ?

I'm still learning that we should do it less fully :)
but more like connected least powered engines...
euler is more like a simple webized prolog engine [1]
and the python version is even simpler, but evolving.

--
Jos De Roo, AGFA http://www.agfa.com/w3c/jdroo/

[1] http://eulersharp.sourceforge.net/2003/03swap/FAQ

Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [RIF] backward vs forward chaining [was some other subject]

Francois Bry
In reply to this post by doug foxvog

doug foxvog wrote:

>Do you mean the procedural semantics should be defined for each rule,
>
surely not. I would not make much sense.

>or
>that one procedural semantics (backward chaining) should be defined for
>all rules?
>  
>
for rulesets.

>Aren't we considering contexts here?  Parts of the web that are not in
>the context in which the question is asked are not applicable for the
>answer.  
>
Considering contexts is good if one can. Very often on the web, contexts
are not konwn before hand. This is one of (the?) essential difference
between the web and hypertext systems considered before the web.

>A context would include that of the included knowledge bases
>and that of all (recursively) referenced ontologies as well as specified
>other areas of the web.  
>
With recursive references, one can soon get a huge number of web sites
-- eg too large for a given evaluation strategy.

>Someone's knowledge base using my ontology
>doesn't necessatate my access to that knowledge base.
>  
>
It depends on how "access" and "using" are defined.

>What forward chaining would mean is that forward rules fire when they
>are asserted or when an outside ontology or knowledge base accesses an
>ontology with a forward rule.  The conclusions are then available
>whenever a question is asked.  
>
This is forward chaining with memoing, ie a common approach. It is often
impracticable for size reasons or if the data are frequently updated.
Those cases where it is not practicable are the interesting ones from a
research viewepoint, I beleive.

>Backward chaining requires the execution
>of backward rules when the question is asked.
>  
>
Pre-evaluated questions with saved answers can be considered. But, you
are right, the standard approach to backward chsaining it at query time.
In a distributed and chanuigng world, furthermore without agreements on
when something is changed, this is one of the appealing features of
backward chaining.

>>>>My point was that forward chaining inherently requires to start
>>>>computing from all web sites that might be involved.   Either those web
>>>>sites are known and limited in number -- and this is fine -- or not
>>>>-- and forward chaining is impracticable.
>>>>        
>>>>
>
>True, but backward chaining also impracticable if the number of sites to
>chain over are not known or unlimited in number for queries that are not
>answered completely within a more limited context.
>  
>
Right. In addition, on the web there are rules that are inherently
inappropriate for backward chaining, cf (1)  (like some other rules are
inherently inappropriate for forward chaining, cf (2)). If I understand
well, this is what you (Douglas) mentioned.

(1) interesting(A) :- link-from-to(B, A), interesting(B)
(2) interesting(A) :- link-from-to(A, B), interesting(B)

Remark: in both examples html-like links, not XLink-like generalized
links, are considered.
--
Francois

Loading...