Mivar based approach

History

When working in the institutions of Ministry of Defense, Varlamov O.O. started developing the theory of “rapid logical inference” in 1985. Then he was assigned a task of analyzing Petri nets and productions to construct algorithms rapidly in intelligent software packages (ISP). Generally, mivar-based theory represents an attempt to combine ER-models and their problem instance – semantic networks, production approach and Petri networks. The first experimental systems operating according to mivar-based principles were developed in 2000. Applied mivar systems were introduced in 2015.

Mivar

Mivar (Multidimensional Informational Variable Adaptive Reality) is the smallest structural element of discrete information space. The abbreviation MIVAR was introduced as a technical term by Varlamov O.O., Doctor of Technical Science, professor at Bauman MSTU in 1993 to designate a “semantic unit” in the process of mathematical modeling. The term has been established and used in all further works of the author.

A number of representatives of Russian association for artificial intelligence (RAAI) – for example, Gorodecki V.I., doctor of technical science, professor at SPIIRAS and Vagin V.N., doctor of technical science, professor at MPEI suppose that the term is incorrect and suggested that the author should use standard terminology.

Object-Property-Relation

Object-Property-Relation (VSO) is a connected graph, the nodes of which are concepts and arcs are connections between concepts.

Mivar space represents a set of axes, a set of axes elements, a set of points of space and a set of values of points.

Let us introduce A = { a n } , n = 1 , … , N ,

where:

Then: ∀ a n ∃ F n = { f n i n } , n = 1 , … , N , i n = 1 , … , I n ,

where:

F n sets form multidimensional space: M = F 1 × F 2 × ⋯ × F n . m = ( i 1 , i 2 , … , i N ) ,

where:

There is a set of values of multidimensional space points of M :

where:

For every point of space M there is a single value from C M set or there is no such value. Thus, C M is a set of data model state changes represented in multidimensional space. To implement a transition between multidimensional space and set of points values the relation μ has been introduced: C x = μ ( M x ) ,

where:

To describe a data model in mivar information space it is necessary to identify three axes:

These sets are independent. The mivar space can be represented by the following tuple:

Thus, mivar is described by « V S O » formula, in which « V » denotes an object or a thing, « S » denotes properties, « O » variety of relations between other objects of particular subject domain. Moreover, the category “Relations” can describe dependencies of any complexity level: formulae, logical transitions, text expressions, functions, services, computational procedures and even neural networks. Wide range of capabilities complicates description of interconnections in the process of modeling, but allows us to take into considerations all the factors. Mivar computations use mathematical logic. In a very simplified form they can be represented as implication in the form of "If…, then …” formula. The result of mivar modeling can be represented in the form of a bipartite graph binding two sets of objects: source objects and resultant objects.

Mivar network

Mivar network - is a bipartite graph that can be described in the form of a two-dimensional matrix, in which information about subject domain of the current task is recorded.

Generally, mivar network provides formalization and representation of human knowledge in the form of connected multidimensional space. That is, mivar network is a method of representing a piece of mivar space information in the form of a bipartite directed graph. The mivar space information is formed by objects and connections between them, which in total represent the data model of the subject domain, moreover, connections include rules for objects processing. Thus, mivar network of subject domain is a part of mivar space knowledge in this domain.

Mivar networks can be represented in the form of a bipartite graph consisting of objects-variables and rules-procedures. First, two lists are made which form two nonintersecting partitions of the graph: the list of objects and the list of rules. Objects are denoted by circles. Each rule in mivar network is extension of productions, hyper rules with multi-activators or computational procedures. It is proved that from the perspective of their further processing, all these formalisms are identical and in fact they are nodes of the bipartite graph, which are denoted by rectangles.

Development of mivar networks on the basis of multi-dimensional binary matrices

Mivar networks can be implemented on multi-processor computational systems or service-oriented architectures. Analysis of capabilities and practical application of mivar networks and production approach demonstrated that there are certain constraints on their application in modern information systems, in particular, dimension of matrix of linear matrix method for determining logical inference path on the adaptive rule networks. Matrix dimension constraint is due to the fact that implementation of this method requires sending general matrix to several different processors. Since every matrix value is initially represented in symbol form, the amount of sent data is crucial when obtaining for example 10000 rules/variables. To implement classical mivar-based method it is required to store only three different values in each cell of the matrix:

Moreover, the analysis of possibility of firing a rule is separated from determining output variables according to stages after firing the rule. Consequently, it is possible to use different matrices for these two actions: “search for fired rules” and “setting values for output variables”, which has allowed us to make a transition to multidimensional binary matrices. Processing and sending binary matrix fragments occupy much less space and improve possibilities of applying mivar networks.

Mivar-oriented logical-and-computational data processing method

To implement logical-and-computational data processing method the following should be done. First, formalized subject domain description should be developed. To do this, we identify main objects-variables and rules-procedures on the basis of mivar-based approach and then make corresponding lists of “objects” and “rules”. Formalized representation of logical-and-computational data processing method is analogous to the bipartite graph of mivar logical network.

Three main stages of mivar-based information processing are identified:

1. Forming mivar matrix of subject domain description;
2. Working with the matrix and designing solution algorithm of the set task;
3. Executing all the computations and finding the solution according to the obtained algorithm.

The first stage is essentially the stage of synthesis of conceptual subject domain model and its formalization in the form of production rules with a transition to mivar rules. “Input objects – rules /procedures – output objects”. Currently, it is this stage that is the most complex and requires involvement of a human-specialist (an expert) to develop a mivar model of the subject domain.

Automated solution algorithm construction or logical inference is implemented at the second stage. Input data for algorithm construction are: mivar matrix of subject domain description and set input object-variables (“GIVEN”) and required object-variables (“FIND”).

Solution according to the obtained algorithm should be implemented at the third stage.

More about mivar-oriented logical-and-computational data processing method

Firstly, the matrix is constructed for the mivar network of logical rules. Then on the basis of matrix analysis it is determined whether there is a successful inference path. Then possible logical inference paths are defined and at the last stage the shortest among these paths is selected, the most optimal according to the set optimality criteria.

Let m rules and n variables be known included in the rules as input variables activating them or as obtained, that is, output variables. Then, matrix V ( m ⋅ n ) ,each row of which corresponds to one of the rules and contains the information about variables used in the rule, can represent all the interconnections between rules and variables.

Moreover, one row and one column are added in the matrix V to store service information.

So, the matrix V of dimension ( m + n ) × ( n + 1 ) , is obtained, which shows the whole structure of the source rule network. Note that the structure of this logical network can change any time, that is, this is a network of rules with changeable evolutionary structure.

An example of using the mivar-oriented logical-and-computational data processing method

To search for logical inference path the following actions are implemented according to the following (enumerated) stages:

1. Known variables are denoted by z and required variables are denoted by w in the row ( m + 1 ) . For example, z denotes positions: 1,2,3 in the row ( m + 1 ) ), the variable w denotes the position ( n − 2 ) .
2. The search of such rules that can be fired, that is, all the input variables of which are known, is implemented successively, for example, top-down. If there are no such rules, there is no logical inference path and input data refinement (addition) should be requested. If there are such rules that can be fired, each of them is labeled in the corresponding place of service row that the rule can be fired. For example, we can write 1 in the matrix cell, which is illustrated in the cell ( 1 , n + 1 ) .
3. If there are several such rules, the choice of such a rule or such rules that should be fired first is implemented according to previously determined criteria. Several rules can be fired simultaneously if sufficient recourses are available.
4. Rule (procedure) firing simulation is implemented by assigning the values “known” to the variables inferred in this rule, that is, z in our example. A fired rule can be marked additionally, for example by number 2 for convenience of further work. For example, the corresponding changes are made in the cells ( m + 1 , n − 1 ) , ( m + 1 , n ) and ( 1 , n + 1 ) .
5. After rule firing simulation, the goal achievement analysis is carried out, that is, required value acquisition is analyzed by comparing special characters in the service row. If there is at least one value “unknown” ( w ) in the service row ( m + 1 ) , logical inference path search is further carried out. Otherwise, the task is considered to be solved successfully and all the rules fired in a corresponding order form logical inference path searched.
6. Firstly, we determine the availability of the rules that can be fired after defining new values at the previous stage. If there are no such rules, there is no inference path and actions are taken analogous to the step 2 of this method. If there are such rules the inference path search continues. In this example there are such rules. In the cell ( 2 , n + 1 ) the number 1 is obtained as an indication that this rule can be fired.
7. At the next stage, analogous to the stage 4 the rules are fired (rule firing simulation), further analogous to the stage 5 and 6 necessary actions are performed a number of times required to obtain the result. The stages 2–7 are implemented until the result is achieved. Moreover, the result can be positive – there is an inference path, as well as negative – there is no inference due to uncertainty of input data.
8. Deducibility feature of the variables 4 and 5 in the cells ( m + 1 , 4 ) and ( m + 1 , 5 ) is obtained, and indication that the rule has already been fired in the cell ( 2 , n + 1 ) is formed, that is, the number 2 is set. After that the analysis of the service row is carried out, which shows that not all the required variables are known. Thus, it is necessary to continue processing matrix V of dimension ( m + n ) × ( n + 1 ) . The analysis of this matrix demonstrates the possibility of rule m firing.
9. When the rule m is fired, new values are obtained for required variables as well.
10. Thus, there are no required rules in the service row in our example and we obtained new values in the cells of the martix: we got 2 in the cell ( m , n + 1 ) − 2 , and we got the value z instead of w in the cell ( m + 1 , n − 2 ) . So, positive result is obtained, consequently, there is logical inference path with given input values.