Исследование в области сложности алгебро-логического анализа данных и синтеза распознающих процедур тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

СОТНЕЗОВ Роман Михайлович

Исследование в области сложности алгебро-логического анализа данных и синтеза распознающих процедур

01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 П!А? Ш

Москва-2012

005014001

005014001

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

Научный руководитель: доктор физико-математических наук, доцент

Дюкова Елена Всеволодовна

Официальные оппоненты: Обухов Юрий Владимирович, доктор физико-

математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт радиотехники и электроники им. В.А. Котельникова Российской академии наук, заведующий лабораторией.

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

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Научно-исследовательский институт системных исследований Российской академии наук.

Защита состоится «42» Q4 2012 г. в часов на заседании

диссертационного совета Д002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына Российской академии наук по адресу: 119333, Москва, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН Автореферат разослан « -?» ¿PS 2012 г.

Ученый секретарь

диссертационного совета Д002.017.02 д.ф.-м.н., профессор

В.В. Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Рассматриваются задачи, в которых требуется найти решение на основе анализа большого объема накопленных знаний. К ним относятся задачи классификации, распознавания и прогнозирования, возникающие в различных плохо формализованных областях таких, как медицинская диагностика и прогнозирование, обработка социологической информации, техническое и геологическое прогнозирование, анализ банковской деятельности и т. д. Для решения перечисленных задач успешно применяются методы распознавания образов, в частности методы, основанные на обучении по прецедентам.

Развиваемый в данной работе подход к задаче распознавания по прецедентам базируется на применении аппарата дискретной математики с использованием логических и алгебро-логических методов анализа данных. Основы проблематики были заложены в работах C.B. Яблонского, Ю.И. Журавлёва, М.Н. Вайнцвайга и М.М. Бонгарда.

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

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

Однако вопросы, связанные с практическим применением логического корректора, в [1] не исследовались.

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

Практическое использование логических процедур распознавания напрямую связано со снижением их вычислительной сложности. При большой размерности обучающей выборки возникает необходимость рассматривать труднорешаемые дискретные задачи перечисления решений. Это задачи поиска покрытий булевых и целочисленных матриц и построения нормальных форм логических функций. Е.В. Дюковой (1977 г.) предложен подход к решению указанных перечислительных задач, основанный на понятии асимптотически оптимального алгоритма. Показано, что при определенных условиях почти всегда исходную задачу Z можно заменить на более простую задачу эффективно решаемую, и такую, что, во-первых, множество решений задачи содержит множество решений задачи I, и, во-вторых, с ростом размера задачи 1 число ее решений асимптотически равно числу решений задачи 2Х. Обоснование данного подхода базируется на получении асимптотик для типичного числа решений каждой из задач 1 и Подход хорошо зарекомендовал себя на практике.

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

При предварительном анализе обучающей выборки и конструировании

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

оптимизационные задачи. Для их решения наряду с методами, имеющими

4

теоретическое обоснование, необходимо разрабатывать эвристические подходы, дающие хорошее приближенное решение.

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

Цели и задачи диссертационной работы. Были выделены следующие основные направления исследований.

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

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

2.2. Развитие методов корректного понижения значности целочисленных данных в задачах распознавания. Использование новых критериев качества перекодирования.

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

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

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

3.3. Получение новых асимптотических оценок для количественных характеристик множества покрытий булевых и целочисленных матриц.

Получение аналогичных оценок для нормальных форм логических функций.

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертации докладывались на следующих конференциях:

1. 9th International Conference on Pattern Recognition and Image Analysis: new Information Technologies (PRIA-9-2008), Нижний Новгород, сентябрь 2008 г.

2. Восьмая Международная конференция «Дискретные модели в теории управляющих систем», Москва, апрель 2009 г.

3. Всероссийская конференция «Математические методы распознавания образов» (ММРО-14), Суздаль, сентябрь 2009 г.

4. Восьмая Международная конференция «Интеллектуализация обработки информации - 2010», Республика Кипр, Пафос, октябрь 2010 г.

5. Second International Conference «Classification, Forecasting, Data Mining», Болгария, Варна, июнь 2010 г.

6. Всероссийская конференция «Математические методы распознавания образов» (ММРО-15), Петрозаводск, сентябрь 2011 г.

7. Научная конференция «Ломоносовские чтения», г. Москва, МГУ, ноябрь 2011 г.

Результаты работы докладывались и обсуждались на научных семинарах Учреждения Российской академии наук Вычислительный центр им. А.А. Дородницына РАН и кафедры Математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Публикации. По теме диссертации опубликовано 11 статей, в том числе 4 статьи в изданиях из списка, рекомендованного ВАК РФ. Основные результаты, полученные в диссертации, включались в научные отчеты по проектам РФФИ 07-01-00516-а, 10-01-00770-а и в отчеты по грантам президента РФ по поддержке ведущих научных школ НШ №5294.2008.1 и НШ №7950.2010.1.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы из 68 наименований. Общий объем работы -112 страниц.

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

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

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

Задача распознавания по прецедентам рассматривается в стандартной постановке для целочисленной информации. Исследуется некоторое множество объектов М, про которое известно, что оно представимо в виде объединения непересекающихся подмножеств (классов) К^—.К^ Объекты множества М описываются набором целочисленных признаков х1( ...,хп, каждый из которых имеет конечное число допустимых значений. В качестве исходной информации дано множество объектов Т = {З^, ...,5т} из М, о которых известно каким классам они принадлежат (обучающая выборка). Требуется по предъявленному набору значений признаков х1,..., хп, описывающему некоторый объект 51 из М, определить класс, к которому относится объект 5.

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

Пусть Я = [Х]^ - набор из г различных признаков, г <п, и пусть

сг = (о^, ...,сгг), а;- допустимое значение признака Х]. при г = 1,2, ...,г. Пара (Я, сг) называется элементарным классификатором (эл.кл.). Близость объекта Я = (а1,..., ап) из М и эл.кл. (Я, сг) оценивается величиной

Пусть и — {(Ях,стг),...,(Нц>ОдУ\ - набор эл.кл, Б ЕМ. Положим =

Определение 1.1.1. Набор эл.кл. II называется корректным для класса К, К £ [К1,..., Щ, если существует функция алгебры логики Ри к такая, что для любых двух объектов 5' и 5" из обучающей выборки, таких что 5' е К, 5" £ К выполняется неравенство

Определение 1.4.1. Корректный набор эл.кл. У с корректирующей функцией Ри к называется монотонным корректным для класса К, если Ри к -монотонная булева функция и ^кО^и (.!>")) = 1 для любого обучающего объекта 5' класса К.

1, если а;-. = аи I = 1,2,..., г, .0, в противном случае.

.....В(я„ач)00).

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

Далее рассматриваются распознающие алгоритмы, работающие по следующей схеме. Для каждого класса К, К Е {К±1 распознающий

алгоритм А конструирует некоторое подмножество №Л(К) множества корректных наборов эл.кл. класса К. Распознавание объекта 5 производится на основе вычисления оценок принадлежности этого объекта к классам Къ ....К^ Оценки вычисляются следующим образом.

Пусть Я(Т, К) - множество обучающих объектов из Т, принадлежащих К, Я (Г, К) - множество обучающих объектов из Т, не принадлежащих К.

Случай 1. Множество №Л(К) состоит из корректных наборов эл.кл. класса К, не обязательно являющихся монотонными. Пусть У £ 14^,(/С), = ц. Положим

§1 /"5' о _ (1, если 0)^(5) = <иу(5'), " (0, иначе.

Тогда оценка принадлежности объекта 5 к классу К имеет вид

Г1№Ю = Л?,^5'"51

где суммирование проводится по всем (и,5') из №А(К) X И(Т,К).

Случай 2. Множество 1УА (К) состоит только из монотонных корректных

наборов эл.кл. класса К. Пусть и 6 ]Л/А(К), \и\ = ц. Положим

_ (1,если о)и(5) > о)(/(5'), , иначе,

гдес<%(5) > (Ну(5'), &>„(£) = (а1( ...,ач), а)у(5') = (а^,а'ч), означает, что аг > а\ при I = 1,2,..., q.

В этом случае оценка принадлежности объекта Я к классу К имеет вид

^'Мо1:;

Г2&Ю - ш т X

|й(т,/011^(101^

ю

где суммирование проводится по всем (£/,5') из УУА(К) х Й(Г, К).

Разработаны и реализованы распознающие алгоритмы А1, А2, АЗ, А4, работающие по описанной выше схеме. В качестве базисных алгоритмов используются одноэлементные эл.кл., то есть эл.кл. вида (х],а), где а -допустимое значение признака Ху. Для построения корректных наборов эл.кл. используются генетические алгоритмы, каждый из которых запускается 10 — 15 раз для получения наилучшего результата. Особями популяции в генетических алгоритмах являются корректные наборы эл.кл.

Алгоритмы А1 и А2 решают задачу построения коллектива корректных наборов эл.кл., в котором каждый набор обладает хорошей распознающей способностью. Алгоритм А1 решает указанную задачу в случае 2, алгоритм А2 в случае 1.

Для построения коллектива корректных наборов эл.кл. исходная выборка разбивается случайным образом на две подвыборки Т0 и 7\ таких, что |7Ы/|Гг| = 4. Подвыборка используется для построения корректных наборов эл.кл., а подвыборка 7\ для оценки качества распознавания построенных корректных наборов эл.кл. Пусть (?0 = И(Т0,К), = Д('Т^К), = ЩТ^К). Оценка распознающей способности корректного набора эл.кл. имеет следующий вид

1 (5,5')е<?ох<?1 ^^(адОеСохоГ

где = для А1 и 8и(5,Б') = 5^(5,5') для А2.

Алгоритмы АЗ и А4 решают задачу построения одного корректного набора эл.кл. по мощности близкого к минимальному соответственно в случаях

2 и 1. Функция приспособленности особи в генетическом алгоритме -мощность корректного набора эл.кл.

Тестирование разработанных алгоритмов проводилось на реальных задачах. Наилучшие результаты показал алгоритм А1.

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

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

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

Л(Ю= X V = щ I ?

;ек2Сн) ШЛЮ 1

здесь Я - кодирующее покрытие, с,-, ] 6 {1,2, ...,п), - число единиц в у—ом столбце матрицы 1Т, Я^Я) - множество номеров столбцов 1Т, входящих в Я, Я2(Н) - множество номеров столбцов матрицы Ьт, не входящих в Я. Ставится задача минимизации функционалов Д(Я) и /2 (Я).

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

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

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

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

где к0 - число мутируемых генов на последнем шаге алгоритма, С - параметр, регулирующий скорость изменения числа мутируемых генов.

Эффективность построенных алгоритмов оценена на тестовых задачах, содержащихся в электронной библиотеке OR Library. Эти задачи состоят из 65

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

Проведено сравнение построенных в работе генетических алгоритмов с двумя алгоритмами, имеющими теоретические оценки точности. Первым алгоритмом является градиентный алгоритм, в качестве второго алгоритма выбран один из вариантов алгоритма General (A.A. Агеев, 2004 г.). Сравнение на большом числе случайных матриц показало, что генетические алгоритмы, как правило, превосходят по точности решения как градиентный алгоритм, так и алгоритм General, что говорит об их практической ценности.

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

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

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

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

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

Пусть Мщп - множество всех матриц размера т х п с элементами из {ОД,..., к — 1}, к > 2; к >2, г < л, - множество всех наборов вида (о-!,.., <гг), где (Т; е {ОД,..., к - 1}, I = 1,2,..., п.

Пусть Ь 6 МтП, Н - набор столбцов матрицы а е ЕЦ, а — (с^,.., аг). Набор столбцов Н называется тупиковым а —покрытием, если выполнены следующие два условия: 1) подматрица ЬИ матрицы образованная столбцами набора Н, не содержит строку а, 2) для каждого р е{1,2, ...,г} подматрица 1Нсодержит по крайней мере одну из строк вида (Д,.., /?г) £ в которой /?р Ор и = ау при у 6 {1,2,..., г}\{р}, т.е. ЬИсодержит а —подматрицу.

Если выполнено только условие 1), то набор столбцов Н называется а — покрытием матрицы I. Если выполнено только условие 2), то набор столбцов Н называется а — совместимым набором столбцов матрицы I.

Нетрудно видеть, что понятие (тупикового) (0,0, ...,0)-покрытия булевой матрицы совпадает с понятием (неприводимого) покрытия булевой матрицы. Отметим, что (0,0, ...,0)-подматрица булевой матрицы является единичной подматрицей.

Пусть I 6 Положим 5{1, а), а 6 ££ - множество всех а —подматриц матрицы I, С{1,а), а£Я[ - множество всех а —покрытий матрицы I, В(Ь, сг), а £ Ек, - множество всех тупиковых а —покрытий матрицы I, 11(1, о),о £ Егк, - множество всех а —совместимых наборов столбцов матрицы I.

Пусть далее

ЗД = иаеЕ^(Ь,а) , Сг{1) = 1>аеЕгСа,ст) , ВгЮ = и„щВ&о) , В(Ь) = и?=1ВГ(£), УгШ = истеЕг и а, су) , иа) = и?=1 иг ах

гх(/с) = [1оек7П-1оек1п^кт-1],

г2 (к) = ]1обк т + 1ояк 1одк т + logk 1одк п[,

Рг(к) = ехр(-т/Гг) (1 - ехр(-т(А: - 1)к~г))г,

/п ® 9п>п °°> означает, что /п = дп(1 + ¿>п), где 6п -» 0 при п -* со;

/п ~ 0п»п 00 > означает, что /„ < + 5П), где 5П -> 0 при п -* со;

|К| - мощность множества V.

В разделе 4.2 доказаны следующие теоремы.

Теорема 4.2.1. Если п<т< к™", ¡3 < 1/2, то для почти всех матриц I из М^п ПРИ п со справедливо

Г=Га(к)

г2 Ю

г=гЛЮ г2(Ю

2)|У<7,)|« У ¡ига)1* У С£кг(1-ехр(-т(к-1)к-г))г;

г=п(к)

г=г,(к)

3) £ 1ВГ(1)1 - \вгг{к){1)\ « |5Гг(к)(Ц| «

ггг2(к)

« 2 ШЩ - КадС^! - сг/к)к^рык)(к) *

ггг2(*с)

« - ехр(-т(/с - 1

Теорема 4.2.2. Если т < кпР,/? < 1/2, то при п -> оо для почти всех матриц I из справедливо

1) £ |вг(ь)1* * \сГ1(к)а)\ *

Г£Г1(к)

* Сг/к)к^к%(к) * сг/к)кг^ ехр(-тк-^Ю);

2) £ 1ВД| » |1/Г1№)(«| «

г<гг(к)

р

Замечание 1. До настоящего момента для рассматриваемого случая п <т < к , /? < 1/2, была известна лишь асимптотика ^к|В(Х)| (Е.В. Дюкова, 2007 г.).

Замечание 2. Оценки, приведенные в утверждении 1 теоремы 4.2.2 впервые получены Е.В. Дюковой (2002 г.). В данной работе удалось получить более простое доказательство этого утверждения.

Приведены аналоги теорем 4.2.1 и 4.2.2 для количественных характеристик неприводимых покрытий булевой матрицы и (0,0,... ,0) — совместимых наборов столбцов булевой матрицы.

Таким образом, показано, что при п <т < кпР, /? < 1/2 для почти всех матриц £ из при п -» оо число всех тупиковых покрытий и число всех совместимых наборов столбцов матрицы А асимптотически равно соответственно числу тупиковых покрытий и числу совместимых наборов столбцов, длины которых принадлежит интервалу [т^(/<:),г2(/с)]. Также показано, что при п<т< кп1<, ¡3 < 1/2 для почти всех матриц £ из М^п при п со число тупиковых покрытий с длиной не меньше, чем г2(/с), асимптотически равно при п -» со, во-первых, числу совместимых наборов столбцов с длиной не меньше, чем г2(к), и, во-вторых, числу а - подматриц с рангом г2(/с).

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

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

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

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

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

Пусть <2(1) - конечная последовательность наборов столбцов матрицы Ь из МтП, содержащая множество Предполагается, что некоторые

элементы в <?(£) могут повторяться. Пусть алгоритм А строит (¿(Ь) с полиномиальной задержкой, т.е. на каждом шаге строится очередной набор из () и при этом выполняется не более <1 элементарных операций, где с1 ограничено сверху полиномом от т и п. Пусть - число шагов алгоритма А (число элементов в (?(/-)). При построении очередного элемента из (¿(Ь) алгоритм А проверяет его на принадлежность В(Ь). Очевидно, что такая проверка может быть осуществлена за полиномиальное от размера матрицы время. Если построенный набор столбцов принадлежит В(1), то дополнительно проверяется, был ли этот набор построен ранее алгоритмом А. Требуется, чтобы данная проверка осуществлялась за полиномиальное от размера матрицы время.

Алгоритм А является асимптотически эффективным, если N¿(1) й ^ р(т,п) х |В(/,)| при п -> оо для почти всех матриц £ из М£п, где р(т,п) -полином от т и п. Если р(т,п) = 1, то алгоритм А называется асимптотически оптимальнъш.

Пусть алгоритм А строит множество тупиковых покрытий В(Ь) матрицы 6 М^п путем перечисления (без повторений) с полиномиальной задержкой множества СГ(Ь) или некоторого его подмножества, Л/л(£) - число шагов алгоритма А. Известно, что в случае та <п< к"1*1, а> 1, /? < 1, алгоритм А является асимптотически оптимальным. В диссертационной работе доказана следующая

Теорема 4.4.4. Если п <т < кп\ р < 1/2, то для почти всех матриц Ь из при п -> оо справедливо

.2

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

1. Sotnezov R.M. Genetic Algorithms in Problems of Discrete Optimization and Recognition // 9th International Conference "Pattern Recognition and Image Analysis: New Information Technologies" (PRIA-9-2008): Conference Preceedings. Vol. 2. - Nizhni Novgorod, 2008. P. 173-175.

2. Сотнезов P.M. Генетические алгоритмы в задаче о покрытии. Сборник тезисов лучших дипломных работ 2008 года. М. Издательский отдел факультета ВМиК МГУ, 2008, с. 73-74.

3. Sotnezov R.M. Genetic Algorithms for Problems of Logical Data Analysis in Discrete Optimization and Image Recognition // Pattern Recognition and Image Analysis, 2009, Vol. 19, No 3, pp. 469-477.

4. Дюкова E.B., Сизов A.B., Сотнезов P.M. Об одном методе построения приближённого решения для задачи о покрытии // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов». М.: МАКС Пресс, 2009. С. 241-243.

5. Сотнезов P.M. Генетические алгоритмы в задаче о покрытии // Восьмая международная конференция «Дискретные модели в теории управляющих систем». Москва, 2009 г. Электронный сборник материалов конференции. С. 179-183 ('http://dmconf.ni/dm8/proceedings.pdf).

6. Дюкова Е.В., Сотнезов Р.М. О сложности дискретных задач перечисления // Докл. Акад. Наук. 2010. Т. 143. №1. С. 11-13.

7. Djukova E.V., Zhuravlev Yu.I., Sotnezov R.M. Synthesis of Corrector Family with High Recognition Ability // New Trends in Classification and Data Mining. Sofia, 2010.-P. 32-39.

8. Дюкова E.B., Сотнезов P.M. О сложности перечисления элементарных классификаторов в логических процедурах распознавания // Интеллектуализация обработки информации: 8-я международная конференция. Кипр, г. Пафос, 17-23 октября 2010 г.: Сборник докладов. -М.: МАКС Пресс, 2010. - С. 43-46.

9. Дюкова Е.В., Сотнезов P.M. Асимптотические оценки числа решений задачи дуализации и ее обобщений // Ж. вычисл. матсм. и матем. физ. 2011. Том 51, № 8. С. 1531-1540.

10. Djukova Е.У., Zhuravlev Yu.I., Sotnezov R.M. Construction of an Ensemble of Logical Correctors on the Basis of Elementary Classifiers // Pattern Recognition and Image Analysis, 2011, Vol. 21, No. 4, pp. 599-605.

11. Дюкова E.B., Сизов A.B., Сотнезов P.M. О корректном понижении значности данных в задачах распознавания // Доклады Всероссийской конференции «Математические методы распознавания образов» (ММРО-15), г. Петрозаводск, 11-17 сентября 2011 г. С. 80-83.

Заказ № 162-П/02/2012 Подписано в печать 29.02.2012 Тираж 100 экз. Усл. п.л.1

ООО "Цифровичок", тел. (495) 649-83-30 www.cfr.ru; е-таИ:т/о@с/г.ги

61 12-1/995

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

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

СОТНЕЗОВ Роман Михайлович

Исследование в области сложности алгебро-логического анализа данных и синтеза распознающих процедур

01.01.09 - Дискретная математика и математическая кибернетика

диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д.ф.-м.н. Е.В. Дюкова

V Р

у"

Москва-2012

Оглавление

Введение.............................................................................................................................4

Глава 1. Синтез процедур распознавания с использованием алгебро-логического подхода.............................................................................................................................27

1.1. Основные определения........................................................................................27

1.2. Модель голосования по корректным наборам эл.кл. класса...........................29

1.3. Построение корректных наборов эл.кл. класса.................................................30

1.4. Модели голосования по монотонным и антимонотонным корректным наборам эл.кл. класса...........................................................................................32

1.5. Связь алгебро-логического подхода с классическими логическими процедурами распознавания...............................................................................35

1.6. Обобщение алгебро-логического подхода на случай произвольного набора распознающих алгоритмов.................................................................................37

1.7. Сложность задачи перечисления корректных наборов эл.кл.........................38

1.8. Тестирование моделей голосования по (монотонным) корректным наборам эл.кл. классов........................................................................................................39

Глава 2.Корректное понижение значности информации в задачах распознавания..44

2.1. Основные определения........................................................................................45

2.2. Алгоритмы поиска оптимальной корректной перекодировки КОД1.............47

2.3. Однокритериальные генетические алгоритмы поиска оптимальной корректной перекодировки КОД2, КОДЗ, КОД4.............................................49

2.4. Двухкритериальный генетический алгоритм поиска оптимальной корректной перекодировки КОД5......................................................................50

2.5. Результаты тестирования....................................................................................50

Глава 3.Генетические алгоритмы в задачах дискретной оптимизации......................55

3.1. Постановка задачи...............................................................................................56

3.2. Представление особей в генетическом алгоритме...........................................58

3.3. Формирование начальной популяции................................................................59

3.4. Функция приспособленности и выбор родительских особей..........................60

3.5. Операторы скрещивания и мутации..................................................................61

3.6. Восстановление допустимости решения...........................................................63

3.7. Обновление популяции.......................................................................................65

3.8. Описание алгоритмов ОАВтагу и ОА1ЧопВтагу.............................................66

3.9. Результаты вычислений на тестовых задачах...................................................68

3.10. Адаптация алгоритмов ОаВтагу и ОаМопВтагу для многопроцессорных комплексов............................................................................................................73

Глава 4. Метрические свойства множества тупиковых покрытий булевых и целочисленных матриц...................................................................................................76

4.1. Основные понятия и результаты, полученные ранее.......................................77

4.2. Метрические свойства множества покрытий булевых и целочисленных матриц в случае п <т........................................................................................83

4.3. Метрические свойства множества максимальных конъюнкций двузначной логической функции в случае п < т.................................................................94

4.4.0 сложности алгоритмов построения тупиковых покрытий булевых и целочисленных матриц, основанных на перечислении совместимых наборов столбцов................................................................................................................98

Заключение.....................................................................................................................103

Список литературы........................................... .............................................................105

Введение

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

Постановка задачи распознавания по прецедентам заключается в следующем. Исследуется некоторое множество объектов М, про которое известно, что оно может быть разбито на непересекающиеся подмножества (классы) Кг,...,К1,1 > 2. Под прецедентной (обучающей) информацией понимается совокупность примеров описаний изучаемых объектов, полученная на основе измерения или наблюдения ряда характеристик этих объектов, а также те «ответы», которые должен был бы дать «идеальный» алгоритм, решая задачу классификации для заданной совокупности описаний. Подлежащие измерению или наблюдению характеристики называются признаками. Требуется уметь классифицировать объекты, не вошедшие в обучающую выборку, т.е. по признаковому описанию каждого такого объекта определять, какому классу он принадлежит. Фактически нужно сравнить вновь предъявленное описание с материалом обучения. Существуют разные мнения о том, как проводить подобное сравнение.

Развиваемый в данной работе подход к задаче распознавания по прецедентам базируется на применении аппарата дискретной математики с использованием логических и алгебро-логических методов анализа данных. Основы проблематики были заложены в работах C.B. Яблонского, Ю.И.

Журавлёва, М.Н. Вайнцвайга и М.М. Бонгарда [4, 6, 7, 9, 42] и развиты в [3, 8, 10-27, 33, 50-62].

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

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

Пусть {х1,...,хп} - совокупность целочисленных признаков, используемая для описания объектов из М и пусть Я = ...,Х]г}- набор из г различных признаков, г < п, а = (аг>... ,аг), а^- допустимое значение признака х^ при I = 1,2,..., г (предполагается, что число допустимых значений каждого признака ограничено). Пара (Я, о) называется элементарным классификатором (эл.кл.).

Пусть 5 = (а1; ...,ап), Б ЕМ. Набор признаков Н = {х;1,... ,х)г} выделяет в описании объекта 5 фрагмент (а;1,..., а^), который обозначается через (5, Я).

Близость объекта 5 из М и эл.кл. (Я, <т) оценивается величиной Д(ад(5) равной 1, если (5, Я) = о, и равной 0, в противном случае.

Построение распознающего алгоритма А основано на конструировании для каждого класса К, К Е {Къ ..., К¿}, множества эл.кл. СА(К) и проведении процедуры голосования по каждому эл.кл. из СА(К{) и СА(К2) и ... и С^К^).

В зависимости от значения функции 5(Яо.)(5), (Я;<т) £ СА(К), распознаваемый объект 51 либо получает голос за принадлежность классу К, либо не получает этого голоса. Оценка Г(5, К) принадлежности объекта 5 классу К вычисляется на основе суммирования голосов, полученных при голосовании по всем эл.кл. из СА(К). Анализ оценок Г (б1, Кг),..., Г (5, К{) позволяет классифицировать объект Я.

Особое внимание уделяется понятию корректного эл.кл. класса К.

Пусть Т - обучающая выборка, К £ {Кг,..., Кг], К = {Кх и ... и К^К. Предполагается, что любые два обучающих объекта из Г, принадлежащие разным классам, имеют разные описания.

Эл.кл. (Я, сг) не является корректным для класса К, если выполнены два условия: 1) (5', Я) = а хотя бы для одного обучающего объекта 5' из К; 2) (5", Я) = о хотя бы для одного обучающего объекта 5" из К. Во всех остальных случаях эл.кл. (Я, сг) считается корректным для К. В существующих алгоритмах используются корректные эл.кл. трех типов, перечисленных ниже.

Эл.кл. типа 1. Выполнено условие 1), но не выполнено условие 2).

Эл.кл. типа 2. Не выполнено условие 1), но выполнено условие 2).

Эл.кл. типа 3. Не выполнено условие 2).

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

Рассмотрим примеры таких алгоритмов.

В алгоритмах голосования по представительным наборам [4, 15, 17, 23, 24, 51, 52, 54, 57, 58] множество СА(К) состоит из корректных эл.кл. типа 1. Пусть (Я, сг) - корректный эл.кл. для класса К типа 1. Тогда существует обучающий объект Б' Е К такой, что (£', Я) = а и для любого обучающего объекта 5" е К выполнено (5", Я) ^ ст. Фрагмент (5"', Я) называется представительным набором для класса К.

В простейшей модификации модели алгоритма голосования по представительным наборам оценка принадлежности К) объекта 5 к классу К имеет вид

где СА (К) - используемое подмножество эл.кл. для К, Я (Т, К) - множество обучающих объектов из К. Очевидно, алгоритм голосования по представительным наборам является корректным.

Другим примером корректного алгоритма является модель алгоритма голосования по антипредставительным наборам [23, 24], в которой используются корректные эл.кл. типа 2. Антипредставителъный набор - это фрагмент (5", Я), где 5" - обучающий объект из К, при этом для любого обучающего объекта Б' из К выполнено (З^Я) Ф (5Я). В простейшей модификации данной модели оценка принадлежности Г2(5', К) объекта 5 к классу К имеет вид

где СА(К) - используемое подмножество корректных эл.кл. для К типа 2, Я (Г, К) - множество обучающих объектов из К.

(.н,сг)есА(к) 5'е/?(гд), (5',Я)=(Т

В тестовых алгоритмах осуществляется поиск специальных наборов признаков - тестов. Набор признаков Я = {хд, ...,Xjr), Я Q {х1> ...,хп} называется тестом, если для любого класса К Е {Къ ...,К{] и любого обучающего объекта SEK фрагмент (S, Я) является представительным набором класса К. Таким образом, тестом является набор признаков, позволяющий различать любые два обучающих объекта из разных классов.

В алгоритмах голосования по покрытиям классов строятся эл.кл. типа 3 [23, 24]. Оценка за класс К аналогична оценке Г2(5, К).

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

Пусть L - булева матрица размера тхп, Н - набор столбцов матрицы L. Набор столбцов Я называется покрытием матрицы L, если каждая строка матрицы L в пересечении, хотя бы с одним столбцом из Я дает 1. Покрытие называется неприводимым, если никакое его подмножество не является покрытием. Покрытие называется минимальным, если не существует покрытия меньшей мощности. Очевидно, что неприводимое покрытие содержит каждую из строк (1,0, ...,0), (ОД, ...,0),(ОД ...,1), то есть содержит единичную подматрицу.

Для нахождения (тупиковых) тестов, а также (тупиковых) представительных наборов строится специальная булева матрица L* (матрица сравнения). Каждая строка этой матрицы образуется в результате сравнения двух обучающих объектов из разных классов. При этом в столбце с номером j ставится 1, если сравниваемые объекты различаются по признаку Xj, и ставится 0 в противном случае.

Пусть S1,...,Sm - обучающие объекты и пусть L*, i Е {1, ...,т} -подматрица матрицы L*, которая образована сравнением обучающего объекта

со всеми обучающими объектами, не принадлежащими тому же классу, что и объект

Очевидно, что набор признаков (хд,..., х^] является тупиковым тестом тогда и только тогда, когда набор столбцов матрицы I* с номерами ]г>... ,]г является неприводимым покрытием.

Очевидно также, что фрагмент Я), - обучающий объект класса К, К Е {К1, ...,К{\, является (тупиковым) представительным набором для класса К тогда и только тогда, когда набор столбцов матрицы Ь\ с номерами из Я является (неприводимым) покрытием.

Задача построения неприводимых покрытий булевой матрицы может быть сформулирована как задача преобразования конъюнктивной нормальной формы монотонной булевой функции в сокращённую дизъюнктивную нормальную форму (как задача построения максимальных конъюнкций монотонной булевой функции) [43]. Данная задача, называемая также дуализацией, относится к числу труднорешаемых задач перечисления решений.

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

Важный результат получен в работе Фридмана М. и Хачияна Л. [63], в которой для дуализации построен инкрементальный квазиполиномиальный алгоритм. В данном случае инкрементальность означает, что алгоритму разрешено на каждом шаге просматривать множество решений, построенных на предыдущих шагах, и на этот просмотр тратить время, ограниченное

квазиполиномом не только от размера задачи, но и от числа найденных решений.

В России вопросы снижения вычислительной сложности задачи дуализации исследуются с середины 20-го столетия [42, 43]. В конце 1970-х годов были разработаны первые эффективные алгоритмы для практически важных случаев этой задачи. В частности, в работах [10, 11] были предложены и теоретически обоснованы модели тестовых алгоритмов распознавания, основанных на асимптотически оптимальном перечислении множества неприводимых покрытий булевой матрицы.

Пусть В(Ь, 0) - множество неприводимых покрытий булевой матрицы Ь и пусть - конечная последовательность наборов столбцов матрицы Ь, содержащая множество В(Ь, 0). Предполагается, что некоторые элементы в (2(1) могут повторяться. Пусть алгоритм А строит с полиномиальной задержкой последовательность (¿(Ь), А1А(Ь) - число шагов алгоритма А (число элементов в ()(Ь)). При построении очередного элемента из (¿(Ь) алгоритм А проверяет его на принадлежность В (1,0). Очевидно, что такая проверка может быть осуществлена за полиномиальное от размеров матрицы время. Если построенный элемент принадлежит В(Ь, 0), то дополнительно проверяется, что этот элемент не был ранее построен алгоритмом А. Требуется, чтобы данная проверка осуществлялась за полиномиальное от размера матрицы время.

Алгоритм А является асимптотически оптимальным, если ЫА(Ь) « | В{1,0) | при п -» оо для почти всех булевых матриц Ь размера тх п.

К настоящему моменту построен ряд асимптотически оптимальных алгоритмов (в основном для случая, когда матрица вытянута по горизонтали [3, 10-13], то есть число строк матрицы меньше числа ее столбцов). Эти алгоритмы основаны на перечислении с полиномиальной задержкой

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

При анализе целочисленных данных в задачах распознавания наравне с методами преобразования нормальных форм монотонной булевой функции применяются методы синтеза нормальных форм логических функций, являющихся характеристическими функциями классов. В [14, 15, 17-20, 24, 25, 53, 59, 60] построены асимптотически оптимальные алгоритмы для задач перечисления максимальных конъюнкций двузначных логических функций, которые сформулированы как задачи построения тупиковых покрытий целочисленной матрицы. Эти алгоритмы успешно протестированы на большом числе практических и модельных задач.

Теоретическое обоснование асимптотически оптимальных методов поиска тупиковых покрытий булевых и целочисленных матриц базируется на изучении метрических (количественных) свойств множества покрытий. К настоящему времени наиболее полно исследован случай, когда число столбцов п в матрице по порядку роста больше при п -> оо числа строк т. Для этого случая в [2, 10 - 15, 17-20, 60] получены асимптотики типичного числа тупиковых покрытий и типичной длины тупикового покрытия как булевой, так и целочисленной матрицы. В частности показано, что число неприводимых покрытий булевой матрицы почти всегда асимптотически равно числу единичных подматриц этой матрицы. Технически более сложным оказалось получение аналогичных оценок в случае, когда число столбцов в матрице не превосходит числа её строк. Для этого случая в [8, 19] была получена лишь асимптотика логарифма типичного числа тупиковых по