Vassil Sgurev, Vladimir Jotsov
Bulgaria, Sofia 1113, acad. G. Bonchev Str. Bl. 29A, IITBAS. Email: vsjotsov@yahoo.com
ON NETWORK FLOW INTERPRETATIONS OF DEFEASIBLE INFERENCE SCHEMES
Abstract. The defeasible reasoning is applicable in situations when exclusions from the used rules could appear, aiming at defeating some of the existing knowledge. Defeasible analogies shorten the process of searching for and applying such knowledge. Their application decreases the complexity of the inference problem as a whole. The paper discusses a special knowledge representation in the network flow form applied especially for defeasible analogies purposes. This allows to combine logical and quantitative approaches, and to obtain the advantages from both of them.
Васил Сгурев, Владимир Йоцов
Болгария, София, ИИТБАН, ул. Акад. Г. Бончева, Бл. 29А.
СЕТЕВЫЕ ПОТОКОВЫЕ СХЕМЫ ДЛЯ АННУЛИРУЮЩЕГО ВЫВОДА
Аннотация. Аннулирующий вывод применяется в ситуациях, когда появляются исключения из правил с целью аннулирования существующих знаний. Для сокращения времени поиска подобных исключений предложено использовать аннулирующие аналогии. В докладе предлагается использовать потоки в сетях для целей аннулирующего вывода по аналогии.
1. INTRODUCTION
In the general case every rule can be represented by the help of a relation of the type "B follows from A": A® B, where B is a statement from the rule head, A is the body of the rule. When an "exclusion from the rules" E(C,A) is applied to statement A, the reasonsequence relation is altered. D. Note introduces in [1,2] the notion defeasible inference on the basis of the use of exclusions, attached to one or to a group of rules or separate statements (facts). Defeasible inference is expanded as a notion and application in papers [3, 4] in the following way.
2. PURPOSE AND INVESTIGATION PROBLEMS
It will be pointed below that the operation mechanisms of the exclusions from the rules can be realised in a different way, which changes the results from logical inference. Thus several different types of defeasible reasoning have been formulated. Let a rule of Horn's type (1) be given:
(1)
where A_{i} are conjuncts from the rule body (I={1, 2, ..., z}, (the conjunction will be further denoted by the symbol C only for the union of conjuncts from the antecedents of the rules), and B is one statement  head of the rule (it is a result of the relation). When applying twovalued logics to artificial intelligence (AI) problems, if at least one statement from A_{i} is not true, then B is not defined (true or false). In case an appropriate exclusion from rule (1) is found (the notion exclusion only will be used further on) in connection with any A_{p} (it is assumed that pI I), the procedure for inference changes. In case the exclusion E(C, A_{p}) and C are true and A_{p} is false, then B can be true (by exception). In [3, 4] extended models of defeasible inference are suggested, generalised in the paper in a formalised type (3), (2)(4) and/or (2)(5).
(2)
(3)
(4)
(5)
where a _{i} are apriori given coefficients of the significance of statements  conjuncts from the antecedents of the rules (the term belief is also used for them). It is seen from the formulas that the exclusions are also a kind of connection of a rule relation character, and their area of operation includes one or more rules (1). The exclusions may be distributed among the objects studied by inherited properties in a connection of ancestorpredecessor type. The defeasible reasoning proposed in (3) is based on the following. If there exists an exclusion E(C, A_{p}) connected with one of the rules with a head B and as a result of its action A_{p} is obtained, then the conjunct A_{p} from the rule body is replaced by O A_{p}. In case C is not true, the corresponding replacement is not executed. When applying Modus Ponens, the juxtaposition between B and O A_{p} leads to a formal logical contradiction. There is not such a contradiction when using the respective exclusion and the Modus Ponens rule. Hence, the formation of exclusions of E(C, A_{p}) type can lead to solution of the contradictions caused by incompleteness in the description of the object area.
In case C from formula (4) is true and exclusion E(C, A_{p}) connects it with the conjunct A_{p}, the significance of the last falls to zero. As a result of the defeasible reasoning considered, A_{p} is eliminated from the body of the respective rule of type (1), since its validity value does not influence the inference process of B. In the last variant of defeasible reasoning (5), when C is true, the respective conjunct A_{p} is directly replaced by C under the action of the exception E(C, A_{p}) attached to the rule.
If there are not any data for the coefficients pointed in (2), their values are accepted as equal. The general inference is made from scheme (4) that no matter whether the presence of reason C leads to A_{p} or O A_{p}, it causes the defeasibility! of the significance of the statement A_{p} confirming B, a _{p}=0 at that. Each one of the exclusions E(Cn ,A_{p}) considered can be replaced by the disjunctive expression (Cn E A_{p}).
The papers discussed suggest the use of an approach for defeasible reasoning in the formation of exclusions E(Cn ,A_{p}). In this way the combinatorial explosion in the search of all the exclusions for the statements from all the rules is avoided and more attention is paid to some definite situations leading to the activation of such analogies. One of the problems which appear is to represent a formal apparatus for defeasible reasoning on the basis of the known approaches for detection of partial similarities between different models [5]. The types of defeasible reasoning are discussed in detail in the next chapter. The application of defeasible type analogies increases the efficiency of the search and application of exclusions. Independently on these facts other (quantitative) methods have been investigated that enable a rise in the efficiency of these tools application and the removal of many shortcomings, typical for the nonquantitative methods.
Different models [6] are used in exact quantitative methods based on linear equalities and inequalities designed for the solution of various problems in connection with deductive logic. For this purpose a method is suggested in this paper for defeasible reasoning by analogy using flows on networks. In this case the choice of the most appropriate hypothesis is reduced to solving the corresponding networkflow optimisation problem, discussed in the third chapter.
3. DEFEASIBLE REASONING BY ANALOGY
The inference by analogy is based on the analysis of a partial similarity among the models investigated. Further on the clauses of Horn's type are called rules, and the statements C; A_{i}  facts. Let us consider different objects of the investigation from a defined object area (the approach suggested is objectindependent). The set of rules and facts, concerning a given object X, form its model: M(X). This model is identified with Herbrand model, and the object area  with Herbrand Universe. All the well formed formulas (facts) from M(X) are logical sequences of X. The analogy is based on juxtapositions and comparisons among different objects. The paper studies comparisons between models of some pairs from the set of objects: X_{1}, X_{2}. The purpose of transformation (the area, to which new knowledge is added), is connected with the object X_{1}, and the transformation basis (the area, in which appropriate exclusions are searched for)  with X_{2}. The comparisons must have mutually excluding character: two facts from M(X_{1}) cannot correspond to one fact from M(X_{2}) and vice versa. In the replacement of the variables by constants particular attention is paid to the excluding of uncertain factors. The features mentioned give the necessary but not sufficient conditions for inference by defeasible analogy.
Definition. Let us consider M(X_{1}). Defeasible analogy is the approach enabling the transfer by analogy of exclusions of the type C ® A_{p}, included in the models of other objects M(X_{j}) and on the basis of sufficient partial similarity between the objects X_{1} and X_{j}, exclusions are added to M(X_{1}). The same can change the deductive inference using defeasible reasoning (3), (4) or (5). Another type of defeasible reasoning allows forming by analogy (without direct transfer from other objects) of exclusions of the type C ® A_{p}.
It is necessary to note the absolute difference between our background definition for defeasible analogies and the defeasible reasoning of D. Note. In our case, if the exclusion considered E(C,A_{p}) concerning one message A_{p} is true and its area of operation covers the rule R_{i}, containing A_{p} in its head or body, then A_{p} is defeated. Hence, without altering the truth value of A_{p}, its connection with R_{i} changes in the following way. In the critical case the connection A_{p}R_{i} is interrupted: The significance of the information whether A_{p} is true or false becomes null in connection with the truth value of R_{i}. From the schemes above shown it follows that A_{p} can be simply cleared from the rule or replaced by another coincidence. The connection A_{p}R_{i} is altered in the general case. The change affects the significance of the fact whether A_{p} is true or not within the frames of the complete rule. The significance increases in some cases on the account of other messages, if there are such. In other cases it decreases, not obligatory to zero. Thus something similar to scales is introduced for the head and the body of R_{i}, on which the changes in the weight of one or a group of statements in connection with R_{i} are fixed. Finally this can change the truth value of R_{i}.
The exclusions can be specialised for one or a group of statements of one or more rules or for all the known rules of the domain. The paper discusses the different partial cases of the defeasible reasoning suggested by us. The discussion is restricted within the frames of Horn’s clauses, and the position of A_{p} is in the rules body.
Let us regard a rule of the type B ¬ A_{1} C A_{2} ... C A_{z}, assigning each A_{i} the corresponding a _{i}. Also, let the knowledge leading to the confirmation of any statement in A_{i} be called examples for B (because they do not support the confirmation of B). Similarity can be found with machine learning terms, for example. The knowledge leading to O A is called counterexamples for B. Then if C is true, the application of the exclusion C ® A_{p} alters the ratio between the examples sets and the counter examples for B, because A is eliminated in one of them. If the result of this is that one of the sets remains empty, the deductive inference is altered. The defeasible analogy is used with the purpose to eliminate the elements in one of the two sets and to change deductive inference. Usually it is described by formula (6), but the mechanism for exclusions application can be in three variants, that are formalised in (3), (4) or (5).
(6)
where S is the substitution mentioned at the beginning of the chapter, allowing the use of the exclusions available connected with other objects in M(X_{1}). If there is such a substitution in the upper line of (6), then exclusion transfer is realised (refer to the intermediate line in the formula) from M(X_{2}) in M(X_{1}). After the lowest line of inference in (6), the results from the use of the defeasible process C ® A_{p} in M(X_{1}) are pointed out. Four variants for the formation of y are investigated so that they can be used in a combination or apart. Independently on the variant selected, if the y (X_{1},X_{2})<T obtained is smaller than an apriori given value T, the hypothesis formed by analogy is rejected.
One of the most simple and efficient procedures in a computing complexity aspect for the formation of y is based on the estimate of the distance between X_{1} and X_{2} in the hierarchical network of objects. For this purpose relations ancestorpredecessor are used that are described in properties acquisition in deductive inference. Let each relation be interpreted by an arc with length 1, at the upper end of which a predecessor! is placed and at the lower  an ancestor. The neighbourhood (the distance) between the objects L(X_{1},X_{2}) is computed in the following way. If X_{1? }X_{2}, then L(X_{1},X_{2}) = 0 (maximal neighbourhood). In case X_{1} and X_{2} have a common predecessor, L(X_{1},X_{2}) = 1 and so on. If X_{1} and X_{2} have not a common predecessor at any hierarchical level, then L(X_{1},X_{2}) = ? . In the variant shown the analogies are done up to an apriori set value of L. The next chapter describes a scheme for defeasible reasoning by analogy, being described in the notions of deduction (Modus Ponens) and formalized by (7).
(7)
where E(C, A_{p}) is connected with X_{2}, and all the remaining statements  with X_{1}. Also, with the purpose to increase the efficiency of defeasible reasoning, it is suggested to use metacontrol of inference by analogy expressed in the use of analogies only in case that one of the sets of the examples and counter examples of the consequent of (1) contains no more than one element. It is suitable to make comparison between the defeasible reasoning suggested and other approaches for reasoning by analogy, at the first place the Haraguchi approach (refer to the first chapter). In order to discover the characteristic differences, it is sufficient to trace what the situation will be after the elimination of y from formula (6). In this case the analogy becomes practically uncontrollable and it cannot function in automatic mode of operation without an expert who has the task to remove the inconsistent hypotheses. The analogy described in one of the early works of Haraguchi is similar, being described in formal deductive inference notions.
4. FLOWS IN NETWORKS FOR INFERENCE BY ANALOGY
A flow interpretation of the inference is proposed in the present paper for formal defeasible reasoning using the terms from [7, 8]. Let the graph G(N,U) be given on a set of arcs U and nodes N. In this case the relation (7) can be represented as a network flow on graphs from Fig. 1.
Figure 1.
The graph is divided by dotted lines into areas, each one containing knowledge about one object X_{j}. The set of sources S contains all A_{i}, the exclusions E, y _{i}. The set of sinks T contains all tn , t_{0}, and t’. Then for all X,yI N the constraints from expression (8) are valid.
(8)
A_{i} corresponds to the arc flow functions f(a_{i},a); Cn , A_{p} and E(Cn ,A_{p})  to f(c_{i},r_{i}), f(a_{p},r_{i}), f(r_{i},a), respectively, and f(y _{i},a) is assigned initially the value 1, if y (X_{j},X_{1})<T or 0 otherwise. Some appropriate exclusions E(Cn ,A_{p}), i? j can be included in the knowledge about an object X_{j}. The pairs of the incoming arcs are disjunctively joint in the nodes r_{i}, and in nodes a and b_{2}  conjunctively. The functional relations v from formula (8) are formed as follows: v(a_{j})=f(a_{j},a); v(tj)=f(a,t_{j}).
Let the conjunction of all A_{i}, exclusions i, y _{i} be denoted by A, which corresponds to the arc (a,b_{2}). Then the implication A® B is set by the arc (b_{1},b_{2}) and as a result of the deductive inference f(b_{2},b_{3}) is computed, the value of which is a true estimate of B. Then the inference by analogy is represented by the following system of equalities and inequalities.
f(a,b_{2})f(a_{i},a)? 0; i=1,...z. ( 9)
f(a,b_{2})f(r_{j},a)? 0; j=1,...n. (10)
f(a,b_{2})f(r_{j},a)? 0; j=1,...n. (11)
f(r_{j},a)f(c_{j},r_{j})? 0; j=1,...n. (12)
2f(r_{j},a)f(c_{j},r_{j})f(a_{p},r_{1j})=0; j=1,...n. (13)
(14)
2f(b_{2},b_{3})f(a,b_{2})f(b_{1},b_{2})=0. (15)
f(r_{j},a) = 0 or 1. (16)
f(x,y)? 0; (x,y)I U. (17)
f(r_{j},t_{j})? 1. (18)
f(a,t’)? 2n+z2. (19)
f(b_{2},t_{0})? 1. (20)
The equations for preserving are given by formulas (13)(15), while the equations from (9) up to (12) guarantee that the conditions from the tables for the logical operations disjunction and conjunction are satisfied.
The problem for defeasible reasoning by analogy put is reduced to a linear programming problem from (9) up to (20) with the following objective function:
(21)
Fig. 1 shows one case of defeasibility of one of the conjuncts Ai by the antecedent of (1). In the general case several conjuncts can be defeated simultaneously, which leads to complication of the graphical representation and the system of formulas. As shown in chapter 1, this is not appropriate in most of the cases, since it can cause decrease of the efficiency in defeasible analogy application.
Similarly to the scheme for inference (7), scheme (6) is realised in a flow form of representation that leads to transformation of rules, but not to check of the probability value of statements as shown above. Usually all the modifications of exclusions from (3) up to (5) are used in the investigations, as well as an inference using efficiency coefficients (1). The modifications indicated do not alter the nature of the scheme for defeasible reasoning by analogy shown in Fig. 1.
5. CONCLUSIONS
The paper presented suggests a network flow approach for defeasible inference by analogy, as well as the possibilities for its application in artificial intelligence and decision support systems. The features and common characteristics of different types of defeasible reasoning are discussed.
A method is proposed in which the defeasible reasoning is done in a network flow form. In this approach the logical programming problems are reduced to the solution of the corresponding problems by exact quantitative methods. For this purpose linear network flow models are used and an extremal linear network problem is solved.
REFERENCES
1. Nute, D. Defeasible reasoning and decision support systems.  Decision Support Systems 4, 1988, 97110.
2. Nute, D., R. Mann, B. Brewer. Using defeasible logic to control selection of a business forecasting method. Proc. of the 21th Hawaii Int. Conf. on System Science. IEEE Comp. Soc. Press, Washington, DC, 1988.
3. Jotsov, V. Defeasible reasoning by using analogies. In Proc. IV Int. Conf. AIMSA’90, edited by P. Jorrand and V. Sgurev. North Holland, 1990, 285292.
4. Sgurev, V., V. Jotsov. Computational analogy: some resultes and perspectives.  J. Probl. of Ind. Cybern. and Robotics 46, 1997, 1220.
5. Haraguchi, M., S. Arikawa. Reasoning by analogy as a partial identity betwen models.  Lecture Notes in Computer Science 265, edited by K. Jantke, Springer, Berlin, 1986, 6187.
6. Jeroslow, R. LogicBased Decision Support. NorthHolland, N.Y., 1986.
7. Sgurev, V.S., M.N. Djelatova. Maximal Linear Flow and Capacity of a Cutting Set.  Problems of Engineering Cybernetics and Robotics, 25, 1986, 310.
8. Sgurev, V.S. A Maximum Network Flow and a Capacity in Networks with Nonlinear Constrains.  Problems of Engineering Cybernetics and Robotics, 31, 1990, 1822.
Site of Information
Technologies Designed by inftech@webservis.ru. 
