Prolog in AI

What is Prolog?

  • Prolog stands for Programming in logic. It is used in artificial intelligence programming.
  • Prolog is a declarative programming language.
    For example: While implementing the solution for a given problem, instead of specifying the ways to achieve a certain goal in a specific situation, user needs to specify about the situation (rules and facts) and the goal (query). After these stages, Prolog interpreter derives the solution.
  • Prolog is useful in AI, NLP, databases but useless in other areas such as graphics or numerical algorithms.

Prolog facts

  • A fact is something that seems to be true.
    For example: It's raining.
  • In Prolog, facts are used to form the statements. Facts consist of a specific item or relation between two or more items.

How to convert English to prolog facts using facts and rules?

It is very simple to convert English sentence into Prolog facts. Some examples are explained in the following table.

English StatementsProlog Facts
Dog is barkingbarking(dog)
Jaya likes food if it is delicious.likes( Jaya, Food):-delicious(Food)

In the above table, the statement 'Dog is barking' is a fact, while the statement 'Jaya likes food if it is delicious' is called rule. In this statement, variable like 'Food' has a first letter in capital, because its value came from previous fact. The symbol ':-' is used to denote that “Jaya likes delicious food”.

Arithmetic Operations in Prolog

  • Prolog provides the facility for arithmetic operations.
  • As per the requirement of the user, arithmetic operations can be divided into some special purpose integer predicates and a series of general predicates for integer, floating point and rational arithmetic.
  • The general arithmetic predicates are handled by the expressions.
  • An expression is either a function or a simple number.
  • Prolog arithmetic is slightly different than other programming languages.
    For example:
    ?- X is  2 + 1.
    X = 3 ?
    yes
In the above example, 'is' is used as a special predefined operator.

The basic arithmetic operators are given in the following table:

Sr. NoOperatorExplanation
1X+YThe sum of 'X' and 'Y'
2X-Ythe difference of 'X' and 'Y'
3X*YThe product of 'X' and 'Y'
4X/YThe quotient of 'X' and 'Y'
5X^Y'X' to the power of 'Y'
6-XNegation of 'X'
7abs(X)Absolute value of 'X'
8sqrt(X)The square root of X
9sin(X)The sine of X
10cos(X)The cos of X

Operator precedence

  • If there is more than one operator in the arithmetic expression such as A-B*C+D, then the prolog decides an order in which the operator should be applied.
  • Prolog gives numerical value for each operator, operators with high precedence like '*' and '/' are applied before operators with relatively low precedence values like '+' and '-'.
  • Operator with same precedence value ('*' or '/') and ('+' or '-') should be applied from left to right.
  • So, the expression A-B*C+D can be written as A-(B*C)+D

Matching and Unification in Prolog

Definition: The two terms are said to be matched, if they are equal or if they consist of variables representing the resulting equal terms.
Prolog matches expressions in structural way. So,
?- 3 + 2= 5
no
Note: In prolog '=' means matches with.

Consider the following example,?- X + 3 =  2 * Y

But the following expressions will match because they have same structure.

Expression 1:
?- X + Y = 2 + 3
X = 2
Y = 3

Expression 2:
?- 2 + Y = X + 3
X = 2
Y = 3

Prolog Lists:

  • Lists are the finite sequence of elements.
  • Prolog uses […] to build a list.
  • The notation [X|Y] represents that the first element is X and second element is Y (X is head and Y is tail).
  • Prolog has some special notation for lists:
    I) [a]          [honda, maruti, renault]
    ii) [a,b,c)    [pen, pencil, notebook]
    iii) []  represents the empty list.
Example 1: Pattern Matching in Lists
?- [a,b] = [a,X]
X = b
but:
?- [a,b] = [X]
no

Example 2:
Consider the following lists:
[a, b, c, d, e, f, g]
[apple, pear, bananas, breadfruit]
[ ] this is an empty list
Now, consider some comparisons of lists:
[a,b,c] matches with [Head|Tail] resulting in Head=a and Tail=[b,c]
[a] matches with [H|T] resulting in H=a and T=[]
[a,b,c] matches with [a|T] resulting in T=[b,c]
[a,b,c] doesn't match with [b|T]
[] doesn't match with [H|T]
[] match with []. Hence, two empty lists get matched with each other.

Backtracking in Prolog

What is backtracking?

If a person reaches a point where a goal cannot be matched, so he can come back (backtrack) to the last spot, where the choice of matching a specific fact or rule was formed. If this process fails, a person again goes to the nearest previous place where a choice was made. So, this procedure is followed until the goal is achieved.

Example:
Consider the following facts,
bird(type (sparrow) name (steve)))
bird(type (penguin) name (sweety)))
bird(type (penguin)name (jones)))

consider the following query:

?- bird(type (penguin)name(X)

So, prolog will try to match the first query, but this query will not match because sparrow doesn't match with penguin. Then, it will try to find next query  to match the fact and succeed with X = sweety. Later, if the query or subgoals are failed, it will go to the saved option and look for more solutions. For example: X = jones

Genetic Learning

Genetic algorithms are the parts of evolutionary computing and are implemented as a computer simulation.

What is biological evolution?
  • Every organism has a set of rules which describes, how that organism is built, and encoded in the genes of an organism.
  • The chromosomes contain hundreds to thousands of genes.
  • Features of the organisms depend on the genes and they have several settings. For example: hair color gene may be brown or black.
  • The genes and their settings are referred to as a genotype of an organism.
  • When two organisms mate, they share their genes, so that the offspring gets half genes from one parent and half genes from the other parent. Hence, this process is called crossover.
  • It is possible that gene is mutated in the organism as a completely new feature.
  • The genetic algorithm follows the process of nature to solve the problems such as selection, crossover, mutation, and acceptance for evolution.
Following are the steps of genetic algorithm:

Step 1: Generate random population of 'n' chromosomes.
Step 2: Evaluate the fitness f(x) of each chromosome 'x' present in the population.  
Step 3: Follow these steps to create a new population:
        a) Selection: From population, select two parents fitness according to their fitness.
        b) Crossover: Perform crossover using  properties of crossover to form a new offspring.
        c) Mutation: Mutate the offspring at each position in chromosome.
        d) Accept: Place a new offspring in the new population.
Step 4: Replace: Use new generated population to run an algorithm.
Step 5: Test and Stop, if end condition is satisfied and return the best solution in the current population.
Step 6: Go to step 2.