Построение логических классификаторов при ограничениях на сложность определяющих их дизъюнктивных нормальных форм тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

МАКСИМОВ ЮРИЙ ВЛАДИМИРОВИЧ

ПОСТРОЕНИЕ ЛОГИЧЕСКИХ КЛАССИФИКАТОРОВ ПРИ ОГРАНИЧЕНИЯХ

НА СЛОЖНОСТЬ ОПРЕДЕЛЯЮЩИХ ИХ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ

01.01.09. — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

2 9Н0Я2ии

Москва - 2012

005055930

005055930

Работа выполнена на кафедре «Интеллектуальные системы» факультета управления и прикладной математики Московского физико-технического института (государственного университета)

Научный руководитель:

Официальные оппопенты:

Ведущая организация:

Доктор физико-математических наук, профессор, академик РАН Журавлёв Юрий Иванович

Доктор физико-математических наук, профессор, академик РАН Матросов Виктор Леонидович, ФГБОУ ВПО Московский педагогический государственный университет, ректор.

Кандидат физико-математических наук Песков Николай Владимирович, ЗАО «Форексис», ведущий разработчик.

Московский государственный университет им. М.В. Ломоносова, факультет ВМК

Защита состоится

/ІГиСкл^.^

2012 г. в

(Р

часов на

заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государствешюм университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан _

2012 г.

Ученый секретарь диссертационного совета

Федько Ольга Сергеевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Несомненную значимость имеет сложность представления булевых функций дизъюнктивными нормальными формами в алгебраическом подходе к решению задач анализа данных, предложенном в работах академика РАН Ю.И. Журавлёва и развитом в многочисленных работах его учеников. В рамках алгебраического подхода элементарные классификаторы используются не в качестве области оптимизации, а как источник базовых операторов, применение к которым соответствующих корректирующих операций и приводит к построению высокоточного алгоритма. В то же время для построения корректного алгоритма над множеством элементарных классификаторов указанное множество должно быть достаточно полно.

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

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

При синтезе логических алгоритмов классификации число нулей характеристической функции класса (число эталонных объектов), как правило, не велико. С учетом этой особенности, C.B. Яблонским, Ю.И. Журавлёвым, АЛО. Коганом, А.Г. Дьяконовым и другими исследователями были предложены эффективные алгоритмы, которые позволяют строить достаточно простые ДНФ для различных классов булевых функций с малым числом нулей. Однако, вопрос о точных границах сложности ДНФ булевых функций с малым числом нулей остается в настоящее время открытым несмотря на многочисленные работы в этом направлении.

Целями работы являются:

1. Исследование типичной и экстремальной сложности минимальных и кратчайших ДНФ булевых санкций с малым числом нулей;

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

3. Разработка механизмов получения высоких нижних оценок сложности ДНФ булевых функций с малым числом нулей.

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

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

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

Методика исследования: методы теории вероятностей, теории сложности, дискретной математики, алгебры и теории множеств.

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

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

Апробация работы. Результаты, изложенные в диссертации, а также их практические приложения в разное время докладывались на

— 15-ой всероссийской конференции «Математические методы распознавания образов» (Петрозаводск, 2011);

— 35-ой конференции-школе «Информационные технологии и системы» (Петрозаводск, 2012);

— 9-ой Международной конференции «Интеллектуализация обработки информации» (Черногория, 2012);

— постер сессиях в рамках международных летних школ-семинаров по информационному поиску и базам данных НиБЭт/ЕОВТ (Санкт-Петербург, 2011) и Ш^Ш (Ярославль, 2012);

— научных семинарах; кафедры «Интеллектуальные системы» факультета управления и прикладной математики МФТИ(2009-2012), отдела Интеллектуальных систем ВЦ РАН(2009-2012) и Лаборатории структурных методов анализа данных в предсказательном моделировании при МФТИ (2012).

Личный вклад. Все выносимые на защиту результаты получены соискателем лично.

Публикации. По теме диссертации опубликовано 5 работ, в том числе 2 [1,2] — в изданиях из списка рекомендованного ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, разбитых на параграфы, заключения и списка литературы из 44 наименований. Общий объем работы составляет 75 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Скажем, что свойство Л выполнено для «почти всех» булевых функций из некоторого класса Р = Р(п), если при п —» оо доля функций класса, для которых указанное свойство не выполнено, стремится к 0.

В работе обозначено через Вп = {0,1}" множество всех булевых векторов размерности п; через 1„ (0„) обозначен вектор размерности п состоящий только из единиц (нулей соответственно); через #х обозначен вес булева вектора х, то есть минимум из числа его нулей и единиц; а через (п)+ обозначено множество {1,2,..., п}. Предполагается, что каждая булева функция /, рассматриваемая далее, задана своей матрицей нулевых точек (матрицей пулей), обозначаемой через М/, по строкам

которой перечислены все различные нули функции. Подматрица произвольной матрицы М, образованная пересечением строк гьг2,--,4 и столбцов обозначена через М-^] ''?*.

Ненулевой вектор а- 6 Вк назван в работе разложимым по векторам «], ...,аи если выполнены следующие равенства

а = V а2 V... V а1, < а, сц >=< а, а2 >= ... =<а,а1>= О,

где под символом <а,/3> понимается скалярное произведение векторов си и /3. Кроме того, если V«, ^ < о;*, сх^ >= 0 при г ф 3, то вектор а назван ортогонально разложимым по векторам «ь ..., о:4. В случае а = 1къ условиях предыдущего определения вектора {<Э!*}-=1 названы ортогональным разложением, единицы.

Рангом ДНФ в теории сложности булевых функций называется число содержащихся в ней литералов, а длиной ДНФ число входящих в нее конъюнкций. Указанные величины для произвольной ДНФ П обозначим гапк(О) и |£>| соответственно. Минимальная ДНФ соответствует ДНФ минимального ранга, а кратчайшая ДНФ соответствует ДНФ минимальной длины. Анализ различных мер сложности вызван неэквивалентностью понятий минимальной и кратчайшей ДНФ, доказанной Ю.И. Журавлёвым.

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

Обозначим через Р£ максимальный по включению класс различных булевых функций от п переменных, имеющих в точности

к различных нулей. Булева функция / € Р)! называется приведенной., если в ее матрице нулей отсутствуют нулевой и единичный столбцы, а также столбцы одинаковые с точностью до инверсии. Приведенные функции класса Р£ = Р^ ' 1 образуют класс С" полных функций. Ю.И. Журавлёвым и А.Ю. Коганом было показано, что построение ДНФ всякой булевой функции класса Р£ с малой сложностью сводится к построению соответствующей ей приведенной, а при к < п — п+1 нулей, построение ДНФ почти всех из них сводится в асимптотике к построению ДНФ полной функции.

Обозначим через класс всех приведенных функций, через Ч>1 класс тех из них, которые не имеют соседних нулевых точек в метрике Хемминга, а через класс булевых функций, который составляют все такие функции из столбцы матрицы нулей которых имеют вес не менее т.

Классы Р", С™, и естественным образом возникают на практике при решении задач анализа данных, а также важны при изучении статистических свойств булевых функций.

Лемма 1.1. Почти все булевы функции класса Р£ при к = 2к^2п + ш(1) являются приведенными.

Лемма 1.2. Почти все приведенные функции от п переменных, имеющие в точности к нулей, не содержат соседних нулей при п —>■ оо.

Лемма 1.3. Выберем произвольное е > 0. При тп < (1 + к = о(2") и ?2 ^ оо почти все функции клас-

са содержатся в классе

Литерал х? назван в работе собственным литералом конъюнкции К ДНФ £> функции /(х1,х2, ...,х„), если К — единственная конъюнкция Д содержащая х"\ Это понятие существенно при анализе сложности ДНФ.

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

Во второй главе предложен метод сетей, позволяющий построить высокие нижние оценки для функций классов С", Щ 11 Суть предлагаемого метода состоит в конструктивном

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

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

Заметим, что литерал х} функции /(х1,х2,..., хп) € Р£ входит в ДНФ не менее одного раза, если в матрице нулей М функции / не существует столбцов и их инверсий, которые бы образовывали вместе со столбцом ортогональное разложение единицы. Достаточно заметить, что если функция / не имеет соседних нулевых точек, то множество точек, смежных с нуля-

11

ми функции, не может быть покрыто с использованием одной конъюнкции.

Обобщение этого замечания дается основной технической леммой данного параграфа. Разрезанием матрицы М, являющейся тестом, на t частей при £ 1, назовем совокупность подматриц {М4}Ц таких, что матрицы Мь М2,..., Мг имеют одинаковое число столбцов; каждая строка матрицы М присутствует хотя бы в одной матрице М,-, 1 ^ г ^ £; число строк матрицы М совпадает с суммой числа строк в матрицах {М$}*=1.

Рассмотрим приведенную булеву функцию /(хь..., хп), заданную матрицей нулей М/ и не имеющую смежных нулевых точек. Зафиксируем ее литерал а{ € {0,1}. Пусть Г) — некоторая ДНФ функции /. Выделим в О различные конъюнкции, в количестве < штук, содержащие литерал

Лемма 2.4 (Случай конкретной ДНФ). Литерал х? входит еще как минимум в одну отличную от выделенных конъюнкцию из Л, если при любом разрезании матрицы М; на £ частей Мь М2,..., Мг существует такая матрица М3, что для функции Ф^- заданной матрицей М3, ни одна из выделенных конъюнкций не определяет разбиение х?.

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

На основе леммы 2.4 устанавливается ряд свойств полных и приведенных булевых функций высокой размерности. На основе

леммы 2.4 и статистических свойств биномиальных коэффициентов устанавливается оценка

Теорема 2.2. Минимальная ДНФ полной булевой функции от п переменных имеет ранг не меньший Зп (1 — е~]°ё2П/36).

Следствие 2.2.2. Минимальная ДНФ булевой функции класса имеет ранг не меньший чем Зп (1 — о(1)) при к = к^2п — к^2)п - Ц1).

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

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

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

Теорема 2.3. Ранг ДНФ реализации D функции / класса Ф"т ограничен снизу выражением

, „ 10 Ъпе (k/2-m) 1

rank D > —п — —--г, при е — 2——--- ^ -

3 3(1 + е) к 4

, „ 10 13пе ' 1 1

rank и > —п — --, при -<е<-.

3 9 + Зе F 4 3

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

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

Продемонстрируем идею конструкции на примере. Рассмотрим булевы функции f G Р£-1 и тр Е Р£, заданные матрицами нулей 5 и Ф соответственно и связанные соотношениями

v(fc>+ - -<k)+ . - "(fc>+ v -<fc)+> ® w(fc)+ - v -(*)+' Ofc = Л Щки = ЕЬ)+ л -(»)+• Тогда ДНФ Бф может быть получена из ДНФ D$ следующим образом

Д., = V xnxix2 V хпх3х4.

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

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

Путем между внешними литералами х? и х*1 в Яг, в работе названа последовательность переходов между внешними литералами внутри ребер гиперграфа, начинающаяся в х^ и заканчивающаяся в х"1. Заметим, что гиперграф НТ может быть достаточно велик, однако на практике нам нужна лишь его небольшая часть, которая может быть конструктивно выделена без анализа всего графа.

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

перграф назван в работе последовательностью ортогональных разложений.

Дальнейшие доказательства основаны на том, что в матрице нулей с большим числом столбцов можно эффективно выделить последовательность ортогональных разложений с небольшим (относительно числа столбцов) числом ребер. Лемма 3.1 утверждает, что в матрице высокой размерности указанная последовательность может содержать число ребер асимптотически равное числу столбцов матрицы нулей. Обозначим через Е(Н) множество гиперребер гиперграфа Н.

Лемма 3.1. Пусть для приведенной функции /(х\, х2, ...,х„) и теста Т существует последовательность ортогональных разложений Бт, содержащая все внешние литералы. Тогда функция / реализуется ДНФ Б3т, определяемой равенством

п3т = ОтУ у К[е],

е£Е(5т)

где К[е\ = хк> Х{22 при е = {ж,/,¡г,/,...,а^1}, а£)г —

произвольная ДНФ реализующая функцию заданную тестовой подматрицей.

Лемма указывает на естественный алгоритм построения ДНФ булевой функции высокой размерности. Первый шаг алгоритма состоит из построения соответствующего гиперграфа на п вершинах. На втором шаге строится ДНФ булевой функции, переменным которой соответствуют внешние вершины гиперграфа.

С использованием указанного подхода и построением последовательностей ортогональных разложений, основанных на разбиении булева куба на цепи, доказаны теоремы 3.1, 3.2 (с использованием теоремы 2.2) и 3.3.

Теорема 3.1. Функция класса С" с числом нулей к не менее 8 может быть реализована ДНФ ранга, не большего 3п + 6 п/ log2 п + 6n0-93 log2 п.

Теорема 3.2. Полная функция может быть реализована ДНФ, содержащей Зп(1 + о(1)) литералов и п(1 + о(1)) конъюнкций при п —> оо; при этом ни одна из границ асимптотически не улучшаема.

Теорема 3.3. Почти все приведенные функции класса Р£ при п > 2к~1 — кс, где С — произвольная положительная постоянная, могут быть реализованы ДНФ с числом литералов Зп(1 + о(1)) и числом конъюнкций ra(l + o(l)), при к —> оо. Каждая из полученных границ является асимптотически точной.

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

Теорема 3.4. Функции класса С" не обладают минимальными ДНФ среди функций класса Р£, п = 2к~г — 1.

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

Дальнейшие доказательства основаны на применении идеи редукции. Сформулировать идею можно следующим образом. ДНФ Dq булевой функции ф{хь х2,.... хп) может быть представлена в виде Вф — xiDv, V ¿ЁхДс, где функции ф и £ заданы булевыми матрицами с меньшим число столбцов и строк. Более того, при малом к ДНФ большинства функций класса Р£ могут быть представлены через ДНФ функций с числом нулей слабо отличающимся от гг/2. Следовательно, после применения редукционных разложений к первым t столбцам случайной функции класса Р£ можно ожидать, что число функций, множество нулей которых значительно превышает n/2t, будет невелико. Отметим, что функции с числом нулей не более log2n — г(п) при е(п) —> оо могут быть реализованы с использованием не более га(1 + о(1)) конъюнкций, а реализация произвольной функции может потребовать максимум пк конъюнкций.

Теорема 3.5. Зафиксируем произвольную монотонную функцию д(п), принимающую только положительные значения, которая удовлетворяет условиям д(п) = o(n1/,s), д(п) —> оо при п —У оо. Положим к = к.(п) > log2n/2. Пусть, дополнительно, для функции д(п) при определенном выше к = к(тг) выполнено 9{п) > (l - (log^maxjf ,l}) +ы(1)).

Определим ко = к0(п) равенством

к0 = log2 п - п ' д(Ы2п)-

Тогда для почти всех функций класса Рцп) при п —У оо выполнено

1^1 <П-2М£)[(1 + О(1)),

где ].т[ обозначено минимальное целое число не меньшее х.

Следствие 3.5.1. Выберем ка = к^2п—(к^27г)а, где 0.5<а< 1. Пусть к = к(п) > 71—(1о§2^)а- Тогда для почти всех функций класса Р"(п) при п —оо выполнено

|£>,| < п • 2М&)[(1 + о(1)) < 2-^(1 + о(1)), где ]х[ обозначено минимальное целое число не меньшее х.

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

Задача классификации, решаемая в настоящей главе, формулируется следующим образом. Рассматриваются две выборки векторов п-мерного признакового пространства: обучающая и контрольная. Каждому из элементов обучающей выборки сопоставлено (известное) подмножество конечного множества классов К1, К2, ...,К[. Решение задачи состоит в том, чтобы по имеющимся данным о выборках восстановить классы объектов, образующих контрольную выборку.

Первый параграф четвертой главы посвящен описанию модели алгоритмов вычисления оценок (АВО) для решения задач классификации. Отдельно рассматривается случай задач

19

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

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

Рассматривается задача классификации с непересекающимися классами 3- Обозначим 93(3) минимум по всем возможным разбиениям объектов контрольной выборки на классы максимального числа корректно классифицируемых алгоритмами вычисления оценок объектов контрольной совокупности задачи 3- В работе приведен ряд полиномиальных методов получения верхних оценок величины ®(3).

В заключении приводятся основные результаты диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Максимов Ю. В. Простые дизъюнктивные нормальные формы булевых функций с малым числом нулей // Доклады РАН. Серия «Математика». - 2012. Т. 445 №2 - С. 143-145.

2. Максимов Ю. В. Корректные алгебры над алгоритмами вычисления оценок в множестве регулярных задач распознавания с непересекающимися классами. // ЖВМиМФ. — 2009. Т. 49 m - С. 1327-1339.

3. Максимов Ю. В. Нижние оценки сложности реализации дизъюнктивными нормальными формами булевых функций специальных классов. // Труды 9-ой международной конференции «Интеллектуализация обработки информации» — М.: «МАКС Пресс», 2011. - С. 75-77.

4. Максимов Ю. В. Эффективная реализация некоторых классов булевых функций дизъюнктивными нормальными формами // Труды конференции ИТИС-35. ISBN 978-5-90115819-7. - 2012. - С. 105-107.

http ://www.itas2012.iitp.ru/pdf/1569607247.pdf

5. Максимов Ю. В. Эффективная реализация логических алгоритмов в задачах классификации с малым числом эталонов // Труды всероссийской конференции ММРО 15. М.: «МАКС Пресс», 2011. - С. 77-79.

МАКСИМОВ ЮРИЙ ВЛАДИМИРОВИЧ

ПОСТРОЕНИЕ ЛОГИЧЕСКИХ КЛАССИФИКАТОРОВ ПРИ ОГРАНИЧЕНИЯХ НА СЛОЖНОСТЬ ОПРЕДЕЛЯЮЩИХ ИХ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ

АВТОРЕФЕРАТ

Подписано в печать 28.09.2012. Печать трафаретная Усл.п.л. - 1,0 Заказ № 3741 Тираж: 90 экз. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение.

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

Цели работы.

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

Глава 1. Классы булевых функций, дизъюнктивных нормальных форм и их свойства.

1.1. Определения и обозначения.

1.2. Классификация булевых функций

1.3. Сложность реализации функций классов Сп, Ф£, Ф£Л, и Ф?)А

Глава 2. Нижние оценки сложности.

2.1. Метод сетей.

2.2. Нижние границы сложности функций классов Сп и

2.3. Нижние границы сложности функций класса А.

Глава 3. Верхние оценки сложности.

3.1. Верхние оценки сложности функций классов С71 и

3.2. Верхние оценки сложности функций классов и

Сложность представления булевых функций дизъюнктивными нормальными формами (ДНФ) имеет большое значение в различных областях математики. Являясь наиболее интерпретируемым типов управляющих схем, ДНФ играют важную роль в теории сложности, задачах контроля, теории распознавания образов, пропозициональной логике и многих других областях математики [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. Оценка качества решения комбинаторно-логическими методами задач классификации с бинарными входными данными и непересекающимися классами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Почти всем правильным булевым функциям от п переменных, которые имеют не более к < 1о§2 п — 1о§2 1о§2 п-\-\ нулей, при п —> оо по формуле 1.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п;

Заключение

1. Вебер К. О различных понятиях минимальности дизъюнктивных нормальных форм. // Проблемы кибернетики. 1979. В. 36. - С. 129-158.

2. Гуревич И.Б., Журавлёв Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания. // Кибернетика. — 1974. №3. — С. 16-20.

3. Дьяконов А.Г. Эффективные формулы вычисления оценок для алгоритмов распо-знавния с произвольными системами опорных можеств. //Ж. Вычисл. Матем. и Ма-тем. Физ. 1999. Т. 39. №11. — С. 1904-1918.

4. Дьяконов А.Г. Реализация одного класса булевых функций с малым числом нулей тупиковыми дизъюнктивными нормальными формами. //Ж. Вычисл. Матем. и Матем. Физ. 2001. Т. 41. №5. - С. 828-835.

5. Дьяконов А.Г. Тестовый подход к реализации дизъюнктивными нормальными формами булевых функций с малым числом нулей. //Ж. Вычисл. Матем. и Матем. Физ. — 2002. Т. 42. №6. С. 924-928.

6. Дьяконов А. Г. Построение дизъюнктивных нормальных форм в задачах распознавания образов с бинарной информацией // Доклады РАН. — 2002. Т. 383. №6. — С. 747-749.

7. Дьяконов А. Г. Построение дизъюнктивных нормальных форм в логических алгоритмах распознавания // Ж. вычисл. матем. и матем. физ. — 2002. Т. 42. №12. — С. 1899-1907.

8. Дьяконов А. Г. Построение ДНФ последовательным перемножением // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. №10. - С. 1589—1600.

9. Дьяконов А.Г. Алгебры над алгоритмами вычисления оценок. // М.: МГУ, 2006.

10. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: нормировка и деление. // Ж. вычисл. матем. и матем. физ. 2007. Т.47 №6. - С. 1099-1109.

11. Дюкова Е. В. Журавлёв Ю. И., Рудаков К. В. Об алгебро-логическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // Ж. вычисл. матем. и матем. физ. 1996. Т. 36. №8. - С. 215-223.

12. Дюкова Е. В., Журавлёв Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. — 2000. Т. 40. №8. С. 1264-1278.

13. Журавлёв Ю.И. О различных понятиях минимальности дизъюнктивных нормальных форм. // Сибирский математический журнал — 1960. Т. 1 №4. — С. 608-609.

14. Журавлёв Ю.И. Об отделимости подмножеств вершин гг-мерного единичного куба. // Тр МИАН СССР. 1958. Т 51. - С. 143-157

15. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. // Проблемы кибернетики. —- 1978. В. 33. — С. 5-68.

16. Журавлёв Ю.И., Коган А.Ю. Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи. //Докл. АН СССР. — 1985. Т. 285. №4. С. 795-799.

17. Журавлев Ю.И., Коган А.Ю. Алгоритм построения дизъюнктивной нормальной формы, эквивалентной произведению левых частей булевых уравнений нельсонов-ского типа //Ж. Вычисл. Матем. и Матем. Физ. — 1986. Т. 26. №8. — С. 1243-1249.

18. Журавлев Ю. И., Рязанов В. В., Сенько О. В «Распознавание». Математические методы. Программная Система. Практические применения. // М.: Фазис, 2006. С. 176.

19. Коган А.Ю. О дизъюнктивных нормальных формах булевых функций с малым числом нулей //Ж. Вычисл. Матем. и Матем. Физ — 1987. Т. 27 №6. — С.924—931.

20. Коган А. Ю. О нижних оценках сложности дизъюнктивных нормальных форм булевых функций с малым числом нулей // Ж. вычисл. матем. и матем. физ. 1987. — Т 27 №12 С 1868-1877.

21. Кудрявцев В. В., Андреев А. Е. О сложности алгоритмов. // Фундаментальная и прикладная математика — 2009. Т. 15. В. 3. — С.135-181

22. Максимов Ю. В. Корректные алгебры над алгоритмами вычисления оценок в множестве регулярных задач распознавания с непересекающимися классами. // Ж. вычисл. матем. и матем. физ — 2009. Т. 49 №7 С. 1327-1339.

23. Максимов Ю. В. Эффективная реализация логических алгоритмов в задачах классификации с малым числом эталонов // Труды всероссийской конференции ММРО-15. М . «МАКС Пресс», 2011 - С. 77-79.

24. Максимов Ю В. Простые дизъюнктивные нормальные формы булевых функций с малым числом нулей // Доклады РАН Серия «Математика». — 2012. Т. 445 №2 — С 143-145.

25. Максимов Ю. В. Нижние оценки сложности реализации дизъюнктивными нормальными формами булевых функций специальных классов. // Труды 9-ой международной конференции «Интеллектуализация обработки информации» — М «МАКС Пресс» 2011 С 75-77

26. Максимов Ю В Эффективная реализация некоторых классов булевых функций дизъюнктивными нормальными формами // Труды конференции ИТИС-35 ISBN 978-5-901158-19-7 2012 - С 105-107http•//www itas2012.ntp.ru/pdf/1569607247.pdf

27. Рудаков К В , Чехович Ю В Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов // Доклады РАН — 2003 Т 388 №1 — С 33-36

28. Соколов Н А Об оптимальной расшифровке монотонных функций алгебры логики //Ж вычисл матем и матем физ — 1982 Т 22 .V2 — С 449-461

29. Трофимов С В Об оптимальном уменьшении числа уравнений в системах нельсо-новского типа//Ж вычисл матем и матем физ — 1986 Т 26 N"10 — С 1552-1558

30. Яблонский С В , Лупанов О Б (ред ) Дискретная математика и математические вопросы кибернетики // Наука, М 1974

31. Яблонский С В Введение в дискретною математику Учебное пособие для вузов, 6-е изд //М Высшая школа, 2010

32. Воюь Е , Сгаша Y , Hammer Р L , Ibaraki Т , Kogan А , Makmo К Logical Analysis of Data Classification with Justification//Annals of Operations Research —2011 Vol 188 Iss 1 P 33-61

33. Djukova E , Inyakm A , Peskov N , Sakharov A Combinatorial (Logical) Data Analysis m Pattern Recognition Problems // Partem Recognition and Image Analysis — 2005 Vol 15 A0 1 P 46-48

34. Feldman V Hardness of approximate two-level logic minimization and РАС learning with membership queries // Journal of Computer and System Sciences — 2009 Vol 75 Iss 1 P 13-26

35. Helleistein L , Raghavan P Exact learning of DNF formulas using DNF hypotheses // J of Computet and System Sciences — 2005 Vol 70 Iss 4 — P 435-470

36. Keains M J , Vaziram U An Introduction to Computational Learning Theory // Cambndge MA MIT Press 1994

37. Kwck S Learning Intermediate Concepts //Lecture Notes m Computer Sciencc — 2001 Vol 2225 P 151-166

38. Miltersen P В , Radhakrishnan J , Wegener I On converting CNF to DNF // Theoretical

39. Computer Science. 2005. Vol. 347. Iss. 1-2. - P. 325-335.

40. Mubayi D., Turan G., Zhao Y. The DNF exception problem. //Theoretical Computer Sciencc. 2006. Vol. 352. Issues 1-3. - P. 85-96

41. Pippenger N. The shortest disjunctive normal form of a random Boolean function // Random Struct. Algorithms. 2003. Vol. 22. Iss. 2. P. 161-186.

42. Shannon C. The Symbolic Analysis of Relay and Switching Circuits // Trans. Am. Inst. Electrical Eng. 1938. Vol. 38. - P. 713.

43. Raab M., Steger A. Balls into bins — a simple and tight analysis. //Lecture Notes In Computer Science. 1998. Vol. 1518. - P. 159-170.

44. Umans C., Hardness of Approximating Eg Minimization Problems. //Foundations of Computer Science, IEEE Annual Symposium on. — 1999. — P. 465-475.

45. Wegener I. The Complexity of Boolean Functions. // NY: John Wiley & Sons, Inc. 1987.