A Synthesis of Pseudo-Boolean Empirical Models by Precedential Information

Проблема принятия решений по частичной, прецедентной информации является важнейшей при создании систем искусственного интеллекта. По результатам наблюдений над поведением внешних объектов или систем необходимо на основе накопленной информации в виде конечного множества троек: ' вектор состояния, значение качества функционирования объекта, бинарный индикатор допустимости этого состояния' синтезировать или, точнее, извлечь из данных математическую модель оптимизации объекта. Целью работы является создание и обоснование математических методов и алгоритмов, позволяющих синтезировать модели скалярной псевдобулевой оптимизации с ограничением в виде дизъюнктивной нормальной формы (ДНФ), используя указанную прецедентную информацию. Особенностью псевдобулевых оптимизационных моделей с сепарабельными целевыми функциями и ДНФ ограничением, имеющим ограниченную константой длину, является их полиномиальная разрешимость. Однако сложность
приведения задачи к форме с ДНФ ограничением в общем случае является экспоненциальной. При извлечении модели из данных ДНФ ограничение синтезируется приближенно, и сложность его аппроксимации оказывается полиномиальной, а число конъюнкций в извлеченной ДНФ не превышает числа примеров в начальной прецедентной информации. В статье показано, как использовать для построения дизъюнктивного ограничения бинарные решающие деревья. Предложены методы выявления свойств монотонности и линейности частично заданной целевой функции и алгоритмы решения задач псевдобулевой скалярной оптимизации при наличии неполной, прецедентной начальной информации. Область применения полученных результатов - системы интеллектуального управления, интеллектуальные агенты. Несмотря на то, что модели управления, извлеченные из данных, являются приближенными, их применение может быть более успешным, чем использование менее реалистичных, не согласованных с моделируемым объектом и выбранных из субъективных соображений моделей.

Ключевые слова

псевдобулева оптимизация; дизъюнктивное ограничение; машинное обучение; интеллектуальное управление; решающие деревья.

Литература

1. Антамошкин, А.Н. Поисковые алгоритмы условной псевдобулевой оптимизации / А.Н. Антамошкин, И.С. Масич // Системы управления, связи и безопасности. - 2016. - Т. 1, № 1. - С. 103-145.
2. Мазуров, В.Д. Применение методов теории распознавания образов в оптимальном планировании и управлении / В.Д. Мазуров // Труды I Всесоюзной конференции по оптимальному планированию и управлению народным хозяйством. - М.: ЦЭМИ, 1971.
3. 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.
4. Loh, W.-Y. Classification and Regression Trees / W.-Y. Loh // Data Mining and Knowledge Discovery. - 2011. - V. 1, № 14. - P. 14-23.
5. Колмогоров, А.Н. Алгоритм, информация, сложность / А.Н. Колмогоров. - М.: Знание, 1991.
6. Донской, В.И. Сложность семейств алгоритмов обучения и оценивание неслучайности извлечения эмпирических закономерностей / В.И. Донской // Кибернетика и системный анализ. - 2012. - Т. 48, № 2. - С. 86-89.
7. Донской, В.И. Оценки емкости основных классов эмпирического обобщения, полученные pVCD методом / В.И. Донской // Ученые записки Таврического национального университета им. В.И. Вернадского. - 2010. - Т. 23 (62), № 2. - С. 56-65.
8. Нильсон, Н. Обучающиеся машины / Н. Нильсон. - М.: Мир, 1967.
9. 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.