A Synthesis of Pseudo-Boolean Empirical Models by Precedential Information

Abstract

The problem of decision-making based on partial, precedential information is the most important when the creation of articial intelligence systems. According to the results of observations over the behaviour of external objects or systems it is necessary to synthesize or, more precisely, extract from the data a mathematical model of optimization of the object on the basis of accumulated empirical information in the form of a nite set of triples: "a state vector, the value of the quality of functioning of the object, a binary indicator of the admissibility of this state". The aim of the work is to create and substantiate mathematical methods and algorithms that allow to synthesize models of scalar pseudoBoolean optimization with a constraint in the form of disjunctive normal form (DNF) using this precedential information. The peculiarity of pseudo-Boolean optimization models with separable objective functions and DNF constraint, which has a bounded constant length, is their polynomial solvability. However, the complexity of bringing the problem to the form with a DNF constraint in general case is exponential. When extracting the model from the data the DNF constraint is synthesized approximately but with polynomial complexity and the number of conjunctions in the extracted DNF does not exceed the number of examples in the initial precedential information. In the paper is shown how to use binary decision trees to construct a disjunctive constraint, proposed the methods to identify the properties of monotonicity and linearity of the partially dened objective functions, and developed algorithms for solving problems pseudo-Boolean scalar optimization in the presence of incomplete, precedential initial information. The scope of application of the obtained results includes intelligent control systems, intelligent agents. Although the control models derived from the data are approximate, their application can be more successful than the use of less realistic, inconsistent with the objects models which are chosen on the base of subjective considerations.