Предикатное описание дополнительных ограничений в задачах распознавания образов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Таханов, Рустем Серикович

• Таханов, Рустем Серикович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Таханов, Рустем Серикович

0 Введение

1 Предикатные пары как язык описания множеств отображений и максимальные предикатные пары

1.1 Основное понятие.

1.2 Максимальность пар предикатов относительно множеств отображений

1.3 Максимальность пар предикатов

1.4 Максимальные предикатные пары в примерах.

1.4.1 Необходимые и достаточные условия максимальности в случае, когда рв — частичный порядок.

1.4.2 Предикатное описание выполняющих наборов 2-КНФ

1.5 Аксиоматика отношения «между».

2 О предикатных ограничениях с эффективно-разрешимой задачей согласования с обучающей выборкой

2.1 Введение

2.2 Алгебраическая структура эффективно разрешимых классов предикатов

2.3 Максимальные классы предикатов в булевом случае.

2.4 Эффективная разрешимость порядкового класса предикатов в общем случае.

2.5 Открытые вопросы

3 Задача монотонизации выборки

3.1 Постановка задачи монотонизации выборки.

3.2 Задача монотонизации выборки и максимальные независимые подмножества

3.3 NP-полнота MaxCMS.

3.4 1-MaxCMS

3.5 2-MaxCMS

3.6 Приближенный алгоритм для 2-MaxCMS.

3.6.1 Обсуждение

4 Предикатное задание универсальных ограничений алгебраического подхода

4.1 Основные понятия и формализм.

4.1.1 Ограничения монотонности.

4.1.2 Симметрические ограничения.

4.1.3 Функциональные ограничения.

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

Интенсивное развитие технологий хранения информации, произошедшее за последние 30 лет, послужило стимулом для нового витка исследований по классической тематике—проблемам связанным с автоматизацией ее интеллектуального анализа. Одним из важных инструментов для решения этой задачи являются методы распознавания образов, развиваемые с начала 50-х годов прошлого века[2, 12, 28, 24, 5, 13].

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

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

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

Одной из причин рассмотрения аппарата предикатных пар для описания дополнительных ограничений стало развитие алгебраического подхода к задачам распознавания[6, 18, 21, 7, 8, 9].

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

Поиск языка подходящего для описания дополнительных ограничений алгебраического подхода привел к созданию теории локальных и универсальных ограничепий[18, 21, 14, 15, 16, 17, 19]. Так как в алгебраическом подходе требуется удовлетворить дополнительным ограничениям при построении достаточно сложных суперпозиций, неудивительно, что математической моделью этих ограничений стали допустимые категории[3]. Условие замкнутости операции суперпозиции морфизмов категории в контексте алгебраического подхода приобретает новое понимание, так как именно это условие наиболее созвучно идее сохранения некоторого структурного свойства отображениями при их суперпозиции.

Однако предикатное описание удовлетворяет подобным же свойствам. Определяя на множествах А, В, С произвольные m-местные предикаты Ра,Рв,Рс) легко видеть, что если а £ II (рл,Рв) ,b £ Н (рв,рс), то bo а — с Е Н(рА,рс), где II (рх,ру) — множество функций / : х —> у сохраняющих предикатную пару (рх, Ру). Именно вышеупомянутое свойство предикатного описания множеств отображений, то есть способность описывать структурные ограничения на множества отображений, которые сохраняются при их суперпозиции, и было основным побудительным мотивом обращения к нему в данной работе.

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

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

Работа состоит из четырех глав.

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

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

Вторая глава посвящена характеризации предикатных ограничений с эффективно-разрешимой задачей согласования с обучающей выборкой. Одним из подходов к ее получению является классификация пар по свойствам предиката на множестве значений, при произвольном предикате на множестве определения. Показана связь такой постановки с замкнутыми классами предикатов и функций многозначной логики. Дана полная классификация эффективно согласуемых с обучающей выборкой предикатных ограничений в булевом случае. В общем случае, введен важный с практической точки зрения порядковый класс предикатов и показана его эффективная разрешимость. Заметим, что в исследованиях по задаче «Обобщенная выполнимость»[33, 40, 41] рассматривалась похожая проблема. В этих работах ставилась задача описания предикатных пар, для которых нахождение сохраняющей пару функции может быть проведено эффективно.

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

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

Благодарности

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Таханов, Рустем Серикович

Заключение

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

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

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

3) Исходя из требований максимальности слева, для отношения «между» предложена аксиоматика и рассмотрены примеры подобных отношений.

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Таханов, Рустем Серикович, 2007 год

1. Боднарчук В.Т., Калужнин JT.A., Котов В.Н., Ромов Б.А. Теория Галуа для алгебр Поста // Кибернетика, 1969, № 3, 1-10, № 5, 1-9.

2. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. 320 с.

3. Букур И., Деляну А. Введение в теорию категорий и функторов. М.: Мир, 1972. 260 с.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М. Мир. 1982.

5. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с.

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

7. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I // Кибернетика. 1977. № 4. С. 5-17.

8. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. II // Кибернетика. 1977. № 6. С. 21-27.

9. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. III // Кибернетика. 1978. № 2. С. 35-43.

10. Журавлев Ю.И., Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М.: Наука, 1987. С. 187-198.

11. Марчепков С.С. Замкнутые классы булевых функций // М. ФИЗМАТ-ЛИТ. 2004.

12. Минский М., Пейперт С. Персептроны. М.:Мир, 1971.262 с.13 14 [1516 1718 19 [2021