Errata

A few newsletters back I promised to only cut and paste working code in newsletters. I messed up again, sigh. The prices are wrong in the rules in the newsletter. As one reader pointed out, the rule-based approach is just as error prone as other methods.

(the error has been fixed in the archive version. ed)

Actually, its my cut and pasting that's flawed. I decided to change the prices midstream and failed to put the new prices in the rules in the newsletter, but ran the example from the updated rules on my machine. This time I really promise not to change code mid stream ever ever again.

However, it is interesting to note that the inadvertent bug in the pricing rules is much easier to find and correct than the deliberate bug in the procedural version. So maybe my cut and paste error actually serves to illustrate the clarity advantage of the rule-based approach.

A Drug Interaction Prototype

Last month we looked at a simple prototype for a rule-based system that dealt with pricing and similar problems. This month we've got a real world example of a drug interaction system (DIS) to work with. We'll use it as a case study in designing a knowledge representation language and reasoning engine for a specific type of application.

The example illustrates many of the issues with knowledge-based systems, in that there are different types of knowledge that need to be represented and used. Those needed for DIS are different from those needed for the pricing example used last month.

For DIS, the goal is to come up with a system that can use general principles of drug interaction to predict interactions of drugs that haven't been tested together. The source material was provided by Dr. Thomas Brown, author of Psychiatric Side Effects of Prescription and Over-the-Counter Medications, Second Edition (Washington DC, American Psychiatric Press, Inc, in press), who is an expert in neurological drug interactions.

The Knowledge

The first step is to start with a self-contained example. In this case it is the potentially deadly serotonin syndrome. Serotonin is a normal chemical messenger created by the cells in the body, but when the mechanism for the creation and/or use of serotonin is altered, problems can occur.

The serotonin syndrome is a drug side-effect that occurs when two conditions are met:

• there is an increase in the amount of serotonin outside the cells, and
• either:
  • an impairment in the body's ability to get rid of serotonin, or
  • an aberration in the body's response to serotonin.

This is the basis for a "first principles" type system. Once we encode this knowledge, then the problem of predicting a drug interaction becomes one of determining if a combination of drugs or medical conditions causes the conditions leading to the serotonin syndrome.

Amphetamine, dextromethorphan, and alcohol are examples of agents that stimulate the release of serotonin. Citalopram, paroxetine, diabetes and St. John's wort all inhibit the body's ability to reabsorb serotonin. Buspirone stimulates the activity of serotonin once released.

Because the system will be designed to find all possible drug interactions, I've added a bit of first principles knowledge from my own research in neurological drugs. This will be used to test if the system finds all the information required.

That rule is a person becomes inebriated if the blood alcohol level increases, and that the blood alcohol level increases when a person consumes alcohol.

The prototype uses some concepts developed in last month's newsletter and adds some new ones for this particular problem. The code examples use Prolog, but any language can be used to implement the concepts presented.

Unlike with previous issues of the newsletter, the full code is not contained in the newsletter, just the significant bits, and the bits that weren't covered in other newsletters. Contact me if you are interested in receiving the full source code for the prototype.

Frame Based

A frame-based knowledge representation is convenient and can, at a later time, be easily mapped to a GUI development environment.

rule('blood alcohol', [
    value :: increased,
    conditions ::
        consumed = alcohol
    ]).

A frame is a general purpose knowledge structure that is composed of 'slots' where a slot is really just an attribute and a value. In the text form of a DIS frame a :: operator separates a slot from its value.

In a minor change from last month's rules, the name of the rule is now the name of an attribute, and the slot 'value' has the value of the attribute.

The example frame is for a rule about 'blood alcohol' and the two slots provide a value for 'blood alcohol' and the conditions under which that value is true. In customizing our system we can have any types of frames we want with any types of slots.

One can easily imagine a dialog box in a GUI with input fields for the various slots. That GUI would create the text file form shown above. But that's a future project, for now knowledge will be hand-coded into structures like the one above.

Ontology Important

Based on the preliminary documents it appears that a tremendous amount of the knowledge is really semantic, and semantic information is best stored in frames that are intended to be used as an ontology.

word(alcohol, [
    a_kind_of :: agent,
    stimulates :: 'serotonin release'
    ]).
word(gin, [
    contains :: alcohol
    ]).
word(martini, [
    contains :: gin,
    contains :: vermouth
    ]).

Note that our ontology for this application has more substance in it, with entries such as 'stimulates' added where appropriate. This will let us encode rules that have as a condition, for example: stimulates serotonin release, that will fire when the fact that a person consumed a martini is entered. This is because the reasoning engine is designed to understand the ontology and trace the relationships, in this case that a martini contains gin and gin contains alcohol and alcohol stimulates serotonin release.

Rules

The frames for rules simply specify the value for a factor and the conditions under which that value is appropriate. This gives us the flexibility to use the rules in a variety of reasoning strategies.

Rule(inebriated, [
    value :: true,
    conditions ::
        'blood alcohol' increased,
explanation :: [
        `When alcohol content in blood increases, person gets drunk.`],
citation :: `Oct 2003 observations of Dennis Merritt`
]).


rule('blood alcohol', [
    value :: increased,
    conditions ::
        consumed = alcohol
]).

These two rules state that the state inebriated is true if blood alcohol is increased and that blood alcohol is increased if alcohol was consumed.

Note that we've defined 'increased' as an operator that can appear after a value, which allows for more natural writing of rules with a condition like 'blood alcohol' increased, rather than 'blood alcohol' = increased.

The frame structures allow us to add other fields to use as we will. In this case a textual explanation of the rule and a citation is provided that might be used in explanations. These could be displayed by the reasoning engine when this rule takes effect, or just used as documentation during development.

Boolean Values

Version 0-0 of DIS assumes the world is black and white. Either blood alcohol is increased or it isn't, a person is inebriated or not. In the real system there will have to be some way to represent the shades of gray in the world. There are a number of choices and we need to decide on the best one.

Certainty factors (CF) are easy to implement and have a nice intuitive feel, but are not based on any mathematical theories.

Fuzzy logic seems like it would work well for some the knowledge. For example, fuzzy values map very nicely to words in the knowledge like "increased" above. The use of fuzzy values requires the development of small mathematical models that can be used to determine the relationship, for example, between consumed alcohol and blood alcohol, as well as the relationship between blood alcohol and inebriation.

But fuzzy logic doesn't capture other parts of the knowledge, in particular the desire to know if the serotonin syndrome is likely or not. In that case we really want more of a probability than a fuzzy value.

Bayesian probability is based on sound mathematics and seems like a good fit for representing the probabilities of various drug interactions.

But, stepping back, Bayesian probability doesn't capture the essence of the concept of inebriation. Increasing the consumption of alcohol doesn't increase the probability of inebriation, but rather increases the degree of inebriation.

Maybe some combination of fuzzy models and Bayesian probability is best? I'm not sure.

But for version 0-0 the world is black and white. You consume a martini, you're drunk; you have the conditions that trigger serotonin syndrome, you have serotonin syndrome.

Reasoning Engine

The first cut at the reasoning engine assumes that in the real world this system will work off data for a given individual. In other words, the data will be known and the system will output what conclusions might be drawn from that data.

So a data-driven approach was used. The system is started with initial data, and then the various rules are tried until none fit anymore. The system then reports on everything it knows.

So if the system started with the data (the square brackets means a list and there could be more things consumed):

consumed = [martini]

then it would output all of the derived information as well as the initial information.

inebriated = true
    'blood alcohol' = increased
    'extra cellular serotonin' = increased
consumed = [martini]

A data-driven reasoning engine was used in version 0-0, but I'm not sure it really captures the essence of the problem. Data-driven (forward chaining) is very good for synthesizing solutions where there are seemingly infinite possibilities, such as in a configuration or planning system. In this case there is only a finite number of known outputs and probably a better reasoning strategy is one that simply walked a list of all solutions using each as a goal in a goal-driven approach, similar to what was used in last month's pricing example.

But version 0-0 started with data-driven approach and here is the code that implements it:

figure_all :-
    rule(Name, Attrs),
    not(used(Name)),
    get_slot(conditions, C, Attrs),
    prove(C),
    get_slot(value, V, Attrs),
    asserta(known(Name, V)),
    asserta(used(Name)),
    !,
    figure_all.
figure_all.

This is a simple forward-chainer that is not very efficient, but gets the job done for the prototype. It finds a rule that has not been used yet, and tries to prove the conditions. If it can prove the conditions, then the value in the rule is asserted as the value for the name of the rule and the rule is noted as having been used. The loop is then recursively started again.

If the conditions can't be proved, then the next rule is tried.

This simple strategy ensures that all the rules that can fire, will. And that rules that depend on other rules will simply wait until they have the conditions necessary to fire. The predicates get_slot/3 and prove/1 were covered in last month's newsletter. But we've added some conditions for prove/1 that allows the rules to use the terms 'increased', 'impaired' and 'aberrated' as operators which makes for more readable rules.

...
    prove(increased(X)) :-
        known(X, increased),
        !.
    prove(impaired(X)) :-
        known(X, impaired),
        !.
    prove(aberrated(X)) :-
        known(X, aberrated),
        !.
...

General Pattern Rules

Moving onto the real rules, the idea behind the system is to encode general patterns that might trigger even for unknown combinations of drugs. This suggests that the idea of logical, pattern-matching variables, might be useful in the rules.

Rule('serotonin syndrome', [
    value :: true,
    conditions ::
        'extra cellular serotonin' increased and
        ( 'serotonin removal' impaired or
            'serotonin response' aberrated ),
    explanation :: [
        `Serotonin syndrome results when two conditions are`,
        `met: an increase in extra cellular serotonin and either`,
        `an impaired or aberrated ability to deal with the extra`,
        `serotonin.`],
Citation :: `Oct 2003 private communication with Dr. Thomas Brown`
]).


rule('extra cellular serotonin', [
    value :: increased,
    conditions ::
        X stimulates 'serotonin release' and (consumed = X or condition = X)
]).


rule('serotonin removal', [
    value :: impaired,
    conditions ::
        X inhibits 'reuptake of serotonin' and (consumed = X or condition = X)
]).

rule('serotonin response', [
    value :: aberrated,
    conditions ::
        X stimulates 'serotonin activity' and (consumed = X or condition = X)
]).

Here we have a general rule for the serotonin syndrome and three rules that are used by it. Each of those is using the ontology to look for the sorts of things that might cause trouble. The logical variable lets us express the idea, as in the last rule, that if there's an X that stimulates serotonin activity and X was consumed or X is a condition the person has, then the serotonin response is aberrated.

Here are some additional ontology entries used in the following examples.

Word('NyQuil(tm)', [
    contains :: alcohol
    ]).
word('Effexor(TM)', [
    a_kind_of :: venlafaxine
    ]).
word(venlafaxine, [
    a_kind_of :: agent,
    inhibits :: 'reuptake of serotonin'
    ]).
word(diabetes, [
    a_kind_of :: condition,
    inhibits :: 'reuptake of serotonin'
    ]).

So if we start the system with the data:

consumed = ['NyQuil(TM)']
condition = diabetes

we get the following derived results.

Inebriated = true
'blood alcohol' = increased
'serotonin syndrome' = true
'serotonin removal' = impaired
'extra cellular serotonin' = increased
condition = diabetes
consumed = ['NyQuil(TM)']

Similarly if we start with

consumed = [martini, 'Effexor(TM)']

we get:

inebriated = true
'blood alcohol' = increased
'serotonin syndrome' = true
'serotonin removal' = impaired
'extra cellular serotonin' = increased
consumed = [martini, 'Effexor(TM)']

There is an interesting design issue here. When logical variables are introduced into the rules, the rules become both more powerful and more difficult to use. I was talking with a language designer at IBM who indicated that as soon as you add pointers to a programming language you increase its expressive power but limit the number of programmers who can use it. Logical variables have the same effect on rule languages.

Testing

To facilitate testing, a file of test case data is kept. Here's two test cases used above:

test(5, [
    consumed :: [martini, 'Effexor(TM)']
    ]).
test(6, [
    consumed :: ['NyQuil(TM)'],
    condition :: diabetes
    ]).

Custom Conditions

As we move ahead in encoding knowledge, we'll come across various ideas we want to express. For example, the Sternbach diagnostic is a criteria that is defined as true when a patient has at least three findings from a set of eleven. So we create a syntax for expressing that idea and then making reasoning engine understand how to use it. A simple modification of prove/1 lets us now use some_of and one_of in the rules.

Rule('Sternbach''s diagnosis', [
    value :: true,
    conditions ::
        some_of(3, ['mental status change',
            agitation, hypertension, uncoordination, myoclonus,
            hyperreflexia, tremor, shivering, diaphoresis,
            diarrhea, fever])
    ]).

rule('mental status change', [
    value :: true,
    conditions ::
        one_of( [confusion, hypomania] )
]).

Testing these new rules and conditions with these inputs:

test(4, [
    'myoclonus' :: true,
    'hypomania' :: true,
    'shivering' :: true
    ]).

yields this result

?- main.
test? 4.
'Sternbach''s diagnosis' = true
'mental status change' = true
shivering = true
hypomania = true
myoclonus = true

yes

Next Steps

The most critical next step for this system is to resolve the way uncertainty is dealt with. After that is done, additional examples of drug interactions knowledge can be added to this system to see what changes they may require.

Product Announcements

Evolution Robotics

(See review in March 2003 issue of this newsletter.)

Evolution Robotics announces a 50% price reduction for its ER1 robot kit. The ER1 gives hands on experience with computer programming and basic engineering to technology enthusiasts, software developers, scientists and inventive young adults across the board. Additionally, the company announces the release of a noncommercial license version of its Evolution Robotics Software Platform 2.0 (ERSP-NC 2.0) specifically for use in the classroom. This offer is available exclusively to educational institutions.

The award-winning Evolution Robotics ER1 Robot is now available for as little as $299 - a 50% reduction. With its professional grade robotics software and highly customizable hardware, ER1 is the ideal gift for the inventive young adult or technology enthusiast on your gift list. The world's first autonomous mobile robot has been featured in CNN, MSNBC, PC Magazine, Time, Geek.com, Linux.com and other high profile media venues.

The ER1 is the first robot with professional-level robotics software and industrial grade hardware designed specifically for enthusiasts, educators and researchers. The ER1 has computer vision, hearing, speech, networking, remote control, e-mail, autonomous mobility, gripping, and IR sensing capabilities - all brought together with an open software system and a reconfigurable chassis. Robot enthusiasts and online Evolution Robotics communities agree that ER1 provides a powerful yet accessible hands-on experience in computer programming, basic engineering and an introduction to the world of robotics.

Additionally, the company announces the release of a noncommercial license version of its Evolution Robotics Software Platform 2.0 (called ERSP(TM)-NC 2.0) specifically for use in classrooms. This offer will be available exclusively to educational institutions. Please send e-mail to [email protected] for pricing details.

ERSP 2.0 is a robot development platform comprised of four areas of functionality: vision, obstacle avoidance, interaction, and architecture. ERSP 2.0 includes library APIs, developer tools, and applications to aid in the robot and software development process. Available on Windows and Linux, education institutions can use ERSP-NC 2.0 in classroom settings to facilitate research, education and encourage a deeper exploration of robotics and associated application development. ERSP is being used by a number of well known consumer electronics companies, including Sony, to develop new robot applications, and entirely new robots.

Amzi! inc.

Amzi! has created a Prolog plug-in for the Eclipse Interactive Development Environment (IDE). Eclipse is an open source IDE that rivals the best of current commercial development environments. The Amzi! plug-in supports comprehensive project support, syntax coloring, predicate cross-reference and outline windows.

A full Prolog listener is included and a source code debugger that combines that best of conventional debuggers with the Prolog four-port model. The current line of code is color-coded by port in the source listing; a full stack trace is presented, which can be examined at any level; and the variable bindings for each stack frame are presented. The combination of these three elements makes for a very clear presentation of Prolog execution which is ideal for students and advanced developers alike.

Eclipse supports remote debugging, so compiled Prolog components running in larger mixed-language application contexts, and even on remote machines can be debugged as easily as local stand-alone Prolog projects.

The Eclipse plug-in is part of the Amzi! 7.0 release which is available in both Student and Professional Editions. See www.amzi.com for details.

Links

These are some links provided by readers:

www.iaail.org - The International Association for AI and the Law

www.jurix.nl - A forum on legal knowledge based systems based in the Netherlands and Flanders.

http://ai.meetup.com/ - An international meet up site for people interested in AI. Meet ups are usually held on the fourth Tuesday of each month, but this month, because of the holidays it will be on December 16th at 7pm. Locations of meet ups are all around the globe.

http://www.agiri.org/ - The Artificial General Intelligence Research Institute (AGIRI) is working on the grand goal of true general purpose artificial intelligence. They have created a software engine, called Novamente, as a first step.

http://www.goertzel.org/work.html - Links to the varied works of Ben Goertzel, one of the principle researchers in AGIRI.