Rule Based Systems

Subject Index -  Links, References and Notes

 

Subject Index


Note: This section contains more or less permanent links ( at least I hope they are permanent, let me know if they are not ).   

 


Links, References and Footnotes 



Rule Based Systems


This may be the appropriate place to make first mention of the "AI" word.  Hopefully, no one will get this far into the index, because, yes, we are talking about "Art*ficial Intell*gence" ( asterisks added to get past no-no word checkers ).  Say it in a job interview and the hiring manager's eyes may go glassy and vague, assuming the manager has never heard of it before.  If they have actually done an AI project in the past, their eyes may glare and turn bright red.

 AI is a bad word in the world of business applications and justifiably so given the miserable results of many failed AI projects in the 1980s.   While it was a fun time for some people, it was a bad scene business-wise.  There were some notable successes and bright spots in the 1980s ( mostly those based on solid commercial packages such as AION, Haley Systems and Neuron Data ), but there was also a large amount of time and effort expended with no return to the companies who financed these projects.

In a sense, the technical side of the business rules movement in the 1990s was a simplification and re-branding of the many interesting but failed AI projects of the 1980s.  They outlived their AI past.  

 

A Definition of Artificial Intelligence ? 

So, with that preface behind us, good sites to find resources about rule-based systems and AI include:

A good discussion about defining "aritificial imtelligence" is found at the Internet FAQ Archives.  The author's definition of AI is:

Artificial intelligence ("AI") can mean many things to many people. Much confusion arises because the word 'intelligence' is ill-defined. The phrase is so broad that people have found it useful to divide AI into two classes: strong AI and weak AI ...

Strong AI makes the bold claim that computers can be made to think on a level (at least) equal to humans and possibly even be conscious of themselves.

Weak AI simply states that some "thinking-like" features can be added to computers to make them more useful tools... and this has already started to happen (witness expert systems, drive-by-wire cars and speech recognition software). What does 'think' and 'thinking-like' mean? That's a matter of much debate.

Another good definition of AI comes from the AI Depot, which has an excellent series of tutorials on various AI subjects.  It has a good, hammer-and-tongs definition of AI.

Artificial Intelligence is a branch of Science which deals with helping machines find solutions to complex problems in a more human-like fashion. This generally involves borrowing characteristics from human intelligence, and applying them as algorithms in a computer friendly way. A more or less flexible or efficient approach can be taken depending on the requirements established, which influences how artificial the intelligent behavior appears.

That old standby, the Wikipedia, provides a very definition of AI.

Artificial intelligence (AI) is a branch of computer science and engineering that deals with intelligent behavior, learning, and adaptation in machines. Research in AI is concerned with producing machines to automate tasks requiring intelligent behavior.

The Wikipedia article also has an interesting comment about the different "schools of thought" within AI.

AI divides roughly into two schools of thought: Conventional AI and Computational Intelligence (CI). Conventional AI mostly involves methods now classified as machine learning, characterized by formalism and statistical analysis. This is also known as symbolic AI, logical AI, neat AI and Good Old Fashioned Artificial Intelligence (GOFAI) ... [ details ] ...

Computational Intelligence involves iterative development or learning (e.g. parameter tuning e.g. in connectionist systems). Learning is based on empirical data and is associated with non-symbolic AI, scruffy AI and soft computing.

The central problem of all these definitions and all definitions of 'AI' that I have encountered is to define the most important term being used to define the term 'AI'. What is intelligence ?  A fundamental problem for the entire field of AI is finding a clear and concise definition of "intelligence".  While I've seen better or worse definitions of the term, I have never seen "intelligence" defined adequately for the purposes of machine simulation.

The Possibility of Intelligence as Emergent Behaviors

On the other hand, who needs intelligence if you can get the job done ( as any experienced hiring manager knows ).

Among the leading AI hacker sites is AI Junkie, which ran a fascinating competition to demonstrate emergent behavior in 2003. Their definition of emergent behavior is:

Emergent behavior is behavior that looks complex and/or purposeful to the observer but is actually derived spontaneously from fairly simple rules. The lower level entities following the rules have no idea of the bigger picture, they are only aware of themselves and maybe a few of their neighbors. Emergent behavior can be found everywhere, from the shoaling habits of fish and ant foraging behavior to the ebbs and flows of traffic tailbacks and the growth of animal societies. 

This describes something very like the complex, unpredicted behaviors often encountered in large rule systems.  The phenomena of 'purposeful behavior derived spontaneously from fairly simple rules' is almost certain to be encountered in rule systems with more than a few hundred rules, sometimes catastrophically.

What I found even more interesting was the entry of the second place winner of the contest, David Lotts' Stem Scaffolding. The result of his design was something that looks very much like the scaffolding of building.

Architects say a major challenge with the next generation of massive buildings is creating the machines that can do the job. These structures are too large to be constructed by a traditional crew with hand tools. They need the construction equivalent of a sewing machine, something that can stay on the leading edge of the structure, and then push itself on top of its last stage, to start the next stage. Thatís what I had in mind for this project. I wanted to create a set of simple agents that would interact to create building-like structures.

But instead of the building machines following a rigid plan, I imagine machines that obey simple predetermined rules for behavior, that interact as they build, creating an architecture that could not be predicted by understanding the machines themselves."

To paraphrase his statement a bit, a crew of simple rule enactors created a result that could not be predicted by understanding the rules themselves.  While a software simulation of "artificial intelligence" is not equivalent to the  behavior of staggeringly complex biological systems demonstrating "real intelligence", computers programs can mimic the same level of "intelligence" as demonstrated in the behavior of simple organisms such as plants and insects.   

What is Intelligence ?

 It might be a better course to use the term "intelligent systems".  It seems to be less loaded with meaning than the term "artificial intelligence", though it would be difficult to say why that is so.  It may be that "intelligence" as noun indicates "The Intelligence", human intelligence, presumably sanctioned by the 'natural order of things', if not by an even higher authority.  The adjective form, describing a noun, seems to indicate an acceptably synthetic and 'ersatz' form of intelligence permissible in the natural order of things.

That still doesn't explain the use of the term "Central Intelligence", but that  particular usage must remain one of the great mysteries of the human mind.

Joking aside, it may well be that accepting and learning to deal effectively with the Great Imponderables of Existence is one of the highest expressions of 'intelligence', in its all-encompassing noun form.

At this point of time, almost any chess playing program running on a standard personal computer can beat almost any human chess player, but does that mean they are more intelligent ?  Since the game of chess is based upon a finite, complete and internally consistent set of rules, the 'knowledge domain' is is amenable to exact deductive reasoning.  But, is real intelligence the capability for 'inexact reasoning' ? 

The ability to make correct decisions based on incomplete and contradictory information may be one of the highest goals of intelligent systems, determining more than any other factor "how artificial the intelligent behavior appears".                   

Back to Subject Index

Rule Based Systems - History


Early Successes

Did anyone ever hear the word "objects" outside the AI world before 1988.  Not that I ever heard.  

Early versions of knowledge engineering methodology influenced many later development in the 1990, including objects, rules, rule engines and many others.   

Today, there is an active technology devoted to building rule-based and knowledge-based applications.  Tools and technical infrastructure to discover, design, develop and manage large rule based systems are plentiful and relatively cheap.  Some are even "open source".

The preeminent 'vault' of old AI toy systems is the Artificial Intelligence Repository at Carnegie Mellon University.   

Smalltalk

There was also an entire class of intelligent business applications developed with the Smalltalk language.  While not specifically an 'AI' language, it was capable of modeling very complex data structures in a relatively easy and natural way. Originally named "Smalltalk 80", it was developed at Xerox Parc as the world's first integrated graphical object-oriented environment.  Alan Kay and a brilliant crew of computer scientists were the inventors of the 'mouse' pointing device and the modern byte-code interpreter, among many other innovations.  There is still some debate about who was the 'first first' rather than the 'second first'.

The marketing objective of Smalltalk was to replace COBOL as the standard  language for business application development - they projected that Smalltalk would own 50% of the market by 1990.  In other words, it was to be Xerox Systems' IBM killer.  It is interesting to note that, perhaps as an example of moral lessons in the history of technology, the leading provider of Smalltalk business solutions today is IBM.  

Memory Lane

Who remembers the Smalltalk version of the Xerox Star workstation, which eventual became the basis of the Apple Lisa, which in turn became the Apple Macintosh ?  Who remembers the Xerox lawsuit against Apple about it ( and visa versa ) ?

Who remembers Xerox 1185 and 1186 AI Workstations , way back in 1985 ?

The Xerox 1185 and 1186 Artificial Intelligence (AI) Workstations, intended for the design, use and delivery of AI software and expert systems, are released. These artificial intelligence machines use the Interlisp-D programming environment and computer techniques developed at PARC to duplicate [ !!! ] the human cognitive process of problem solving.

Note the emphasis on the word "duplicate" !  Ah, the Age of Innocence ...

 

Back to Subject Index

Rule Based Systems - Conceptual Modeling


 

 

Zachman Framework

 








http://bizrules.info/

For Rule CM Method


The Business Rules Knowledge Base shows and tells you 

what you need to know about business rules

why you should use the business rules approach, methodology and tools

how how to get from the rules idea stage to the action stage

where to go for more information, resources, and blogs

who are the business rule engine (BRE) vendors, business rule management system (BRMS) vendors, and business rules consultants that can help you get there

when business rules events such as conferences and seminars are taking place.







 

Common Sense Reasoning / Qualitative Reasoning

Papers on Qualitative Reasoning at University of Texas Department of Computer Science

http://www.cs.utexas.edu/~qr/papers-QR.html

Kuipers' Classic, Commonsense reasoning about causality: deriving behavior from structure.

 

 

B. J. Kuipers. 1984. Commonsense reasoning about causality: deriving behavior from structure. Artificial Intelligence 24: 169-203.

 

ftp://ftp.cs.utexas.edu/pub/qsim/papers/Kuipers-aij-84.pdf


Problem Solving and Truth Maintenance Systems

http://www.cis.temple.edu/~ingargio/cis587/readings/tms.html

http://www2.parc.com/spl/members/dekleer/Publications/PhysicsQualitative.pdf

 

Generic Task Models and Design Patterns

 

http://www.edlin.org/cs/patterns.html



http://c2.com/ppr/

Portland Pattern Repository

Patterns are the recurring solutions to the problems of design. People learn patterns by seeing them and recall them when need be without a lot of effort. Patterns link together in the mind so that one pattern leads to another and another until familiar problems are solved. That is, patterns form languages, not unlike natural languages, within which the human mind can assemble correct and infinitely varied statements from a small number of elements. 

http://www.csc.calpoly.edu/~dbutler/tutorials/winter96/patterns/


Patterns are devices that allow programs to share knowledge about their design. In our daily programming, we encounter many problems that have occured, and will occur again. The question we must ask ourself is how we are going to solve it this time. Documenting patterns is one way that you can reuse and possibly share the infomation that you have learned about how it is best to solve a specific program design problem. 

http://developer.yahoo.com/ypatterns/page.php?page=lifecycle

What's a Pattern?
A pattern describes an optimal solution to a common problem within a specific context. 

From the IAWiki: 

Patterns are optimal solutions to common problems. As common problems are tossed around a community and are resolved, common solutions often spontaneously emerge. Eventually, the best of these rise above the din and self-identify and become refined until they reach the status of a Design Pattern.

Each pattern has four primary components: 

a title 
a problem 
a context 
a solution 

Because a picture is worth a thousand words, the patterns also have a "sensitizing example" (we have tried to include a screen shot along with an animation example of the interaction) that visually represents the pattern. 

http://www.iawiki.net/WebsitePatterns

Patterns are optimal solutions to common problems. As common problems are tossed around a community and are resolved, common solutions often spontaneously emerge. Eventually, the best of these rise above the din and self-identify and become refined until they reach the status of a Design Pattern. 
Architect Christopher Alexander was the first to name this phenomenon with respect to living spaces. He and his co-writers introduced the concept of Architecture Patterns to describe features that living spaces share whether they be rooms, buildings or towns. 

Patterns are atomic in that they can be grouped to form more complex patterns: a chair pattern nests within a dining room pattern that nests within a house pattern that nests within a town pattern. 

One idea that distinguishes Patterns from simple prescriptions is that Patterns never lose sense of their context; they describe things that work together and the rules that govern those collections. 

 


U Calagary Design Patterns

http://pages.cpsc.ucalgary.ca/~kremer/patterns/index.html

What is a design pattern?

* A design pattern is to design is what a class library is to coding
* Documentation of expert software engineers' "behaviour"
* Documentation of specific reoccuring problems (and solutions)
* Abstraction of common design occurances
* Large range of granularity -- from very general design principles to language-specific idioms



http://pages.cpsc.ucalgary.ca/~kremer/courses/

http://pages.cpsc.ucalgary.ca/~kremer/courses/topics.html





http://pages.cpsc.ucalgary.ca/~kremer/courses/CG/

KNOWLEDGE ENGINEERING
PART A


Generic Tasks and KADS

 

KADS

http://www.cems.uwe.ac.uk/~rstephen/courses/UQC833hm/week7/lecture.html

 


http://epubs.cclrc.ac.uk/bitstream/581/wilson89task%5B1%5D.pdf

Generic Task Models in KADS

...

Analysis
| identify
| | classify
| | | simple classify
| | | diagnosis
| | | | single fault diagnosis
| | | | | heuristic classification
| | | | | systematic classification
| | | | | | causal tracing
| | | | | | localisation
| | | | multiple fault diagnosis
| | | assessment
| | monitor
| predict
| | prediction of behaviour
| | prediction of values
Modification
| repair
| remedy
| control
| | maintain
Synthesis
| transformation
| design
| | transformational design
| | incremental design
| | | single stream incremental design
| | | multiple stream incremental design
| | configuration
| | decomposition
| planning
| modelling

Table 4: Taxonomy of Problem Types (after Breuker et al, 1987)



http://ksi.cpsc.ucalgary.ca/KAW/KAW98/motta/


http://www.webkb.org/kb/KADS1.html


The generic task models include data-flow structures (the "Inference structures") and control structures (the "Task structures"). Inference structures also called interpretation models since they help to find which information is interesting in the expertise sources. They show the input-output relations between primitive tasks (called "inference") or complex tasks (called "task"), but do not specify the control on these tasks, i.e. in which order they must be applied (this is application-dependent). 


From the KADS Ontology ( reformatted ):  

The following is a loose assembly of possible tasks.  Note that some are under-defined.

Collect
Generalize find a superclass/superset for one or several instances/facts or classes Classify, Cluster
Classify the class hierarchy is given Abstract class, Identify
Abstract  class->superclass
Identify instance->class
Cluster classes are learnt from examples
Specialize find a subclass/subset or an instance/fact Refine, Instanciate, Select
Refine class->subclass
Instanciate class->subclass/instance
Select set of instance->subset of instance
Compare  in the sense given by KADS - [compare values ? ] Compare Value, Match
Compare Value
Match compare structures
Modify  in the sense given by KADS Assign, Evaluate, Transform, Assemble, Decompose
Assign a value to an attribute of something
Evaluate produces a concept regarding the structure of something
Transform e.g. sort, restructure
Assemble
Decompose 
Determine truth or relevance Establish, Cover, Verify
Establish
Cover
Verify
Explore option e.g. Make_decision (Select), Propose_solution (Generate) Make decision, Propose solution, Generate
Make_decision
Propose solution
Generate
Reduce Working Set e.g. Anticipate, Prefer, Rule out Anticipate, Prefer, Rule out
Anticipate
Prefer
Rule out


Temporal Modeling

An excellent site on the subject of temporal modeling is Time Rover.  If you always wanted to sink your teeth into temporal modeling statements such as "ev2 any number of cycles after ev1, with no ev3 in between: Always ( {ev1} Implies ( (Not{ev3} Until {ev2}) And Eventually {ev2} ) )", the site is a golden opportunity to do so.  

From the KADS ontology ( slightly reformatted ). 

Temporal_entity {point or interval in time, e.g. Time_period, Point_in_time, WN_time/n}

  > WN_time/n,  (Point_in_time, Time_period);

WN_time/n {the continuum of experience in which events pass from the future through the present to the past};

Point_in_time {point in time of a Situation};

Time_period {duration of a Situation};

 


Back to Subject Index

Rule Based Systems - Data and Metadata, Models and Metamodels


An interesting blog in .de-Land.

http://oxygen.informatik.tu-cottbus.de/RealRules/

 

http://www.eclipse.org/articles/Article-Rule Modeling With EMF/article.html

http://www.eclipse.org/articles/Article-Rule%20Modeling%20With%20EMF/article.html

Back to Subject Index

Rule Based Systems - Design



http://www.pega.com/Products/RulesTechnology.asp?gclid=CJayvp7IwogCFUxuGgodV3GUEQ



Dozens of Fit-for-Purpose Rule Types Provides a variety of rule types to help organizations get started quickly and maximize performance 

Declarative Rules: Compute values or enforce constraints as other properties change 

Decision Tree Rules: Conduct fact-based inferencing to execute "if-then" types of logic 

Integration Rules: Streamline interfacing between systems and applications 

Transformation Rules: Automate data mapping and parsing between disparate systems 

Process Rules: Manage the receiving, assignment, routing, and tracking or work 

 

http://www.compinfo-center.com/tpai-t.htm

The compinfo-center cites a definition formulated by Knowledge Technology Inc.

Artificial Intelligence (PC AI) (Knowledge Technology, Inc) 

An AI program that models the nuances of the human thought process or solves complicated real-world problems can be complex. Languages for building AI programs have the capacity to that take care of low-level computing processes, thus allowing the developer to focus on the requisite complexity. AI programs work with concepts expressed in words, phrases, or sentences. Therefore, the ability to handle symbolic (i.e., non-numeric) data is an important feature. To develop an AI system, a programmer tries numerous ways of implementing each constituent function. Rather than go through a lengthy edit-compile-debug cycle to test each rendition of a function, an AI language should allow the programmer to quickly see the results of a new idea. Languages that feature interactive programming address this need. Programmer can not anticipated the exact type or quantity of data that flows through a program, so the must adapt on the fly. A language that incorporates flexible data structures allows this happen in an easy, natural way. Many types of inference processes recur throughout an AI applications. A language that has one or more of these processes built-in can save time and effort. 

 

 

 

Back to Subject Index

Rule Based Systems - Association and Associative Networks


 

Back to Subject Index

Rule Based Systems - Other Approaches


A major alternative, and perhaps the most conceptually powerful alternative in the the long run, is in the field of  Logic Programming.  The Prolog language and its many variants are leading examples of Logic Programming.

A wonderful and intellectually challenging site is the Library for Automated Theorem Proving site at the University of Miami, hosting the TPTP (Thousands of Problems for Theorem Provers) Problem Library.  It contains literally thousands of logic proofs, puzzles, set of mathematical even collections of logical anomalies and contradictions ( where both A and NOT A must be true in order to satisfy the set of rules ).

Among many other good things, they have provide a good of definition of Automated Theorem Proving.  Note that the text is slightly reformatted for readability.

Automated Theorem Proving (ATP) deals with the development of computer programs that show that some statement (the conjecture) is a logical consequence of a set of statements (the axioms and hypotheses). ATP systems are used in a wide variety of domains. For example,

-- a mathematician might prove the conjecture that groups of order two are commutative, from the axioms of group theory;

-- a management consultant might formulate axioms that describe how organizations grow and interact, and from those axioms prove that organizational death rates decrease with age;

-- a hardware developer might validate the design of a circuit by proving a conjecture that describes a circuit's performance, given axioms that describe the circuit itself;

-- or a frustrated teenager might formulate the jumbled faces of a Rubik's cube as a conjecture and prove, from axioms that describe legal changes to the cube's configuration, that the cube can be rearranged to the solution state.

All of these are tasks that can be performed by an ATP system, given an appropriate formulation of the problem as axioms, hypotheses, and a conjecture. 

They also have a good definition of the field called Commonsense Reasoning. Again, the text is slightly re-formatted.

Commonsense reasoning is the branch of artificial intelligence concerned with replicating human thinking. There are several components to this problem, including:

-- developing adequately broad and deep commonsense knowledge bases;

-- developing reasoning methods that exhibit the features of human thinking, including

-- the ability to reason with knowledge that is true by default,

-- the ability to reason rapidly across a broad range of domains,

-- and the ability to tolerate uncertainty in your knowledge;

-- developing new kinds of cognitive architectures that support multiple reasoning methods and representations.

In fact, this may be the best statement of requirements for a simple, intuitive rule-based environment capable of taking on something as gigantic and complex as a Semantic Web.  

 

Back to Subject Index

 


Appendix


 

Back to Subject Index