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.
Pseudo-boolean optimization, disjunctive constraint, machine learning, decision trees
Короткий адрес: https://sciup.org/147232889
IDR: 147232889 | УДК: 519.854 | DOI: 10.14529/mmp180208
Синтез эмпирических псевдобулевых моделей по прецедентной информации
Проблема принятия решений по частичной, прецедентной информации является важнейшей при создании систем искусственного интеллекта. По результатам наблюдений над поведением внешних объектов или систем необходимо на основе накопленной информации в виде конечного множества троек: вектор состояния, значение качества функционирования объекта, бинарный индикатор допустимости этого состояния синтезировать или, точнее, извлечь из данных математическую модель оптимизации объекта. Целью работы является создание и обоснование математических методов и алгоритмов, позволяющих синтезировать модели скалярной псевдобулевой оптимизации с ограничением в виде дизъюнктивной нормальной формы (ДНФ), используя указанную прецедентную информацию. Особенностью псевдобулевых оптимизационных моделей с сепарабельными целевыми функциями и ДНФ ограничением, имеющим ограниченную константой длину, является их полиномиальная разрешимость. Однако сложность приведения задачи к форме с ДНФ ограничением в общем случае является экспоненциальной. При извлечении модели из данных ДНФ ограничение синтезируется приближенно, и сложность его аппроксимации оказывается полиномиальной, а число конъюнкций в извлеченной ДНФ не превышает числа примеров в начальной прецедентной информации. В статье показано, как использовать для построения дизъюнктивного ограничения бинарные решающие деревья. Предложены методы выявления свойств монотонности и линейности частично заданной целевой функции и алгоритмы решения задач псевдобулевой скалярной оптимизации при наличии неполной, прецедентной начальной информации. Область применения полученных результатов - системы интеллектуального управления, интеллектуальные агенты. Несмотря на то, что модели управления, извлеченные из данных, являются приближенными, их применение может быть более успешным, чем использование менее реалистичных, не согласованных с моделируемым объектом и выбранных из субъективных соображений моделей.
Список литературы A synthesis of pseudo-Boolean empirical models by precedential information
- Антамошкин, А.Н. Поисковые алгоритмы условной псевдобулевой оптимизации / А.Н. Антамошкин, И.С. Масич // Системы управления, связи и безопасности. - 2016. - Т. 1, № 1. - С. 103-145.
- Мазуров, В.Д. Применение методов теории распознавания образов в оптимальном планировании и управлении / В.Д. Мазуров // Труды I Всесоюзной конференции по оптимальному планированию и управлению народным хозяйством. - М.: ЦЭМИ, 1971.
- Rokach, L. Data Mining with Decision Trees: Theory and Applications / L. Rokach, O.Z. Maimon. - New Jersey; London; Singapore; Bejing; Shanghai; Hong Kong; Taipei; Chennai: World Scientific, 2014.
- Loh, W.-Y. Classification and Regression Trees / W.-Y. Loh // Data Mining and Knowledge Discovery. - 2011. - V. 1, № 14. - P. 14-23.
- Колмогоров, А.Н. Алгоритм, информация, сложность / А.Н. Колмогоров. - М.: Знание, 1991.
- Донской, В.И. Сложность семейств алгоритмов обучения и оценивание неслучайности извлечения эмпирических закономерностей / В.И. Донской // Кибернетика и системный анализ. - 2012. - Т. 48, № 2. - С. 86-89.
- Донской, В.И. Оценки емкости основных классов эмпирического обобщения, полученные pVCD методом / В.И. Донской // Ученые записки Таврического национального университета им. В.И. Вернадского. - 2010. - Т. 23 (62), № 2. - С. 56-65.
- Нильсон, Н. Обучающиеся машины / Н. Нильсон. - М.: Мир, 1967.
- Bonates, T.O. Pseudo-Boolean Regression / T.O. Bonates, P.L. Hammer // Rutcor Research Report RRR 3-2007. - New Jersey: Rutgers Center for Operations Research of Rutgers University, 2007.
