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

Сложность представления булевых функций дизъюнктивными нормальными формами (ДНФ) имеет большое значение в различных областях математики. Являясь наиболее интерпретируемым типов управляющих схем, ДНФ играют важную роль в теории сложности, задачах контроля, теории распознавания образов, пропозициональной логике и многих других областях математики [15, 18, 21, 31, 32, 36, 37, 44].

Задача распознавания.

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

Построение множества всевозможных элементарных классификаторов, равно как и различных частей этого множества, связано с вычислительными трудностями переборного характера. В связи с этим важно получение эффективных алгоритмов построения наиболее простых множеств элементарных классификаторов обеспечивающих точную классификацию.

Логические алгоритмы распознавания, используемые в качестве базовых, хорошо показали себя на практике при решении задач распознавания с бинарной информацией, и, как правило, могут быть использованы даже при существенно неполной и противоречивой информации. Построение этих алгоритмов основано на выделении элементарных классификаторов в виде частичных описаний объектов, содержащих информацию о различиях классов.

Более точно задачу построения множества элементарных классификаторов можно поставить с использованием языка теории дизъюнктивных нормальных форм (ДНФ). В алгебраическом подходе указанные ДНФ строятся для характеристических функций классов (равных единице на описаниях объектов своего класса и равных нулю на описаниях объектов других классов). Как правило, построение дизъюнктивной нормальной формы характеристической функции класса К производится в два шага. На первом шаге строится ДНФ, которая обращается в ноль только на бинарных описаниях объектов из других классов. Затем из полученной ДНФ удаляются те конъюнкции, которые не обращаются в единицу на описаниях эталонных объектов классов К. На основании полученных формул решается вопрос о принадлежности нового объекта одному из классов. Сокращенной ДНФ характеристической функции класса при этом соответствует множество всевозможных элементарных классификаторов. Таким образом возникает задача построения ДНФ булевой функции с ограниченным, как правило небольшим, числом нулей (числом эталонных объектов).

Известно, что сокращенная дизъюнктивная нормальная форма имеет, как правило, экспоненциальный размер относительно множества входных переменных (признаков). Кроме того, множество элементарных конъюнкций ДНФ характеристической функции класса используется в качестве входного множества объектов для дальнейших построений в рамках алгебраического подхода, возникает необходимость построить указанное множество наиболее простым. В то же время, построение минимальной ДНФ булевой функции в общем случае является сложной переборной задачей, качество аппроксимации которой эффективными алгоритмами также невысоко [34, 35, 43].

Первые эффективные подходы к построению простых ДНФ булевых функций с малым числом нулей указал C.B. Яблонский. Его идеи были развиты в работах Ю. И. Журавлёва. А. Ю. Когана, А. Г. Дьяконова и других исследователей [5, 16, 39]. Предложенные ими эффективные алгоритмы позволяют строить достаточно простые ДНФ для различных классов булевых функций с малым числом нулей. Однако, несмотря на вновь возросший в последнее десятилетие объем публикаций по минимизации функций в классе нормальных форм, вопрос о точных границах их сложности остается открытым.

Цели работы.

Цели настоящей работы следующие.

1. Получение новых и улучшении существующих нижних и верхних оценок минимального числа литералов и конъюнкций в реализации дизъюнктивными нормальными формами булевых функций различных классов от большого числа переменных с ограниченным числом нулей;

2. Оценка сложности комбинаторно-логических классификаторов, основанных на описании характеристических функций классов дизъюнктивными нормальными формами;

3. Оценка качества решения комбинаторно-логическими методами задач классификации с бинарными входными данными и непересекающимися классами.

Содержание работы.

В первой главе приводится обзор предшествующих публикаций по теме диссертации, постановка задачи распознавания образов и ДНФ-реализации булевой функции по матрице нулей. Кроме того вводятся ключевые определения и обозначения используемые в работе.

В первом параграфе первой главы излагается общепринятая терминология теории дизъюнктивных нормальных форм связанных исследованием изложенным в настоящей работе. Помимо этого в параграфе приведен ряд определений и обозначений, активно используемых в диссертации.

Второй параграф первой главы посвящен классификации булевых функций. В рамках параграфа даны описания рассматриваемых классов булевых функций, мотивация к их исследованию, описаны статистические свойства и ключевые определения. Пусть п размерность рассматриваемых далее булевых функций.

Класс состоит из всех булевых функций имеющих к нулейкласс состоит из всех таких функций матрицы нулей которых не имеют равных (с точностью до инверсии), а также не содержат нулевого и единичного столбцов. Класс Сп образуют приведенные функции от максимального числа переменныхкласс составляют функции из не имеющие соседних нулевых точеккласс Ф? А состоит из булевых функций класса Ф£, заданных такими матрицами нулевых точек, минимум из числа единиц и нулей в каждом столбце которых не меньше Л.

В параграфе изложен ряд статистических свойств булевых функций, позволяющий строить по оценкам сложности функций (типичных, экстремальных) одного из классов оценки сложности булевых функций (типичных, экстремальных) в других.

Указанные классы естественным образом возникают при анализе статистических свойств булевых функций с малым числом нулей. В параграфе также даны основные соотношения между данными классами.

В заключительном, третьем параграфе первой главы дается краткий обзор наиболее существенных результатов по минимизации сложности ДНФ булевых функций с малым числом нулей.

Во второй главе предложен метод сетей позволяющий построить высокие нижние оценки для функций классов Сп, Ф&tradeи Ф? Л. Суть предлагаемого метода состоит в выделении подмножеств булева куба небольшой мощность, но покрываемых малым числом конъюнкций.

В первом параграфе второй главы дается ряд вспомогательных утверждений и формулируется основная техническая лемма метода.

Целью второго параграфа второй главы является применение полученных результатов к получению нижней оценки сложности функций классов С11 и Ф£.

В третьем параграфе второй главы метод сетей применяется для построения высоких нижних оценок функций класса Ф^Л. Показано, что метод сетей может эффективно учитывать дополнительную информацию о структуре матрицы нулей булевой функции.

В третьей главе приведены эффективные методы синтеза ДНФ булевых функций различных классов.

Первый параграф третьей главы посвящен построению простых ДНФ функций класса Предложенный подход основан, в определенном смысле, на идеях, предложенных А. Г. Дьяконовым [4, 5].

Второй параграф третьей главы посвящен оценке сложности булевых функций классов и Рассуждения параграфа в целом основаны на применении идеи редукции.

Четвертая глава диссертационной работы посвящена анализу сложности и оценке качества решения комбинаторно-логическими методами задач классификации с бинарными описаниями объектов.

Основные результаты диссертации.

1. Предложен метод сетей, с использованием которого построены наилучшие из известных нижние оценки сложности представления дизъюнктивными нормальными формами ряда важных классов булевых функций.

2. Разработан подход к построению дизъюнктивных нормальных форм булевых функций с использованием последовательностей ортогональных разложений. С помощью указанного подхода получен ряд экстремальных оценок сложности дизъюнктивных нормальных форм булевых функций.

3. Получено обобщение редукционного подхода к построению простых дизъюнктивных нормальных форм. С использованием данного подхода для сложности дизъюнктивных нормальных форм ряда булевых функций доказаны верхние оценки, являющиеся в настоящий момент наилучшими.

Список полученных оценок.

Кратко напомним определения основных рассматриваемых классов булевых функций. Класс состоит из всех булевых функций имеющих к нулейкласс Ф£ состоит из всех таких функций матрицы нулей которых не имеют равных (с точностью до инверсии), а также не содержат нулевого и единичного столбцов. Класс С" образуют приведенные функции от максимального, относительно числа нулей, числа переменныхкласс составляют функции из Ф£ не имеющих соседних нулевых точеккласс класс Ф? Л (Ф?Л) состоит из булевых функций класса Ф?(Ф?), заданных такими матрицами нулевых точек, минимум из числа единиц и нулей в каждом столбце которых не меньше Л.

Всякой полной функции по формуле 1.1 может быть сопоставлена некоторая приведенная функция, полностью определяющая сложность ДНФ реализации исходной.

Рассматриваемые в работе классы связаны следующим рядом асимптотических статистических соотношений.

Почти все булевы функции класса при к = 2 п + ио (1) являются приведенными;

Почти всем правильным булевым функциям от п переменных, которые имеют не более к < 1о§-2 п — 1о§-2 1о§-2 п— нулей, при п —> оо по формуле 1.1 ставится в соответствие полная булева функция (Ю.И. Журавлёв и А. Ю. Коган);

Почти все функции класса Ф¹ лежат в классе.

• При m < | — (1 + е) у °2ёт> и к — о (2п) почти все функции классов и Фд содержаться в классе Фд т для произвольного положительного е.

Ниже приведен список основных оценок, полученных с использованием предложенных в диссертации методов (во всех оценках приведен главный член разложения).

1. Почти все функции класса имеют длину не более 2 lo" kn (предыдущая рекордная оценка — fc (lo&2^log2n));

2. Все функции класса при п = 2к~1 — poly (k) имеют ранг асимптотически равный 3п. В том числе функции класса Сп имеют ранг асимптотически равный 3п (предыдущая рекордная нижняя оценка 2? г, а верхняя 477,);

3. Все функции класса^7fclm имеют следующее ограничение на ранг.

7 ^ 10 Ъпе (к/2 — m) 1 rank D > —п——г. при е = 2—- ^.

3 3(1 + е)' к 4 ^ 10 13пе 1 1 rank D > —п—. при —.

3 9 + Зе F 4 3.

Используя ранее известные методы, можно построить нижнюю оценку (в общем случае) не более 2п;

Заключение

.