Введение к работе
Актуальность темы. Одним из важных направлений в создании алгоритмических моделей решения тех или иных задач является доказательство оценок числа шагов таких алгоритмов. Это особенно актуально для задач искусственного интеллекта, так как размерность решаемых задач, как правило, очень велика.
Выбор языка, адекватно описывающего поставленную задачу — существенный этап решения задач искусственного интеллекта. В диссертации в качестве такого языка предлагается использование языка логики первого порядка, причем в зависимости от специфики конкретной задачи рассматривается либо язык исчисления высказываний, либо язык исчисления предикатов.
В диссертации рассматривается логико-аксиоматический подход к решению задач распознавания образов, основанный на сведении некоторых задач распознавания к задачам поиска вывода в логических исчислениях. Термин „логико-аксиоматический метод решения задач распознавания образов" был предложен совместно автором диссертации и Тимофеевым А.В. в [1] в связи с тем, что описание класса представляет собой утверждения об объектах, безусловно истинные для каждого объекта из этого класса и, следовательно, могут рассматриваться как аксиомы этого класса. При этом рассматриваются задачи, в которых объекты могут быть описаны с помощью логических формул. При использовании пропозициональных формул такой подход является достаточно представительным частным случаем логико-алгебраического подхода, подробно обоснованного и развитого в работах Ю.И.Журавлева и его учеников.
Во многих прикладных задачах в качестве исходных признаков удобно рассматривать не пропозициональные (булевы) переменные, а свойства и отношения между частями распознаваемого объекта, то есть предикаты. В этом случае описания классов будут задаваться формулами исчисления предикатов. Поскольку в каждой конкретной задаче область, являющаяся образом распознаваемых объектов, конечна, то описания классов и объектов формулами исчисления предикатов можно промоделировать пропозициональными формулами. Однако длина записи таких формул экспоненциально зависит от размера моделируемой области. В диссертации показано, что в оценках числа шагов алгоритмов решения задач распознавания образов такого рода экспоненты избежать нельзя, если Р ф NP. Но длина записи исходных данных при использо-
вании формул языка исчисления предикатов существенно сокращается по сравнению с использованием пропозициональных формул. В связи с этим логико-аксиоматический подход, использующий формулы исчисления предикатов, представляется оправданным и ниже будет называться логико-предметным.
Логико-предметный подход к решению задач распознавания образов представляется удобным также в случаях, когда параметры распознаваемого объекта имеют интервальный характер или описания объекта содержат взаимоисключающие признаки, например, цвет объекта.
В [1] ряд задач распознавания образов сведен к задаче проверки выводимости формул специального вида из заданного множества атомарных формул. В общей постановке задачи проверки истинности (или выполнимости) формул вызывают значительные трудности. Так, например, для исчисления высказываний задача проверки выполнимости формулы в КНФ является NP-полной. Задача проверки выполнимости формулы исчисления предикатов алгоритмически неразрешима. В то же время для формул различного вида можно получить разрешимые фрагменты исчисления предикатов. В [8] сформулированы серии задач, для которых доказаны их NP-полнота, в то время как для каждой задачи этой серии имеется полиномиальный разрешающий алгоритм.
В диссертации для решения задач распознавания образов используется разрешимый фрагмент исчисления предикатов. Для алгоритмов, решающих поставленные задачи, доказаны оценки числа шагов их решения [2].
Для уменьшения числа шагов работы алгоритмов автором диссертации предложены многоуровневые описания классов. Доказаны условия уменьшения числа шагов работы алгоритмов, решающих рассматриваемые задачи распознавания образов [4, 5].
Многоуровневые описания классов также применимы к созданию искусственных нейронных сетей [3] и к естественному их использованию на многоядерных компьютерах.
Существенной характеристикой распознающей системы является ее способность адаптироваться к тем или иным изменениям объекта. В диссертации рассматриваются следующие задачи, которые можно отнести к задачам, учитывающим такого рода изменения: задача распознавания объекта в условиях неполной информации, задача распознавания частично заслоненных объектов, задача распознавания объектов, подвергнутых преобразованиям, не выводящим из заданного класса (ин-
вариантное распознавание). Для решения этих задач в рамках логико-аксиоматического подхода предложены решающие их алгоритмы, для которых доказаны оценки числа их шагов .
Цель работы. Диссертация посвящена разработке алгоритмов решения задач распознавания образов, допускающих формализацию в рамках логики первого порядка, а также доказательству оценок их временной сложности. Существенным моментом доказательства выводимости формул исчисления предикатов является алгоритмическая неразрешимость задачи в общей постановке. При решении задач распознавания образов использовался разрешимый фрагмент исчисления предикатов. Для достижения поставленной цели необходимо решить следующие задачи.
-
Построение математической модели логико-аксиоматического подхода к решению задач распознавания образов, включающей в себя как распознавание изолированных объектов, так и объектов, содержащихся в объектах более сложной структуры. Формализация понятий распознавания образов в условиях неполной информации об объекте. Формализация понятия распознавания при условии инвариантности распознаваемого объекта к заданному множеству преобразований.
-
Доказательство оценок числа шагов стандартных алгоритмов, проверяющих истинность формул, полученных при построении математической модели логико-аксиоматического подхода к решению задач распознавания образов.
-
Для сокращения времени решения сформулированных в диссертации задач потребовалась разработка метода, позволяющего существенно снизить показатель степени экспоненты, ограничивающей число шагов решения задач распознавания. Доказательство для предложенного метод его корректности и условий, при которых происходит уменьшение времени решения поставленных задач.
-
Разработка и оценки числа шагов алгоритмов для решения задач распознавания образов с неполной информацией об объекте, в частности, для решения задачи распознавания частично заслоненного объекта.
-
Разработка и оценки числа шагов алгоритмов для распознавания объектов в системе, способной одинаково распознавать объекты, отличающиеся только преобразованиями из заданной группы с конечным числом образующих.
Методы исследования. В работе использованы положения теории распознавания образов, математической логики, теории алгоритмов и теории сложности алгоритмов
Научная новизна. В диссертации формализована и исследована логико-аксиоматическая модель решения задач распознавания образов, являющаяся естественным расширением логико-алгебраического подхода к решению таких задач. В частности, получены следующие результаты, выносимые на защиту.
-
Построена математическая модель логико-аксиоматического подхода к решению задач распознавания образов.
-
Доказаны оценки числа шагов исследованных алгоритмов решения задач распознавания при логико-аксиоматическом подходе. Доказана NP-трудность рассмотренных задач распознавания в случае, если исходные признаки являются предикатами, определяющими свойства частей объекта и отношения между ними.
-
Введено понятие многоуровневого описания классов для эффекти-визации алгоритмов, решающих сформулированные задачи распознавания образов. Доказаны оценки числа шагов решения рассматриваемых задач при использовании двухуровневого описания классов.
-
Обоснована возможность построения нейронных сетей и распараллеливания вычислений на основе многоуровневого описания классов.
-
Введено понятие неполного вывода как средства адаптации распознающей системы к неполной информации и доказаны оценки числа шагов его реализации.
-
Разработаны алгоритмы и доказаны оценки числа их шагов при распознавании объектов, искаженных преобразованиями из заданной группы преобразований с конечным числом образующих.
По существу, полностью завершено исследование проблемы разработки алгоритмов и оценки числа их шагов в области решения задач распознавания образов, формализуемых в рамках простого фрагмента языка исчисления предикатов.
Теоретическая и практическая значимость. Работа носит теоретический характер. Полученные результаты могут быть использованы при построении интеллектуальных систем распознавания, в частности,
для моделирования окружающей среды в памяти интеллектуального робота.
Апробация работы. Результаты работы докладывались на ряде научных семинаров и конференций различного уровня, среди которых можно отметить следующие:
IX Международный семинар "Дискретная математика и ее приложения- Москва, МГУ, 2007.
XIII Международная конференция „Knowledge-Dialog-Solution" (KDS-2007) - Варна, Болгария, 2007.
Международная научно-техническая выставка-конгресс. „Мехатро-ника и робототехника" — Санкт-Петербург, Ленэкспо, 2007.
Международная научная конференция „Космос, астрономия, программирование" [Лавровские чтения] — 20-22 мая 2008г.
XV Международная конференция „Проблемы теоретической кибернетики" — Казань 2-7 июня 2008 г.
Семинар теоретического и экспериментального программирования Института систем информатики имени А.П. Ершова СО РАН, совместный с НГУ — 1 ноября 2008г.
XVII Международная школа-семинар „Синтез и сложность управляющих систем" имени академика О. Б. Лупанова — Новосибирск, 27 октября - 1 ноября 2008 г.
Восьмая между народная научная конференция „Дискретные модели в теории управляющих систем" — Москва, 6-9 апреля 2009 г.
Публикации результатов. Основные результаты диссертации опубликованы в работах [1 - 29], список которых приведен в конце автореферата. Из них 8 публикаций [1-8] — в журналах, входящих в перечень ВАК. В совместной статье [1] соискателю принадлежат математические результаты, включая точную математическую постановку рассматриваемых задач, формулировку и доказательство теоремы; Тимофееву А.В. — идея подхода и общее руководство. В статье [3] соискателю принадлежит точная математическая постановка рассмотренной задачи; Тимофееву А.В. — выявление актуальности исследования. В совместной статье [8] соискателю принадлежит детальная проработка доказательств
и выявление полиномиальности подзадач серии 4; Косовскому Н.К. — выявление сформулированных серий задач.
Объем и структура диссертации. Диссертация содержит введение, 5 глав, заключение и список литературы. Общий объем диссертации составляет 200 страниц.
Похожие диссертации на Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходе
