|
|||||||||||||||
AI Expert NewsletterAI - The art and science of making computers do interesting things that are not in their nature. November 2003RulesBusiness rules is the current term for a type of knowledge that is knotty to automate. The type of knowledge it refers to is logical knowledge, as distinct from factual knowledge or procedural knowledge. Factual knowledge is exactly that, and it can very naturally be stored in a computer because a computer's basic architecture includes memory, both internal and external, that is ideally suited to storing factual information. Database tools and the constructs in programming languages that describe facts have evolved naturally from computer memory. Procedural knowledge is the knowledge of how to do something, the steps to take to perform a task. A computer has a central processing unit (CPU) that does things, one step at a time, which is ideally suited for executing procedures. Programming languages have evolved from this basic architecture that make it easy to encode and execute procedural knowledge. It is a computer's natural aptitude for facts and procedures that lead to the birth of "data" "processing." Logical knowledge is about relationships between entities. Despite the stereotypes and use of the word 'logic' in talking about computers, computers do NOT have a natural aptitude for storing and using logic. Tools and techniques have been developed for automating logical knowledge, but they do not have the clean connection to the underlying machine that tools for factual and procedural knowledge have. Logic lets you assert: If an individual is human then that individual is mortal. This isn't a fact that is easily stored as data. Nor is it a procedure. It is an assertion of a relationship that can be applied to deducing new facts from old. It doesn't fit well as a passive fact in memory, because it is meant to be applied to data; but it doesn't fit well as a procedure because it is not a step in a sequence of steps to be executed. If logic was limited to philosophical assertions, who cares. But logic is also how you express relationships like: If a call was made on a weekend the price is 5 cents a minute. The pragmatic value of automating this type of logic is more apparent. Conventional ToolsThe most common method of automating logical relationships, such as the pricing rules above, is to shoehorn them into either data or procedures. There are difficulties, as we'll see, but this approach has the tremendous advantage of using the same tools and programming talent used for all other aspects of application development. Database ApproachThe pricing rules above could be put into a decision table with rows and columns like this.
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 ApproachThe 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 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 ToolsThe 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 turn around, and increased capabilities. Code CornerWhen an off-the-shelf tool fits a problem well, then it is a good choice. But often times 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 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:
Knowledge RepresentationFrame 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 * 5, 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 * 5. 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's 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 * 7, conditions :: (day_type = weekday) and (start >= 2000) ]). rule(r3, [ goal :: price = duration * 10, 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 its found a solution. get_slot(Slot, Val, [Slot :: Val | _]) :- !. get_slot(Slot, Val, [_ | Slots] :- !, get_slot(Slot, Val, Slots). Reasoning EngineBefore 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's 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 EnhancementsThe 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 use 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. |
|||||||||||||||
|
Copyright
©2002-04 Amzi! inc. and CMP.
All Rights Reserved.
|
