I knew it!

Which Programming Language are You?

MongoDB Presentation

Hi,

today I had the honor to make a presentation with Brunno Gommes (@brunnogomes) about MongoDB on a Workshop (actually the second) of Free Software at CIn-UFPE. The workshop was organized by the University Linux User Group (CIn-LUG).

The content of the presentation was to introduce people to MongoDB basic operations and give a snapshot of the advanced features. To those who don't know MongoDB I strongly recommend to start to reading the presentation. Probably I will talk more about it here on the Codecereal.

Anyway, I'm publishing my presentation here, so enjoy it:

Mongodb workshop cinlug

View more presentations from Daker Fernandes.

DiagnostiCar (4) - Abductive Reasoning

Hi,

finally I had some time to write about abductive reasoning, the core of the DiagnostiCar expert system. As you may know from my previous posts (means you're tough and reached this point :P), the abductive reasoning tries to infer what facts implies a given situation.

To build such a reasoning we must start with the conclusion and try to prove it. Let's say that we have the following scenario:

known mortal(X) <- human(X).

known human(socrates).

How abductive reasoning behaves when tries to find out what things are mortal?

The first step is to check if mortal(X) is a tautology such as:

known mortal(xerxes).

As in our example there isn't such tautology the reasoning agent must try to find a rule which implies that something is mortal. In our case proceeds that mortal(X) <- human(X) so to prove that something is mortal we have to prove that it is human. The first step is then repeated and we reach the tautology human(socrates) which asserts that Socrates is mortal.

Note that we have no difference with we try to use Prolog directly:

mortal(X) :-
    human(X).

human(socrates).

Now consider a non trivial example. Imagine that we want to prove that mortal(aristoteles) but we may let the reasoner conclude that such affirmation is only possible if Aristoteles is a human. Pretty smart huh? That's what abductive reasoning is capable of. To build such a predicate we will need to know not only what are proving but also the user id (to ask questions when possible) and a list to yield what is being assumed.

Now lets try to prove a goal using the following rules (together with the Prolog code):

1 - Check if the goal is a tautology:

abduction(_, Goal, _) :-
    known(Goal).

2 - Check equalities:

abduction(_, Value == Value, _) :-
    Value = Value.

abduction(_, Value \= Value, _) :-
    Value \= Value.

3 - Check if the goal is implied by something else:

abduction(Uid, Goal, Assuming) :-
    known(Goal <- Cause),
    abduction(Uid, Cause, Assuming).

4 - If the goal is an or or an and conjunction:

abduction(Uid, Left & Right, Assuming) :-
    abduction(Uid, Left, Assuming),
    abduction(Uid, Right, Assuming).

abduction(Uid, Left v _, Assuming) :-
    abduction(Uid, Left, Assuming).

abduction(Uid,_ v Right,Assuming) :-
    abduction(Uid, Right, Assuming).

5 - Ask the user:

abduction(Uid, Goal, _) :-
    functor(Goal,Question,1), 
    askable(Question),
    arg(1,Goal,Answer),
    ask(Uid,Question,Answer). % Defined in a previous post

6 - Make an assumption:

abduction(_, Goal, Assuming) :-
    assumable(Goal),
    member(Goal, Assuming).
    % Says that the goal must be assumed to reach the goal.

This does it's task but we still have some problems. The first one is the lack of constraints. This reasoning doesn't consider if you assume something that implies in a contradiction. e.g.: known false <- mortal(X) & immortal(X). Another problem we can observe is that the system doesn't follow the Occam's razor principle, which affirms that between two valid explanation the simplest tends to be true. Finally we have a crucial problem is a infinite loop occurence when you try to prove the negation of something and the goal is a tautology.

Let's solve those problems by parts. The first can be solved with a predicate which proves the goal and doesn't reach a contradiction at the same time:

reason(Uid, Goal, Assuming) :-
    abductive_reasoning(Uid, Goal, Assuming),
    not(abductive_reasoning(Uid, false, Assuming)).

But that predicate falls directly to the third problem. To solve this problem, the must intuitive solution is do a search starting with a empty list of assumptions and try incrementing the list size until it reachs a cutoff that you may assume that there is no explanation bigger than that. A simple and clear implementation of that would be:

max_assumptions(5).
abductive_reasoning(Uid, Goal, Assuming) :-
    max_assumptions(Max),
    abduction(Uid, Goal, Assuming, Max).

abduction(Uid, Goal, Assuming, Depth) :-
    Depth >= 0,
    max_assumptions(Max),
    Len is Max - Depth,
    length(Assuming, Len),
    abduction(Uid, Goal, Assuming).

abduction(Uid, Goal, Assuming, Depth) :-
    NextStep is Depth - 1,
    NextStep >= 0,
    abduction(Uid, Goal, Assuming, NextStep).

It is not the most efficient code to handle code but works fine. You can avoid process a search path again by creating a dynamic predicate and asserting when a branch of the search is truth or false. It may use a lot of memory but it helps to execute faster.

DiagnostiCar (3) - Question & Answer Interface

This post aims to explain how to create an interactive shell so that users may answer questions when the reasoning system need user information. The reasoning engine will access the ask engine by an predicate (I will call it ask). An naive implementation of the ask predicate could be:

ask(X) :-
 write(X), write(' is true?'), nl,
 read(yes).

It works, but askable predicates will be asked every time the reasoner will need an information, even if it was previously answered. Another specific problem from DiagnostiCar constraints, was how to separate which information is from which user, considering we're at an web application environment. The simultaneous users access to the reasoning engine couldn't simply be locked while an user was giving an answer back, so we must find a smarter way to ask.

To remember info in Prolog, we will need to use dynamic relations to store the asked questions, for those who don't know about dynamic relations I will give a short explanation. If you want to know more, read the "Building Expert Systems in Prolog"[1] book.

Dynamic relations works similarly as a relational table in a relational database [2], but without a type scheme (although it's strongly recommended to make a convention). The informations required to create a dynamic relation are just it's name and arity. To declare a dynamic predicate you just need to run dynamic(Predicate). Once the relation is a dynamic one, you can store information (assert/1 or asserta/1) or delete information (use retract/1 and retractall/1) eg.: assert(foo(bar)). To query a dynamic predicate you just have to call it (it allows unification!) eg.: ?- foo(bar).  -> true. I made the following basic but illustrative example about Prolog DB:

create_account(Id, Ammount) :-
    assert(account(Id, Ammount)).
    
deposit(Id, Ammount) :-
    retract(account(Id, PrevAmmount)),
    NewAmmount is Ammount + PrevAmmount,
    assert(account(Id, NewAmmount)).
    
withdraw(Id, Ammount) :-
    account(Id, PrevAmmount),
    PrevAmmount >= Ammount,
    retract(account(Id, PrevAmmount)),
    NewAmmount is PrevAmmount - Ammount,
    assert(account(Id, NewAmmount)).

To test the predicates do some queries:

?- create_account(1, 1000).
true.

?- deposit(1, 200).
true.

?- account(Id, Ammount).
Id = 1,
Ammount = 1200.

?- withdraw(1, 400).
true.

?- withdraw(1, 20000).
false.

?- account(Id, Ammount).
Id = 1,
Ammount = 800.

The best solution found, to solve the concurrence and the question tracking, was to create predicates to read and write, so the webapp could obtain such information from the expert system. To avoid repeating the same questions, we will have to maintain a table with questions made, one with the answered questions and another to keep the answers from the users. Note that each relation needs to keep an user id to know from which user each information belongs to. The expert system question interface is the following:

% asked: UserId | Question
:- dynamic asked/2.
% asked: UserId | Question
:- dynamic askfor/2.
% known: UserId | Question | Fact
:- dynamic known/3.

% Predicate used by the expert system to ask.
ask(Uid, Question, Answer) :-
    known(Uid, Question, Answer).
ask(Uid, Question, _ ) :-
    not(asked(Uid,Question)),
    not(askfor(Uid,Question)),
    assert(askfor(Uid, Question)),
    fail.

% Predicate used by the web app to input users answers for a given qeustion.
answer(Uid, Question, [Answer | Answers]) :-
    assert(known(Uid, Question, Answer)),
    answer(Uid, Question, Answers).
answer(Uid, Question, []) :-
    assert(asked(Uid, Question)),
    retractall(askfor(Uid,Question)).

% Routine called by the webapp to clean the data from a user whose 
% session was expired.
cleanup(Uid) :-
    retractall(askfor(Uid,_)),
    retractall(known(Uid,_,_)),
    retractall(asked(Uid,_)).

Not that hard! I will try to tell all about the abductive reasoning on the next post.

[1] "Building Expert Systems in Prolog"

[2] SWI Database

DiagnostiCar (2) - Knowledge Representation Language

I'm giving sequence to the last post about the DiagnostiCar expert system. Today I'm going to specify the predicates to represent some domain specific knowledge.

Prolog has a helpful and clean syntax [1] (at least when you're used to :P) and it's easy to define new operators syntax in SWI [2]. Such feature improves the readability of the knowledge base.

To make an abductive reasoning we will need at least the logic operators 'and','or' and 'implies' to represent knowledge and chain it.

Our simple language will have the following syntax:

• known X. - Says that the sentence X must be true;
• X <- Y - X is caused by Y;
• X & Y - Is true if X and Y are true;
• X v Y - Is true if X or Y are true ('|' is already used by Prolog);
• assumable X - X can be assumed to prove something;
• askable X - X can be asked to the user;

Note that I'm not using the negation, because some dangerous particularities of Prolog negation as failure.

It's interesting to note the similarity if we represented with the defaul prefixed notation of Prolog predicades:

- known(X)
- <-(X,Y)
- &(X,Y)
- v(X,Y)
- assumable(X)
- askable(X)

Defining opertors increases the readabilty of the knowledge representation significantly. To redefine operators we will use the SWI predicate op/3 [2]. We can only run this predicate like:

:- op(910, xfy, &).

The op predicate has three fields op(+Precedence, +Type, :Name). The first one says the precendence of the operator (a number between 0 and 1200). The second is how the functor will be placed within it's "children nodes", for example: xfy let the functor between the arguments while xf let the functor after it's argument (remembering that you can only create unary or binary operators). For our representation language we will have:

:- discontiguous(     known/1 ). % The discontiguous predicate tells Prolog
:- discontiguous( assumable/1 ). % that the given predicate can be declared
:- discontiguous(   askable/1 ). % unsorted.

:- op(910, xfy,      &    ). % a higher priority with an infix notation
:- op(920, xfy,      v    ). % infix notation and lower priority than &
:- op(930, xfy,     <-    ). % infix notation
:- op(940,  fx,   known   ). % prefixed notation and lowest priority
:- op(940,  fx, assumable ). % prefixed notation and lowest priority
:- op(940,  fx,   askable ). % prefixed notation and lowest priority

Now let's model the car problems knowledge into our language (remember that Upper names are variables):

%
% DiagnostiCar - Knowledge Base
%

% Observe that implication is seen as the real sense of consequence <- cause.
known problem(crank_case_damaged) <- crank_case_damaged.
known problem(hydraulic_res_damaged) <- hydraulic_res_damaged.
known problem(brakes_res_damaged) <- brakes_res_damaged.
known problem(old_engine_oil) <- old_engine_oil & leak_color(black).

known leak(engine_oil) <- crank_case_damaged.
known leak(hydraulic_oil) <- hydraulic_res_damaged.
known leak(brakes_oil) <- brakes_res_damaged.

% Implications in false can be seen as constraints.
known oil(Oil) <- exists_leak(true) & leak(Oil).
known false <- oil(brakes_oil) & leak_color(Color) & Color \= green. 
known false <- oil(engine_oil) & leak_color(Color) & Color \= brown & Color \= black.
known false <- oil(hydraulic_oil) & leak_color(Color) & Color \= red.

% The assumable predicate asserts what will be can be suposed 
assumable crank_case_damaged.    
assumable hydraulic_res_damaged. % to prove something e else.
assumable brakes_res_damaged.
assumable old_engine_oil.

askable leak_color(Color). % Askable predicate asserts which information will be asked for the user.
askable exists_leak(TrueOrFalse). % The argument of the predicate will be unified with the answer.

known goal(X) <- problem(X). % The goal predicate is what we want to prove with the expert system.

That's all for now. On the next post I will explain the question and answer interface using the dynamic Prolog predicates.

[1] Prolog Syntax

[2] Prolog 'operator/3' documentation

DiagnostiCar (1) - Introduction

I'm here to tell my expirience with logic programming on a graduation project - DiagnostiCar.

The DiagnostiCar core feature was an expert system for giving hints to laypeople about their cars symptoms and their causes and consequences to avoid being deceived by mechanics (an habit of the job). Communication between the system and the users was conceived to happen with multiple choice questions forms and at the end the system gives the possible causes for the observed car characteristics.

This is a video of the DiagnostiCar expert system interface working:



Although there are many other interesting aspects about the DiagnostiCar, let's focus on the shell system. The expert system reasoning system used was abductive reasoning which is a kind of reasoning that tries to find a plausible cause (or a set of them) for a given fact occurrence [1][2]. Find the causes for a given observation is exactly what we need for diagnose car problems (the cause of the observable symptoms).

I choose to use Prolog not only because it's default support to first-order logic (although some logic limitations on negation [3]), but it has a nice support for pattern matching and syntax operator definition (most of the Prolog implementations). From the Prolog implementations I've picked SWI Prolog due to it's multi-thread support (necessary for a system running on a multiple user environment), stability and speed (not as fast as the YAP) [4].

To illustrate the process of development of the expert system we will restrict our diagnosis to the problems consisting of some oil leaks problem. Here are some of the knowledge about car diagnosis I will use as example in the next sections:

• A crank case, hydraulic oil reservoir and brakes fluid reservoir damaged are problems;
• The crank case damaged provokes leak of engine oil;
• The hydraulic reservoir damaged provokes leak of hydraulic system oil;
• The brakes fluid reservoir damaged provokes leak of engine oil; 
• If an oil is leaking it dirts the garage's floor.
• The brakes fluid is green.
• The hydraulic oil is red.
• The engine oil is black or brown.
• If the engine oil is black, then it needs to be changed.

For the next parts, it's good to know the basic about Prolog. A VERY good material about Prolog, it's a the book "Building Expert Systems in Prolog"[5] which guided through the realms of logic programming and the nasty api's documentations. It is also very pratical and full of examples to follow. It's also good see the SWI reference to check some SWI particularities[6].

[1] Abductive Logic Programming
[2] Abducive Reasoning
[3] Prolog Negation as Failure
[4] Prologs Implementation Comparisons
[5] "Building Expert Systems in Prolog"
[6] SWI Manual

First Post

Spock says lambda, lambda, lambda to CodeCereal: