An approach to modelling self-supervised learning for automated inferring good classification tests is proposed. The concepts of internal and external learning contexts are formulated. A model of intelligent agent, capable of improving own learning process of inferring good classification tests in the external context is advanced. Internal evaluation is used in an internal process of learning with the aim of tuning the external learning process. The same learning algorithm is used for supervised learning both in the external context and in the internal context. The structure of good test inferring is described and a procedure to recognize the end of inferring process is proposed.
Self-learning embodies one of the essential properties of human intelligence related to an internal evaluation of the mental process quality. A deeper level of learning – selflearning – allows to manage the learning process in an external context in terms of its effectiveness through the internal evaluation and developing rules to select the best learning strategies and parameters without a teacher.
We shall understand self-learning as a process of improvement of an agent's (or system’s) actions on the basis of self-evaluation of his (its) actions in a variable context. When the agent selects sub-contexts and some actions in learning process, he (it) uses some criteria. The self-learning is related to the ability to change these criteria, to form new criteria, which is essentially to improve the learning algorithms, making them more consistent with the external context and more effective.
The purpose of this paper is to model a self-learning process in the logical or
symbolic supervised algorithms of machine learning. This mode of learning covers
mining logical rules and dependencies from data: “if-then” rules, decision trees,
functional, implicative and associative dependencies. We shall consider a special kind of
symbolic machine learning, namely, inferring good tests from data [
their symbolic descriptions. The self-learning at the internal (deep) level implements the analysis and internal evaluation of classification rule inferring in the external context and allows one to reveal the relationships between the external contexts (subcontexts) and the parameters of learning. The implementation of self-learning in the internal context can be based on the same algorithm of symbolic machine learning that works in the external context.
The paper is organized as follows. The related works are discussed in Section 2. Sections 3 and 4 deal with defining a software agent capable of self-learning and the structure of the internal context. Sections 5, 6, and 7 cover the description of selflearning in inferring good maximally redundant classification tests from data. To complete the paper, we give a short conclusion. 2
The analysis of modern researches has been implemented in the following directions:
modeling of self-learning (self-supervised learning), deep learning [
In the first direction, it is particularly interesting [
In [
It is an ordinary practice to associate self-learning with deep learning. Impressive
successes in deep learning achieved in simulation games [
Neural networks recognize classes of objects and form a feature hierarchy of
classes, but do not form their symbolic logical descriptions or rules to recognize them.
There are a number of works in which attempts are made to find the interconnection
between artificial neural networks and symbolic machine learning within the
framework of the analysis of formal concepts (FCA) [
In some works, the authors propose the use of robot’s manipulation reflection in
learning algorithms for improving and accelerating robot’s training. For example,
industrial Robot of Japanese Company Fanuc uses a method known as "training with
reinforcement" to grab objects by a manipulator. In this process, the robot fixes its
work on video and uses this video for correcting own activity. Domestic development
of robots is also based on the use of artificial neural networks [
Intelligence acts always in a changing context. Several examples of changing contexts can be: the descriptions of patient's conditions supplemented by doctor's decisions and patient's responses, images of the Earth's surface, and student personal characteristics. The task of self-learnable individual or an automatic device in a such changing context is to support any purposeful action or function (search of food, search for exit from a labyrinth, etc.). Intelligence must have some abilities to act in the context by choosing sub-contexts and/or actions in them, as well as by assessing the extent to which its actions bring it closer to the goal. We shall refer to the context in which an intellectual being or device is acting as the external context.
The objects in the external context (training samples) are described in terms of
their properties (features, attributes) and they are specified by splitting into classes.
The task of learning is to find rules in a given space of object descriptions in order to
repeat the classification of objects represented by splitting objects into disjoint
classes. Good tests approximate the specified object classification in the best way and
give the minimum sets of attributes (values) that carry out the greatest possible
generalization within object classes and distinguish in pairs all objects from different
classes [
- external context is partitioned into sub-contexts in which good tests are inferred independently;
- sub-contexts are chosen and formed by the logical rules based on analyzing subcontexts’ characteristics; the choice of sub-context determines the speed and efficiency of classification task.
The strategies for selecting sub-contexts of the external context and the algorithms to find good tests in them are easy to describe (to represent) with the use of special multi-valued attributes. In what follows, we shall call the intellectual being an agent, although it does not mean that we identify it with the agent in multiagent systems. Summing up the foregoing, we conclude that for self-learning the agent should have: 1. A display of the external context in terms of the internal context); 2. A set of rules (possible actions) for selecting context (sub-context); 3. A display of the desired target (state); 4. An operation (a function) for comparing the desired target with the achieved result.
During the training process, the agent must develop a sequence of actions that will lead to the goal. We shall consider the permanent external context and its changes only in connection with the activity of the agent, for example, a sub-context can be deleted when the agent has completely solved the problem for this sub-context. Decomposition of contexts into sub-contexts in the tasks of inferring good classification tests have been considered in [25-26].
When the agent selects sub-contexts and its (his) actions in learning process, it (he)
uses some criteria. These criteria can be: the number of sub-contexts to be considered,
the number of tests already extracted in sub-context, the number of objects and values
of attributes in sub-context, the number of essential objects and values of attributes
(attributes) in sub-context [
Let us assume that the internal context necessarily contains: 1. Description of selected sub-context in terms of its properties; 2. Description of selected action and the rule for its selection; 3. Internal estimation of learning process with the use of some criteria of its efficiency. 4
Let K be the descriptions of external sub-context via its properties, А = {A1, A2, …. An} be the descriptions of algorithms of good tests inferring via their properties in this sub-context, R = {R1, R2, …,.Rm} be the set of rules for selecting sub-contexts, and V = {V1, V2, …, Vq) be the set of rules for evaluating the process of good test inferring. Then the internal context is described by the direct product of sets K, A, R and its mapping on V: K × A × R → V. There are more simple variants of the internal context: K × A → V and K × R → V.
The same algorithm can be used in both the external and the internal context in order to infer the logical rules for distinguishing the variants of learning in the external context evaluated as good ones from the variants evaluated as not good ones. A few algorithms for good test inferring have been elaborated: ASTRA [27], DIAGARA, NIAGARA, and, INGOMAR [28].
We come to the realization of deep learning for the symbolic machine learning tasks. The internal context is a memory of the agent, the rules extracted from the internal context represent the agent's knowledge about the effectiveness of its actions in the external context. Actions in the internal and external contexts can be represented as actions of two agents functioning in parallel and exchange data (Fig. 1).
Agent A1 transmits the data (the descriptions of contexts, algorithms, rules for selecting sub-contexts) to Agent A2. Agent A2 acts in the internal context (obtained from agent A1) and passes to agent A1 the rules, which the latter applies to select the best variant of learning with each new external sub-context.
For Agent A2, the internal context (memory) should not be empty, but this agent (as well as Agent A1) can use an incremental mode of learning [28]. A few incremental algorithms for good test inferring in symbolic contexts are described in [28]. 5
Good test analysis (GTA) deals with the formation of best descriptions of a given object class (class of positive objects) against the objects do not belonging to this class (class of negative objects) on the basis of lattice theory. We assume that objects (or patterns) are described in terms of values of a given set U of attributes. The key notion of GTA is the notion of classification. To give a target classification of objects, we use an additional attribute k ∉ U. This attribute partitions a given set of objects into disjoint classes the number of which is equal to the number of values of this attribute. We need in the following series of definitions.
Denote by M the set of attribute values such that M = ∪a∈U rng(a), where rng(a) is the set of all values of a. Let G = G+ ∪ G− be the set of objects, where G+ and G− are the sets of positive and negative objects, respectively.
Let T be a table with many-valued data, where lines correspond to objects and columns correspond to attributes. For representing data, we do not use any scaling.
Denote a description of g ∈ G by δ(g), and descriptions of positive and negative objects by D+ = {δ(g)| g ∈ G+} and D− = {δ(g)| g ∈ G−}, respectively. The Galois connections [29] between the ordered sets (2G, ⊆) and (2M, ⊆), i.e. 2G → 2M and 2M → 2G, are defined by the following mappings called derivation operators [30]: for A ⊆ G and B ⊆ M, val(A) = ∩g∈A δ(g) and obj(B) = {g| B ⊆ δ(g), g ∈ G}.
There are two closure operators [30, 31]: generalization_of(B) = val(obj(B)) and generalization_of(A) = obj(val(A)). A is closed if A = obj(val(A)) and B is closed if B = val(obj(B)). If (val(A) = B) & (obj(B) = A), then a pair (A,B) is called a formal concept [30, 32], subsets A and B of which are called concept extent and intent, respectively. A triplet (G,M,I), where I is a binary relation between G and M, is a formal context K. According to the values of a goal attribute, we get some possible forms of the formal contexts: Kε := (Gε,M,Iε) and Iε := I ∩ (G ε × M), where ε ∈ rng(k), rng(k) = {+,−} (if necessary the value τ can be added to provide undefined objects) [32]. A classification context K± is formed by the sub-position of contexts K+ and K−, and the apposition of the resulted context with (G±, k, G±×k), i.e. after adding the classification attribute k. Let us rewrite the definitions of tests by using notation of classification contexts and semi-concepts [33]: pairs like (obj(B),B), B ⊆ M, the left side of which is called an extent, and pairs like (A,val(A)), A ⊆ G, the right side of which is called an intent. Here and later words “diagnostic test” (and GMRT) will be used for semi-concepts (or concepts), the right part of which is a test.
Definition 1. A diagnostic test (DT) for K+ is a pair (A,B) such that B ⊆ M, A = obj(B) ≠ ∅, A ⊆ G+, and obj(B)∩G ≠ ∅.
Definition 2. A diagnostic test (A,B) for K+ is to be said maximally redundant if obj(B∪m) ⊂ A for all m ∈ M \B.
Definition 3. A diagnostic test (A,B) for K+ is to be said good iff any extension A1 = A∪i, i ∈ G+ \A, implies that (A1,val(A1)) is not a DT for K+ .
A maximally redundant test which is simultaneously good is called a good maximally redundant test (GMRT).
Definitions of tests (as well as other definitions), associated with K+, are applicable to K−.
If a good DT (A,B) for K+ is maximally redundant, then any extension B1 = B ∪ m, m ∉ B, m ∈ M implies that (obj(B1),B1) is not a good DT for K+.
In the general case a set B is not closed for DT (A,B), consequently, DT is not
obligatorily a formal concept. A GMRT can be regarded as a special type of formal
concept [
To transform inferring GMRTs into an incremental process, we introduce two kinds of subtasks for K+ (K−), called subtasks of the first and second kind, respectively [34]:
1. Given a positive object g, find all GMRTs (obj(B),B) for K+ such that B is contained in δ(g). In the general case, instead of δ(g) we can consider any subset of values B1, such that B1 ⊆ M, obj(B1) ≠ ∅, B1 ⊈ δ(g), ∀g ∈ G−.
2. Given a non-empty set of values B ⊆ M such that (obj(B),B) is not a DT for positive objects, find all GMRTs (obj(B1),B1) such that B ⊂ B1.
Accordingly, we define two kinds of sub-contexts of a given classification context called object and attribute value projections, respectively. If (G,M,I) is a context and if H ⊆ G, and N ⊆ M, then (H,N,I∩H×N) is called a sub-context of (G,M,I) [35].
Definition 4. The object projection ψ(K+,g) returns sub-context (N,δ(g),J), where N = {n ∈ G+ | n satisfies (δ(n) ∩ δ(g) is a test for K+)}, J = I+ ∩(N×δ(g)).
Definition 5. The attribute value projection ψ(K+,B) returns sub-context (N,B,J), where N = {n ∈ G+ | n satisfies (B ⊆ δ(n))}, J = I+∩(N×B). In the case of negative objects, symbol + is replaced by symbol − and vice versa.
The decomposition of inferring GMRTs into the subtasks requires the following actions: 1. Select an object or value to form a subtask. 2. Form the subtask. 3. Reduce the subtask. 4. Delete the object or value when the subtask is over.
The following theorem gives the foundation for reducing sub-contexts formed by object and attribute value projections [27, 28].
Theorem 1. Let B ⊆ M, (obj(B),B) be a maximally redundant DT for positive objects and obj(m) ⊆ obj(B), m ∈ M. Then m cannot belong to any GMRT for positive objects different from (obj(B),B). 6
Let Sgood+ (Sgood−) be the partially ordered set of obj+(m), m ∈ M satisfying the condition that (obj+(m), val(obj+(m))) is a current good DT for K+ (K−). The basic recursive procedure (BRP) for K+ is defined in Fig. 2, where • the first step of recursion is omitted for simplicity; • the output Sgood+ is implicitly given via a globally defined set, which is modified during the procedure; algorithm formSgood is given in Fig. 3; • variable ψtype has two possible values: object or attribute value projection; • algorithm choiceOfprojection returns ψtype, and X, which can be either g or B w.r.t. value of ψtype;
• algorithm formSubcontext implements a definition of object or attribute value projection and returns new subcontext K∗; conditions for the end of recursion are described in steps 7, 25;
• after the end of the current recursion iteration the control goes to the previous recursion iteration from steps 13, 31;
• checking whether (obj+(m),val(obj+(m))) is a DT for K+ is performed as follows: val(obj+(m)) is a test for K+ iff obj(val(obj+(m))) = obj+ (m).
Input: K+,K−,Sgood+
Output: Sgood+ 1. f := 0; 2. forall m ∈ M do 3. if val(obj+(m)) is a test for K+ then 4. formSgood(obj+(m),Sgood+); 5. M := M \m, f := 1; 6. end 7. if |M|≤ 1 then 8. return; 9. if f = 0 then 10. ψtype, X choiceOfprojection (K+,K−); 11. K∗ + formSubcontext(ψtype,X,K+); 12. BRP (K∗ +,K−,Sgood+); 13. if ψtype = object projection then
Essentially, the process of forming Sgood is an incremental procedure of finding all maximal elements of a partially ordered (by inclusion relation) set. It is based on topological sorting of partially ordered sets. Thus, when the algorithm is over, Sgood contains the extents of all the GMRTs for K+ (for K−) and only them. The opera tion of inserting an element A∗ into Sgood (in algorithm formSgood) under lexicographical ordering of these sets is reduced to lexicographically sorting a sequence of kelement collections of integers.
A sequence of n-collections whose components are represented by integers from 1 to |M|, is sorted in time of O(|M| + L), where L is the sum of lengths of all the collections of this sequence [36]. Consequently, if Lgood is the sum of lengths of all the collections A of Sgood, then the time complexity of inserting an element A∗ into Sgood is of order O(|M| + Lgood). The set Tgood of all the GMRTs is obtained as follows: Tgood = {t|t = (A,val(A)), A ∈ Sgood}.
Input: A∗ ⊆ G+,Sgood+ Output: Sgood+ 1. forall A ∈ Sgood do 2. if A ⊂ A∗ then 3. Sgood+ := Sgood+ \A; 4. else 5. if A∗ ⊆ A then 6. return; 7. end 8. Sgood+ := Sgood+ ∪A∗; 9. return; However, any attention is hardly paid to this topic in computer science. Knowledge engineering has arisen from a paradigm in which knowledge is considered as something to be separated from its bearer and to function autonomously with a problemsolving application. This paradigm ignores the very essential feature of intelligence, namely, its continuous cognitive activity. Knowledge is corrected constantly. This means that the mechanism of using knowledge cannot be separated from the mechanism of discovering knowledge. The future realization of our approach to selfimproving good test inferring will support using logical rules extracted from the internal context for deductive process of choosing variants of learning. 9
The concept of self-learning in the processes of inferring good classification tests is proposed in the paper. The inferring of good classification tests is a task of symbolic machine learning, for which the questions of self-learning has been not considered earlier. The results of this article are the following:
A model of self-learning was proposed allowing to manage the process of inferring good tests in terms of its effectiveness through an internal evaluation of the learning process and the development of rules for choosing the best strategies, algorithms, and learning characteristics.
The concepts of internal and external learning contexts were formulated. The structure of the internal context was proposed.
A model of intelligent agent, capable of improving own learning process of inferring good classification tests in the external context was advanced;
It was shown that the same learning algorithm can be used for supervised learning both in the external context and in the internal context. The proposed approach is a model of deep learning implemented by inferring logical rules from examples. Acknowledgments. The research is partially supported by RFR grant № 18-0700098A. 24. Pavlovsky, V.E., Pavlovsky V.V.: Technologies SLAM for moving robots: State and Prospects. Mechatronics, Automation, Management, 17(6), 384-394 (2016). (in Russian) 25. Naidenova, X., Parkhomenko, V., Shvetsov, K.: Context-Dependent Incremental Learning Good Maximally Redundant Tests. SAI Intelligent Systems Conference 2015, pp. 1-6. London, UK: IEEE (2015). DOI:10.11.1109/IntelliSys.2015.7361258 https://www.researchgate.net/publication/292608731_Context
Dependent_Incremental_Learning_of_Good_Maximally_Redundant_Tests 26. Naidenova, X., Parkhomenko, V.: Context-Dependent Classification Reasoning Based on Good Diagnostic Tests. Proc. of FCA&A’ 2015 (co-located with ICFCA’2015), J. Baixeries, Ch. Sacarea, and M. Ojeda-Aciego (eds), pp. 65-80. University de Malaga (2015).
ISSN-84-606-7410-8. http://ceur-ws.org/Vol-1434/proceedings-fcaa.pdf 27. Naidenova, X., Plaksin, M. Shagalov, V.: Inductive inferring all good classification tests.
Proceedings of International Conference “Knowledge-Dialog-Solution”, vol. 1, pp.79-84.
Jalta, Ukraine (1995). 28. 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, pp. 89–146. New York, NY: Springer. (2006). 29. Ore, O.: Galois connections. Trans. Amer. Math. Soc 55 (1944) 494–513. 30. Ganter, G., Kuznetsov, S. O.: Pattern Structures and Their Projections. In: H. S. Delugach, G. Stumme (eds.), Conceptual Structures: Broadening the Base, Proceedings of the 9th International Conference on Conceptual Structures, 129–142 (2001). 31. Naidenova, X.: The Data-Knowledge Transformation. In: V. Solovyev (ed.), Text Processing and Cognitive Technologies, vol. 3, Pushchino, 130–151 (1999). 32. Ganter, B., Kuznetsov, S. O.: Formalizing Hypotheses with Concepts. In: Conceptual Structures: Logical, Linguistic, and Computational Issues, Proceedings of the 8th International Conference on Conceptual Structures, 342–356 (2000). 33. Luksch, P., Wille, R.: A Mathematical Model for Conceptual Knowledge Systems. In: H.H. Bock, P. Ihm (eds.), Proceedings of the 14th Annual Conference of the Gesellschaft fur Klassifikation (GfKl 1990), 156–162 (1991). 34. Naidenova, X., Parkhomenko, V.: Attributive and Object Sub-contexts in Inferring Good Maximally Redundant Tests. In: K. Bertet, S. Rudolph (eds.), Proceedings of the Eleventh International Conference on Concept Lattices and their Applications, Košice, Slovakia, October 7-10, 2014., vol. 1252 of CEUR Workshop Proceedings, 181–193 (2014). 35. Ganter, B., Wille, R.: Formal concept analysis: mathematical foundations. Springer, Berlin (1999). 36. Aho, A. V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms.
Addison-Wesley (1975). 37. Sperner, E.: Ein Satz über Untermenge einer Endlichen Menge. Math. Z. 27, 544-548 (1928).