Wednesday, May 09, 2012

Drools 5.4: Artificial Intelligence, A Little History

If you like the article, please vote up ad dzone:

As part of the 5.4 release, going out the door as we speak, I updated the intro docs. I have tried to give a wider understanding of the field and scope of work. Here is a copy. I'll try and improve the sections over future releases, I ran out of time and the later sections are little rushed and thin. I'm not the best of writers, so please have patience, all contributions welcome :)

A Little History

Over the last few decades artificial intelligence (AI) became an unpopular term, with the well know "AI Winter". There were large boasts from scientists and engineers looking for funding, that never lived up to expectations along with many failed projects. Thinking Machines Corporation and the 5th Generation Computer (5GP) project probably exemplify best the problems at the time.

Thinking Machines Corporation was one of the leading AI firms in 1990, it had sales of nearly $65 million. Here is quote from it's brochure:
Some day we will build a thinking machine. It will be a truly intelligent machine. One that can see and hear and speak. A machine that will be proud of us.

Yet 5 years later it filed for Chapter 11. has a fascinating article titled "The Rise and Fall of Thinking Machines". The article covers the growth of the industry and how a cosy relationship with Thinking Machines and DARPA over heated the market, to the point of collapse. It explains how and why commerce moved away from AI and towards more practical number crunching super computers.

The 5th Generation Computer project was a 400mill USD project in Japan to build a next generation computer. Valves was first, transistors was second, integrated circuits was third and finally microprocessors was fourth. This project spurred an "arms" race with the UK and USA, that caused much of the AI bubble. The 5GP would provide massive multi-cpu parallel processing hardware along with powerful knowledge representation and reasoning software via Prolog; a type of expert system. By 1992 the project was considered a failure and cancelled. It was the largest and most visible commercial venture for Prolog, and many of the failures are pinned on the problems trying to run a logic based programming language concurrently on multi cpu hardware with effective results. Some believe that the failure of the 5GP project tainted Prolog and resigned it academia, see "Whatever Happened to Prolog" by John C. Dvorak.

However while research funding dried up and the term AI became less used, many green shoots where planted and continued more quietly under discipline specific names: cognitive systems, machine learning, intelligent systems, knowledge representation and reasoning. Offshoots of these then made their way into commercial systems, such as expert systems in the Business Rules Management System (BRMS) market.

Imperative, system based languages, languages such as C, C++, Java and .Net have dominated the last 20 years. Enabled by the practicality of the languages and ability to run with good performance on commodity hardware. However many believe there is renaissance undergoing in the field of AI, spurred by advances in hardware capabilities and AI research. In 2005 Heather Havenstein authored "Spring comes to AI winter" which outlines a case for this resurgence, which she refers to as a spring. Norvig and Russel dedicate several pages to what factors allowed the industry to over come it's problems and the research that came about as a result:

Recent years have seen a revolution in both the content and the methodology of work in artificial intelligence. It is now more common to build on existing theories than to propose brand-new ones, to base claims on rigorous theorems or hard experimental evidence rather than on intuition, and to show relevance to real-world applications rather than toy examples.” (Artificial Intelligence : A Modern Approach.)

Computer vision, neural networks, machine learning and knowledge representation and reasoning (KRR) have made great strides in become practical in commercial environments. For example vision based systems can now fully map out and navigate their environments with strong recognition skills, as a result we now have self driving cars about to enter the commercial market. Ontological research, based around description logic, has provided very rich semantics to represent our world. Algorithms such as the tableaux algorithm have made it possible to effectively use those rich semantics in large complex ontologies. Early KRR systems, like Prolog in 5GP, were dogged by the limited semantic capabilities and memory restrictions on the size of those ontologies.

Knowledge Representation and Reasoning

In A Little History talks about AI as a broader subject and touches on Knowledge Representation and Reasoning (KRR) and also Expert Systems, I'll come back to Expert Systems later.
KRR is about how we represent our knowledge in symbolic form, i.e. how we describe something. Reasoning is about how we go about the act of thinking using this knowledge. System based languages, like Java or C+, have classification systems, called Classes, to be able to describe things, in Java we calls these things beans or instances. However those classification systems are limited to ensure computational efficiency. Over the years researchers have developed increasingly sophisticated ways to represent our world, many of you may already have heard of OWL (Web Ontology Language). Although there is always a gap between what we can be theoretically represented and what can be used computationally in practically timely manner, which is why OWL has different sub languages from Lite to Full. It is not believed that any reasoning system can support OWL Full. Although Each year algorithmic advances try and narrow that gap and improve expressiveness available to reasoning engines.

There are also many approaches to how these systems go about thinking. You may have heard of discussions comparing the merits of forward chaining, which is reactive and data driven, or backward chaining, which is passive and query driven. Many other types of reasoning techniques exists, each of which enlarges the scope of the problems we can tackle declaratively. To list just a few: imperfect reasoning (fuzzy logic, certainty factors), defeasible logic, belief systems, temporal reasoning and correlation. Don't worry if some of those words look alien to you, they aren't needed to understand Drools and are just there to give an idea of the range of scope of research topics; which is actually far more extensive than this small list and continues to grow as researches push new boundaries.

KRR is often refereed as the core of Artificial Intelligence Even when using biological approaches like neural networks, which model the brain and are more about pattern recognition than thinking, they still build on KRR theory. My first endeavours with Drools were engineering oriented, as I had no formal training or understanding of KRR. Learning KRR has allowed me to get a much wider theoretical background. Allowing me to better understand both what I've done and where I'm going, as it underpins nearly all of the theoretical side to our Drools R&D. It really is a vast and fascinating subject that will pay dividends for those that take the time learn, I know it did and still does for me. Bracham and Levesque have written a seminal piece of work, called "Knowledge Representation and Reasoning" that for anyone wanting to build strong foundations is a must read. I would also recommend the Russel and Norvig book "Artificial Intelligence, a modern approach" which also covers KRR.

Rule Engines and Production Rule Systems

We've now covered a brief history of AI and learnt that the core of AI is formed around KRR. We've shown than KRR is vast and fascinating subject which forms the bulk of the theory driving Drools R&D.
The rule engine is the computer program that delivers KRR functionality to the developer. At a high level it has three components:
  • Ontology
  • Rules
  • Data
As previous mentioned the ontology is the representation model we use for our "things". It could be a simple records or Java classes or full blown OWL based ontologies. The Rules do the reasoning and facilitate thinking. The distinction between rules and ontologies blurs a little with OWL based ontologies, who's richness is rule based.

The term rule engine is quite ambiguous in that it can be any system that uses rules, in any form, that can be applied to data to produce outcomes. This includes simple systems like form validation and dynamic expression engines. The book "How to Build a Business Rules Engine (2004)" by Malcolm Chisholm exemplifies this ambiguity. The book is actually about how to build and alter a database schema to hold validation rules. The book then shows how to generate VB code from those validation rules to validate data entry. Which while very valid, it is very different to what we talking about so far.

Drools started life as a specific type of rule engine called a production rule system (PRS) and was based around the Rete algorithm. The Rete algorithm, developed by Charles Forgey in 1979, forms the brain of a Production Rules System and is able to scale to a large number of rules and facts. A Production Rule is a two-part structure: the engine matches facts and data against Production Rules - also called Productions or just Rules - to infer conclusions which result in actions.
The process of matching the new or existing facts against Production Rules is called pattern matching, which is performed by the inference engine. Actions execute in response to changes in data, like a database trigger; we say this is a data driven approach to reasoning. The actions themselves can change data, which in turn could match against other rules causing them to fire; this is referred to asforward chaining

Drools implements and extends the Rete algorithm;. The Drools Rete implementation is called ReteOO, signifying that Drools has an enhanced and optimized implementation of the Rete algorithm for object oriented systems. Our more recent work goes well beyond Rete. Other Rete based engines also have marketing terms for their proprietary enhancements to Rete, like RetePlus and Rete III. Th e most common enhancements are covered in "Production Matching for Large Learning Systems (Rete/UL)" (1995) by Robert B. Doorenbos. Leaps used to be provided but was retired as it became unmaintained, the good news is our research is close to producing an algorithm that merges the benefits of Leaps with Rete.

The Rules are stored in the Production Memory and the facts that the Inference Engine matches against are kept in the Working Memory. Facts are asserted into the Working Memory where they may then be modified or retracted. A system with a large number of rules and facts may result in many rules being true for the same fact assertion; these rules are said to be in conflict. The Agenda manages the execution order of these conflicting rules using a Conflict Resolution strategy.

Hybrid Reasoning Systems

You may have read discussions comparing the merits of forward chaining (reactive and data driven) or backward chaining(passive query). Here is a quick explanation of these two main types of reasoning.

Forward chaining is "data-driven" and thus reactionary, with facts being asserted into working memory, which results in one or more rules being concurrently true and scheduled for execution by the Agenda. In short, we start with a fact, it propagates and we end in a conclusion.

Backward chaining is "goal-driven", meaning that we start with a conclusion which the engine tries to satisfy. If it can't it then searches for conclusions that it can satisfy; these are known as subgoals, that will help satisfy some unknown part of the current goal. It continues this process until either the initial conclusion is proven or there are no more subgoals. Prolog is an example of a Backward Chaining engine. Drools can also do backward chaining, which we refer to as derivation queries.

Historically you would have to make a choice between systems like OPS5 (forward) or Prolog (backward). Now many modern systems provide both types of reasoning capabilities. There are also many other types of reasoning techniques, each of which enlarges the scope of the problems we can tackle declaratively. To list just a few: imperfect reasoning (fuzzy logic, certainty factors), defeasible logic, belief systems, temporal reasoning and correlation. Modern systems are merging these capabilities, and others not listed, to create hybrid reasoning systems (HRS).

While Drools started out as a PRS, 5.x introduced Prolog style backward chaining reasoning as well as some functional programming styles. For this reason HRS is now the preferred term when referring to Drools, and what it is.

Drools current provides crisp reasoning, but imperfect reasoning is almost ready. Initially this will be imperfect reasoning with fuzzy logic, later we'll add support for other types of uncertainty. Work is also under way to bring OWL based ontological reasoning, which will integrate with our traits system. We also continue to improve our functional programming capabilities.

Expert Systems  

You will often hear the terms expert systems used to refer to production rule systems or Prolog like systems. While this is normally acceptable, it's technically wrong as these are frameworks to build expert systems with, and not actually expert systems themselves. It becomes an expert system once there is an ontological model to represent the domain and there are facilities for knowledge acquisition and explanation.

Mycin is the most famous expert system, built during the 70s. It is still heavily covered in academic literature, such as the recommended book "Expert Systems" by Peter Jackson.

Recommended Reading

General AI, KRR and Expert System Books

For those wanting to get a strong theoretical background in KRR and expert systems, I'd strongly recommend the following books. "Artificial Intelligence: A Modern Approach" is must have, for anyone's bookshelf.
  • Introduction to Expert Systems
    • Peter Jackson
  • Expert Systems: Principles and Programming
    • Joseph C. Giarratano, Gary D. Riley
  • Knowledge Representation and Reasoning
    • Ronald J. Brachman, Hector J. Levesque
  • Artificial Intelligence : A Modern Approach.
    • Stuart Russell and Peter Norvig


Here are some recommended papers that cover some interesting areas in rule engine research.
  • Production Matching for Large Learning Systems : Rete/UL (1993)
    • Robert B. Doorenbos
  • Advances In Rete Pattern Matching
    • Marshall Schor, Timothy P. Daly, Ho Soo Lee, Beth R. Tibbitts (AAAI 1986)
  • Collection-Oriented Match
    • Anurag Acharya and Milind Tambe (1993)
  • The Leaps Algorithm (1990)
    • Don Battery
  • Gator: An Optimized Discrimination Network for Active Database Rule Condition Testing (1993)
    • Eric Hanson , Mohammed S. Hasan

Drools Books

There are currently three Drools books, all from Packt Publishing.
  • JBoss Drools Business Rules
    • Paul Brown
  • Drools JBoss Rules 5.0 Developers Guide
    • Michali Bali
  • Drools Developer's Cookbook
    • Lucas Amador

If you like the article, please vote up ad dzone:



  1. Great Post Mark, I was really hoping from Drools Community.

    Great Post, Great Work

  2. How does Drools relate to LISP? I would have expected a post on AI to mention LISP at least once!

  3. Drools is Hybrid Reasoning System, with a Production Rule System lineage. These systems come with out of the box support for various types of reasoning capabilities.

    Lisp is just a language, that supports a functional and declarative programming styles. It is not an engine and has no "out of the box" reasoning capabilities. However you can build those things ontop of Lisp.

  4. What are advantages/disadvantages of using inference engine of Drools compared to a datalog program (ex. IRIS, Quantitative datalog@

  5. really nice article, but a bit hard to understand for me. AI is a very interesting thing, but i guess i need to find some books for beginners in this topic.

  6. "What are advantages/disadvantages of using inference engine of Drools compared to a datalog program (ex. IRIS, Quantitative datalog@"

    Datalog is query only, so it's a passive system. Drools is both query based and reactive based. Reactive is more like a trigger on a view in a database.

    Further still Drools can do transititive closures over a graph, like datalog, but we can materialize those as a view. What this means is the query stays "open" and you'll continue to receive new results as the underlying data changes, thus we have a reactive transitive closure. Datalog systems would have to re-poll, executing the entire graph again, to see if there any new results.

    We allow our reactive rules to query and join with the results a query, making it fully hybrid.

  7. "really nice article, but a bit hard to understand for me. AI is a very interesting thing, but i guess i need to find some books for beginners in this topic."

    It's heavy subject indeed, because it's so large and it's difficult to understand what each area means and how it all fits together. When writting this article the hardest bit was to avoid introducing new jargon to explain the concepts; because it would just be another word the end user doesn't understand, this was much harder than I expected. i.e. if I started off with "drools is a production rule system that allows the use of propositional and first order logic", people are going to ask what "propositional" and "first order" logic is. I'd then spend more time explaining the jargaon, than the problem :)

    I'll try and improve it over time. However the books I recommend, do a far better job than I ever could.

  8. An interesting approach that I've been working on is that the output of Machine Learning algorithms (such as neural networks) can be represented in PMML (predictive model markup language) and executed by a scoring service. Drools can call the scoring service in making decisions.

  9. Thanks Mark.
    Good introduction but I think it needs a little review.
    It's a little hard for beginners to understand the whole article.

  10. Thanks for Sharing a useful content about Artificial Intelligence
    Please visit our website At SFJ Business Solutions we to shared some blogs about AI
    AI online course

  11. This course offers you get practical, hands-on experience to ensure hassle-free execution of real-life projects. artificial intelligence training in pune

  12. Thank you for sharing . really impressed to read about this article
    onbee store for online store

  13. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. machine learning projects for final year In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.

    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

  14. They are not perfectly artificially intelligent because we get to remember that it is a computing system along the process somewhere else. artificial intelligence training in hyderabad

  15. Very good points you wrote here..Great stuff...I think you've made some truly interesting points.Keep up the good work.


  16. Data Science Course Training in Hyderabad

    Data Science Training in Hyderabad, Data Science Course in Hyderabad, Data Science Training, Data Science Course, Data Science Institute, Data Science Certification

    Data Science Course in Hyderabad

    Data Science Training in Hyderabad
    Data Science Course Training in Hyderabad

    Advanced-Data science training with Free Internship & 100% Placement Assistance

    About the Data Science course Training in Hyderabad

    Data is everywhere, which is growing exponentially globally, and this may still grow at an accelerating rate for the foreseeable future. Businesses generate massive amounts of data within the type of blogs, messages, transaction documents, mobile device data, social media, etc. By using this data effectively, a firm can create vital value and grow their economy by enhancing productivity, increasing efficiency, and delivering more value to consumers.

    Data Science helps in combining the disruption into categories and communicating their potential, which allows data and analytics leaders to drive better results. Top businesses thought there is a necessity to research the data for significant benefits. They use the insights from data for the advantage of users.

    Human deciding is becoming increasingly inadequate to pander to a never-ending expansion of the data . However, Data Science and Machine Learning are excelling in solving highly complex data-rich problems. To think beyond the human brain and maintain the balance with the knowledge that's evolved, disrupted, and being employed the sectors altogether, data scientists foster new methodologies. Data scientists must try 'big data expeditions' to explore the data for previously undiscovered value - the first common application of data science. Typical applications include marketing segmentation, advertising, tweaking dynamic pricing models, or banks finding risks and adjusting the financial risk models.

    What are the Tools utilized in Data Science?

  17. Why you should opt for an online course in digital marketing data science course syllabus

  18. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
    data science course in India

  19. Thanks For sharing a nice post about Course.It is very helpful and useful for science courses

  20. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
    Artificial Intelligence Course

  21. keep up the good work. this is an Ossam post. This is to helpful, i have read here all post. i am impressed. thank you. this is our site please visit to know more information
    data science training in Hyderabad

  22. Python is a dynamic and object-oriented programming language, widely used for web application development. 90% of people prefer Python over other technology because of its simplicity, reliability and easy interfacing. data science course in india

  23. Thanks for posting the best information and the blog is very interesting.Data science course in Faridabad