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

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

Постановка задачи распознавания по прецедентам заключается в следующем. Исследуется некоторое множество объектов М, про которое известно, что оно может быть разбито на непересекающиеся подмножества (классы) Кг,., К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] была получена лишь асимптотика логарифма типичного числа тупиковых покрытий. Таким образом, оставался открытым вопрос, касающийся получения точных асимптотических оценок важных количественных характеристик множества покрытий булевых и целочисленных матрицы в случае квадратных и вытянутых по вертикали матриц.

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

В [22] построен распознающий алгоритм, основанный на поиске всех тупиковых (безызбыточных) корректных наборов эл.кл. класса К, состоящих из эл.кл. вида (Я, ет), где Я состоит из одного признака, а означение этого признака, встречающееся в описании обучающих объектов из К. Поиск таких наборов соответствует перечислению всех тупиковых покрытий булевой матрицы Ьк, имеющей не менее 2п столбцов и т1т2 строк, где тг — число обучающих объектов из класса К, т2 — число остальных обучающих объектов.

В [22] предложена процедура сокращения перебора, возникающего при поиске тупиковых покрытий матрицы Ьк. Однако, исследование предложенной модели на прикладных задачах не проводилось, по-видимому, из-за больших временных затрат. Не ставилась также задача отбора наилучших в смысле качества распознавания корректного набора эл.кл.

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

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

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

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

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

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

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

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

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

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

В диссертационной работе получены следующие результаты.

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

В этом случае функция приспособленности — оценка распознающей способности корректного набора эл.кл.

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

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

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

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

Диссертационная работа состоит из введения, четырех глав и заключения.

Заключение

.

В работе получены следующие результаты.

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

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

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

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

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

6. Показано, что при п < т, для почти всех матриц Ь из при п оо число всех тупиковых покрытий и число всех совместимых наборов столбцов матрицы Ь асимптотически равно соответственно числу тупиковых покрытий и числу совместимых наборов столбцов, длина которых принадлежит интервалу [^(/с),?^^)]. Аналогичный результат получен для задач преобразования нормальных форм двузначной логической функции.

7. Показано, что при п < т, для почти всех матриц Ь из при п оо число совместимых наборов столбцов с длиной не больше, чем гх (/с) асимптотически совпадает с числом наборов столбцов матрицы с длиной гг (к). Аналогичный результат получен для задач преобразования нормальных форм двузначной логической функции.

8. Показано, что при п < т, для почти всех матриц Ь из при п оо число тупиковых покрытий с длиной не меньше, чем г2(к), асимптотически совпадает при п -> оо с числом совместимых наборов столбцов с длиной не меньше, чем г2(к), и с числом о — подматриц с рангом г2(к). Аналогичный результат получен для задач преобразования нормальных форм двузначной логической функции.