Geodesic
A synthesis of pseudo-Boolean empirical models by precedential information
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 2, pp. 96-107 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{VYURU_2018_11_2_a7,
     author = {V. I. Donskoy},
     title = {A synthesis of {pseudo-Boolean} empirical models by precedential information},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {96--107},
     year = {2018},
     volume = {11},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a7/}
}
TY  - JOUR
AU  - V. I. Donskoy
TI  - A synthesis of pseudo-Boolean empirical models by precedential information
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2018
SP  - 96
EP  - 107
VL  - 11
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a7/
LA  - en
ID  - VYURU_2018_11_2_a7
ER  - 
%0 Journal Article
%A V. I. Donskoy
%T A synthesis of pseudo-Boolean empirical models by precedential information
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2018
%P 96-107
%V 11
%N 2
%U http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a7/
%G en
%F VYURU_2018_11_2_a7
V. I. Donskoy. A synthesis of pseudo-Boolean empirical models by precedential information. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 2, pp. 96-107. http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a7/

[1] Antamoshkin A. N., Macich I. S., “Search Algorithms for Conditional Pseudo-Boolean Optimization”, Control, Communications and Security Systems, 1:1 (2016), 103–145 (in Russian) | Zbl

[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, M., 1971, 49 (in Russian)

[3] L. Rokach, O.Z. Maimon, Data Mining with Decision Trees: Theory and Applications, World Scientific, New Jersey–London–Singapore–Bejing–Shanghai–Hong Kong–Taipei–Chennai, 2014 | DOI

[4] W.-Y. Loh, “Classification and Regression Trees”, Data Mining and Knowledge Discovery, 1:1 (2011), 14–23 | DOI

[5] Kolmogorov A. N., Algorithm, Information, Complexity, Znanie, M., 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, 48:2 (2012), 233–241 | DOI | MR | Zbl

[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, 23(62):2 (2010), 56–65 (in Russian)

[8] Nilsson N. J., Learning Machines, McGraw-Hill, N.Y., 1965 | Zbl

[9] T.O. Bonates, P.L. Hammer, Pseudo-Boolean Regression, Rutcor Research Report RRR 3-2007, Rutgers Center for Operations Research of Rutgers University, New Jersey, 2007