Context-Dependent Deductive and Inductive Reasoning Based on Good Diagnostic Tests Xenia Naidenova1 and Vladimir Parkhomenko2 1 Military Medical Academy, Saint-Petersburg, Russia ksennaidd@gmail.com 2 Peter the Great St. Petersburg Polytechnic University, St. Petersburg, Russia parhomenko.v@gmail.com Abstract. A sketch of classification reasoning is given in the paper. The key ideas of the reasoning are ideas of classification and its good approximations based on good diagnostic tests. Such good tests, which are maximally redundant (GMRTs), i.e. their subsets of attributes are closed, are considered. Classification reasoning embraces two interrelated processes: inductive inferring implicative assertions based on GMRTs and using these assertions in deductive steps of reasoning. A peculiarity of our inductive model of classification reasoning is the control and trans- formation of subcontexts during inductive phase of reasoning by the use of deductive reasoning rules, for example the rules prohibiting some pairs of attributive values. Keywords: good diagnostic test, classification reasoning, essential at- tributes, essential objects, implications, subcontexts, deduction, induc- tion, closed sets 1 Introduction Classification reasoning is a part of commonsense (plausible) reasoning based on two kinds of logical rules extracted from observable datasets (functional and implicative dependencies). The principle concepts of this reasoning are the con- cepts of classification and its good approximations. We assume that objects are described by a set U of symbolic or numeric attributes. To give a target clas- sification of objects, we use an additional attribute KL not belonging to U . A target attribute partitions a given set of objects into disjoint classes the number of which is equal to the number of values of this attribute. In Tab. 1, we have two classes: KL+ (positive objects) and KL− (negative objects). We concentrate on the case of object classification into two classes and task of concept formation [2,5]. The goal of this task is to describe/classify new objects according to description/classification of existing objects. Inferring good diag- nostic tests (GDTs) is the formation of the best descriptions of a given object class KL+ against the objects not belonging to this class (KL− ). Let M = {∪dom(attr), attr ∈ U }, where dom(attr) is the set of all values of attr. Let X ⊆ M and G be the set of indices of objects considered (objects c 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. Local Proceedings also appeared in ISBN 978-84-606-7410-8, Universidad de Málaga (Dept. Matemática Aplicada), Spain. 66 Xenia Naidenova and Vladimir Parkhomenko Table 1. Motivating Example of classification No Height Color of Hair Color of Eyes KL 1 Low Blond Blue KL+ 2 Low Brown Blue KL− 3 Tall Brown Hazel KL− 4 Tall Blond Hazel KL− 5 Tall Brown Blue KL− 6 Low Blond Hazel KL− 7 Tall Red Blue KL+ 8 Tall Blond Blue KL+ for short), G = G+ ∪ G− , where G+ and G− the sets of positive and negative objects, respectively. Denote by d(g) the description of object g ∈ G. Let P(X) = {g | g ∈ G, X ⊆ d(g)}. We call P(X) the interpretation of X in the power set 2G . If P(X) contains only positive objects and the number of these objects more than 2, then we call X a description of some positive objects and (P(X), X) a test for positive objects. Let us define a good test or good description of objects. Definition 1. A set X ⊆ M of attribute values is a good description of positive (negative) objects if and only if it is the description of these objects and no such subset Y ⊆ M exists, that P(X) ⊂ P(Y ) ⊆ G+ . It can be seen [15,11,1] that this problem is reduced to searching for causal dependencies in the form X → v, X ⊆ M, v is value of attribute KL for all positive (negative) objects. Sec.2 describes an approach to classification reasoning based on implications. Sec.3 describes the definitions of Good Test Analysis. Sec.4 presents the de- composition of inferring good tests into two kinds of subtasks. An approach to selecting and ordering subcontexts is given in Subsec.5.1. Some situations of re- ducing the classification context are considered in Subsec.5.2. A set of examples illustrates all the considerations. 2 Classification Reasoning Classification reasoning based on GDTs embraces two interrelated processes: inductive inferring implicative assertions and using them for pattern recognition problems. We need the following three types of logical rules in order to realize classification reasoning (deductive and inductive): – INSTANCES or relationships between objects or facts really observed. In- stance can be considered as a logical rule with the least degree of general- ization. On the other hand, instances can serve as a source of training set of positive and negative examples for inductive inference of generalized rules. Context-Dependent Reasoning Based on Good Diagnostic Tests 67 – RULES OF THE FIRST TYPE or logical assertions. These rules describe regular relationships between objects and their properties, between proper- ties of different objects, between objects and their classes. The rules of the first type can be given explicitly by an expert or derived automatically from instances with the help of some learning process. These rules are represented, in the paper, in the form of implications. – RULES OF THE SECOND TYPE or commonsense reasoning rules with the help of which rules of the first type are used, updated, and inferred from data (instances). The rules of the second type embrace both inductive and deductive reasoning rules. The rules of the first type can be represented with the use of only one class of logical statements based on implicative dependencies between names. Names are used for designating concepts, things, events, situations, or any evidences. They can be considered as attributes and attributes’ values in the formal repre- sentations of logical rules. 1. Implication: a, b, c → d. This rule means that if the values standing on the left side of rule are simultaneously true, then the value on the right side of rule is always true. 2. Interdiction or forbidden rule (a special case of implication): a, b, c → f alse (never). This rule interdicts a combination of values enumerated on the left side of rule. The rule of interdiction can be transformed into several implications such as a, b →not c; a, c →not b; b, c →not a. 3. Compatibility: a, b, c → VA where VA is the frequency of occurrence of rule. The compatibility is equivalent to the following implications: a, b → c, VA ; a, c → b, VA; b, c → b, VA. Generally, the compatibility rule represents the most common combination of values, which is characterized by an insignificant number of exceptions (contrary examples) from regularity. 4. Diagnostic rule: x, d → a; x, b →not a; d, b → f alse. For example, d and b can be two values of the same attribute. This rule works when the truth of ’x’ has been proven and it is necessary to determine whether ’a’ is true or not. If ’x&d’ is true, then ’a’ is true, if ’x&b’ is true, then ’a’ is f alse. 5. Rule of alternatives: a or b → true (always); a, b → f alse. This rule says that a and b cannot be simultaneously true, either a or b can be true but not both. This rule is a variant of interdiction. Deductive steps of classification reasoning consist of inferring consequences from some observed facts with the use of implications (i.e. knowledge). For this goal, deductive rules of reasoning are applied the main forms of which are modus ponens, modus tollens, modus ponendo tollens, and modus tollendo ponens. Let x be a set of true values of some attributes observed simultaneously. Deductive reasoning rules of the second type are: 1. Using implication: Let r be an implication, left(r) be the left part of r and right(r) be the right part of r. If left(r) ⊆ x, then x can be extended by 68 Xenia Naidenova and Vladimir Parkhomenko right(r) : x ← x ∪ right(r). Using implication is based on modus ponens: if A, then B; A; hence B. 2. Using interdiction: Let r be an implication y →not k. If left(r) ⊆ x, then k is the forbidden value for all extensions of x. Using interdiction is based on modus ponendo tollens: either A or B (A, B — alternatives); A; hence not B; either A or B; B; hence not A. 3. Using compatibility: Let r = ’a, b, c → k, VA’. If left(r) ⊆ x, then k can be used to extend x along with the calculated value VA for this extension (a special consideration is required for calculating VA). 4. Using diagnostic rules: Let r be a diagnostic rule such as ’x, d → a; x, b →not a’, where ’x’ is true, and ’a’, ’not a’ are hypotheses or possible values of some attribute. Using the diagnostic rule is based on modus ponens and modus ponendo tollens. There are several ways for refuting one of the hypotheses: – To infer either d or b by using existing knowledge; – To involve new known facts (extended context) and/or propositions for inferring (with the use of inductive reasoning rules of the second type) new implications for distinguishing between the hypotheses ’a’ and ’not a’; to apply the newly obtained rules; – To get the direct answer on whether d or b is true by involving an external source of knowledge. 5. Using rule of alternatives: Let ’a’ and ’b’ be two alternatives (mutually ex- clusive) hypotheses about the value of some attribute, and the truth of one of hypotheses has been established, then the second hypothesis is rejected. Using the rule is based on modus tollendo ponens: either A or B (A, B — alternatives); not A; hence B; either A or B; not B; hence A. We can call the rules listed above the rules of “forward inference”. However, we have in natural classification reasoning so called “backward inference”. 6. Generating hypothesis or abduction rule. Let r be an implication y → k. We have “if k is true, then y may be true”. 7. Using modus tollens. Let r be an implication y → k. If ’not k’ is inferred, then ’not y’ is also inferred. When applied, the above given rules generate the reasoning, which is not demonstrative. The purpose of it is to infer all possible hypotheses of the value of some objective attribute. It is essential that hypotheses do not contradict with knowledge (first-type rules) and the observable real situation, where the reason- ing takes place (contextual knowledge). Inference of hypotheses is reduced to constructing all intrinsically consistent extensions of a set of values in which the number of involved attributes is maximum possible (there are no prohibited pairs of values in such extensions). All hypotheses have different admissibility determined by the quantity and “quality” of compatibility rules involved in rea- soning. A very simple structure of knowledge base (KB) and an example of applying the rules of second type for a pattern recognition problem can be found in [19]. The process of deductive reasoning can require inferring new rules of the first type from data when i) the result of reasoning contains several hypotheses and Context-Dependent Reasoning Based on Good Diagnostic Tests 69 it is impossible to choose one and only one of them (uncertainty), and ii) it is impossible to infer any hypothesis. Inductive steps of classification reasoning consist in using already known facts, observations and experimental results for inferring implications and their correcting. The main forms of induction have been formulated by J. Stuart Mill [12]. The formalization of these forms of induction has been offered by V.K. Finn [6]. For inferring GDTs, the Combined Similarity and Difference Method of the Mill are used and realized by means of inductive inference rules of the second type proposed in [13]. Deductive rules of the second type described above also work for inductive inferring implications since implications obtained are involved immediately to reduce the search space. In the paper, we shall illustrate using the forbidden and diagnostic rules of the second type for GDTs inferring. 3 Key Notions of Good Test Analysis Assume that G = 1, N be the set of objects and M = {m1 , m2 , . . . , mj , . . . mm } be the set of values. The object descriptions are represented by rows of a table, columns of which are associated with the attributes taking their values in M (see, please, Tab.1). Denote by {Bg | Bg ⊆ M, g ∈ G} the description of an object. The Galois connection [21] between the ordered sets (2G , ⊆) and (2M , ⊆), i.e. 2G → 2M and 2M → 2G , is defined by the following mappings called derivation operators (see although different notations in [16,9]): for A ⊆ G and B ⊆ M , A0 = val(A) = {intersection of all Bg | Bg ⊆ M, g ∈ A} and B 0 = obj(B) = {g| g ∈ G, B ⊆ Bg }. We consider obj(B) = {intersection of all obj(m)| obj(m) ⊆ G, m ∈ B}. In the Formal Concept Analysis, for g ∈ G and m ∈ M , {g}0 or simply g 0 is called object intent, and {m}0 or simply m0 is called attribute extent [7]. There are two closure operators [16]: generalization of(B) = B 00 = val(obj(B)) and generalization of(A) = A00 = obj(val(A)). A set A is closed if A = obj(val(A)) and a set B is closed if B = val(obj(B)). If A0 = B & B 0 = A, then a pair (A, B) is called a formal concept, subsets A and B of which are called concept extent and intent, respectively. A triple (G, M, I), where I is a binary relation G × M is called a formal context K. Let K := (G , M, I ) and I := I ∩ (G × M ), where  ∈ {+, −} (one can add the value τ if there is an undefined object) [8]. K± := (G+ ∪ G− , M ∪ {KL}, I+ ∪ I− ∪ (G± × {KL})). Definition 2. A Diagnostic (classification) Test (DT) for G+ is a pair (A, B) such that B ⊆ M , A = obj(B) 6= ∅, A ⊆ G+ , and B 6⊆ val(g), ∀g ∈ G− . Equivalently, obj(B) ∩ G− = ∅. Definition 3. A DT (A, B) for G+ is maximally redundant if obj(B ∪ m) ⊂ A for all m ∈ / B and m ∈ M . Definition 4. A DT (A, B) for G+ is irredundant if any narrowing B∗ = B \ m, m ∈ B implies that (obj(B∗ ), B∗ )) is not a test for G+ . 70 Xenia Naidenova and Vladimir Parkhomenko Definition 5. A DT (A, B) for G+ is good if and only if any extension A∗ = / A, i ∈ G+ implies that (A∗ , val(A∗ )) is not a test for G+ . A ∪ i, i ∈ If a good test (A, B) for G+ is maximally redundant (GMRT), then any extension B∗ = B ∪ m, m ∈ / B, m ∈ M implies that (obj(B∗ ), B∗ ) is not a good test for G+ . The relation GMRTs to the Formal Concept Analysis is considered in [17]. Any object description d(g), g ∈ G in a given classification context is a maxi- mally redundant set of values because ∀m ∈ / d(g), m ∈ M, obj(d(g) ∪ m) is equal to ∅. In Tab.1, ((1, 8), Blond Blue) is a GMRT for KL+ , ((4, 6), Blond Hazel) is a maximally redundant test for KL− but not a good one, and ((3, 4, 6), Hazel) is a good maximally redundant and, simultaneously, good irredundant test for KL− . 4 Decomposition of Inferring GMRTs into Subtasks There are two kinds of subtasks for inferring GMRTs: 1. given a set of values B, where B ⊆ M, obj(B) 6= ∅, B 6⊆ d(g), ∀g ∈ G− , find all GMRTs (obj(B∗ ), B∗ ) such that B∗ ⊂ B; 2. given a non-empty set of values X ⊆ M such that (obj(X), X) is not a test for positive objects, find all GMRTs (obj(Y ), Y ) such that X ⊂ Y . For solving these subtasks we need to form subcontexts of a given classifica- tion context K± . In the first case, we have to include in subcontext all positive objects, the descriptions of which intersect B. The subtask is useful to find all GMRTs intents of which are contained in the description d(g) of an object g. This subtask is considered in [5] for fast incremental concept formation. The fol- lowing notions of object and value projections are developed to form subcontexts [18]. Definition 6. The projection proj(d(g)), g ∈ G+ on the set D+ , where D+ is the set of descriptions of all positive objects, is denoted by {z| z = d(g) ∩ d(g∗ ) 6= ∅, d(g∗ ) ∈ D+ & (obj(z), z) is a test for G+ }. Note that d(g) ∈ proj(d(g)). Definition 7. The value projection on a given set D+ proj(B) is {d(g) | B ⊆ d(g), d(g) ∈ D+ } or, equivalently, proj(B) = {d(g) | g ∈ (obj(B) ∩ G+ )}. The projections define the methods to construct two kinds of subcontexts of K± . The following theorem gives the foundation of reducing subcontexts [14]. Theorem 1. Let X ⊆ M, (obj(X), X) be a maximally redundant test for pos- itive objects and obj(m) ⊆ obj(X), m ∈ M . Then m can not belong to any GMRT for positive objects different from (obj(X), X). Context-Dependent Reasoning Based on Good Diagnostic Tests 71 Let splus(m) be obj(m)∩G+ (obj(m)∩G− ) and SPLUS={splus(m), m ∈ M }. Consider an example of reducing subcontext in Tab. 1. For values Hazel, Brown, Tall, Blue, Blond, and Low, SPLUS={obj(m)∩G− } = {{3, 4, 6}, {2, 3, 5}, {3, 4, 5}, {2, 5}, {4, 6}, {2, 6}}. We have val(obj(Hazel)) = Hazel, hence ((3,4,6), Hazel) is a test for G− . Then value Blond can be deleted from consideration, because splus(Blond) ⊂ splus(Hazel). It is essential that the projection is a subset of object descriptions defined on a certain restricted subset t∗ ⊆ M of values. Let s∗ be the subset of objects, descriptions of which produce the projection. In the projection, splus(m) = obj(m) ∩ s∗ , m ∈ t∗ . Let STGOOD be the partially ordered set of elements s such that (s, val(s)) is a good test for D+ . Forming the Set STGOOD. The important part of our basic recursive algorithm is how to form the set STGOOD. Let L = (2S , ≤) be the set lattice [22]. The ordering determined in the set lattice coincides with the set-theoretical inclusion. Subset s1 is absorbed by subset s2 , i.e. s1 ≤ s2 , if and only if s1 ⊆ s2 . Under formation of STGOOD, subset s ⊆ G+ is stored in STGOOD if and only if it is not absorbed by any element of this set. It is necessary also to delete from STGOOD all the elements that are absorbed by s if s is stored in STGOOD. Thus, when the algorithm is over, the set STGOOD contains all the collections of objects that are the extents of GMRTs and only such collections. The set TGOOD of all the GMRTs is obtained as follows: TGOOD = {tg| tg = (s, val(s)), s ∈ STGOOD}. The basic recursive procedure for solving any kind of subtasks has been described in [20]. 5 Selecting and Ordering Subcontexts and Inferring GMRTs Algorithms of GMRTs inferring are constructed by the rules of selecting and ordering subcontexts of the main classification context. Before entering into the details, we give some new definitions. Definition 8. Let t be a set of values such that (obj(t), t) is a test for G+ . The value m ∈ M, m ∈ t is essential in t if (obj(t \ m), (t \ m)) is not a test for a given set of objects. Generally, we are interested in finding the maximal subset sbmax(t) ⊂ t such that (obj(t), t) is a test but (obj(sbmax(t)), sbmax(t)) is not a test for a given set of positive objects. Then sbmin(t) = t \ sbmax(t) is a minimal set of essential values in t. Definition 9. Let s ⊆ G+ , assume also that (s, val(s)) is not a test. The object g, g ∈ s is said to be an essential in s if (s \ g, val(s \ g)) proves to be a test for a given set of positive objects. 72 Xenia Naidenova and Vladimir Parkhomenko Generally, we are interested in finding the maximal subset sbmax(s) ⊂ s such that (s, val(s)) is not a test but (sbmax(s), val(sbmax(s))) is a test for a given set of positive objects. Then sbmin(s) = s \ sbmax(s) is a minimal set of essential objects in s. Finding quasi-maximal (minimal) subsets of objects and values is the key procedure behind searching for initial content of STGOOD and determining the number of subtasks to be solved. 5.1 Using the Diagnostic Rule of the Second Type An Approach for Searching for Initial Content of STGOOD. In the beginning of inferring GMRTs, the set STGOOD is empty. Next we describe the procedure to obtain an initial content of it. This procedure extracts a quasi- maximal subset s∗ ⊆ G+ , which is the extent of a test for G+ (maybe not good). We begin with the first object g1 of s∗ , then we take the next object g2 of s∗ and evaluate the function to be test({g1 , g2 }, val({g1 , g2 })). If the value of the function is true, then we take the next object g3 of s∗ and evaluate the function to be test({g1 , g2 , g3 }, val({g1 , g2 , g3 })). If the value of the function to be test({g1 , g2 }, val({g1 , g2 })) is f alse, then the object g2 of s∗ is skipped and the function to be test({g1 , g3 }, val({g1 , g3 }))) is evaluated. We continue this process until we achieve the last object of s∗ . This procedure can be considered as a realization of the diagnostic rule of the second type. To illustrate this procedure, we use the sets D+ and D− represented in Tab.2 and 3 (our illustrative example). In these tables M = {m1 , . . . , m26 }. The set SPLUS0 for positive class of objects is in Tab.4. The initial content of STGOOD0 is {(2,10), (3, 10), (3, 8), (4, 12), (1, 4, 7), (1, 5,12), (2, 7, 8), (3, 7, 12), (1, 2, 12, 14), (2, 3, 4, 7), (4, 6, 8, 11)}. In what follows, we denote subsets of values {m8 , m9 }, {m14 , m15 } by ma and mb , respectively. Applying operation generalization of(s) = s00 = obj(val(s)) to ∀s ∈ STGOOD, we obtain STGOOD1 = {(2,10), (3, 10), (3, 8), (4, 7, 12), (1, 4, 7), (1, 5,12), (2, 7, 8), (3, 7, 12), (1, 2, 12, 14), (2, 3, 4, 7), (4, 6, 8, 11)}. By Th.1, we can delete value m12 from consideration, see splus(m12 ) in Tab.4. The initial content of STGOOD allows to decrease the number of using the procedure to be test() and the number of putting extents of tests into STGOOD. The number of subtasks to be solved. This number is determined by the number of essential values in the set M . The quasi-minimal subset of essential values in M can be found by a procedure analogous to the procedure applicable to search for the initial content of STGOOD. As a result of this procedure, we have quasi-maximal subset sbmax(M ) of M , such that (obj(sbmax(M )), sbmax(M )) is not a test for positive examples. Then subset LEV = M \sbmax(M ) is quasi-minimal subset of essential values in M . We have the following LEV : {m16 , m18 , m19 , m20 , m21 , m22 , m23 , m24 , m26 }. Note, that searching for the number of subtasks to be solved is also based on using the diagnostic rule of the second type. Context-Dependent Reasoning Based on Good Diagnostic Tests 73 Table 2. The set D+ of positive object descriptions G D+ 1 m1 m2 m5 m6 m21 m23 m24 m26 2 m4 m7 m8 m9 m12 m14 m15 m22 m23 m24 m26 3 m3 m4 m7 m12 m13 m14 m15 m18 m19 m24 m26 4 m1 m4 m5 m6 m7 m12 m14 m15 m16 m20 m21 m24 m26 5 m2 m6 m23 m24 6 m7 m20 m21 m26 7 m3 m4 m5 m6 m12 m14 m15 m20 m22 m24 m26 8 m3 m6 m7 m8 m9 m13 m14 m15 m19 m20 m21 m22 9 m16 m18 m19 m20 m21 m22 m26 10 m2 m3 m4 m5 m6 m8 m9 m13 m18 m20 m21 m26 11 m1 m2 m3 m7 m19 m20 m21 m22 m26 12 m2 m3 m16 m20 m21 m23 m24 m26 13 m1 m4 m18 m19 m23 m26 14 m23 m24 m26 Table 3. The set D− of negative object descriptions G D− G D− 15 m3 m8 m16 m23 m24 32 m1 m2 m3 m7 m9 m13 m18 16 m7 m8 m9 m16 m18 33 m1 m5 m6 m8 m9 m19 m20 m22 17 m1 m21 m22 m24 m26 34 m2 m8 m9 m18 m20 m21 m22 m23 m26 18 m1 m7 m8 m9 m13 m16 35 m1 m2 m4 m5 m6 m7 m9 m13 m16 19 m2 m6 m7 m9 m21 m23 36 m1 m2 m6 m7 m8 m13 m16 m18 20 m19 m20 m21 m22 m24 37 m1 m2 m3 m4 m5 m6 m7 m12 m14 m15 m16 21 m1 m20 m21 m22 m23 m24 38 m1 m2 m3 m4 m5 m6 m9 m12 m13 m16 22 m1 m3 m6 m7 m9 m16 39 m1 m2 m3 m4 m5 m6 m14 m15 m19 m20 m23 m26 23 m2 m6 m8 m9 m14 m15 m16 40 m2 m3 m4 m5 m6 m7 m12 m13 m14 m15 m16 24 m1 m4 m5 m6 m7 m8 m16 41 m2 m3 m4 m5 m6 m7 m9 m12 m13 m14 m15 m19 25 m7 m13 m19 m20 m22 m26 42 m1 m2 m3 m4 m5 m6 m12 m16 m18 m19 m20 m21 m26 26 m1 m2 m3 m5 m6 m7 m16 43 m4 m5 m6 m7 m8 m9 m12 m13 m14 m15 m16 27 m1 m2 m3 m5 m6 m13 m18 44 m3 m4 m5 m6 m8 m9 m12 m13 m14 m15 m18 m19 28 m1 m3 m7 m13 m19 m21 45 m1 m2 m3 m4 m5 m6 m7 m8 m9 m12 m13 m14 m15 29 m1 m4 m5 m6 m7 m8 m13 m16 46 m1 m3 m4 m5 m6 m7 m12 m13 m14 m15 m16 m23 m24 30 m1 m2 m3 m6 m12 m14 m15 m16 47 m1 m2 m3 m4 m5 m6 m8 m9 m12 m14 m16 m18 m22 31 m1 m2 m5 m6 m14 m15 m16 m26 48 m2 m8 m9 m12 m14 m15 m16 74 Xenia Naidenova and Vladimir Parkhomenko Table 4. The set SPLUS0 splus(m), m ∈ M splus(m), m ∈ M splus(ma ) → {2, 8, 10} splus(m22 ) → {2, 7, 8, 9, 11} splus(m13 ) → {3, 8, 10} splus(m23 ) → {1, 2, 5, 12, 13, 14} splus(m16 ) → {4, 9, 12} splus(m3 ) → {3, 7, 8, 10, 11, 12} splus(m1 ) → {1, 4, 11, 13} splus(m4 ) → {2, 3, 4, 7, 10, 13} splus(m5 ) → {1, 4, 7, 10} splus(m6 ) → {1, 4, 5, 7, 8, 10} splus(m12 ) → {2, 3, 4, 7} splus(m7 ) → {2, 3, 4, 6, 8, 11} splus(m18 ) → {3, 9, 10, 13} splus(m24 ) → {1, 2, 3, 4, 5, 7, 12, 14} splus(m2 ) → {1, 5, 10, 11, 12} splus(m20 ) → {4, 6, 7, 8, 9, 10, 11, 12} splus(mb ) → {2, 3, 4, 7, 8} splus(m21 ) → {1, 4, 6, 8, 9, 10, 11, 12} splus(m19 ) → {3, 8, 9, 11, 13} splus(m26 ) → {1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 14} Proposition 1. Each essential value is included at least in one positive object description. Proof. Assume that for an object description tg , g ∈ G+ , we have tg ∩ LEV = ∅. Then tg ⊆ M \ LEV. But M \ LEV is included at least in one of the negative object descriptions and, consequently, tg also possesses this property. But it contradicts to the fact that tg is the description of a positive object. t u Proposition 2. Assume that X ⊆ M . If X ∩ LEV = ∅, then to be test(obj(X), X) = f alse. Proposition 3. Let K± be a given classification context. For finding all GRMTs containing in K± , it is sufficient to solve this problem only for subcontexts asso- ciated with essential values in M (the set LEV). Proposition 2 is the consequence of Proposition 1. The poof of Proposition 3 is obvious. Note that the description of t14 = {m23 , m24 , m26 } is closed because of obj{m23 , m24 , m26 } = {1, 2, 12, 14} and val{1, 2, 12, 14} = {m23 , m24 , m26 }. We also know that s = {1, 2, 12, 14} is closed too (we obtained this result during generalization of elements of STGOOD). So (obj({m23 , m24 , m26 }), {m23 , m24 , m26 }) is a maximally redundant test for positive objects and we can, conse- quently, delete t14 from consideration. As a result of deleting m12 and t14 , we have the modified set SPLUS (Tab.5). 5.2 Using the Rule of Alternative for Splitting Subcontexts Essentially, searching for GMRTs turns out a process of generating deductive reasoning rules of the first type, which are used immediately during this process. Now we shall give an example of constructing and using the rules of alternative (forbidden rules). Context-Dependent Reasoning Based on Good Diagnostic Tests 75 Table 5. The set SPLUS1 splus(m), m ∈ M splus(m), m ∈ M splus(ma ) → {2, 8, 10} splus(m22 ) → {2, 7, 8, 9, 11} splus(m13 ) → {3, 8, 10} splus(m23 ) → {1, 2, 5, 12, 13} splus(m16 ) → {4, 9, 12} splus(m3 ) → {3, 7, 8, 10, 11, 12} splus(m1 ) → {1, 4, 11, 13} splus(m4 ) → {2, 3, 4, 7, 10, 13} splus(m5 ) → {1, 4, 7, 10} splus(m6 ) → {1, 4, 5, 7, 8, 10} splus(m7 ) → {2, 3, 4, 6, 8, 11} splus(m18 ) → {3, 9, 10, 13} splus(m24 ) → {1, 2, 3, 4, 5, 7, 12} splus(m2 ) → {1, 5, 10, 11, 12} splus(m20 ) → {4, 6, 7, 8, 9, 10, 11, 12} splus(mb ) → {2, 3, 4, 7, 8} splus(m21 ) → {1, 4, 6, 8, 9, 10, 11, 12} splus(m19 ) → {3, 8, 9, 11, 13} splus(m26 ) → {1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13} Form all the pairs of objects (i, j) ⊆ G+ ; form a set FR of forbidden pairs of objects, FR = {(i, j) : to be test((i, j), val(i, j)) is f alse} (Tab. 6); then the set of admissible pairs is ADM = {(i, j) : to be test((i, j), val(i, j)) is true} (Tab. 6). Each forbidden pair (i, j) generates rule of alternative: j OR i → true(always); i, j → f alse. This rule says that i and j cannot simultaneously enter in any ex- tent of GMRTs, either i or j but not both. These rules of alternatives allow splitting any splus(m), m ∈ M into subsets not containing any forbidden pair of objects. An example is in Tab. 7. As a result of splitting, we shall obtain the splitting tree, leaves of which are subsets of objects not containing any prohibited object pairs. Subcontexts for GMRTs inferring are leaves of the tree with the number of objects more or equal to 4. So, in Tab. 7, we have only one subcontext (4,7,8,11) for searching for tests. As far as triplets of objects, if a triplet is not the extent of a test, then we have all information about pairs of objects contained in it. An analysis of set ADM leads to using some inductive reasoning rules [19]. If element j enters in sq+1 , then it must enter in q proper subsets of sq+1 , where sq+1 is a set containing (q + 1) elements. If we observe that j enters in only one doublet (pair), then it cannot enter in any triplet. If we observe that j enters in only one triplet, then it cannot enter in any quadruplet and so on. If an element enters in two and only two doublets, it means that it will enter only in one triplet. If an element enters in three and only three doublets, it can enter in only one quadruplet. This inductive reasoning is applicable to constructing triplets from doublets, quadruplets from triplets and so on. In our example: Object 9 enters in one and only one doublet, hence (9,11) cannot be included in any triplet. We conclude that (9,11) is the extent of a GMRT. Object 5 enters in two and only two pairs, hence it is included in only one triplet (1,5,12) already contained in the initial content of STGOOD. Object 5 cannot be included in any quadruplet. Object 6 76 Xenia Naidenova and Vladimir Parkhomenko Table 6. Classification of object pairs g Admissible pairs of objects Forbidden pairs of objects (1,3) (1,6) (1,8) (1,9) (1,10) 1 (1,2) (1,4) (1,5) (1,7) (1,12) (1,11) (1,13) 2 (2,1) (2,3) (2,4) (2,7) (2,8) (2,10) (2,12) (2,5) (2,6) (2,9) (2,11) (2,13) 3 (3,2) (3,4) (3,7) (3,8) (3,10) (3,11) (3,12) (3,1) (3,5) (3,6) (3,9) (3,13) 4 (4,1) (4,2) (4,3) (4, 6) (4,7) (4,8) (4,11) (4,12) (4,5) (4,9) (4,10) (4,13) (5,2) (5,3) (5,4) (5,6) (5,7) 5 (5,1) (5,12) (5,8) (5,9) (5,10) (5,11) (5,13) (6,1) (6,2) (6,3) (6,5) (6,7) 6 (6,4) (6,8) (6,11) (6,9) (6,10) (6,12) (6,13) 7 (7,1) (7,2) (7,3) (7,4) (7,8) (7,11) (7,12) (7,5) (7, 6) (7,9) (7,10) (7,13) 8 (8,2)(8,3)(8,4) (8,6)(8,7) (8,10) (8,11) (8,1) (8,5) (8,9) (8,12) (8,13) 9 (9,11) All the other pairs (10,1) (10,4) (5,10) (10,6) (10,7) 10 (10,2) (10,3) (10,8) (10,9) (10,11) (10,12) (10,13) (11,1) (11,2) (5,11) (11,9) 11 (11,3) (11,4) (6,11) (7,11) (11,9) (11, 10) (11, 12) (11,13) (12,6) (12,8) (12,9) (12,10) 12 (12,1) (12,2) (12,3) (12,4) (12,5) (12,7) (12,11) (12,13) 13 ∅ All the pairs Table 7. An example of splitting splus(m2 ) No splus(m2 ) Forbidden pair 1 (4,7,8,11,12) (8,12) 2 (4,7,8,11), (4,7,11,12) 3 (4,7,11,12) (11,12) 4 (4,7,11) (4,7,12) Context-Dependent Reasoning Based on Good Diagnostic Tests 77 enters in three and only three pairs, hence it is included in only one quadruplet (4,6,8,11), already contained in STGOOD. Object 13 is not included in any admissible pair of objects. We put {9, 11} and {13} into STGOOD and delete objects 9, 5, 6, and 13 from consideration. This action implies deleting values m16 , m18 , and m23 (see, please Tab. 8), because splus(mi ), where i take values 16, 18 or 23, are absorbed by some elements of STGOOD. Table 8. The set SPLUS2 splus(m), m ∈ M splus(m), m ∈ M splus(ma ) → {2, 8, 10} splus(m22 ) → {2, 7, 8, 11} splus(m13 ) → {3, 8, 10} splus(m23 ) → {1, 2, 12} splus(m16 ) → {4, 12} splus(m3 ) → {3, 7, 8, 10, 11, 12} splus(m1 ) → {1, 4, 11} splus(m4 ) → {2, 3, 4, 7, 10, 13} splus(m5 ) → {1, 4, 7, 10} splus(m6 ) → {1, 4, 7, 8, 10} splus(m7 ) → {2, 3, 4, 6, 8, 11} splus(m18 ) → {3, 10} splus(m24 ) → {1, 2, 3, 4, 7, 12} splus(m2 ) → {1, 10, 11, 12} splus(m20 ) → {4, 7, 8, 10, 11, 12} splus(mb ) → {2, 3, 4, 7, 8} splus(m21 ) → {1, 4, 8, 9, 10, 11, 12} splus(m19 ) → {3, 8, 11} splus(m26 ) → {1, 2, 3, 4, 7, 10, 11, 12} We analyze triplets in SPLUS: splus(m∗ ) = {2, 8, 10}, splus(m1 ) = {1, 4, 11}, splus(m19 ) = {3, 8, 11}, and splus(m13 ) = {3, 8, 10}. As a result, we obtain the extents of two new GMRTs {3, 11} and {8, 10}. After that, we can delete object 10. Then we can delete values m5 , m2 , and m4 after analyzing their modified splus. Now we split splus(m22 ), splus(m20 ), splus(m21 ), splus(m24 ), and splus(m26 ), because these values are the only remaining essential values in the set LEV. Tab. 9 shows the number of subtasks in splitting trees for these essential values and new obtained tests. Table 9. Splitting splus(m), m is essential value splus(m) The number of subtasks New tests Deleted elements splus(m22 ) {7, 8, 11} m26 splus(m20 ) 1 m20 splus(m21 ) m21 , t8 m24 , t1 , t12 , t7 ; remaining set splus(m24 ) 2 of indices {2, 3, 4} is absorbed by element {2, 3, 4, 7} in STGOOD 78 Xenia Naidenova and Vladimir Parkhomenko Some words about future investigations. The most important mathematical tasks worth solving are the following: 1. For irredundant splus(m) to determine whether it contains extents of new GMRTs; 2. Optimization of selecting forbidden pairs of objects in order not to obtain repetition of subsets in splitting trees. 6 Conclusion A sketch of classification reasoning is given in the paper. The key notions of the reasoning are notions of classification and its good approximations based on good diagnostic tests. The good diagnostic tests have the dual nature: they generate functional and implicative dependencies and, in the same time, sets of objects satisfying these dependencies. The dependencies are logical assertions on the base of which deductive phase of classification reasoning is realized. In the paper, we deal only with GMRTs as value implications. An algorithm for inferring GMRTs from a set of data is given. A decomposition of the main task of inferring GMRTs into subtasks associated with the certain types of sub- contexts is introduced. There are various ways of using the proposed decompositions and extracted initial information about GMRTs, but we confine ourselves to the most impor- tant ideas allowing to obtain not only tests (and corresponding knowledge) but also, simultaneously, contexts inside of which these tests have been inferred. Currently, there is considerable interest in contextual information search and representation for using it to improve web search results or query expansion [3,4,10]. Classification reasoning can serve as a basic tool for constructing and using content-dependent knowledge in different problem domains and applica- tions. References 1. Baixeries, J., Kaytoue, M., Napoli, A.: Computing functional dependencies with pattern structures. In: Szathmary, L., Priss, U. (eds.) Proceedings of The Ninth In- ternational Conference on Concept Lattices and Their Applications. CEUR Work- shop Proceedings, vol. 972, pp. 175–186. CEUR-WS.org (2012) 2. Banerji, R.B.: Theory of problem solving: an approach to artificial intelligence, vol. 17. Elsevier Publishing Company (1969) 3. Bankar, S., Nagpure, R.: Contextual information search based on domain using query expansion. In: International Journal of Emerging Trends and Technology in Computer Science. vol. 3, pp. 148 – 151 (2014) 4. Bouramoul, A., Kholladi, M.K., Doan, B.L.: PRESY: A Context Based Query Reformulation Tool for Information Retrieval on the Web. Journal of Computer Science 6(4), 470–477 (2010) 5. Ferré, S., Ridoux, O.: The use of associative concepts in the incremental building of a logical context. In: Priss, U., Corbett, D., Angelova, G. (eds.) ICCS. Lecture Notes in Computer Science, vol. 2393, pp. 299–313. Springer (2002) Context-Dependent Reasoning Based on Good Diagnostic Tests 79 6. Finn, V.: The synthesis of cognitive procedures and the problem of induction. NTI ser.2, 1-2, 8–44 (1999), (in Russian) 7. Ganter, B., Wille, R.: Formal concept analysis: mathematical foundations. Springer, Berlin (1999) 8. Ganter, B., Kuznetsov, S.O.: Formalizing hypotheses with concepts. In: Proceed- ings of the Linguistic on Conceptual Structures: Logical Linguistic, and Computa- tional Issues. pp. 342–356. Springer-Verlag (2000) 9. Ganter, B., Kuznetsov, S.: Pattern structures and their projections. In: Delugach, H., Stumme, G. (eds.) Conceptual Structures: Broadening the Base, Lecture Notes in Computer Science, vol. 2120, pp. 129–142. Springer Berlin Heidelberg (2001) 10. Klimešová, D., Ocelı́ková, E.: Study on context understanding, knowledge trans- formation and decision support systems. WSEAS Trans. Info. Sci. and App. 7(7), 985–994 (Jul 2010) 11. Kuznetsov, S.: Machine learning on the basis of formal concept analysis. Automa- tion and Remote Control 62(10), 1543–1564 (2001) 12. Mill, J.S.: The System of Logic Ratiocinative and Inductive Being a Connected View of the Principles of Evidence, and the Methods of Scientific Investigation. Longmans (1872) 13. Naidenova, K.: Reducing one class of machine learning algorithms to logical oper- ations of plausible reasoning. Journal of Computer and Systems Sciences Interna- tional 48(3), 401–414 (2009) 14. Naidenova, X.A., Plaksin, M.V., Shagalov, V.L.: Inductive Inferring All Good Clas- sification Tests. In: Valkman, J. (ed.) ”Knowledge-Dialog-Solution”, Proceedings of International Conference. vol. 1, pp. 79 – 84. Kiev Institute of Applied Informatics, Kiev, Ukraine (1995) 15. Naidenova, X.: Machine Learning as a diagnostic task. In: Arefiev, I. (ed.) Knowledge-Dialog-Solution, Materials of the Short-Term Scientific Seminar, pp. 26 – 36. State North-West Technical University Press, St Petersburg, Russia (1992) 16. Naidenova, X.: The Data-Knowlege Transformation. In: Solovyev, V. (ed.) Text Processing and Cognitive Technologies, vol. 3, pp. 130–151. Pushchino (1999) 17. Naidenova, X.: Good classification tests as formal concepts. In: Domenach, F., Ignatov, D., Poelmans, J. (eds.) Formal Concept Analysis, Lecture Notes in Com- puter Science, vol. 7278, pp. 211–226. Springer Berlin Heidelberg, Leuven (2012) 18. Naidenova, X., Ermakov, A.: The decomposition of good diagnostic test inferring algorithms. In: Alty, J., Mikulich, L., Zakrevskij, A. (eds.) ”Computer-Aided De- sign of Discrete Devices” (CAD DD2001), Proceedings of the 4-th Inter. Conf., vol. 3, pp. 61 – 68. Minsk (2001) 19. Naidenova, X.: An incremental learning algorithm for inferring logical rules from examples in the framework of the common reasoning process. In: Triantaphyllou, E., Felici, G. (eds.) Data Mining and Knowledge Discovery Approaches Based on Rule Induction Techniques, Massive Comp., vol. 6, pp. 89–147. Springer (2006) 20. Naidenova, X.A., Parkhomenko, V.: Attributive and object subcontexts in inferring good maximally redundant tests. In: Bertet, K., Rudolph, S. (eds.) Proceedings of the Eleventh International Conference on Concept Lattices and Their Applications, Košice, Slovakia, October 7-10, 2014. CEUR Workshop Proceedings, vol. 1252, pp. 181–193. CEUR-WS.org (2014) 21. Ore, O.: Galois connections. Trans. Amer. Math. Soc 55, 494–513 (1944) 22. Rasiowa, H.: An Algebraic Approach to Non-classical Logics. Studies in logic and the foundations of mathematics, North-Holland Publishing Company (1974)