=Paper=
{{Paper
|id=None
|storemode=property
|title=Context-Dependent Deductive and Inductive
Reasoning Based on Good Diagnostic Tests
|pdfUrl=https://ceur-ws.org/Vol-1434/paper5.pdf
|volume=Vol-1434
|dblpUrl=https://dblp.org/rec/conf/icfca/NaidenovaP15
}}
==Context-Dependent Deductive and Inductive
Reasoning Based on Good Diagnostic Tests==
https://ceur-ws.org/Vol-1434/paper5.pdf
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)