A Synthesis of Pseudo-Boolean Empirical Models by Precedential Information

The problem of decision-making based on partial, precedential information is the most important when the creation of artificial 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 finite 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 pseudo-Boolean 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 defined 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.

Keywords

pseudo-Boolean optimization; disjunctive constraint; machine learning; decision trees.

References

1. Antamoshkin A.N., Macich I.S. Search Algorithms for Conditional Pseudo-Boolean Optimization. Control, Communications and Security Systems, 2016, no. 1, pp. 103-145. (in Russian)
2. Mazurov Vl.D. Application of Methods of Theory of Pattern Recognition in the Optimal Planning and Management. Proceeding of I-st all-Union Conference on Optimal Planning and National Economy Management. Moscow, 1971, p. 49. (in Russian)
3. Rokach L., Maimon O.Z. Data Mining with Decision Trees: Theory and Applications. New Jersey, London, Singapore, Bejing, Shanghai, Hong Kong, Taipei, Chennai, World Scientific, 2014. DOI: 10.1142/9097
4. Loh W.-Y. Classification and Regression Trees. Data Mining and Knowledge Discovery, 2011, vol. 1, no. 14, pp. 14-23.
5. Kolmogorov A.N. Algorithm, Information, Complexity, Moscow, Znanie, 1991. (in Russian)
6. Donskoy V.I. Complexity of Families of Learning Algorithms and Estimation of the Nonrandomness of Extraction of Empirical Regularities. Cybernetics and Systems Analysys, 2012, vol. 48, no. 2, pp. 233-241. DOI: 10.1007/s10559-012-9402-2
7. Donskoy V.I. Capacity Estimates of the Main Classes of Empirical Generalizations Derived by the pVCD Method. Scientific Notes of Taurida National V.I. Vernadsky University, 2010, vol. 23 (62), no. 2, pp. 56-65. (in Russian)
8. Nilsson N.J. Learning Machines. N.Y., McGraw-Hill, 1965.
9. Bonates T.O., Hammer P.L. Pseudo-Boolean Regression. Rutcor Research Report RRR 3-2007. New Jersey, Rutgers Center for Operations Research of Rutgers University, 2007.