This is sent to both c.l.l and comp.ai because I'm hoping the c.l.l
crowd may have some familiarity the Winston-Horn book, and the AI
folks may have some higher level rule-bases shell thoughts.
I was looking at the simple(?) forward chaining system that is
discussed in the LISP, 3rd edition book. I've also read the chapter in
Norvigs Paradigms of AI book. I HAVEN'T looked at the backward
chaining chapters of the W-H book, so perhaps this is all premature.
I am wondering how rule based systems, in general, deal with ambiguity
and precedance of rules.
Let me give an example, in this case trying to determine the pricing
for an item.
And some simple rules:
Item 123: Granite Book End
Item 456: Pencil Sharpener
;; Each item has its own price
if the item number is 123 then price = $10.00
if the item number is 456 then price = $15.00
;; Certain orders affect every item on the order
if the order is a NO CHARGE order then price = $0.00
;; Certain customers get a fixed rate
if BOB is ordering and ITEM TYPE is BOOKENDS then price = $5.00
So, as you can see (I hope) if BOB order both items, 123 and 456, they
will be priced at $5 and $15 respectively.
However, if BOB is getting a NO CHARGE order, then they are all $0.00.
That's common sense (but for some reason (common-sense) is not bound in
my Lisp system, and I can't find it in the Hyper Spec.)
But you can also see that save for some precedance arrangement, BOB
getting a NO CHARGE order for item 123 has 3 possible values.
The W-H simple forward chaining pattern matching system would
probably find the first rule that matches, bind PRICE to whatever, and
then fail the rest of the rules because while the criteria matches,
the price won't, and the W-H system wants to match everything.
Also, something like the NO CHARGE is so "powerful" that the system
should "know" that there isn't any reason to search any farther. A
rule that has the power of a heuristic, almost.
I suppose that most of this is centered on the search alogrithm
itself. I reckon it's just a matter of mashing up the system to find
all possible solutions, and have each goal node given a precedance,
and have the system return the node with the highest precedance.
I suppose the trick there is saving each solution as its found, but
not binding the answer (in the W-H case) so that the system can
continue to accumulate answers. That shouldn't be too hard, I reckon.
I can decide later if it's a fault to get to answers of the same
precedance.
And, just to ask, does a backward chaining system solve this kind of
issue in a better way?
I look at something like the W-H code and find is deceptively simple.
I look at it and say "That's almost what I need, except for...". But
perhaps I'm being naive. At this point in the process, I'm kind of
going through the "tool chest" and seeing what I have that might fit
the bolt I'm trying to turn, but I don't necessarily understand the
tool itself. I've not much experience in rule based systems.
It doesn't SEEM that difficult, and my problem domain isn't THAT
large. However, the above example is pretty common.
I'm not looking for a package to solve the problem. I think it's
a problem in algorithm design and in rule design, but I'm not
experienced enough in either to say which, and figure that they affect
each other equally.
Of course, the "rule based" concept may be limiting my approach as
well, but so far it seems like the best path to solve the arbitrary
and complex (more arbitrary than complex I think, but complex in their
arbitrariness) pricing structures we need to automate on our system.
Gotta love the guys in marketing...
Perhaps I need to pick up Norvigs OTHER AI book.
Thanx for any pointers.
--
Will Hartung - Rancho Santa Margarita. It's a dry heat. ······@netcom.com
1990 VFR750 - VFR=Very Red "Ho, HaHa, Dodge, Parry, Spin, HA! THRUST!"
1993 Explorer - Cage? Hell, it's a prison. -D. Duck
On Tue, 7 Jul 1998 17:35:59 GMT, Will Hartung <······@netcom.com> wrote:
> I am wondering how rule based systems, in general, deal with ambiguity
> and precedance of rules.
In general, they don't do anything with them. The standard rule-based
system just implement automated deduction, i.e. mathematical logic. The
semantics (meaning) of logic is VERY well understood, and can be found in
any introductory logic text.
For precedence, people generally use the order of the rules, and then ask
the system for the first answer that it can find. This is called "logic
programming". In the semantics, though, ALL the answers are correct.
If you want something more complex, like rules with weights and then finding
the "best" answer, this usually has to be built on top of a rules engine.
You might want to check out probability, bayes nets, or fuzzy logic.
> if the item number is 123 then price = $10.00
> if the item number is 456 then price = $15.00
> if the order is a NO CHARGE order then price = $0.00
> if BOB is ordering and ITEM TYPE is BOOKENDS then price = $5.00
In the most natural expression of these rules with most simple rules
systems, if Bob ordered Bookend 123 at no charge then the price would be all
of $10, $0, and $5. Or, if you made price a function (with only one value),
then you've written inconsistent rules so you don't really have a right to
complain about any answer the system might give you.
> The W-H simple forward chaining pattern matching system would
> probably find the first rule that matches, bind PRICE to whatever, and
> then fail the rest of the rules because while the criteria matches,
> the price won't, and the W-H system wants to match everything.
Probably not, actually. It'll probably return each of the prices, saying
that each one has a valid proof and without a preference mechanism it can't
tell the difference.
> It doesn't SEEM that difficult, and my problem domain isn't THAT
> large. However, the above example is pretty common.
Logics with preference and ambiguity can quickly become very complex.
These kinds of algorithms are much harder to write and understand than
ordinary logic theorem provers.
Good luck,
-- Don
--
Don Geddis ······@tesserae.com
Tesserae Information Systems, Inc. http://tesserae.com
275 Shoreline Drive, Suite 505 (650) 508-7893
Redwood Shores, CA 94065 (650) 508-7891 [fax]
Actually, the choice of forward- or backward-chaining depends upon what you
want your application to do. For instance, if you are setting up a knowledge
base, iterative forward-chaining does a good job of producing gobs o' rules
(which is typically what you want). Then, if you want to make deductions,
backward-chaining is ideal -- very easy to follow its logic backward, and
you get quick solution(s). Definitely read Winston & Horn; or at least skim.
The above is obviously -my- interpretation, let the reader beware.
Will Hartung <······@netcom.com> wrote in message
················@netcom.com...
>This is sent to both c.l.l and comp.ai because I'm hoping the c.l.l
>crowd may have some familiarity the Winston-Horn book, and the AI
>folks may have some higher level rule-bases shell thoughts....
In article <················@netcom.com> ······@netcom.com
(Will Hartung) writes:
>
>I am wondering how rule based systems, in general, deal with ambiguity
>and precedance of rules.
>
>Let me give an example, in this case trying to determine the pricing
>for an item.
>
. . .
>
>Of course, the "rule based" concept may be limiting my approach as
>well, but so far it seems like the best path to solve the arbitrary
>and complex (more arbitrary than complex I think, but complex in their
>arbitrariness) pricing structures we need to automate on our system.
>
. . .
Will:
The field of AI and Law is concerned with the creation and application
of AI techniques to support reasoning and decision making in
"regulation-based" domains such as the law. A closely related field is that
of deontic logic, which models reasoning about what agents are required to
do, permitted to do, and forbidden to do.
The field of AI and Law, while aimed primarily at solving legal
problems, is relevant to any domain where there is a set of rules
or policies that the reasoner is obligated to follow. Typical non-legal
application domains include administration of companies' employee benefit
programs, university degree requirements, and libraries' rules for accessing
and borrowing materials.
Areas of recent interest include the access rules that implement computer
security and privacy policies, and regulations that govern E-commerce
and other networking applications. It seems to me that your example of
rules for giving discounts to customers fits this paradigm.
There is a natural confusion regarding the use of the term "rule-based" here
because in AI a "rule-based(1)" system usually means that the BEHAVIOR of
the intelligent system is expressed as a set of logical or condition/action
rules. While in regulated domains (such as law), there is a rule base(2)
"out there" in the world that must be dealt with by the intelligent
system (whether or not the system is internally rule-based(1)).
Systems of regulations, being written by humans for human use, are
usually full of ambiguities, internal contradictions, "open-textured"
concepts (such as a "reasonable expectation" or "substantial harm")
and cases that are not covered by the existing regulations. So, one
cannot just encode this rule base(2) in a computer and expect it to
function as a rule-base(1)"
You will find lots of interesting ideas and theories in the AI and Law
literature that expand on and hopefully clarify the issues in creating
a regulatory expert system.
To learn more about AI and Law, the WWW site of IAAIL (the International
Association for Artificial Intelligence and Law) is:
http://nathan.gmd.de/iaail/iaail.html
where you will find Tables of Contents for recent AI and Law conferences
and the AI and Law journal.
Good luck,
Carole Hafner
***************-------------**************-------------***************
* Prof. Carole D. Hafner ······@ccs.neu.edu *
* College of Computer Science Phone: (617) 373-5116 *
* Northeastern University FAX: (617) 373-5121 *
* Boston, MA 02115 USA http://www.ccs.neu.edu/home/hafner/ *
***************-------------**************-------------***************
In article <················@netcom.com> ······@netcom.com
(Will Hartung) writes:
> >
> >I am wondering how rule based systems, in general, deal with ambiguity
> >and precedance of rules.
> >
> >Let me give an example, in this case trying to determine the pricing
> >for an item.
> >
> . . .
> >
> >Of course, the "rule based" concept may be limiting my approach as
> >well, but so far it seems like the best path to solve the arbitrary
> >and complex (more arbitrary than complex I think, but complex in their
> >arbitrariness) pricing structures we need to automate on our system.
> >
> . . .
>
Fuzzy logic might be something for you to investigate. This is a technology
specifically designed to deal with non-crisp rule situations. A web site that
has material on this topic is:
http://www.geocities.com/siliconvalley/lakes/6007/Fuzzy.htm
Best,
Peter.
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
···········@my-dejanews.com wrote:
>
> In article <················@netcom.com> ······@netcom.com
> (Will Hartung) writes:
> > >
> > >I am wondering how rule based systems, in general, deal with ambiguity
> > >and precedance of rules.
> > >
> > >Let me give an example, in this case trying to determine the pricing
> > >for an item.
> > >
> > . . .
> > >
> > >Of course, the "rule based" concept may be limiting my approach as
> > >well, but so far it seems like the best path to solve the arbitrary
> > >and complex (more arbitrary than complex I think, but complex in their
> > >arbitrariness) pricing structures we need to automate on our system.
> > >
> > . . .
> >
>
> Fuzzy logic might be something for you to investigate. This is a technology
> specifically designed to deal with non-crisp rule situations. A web site that
> has material on this topic is:
>
> http://www.geocities.com/siliconvalley/lakes/6007/Fuzzy.htm
>
> Best,
>
> Peter.
>
> -----== Posted via Deja News, The Leader in Internet Discussion ==-----
> http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
Also see Earl Cox's books, "Fuzzy Systems Handbook" and "Fuzzy Logic for
Business and Industry". In it he describes a fuzzy system for
determining retail prices.
But you have hit on two of the weaknesses of traditional rule-based
systems, both of which are addressed through the use of fuzzy logic...
--
*********************************************************************
Anthony Cowden, Manager, Fuzzy Systems Solutions
Sonalysts, Inc.
Fuzzy Systems Solutions: http://www.sonalysts.com/fuzzy.html
Fuzzy Query (TM): http://www.sonalysts.com/fq.html