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

• Автор: Косовская, Татьяна Матвеевна
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 200 с. : ил.

Введение.

Глава I. Общая постановка рассматриваемых задач распознавания . .

1.1. Языки исчисления высказываний и исчисления предикатов как средство формализации описаний

1.2. Оценки сложности задач и алгоритмов, классы сложности

1.3. Описания объектов как совокупность формул

1.4. Описания классов как формулы формализованных языков

1.5. Построение описаний классов с глобальными характеристиками

объектов

I Построение описаний классов с локальными характерисгиками объектов

I.7. Постановка задач распознавания как задач нахождения вывода в

логических исчислениях

Глава II. Оценки числа шагов работы алгоритмов, решающих поставленные задачи
II. 1. Распознавание объектов при их глобальной характеризации пропозициональными переменными.
.2. Распознавание объектов при их локальной характеризации предикатными формулами.
.3. Замечания о связи между оценками числа шагов работы алгоритма, решающего задачу распознавания образов, описанную формулами исчисления предикатов, и соотношением между классами Р и
II.4. Пример распознавания объекта с локальными характеристиками
и оценки числа шагов
Глава III. Многоуровневое описание классов как средство эффективизации алгоритмов, решающих различные задачи распознавания образов .
III. 1. Многоуровневое описание классов
1.2. Условия уменьшения числа шагов решения задач распознавания образов, описываемых пропозициональными формулами
1.3. Примеры построения двухуровневых описаний классов при глобальной характеризации объекта.
1.4. Условия уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов.
III.5. Пример применения двухуровневого описания при локальной характеризации объекта.
1.6. Использование многоуровневого описания классов для построения нейронных сетей
1.7. Многоуровневое описание классов в задачах распознавания образов как средство для параллелизации вычислений.
Глава IV. Адаптация логи копредметной распознающей системы к неполной информации.
IV. 1. Построение неполного вывода как средство адаптации распознающей системы к неполной или недостоверной информации
IV.2. Оценки числа шагов построения неполного вывода.
IV.3. Распознавание в условиях неполной информации. Построение неполного вывода.
IV.4. Пример распознавания частично заслоненного объекта
Глава V. Адаптация логикопредметной распознающей системы к преобразованиям, не выводящим из заданного класса.
V Инвариантность к заданному множеству преобразований. Инвариантные признаки и инвариантные описания классов
V.2. Инвариантные описания классов е неинвариантными признаками
V.3. Задача инвариантного распознавания как задача поиска логического вывода.
V.4. Алгоритм инвариантного распознавания
V.5. Оценки числа шагов работы алгоритмов инвариантной идентификации .
V.6. Примеры инвариантных распознающих систем с неинвариантными
признаками.
Заключение.
Список литературы


Как уже было сказано, одним из важных направлений в создании алгоритмических моделей решения тех или иных задач является доказательство оценок числа шагов таких алгоритмов. В общей постановке задача проверки истинности или выполнимости формул вызывает значительные трудности. КНФ является ПРнолной 7. Для формул исчисления предикатов различного вида можно получить разрешимые фрагменты. В сформулированы серии задач, для которых доказаны их ПРполиота, в то время как для каждой задачи этой серии имеется полиномиальный разрешающий алгоритм. В диссертации для решения задач распознавания образов для каждого конкретного описания классов доказаны линейные от длины записи описания распознаваемого объекта по времени оценки числа шагов алгоритмов, решающих эти задачи для пропозиционального случая , . Рассмотрен разрешимый фрагмент исчисления предикатов, в котором могут быть формализованы задачи распознавания образов. Доказано, что если описания классов являются исходными данными алгоритмов, то задачи распознавания образов с признакамипредикатами являются ПРтрудными. При этом, так же как и в , для каждого конкретного описания классов эти задачи имеют полиномиальный со степенью полинома, зависящей от длины записи описания классов алгоритм решения. В предложены многоуровневые описания классов, при использовании которых в диссертации доказаны условия уменьшения числа шагов работы алгоритмов, решающих рассматриваемые задачи распознавания образов , , , . Многоуровневые описания классов являются также удобным средством анализа составных сложных объектов. Введение предикатов различных уровней оказалось полезным при создании искусственных нейронных сетей , . Диссертация состоит из введения и пяти глав. В первой главе вводятся основные понятия, необходимые для формулировки постановки задач распознавания образов как задач нахождения вывода в логических исчислениях, а также формулируются рассматриваемые в диссертации задачи идентификации, классификации и анализа сложного объекта. Показывается, к задачам выводимости каких именно формул исчислений высказываний и предикатов эти задачи сводятся. Основные результаты этой главы опубликиваны в . Рассматриваются задачи распознавания образов в следующей постановке . Пусть имеется множество П конечных множеств и1, . Частью т объекта и называется любое его подмножество не обязательно собственное. Пусть также па частях т задан набор предикатов р,. Задано разбиение множества О на К возможно пересекающихся классов О. Здесь и далее посредством х обозначается список элементов конечного множества х соответствующий некоторой перестановке номеров его элементов. Тот факт, что элементами списка являются элементы множества у, будем записывать в виде х С у. Эх1. Эжтя Ф х, Ах 1,. Ах. Аксо. Л3 элементарная конъюнкция. При этом если для некоторого верна Ай, то и 2. С помощью построенных описаний в предлагается решать следующие задачи распознавания образов. Задача идентификации. Проверить, припадлеоюит ли объект со или его часть классу 2. Задача классификации. Найти все такие номера, классов к, что
Задача анализа сложного объекта. Найти и классифицировать все части т объекта со, для которых г Г2. Решение задач идентификации, классификации и анализа сложного объекта сведено к доказательству соответственно секвенций
Ь Лкх, Ь V Акр, 5о Р V Эт Лкх. Рассматриваются способы построения описаний классов как при использовании языка исчисления высказываний что является достаточно хорошо разработанной областью теории распознавания образов, так и при использовании языка исчисления предикатов дастся пример построения описания классов по эталонным объектам класса. Во второй главе доказываются оценки числа шагов работы алгоритмов, решающих поставленные задачи в различных формулировках. Основные результаты этой главы опубликованы в . Для задач, имеющих описания в терминах пропозициональных формул булевых функций и использующих для своего решения различные варианты исчисления высказываний, доказываются полиномиальные оценки числа шагов их решения. В частности, доказаны следующие оценки. Следствие теоремы И.