1. Gladun V., Vashchenko N. Analitical Processes in Pyramidal Network. Information Theories and Application, Sofia: FOI-COMMERCE, 2001.
2. Gladun V., Vashchenko N. Control on the Basis of Network Models. Artificial Intelligence in Real-Time Control: 7th IFAC Symposium. - Arizona, USA, 1998. p.88-93.
3. Kiselyova N., Gladun V. Vashchenko N. Computational Materials Design Using Artificial Intelligence Methods// Journal of Alloys and Compounds.-279(1998).-P. 8-13.
4.Gladun V., Vashchenko N. Decision Making on the Basis of Network Models// 7-th Intern. Conf. "Knowledge-Dialogue-Solution-98"-Szczecin: Maritim University.-1998.-P.13-17.
5. Gladun V., Vashchenko N. Balance Methods of Actions Planning in Control Systems //Information Theories and Application, Sofia: FOI-COMMERCE, 1995, V 3. N2, p. 3-11
6. Gladun V., Vashchenko N. Local Statistical Methods of Knowledge Formation// Cybernetics and System Analysis.-1995.-v.31.-N2.-P.207-217
7. Gladun V., Rabinovich Z. Formation of the World Model in Artificial Intelligence Systems// Machine Intelligence, 9.-Ellis Herwood Ltd., Chichester.-1980.-P.299-309.
8. V.P.Gladun. Partnership with Computers. - Kiev: "Port-Royal", 2000. - 128 p. (in Russian).
9. V.P.Gladun, V.Ju.Velichko, N.N.Kiselyova, N.N.Moskalkova. Inference of Hypothesis on Composition and Properties of Objects on the Basis of Analogy //Iskusstvennij Intellekt. - 2000. - N1. - pp. 44-52.(in Russian).
10. Gladun V.P. Purposeful Man-Computer Systems. //Iskusstvennij Intellekt. - 1999. - N2. - pp. 51-59.(in Russian).
11. Kiselyova N.N., Gladun V.P., Vashchenko N.D., LeClair S.R., Jackson á.G. Prediction of Inorganic Compounds Perspective for Search of New Electrooptical Materials// Perspektivnie Materiali, 1998, N3. pp.28 -32. (in Russian).
12. V.P.Gladun, N.D.Vashchenko. Local Statistical Methods of Knowledge Formation// Kibernetika i Sistemni analiz. 1995, N2, pp. 62-74. (in Russian).13. V.P.Gladun. Processes of New Knowledge Formation. Sofia: CD Pedagog, 1994. - 192 p. (in Russian).
14. V.P.Gladun. Planning of Solutions. Kiev: Naukova Dumka, 1987. - 186 p. (in Russian).
Abstract.
The paper deals with solution of the main analytical problems, such as knowledge discovery, classification, diagnostics and prediction, on the basis of growing pyramidal networks, which make it possible to process large-scale data without any limitations on their complexity.
Keywords: knowledge discovery, classification, diagnostics, prediction, growing pyramidal networks, concept formation.
1. Introduction.
From the early seventies a considerable number of theoretic and applied investigations were aimed at solution of analytical problems on the basis of methods which use data organization in the form of growing pyramidal network [1-4]. They result in conclusion that pyramidal network is effective tool for automation of attributive analysis of large data volumes.
The paper deals with methods of solution on the pyramidal network basis of main analytical problems, such as knowledge discovery, classification, diagnostics and prediction.
Let us formulate some requirements for models used for solution of the analytical problems.
1. What kind of knowledge is preferable to make classification, diagnosis or prognosis more reliable? It can be knowledge about dependency of the quantity to be defined on one or two other properties of the object under investigation. But it's better to use multi-parametric models reflecting all essential dependencies that characterize the object under investigation. So, the model should be the multi-parametric one.
2. The model should reflect dependencies on combinations of known properties to take into account their joint simultaneous influence on the quantity to be defined.
3. The model should be suitable for verification or interpretation by human beings. This requirement is provided if the model is described by a logical expression, in which variables are names of attribute values.
4. The best results of diagnostics or prediction as a rule correspond to more generalized models of classes, i.e. to models that are described by more simple logical expressions. The degree of logical expression simplicity can be measured by the number of its variables.
5. Performance time of choice operations grows quickly when the volume of data grows. This effect of information explosion blocks practical application of some methods of analytical analysis. The model should minimize examinations of large-scale data.
In pyramidal network analytical problems are
solved on the basis of the generalized multiparameter models of classes of objects which
are formed by analysis of a training set and then are described in the form of logical
expressions.
In contrast to another means of analytical processing of attributive descriptions [5-7]
pyramidal networks make it possible to solve analytical problems with large-scale data
without any limitations on complexity of distribution of analyzed objects in the attribute
space.
2. Growing Pyramidal Network.
A growing pyramidal network is an acyclic oriented graph having no vertices with a single incoming arc. Examples of the pyramidal networks are shown in Figs.1, 2. Vertices having no incoming arcs are referred to as receptors. Other vertices are called conceptors. The subgraph of the pyramidal network that contains vertex a and all the vertices from which there are paths to vertex a is called the pyramid of vertex a. The set of vertices contained in the pyramid of vertex a is referred to as the subset of vertex a. The set of vertices reachable by paths from vertex a is called the superset of vertex a. Vertices that are directly joined to vertex a form its 0-subset and 0-superset.
In various applications receptors correspond to values of attributes. They could be names of properties, relations, states, actions, objects and classes of objects.
Input information of the network is represented as a set of attribute values. Corresponding receptors switch to a state of excitation. The process of excitation propagates through the network. A conceptor switches into the state of excitation if all vertices of its 0-subset are excited. Receptors and conceptors retain their state of excitation during all operations of network building.
Let Fa be the subset of excited vertices of the 0-subset of vertex a; G be the set of excited vertices in the network that do not have other excited vertices in their supersets. New vertices are added to the network by the following two rules:
A1. If vertex a is not excited and the power of set Fa exceeds 1, then the arcs joining vertices of set Fa with the vertex a are liquidated and a new conceptor is added to the network which is joined with vertices of set Fa by incoming arcs and with the vertex a by an outgoing arc. The new vertex is in the state of excitation.
Rule A1 is illustrated in Fig.1 (Networks I, II). Network II was obtained after the excitation of receptors 2,3,4,5 in situation I.
Once new vertices have been introduced into all network sections where the condition of rule A1 is satisfied, rule A2 is applied.
A2. If the power of set G exceeds 1 a new conceptor is added to the network, which is joined with all vertices of set G by incoming arcs.
The new vertex is in the state of excitation. Rule A2 is illustrated in Fig.1 (Networks II, III). Network III was obtained after the excitation in situation II of receptors 2,3,4,5,6,7.
Fig.1. Network building.
In the case when sets of attribute values are descriptions of some objects, conceptors formed by rule A1 represent intersections of these descriptions and conceptors formed by rule A2 correspond to complete descriptions.
Pyramidal networks are convenient for execution of various operations of associative search. For example, it is possible to select all the objects that contain a given combination of attribute values by tracing the paths that originate from the network vertex corresponding to this combination. To select all the objects whose descriptions intersect with the description of a given object it is necessary to trace the paths originating from vertices of its pyramid. The algorithm of network formation automatically establishes associative proximity between objects having common combinations of attribute values. Processing of one object description is localized in a relatively small part of the network: in the object pyramid.
Hierarchical organization is an important property of pyramidal networks. This provides a natural way for reflecting the structure of complex objects and generic-species interconnections.
Conceptors of the network correspond to combinations of attribute values that define conjunctive classes of objects. Thus, during the network construction classification of objects is performed.
A pyramidal network stores information by mapping it to the network structure. The information about objects and classes of objects is represented by ensembles of vertices (pyramids) distributed over the entire network. Introduction of new information in the network causes changes in its structure.
Naturally, the advantages of pyramidal networks can be best seen in their physical realization that allows parallel propagation of signals through the network. It is quite important that the possibility of parallel propagation of signals is combined in the network with parallel signal reception.
3. Knowledge Discovery.
In logic generalized multi-parametric models of classes of objects are called concepts. A concept integrates knowledge, which is necessary for classification, diagnostics or prediction. In this section we shall consider the method of discovering knowledge in the form of a concept on the basis of a pyramidal network.
Let L be a training set containing objects of classes V1, V2,...,Vn.
LC Vi? ? (i=1,2,...,n). All the objects of set L are represented by sets of attribute values. Each object lI L is equipped with a type indicator lI Vi. It is required to form concepts Q1 , Q2 ,...,Qn corresponding to classes V1, V2,...,Vn and providing the correct classification of the objects from training set L.
Given is a pyramidal network representing all the objects of training set L.
To form concepts Q1, Q2,...,Qn corresponding to classes V1,V2,...,Vn it is necessary to scan pyramids of all the objects of the training set. While scanning special vertices are identified which can be used for classification of objects. They are referred to as check vertices.
Check vertices are selected using two characteristics of the network vertices: {m1, m2 ,..., mn}, where mi (i=1,2,...,n) is the number of objects from class Vi whose pyramids include the given vertex, and k, which is the number of receptors in the pyramid of this vertex. For receptors, k=1. While scanning the pyramid is transformed by the following rules.
B1. If in the pyramid of an object from class Vi the vertex having the largest k among all the vertices with the largest mi is not a check vertex of concept Qi, then it is marked as a check vertex of the concept Qi.
B2. If the pyramid of an object from class Vi contains check vertices of other concepts whose supersets do not contain excited check vertices of concept Qi, then in each of these supersets the vertex having the largest k among all excited vertices with the largest mi is marked as a check vertex of concept Qi .
According to this rule the excitation of the pyramid of vertex 2 ( Fig.2.I) results in choosing vertex 5 as the check vertex of concept Qi (Fig. 2.II).
Fig. 2. Concept formation.
Check vertices identify the most typical combinations of attribute values. If at least one new check vertex appears while scanning objects of the training set, the training set is rescanned. The algorithm stops if during the scanning of the training set no new check vertex appears. A concept that arises as a result is represented by some collection of check vertices.
Analyzing the network it is possible to construct a description of a concept in the form of a logical expression [2, 3]. For example, the concept represented by "crossed" vertices in Fig. 2.II can be described by the following expression:
(12 U 13) U O 11 U (16 U 17 U 18) U O (14 U 15).
After building the concept for some class of objects, the problems of diagnostics and prediction are reduced to classification of new objects by the comparison of their attribute descriptions with the concept. For this the following classification rule is used.
Classification rule. An object belongs to class Vi if its pyramid includes check vertices of concept Qi and does not contain check vertices of any other concept not having excited check vertices of concept Qi in their supersets. If this condition does not hold for any of the concepts, the object is unrecognized.
Besides, objects can be classified by evaluating the logical expressions that represent corresponding concepts. The variables corresponding to the attribute values that occur in the object description being recognized are assigned the value 1; all other variables are assigned the value 0. If the entire expression takes the value 1, that means that the object belongs to the class, which is described by the logical expression. A modification of the concept formation algorithm for the case when object classes intersect is described in [2,3].
4. Commentary. Applications.
Different variants of the formal description of pyramidal networks are presented in [2,3,8].
It has been proved [2] that execution time of the above algorithm is always finite. After the execution of the algorithm the above classification rule completely separates the training set into subsets Li=ViC L (i=1,2,...,n).
For better understanding of the concept formation algorithm we shall give its geometric interpretation.
Every network vertex having k receptors in its subset corresponds to (s-r)-dimensional plane in s-dimensional attribute space. The plane contains all the points corresponding to objects whose perceiving results in exiting of this vertex. (s-r)-dimensional planes corresponding to check vertices of concept Qi are referred to as zones of concept Qi.
The following statements are true for growing pyramidal networks.
Statement 1. The zone of any network vertex is totally included in zones of its subset vertices and totally includes all zones of its superset vertices.
Statement 2. The point corresponding to an object in the attribute space is located inside an intersection of zones of those check vertices, which are exited when the object is perceived.
Let us say that point a corresponding to the object in the attribute space is directly included in the zone Z of concept Qi if there is no other zones of this concept which include point a and totally are included in zone Z.
The geometric interpretation of the above-described rules for concept formation algorithm is as follows.
Rule B1. For every object of class Vi, (s-k)-dimensional plane of the exited vertex having the highest k among all the vertices with the highest mi becomes the zone of concept Qi.
Rule B2. If the point corresponding to an object of class Vi in the attribute space is directly included in zones of the other concepts, then a zone of concept Qi is created inside each of those zones.
The algorithm of concept formation stops, when during regular examination of the training set, points corresponding to objects from any class are not directly included in zones of the other concepts. When learning is finished, an object corresponds to concept Qi if the appropriate point in the attribute space is directly included in at least one zone of concept Qi and is not included in any zone of the other concepts.
Thus, the algorithm results in construction of some region for every formed concept, which consists of zones in the attribute space. The region includes all points of objects corresponding to the concept and does not include any point of the other objects of the training set. This region approximates the distribution domain of objects corresponding to the concept.
Since the approximating region consists of linear elementary regions (hyperplanes), its bounding surface is piecewise linear. So, the algorithm performs the piecewise linear division of objects corresponding to different concepts.
Zones directly including points of objects from different classes are referred to as boundary zones.
Statement 3. According to Rule 2 new zones can be created only directly inside boundary zones.
Formation of new zones inside boundary zones results in division of boundary zones.
Construction of approximating region for concept Qi consists of two processes: rough covering with concept Qi zones the distribution domain of training set objects corresponding to concept Qi (Rule B1); and division of arising boundary zones (Rule B2).
The method provides solution of analytical problems on the basis of multi-parametric models of classes of objects. The model reflects dependencies of the quantity to be defined on combinations of attribute values.
It is important that the algorithm provides the possibility to include in the concept exclusive attributes that do not belong to objects of the class under investigation. As a result, concepts formed by the algorithm have more perfect logical structure. It stimulates a more accurate diagnostics and prediction. In logical expressions exclusive attributes are represented by variables with negations.
All the search operations are restricted to a comparatively small section of the network, which includes the pyramid of the object and vertices directly linked with it. As a result the method can be applied for solution of practical problems based on large-scale data.
There is a strong analogy between main processes that take place in growing pyramidal networks and neural networks. The decisive advantage of pyramidal network is that its structure is being formed completely automatically depending on initial data. There is no problem of dependence of the learning process on abundance of the initial structure. Knowledge generated by neural nets is not explicitly represented in the form of rules or concepts. It makes difficult its interpretation and understanding by a human being.
The methodology of solution of the analytical problems on the basis of pyramidal network is implemented in the CONFOR (CONcept FORmation) system that has passed long-term examination. Typical application fields for CONFOR are as follows: prediction of new chemical compounds and materials with predefined properties [9], discovery of regularities characterizing enterprises and regions, prediction in geology, biology, the solar activity forecasting, technical diagnostics and so on. In some applications the continuous ranges of numerical values of attributes are quantized by the DISCRET system on the basis of analysis of distributions of the training set objects over the scales of attributes.
References
PARTNERSHIP WITH COMPUTERS
Man-Computer Purposeful
Systems
Abstract.
Creation of computers was stimulated by the need to have a tool
to support mental processes. According to the modern views, capabilities of computer
systems are not limited to the functions of that of a tool. In principle modern computer
systems are capable to perform all components of a task-oriented behavior act including
the formation of goal and the choice of actions. So one can say that such new type
systems are, namely, man-computer task-oriented systems. As a result, a new type of
man-computer interaction appears, which could be defined by the word
"partnership". In a task-oriented computer system, general control
is realized by the highest level metaprocedures that work on the basis of a common
conceptual knowledge.
The book deals with the conception of task-oriented
man-computer systems. For the major metaprocedures, such as knowledge discovery, concept
formation, classification, diagnostics, prediction, decision- making and planning,
the network knowledge representation is used. Original methods to process effectively
large volumes of data have passed a long-term testing. Suggested areas of application are
as follows: prediction of new chemical compounds and materials with predefined properties,
discovery of characteristic trends in particular industries and regions, medical and
technical diagnostics, prediction in geology, biology and so on.
To purchase the book, please, contact with the publishing agency: "Port-Royal": p/b 322/7, Kiev-146, Ukraine, phone (380+44) 220-61-73
ADUIS | Products | Conferences | Write to us
Copyright (c) 1998-2018 ADUIS www.aduis.com.ua |