view release on metacpan or  search on metacpan

lib/AI/ExpertSystem/Advanced.pm  view on Meta::CPAN

#
# AI::ExpertSystem::Advanced
#
# Author(s): Pablo Fischer (pfischer@cpan.org)
# Created: 11/29/2009 18:28:30 CST 18:28:30
package AI::ExpertSystem::Advanced;

=head1 NAME

AI::ExpertSystem::Advanced - Expert System with backward, forward and mixed algorithms

=head1 DESCRIPTION

Inspired in L<AI::ExpertSystem::Simple> but with additional features:

=over 4

=item *

Uses backward, forward and mixed algorithms.

=item *

Offers different views, so user can interact with the expert system via a
terminal or with a friendly user interface.

=item *

The knowledge database can be stored in any format such as YAML, XML or
databases. You just need to choose what driver to use and you are done.

=item *

Uses certainty factors.

=back

=head1 SYNOPSIS

An example of the mixed algorithm:

    use AI::ExpertSystem::Advanced;
    use AI::ExpertSystem::Advanced::KnowledgeDB::Factory;

    my $yaml_kdb = AI::ExpertSystem::Advanced::KnowledgeDB::Factory->new('yaml',
        {
            filename => 'examples/knowledge_db_one.yaml'
        });

    my $ai = AI::ExpertSystem::Advanced->new(
            viewer_class => 'terminal',
            knowledge_db => $yaml_kdb,
            initial_facts => ['I'],
            verbose => 1);
    $ai->mixed();
    $ai->summary();

=cut
use Moose;
use AI::ExpertSystem::Advanced::KnowledgeDB::Base;
use AI::ExpertSystem::Advanced::Viewer::Base;
use AI::ExpertSystem::Advanced::Viewer::Factory;
use AI::ExpertSystem::Advanced::Dictionary;
use Time::HiRes qw(gettimeofday);
use YAML::Syck qw(Dump);

our $VERSION = '0.03';

=head1 Attributes

=over 4

=item B<initial_facts>

A list/set of initial facts the algorithms start using.

During the forward algorithm the task is to find a list of goals caused
by these initial facts (the only data we have in that moment).

Lets imagine your knowledge database is about symptoms and diseases. You need
to find what diseases are caused by the symptoms of a patient, these first
symptons are the initial facts.

Initial facts as also asked and inference facts can be negative or positive. By
default the initial facts are positive.

Keep in mind that the data contained in this array can be the IDs or the name
of the fact.

This array will be converted to L<initial_facts_dict>. And all the data (ids or
or names) will be made of only IDs.

    my $ai = AI::ExpertSystem::Advanced->new(
            viewer_class => 'terminal',
            knowledge_db => $yaml_kdb,
            initial_facts => ['I', ['F', '-'], ['G', '+']);

As you can see if you want to provide the sign of a fact, just I<encapsulate>
it in an array, the first item should be the fact and the second one the
sign.

=cut
has 'initial_facts' => (
        is => 'rw',
        isa => 'ArrayRef[Str]',
        default => sub { return []; });

=item B<initial_facts_dict>

This dictionary (see L<AI::ExpertSystem::Advanced::Dictionary> has the sasme
data of L<initial_facts> but with the additional feature(s) of proviing
iterators and a quick way to find elements.

=cut
has 'initial_facts_dict' => (
        is => 'ro',
        isa => 'AI::ExpertSystem::Advanced::Dictionary');

=item B<goals_to_check>

    my $ai = AI::ExpertSystem::Advanced->new(
            viewer_class => 'terminal',
            knowledge_db => $yaml_kdb,
            goals_to_check => ['J']);

When doing the L<backward()> algorithm it's required to have at least one goal
(aka hypothesis).

This could be pretty similar to L<initial_facts>, with the difference that the
initial facts are used more with the causes of the rules and this one with
the goals (usually one in a well defined knowledge database).

The same rule of L<initial_facts> apply here, you can provide the sign of the
facts and you can provide the id or the name of them.

From our example of symptoms and diseases lets imagine we have the hypothesis
that a patient has flu, we don't know the symptoms it has, we want the
expert system to keep asking us for them to make sure that our hypothesis
is correct (or incorrect in case there's not enough information).

=cut
has 'goals_to_check' => (
        is => 'rw',
        isa => 'ArrayRef[Str]',
        default => sub { return []; });

=item B<goals_to_check_dict>

Very similar to L<goals_to_check> (and indeed of L<initial_facts_dict>). We
want to make the job easier.

It will be a dictionary made of the data of L<goals_to_check>.

=cut
has 'goals_to_check_dict' => (
        is => 'ro',
        isa => 'AI::ExpertSystem::Advanced::Dictionary');

=item B<inference_facts>

Inference facts are basically the core of an expert system. These are facts
that are found and copied when a set of facts (initial, inference or asked)
match with the causes of a goal.

L<inference_facts> is a L<AI::ExpertSystem::Advanced::Dictionary>, it will
store the name of the fact, the rule that caused these facts to be copied to
this dictionary, the sign and the algorithm that triggered it.

=cut
has 'inference_facts' => (
        is => 'ro',
        isa => 'AI::ExpertSystem::Advanced::Dictionary');
       
=item B<knowledge_db>

The object reference of the knowledge database L<AI::ExpertSystem::Advanced> is
using.

=cut
has 'knowledge_db' => (
        is => 'rw',
        isa => 'AI::ExpertSystem::Advanced::KnowledgeDB::Base',
        required => 1);

=item B<asked_facts>

During the L<backward()> algorithm there will be cases when there's no clarity
if a fact exists. In these cases the L<backward()> will be asking the user
(via automation or real questions) if a fact exists.

Going back to the L<initial_facts> example of symptoms and diseases. Imagine
the algorithm is checking a rule, some of the facts of the rule make a match
with the ones of L<initial_facts> or L<inference_facts> but some wont, for
these I<unsure> facts the L<backward()> will ask the user if a symptom (a fact)
exists. All these asked facts will be stored here.

=cut
has 'asked_facts' => (
        is => 'ro',
        isa => 'AI::ExpertSystem::Advanced::Dictionary');

=item B<visited_rules>

Keeps a record of all the rules the algorithms have visited and also the number
of causes each rule has.

=cut
has 'visited_rules' => (
        is => 'ro',
        isa => 'AI::ExpertSystem::Advanced::Dictionary');

=item B<verbose>

    my $ai = AI::ExpertSystem::Advanced->new(
            viewer_class => 'terminal',
            knowledge_db => $yaml_kdb,
            initial_facts => ['I'],
            verbose => 1);

By default this is turned off. If you want to know what happens behind the
scenes turn this on.

Everything that needs to be debugged will be passed to the L<debug()> method
of your L<viewer>.

=cut
has 'verbose' => (
        is => 'rw',
        isa => 'Bool',
        default => 0);

=item B<viewer>

Is the object L<AI::ExpertSystem::Advanced> will be using for printing what is
happening and for interacting with the user (such as asking the
L<asked_facts>).

This is practical if you want to use a viewer object that is not provided by
L<AI::ExpertSystem::Advanced::Viewer::Factory>.

=cut
has 'viewer' => (
        is => 'rw',
        isa => 'AI::ExpertSystem::Advanced::Viewer::Base');

=item B<viewer_class>

Is the the class name of the L<viewer>.

You can decide to use the viewers L<AI::ExpertSystem::Advanced::Viewer::Factory>
offers, in this case you can pass the object or only the name of your favorite
viewer.

=cut
has 'viewer_class' => (
        is => 'rw',
        isa => 'Str',
        default => 'terminal');

=item B<found_factor>

In your knowledge database you can give different I<weights> to the facts of
each rule (eg to define what facts have more I<priority>). During the
L<mixed()> algorithm it will be checking what causes are found in the
L<inference_facts> and in the L<asked_facts> dictionaries, then the total
number of matches (or total number of certainity factors of each rule) will
be compared versus the value of this factor, if it's higher or equal then the
rule will be triggered.

You can read the documentation of the L<mixed()> algorithm to know the two
ways this factor can be used.

=cut
has 'found_factor' => (
        is => 'rw',
        isa => 'Num',
        default => '0.5');

=item B<shot_rules>

All the rules that are shot are stored here. This is a hash, the key of each
item is the rule id while its value is the precision time when the rule was
shot.

The precision time is useful for knowing when a rule was shot and based on that
you can know what steps it followed so you can compare (or reproduce) them.

=back

=cut
has 'shot_rules' => (
        is => 'ro',
        isa => 'HashRef[Str]');

=head1 Constants

=over 4

=item * B<FACT_SIGN_NEGATIVE>

Used when a fact is negative, aka, a fact doesn't happen.

=cut
use constant FACT_SIGN_NEGATIVE => '-';

=item * B<FACT_SIGN_POSITIVE>

Used for those facts that happen.

=cut
use constant FACT_SIGN_POSITIVE => '+';

=item * B<FACT_SIGN_UNSURE>

Used when there's no straight answer of a fact, eg, we don't know if an answer
will change the result.

=back

=cut
use constant FACT_SIGN_UNSURE   => '~';

lib/AI/ExpertSystem/Advanced.pm  view on Meta::CPAN

            last;
        }

        $self->{'viewer'}->debug("Checking rule: $current_rule") if
            $self->{'verbose'};
        
        if ($self->is_rule_shot($current_rule)) {
            $self->{'viewer'}->debug("We already shot rule: $current_rule")
                if $self->{'verbose'};
            next;
        }

        $self->{'viewer'}->debug("Reading rule $current_rule")
            if $self->{'verbose'};
        $self->{'viewer'}->debug("More rules to check, checking...")
            if $self->{'verbose'};

        my $rule_causes = $self->get_causes_by_rule($current_rule);
        # any of our rule facts match with our facts to check?
        if ($self->compare_causes_with_facts($current_rule)) {
            # shoot and start again
            $self->shoot($current_rule, 'forward');
            # Undef to start reading from the first rule.
            $current_rule = undef;
            next;
        }
    }
    return 1;
}

=head2 B<backward()>

    use AI::ExpertSystem::Advanced;
    use AI::ExpertSystem::Advanced::KnowledgeDB::Factory;

    my $yaml_kdb = AI::ExpertSystem::Advanced::KnowledgeDB::Factory->new('yaml',
        {
            filename => 'examples/knowledge_db_one.yaml'
            });

    my $ai = AI::ExpertSystem::Advanced->new(
            viewer_class => 'terminal',
            knowledge_db => $yaml_kdb,
            goals_to_check => ['J']);
    $ai->backward();
    $ai->summary();

The backward algorithm starts with a set of I<assumed> goals (facts). It will
start reading goal by goal. For each goal it will check if it exists in the
initial, inference and asked facts (see L<is_goal_in_our_facts()>) for more
information).

=over 4

=item *

If the goal exist then it will be removed from the dictionary, it will also
verify if there are more visited rules to shoot.

If there are still more visited rules to shoot then it will check from what
rule the goal comes from, if it was copied from a rule then this data will
exist. With this information then it will see how many of the causes of this
given rule are still in the L<goals_to_check_dict>.

In case there are still causes of this rule in L<goals_to_check_dict> then the
amount of causes pending will be reduced by one. Otherwise (if the amount is
0) then the rule of this last removed goal will be shoot.

=item *

If the goal doesn't exist in the mentioned facts then the goal will be searched
in the goals of every rule.

In case it finds the rule that has the goal, this rule will be marked (added)
to the list of visited rules (L<visited_rules>) and also all of its causes
will be added to the top of the L<goals_to_check_dict> and it will start
reading again all the goals.

If there's the case where the goal doesn't exist as a goal in the rules then
it will ask the user (via L<ask_about()>) for the existence of it. If user is
not sure about it then the algorithm ends.

=back

=cut
sub backward {
    my ($self) = @_;

    my ($more_goals, $current_goal, $total_goals) = (
            1,
            0,
            scalar(@{$self->{'goals_to_check'}}));
    
    WAIT_FOR_MORE_GOALS: while($more_goals) {
        READ_GOAL: while(my $goal = $self->{'goals_to_check_dict'}->iterate) {
            if ($self->is_goal_in_our_facts($goal)) {
                $self->{'viewer'}->debug("The goal $goal is in our facts")
                    if $self->{'debug'};
                # Matches with any visiited rule?
                my $rule_no = $self->{'goals_to_check_dict'}->get_value(
                        $goal, 'rule');
                # Take out this goal so we don't end with an infinite loop
                $self->{'viwer'}->debug("Removing $goal from goals to check")
                    if $self->{'debug'};
                $self->{'goals_to_check_dict'}->remove($goal);
                # Update the iterator
                $self->{'goals_to_check_dict'}->populate_iterable_array();
                # no more goals, what about rules?  
                if ($self->{'visited_rules'}->size() eq 0) {
                    $self->{'viewer'}->debug("No more goals to read")
                        if $self->{'verbose'};
                    $more_goals = 0;
                    next WAIT_FOR_MORE_GOALS;
                }
                if (defined $rule_no) {
                    my $causes_total = $self->{'visited_rules'}->get_value(
                            $rule_no, 'causes_total');
                    my $causes_pending = $self->{'visited_rules'}->get_value(
                            $rule_no, 'causes_pending');
                    if (defined $causes_total and defined $causes_pending) {
                        # No more pending causes for this rule, lets shoot it