Построение логических классификаторов при ограничениях на сложность определяющих их дизъюнктивных нормальных форм

• Автор: Максимов, Юрий Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 75 с. : ил.

Содержание
Введение
Задача распознавания
Цели работы
Содержание работы
Глава 1. Классы булевых функций, дизъюнктивных нормальных форм и их свойства
1.1. Определения и обозначения
1.2. Классификация булевых функций
1.3. Сложность реализации функций классов Р£, С", Ф£, Ф£Л,
и ф;;.л
Глава 2. Нижние оценки сложности
2.1. Метод сетей
2.2. Нижние границы сложности функций классов С” иФ
2.3. Нижние границы сложности функций класса Ф£ Л
Глава 3. Верхние оценки сложности
3.1. Верхние оценки сложности функций классов Сп и Ф£
3.2. Верхние оценки сложности функций классов Р£, Ф£ и Фф
Глава 4. Приложения к задачам классификации
4.1. Модель алгоритмов вычисления оценок
4.2. Сложность оценки качества классификаторов в модели алгоритмов вычисления оценок
Заключение
Основные результаты диссертации
Список полученных оценок
Список использованных источников

Введение
Сложность представления булевых функций дизъюнктивными нормальными формами (ДНФ) имеет большое значение в различных областях математики. Являясь наиболее интерпретируемым типов управляющих схем, ДНФ играют важную роль в теории сложности, задачах контроля, теории распознавания образов, пропозициональной логике и многих других областях математики [15, 18, 21, 31, 32, 36, 37, 44].
Задача распознавания
Ключевую роль играет сложность представления булевых функций дизъюнктивными нормальными в алгебраическом подходе к распознаванию образов, предложенном в работах академика РАН Ю. И. Журавлёва и развитому в многочисленных работах его учеников [11, 12, 15, 18, 27, 33|. В этих работах были развиты «прямые методы» построения корректных, то есть точных на прецедентах, алгоритмов классификации путем применения специальных алгебраических операций к базовым (некорректным) распознающим операторам. При этом область применения фундаментальных конструкций и понятий (полноты, регулярности и т.п.), заложенных в рамках алгебраического подхода много шире, чем только задачи анализа данных. Главный технический прием указанного подхода состоит в том, что элементарные классификаторы, используются не как объект оптимизации, а как источник базовых операторов, применение к которым соответствующих корректирующих операций и приводит к построению высококачественного алгоритма (решения).
Построение множества всевозможных элементарных классификаторов, равно как и различных частей этого множества, связано с вычислительными трудностями переборного характера. В связи с этим важно получение эффективных алгоритмов построения наиболее простых множеств элементарных классификаторов обеспечивающих точную классификацию.
Логические алгоритмы распознавания, используемые в качестве базовых, хорошо показали себя на практике при решении задач распознавания с бинарной информацией, и, как правило, могут быть использованы даже

при существенно неполной и противоречивой информации. Построение этих алгоритмов основано на выделении элементарных классификаторов в виде частичных описаний объектов, содержащих информацию о различиях классов.
Более точно задачу построения множества элементарных классификаторов можно поставить с использованием языка теории дизъюнктивных нормальных форм (ДНФ). В алгебраическом подходе указанные ДНФ строятся для характеристических функций классов (равных единице на описаниях объектов своего класса и равных нулю на описаниях объектов других классов). Как правило, построение дизъюнктивной нормальной формы характеристической функции класса К производится в два шага. На первом шаге строится ДНФ, которая обращается в ноль только на бинарных описаниях объектов из других классов. Затем из полученной ДНФ удаляются те конъюнкции, которые не обращаются в единицу на описаниях эталонных объектов классов К. На основании полученных формул решается вопрос о принадлежности нового объекта одному из классов. Сокращенной ДНФ характеристической функции класса при этом соответствует множество всевозможных элементарных классификаторов. Таким образом возникает задача построения ДНФ булевой функции с ограниченным, как правило небольшим, числом нулей (числом эталонных объектов).
Известно, что сокращенная дизъюнктивная нормальная форма имеет, как правило, экспоненциальный размер относительно множества входных переменных (признаков). Кроме того, множество элементарных конъюнкций ДНФ характеристической функции класса используется в качестве входного множества объектов для дальнейших построений в рамках алгебраического подхода, возникает необходимость построить указанное множество наиболее простым. В то же время, построение минимальной ДНФ булевой функции в общем случае является сложной переборной задачей, качество аппроксимации которой эффективными алгоритмами также невысоко [34, 35, 43].
Первые эффективные подходы к построению простых ДНФ булевых функций с малым числом нулей указал С.В. Яблонский. Его идеи были развиты в работах Ю.И. Журавлёва, А.Ю. Когана, А.Г. Дьяконова и других исследователей [5, 16, 39]. Предложенные ими эффективные алгоритмы позволяют строить достаточно простые ДНФ для различных классов булевых

3 ПЕ 2 ’

2п — /11 < /д -Ь 2/15 + /15 ~Ь 2/14 + /13
2п — /12 — /14 — /13 3/12 + 2/11 + /.10 + /Ц + 2/13
Оценим функцию ДИ):
Д-Д 2п — /12 + /11 + /1б 4~ 2/15 + 2/14 4- /13
Из определяющей максимум системы неравенств, получаем
/15 + /14/2 > 2/12 + /1з/2,
3(1 — £г)/12/2 + е/11 + /1б/2 + /14/2 + 2дз/2 > п(1 — е)/2,
(1 — е)(/11 + /15 + /1б/2 + /14 + цз/2) > п(1 — е).
Откуда Д£>) > 2п + Зп(1 — е)/2 + /12(1 + е)/2 + /13(1 + 2е)/2 > |п-
2п — /-1 < /11 + 2/15 + /10 + 2/14 "Ь /13
2п — /12 — /14 — /13 < 3/12 + 2/11 + Мб + /14 + 2/1з
Оценим функцию Д£>):
3/12 + 3/11 4~ 2/10 + 2/15 4~ З/14 + З/13.
Система неравенств в рассматриваемом случае имеет вид
-/11 - Уб/2 - /15 - /14 - /1з/2 <
-/12 - /11/2 - /16/4 - /14/2 - З/13/4 -п/2 -(1 + Зе)/12 - 2е/11 - /г6 - 2/14 - /13 < -«(1 - е)
-(1 + в)/11 - (1 + е)/16 - 2/1,5 ~ £/14 - 2е/13 <
Умножим первое неравенство на 4, второе на 8 и сложим с последними двумя
3(1 + е/3)/12 4~ 3(1 + е/3)/11 + 2(1 + е/6)/10+
2/15 + 3(1 + е/9)/14 + 3(1 + 2е/9)/13 > — (2-5)
Следовательно, ДО) > уп
Заметим, что оценки в случаях бис/ совпадают при е = 1/4 и равны Згг. При е < 1/4 оценка случая Ь является наименьшей, что завершает доказательство теоремы.