AI and the Law
The program that priced a call would take call data, compute the boolean values
of weekend and night, and then do a table lookup to get the price per minute.
This approach gets thorny, though, as the number of parameters increase and
only a subset of those parameters applies for a given call. That can already
be seen in this simple example where we need to store information about the
boolean night for a weekend call, when it isn't necessary (the night
and day rate being the same on the weekend).
And the clarity of the original rule specifications is lost, making maintenance
difficult.
Procedural Approach
The rules could be coded procedurally using if-then branching statements to
express the relationships.
if day = weekend
then price = 5
else
if time = night
then price = 7
else price = 10
Or should it be:
if time = night
if day = weekend
then price = 5
else price = 7
else
if day = weekend
then price = 7
else price = 10
The problem with this approach is that artificial decisions need to be made about
the ordering of the if-then statements because they are really branching statements.
They don't have the pattern-matching sense of the original logical relationships,
which have no implied order.
Like with the decision table, the clarity of the original rules is lost. This
approach is also highly error-prone. Did you see the bug in the above code?
How about now?
Specialized Tools
The problems of automating logical knowledge were first studied at Stanford
University by researchers trying to encode medical diagnostic knowledge, which
was naturally expressed as pattern-matching if-then rules. The number and complexity
of the rules was such that repeated attempts to use the above approaches simply
failed.
Given that the problem is really that the underlying machine doesn't support
logical relationships, they created a virtual machine that did. They developed
a rule engine that was programmed by entering rules directly.
They called their technology heuristic programming, which is a fancy way of
saying rule-based programming. They were looking for funding, and no one cared
about heuristic programming, and pattern-matching rules are sort of how a human
brain works, so they called it artificial intelligence instead.
The new name worked great, providing funding and generating tremendous media
hype and lots of follow-on companies and products. But expectations weren't
met, there was disappointment, and the name became a detriment to marketing
the technology. So now the savvy marketing types call it rule-based programming.
No matter what you call it, the underlying technology is the same--a pattern-matching
engine that looks for a rule to apply, applies it, and then does it again until
some end condition is reached.
The advantages are tremendous. The pricing rules above can be entered almost
directly as they are stated. This makes the encoding almost error-free. Further,
it lets the domain experts, such as the marketeers creating the call pricing
strategy, examine and in many cases maintain the rules themselves.
Because of the natural expressive power of the rules, more complexity can be
incorporated, and changes can be rapidly introduced. The phone company using
a rule-based approach to pricing will be more responsive to changing market
and regulatory conditions than one that doesn't.
The disadvantage with specialized rule tools is they are almost always proprietary,
require special training, and don't always adapt well to the particular logical
knowledge of a particular domain. For example, a tool designed for business
process automation isn't well suited for our pricing example, and a tool that
handles pricing won't work as well for configuration problems.
Despite these problems, the advantages of successful deployment provide competitive
advantages that make them easily worth while. All the vendors in the field have
success stories of customers switching from conventional tools to a rule or
logic-based tool and quote numbers like 10-1 reductions in code size, vastly
increased reliability, much quicker turnaround, and increased capabilities.
Code Corner
When an off-the-shelf tool fits a problem well, then it is a good choice. But
oftentimes the off-the-shelf tool doesn't quite work as required, or is simply
too expensive. In that case it's time to consider writing your own.
The advantage to writing your own rule language and engine is that it can be adapted
precisely to the application at hand. In this month's code corner we'll build
one for the pricing rules example. The examples will use Prolog, but the ideas
can be incorporated in any language.
There are two key aspects in building a rule engine:
- designing the knowledge representation, and
- implementing the reasoning engine.
Knowledge Representation
Frame-like structures are a very convenient way to store information, and have
the advantage that they can be easily mapped to various front-end user interfaces.
The frames will have two slots, one for the goal of the rule and the other for
the conditions. The :: operator
is used to separate the name of the slot from its value. Here's the first pricing
rule.
rule(r1, [
goal :: price = duration * 7,
conditions :: day_type = weekend
]).
We can now put a front end on this type of structure that maps to fields in
a GUI, or use Prolog's definite clause grammar (DCG) to create a more natural
language syntax, such as
if day_type = weekend then price = duration * 7.
In either case, internally we'll use the frame representation of the rule,
and the user interface project we'll save for another day.
The other key decision is how to store the factual knowledge that is used and
derived by the rules. For this application, simple attribute-value pairs can
be stored in Prolog clauses called known/2. For example,
known(day, saturday).
These facts will be dynamically asserted as discovered.
Here are the rest of the rules for the pricing example, including two rules that determine whether a day
is a weekend or not.
rule(r2, [
goal :: price = duration * 10,
conditions :: (day_type = weekday) and (start >= 2000)
]).
rule(r3, [
goal :: price = duration * 20,
conditions :: (day_type = weekday) and (start < 2000)
]).
rule(r4, [
goal :: day_type = weekend,
conditions :: (day = saturday) or (day = sunday)
]).
rule(r5, [
goal :: day_type = weekday,
conditions :: (day \= saturday) and (day \= sunday)
]).
In order for Prolog to read these rules, we need to define the operators that
are not already part of the language. These definitions should appear in the
beginning of the file.
:- op(850, xfx, ::).
:- op(820, xfy, or).
:- op(810, xfy, and).
We need a utility predicate that can extract a slot value from a frame. It
is a variation on the classic member/2 predicate that knows about our
particular format for slots and also doesn't backtrack once it's found a solution.
get_slot(Slot, Val, [Slot :: Val | _]) :-
!.
get_slot(Slot, Val, [_ | Slots] :-
!,
get_slot(Slot, Val, Slots).
Reasoning Engine
Before getting into the details of the reasoning engine, we need some test data. This is
the sort of application that will be driven by data and will not require an interactive dialog
with the user. So here are a few test phone calls, with an ID, Day, Start Time (in 24 hour HHMM
format), and Duration in minutes.
phone_call(1, tuesday, 1800, 10).
phone_call(2, wednesday, 2200, 10).
phone_call(3, saturday, 2200, 10).
phone_call(4, monday, 1600, 10).
phone_call(5, sunday, 800, 10).
For testing we create a main/0 predicate that uses a repeat/fail loop
to walk through the test calls, initializing the reasoning engine each time
and then asserting the known data for the call being processed. The call to
solve/2 then finds the price.
For a real application, this code would most likely be in a procedural language
that is choreographing the interaction between a database of call data, the pricing
logic base and the billing output.
main :-
price_calls.
price_calls :-
phone_call(ID, Day, Start, Duration),
init,
assert( known(duration, Duration) ),
assert( known(start, Start) ),
assert( known(day, Day) ),
solve(price, P),
write(id = ID), tab(2),
write(price = P), nl,
fail.
price_calls.
Initialization is simply clearing out any known/2 clauses from a previous
run.
init :-
retractall(known(_,_)).
The main entry point, solve/2, immediately calls find/2 which
tries to find the value for an attribute. There are two ways, the first being
that the value of the attribute is already known. If it is, find/2 looks
no further and then tests to see if the value is the one being sought and fails
or succeeds accordingly.
The second way is to use the rules. The second clause does a backtracking search
of the rule/2 frames, first checking if the goal slot sets a value for
the sought-after attribute, then getting the conditions of the rule and calling
prove/1 to see if the conditions hold or not.
If not, another rule is tried, but if so, the attribute's value is evaluated,
in case it is a formula, stored in a known/2 clause so it doesn't have
to be computed again, and then compared with the sought-after value.
solve(Attr, Val) :-
find(Attr, Val).
find(Attr, Val) :-
known(Attr, X),
!,
Val = X.
find(Attr, Val) :-
rule(R, RuleAttrs),
get_slot(goal, Attr = X, RuleAttrs),
get_slot(conditions, Conds, RuleAttrs),
prove(Conds),
eval(X, V),
assert(known(Attr, V)),
!,
Val = V.
prove/1 recursively breaks down complex condition statements with ands
and ors in them, looking for primitive conditions to prove.
prove( C1 and C2 ) :-
prove(C1),
prove(C2).
prove(C1 or C2) :-
( prove(C1)
;
prove(C2) ).
For the primitive conditions, prove/1 uses find/2 to get the
value of an attribute and then performs whatever test is necessary.
prove(A = V) :-
find(A, V).
prove(Attr \= Val) :-
find(Attr, V),
V \= Val.
prove(Attr < Val) :-
find(Attr, V),
V < Val.
prove(Attr >= Val) :-
find(Attr, V),
V >= Val.
It's easy to expand the system to include other such tests.
Because find/2 calls prove/1 and prove/1 calls find/2,
the system will easily track through complex chains of interconnected rules.
Tracing the behavior of this program in a Prolog debugger will illustrate that.
Because the rules don't just return a price per minute, but actually calculate
the price of the call, we need the ability to evaluate a formula where some
of the elements in the formula refer to values of facts. This could recursively
call find/2, allowing forumlas to trigger further reasoning, but for
now we assume that the formula refers to facts already known.
The clauses of eval/2 break down the forumla, applying the mathematical
operations at each step using the Prolog built-in math operator, is/2.
We only implemented multiplication because that's all we needed. Other eval/2
clauses can be added for other mathematical operators or other types of functions
we might want implemented.
eval(A, V) :-
known(A, V),
!.
eval(E1 * E2, V) :-
eval(E1, V1),
eval(E2, V2),
V is V1 * V2,
!.
eval(V, V).
We now have our own rule language for rules like pricing rules. It can be integrated
into larger application contexts, and expanded as the application requires.
It can also be used for other types of problems that are similar to pricing.
Testing it in a Prolog listener:
?- main.
id = 1 price = 100
id = 2 price = 70
id = 3 price = 50
id = 4 price = 100
id = 5 price = 50
yes
Enhancements
The rules should be kept in a different file from the reasoning engine, so
that different logic bases could be used for different applications. The solve
predicate would then consult the appropriate rule file.
Either a GUI or DCG front end on the rules would be nice. This would allow
for easier editing of the rules.
The reasoning engine could do with some tracing statements that optionally
display what rule is being tried, what condition being tested, etc. This could
be used for debugging.
The issue with weekdays and weekends was solved with a rule, but an ontology
would be a better solution. It would allow the adding and use of definitions
independent of the actual rules.
For large complex rule bases, a more efficient rule syntax could be used that
had the attribute as a primary argument that was indexed, allowing for quick
access of rules for a particular attribute.
Until next month,
Dennis Merritt
dennis@ddj.com
|
 |
|
MICROSITES
FEATURED TOPIC
ADDITIONAL TOPICS
|
|
|
|
|
|
|
| |
|
|
