Re: [RIF] backward vs forward chaining [was some other subject]
|
View:
New views
5 Messages
—
Rating Filter:
Alert me
|
 |
|
|
|
Re: [RIF] backward vs forward chaining [was some other subject]
by doug foxvog
::
Rate this Message:
Francois Bry wrote: > Peter F. Patel-Schneider wrote: >> From: Francois Bry <bry@...> >> Date: Thu, 02 Feb 2006 08:51:58 +0100 >>> Peter F. Patel-Schneider wrote: >>>> From: Michael Kifer <kifer@...> >>>> Date: Wed, 01 Feb 2006 15:03:06 -0500 >>>>> Francois Bry <bry@...> 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 doug.foxvog@... +353 (91) 495 150 Digital Enterprise Research Institute (DERI) National University of Ireland, Galway Galway, Ireland http://www.deri.ie ========================================================== |
|
|
Re: [RIF] backward vs forward chaining [was some other subject]
by Adrian Walker
::
Rate this Message:
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 <bry@...> >>Date: Thu, 02 Feb 2006 08:51:58 +0100 >> >> >> >>>Peter F. Patel-Schneider wrote: >>> >>> >>> >>>>From: Michael Kifer <kifer@...> >>>>Date: Wed, 01 Feb 2006 15:03:06 -0500 >>>> >>>> >>>> >>>>>Francois Bry <bry@...> 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 > > |
|
|
|
|
|
Re: [RIF] backward vs forward chaining [was some other subject]
by Francois Bry
::
Rate this Message:
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. > > 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 |
| Free embeddable forum powered by Nabble | Forum Help |
