The main goal of this work is to introduce theoretical background of the extended forward inference algorithm. Proposed algorithm allow to continue inference after its failure. Inference failure means that the inference engine is unable to obtain the solutions - the new facts or goals confirmation. Two-phase extension of classical inference algorithm is considered. In the first phase, classical forward inference is executed. If inference fails, second phase is activated and targeted search for additional facts is executed in the interactive mode. Inference extension proposed in this work is inspired be the rough sets theory which provides the conception of lower and upper approximations of particular sets.
Rule-based systems are a well known solvers for specialized domains of competence, in which effective problem solving normally requires human expertise. This approach to solving ill-structured and non-algorithmic problems has been known for many years and it seemed that in this field everything had been said. But the rules are still the most popular, important and useful tool for constructing knowledge bases. During the last decade we could observe the growth of interest on rule knowledge bases applications.
In the presented work, the extension of the forward inference algorithm will be
considered. The modifications and extensions of the inference algorithms for rule-based
systems were described in the previous works [
First group of approaches finishes any consideration after inference failure. This is
typical for currently used main expert system shells and frameworks for expert systems.
Second group attempts to continue inference using question-asking strategies. If the
initial information is insufficient, the system will ask the user for additional data. There are
few articles which discuss the question-asking problem analytically. Some of the early
applications of experts systems consider the issue of question asking strategies — the
system EXPERT [
Third group of approaches treats inference failure as a symptom of incompleteness. The most popular approach to process incomplete data is based on the uncertain reasoning. Reasoning under uncertainty has been studied in the fields of statistic, probability theory and decision theory. The oldies methods applied in uncertain reasoning are probability theory, including Bayesian networks, certainty factors, relatively newer are Dempster-Shafer theory, fuzzy logic and fuzzy set, rough sets, several non-monotonic logic have been also proposed. Methods mentioned above differ significantly, they try to quantitative estimate the degree of truth information, which can not be true from the logical point of view.
In this work we want to introduce different proposals of deal with inference failure. We propose an extension of classical inference algorithm, which includes two steps. In the first stage, classical forward inference is executed. If inference is successful, its result are presented in the typical way and the second stage is unnecessary and not activated. If inference fails, we propose simple idea: resumption of the inference and the acquisition of the missing facts. It could be done if a system is able to work in the interactive mode and the source of information about missing facts exist. Typically, the end-user may provide such information, in general, such information can be provided by any system environment, which is able to operate interactively (for example technical equipment with sensors, detectors). The acquisition of the missing facts seems to be a naive idea, however, we propose targeted search for additional facts, based on the results of failed inference from first stage. Detailed description of proposed approach is the topic of the next section. Introduced approach is similar to the described above question-asking method, the main difference is the utilisation of rough set inspired method of evaluating the acceptable fact extension set. In contrast to described question-asking method, proposed approach appends to resume classical forward inference and acceptable fact extensions a trigger for new inference. 3 3.1
In presented work the knowledge base is defined as a pair KB = (R, F ) where R is a non-empty finite set of rules and F is a finite set of facts. R = {r1, r2, . . . , rn}, each rule r ∈ R will have a form of Horn’s clause r : p1 ∧ p2 ∧ · · · ∧ pm → c, where m — the number of literals in the conditional part of rule r, and m ≥ 0, pi — i-th literal in the conditional part of rule r, i = 1 . . . m, c — literal of the decisional part of rule r. For each rule r ∈ R the following functions are defined: – concl(r) — the value of this function is the conclusion literal of rule r: concl(r) = c; – cond(r) — the value of this function is the set of conditional literals of rule r: cond(r) = {p1, p2, . . . pm}, – literals(r) — the value of this function is the set of all literals of rule r: literals(r) = cond(r) ∪ {concl(r)}, – csizeof (r) — conditional size of rule r, equal to the number of conditional literals of rule r: csizeof (r) = |cond(r)| = m, – sizeof (r) — whole size of rule r, equal to the number of conditional literals of rule r increased by the 1 for single conclusion literal, for rules in the form of Horn’s clause: sizeof (r) = csizeof (r) + 1.
We will also consider the facts as clauses without any conditional literals. The set of all such clauses f will be called set of facts and will be denoted by F : F = {f : ∀f∈F cond(f ) = {} ∧ f = concl(f )}.
In this work, rule’s literals will be denoted as the pairs of attributes and their values. Attributes are defined in a manner that is quite similar to that of a rough set theory. Let A be a nonempty finite set of conditional and decision attributes1. For every attribute a ∈ A the set Va will be denoted as the set of values of attribute a. Attribute a ∈ A may be simultaneously conditional and decision attribute. Also a conclusion of a particular rule ri can be a condition in other rule rj . It means that rule ri and rj are connected and it is possible that inference chains to occur. The literals of the rules from R are considered as attribute-value pair (a, v), where a ∈ A and v ∈ Va. Furthermore the notation (a, v) and a = v is equivalent. 3.2
Typically, inference failure is the result of incompleteness — it is possible to consider incompleteness of facts actually describing problem to solve, and/or the incompleteness or rules base. The condition p ∈ cond(r) of rule r will be true, if it is a fact: p ∈ F . For each rule r and non-empty set of facts F 6= ∅ it is possible to show following cases of matching the conditional part of each rule r ∈ R: cond(r) and set of facts F : 1. cond(r) ⊆ F — full matching, all rule’s conditions are facts: ∀pi∈cond(r)pi ∈ F , rule r is fireable, and r is able to draw new fact concl(r). 2. (cond(r) 6⊆ F ) ∧ (cond(r) ∩ F = ∅) — the lack of matching, all rule’s conditions are not facts: ∀pi∈cond(r)pi ∈/ F , rule r is definitively not fireable, and is not able to draw new fact. 3. (cond(r) 6⊆ F ) ∧ (cond(r) ∩ F 6= ∅) — partial matching, not all rule’s conditions are facts: ∃pi∈cond(r)pi ∈/ F , rule r is not fireable, and is not able to draw new fact.
The degree of matching rule r to the facts F we will describe using rule to facts matching factor M F (r) defined in the following way:
|cond(r) ∩ F | M F (r) =
|cond(r)|
For cases described above: M F (r) = 1 for case 1, M F (r) = 0 for case 2, 0 < M F (r) < 1 for case 3. From the inferential point of view, both cases 2 and 3 cause the impossibility of obtaining new facts. However, in the third case the rule r is promising — it will be fireable when we will succeed to asset as true conditions, that were considered to be false until now. The higher the M F (r) is, the greater is rule r usefulness. For the clarity of the further presentation, let RF be the set of rules fully matched to the facts, RP be the set of rules partially matched to the facts and RN denotes the set of rules that do not match to the facts at all:
RF = {r ∈ R : cond(r) ⊆ F } RP = {r ∈ R : (cond(r) 6⊆ F ) ∧ (cond(r) ∩ F 6= ∅)}
RN = {r ∈ R : cond(r) ∩ F = ∅} 1 Decision attributes are attributes that are at least once included in conclusion of any rule from R.
Inference extension proposed in this work is inspired be the rough sets theory [
Based on the knowledge provided by the rule r ∈ R and nonempty set of facts F , it is possible to identify the set of rule r conditions, which can be with certainty classified as the facts: F (r) = {c ∈ cond(r) : cond(r) ⊆ F }. Informally, the set F (r) is conceptually similar to the lower approximation of the fact set F under the knowledge described by the rule r.
It is also possible to identify set of rule r conditions, which can be only classified as possible facts: F (r) = {c ∈ cond(r) : cond(r) ∩ F 6= ∅}. The items of F (r) are facts or they appears in the rule r premises partially matched to the facts set. Informally, the set F (r) is conceptually similar to the upper approximation of the fact set F under the knowledge described by the rule r. The set FBN (r) = F (r) − F (r) contains conditions representing missing facts. If these conditions will be the facts, the rule r will be fireable. It is informally similar to the boundary region of F , and thus consists of those conditions that cannot be classified as the facts on the basis of knowledge described in the rule r, but are interesting in the context of inference after failure. The set FBN (r) will be called basic fact extension set for rule r.
It is possible to consider approximation-like total sets described above, for any nonempty set of rules R ⊆ R:
F T (R) = {F (r) : r ∈ R} F T (R) = {F (r) : r ∈ R}
FT BN (R) = F (R) − F (R)
The first naive extension of forward inference proposed in this work, will use the set FBN (R) it will be called fact extension set for rules R. The pseudo-code 3 presents the implementation of classical forward inference algorithm (CFI). The input data are — rule base: R = {r1, r2, ..., rm}, facts set: F = {f1, f2, ..., fk}. The output data are — new facts in F = {f1, f2, ..., fk, fk+1, ..., fnk}, function result: true if new facts inferred, false otherwise.
The first proposed extended forward inference algorithm (EFI) is presented by the pseudo-code 4. At the beginning the EFI algorithm calls classical forward inference CFI. If inference is successful, function CFI returns true and the first stage of the EFI algorithm is the last one — the EFI works like CFI. If inference is unsuccessful, function CFI returns false and the second stage of algorithm is activated. On this stage, the promising rules subset R is selected and the FBN (R) is determined. The FBN (R) set contains sets of conditions representing possible facts. This set can be ordered by the selected strategy — for simplicity the minimal subset will be considered first.
Next, the algorithm looks for first acceptable extension of the facts set e ∈ FBN (R). Decision about the truth of the fact is taken by the function accepted, which return true if proposed extension e is acceptable, false otherwise. In object-oriented implementation of EFI algorithm, function accepted is defined as the abstract function or method. It
Algorithm 3: CFI — Classical Forward Inference algorithm function CFI( R, F ) : boolean var A ← ∅ var N F ← ∅ begin select rules subset RF from R according to F while RF 6= ∅ do r ← select rule from RF according to current selection strategy N F ← N F ∪ {concl(r)} F ← F ∪ N F A ← A ∪ {r} select rules subset RF from R − A according to F end while return N F 6= ∅ end function may be implemented in any way, e.g. through interaction with the system user or, in general, with system environment. First acceptable extension e is added to the fact set and EFI function calls itself recursively. Next call of CFI function should be successful — accepted facts extension should fire proper new rule. Thus, it is possible to skip recursive call and to call CFI directly. Recursive version is more general and allows the consideration of different methods of evaluating possible facts extensions.
Proposed method of inference after failure looks for first acceptable facts sets extension FT BN (r). Method of calculation the possible facts extension set described above, ensures successful classical inference after acceptance of any set’s element. It can trigger only one step of classical inference, or it may cause many iteration of the algorithm. Unfortunately, the results of inference may be unpredictable and distant from expectation. Additionally, iterative acquisition of acceptable fact extension may be uncomfortable for the user — the number of possible query for large rule bases can be high, thus unacceptable in the real-world applications.
Proposed algorithm is also sensitive to the order of selection of the FT BN (R) set’s elements. Different order of the elements selected from FT BN (R) can lead to different inference results. It is not clear whether the obtained inference results are useful and satisfactory from the point of view of the problem being solved. Although the proposed solution may be capable of providing potentially useful results, it is possible to formulate more appropriate methods of determination of FT BN (R) set and selection of promising facts extension. As presented below, extraction of the internal rules dependencies will be a source of information for improving selection of possible facts. 3.5
For each rule base R with n rules, it is possible to consider a partition P R of a set R. P R is grouping of set’s R rules into non-empty subsets, in such way that every rule is included in one and only one of the subsets: ∅ ∈/ P R, SR∈P R = R and if Ri, Rj ∈ P R and Ri 6= Rj then Ri T Rj = ∅. The sets in P R will be called the rules groups of the partition. In this work only simple partitioning strategies will be considered. The membership criterion function decides about the membership of rule r in a particular group R ⊆ P R according to the membership function mc. Simple strategy divides the rules by using the algorithm with time complexity not higher than O(n · k), where n = |R| and k = |P R|. Simple strategy creates final partition P R by a single search of the rules set R and allocation of each rule r to the proper cell R, according to the value of the function mc(r, R) described bellow.
Proposed approach assumes that the membership criteria is defined by the mc function, which is defined individually for every simple partition strategy. The function: mc : R × P R → [0..1], return the value 1 if the rule r ∈ R with no doubt belongs to the group R ⊆ P R, 0 in the opposite case. The value of the function from the range 0 < mc < 1 means the partial membership of the rule r to the group R. The method of determining its value and its interpretation depends on the specification of a given partition method. It is possible to achieve many different partitions of rule base using single mc function.
The simple strategy partitioning algorithm is presented [
By using the simple partition algorithm [
The second partitioning strategy considered in this work is decision oriented partition denoted P RD. It also uses the simple partition algorithm with the mc function defined in the following way: mc(r, R) = 1 if ∀ri∈R attrib(concl(ri)) = attrib(concl(r)), 0 otherwise. (2)
Each generated group of the rules have the following form: R = {r ∈ R : ∀ri∈R attrib(concl(ri)) = attrib(concl(r))}. When we distinguish different decisions by the different attribute from conclusions appearing in the rules — we obtain one group for each decision attribute. Thus any rule set R ∈ P RD can be described as R = {S R′ ∈ P RB : ∀ri, rj ∈ R′ attrib(concl(ri)) = attrib(concl(rj ))}. It means that the decision produced by the ordinal decision partition can be constructed as the composition of the basic decision partitions. By analogy, decision oriented partition is similar to the decision tables DT = (U, A ∪ {d}), where d is single decision attribute.
The partitioning strategy P RB and P RD describes global dependencies appearing in the rule base. To express and utilize dependencies between rules in any partition P R, it is possible to define partitions connection graph GP R = (P R, C). P R represents nodes of GP R, C ⊆ P R × P R represents relation which defines edges of GP R. In the context of connection graph, we assume that for any rules group R we consider two sets — In(R) and Out(R). In(R) and Out(R) denote respectively the set of input and output data of the rules set. Items of those sets are literals appearing in the rules from R. The structure of In(R) and Out(R) depends on the currently considered partition strategy. The C relation can be defined in the following way: C = {(x, y) ∈ P R × P R : Out(x) ∩ In(y) 6= ∅}. In the introduced modification of inference, the decision partition strategy is considered and following mappings are proposed: Out(R) = Concl(R), In(R) = Cond(R). Thus, the C relation connects the group of rules with the common attributes in conclusion and conditions. The subsets can be defined: connected inputs sub-set InC (R) ⊆ In(R) can be considered: InC (R) = {(a, v) ∈ In(R) : ∃r∈R (a, v) = concl(r)}, and connected output sub-set OutC (R) ⊆ Out(R) : OutC (R) = {(a, v) ∈ Out(R) : ∃r∈R (a, v) ∈ cond(r)}. 3.6
Simple decision models provided by the two previously described partitioning strategies allow to direct the searching of the fact extension set. For relatively small rule sets, or „flat” rules sets (∀R⊆P RInC (R) = ∅ ∧ OutC (R) = ∅), basic decision partition can be used. The partitions connection graph GP R provides enough information to identify such situations. For rules bases containing big number of rules, basic decision partition may produce large number of rules group and ordinal decision partition strategy may be used. Apart of used partitioning method, decision model allows to consider different strategies of selection the promising rules set for facts extension searching.
First, it is possible to reject rules sets from P R with empty intersection with facts set. Let’s assume that P RF ⊆ P R is subset of partition P R with non empty intersection with the facts set: P RF = {R : ∃r∈R cond(r) T F 6= ∅}. For each group R ∈ P R it is possible to determine fact extension set FT BN (R). Thus, the set of fact extension sets can be considered: F ES = {FT BN (R) : R ∈ P RF }.
Selection of the first acceptable fact set extension will consist of two steps. In first step, the most promising rules group from P RF will be selected. In the second step, the most adequate facts extension set for selected rules set will be promoted for acceptance. The combination of two above steps provides the different strategies of selecting facts extension set. On the level of the most promising rules group R selection, it is possible to indicate the following possibilities: – The connected output sub-set: OutC (R) = ∅ — inference will produce the one or multiple new facts from Out(R) and the inference will stop. The new facts are unable to trigger any other rule. This rule selection strategy offers shortest inference path and predictable effects — only facts from Out(R) are expected. – The connected output sub-set: OutC (R) 6= ∅ — inference will produce the one or multiple new facts from Out(R) and inference will likely continue. The new facts are able to trigger other rules from rules group connected with R. This rule selection strategy offers the ability to obtain new facts not only from the Out(R). – It is possible to select the rule group R as a start point of longest path in the GP R.
This strategy offers the possibility of obtaining a variety new facts. – The rules group with maximal facts coverage can be selected — M F (R) = |C|Conodn(dR(R)∩)F|| .
The modified after failure inference algorithm differs in two lines and therefore will not be presented as separate pseudo-code. The line number (1) in the algorithm 4 should be replaced by the following two lines: 1. P R = createDecisionPartition( R )
The first version of EFI algorithm (4) has been implemented as a part of kbExplorator desktop system. kbExplorator is the system which integrates two components — desktop and web application. Web application allows to create, edit and manage rules bases which are stored on the kbExplorator server. The knowledge bases are assigned to the users registered in the web application. Desktop application allows to perform different operations on the knowledge base stored on the server, operations jointly referred to as exploration. Web application is mainly dedicated to the knowledge engineers as a tool for knowledge base building and improving. Desktop application is the tool for more sophisticated knowledge exploration. The kernel of the desktop application consist of object-oriented packages implemented in Java. Packages offer, among other things, different types of reasoning, both classic and modified versions and also new algorithms, including EFI proposed in this work. Applications now have the status of a prototype, they will be available as the free software online in the coming months. Till now, kbExplorator is one of the few expert system building tools which allows to continue inference after its failure.
The first version of EFI algorithm selects a minimal acceptable facts extensions. The main advantage of this algorithm is its simplicity. Unfortunately, experiments confirmed earlier expectations, the results of inference may be unpredictable and iterative acquisition of acceptable fact extension have proven to be uncomfortable for the user. For large rule bases, iterative acquisition of missing fact was not acceptable for the real-world applications.
Proposed algorithm is also sensitive to the order of selection of the fact extension set elements. Different order of the elements selections can lead to different inference results. It is not clear whether the obtained inference results are useful and satisfactory from the point of view of the problem being solved. Although the proposed solution may be capable of providing potentially useful results, modification proposed in the previous section will be considered in the future work. Modified EFI algorithm utilizes the internal dependencies between rules divided into the decision oriented group of rules. Detailed experiments will be made in the next stage of research and the experimental results will be presented in the next publications. One of the reasons is the need of implementation of similar methods for a comparative study. Unfortunately, there is a lack of detailed source information which presents enough information about the implementation details on the proper level of detail. Additional literature studies are needed and future research could be focused on a comparative study of algorithms proposed in this work with the question-asking oriented methods.
Main tool of proposed optimisation are decision oriented partitions of rule base. The complexity of decision partition is O(n · k), where n = |R|, k = |P R|, where the number of groups in the partition k : 1 ≤ k ≤ n typically is significantly smaller than the number of rules n. We have to store additional information for created rules partitions, however additional memory or disk space occupation for data structures seems acceptable. For n rules and k rules group we need approximately is · n + ps · m bytes of additional memory for data structures (is âA˘ Tˇ size of integer, ps âA˘ Tˇ size of a pointer or reference).
In the presented work, the conception of the extended forward inference algorithm
was presented. This algorithm allows to continue the inference after its failure.
Inference failure means that the inference engine is unable to obtain the solutions: the new
facts or goals confirmation. It often happens that the initial facts are not sufficient for
a knowledge-based system to reach any conclusion, and more information is needed.
In this work two-phase extension of classical inference algorithm was considered. In
the first phase classical forward inference is executed. If inference fails, second phase
is activated and targeted search for additional facts is executed in the interactive mode.
Proposed solution is similar to a question-asking method described in [
In general, the proposed approach is inspired by the set approximation, but relation with the rough set theory is not strict. The description presented in this article informally refers to the lower and upper approximations. Based on the knowledge provided by the rules and set of facts, it is possible to identify the set of rules conditions which can be with certainty classified as the facts. It is conceptually similar to the lower approximation of the fact set. It is also possible to identify set of rules conditions which can be only classified as possible facts, because they appear in the rules premises partially matched to the facts set. It is conceptually similar to the upper approximation of the fact set. The boundary set contains conditions which represent missing facts. If these conditions are facts, some rules will be fireable. It is informally similar to the boundary region of facts, and thus consists of those conditions that cannot be classify as the facts on the basis of knowledge described in the rules base, but are interesting in the context of inference after failure. This work introduced theoretical background of the algorithm, detailed experiments will be made in the next stage of research and the experimental results will be presented in the next publications.
This work is a part of the project „Exploration of rule knowledge bases” founded by the Polish National Science Centre (NCN: 2011/03/D/ST6/03027).