Mivar NETs and logical inference with the linear complexity

Mivar NETs and logical inference with the linear complexity
Олег Олегович Варламов

MIVAR: Transition from Productions to Bipartite Graphs MIVAR Nets and Practical Realization of Automated Constructor of Algorithms Handling More than Three Million Production Rules. The theoretical transition from the graphs of production systems to the bipartite graphs of the MIVAR nets is shown. Examples of the implementation of the MIVAR nets in the formalisms of matrixes and graphs are given. The linear computational complexity of algorithms for automated building of objects and rules of the MIVAR nets is theoretically proved. On the basis of the MIVAR nets the UDAV software complex is developed, handling more than 1.17 million objects and more than 3.5 million rules on ordinary computers. The results of experiments that confirm a linear computational complexity of the MIVAR method of information processing are given.

O.O. Varlamov

MIVAR: Transition from Productions to Bipartite Graphs Mivar Nets and Practical Realization of Automated Constructor of Algorithms Handling More than Three Million Production Rules

Oleg O. Varlamov, Moscow Automobile and Road State Technical University (MADI), Moscow Institute of Physics and Technologies (university) (MIPT), Russia.

Annotation. The theoretical transition from the graphs of production systems to the bipartite graphs of the MIVAR nets is shown. Examples of the implementation of the MIVAR nets in the formalisms of matrixes and graphs are given. The linear computational complexity of algorithms for automated building of objects and rules of the MIVAR nets is theoretically proved. On the basis of the MIVAR nets the UDAV software complex is developed, handling more than 1.17 million objects and more than 3.5 million rules on ordinary computers. The results of experiments that confirm a linear computational complexity of the MIVAR method of information processing are given.

Keywords: MIVAR, MIVAR net, logical inference, computational complexity, artificial intelligence, intelligent systems, expert systems, General Problem Solver.

Introduction

The problem of elaboration of intellectual systems is up-to-date and important. Elaboration of expert systems of new generation would allow automation of solving difficult problems. The MIVAR (Multidimensional Informational Variable Adaptive Reality) approach has provided an opportunity to offer new models and methods for data mining and management. The MIVAR technologies have been being elaborated in Russia for quite a long period of time. The first articles concerned some problems of graph theory and the elaboration of lineal matrix method of logic inference path finding on the adaptive net of rules [1-3]. Then, some work concerning the elaboration of MIVAR information space was done [4-5]. The most strictly formalized definition of the MIVARs can be found in papers [6-7]. Then the questions of the development [8-10] and the use of MIVARs for different simulators and instruction systems were discussed [11-22]. The fullest overview of theory and last achievements in MIVARs can be found in papers [4,6,10,15,18].

MIVAR nets allow the creation of new “General Problem Solver” the prototype of which is an UDAV (Universal Designer Algorithms Varlamov) programme complex. MIVAR nets remove restrictions existed before and, in fact, create expert systems of new generation which are capable to process millions of rules in acceptable time. MIVAR nets can be seen as a qualitative leap and transition to the new possibilities in information processing.

Let’s consider the systems of artificial intelligence as active self-learning logically thinking systems. In the last century, technologies of expert systems creating were elaborated for particular narrow subject domains. This was due to the difficulties in formalizing of required subjects domains as to the fact that systems of logic conclusion could not process more than 20 rules (because an exhaustive search is a Nondeterministically polynomical). At the same time, “intellectual software packages” (ISP) were developed, allowing the automated solution of problems from different domains where the calculations and the construction of algorithms were required. Technologies of ISP are developing in MIVARs and service-oriented architectures.

The MIVAR approach unifies and develops achievements from different scientific domains: databases, computational problems, logic processing, and includes two main technologies:

1) The MIVAR technology of information accumulation – is a method of creating of global evolutional bases of data and rules (knowledge) with changeable structure based on the adaptive discrete MIVAR information space of unified representation of data and rules which bases on three main definitions: “Thing, Property, Relation”.

2) The MIVAR technology of information processing – is a method of creation of the system of logic inference or “automatic construction of algorithms from modules, services and procedures” based on the active MIVAR net of rules with lineal computational complexity.

The MIVAR technology of information accumulation is designed for keeping any information with possible evolutional change of its structure and without any restrictions of its volume and the form of representation.

The MIVAR technology of information processing is designed for the processing of information, including logic inference, computational procedures and services.

In fact, MIVAR nets allow to develop production approach and to create an automatic learning logically thinking system. The MIVAR approach unifies and develops production systems, ontology, semantic nets, service-oriented architectures, multi-agent systems and other modern information technologies.

Currently, the software complex “UDAV” executes the search of logic inference and automatically constructs algorithms of problem solving controlled by the flow of entrance data. UDAV processes more than 1.17 million of variables and 3.5 million of rules. Software realization proves the lineal computational complexity of the search of logic inference on practice.

Analyses of paradigms and models of information processing

Traditionally, there exist the following paradigms and models of data processing: propositional calculus, predicate calculus, productions, semantic nets, Petri nets, ontology, and others. Production approach has important advantages. D.A. Pospelov wrote that the knowledge about the world can have double nature:

1) can contain the description of facts and events of the world that fix their presence or absence, and main relations and regularities containing these facts and events;

2) can contain procedural descriptions of how these facts and events should be manipulated and different goals of the system should be achieved [23].

Productions are generally described as “IF… THEN…”. Some specialists in intellectual systems believe that the description of knowledge in the form of productions is universal: all the knowledge can be described in this form. Different rules, procedures, formulas or services can be represented in the system of productions. In fact, all causal statements can be reduced to productions. So, the use of production approach for the logic and computational processing of different data is reasonable and efficient.

To solve various practical problems in the sphere of computer sciences databases (storage) and logical computational data processing is required. Historically, the areas of logic inference and computational processing have been developing independently and successfully solved problems of various classes. To some extent, there existed a contradiction between these two approaches [2, 3, 4, 10-17, 23-32]. In addition, the problems of processing and storage of the data were divided.

Databases were used to store and to search required data, systems of logic inference – to process the information. In a result, these two domains hardly intersected, although there were quite a lot of propositions to unite all the functions of data storage and processing in the single system [4, 10, 23-32].

The MIVAR approach allows to unify in the single formalism both data storage (in the MIVAR information space – database) and processing (in the MIVAR logical-computing nets).

The MIVAR approach allows solving various scientific and practical problems. First, let’s make an analysis of previously existed approaches and estimate their limits. Then, we’ll move to the analyses of problems, achievements and perspectives in the domain of databases and the MIVAR information space of unified representation of data and rules.

Possibilities and limitations of production approach

Production approach possesses some important advantages. D.A. Pospelov proposes 9 types of productions and the possibility of other types to exist is underlined [23]. There are examples of knowledge represented in the form of productions. Pospelov defines production system as an aggregate of productions, which can include productions of all listed types. There are some production constructions. The general form is

i, П, Р, A=>B, Q

Here, A=>B is an ordinary production “if… else…” called a production core. P characterizes external condition or applicability conditions of production determined by factors which are not included in A. Condition P allows to chose needed productions from all production with A in left part of the core. П characterizes the sphere of the subject domain of the knowledge base, or pre-conditions of production applicability. These preconditions are not different from Р but they form the formal system in the frames of which logic reasoning will be drawn. Q characterizes post-conditions of the production indicating the changes that need to be brought into the base of knowledge and the system of productions after implementing of this production [23, p. 134-135].

In general form, productions are rather rare. Horoshevsky marks out an intermediate “layer of rules” for which the research of different logic inference on rules systems is made [31, p.82-83].

Logic processing is understood as some conclusion lying in the base of human reasoning. Each process of drawing a conclusion depends on the examination of options. To increase the efficiency of process of logic inference is a central problem of all systems of the deductive conclusion [23, p. 79].

D.A. Pospelov has described two methods of logic inference: the method of forward wave and the method of backward wave. In the first method, the wave of the searching paths is propagating from all initial areas to the aim area. In the second, this wave is propagating from the aim area towards initial areas. The difference of two methods comes to different number of steps of the search. The combined method is frequently used when forward and backward waves meet, and the path from initial data towards the aim is being driven [23, p.85]. Picture 1 shows an example the graph of non-oriented “AND-OR” net [23, p. 83].