Professional programming for artificial intelligence systems in PROLOG
In the tasks of artificial intelligence, various models of knowledge representation and computational methods are used - soft computations, genetic algorithms, neural networks, logical models and other approaches. All these methods are based on symbolic calculations and therefore can be implemented on the basis of the PROLOG language.
Here we look at the methods of building intelligent systems based on a logical approach that is closest to the nature of logical programming and is often used in expert systems.
The basis of the logical conclusion is the mathematical concept of "formal system (FS)". FS is a collection of abstract objects interconnected by certain rules. Recall the definition. The formal system F is given if the quad is defined:
F = (Al, Sn, Ax, Ru)
Al - the alphabet - a finite set of characters;
Sn - syntax - the procedure for constructing correctly constructed FS formulas;
Ax - axioms - the set of correct formulas given initially;
Ru - inference rules - a finite set of rules that allow to obtain new formulas from other FS formulas.
Any program in the language of the PROLOGUE is a FS, which in one program can be several. In the PROLOGUE, the notion of unification plays an important role, allowing the FS rules to be more widely applied by substitution of parameters. A good example of a file system in a program is the PROLOG () parser.
FS can be used to generate new statements (direct inference) or to prove the correctness of statements (inverse conclusion). In the PROLOGUE, both variants of inference can be realized, although the reverse inference is realized directly, since it is embedded in the structure of the language.
A logic programming language provides many interesting possibilities for solving intellectual problems, i.e. requiring logical inference to obtain a solution. As a rule, the possibilities of a language in creating various types of application systems are demonstrated in fairly simple examples, intended more to demonstrate the paradigm of logic programming, for educational purposes.
To create practically useful application systems, a number of properties are required which are absent in the PROLOG system, but which can be added to it.
Just in case, let us recall that the computation in logic programming consists in the search for logical inference. This term refers to a tree whose root is the statement to be proved, and the remaining vertices contain statements related to each other by logical following. At the same time, the terminal vertices (leaves) of the tree must be the initial data - assertions formulated in the problem statement.
Building a logical inference tree consists in searching for interrelated chains of statements from leaves to apex among a set of all possible paths from top to leaves. This set is called the task search space.
Search can be direct - from data to the desired and reverse - from the desired to the data. In the first approach, the conditions of the problem calculate what is possible - the new statements, thereby increasing the amount of the known about the problem.
In the second approach, hypotheses are built - a sequence is built, more precisely a tree, hypotheses, which should lead to known data.
Since the PROLOGUE is based on inverse output, we first consider inverse output.
To illustrate the problems that arise when constructing non-toy expert systems, we use as a subject area planimetry, more precisely, its small part associated with the solution of triangles.
Consider a specific task.
In an isosceles triangle, there is a height from a vertex located between equal sides. In the resulting inner triangle, the height is again drawn, then another height in the new triangle, and so on. total - 10 heights. The base length of triangle AC and side BC is known. Any triangle formed by the altitudes must be solved.
The presentation of the main objects can be as follows:
For simplicity, consider the calculation of the second height of the triangle - DE. Let us write the conditions of the problem by means of the PROLOG language:
s (1, exist (d, tri (a, b, c))).
s (2, height (seg (b, d), tri (a, b, c))).
s (3, height (seg (d, e), tri (b, c, d))).
s (4, height (seg (f, e), tri (b, e, d))).
s (5, height (seg (f, g), tri (f, e, d))).
s (6, height (seg (h, g), tri (f, g, e))).
s (7, height (seg (h, i), tri (g, h, e))).
s (8, height (seg (i, k), tri (h, i, e))).
s (9, height (seg (k, l), tri (i, k, e))).
s (10, height (seg (l, m), tri (l, k, e))).
s (11, height (seg (m, n), tri (m, l, e))).
s (12, equal (seg (a, b), seg (b, c))).
s (13, length (seg (a, b), 10)).
s (14, length (seg (a, c), 16)).
s (15, length (seg (d, e), x)).
')
To ensure the numbering of the conditions of the problem, the predicates are written in additional brackets in the form of s (N, P).
The last line in the source data of the problem defines the goal - the statement that must be proved. In our case, the target length (seg (d, e), x) contains the variable x, which allows us to calculate the value of the length of the segment DE.
One of the main difficulties in applying the PROLOGUE to the implementation of commercial systems is the occurrence of a program looping during the calculation process. The reason for this may not be an error in the program, but the recursiveness of the properties of the objects of the domain and, accordingly, the recursiveness of the rules of inference.
For example, in the inference rules for solving triangles, inevitably there is a recourse to similar rules.
Example 1, Calculating the length of a segment in a triangle.
Calculating the length of the side of a triangle through height and area:
length (seg (A, C), L): -
height (seg (B, D), tri (A, B, C)),
length (seg (B, D), L1),
area (tri (A, B, C), S1),
L is (2 * S1) / L1.
Calculate the length of the height of the triangle through the base and area:
length (seg (B, D), L): -
height (seg (B, D), tri (A, B, C)),
length (seg (A, C), L1),
area (tri (A, B, C), S1),
L is (2 * S1) / L1.
To solve our problem, four rules are enough to calculate the length of the segment — calculating the length of the segment formed by the height of an isosceles triangle, the Pythagorean theorem, calculating the length of height through the area and the base of the triangle, and getting the value from an equal segment.
In the process of finding a solution, all emerging goals are numbered. All the solutions that were considered in the search process form the task search space, from which only a small part falls into the resulting logical inference tree.
The solution - the logical inference tree for our problem can be written as a list of numbered predicates as follows:
Each predicate is a goal derived from the process of solving a problem and has a number assigned to it in the course of calculations. On the right, in square brackets, is the list of predicate numbers used in the rule of the same name for obtaining the result.
The same tree in the graphical representation has the following form:
As you can see from the figure, all terminal vertices of the tree are statements from the source data.
We present a textual interpretation of the solution obtained.
1) To calculate the length of the segment seg (d, e) (331), the rule is used: if the desired segment is height in a triangle, then its length is equal to the area of the triangle divided by the base and multiplied by two. Arguments for this rule are derived from targets with numbers 66,332.3,
The area of the triangle cdb is 24 - target 332. The length of the base bc is 10 - target 66. The required length is 2 * (24/10) = 4.8. The segment de is the height of the triangle cdb - goal 3 (initial data).
2) The length of the segment bc (66) is calculated from the rule - if the desired segment is equal to another segment with a known length, then the desired length is equal to the length of an equal segment.
In our case, the desired segment bc is equal to the segment ab - this is specified in the source data — goal 12, the length of the segment ab is specified in statement 13.
3) The area of the triangle cdb (332) is calculated according to the rule for right-angled triangles by the lengths of the legs, the arguments are given by targets 46,44, 333, 334.
The rectangle triangle cdb (333) follows from the fact that the segment bd is the height of the triangle abc (2). This implies the definition of segments that are legs in this triangle — bd and dc (334). This is followed by the calculation of the lengths of the legs (44) and (46).
4) The length of the leg db (44) is calculated through the right-angled triangle bdc of the targets with numbers 77,66,46,45.
Goal 77 - apply the Pythagorean theorem to calculate the segment db. Target 66 - calculate the length of the segment bc. Goal 46 is the length of the segment dc. Objective 45 is the presence of a right-angled triangle dbc with the required segment db.
5) The length of the leg dc (46) is calculated from targets 14, 47 according to the segment rule with the median of a triangle. Target 14 is specified in the source data — the length of the ac segment to which the median bd (47) is omitted. The rule applies - height in an isosceles triangle, dropped on its base, is the median.
Since in the given example the data were obtained as a result of applying a specific logic program, it can be assumed that the search volume was 334 targets, of which 13 were the necessary solution of the problem.
For a more complicated case, for example, to calculate the tenth height in our triangle - the segment LM, the search volume was 1667 targets, and in the process of finding a conclusion, 138 statements were made, of which not all were included in the desired solution. The insignificant amount of search is due to the fact that only four rules were used to calculate the length of the segment.
We looked at a simplified example to illustrate the main aspects of solving problems that require logical inference. If we try to describe all the planimetry theorems for calculating the length of a segment — the similarity and equality of triangles, trigonometric functions, composite segments, the volume of necessary calculations increases by orders of magnitude and here we will need to have additional possibilities to cope with all the arising difficulties.
In order to solve sufficiently voluminous intellectual tasks, the usual PROLOG language is not enough, since it lacks a number of properties, without which it is difficult to build a practically useful program. These improvements to the PROLOGUE language system can be divided into two groups - the control of finding the output (logical) and technological.
The following search management enhancements are needed:
Conclusion
We reviewed the main aspects of building a formal system in the form of a program for solving logical problems. FS solves problems by full busting options.
If the method given here describes the rules for all the necessary planimetry theorems, the search space will be very heavy for the average computer, and maybe for a supercomputer. However, we are well aware that a sensible schoolchild will solve almost any problem that can be solved in a reasonable time, without performing too much enumeration.
How he does it? By analyzing and planning solutions, outlining the most promising approaches and not considering deliberately useless. The knowledge that he will use to plan the solution is not a geometric theorem - this is the knowledge that is called expert - knowledge about the methods of finding a solution that an expert usually gets in the process of learning and develops independently in the process of gaining experience.
Conclusion - one FS is not an expert system. For ES, you need to combine several FS. In the following, we will consider in more detail how to do this.
Here we look at the methods of building intelligent systems based on a logical approach that is closest to the nature of logical programming and is often used in expert systems.
The basis of the logical conclusion is the mathematical concept of "formal system (FS)". FS is a collection of abstract objects interconnected by certain rules. Recall the definition. The formal system F is given if the quad is defined:
F = (Al, Sn, Ax, Ru)
Al - the alphabet - a finite set of characters;
Sn - syntax - the procedure for constructing correctly constructed FS formulas;
Ax - axioms - the set of correct formulas given initially;
Ru - inference rules - a finite set of rules that allow to obtain new formulas from other FS formulas.
Any program in the language of the PROLOGUE is a FS, which in one program can be several. In the PROLOGUE, the notion of unification plays an important role, allowing the FS rules to be more widely applied by substitution of parameters. A good example of a file system in a program is the PROLOG () parser.
FS can be used to generate new statements (direct inference) or to prove the correctness of statements (inverse conclusion). In the PROLOGUE, both variants of inference can be realized, although the reverse inference is realized directly, since it is embedded in the structure of the language.
A logic programming language provides many interesting possibilities for solving intellectual problems, i.e. requiring logical inference to obtain a solution. As a rule, the possibilities of a language in creating various types of application systems are demonstrated in fairly simple examples, intended more to demonstrate the paradigm of logic programming, for educational purposes.
To create practically useful application systems, a number of properties are required which are absent in the PROLOG system, but which can be added to it.
Just in case, let us recall that the computation in logic programming consists in the search for logical inference. This term refers to a tree whose root is the statement to be proved, and the remaining vertices contain statements related to each other by logical following. At the same time, the terminal vertices (leaves) of the tree must be the initial data - assertions formulated in the problem statement.
Building a logical inference tree consists in searching for interrelated chains of statements from leaves to apex among a set of all possible paths from top to leaves. This set is called the task search space.
Search can be direct - from data to the desired and reverse - from the desired to the data. In the first approach, the conditions of the problem calculate what is possible - the new statements, thereby increasing the amount of the known about the problem.
In the second approach, hypotheses are built - a sequence is built, more precisely a tree, hypotheses, which should lead to known data.
Since the PROLOGUE is based on inverse output, we first consider inverse output.
To illustrate the problems that arise when constructing non-toy expert systems, we use as a subject area planimetry, more precisely, its small part associated with the solution of triangles.
Consider a specific task.
In an isosceles triangle, there is a height from a vertex located between equal sides. In the resulting inner triangle, the height is again drawn, then another height in the new triangle, and so on. total - 10 heights. The base length of triangle AC and side BC is known. Any triangle formed by the altitudes must be solved.
The presentation of the main objects can be as follows:
- seg (A, B) - a segment with end points A and B;
- tri (A, B, C) is a triangle with vertices A, B, C;
- length (seg (A, B), L) is the length of the segment;
- equal (tri (A, B, C), tri (X, Y, Z)) - equality of triangles.
For simplicity, consider the calculation of the second height of the triangle - DE. Let us write the conditions of the problem by means of the PROLOG language:
s (1, exist (d, tri (a, b, c))).
s (2, height (seg (b, d), tri (a, b, c))).
s (3, height (seg (d, e), tri (b, c, d))).
s (4, height (seg (f, e), tri (b, e, d))).
s (5, height (seg (f, g), tri (f, e, d))).
s (6, height (seg (h, g), tri (f, g, e))).
s (7, height (seg (h, i), tri (g, h, e))).
s (8, height (seg (i, k), tri (h, i, e))).
s (9, height (seg (k, l), tri (i, k, e))).
s (10, height (seg (l, m), tri (l, k, e))).
s (11, height (seg (m, n), tri (m, l, e))).
s (12, equal (seg (a, b), seg (b, c))).
s (13, length (seg (a, b), 10)).
s (14, length (seg (a, c), 16)).
s (15, length (seg (d, e), x)).
')
To ensure the numbering of the conditions of the problem, the predicates are written in additional brackets in the form of s (N, P).
The last line in the source data of the problem defines the goal - the statement that must be proved. In our case, the target length (seg (d, e), x) contains the variable x, which allows us to calculate the value of the length of the segment DE.
One of the main difficulties in applying the PROLOGUE to the implementation of commercial systems is the occurrence of a program looping during the calculation process. The reason for this may not be an error in the program, but the recursiveness of the properties of the objects of the domain and, accordingly, the recursiveness of the rules of inference.
For example, in the inference rules for solving triangles, inevitably there is a recourse to similar rules.
Example 1, Calculating the length of a segment in a triangle.
Calculating the length of the side of a triangle through height and area:
length (seg (A, C), L): -
height (seg (B, D), tri (A, B, C)),
length (seg (B, D), L1),
area (tri (A, B, C), S1),
L is (2 * S1) / L1.
Calculate the length of the height of the triangle through the base and area:
length (seg (B, D), L): -
height (seg (B, D), tri (A, B, C)),
length (seg (A, C), L1),
area (tri (A, B, C), S1),
L is (2 * S1) / L1.
To solve our problem, four rules are enough to calculate the length of the segment — calculating the length of the segment formed by the height of an isosceles triangle, the Pythagorean theorem, calculating the length of height through the area and the base of the triangle, and getting the value from an equal segment.
In the process of finding a solution, all emerging goals are numbered. All the solutions that were considered in the search process form the task search space, from which only a small part falls into the resulting logical inference tree.
The solution - the logical inference tree for our problem can be written as a list of numbered predicates as follows:
- (78) hypot (tri (d, b, c), seg (b, c)) [79]
- (45) exist_rect (tri (d, b, c), seg (d, b)) [2]
- (46) length (seg (d, c), 8) [14,47]
- (66) length (seg (b, c), 10) [13,12]
- (77) pif_length ([seg (d, b), 6], [[seg (d, c), 8], [seg (b, c), 10]]) [78]
- (47) median (tri (a, b, c), seg (b, d)) [2.48]
- (333) rectangle (tri (c, d, b), _ 2F28) [2]
- (334) catets (tri (c, d, b), [seg (b, d), seg (d, c)]) [78]
- (44) length (seg (d, b), 6) [77,66,46,45]
- (46) length (seg (d, c), 8) [14,47]
- (332) area (tri (c, d, b), 24) [46,44,334,333]
- (66) length (seg (b, c), 10) [13,12]
- (331) length (seg (d, e), 4.8) [66,332,3]
Each predicate is a goal derived from the process of solving a problem and has a number assigned to it in the course of calculations. On the right, in square brackets, is the list of predicate numbers used in the rule of the same name for obtaining the result.
The same tree in the graphical representation has the following form:
As you can see from the figure, all terminal vertices of the tree are statements from the source data.
We present a textual interpretation of the solution obtained.
1) To calculate the length of the segment seg (d, e) (331), the rule is used: if the desired segment is height in a triangle, then its length is equal to the area of the triangle divided by the base and multiplied by two. Arguments for this rule are derived from targets with numbers 66,332.3,
The area of the triangle cdb is 24 - target 332. The length of the base bc is 10 - target 66. The required length is 2 * (24/10) = 4.8. The segment de is the height of the triangle cdb - goal 3 (initial data).
2) The length of the segment bc (66) is calculated from the rule - if the desired segment is equal to another segment with a known length, then the desired length is equal to the length of an equal segment.
In our case, the desired segment bc is equal to the segment ab - this is specified in the source data — goal 12, the length of the segment ab is specified in statement 13.
3) The area of the triangle cdb (332) is calculated according to the rule for right-angled triangles by the lengths of the legs, the arguments are given by targets 46,44, 333, 334.
The rectangle triangle cdb (333) follows from the fact that the segment bd is the height of the triangle abc (2). This implies the definition of segments that are legs in this triangle — bd and dc (334). This is followed by the calculation of the lengths of the legs (44) and (46).
4) The length of the leg db (44) is calculated through the right-angled triangle bdc of the targets with numbers 77,66,46,45.
Goal 77 - apply the Pythagorean theorem to calculate the segment db. Target 66 - calculate the length of the segment bc. Goal 46 is the length of the segment dc. Objective 45 is the presence of a right-angled triangle dbc with the required segment db.
5) The length of the leg dc (46) is calculated from targets 14, 47 according to the segment rule with the median of a triangle. Target 14 is specified in the source data — the length of the ac segment to which the median bd (47) is omitted. The rule applies - height in an isosceles triangle, dropped on its base, is the median.
Since in the given example the data were obtained as a result of applying a specific logic program, it can be assumed that the search volume was 334 targets, of which 13 were the necessary solution of the problem.
For a more complicated case, for example, to calculate the tenth height in our triangle - the segment LM, the search volume was 1667 targets, and in the process of finding a conclusion, 138 statements were made, of which not all were included in the desired solution. The insignificant amount of search is due to the fact that only four rules were used to calculate the length of the segment.
We looked at a simplified example to illustrate the main aspects of solving problems that require logical inference. If we try to describe all the planimetry theorems for calculating the length of a segment — the similarity and equality of triangles, trigonometric functions, composite segments, the volume of necessary calculations increases by orders of magnitude and here we will need to have additional possibilities to cope with all the arising difficulties.
In order to solve sufficiently voluminous intellectual tasks, the usual PROLOG language is not enough, since it lacks a number of properties, without which it is difficult to build a practically useful program. These improvements to the PROLOGUE language system can be divided into two groups - the control of finding the output (logical) and technological.
The following search management enhancements are needed:
- looping protection;
- save created output;
- the ability to work with large volumes of rules;
- saving the trace of the search of output in the state space of the subject area for debugging;
- management of the volume of calculations to protect against unnecessary inefficient searches in the presence of an error or lack of a solution;
- building an explanation of the decision.
Technological improvements: - integration with procedural programming languages;
- integration with operating system tools;
- code efficiency;
- the possibility of creating offline programs.
Most modern systems of the PROLOGUE language have a compiler and other tools that provide the ability to create application programs that are applicable without the PROLOG language interpreter, in conjunction with programs in other programming languages or autonomously.
To obtain search improvements, it is necessary to insert additional checks in each PROLOG rule in the application program and, accordingly, additional arguments.
In order not to do it manually, you can use special tool systems. The research and production company Semantics Research has developed a system called Exxlog, which can be downloaded for free on the company's website (exxlog.ru).
Conclusion
We reviewed the main aspects of building a formal system in the form of a program for solving logical problems. FS solves problems by full busting options.
If the method given here describes the rules for all the necessary planimetry theorems, the search space will be very heavy for the average computer, and maybe for a supercomputer. However, we are well aware that a sensible schoolchild will solve almost any problem that can be solved in a reasonable time, without performing too much enumeration.
How he does it? By analyzing and planning solutions, outlining the most promising approaches and not considering deliberately useless. The knowledge that he will use to plan the solution is not a geometric theorem - this is the knowledge that is called expert - knowledge about the methods of finding a solution that an expert usually gets in the process of learning and develops independently in the process of gaining experience.
Conclusion - one FS is not an expert system. For ES, you need to combine several FS. In the following, we will consider in more detail how to do this.
Source: https://habr.com/ru/post/277229/
All Articles