A large class of machine learning algorithms based on mining good classification tests is described. The Galois lattice is used for constructing good classification tests. Special rules are determined for constructing Galois lattices over a given context. All the operations of lattice construction take their interpretations in human mental acts. This paper provides a framework for solving diverse and very important problems of constructing machine learning algorithms based on the concept of good classification test. Good classification tests (GCTs) are item sets of a special kind. They serve as a basis for mining implicative logical rules from the data sets. The lattice theory is used as a mathematical language for constructing GCTs. The definition of GCTs is based on correspondences of Galois on S×T, where S is a given set of objects and T is a set of attributes' values (items). Any classification test is a dual element of the Galois Lattice generated over a given context (S, T). All the operations of lattice construction take their interpretations in human mental acts. In this paper, we focus on conceptual knowledge the main elements of which are objects, properties (attribute values), and classifications (attributes). Taking into account that implications express the links between concepts (object ↔ class, object ↔ property, property ↔ class) we believe classification reasoning to be based on using and searching for only one type of logical dependencies, namely, implicative dependencies. Implicative assertions are considered as logical rules of the first type including the following ones. Implication: a, b, c → d. Interdiction or forbidden rule: a, b, c → false (never). This rule can be transformed into several implications such as a, b → not c; a, c →
not b; b, c → not a. Compatibility: a, b, c → VA, where VA is the frequency of rule’s
occurrence. The compatibility is equivalent to the collection of implications as
follows: a, b → c, VA; a, c → b, VA; b, c → b, VA. Generally, the compatibility rule
represents a most frequently observed combination of values. The compatibilities can
serve as one of the bases of association rules [
Rules of the second type or classification reasoning rules are the rules with the help of which rules of the first type are used, updated, and inferred from data (instances). They embrace both inductive and deductive reasoning rules. Deductive steps of reasoning consist of inferring consequences from some observed facts with the use of implications. For this goal, the main forms of deductive reasoning are applied: modus ponens, modus tollens, modus ponendo tollens, and modus tollendo ponens.
Let X be a collection of true values of some attributes (or evidences) observed simultaneously. Let r be an implication, left(r) and right(r) be the left and the right parts of r, respectively Using implication: if left(r) ⊆ X, then X can be extended by right(r): X ← X ∪ right(r). Using implication is based on modus ponens: if A, then B; A; hence B. 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; and either A or B; B; hence not A. Using compatibility: let r = ‘a, b, c → k, VA’, where VA is the support of r. If left(r) ⊆ X, then k can be used to extend X along with the calculated value VA for this extension. Calculating VA requires a special consideration. Using compatibility is based on modus ponens. Using diagnostic rules: let r be a diagnostic rule ‘X, d → a; X, b → not a’, where ‘X’ is true, and ‘a’, ‘not a’ are some alternatives. Using diagnostic rule is based on modus ponens and modus ponendo tollens. There are several ways for refuting one of the hypotheses: (1) to infer either d or b using existing knowledge (with the use of deductive reasoning rules); (2) inferring (with the use of inductive reasoning rules of the second type) new implications for distinguishing between the hypotheses ‘a’ and ‘not a’; (3) to address an expert. Using rule of alternatives 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.
the following hypothesis is generated “if k is true, then y may be true”. Using modus tollens: let r be an implication y → k. If ‘not k’ is inferred, then ‘not y’ is also inferred.
When applied, these rules generate the reasoning, which is not demonstrative. The
deductive reasoning rules act by means of extending an incomplete description X of
some evidences and disproving impossible extensions. All generated extensions must
not contradict with knowledge (the first-type rules) and an observable real situation,
where the reasoning takes place. They must be intrinsically consistent (there are no
prohibited pairs of values in such extensions). The inductive reasoning rules deal with
known facts and propositions, observations and experimental results to obtain or
correct the first-type rules. For this goal, the main inductive cannons stated by a British
logician John Stuart Mill [
Denote by R a set of objects and by S the set of indices of objects of R. Let R(+) and S(+) be the sets of positive objects and indices of positive objects, respectively. Then R(-) = R/R(+) is the set of negative objects. Denote by Т a set of attributes values or items (values, for short) each of which appears in description at least of one of the objects of R.
The definition of good tests is based on correspondences of Galois G on S×T and
two relations S → T, T → S [
Of course, we have obj(t) = {intersection of all s(A): s(A) ⊆ S, A ∈ t}. Operations val(s), obj(t) are reasoning operations related to discovering the general feature of objects the indices of which belong to s and to discovering the indices of all objects possessing the feature t, respectively.
The operation generalization_of(t) = t′ = val(obj(t)) gives the maximal general feature for objects the indices of which are in s(t); the operation generalization_of(s) = s′ = obj(val(s)) gives the maximal set of objects possessing the feature t(s).
The generalization operations are actually closure operators [
These generalization operations are not artificially constructed operations. One can perform, mentally, a lot of such operations during a short period of time. We give an example of these operations. Suppose that somebody has seen two films (s) with the participation of Gerard Depardieu (val(s)). After that he tries to know all the films with his participation (obj(val(s))). One can know that Gerard Depardieu acts with Pierre Richard (t) in several films (obj(t)). After that he may discover that these films are the films of the same producer Francis Veber (val(obj(t))).
Notice that these generalization operations are also used in FCA [
Let S(+) and S(-) = S\ S(+) be the sets of indices of positive and negative objects respectively.
Definition 1. A classification test for R(+) is a pair (s, t) such that t ⊆ T (s = obj(t) ≠ Ø), s ⊆ S(+) & t ⊄ t’, ∀t’, t‘ is the description of an object belonging to R(-).
In general case, a set t is not closed for classification test (s, t), i. e., the condition
val(obj(t)) = t is not always satisfied; consequently, a classification test is not
obligatory a concept of FCA [
Definition 2. A classification test (s, t), t ⊆ T (s = obj(t) ≠ ∅) is good for R(+) if and only if any extension s’ = s ∪ i, i ∉ s, i ∈ S(+) implies that (s’, val(s’)) is not a test for R(+).
Definition 3. A good classification test (s, t), t ⊆ T (s = obj(t) ≠ ∅) for R(+) is irredundant if any narrowing t’ = t\A, A ∈ t implies that (obj(t’), t’)) is not a test for R(+).
extension of t’ = t ∪ A, A ∉ t, A ∈ T implies that (obj(t ∪ A), t’) is not a good test for R(+).
It is possible to show that good maximally redundant tests (GMRTs) are closed
maximal frequent itemsets and good irredundant tests (GIRTs) are minimal generators
[
Generating all types of tests is based on inferring the chains of pairs (s, t) ordered
by the inclusion relation. The set of all concepts ordered by the relation ≤, where (s, t)
≤ (s*, t*) is satisfied if and only if s ⊆ s* and t ⊇ t*, s ∈ 2S , t ∈ 2t, is an algebraic
lattice with operations ∩, ∪ [
Inferring the chains of dual lattice elements ordered by the inclusion relation lies in the foundation of generating all types of classification tests. The following inductive transitions from one element of a chain to its nearest element in the lattice are used: (i) from sq to sq+1, (ii) from tq to tq+1, (iii) from sq to sq-1, and (iv) from tq to tq-1, where q, q+1, q-1 are the cardinalities of enumerated subsets.
Inductive transitions can be smooth or boundary. Under smooth transition, extending (narrowing) of collections of values (objects) is going with preserving a given property of them. These properties are, for example, “to be a test for a given class of objects”, “to be an irredundant collection of values”, “to be a good test for a given class of objects” and some others. A transition is said to be boundary if it changes a given property of collections of values (objects) into the opposite one. For realizing the inductive transitions we use the following rules: generalization and specification rules, and dual generalization and specification rules.
The generalization rule is used to get all the collections of objects sq+1 = {i1, i2, …
iq, iq+1} from a collection sq = {i1, i2, … iq} such that (sq, val(sq)) and (sq+1, val(sq+1))
are tests for a given class of objects. The termination condition for constructing a
chain of generalizations is: for all the extension sq+1 of sq, (sq+1, val(sq+1)) is not a test
for a given class of positive objects. The generalization rule uses, as a leading process,
an ascending chain (s0 ⊆ … ⊆ si ⊆ si+1 ⊆ … ⊆ sm) and the operation
generalization_of(s) = s′ = obj(val(s)) for each obtained collection of objects in case of inferring
GMRTs [
The specification rule is used to get all the collections of values tq+1 = {A1, A2, …,
Aq+1} from a collection tq = {A1, A2, …, Aq} such that tq and tq+1 are irredundant
collections of values and (obj(tq), tq) and (obj(tq+1), tq+1) are not tests for a given class of
objects. The termination condition for constructing a chain of specifications is: for all
the extensions tq+1 of tq, tq+1 is either a redundant collection of values or a test for a
given class of objects. This rule has been used for inferring GIRTs [
Both generalization and specification rules realize the Joint Method of Agreement
and Difference [
The dual generalization (specification) rules relate to narrowing collections of values (objects).
All inductive transitions take their interpretations in human mental acts. The extending of a set of objects with checking the satisfaction of a given assertion is a typical method of inductive reasoning. For example, Claude-Gaspar Bashet de Méziriak, a French mathematician (1581 – 1638) has discovered (without proving it) that apparently every positive number can be expressed as a sum of at most four squares; for example, 5 = 22 + 12, 6 = 22 + 12+ 12, 7 = 22 + 12+ 12+12, 8 = 22 + 22, 9 = 32. Bashet has checked this rule for more than 300 numbers. In pattern recognition, the process of inferring hypotheses about the unknown values of some attributes is reduced to the maximal expansion of a collection of known values of some others attributes in such a way that none of the forbidden pairs of values would belong to this expansion. The contraction of a collection of values is used, for instance, in order to delete redundant (non-informative) values from it. The contraction of a collection of objects is used, for instance, to isolate a certain cluster in a class of objects. Thus, we distinguish lemons in the citrus fruits.
The boundary inductive transitions are used to get: (1) all the collections tq from a collection tq-1 such that (obj(tq-1), tq-1) is not a test but (obj(tq), tq) is a test, for a given set of objects;
(2) all the collections tq-1 from a collection tq such that (obj(tq), tq) is a test, but (obj(tq-1), tq-1) is not a test for a given set of objects;
(3) all the collections sq-1 from a collection sq such that (sq, val(sq)) is not a test, but (sq-1, val(sq-1)) is a test for a given set of objects;
(4) all the collections of sq from a collection sq-1 such that (sq-1, val(sq-1)) is a test, but (sq,val(sq)) is not a test for a given set of objects.
All the boundary transitions are interpreted as human reasoning operations.
Transition (1) is used for distinguishing two diseases with similar symptoms. Transition (2)
can be interpreted as including a certain class of objects into a more general one:
squares can be named parallelograms, all whose sides are equal. In some intellectual
psychological tests, a task is given to remove the “superfluous” (inappropriate) object
from a certain group of objects (rose, butterfly, phlox, and dahlia) (transition (3)).
Transition (4) can be interpreted as the search for a refuting example. The boundary
inductive transitions realize the Methods of Difference and Concomitant Changes [
Note that reasoning begins with using a mechanism for restricting the space of searching for tests: (i) for each collection of values (objects), to avoid constructing all its subsets and (ii) to restrict the space of searching only to the subspaces deliberately containing the desired GMRTs or GIRTs. For this goal, admissible and essential values (objects) are used.
First, consider the boundary transition (1): getting all the collections tq from a collection tq-1 such that (obj(tq-1), tq-1) is not a test but (obj(tq), tq) is a test for a given set of objects. For this transition, we use the inductive diagnostic rule and a method for choosing values to extend tq-1. We extend tq-1 by choosing values that appear simultaneously with it in the objects of R(+) and do not appear in any object of R(-). These values are to be said essential ones.
Consider the boundary inductive transition (3): getting all the collections sq-1 from a collection sq such that (sq, val(sq)) is not a test, but (sq-1, val(sq-1)) is a test for a given set of objects. For this transition, we use the dual inductive diagnostic rule and a method for choosing objects to delete them from sq. By analogy with an essential value, we define an essential object (index of essential object).
Let s be a subset of objects belonging to a given positive class of objects; assume also that (s, val(s)) is not a test. The object tj, j ∈ s is to be said an essential in s if (s\j, val(s\j)) is a test for a given set of positive objects. 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.
The dual inductive diagnostic rule can be used for inferring compatibility rules of the first type. The number of objects in sbmax(s) can be understood as a measure of “carrying-out” for an acquired rule related to sbmax(s), namely, val(sbmax(s)) → k(R(+)) frequently, where k(R(+)) is the name of the set R(+).
The inductive rules generate logical rules of the first type (see, please Table 1).
During the lattice construction, the deductive rules of the first type (implications, interdictions, rules of compatibility (approximate implications), and diagnostic rules) are generated and used immediately for pruning the search space.
We give some examples of realizing the generalization rule for inferring all GMRTs. Any realization of this rule must allow, for each element s, the following actions: a) to avoid constructing the set of all its subsets, b) to avoid the repetitive generation of it.
Let S(test) be the partially ordered set of elements s = {i1, i2, … iq}, q = 1, 2, …, nt
- 1 obtained as a result of generalizations and satisfying the following condition: (s,
val(s)) is a test for a given class R(+) of objects. Here nt denotes the number of
positive objects. Let STGOOD be the partially ordered set of elements s satisfying the
following condition: (s, val(s)) is a GMRT for R(+). Consider some methods for
choosing objects admissible for extending s [
Method 1. Suppose that S(test) and STGOOD are not empty and s ∈ S(test). Construct the set V: V = {∪ s’, s ⊆ s’, s’ ∈ {S(test) ∪ STGOOD}}.
If we want an extension of s not to be included in any element of {S(test) ∪ STGOOD}, we must use, for extending s, the objects not appearing simultaneously with s in the set V. The set of objects, candidates for extending s, is equal to: CAND(s) = nts\V, where nts = {∪ s, s ∈ S(test)}.
An object j* ∈ CAND(s) is not admissible for extending s if at least for one object i ∈ s the pair {i, j*} either does not correspond to a test or it corresponds to a good test (it belongs to STGOOD).
Let Q be the set of forbidden pairs of objects for extending s: Q = {{i, j} ⊆ S(+): ({i, j}, val({i, j}) is not a test for R(+)}. Then the set of admissible objects is select(s) = {i, i ∈ CAND(s): (∀j) (j ∈ s), {i, j} ∉ {STGOOD or Q}}.
The set Q can be generated before searching for all GMRTs for R(+).
Method 2. In this method, the set CAND(s) is determined as follows. Let s* = {s ∪ j} be an extension of s, where j ∉ s. Then val(s*) ⊆ val(s). Hence the intersection of val(s) and val(j) must be not empty. The set CAND(s) = {j: j ∈ nts\s, val(j) ∩ val(s) ≠ Ø}.
The set ext(s) contains all the possible extensions of s in the form snew = (s ∪ j), j ∈ select(s) and snew corresponds to a test for R(+). This procedure of forming ext(s) executes the function generalization_of(snew) for each element snew ∈ ext(s).
The generalization rule is a complex process in which both deductive and inductive reasoning rules of the second type are used (please, see Table 2). The knowledge acquired via a generalization process (the sets Q, L, CAND(s), S(test), STGOOD) is used for pruning the search in the domain space.
Searching for only admissible variants of generalization is not an artificially constructed operation. A lot of examples of using this rule in human thinking can be given. For example, if your child were allergic to oranges, then you would not buy these fruits but also orange juice and products containing orange extracts. A good gardener knows the plants that cannot be adjacent in a garden. The problems related to placing individuals, appointing somebody to the post, finding lodging for somebody deal with partitioning a set of objects or persons into groups by taking into account forbidden pairs of them. 6
To transform good classification tests inferring into an incremental process, we
introduce two kinds of subtasks [
Each example contains only some subset of values from T; hence each subtask of the first kind is simpler than the initial one. Each subset X of T appears only in a part of all examples; hence each subtask of the second kind is simpler than the initial one.
There are the analogies of these subtasks in natural human reasoning. Describing a
situation, one can conclude from different subsets of the features associated with this
situation. Usually, if one tells a story from his life, then somebody else recalls a
similar story possessing several equivalent features. We give, as an example, a fragment
of the reasoning of Dersu Usala, the trapper, the hero of the famous book of Arseniev,
V. K. [
On the shore, there was the trace of bonfire. First of all, Dersu noted that the fire ignited at one and the same place many times. He concluded that here was a constant ford across the river. Then he said that three days ago a man passed the night near the bonfire. It was an old man, the Chinese, a trapper. He did not sleep during entire night, and, in the morning, he did not cross the river and he left. Dersu deduced that only one person was here from the only one track on the sand. He deduced that the person was a trapper on the basis of a wooden rod used for making traps for small animals. That this was the Chinese, Dersu learned from the manner to arrange bivouac. That this was an old man, Dersu deduced after inspecting the deserted footwear: young person first tramples nose edge of foot-wear, but old man tramples heel.
The subtask of the first kind. We introduce the concept of an object’s (example’s) projection proj(R)[t] of a given positive object t on a given set R(+) of positive examples. The proj(R)[t] is the set Z = {z: (z is non empty intersection of t and t’) & (t’ ∈ R(+)) & ((obj(z), z) is a test for R(+))}.
If the proj(R)[t] is not empty and contains more than one element, then it is a subtask for inferring all GMRTs that are in t. If the projection contains one and only one element t, then (obj(t), t) is a GMRT.
The subtask of the second kind. We introduce the concept of an attributive projection proj(R)[A] of a given value A on a given set R(+) of positive examples. The projection proj(R)[A] = {t: (t ∈ R(+)) & (A appears in t)}. Another way to define this projection is: proj(R)[A] = {ti: i ∈ (obj(A) ∩ s(+))}. If the attributive projection is not empty and contains more than one element, then it is a subtask of inferring all GМRТs containing a given value A. If A appears in one and only one object X, then A does not belong to any GMRT different from X.
Forming the projection of A makes sense if A is not a test and the intersection of all
positive objects in which A appears is not a test too, i.e., obj(A) ⊄ s(+) and t′ =
t(obj(A) ∩ s(+)) does not correspond to a test for R(+). The procedures using these
subtasks for inferring GMRTs can be found in [
Restricting the search for tests to a sub-context of given context favors completely
separating tests [
We introduce the following operations: choosing object (value) for subtasks,
forming and reducing subtasks. The choice of values (objects) for forming subtasks
requires a special consideration. It is convenient using essential values in an object and
essential objects in a projection for the decomposition of inferring good tests into
subtasks of the first or second kind. The following theorem gives the foundation for
reducing projections [
Theorem 1. Let A be a value from T, (obj(X), X) be a maximally redundant test for a given set R(+) of positive objects and obj(A) ⊆ obj(X). Then A does not belong to any GMRT for R(+) different from (obj(X), X).
Solving subtasks of the first kind initializes deleting object descriptions (item sets), deleting item sets from projection may be followed by deleting values (items) satisfying Theorem 1 or becoming less frequently. Deleting values (items) from item sets may result in deleting item sets not containing any tests for a given class of objects. 7
Incremental supervised learning is necessary when a new portion of observations
becomes available over time. Suppose that each new object comes with the indication
of its class membership. The following actions are necessary with the arrival of a new
object: 1) checking whether it is possible to perform generalization of some existing
rules (tests) for the class to which a new object belongs (a class of positive objects, for
certainty), that is, whether it is possible to extend the set of objects covered by some
existing rules or not; 2) inferring all good classification tests contained in the new
object description; 3) checking the validity of rules (tests) for negative objects, and, if
it is necessary, modifying the tests that are not valid (test for negative objects is not
valid if it is included in a new (positive) object description). The second act can be
reduced to the subtask of the first kind. The third act can be reduced either to the
inductive diagnostic rule followed by the subtasks of the first kind or only to the subtask
of the second kind. These acts have been implemented in an incremental algorithm
INGOMAR for inferring GMRTs [
The methodology presented in this paper provides a framework for solving diverse and very important problems of constructing machine learning algorithms based on a unified logical model in which it is possible to interpret any elementary step of logical inferring as a human mental operation. This methodology deals with object classifications and their approximations by the use of classification tests constructed in a given features space. This fact allows managing the procedures of discovering knowledge from data by the aid of domain ontology.