On Thu, August 12, 2010 2:37, John F. Sowa said:
> On 8/11/2010 6:16 PM, Pat Hayes wrote:
>> Or (just to keep the record clear) another option is to simply abandon
>> this quest to achieve decidability, and work with semi-decidable
>> complete logics such as classical FOL. (01)
> Yes, and some groups, including Cyc and VivoMind, go a bit farther: (02)
> 1. Note that the complexity class (including P, NP, or undecidable) is
> *not* a property of a logic, but of problems stated in the logic. (03)
> 2. If you use a very expressive logic, you are not required to use
> all possible features of that logic in every problem. (04)
> 3. Instead, you can use a variety of inference engines optimized
> for different subsets. (In the case of Cyc, they have about
> three dozen different inference engines optimized for various
> subsets of CycL.) (05)
Cyc has a dozens of "rule macro predicates", which are predicates
which provide a compact way of stating a rule. When commonly used rule
patterns were discovered, RMPs were created for them and efficient code
was written for executing the rule. The timing for reasoning using such
modules is known or calculable. Such modules are not considered
separate inference engines, but are called by the inference engine if
a statement using the RMP (i.e., an encoded rule) is to be used in
reasoning. [At least that was the situation up until 2003.] (06)
A non-Cyc system could reason using the RMP, by expanding the macro &
using the resultant rule (which would be slower than using the optimized
code). (07)
The basic inference engine is always used, the special reasoning routines
are preferentially used if and when applicable. The Cyc reasoner also
allows the user to limit the use of certain types of rules & to specify
maximum reasoning depth, time, number of answers, and a number of other
inference parameters. (08)
> 4. For all the common cases and many rare cases, it is possible
> to perform a quick syntactic check to determine the complexity
> class of the given problem. Then assign the problem to an
> appropriate inference engine (or sometimes different engines
> for different aspects of a complex problem).
>
> 5. For most cases, it is possible to give the user a guarantee
> of performance on a particular problem (if it is an easy one)
> or a warning (if it is a hard one). For those rare cases,
> where the complexity class cannot be determined, it is also
> possible to say that as part of the warning.
>
>> As Ian points out in another message in this thread, this means that
>> one cannot then undertake to offer users a universal *guarantee* of
>> performance
>
> True, but Cyc could also provide a guarantee for most if not all
> the cases for which an OWL reasoner can provide a guarantee. But
> Cyc can also offer to do its best effort on those problems for
> which a guarantee is not possible. (09)
... and which an OWL reasoner may not be able to solve. (010)
> As that article on the issue of P=NP points out, many problems,
> such as graph isomorphism (GI), that may take exponential time
> have a huge number of efficient special cases. For example,
> the *only* cases for which GI takes exponential time are ones
> where the upper bound on the branching factor of the graph is
> O(n) -- i.e., the number of links to any node is proportional
> to the total number n of nodes in the graph.
>
> For conceptual graphs and even RDF graphs, the branching factor
> is almost never O(n). It's usually bounded by a constant or
> at worst by a polynomial in (log n).
>
>> In our case, it would mean that all this plethora of multiple
>> standards and notations (RDFS, OWL, OWL2, RIF, RuleML, WhatNextML...)
>> could be simply described as being what they in fact are, which is
>> various subsets of classical FO logic, or of ISO Common Logic. One
>> parser could handle all of them, all expressed in a single notation,
>> and the work of re-designing a syntax and a new semantics, and writing
>> a bundle of close-to-unreadable specification documents would not have
>> to be re-done every few years. (011)
> Certainly. That's what Cyc does. They have been able to handle a
> huge range of options by implementing different inference engines. (012)
Or inference modules. (013)
> But the users and SMEs don't have to worry about (or even know about)
> the complexity classes or the inference engines. For most cases,
> even the knowledge engineers don't have to worry, except in the
> unusual cases where they have to add another inference engine or
> revise the tests for choosing which inference engine to use. (014)
The tests for which inference modules to use would be made by the coders,
not the knowledge engineers. The knowledge engineers may detect a
commonly used rule pattern and design a rule macro predicate to encode it,
after which the coders are asked to design an efficient module for
inference using the encoded rule. (015)
-- doug f (016)
> For many problems, it's also possible to write a static analyzer
> and compiler that extracts axioms from Cyc and translates them
> to an optimized form for inference engines outside of Cyc.
> See, for example, the approach that Bill Andersen and his
> buddies implemented. I discuss that on p. 6 of the following:
>
> http://www.jfsowa.com/pubs/fflogic.pdf
> Fads and fallacies about logic
>
> John (017)
=============================================================
doug foxvog doug@xxxxxxxxxx http://ProgressiveAustin.org (018)
"I speak as an American to the leaders of my own nation. The great
initiative in this war is ours. The initiative to stop it must be ours."
- Dr. Martin Luther King Jr.
============================================================= (019)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (020)
|