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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

РАЗРАБОТКА И ОЦЕНКИ ЧИСЛА ШАГОВ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ РАСПОЗНАВАНИЯ ОБРАЗОВ ПРИ ЛОГИКО-АКСИОМАТИЧЕСКОМ ПОДХОДЕ

Специальность 05.13.17 — „Теоретические основы информатики"

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

КОСОВСКАЯ Татьяна Матвеевна

АВТОРЕФЕРАТ

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

Санкт-Петербург

004600827

2009

004600827

Работа выполнена в лаборатории информационных технологий в управлении и робототехнике Учреждения Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН.

Научный консультант: доктор технических наук, профессор

ТИМОФЕЕВ Адиль Васильевич (Санкт-Петербургский институт информатики и автоматизации РАН)

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

профессор ЧИРКОВ Михаил Константинович (Санкт-Петербургский государственный университет)

доктор физико-математических наук, профессор БЕЛЬТЮКОВ Анатолий Петрович (Удмурдский государственный университет)

доктор физико-математических наук, профессор ФЛЕГОНТОВ Александр Владимирович (Российский государственный педагогический университет им. А.И.Герцена)

Ведущая организация: Санкт-Петербургский государственный университет аэрокосмического приборостроения

Защита состоится « ^& $ 2010 г. в / часов на

заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, С.-Петербург, Старый Петергоф, Университетский пр., 28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, С.-Петербург, Университетская наб., 7/9.

Автореферат разослан « ^ » 2010 г.

Ученый секретарь диссертационного совета Даугавет И.К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В диссертации рассматривается логико-аксиоматический подход к решению задач распознавания образов, основанный на сведении некоторых задач распознавания к задачам поиска вывода в логических исчислениях. Термин „логико-аксиоматический метод решения задач распознавания образов" был предложен совместно автором диссертации и Тимофеевым A.B. в [1] в связи с тем, что описание класса представляет собой утверждения об объектах, безусловно истинные для каждого объекта из этого класса и, следовательно, могут рассматриваться как аксиомы этого класса. При этом рассматриваются задачи, в которых объекты могут быть описаны с помощью логических формул. При использовании пропозициональных формул такой подход является достаточно представительным частным случаем логико-алгебраического подхода, подробно обоснованного и развитого в работах Ю.И.Журавлева и его учеников.

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

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

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

В [1] ряд задач распознавания образов сведен к задаче проверки выводимости формул специального вида из заданного множества атомарных формул. В общей постановке задачи проверки истинности (или выполнимости) формул вызывают значительные трудности. Так, например, для исчисления высказываний задача проверки выполнимости формулы в КНФ является МР-полной. Задача проверки выполнимости формулы исчисления предикатов алгоритмически неразрешима. В то же время для формул различного вида можно получить разрешимые фрагменты исчисления предикатов. В [8] сформулированы серии задач, для которых доказаны их КР-полнота, в то время как для каждой задачи этой серии имеется полиномиальный разрешающий алгоритм.

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

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

Многоуровневые описания классов также применимы к созданию искусственных нейронных сетей [3] и к естественному их использованию на многоядерных компьютерах.

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

вариантное распознавание). Для решения этих задач в рамках логико-аксиоматического подхода предложены решающие их алгоритмы, для которых доказаны оценки числа их шагов .

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

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

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

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

4. Разработка и оценки числа шагов алгоритмов для решения задач распознавания образов с неполной информацией об объекте, в частности, для решения задачи распознавания частично заслоненного объекта.

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

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

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

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

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

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

4. Обоснована возможность построения нейронных сетей и распараллеливания вычислений на основе многоуровневого описания классов.

5. Введено понятие неполного вывода как средства адаптации распознающей системы к неполной информации и доказаны оценки числа шагов его реализации.

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

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

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

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

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

— 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] соискателю принадлежат математические результаты, включая точную математическую постановку рассматриваемых задач, формулировку и доказательство теоремы; Тимофееву A.B. — идея подхода и общее руководство. В статье [3] соискателю принадлежит точная математическая постановка рассмотренной задачи; Тимофееву A.B. — выявление актуальности исследования. В совместной статье [8] соискателю принадлежит детальная проработка доказательств

и выявление полиномиальноети подзадач серии 4; Косовскому Н.К. — выявление сформулированных серий задач.

Объем и структура диссертации. Диссертация содержит введение, 5 глав, заключение и список литературы. Общий объем диссертации составляет 200 страниц.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

Рассматриваются задачи распознавания образов в следующей постановке. Пусть имеется множество П конечных множеств и = ..., и^}, которые в дальнейшем будут называться распознаваемыми объектами. Частью г объекта и> называется любое его подмножество (не обязательно собственное). Пусть также на частяхт задан набор предикатоврх,..., рп, характеризующих свойства и отношения между элементами объекта а;.

Задано разбиение множества О. на К (возможно пересекающихся) классов П = Ц*=1 ^к■

Логическим описанием 5(о») объекта ш называется набор всех истинных постоянных формул вида рДт) или ->р;(т), выписанных для всех возможных частей т объекта и!.

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

чения для переменных списка х, удовлетворяющие формуле А(х), различны, вместо формулы Зх!..Зхт ^ х^) & Л{х\,..., хт)) будет использоваться обозначение 3х^А(х).

Логическим описанием класса (ОК) называется такая формула Ак(х) со свободными переменными х, что

1. Ак(х) содержит в качестве атомарных только формулы видарг{у), где у С х;

2. Ак(х) не содержит кванторов;

3. Ак(х) имеет вид дизъюнкции элементарных конъюнкций;

4. если для некоторого списка (упорядоченного множества) и всех элементов множества и истинна формула Ак(ш), то и; 6

То есть логическое описание класса имеет вид

Ак(х) = Ч&Ай*),

где АКх-1) - элементарная конъюнкция. При этом если для некоторого ^ верна А{(и), то и £ Г1к-

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

Задача идентификации. Проверить, принадлежит ли объект и> или его часть классу Пк.

Задача классификации. Найти все такие номера классов к, что и) £ Пь

Задача анализа сложного объекта. Найти и классифицировать все части т объекта и>, для которых т 6 П.

Решение задач идентификации, классификации и анализа сложного объекта сведено к доказательству соответственно секвенций

5Н Ь (1.7.1)

в{и>) |= V Ак(р). (1.7.2)

к=\

5И н V ^Му)- (1-7-3)

к=1

Рассматриваются способы построения описаний классов как при использовании языка исчисления высказываний (что является достаточно

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

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

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

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

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

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

Сформулированы и доказана №-полнота двух задач

ВЫПОЛНИМОСТЬ В КОНЕЧНОЙ ИНТЕРПРЕТАЦИИ

ДАНО. Пусть заданы конечное множество объектов и> = {а^, ..., Ш;} и набор истинных постоянных атомарных формул вида (г), где г = 1 ,...,п, т С и, а¿^ - логические константы. Пусть также дана бескванторная формула А(у), представленная в виде дизъюнкции простых конъюнкций атомарных формул (у = (уу, ..., уа) - список предметных переменных, входящих в формулу).

ВОПРОС. Существует ли набор значений для у из и)а, для которого

формула А(у) истинна?

То есть верно ли, что

Зх{х С и к А(х)).

ВЫПОЛНИМОСТЬ НА ЗАДАННОМ МНОЖЕСТВЕ

ДАНО. Пусть заданы конечное множество объектов и = {ыь ..., ы(} и набор истинных постоянных атомарных формул видар"'Т (г), где i = 1,..., га, г С и/, Q¿tf - логические константы. Пусть такэ/се дана бескванторная формула А(у), представленная в виде дизъюнкции элементарных конъюнкций атомарных формул (у — (у\, .... ijt) список предметных переменных, входящих в формулу).

ВОПРОС. Существует ли набор различных значений для у из ш1, для которого формула А(у) истинна?

То есть верно ли, что

ЗУ;,, ■ • •, • •, Уц} = и & A{yh,..., yit)).

Следствиями NP-полноты этих задач будут следующие три утверждения.

Следствие теоремы И.8. Если описание класса Ak(x) является исходным данным алгоритма распознавания, то задача идентификации NP-mpydna.

Следствие теоремы II.9. Если описание класса Ak(x) является исходным данным алгоритма распознавания, то задача классификации NP-mpydna.

Теорема 11.10. Если описание класса Ак(х) является исходным данным алгоритма распознавания, то задача анализа сложного объекта NP-трудна.

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

Теорема 11.11. Если Р ф NP, то не существует такого числа N, что число шагов всякого алгоритма, решающего конкретную задачу распознавания образов с заранее известными описаниями классов, ограничено сверху полиномом степени N от длины записи распознаваемого объекта.

Доказано, что для каждого конкретного описания классов, так же как и в сериях задач из [8], возможен полиномиальный алгоритм решения поставленных задач, однако полином имеет достаточно высокую степень,

зависящую от длины записи описаний классов. При использовании переборного алгоритма для доказательства секвенций (1.7.1), (1-7.2) или (1.7.3) степень такого полинома зависит от количества предметных переменных, входящих в формулы, задающие описания классов. При построении вывода секвенций (1.7.1), (1-7.2) или (1.7.3) степень такого полинома зависит от максимального количества атомарных формул, входящих в элементарные конъюнкции, являющиеся дизъюнктивными членами описаний классов. Более точно, доказаны следующие теоремы и следствия из них.

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

А{х) - элементарная конъюнкция с предикатами р\, ...,рп и предметными переменными х,

|Л| - количество различных вхождений предметных переменных в формулу А{х),

02г—1 - количество вхождений предикатар; в формулу А(х) без отрицания,

а-2, - количество вхождений предиката^ в формулу А(х) с отрицанием,

а = Ег^л «г ~ общее количество атомарных формул в Л{х), т - количество аргументов в А(х), 7], - количество аргументов предиката р; (1 < г < п), г] = тах,(??г),

1,51 - количество различных вхождений предметных констант в ¿"(ш), б'2г-1 - количество вхождений предиката рг в 3(и>) без отрицания, 32г - количество вхождений предиката^ в Я (си) с отрицанием, я = тах

1<г<2п

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

АГ ' + Х> • О

¿=1

шагов, где под шагом понимается подстановка значения переменной в

формулу или сравнение конъюнкта формулы с формулами совокупности S(u>) на их графическое совпадение.

Следствие 6 теоремы II.5. Если m - максимальное количество переменных в элементарных конъюнкциях, входящих в описания классов, то при использовании алгоритма полного перебора число шагов решения любой из сформулированных выше задач распознавания образов составляет

0(Г ■ \А\ ■ |5|).

Теорема II.6. Количество шагов проверки того, что секвенция S(и>) h Бх/_ А(х) выводима в секвенциальном исчислении предикатов, а также нахождения значений для переменных х, существование которых утверждается в правой части секвенции, не превосходит

|Л| + s? ■... ■ s%? • (è(a2i_i + a2i)m + а2 ■ /у2)+ »=1

п

• а2г-1 + S2i ■ a2l) ■ 7)i,

1-Х

где \А\ - длина записи формулы А{х).

Теорема II.7. Количество шагов проверки методом резолюций для исчисления предикатов того, что из S(io) следует Зхф А{х), а также нахождения значений для переменных х, существование которых утверждается в формуле, не превосходит

\А\ + si1 ■... - sa2% • (¿(оя_1 4- + а2 ■ r¡2)+ i=i

п

J2(s2i~ 1 • a2i-l + S2i ' Ü2i) ■ ГЦ, i=l

где \A\ - длина записи формулы A(x).

Следствие 7 теорем II.6 и II.7. Если а - максимальное количество вхождений атомарных формул в элементарные конъюнкции, составляющие описания классов, s - максимальное количество вхождений одного и того otee предиката (только без отрицаний или только с отрицаниями) в описание объекта, D - количество дизъюнктов в описаниях классов, используемых при решении задачи, то при использовании секвенциального исчисления предикатов или метода резолюций для исчисления предикатов число шагов решения любой из сформулированных выше задач распознавания образов составляет

0(П ■ s5).

Результаты проиллюстрированы оценками числа шагов распознавания контурного изображения.

Глава 3. „Многоуровневое описание классов как средство эффекти-визации алгоритмов, решающих различные задачи распознавания образов". В этой главе описаны предложенные автором многоуровневые описания классов и доказаны оценки числа шагов решения задач распознавания образов при использовании таких многоуровневых описаний классов. Основные результаты третьей главы опубликованы в [4, 5, 3|.

Рассматриваются объекты, структура которых позволяет выделить более простые их части и дать описание объекта в терминах свойств этих частей и отношений между ними. В частности, это можно сделать, выделяя "часто"встречающиеся подформулы РЦу) формул Ак(х) "небольшой сложности". При этом записывается система эквивалентностей вида ^ РНу)> гД° РI1 новые предикаты, которые будем называть предикатами 1-го уровня.

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

Обозначим предикаты, задаваемые этими подформулами, посредством р] (г = 1, ..., П1) и назовем их предикатами первого уровня. Эти предикаты определяются равносильностями

Р1\х1) ~ Р^у})

при г = 1,...

Обозначим формулы, полученные из Ак(х) путем замены всех вхождений формул вида Р}(у\) на атомарные формулы р}(х}) (при у} С х) посредством Л^х1). Здесь х1 - список всех переменных формулы А^х1), состоящий как из некоторых (быть может всех) исходных переменных формулы Ак(х), так и из переменных первого уровня, появившихся в формуле А}.(тх). При этом если для некоторых ц, г'г, ¿з выполнены соотношения у^и у12 = у-з и у1Г\у}2 = 0, то будем писать (х},,^) вместо (¡г*) и говорить, что Р^ задает бинарное отношение между объектами 1-го уровня. Аналогично можно определить многоместное отношение между объектами 1-го уровня. Такие формулы можно рассматривать как

описания классов в терминах предикатов исходного (нулевого) и первого уровней.

Описанием первого уровня Б1^) объекта и назовем множество всех атомарных формул вида для которых истинны подформулы

и тУ с ш. Объекты первого уровня представляют из себя списки исходных объектов т^.

Процедуру выделения часто встречающихся подформул небольшой сложности можно повторить с формулами А\{хх). В результате получим Ь-уровневое описание классов вида

<* рИу\)

, (Ш.1)

^ РМ)

^ р^Ш

равносильное исходному описанию классов.

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

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

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

р\(х\)

• Рп,«)

а - суммарное количество вхождений пропозициональных переменных в формулы в ДНФ ..., Ак (а = а\ + ... + ак),

а1 - суммарное количество вхождений пропозициональных переменных в формулы в ДНФ А\,..., А1К. доказаны теоремы.

Теорема III. 1. Если формулы Р/,..., Р* не пересекаются, то для того, чтобы при двухуровневом описании классов в терминах признаков исходного и первого уровней при некотором д, выполнялось равенство а1 = с1 ■ а необходимо и достаточно, чтобы

.7=1

Теорема III.2. Если Р/,... , Р^ - правильно выделенные подформулы формул А\,..., Ак, то для того, чтобы при двухуровневом описании классов в терминах признаков исходного и первого уровней при некотором <1 выполнялось равенство а1 — в, - а необходимо, чтобы

щ

£("]-1)-^>(1 -О)-а (Ш.5).

7 = 1

Теорема III.3. Пусть число (1 определяется равенством а} = д ■ а. Тогда для того, чтобы при двухуровневом описании классов верхняя оценка числа применений правил вывода секвенциального исчисления высказываний или правила резолюций для решения задачи классификации была меньше, чем при исходном описании, достаточно, чтобы

Е V) < (1 -в,)-а. (Ш.6)

.7=1

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

Для общего (предикатного) случая при обозначениях ти...,тк - количество предметных переменных в Л^З^), ..., Ак(хк) соответственно,

Л1 (у!). • • •. ' подформулы формул л^жх), ..., Ак(хк),

р}П1 - количество различных предметных переменных в Р/(?/}). ..., Рщ{у\ ) соответственно,

¿1 - максимальное количество различных переменных, входящих в элементарные конъюнкции формулы А^хь), но не вошедших в подформулы Pi{y\), - • •, Pn,(Vn,)i

t\ - суммарное количество объектов, для которых истинна хоть одна из подформул Pi{y\), ■. -, Рщ{Ущ) и тех исходных элементов объекта и, которые не вошли в указанные объекты,

Pj - предикаты первого уровня, определяемые эквивалентностями р){х)) ~ Р}{у%

А\{х\) получены из формул Ак(хк) (при к = 1,...,К) заменой всех вхождений подформул Р]{у)) на атомарные формулы pj(zj) (при j = 1,...,ni) соответственно,

nl - максимальное количество различных переменных 1-го уровня, входящих в элементарные конъюнкции формулы ^{.(sj.) доказаны теоремы.

Теорема III.4. Пусть задай конечный набор предикатов pi,..., рп, а также набор формул ..., Aj{(xk), записанных в виде дизъ-

юнкции элементарных конъюнкций атомарных формул с предикатами

Тогда проверка истинности формул ^(zi), ..., Ак{хк) на множестве ui — {wi,... равносильна проверке истинности формул Ai(x\), ..., Ак(хк) и эквивалентиостей p](zj) «-» Pj{yj) на этом же множестве.

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

151 • (£ tmk • |Afc| - £ t»> • \Pj\) > 1^1 • £ h'M • (HI.7)

k=1 j=l fc=l

Следствие 1 теоремы III.4. Если в условии теоремы дополнительно наложены условия fij < г, т = max{mi,..., тк} и t\ < t, то для того, чтобы оценка числа шагов работы алгоритма, решающего задачу анализа сложного объекта, уменьшилась начиная с некоторого t, достаточно чтобы

m-f + tSi+ni < tm. (III.8)

Следствие 2 теоремы III.4. Если выполнены условия следствия 1 и max{r, Si+ni} < т, то найдется такое Ц, что для ecext > tо оценка числа шагов работы алгоритма, решающего задачу анализа слоэююго объекта, уменьшится.

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

йк - максимальное количество атомарных формул в элементарных конъюнкциях, входящих в Ак,

al - максимальное количество атомарных формул в элементарных конъюнкциях, входящих в Aj.,

pj - количество атомарных формул в подформуле Рр s1 - количество атомарных формул в описании первого уровня, то есть в множестве, состоящем как из формул исходного описания S(u>) (вида Pi{r) или ->Pi(r)), так и из формул с предикатами 1-го уровня вида р}{т1) или -л^(т1), для которых определяющие их подформулы следуют из исходного описания.

Теорема III.5. Пусть задан конечный набор предикатов pi,..., рп, а также набор формул yli(^i), ... ,Ак(хк), записанных в виде дизъюнкции элементарных конъюнкций атомарных формул с предикатами

Тогда проверка истинности формул А\(х\), ... ,Ак(хк) на множестве и = {u>i,...,u>t} равносильна проверке истинности формул yli(zj), ...,Ак{х1к) и эквивалентностей Pj(xj) <-> Р}{у}) на этом же множестве.

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

к т .к 1

£ sak - £ S»' > £ s1 \ (III.9)

k= 1 j=1 k=1

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

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

схематично изображена на рис. III.2.

Рис. III.2. Двухслойная нейронная сеть.

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

Рис. III.3. Применение параллельных процессоров при использовании Ь-уровневого описания классов.

Параллельно находятся все константы, выполняющие предикаты 1-го уровня, затем параллельно находятся все константы, выполняющие предикаты 2-го уровня,... , параллельно находятся все константы, выполняющие предикаты Ь-го уровня, вычисляется значение формулы А^{хь).

Глава 4. „Адаптация логико-предметной распознающей системы к неполной информации ". В этой главе рассматривается способность распознающей системы адаптироваться к неполной информации о распознаваемом объекте. С этой целью для решения задач распознавания объекта в условиях неполной информации и распознавания частично заслоненного объекта вводится понятие неполного вывода и доказываются оценки числа шагов решения этих задач. Результаты этой главы опубликованы в [6].

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

Фрагментом формулы А(х) будем называть любую ее подформулу А(у), где список переменных у является подсписком списка переменных х.

Пусть тп - количество предметных переменных в А(х), тп - количество предметных переменных в Л(у), а - количество атомарных формул в А(х), а- количество атомарных формул в А(у). Числа д и г вычисляются по формулам д = г = ^ и характеризуют степень совпадения формул А{х) и А(у).

При таких обозначениях формулу А(у) называется (д., ^-фрагментом формулы А(х).

Если секвенция Б(и>) Н ЗЗ;^ А(х) не выводима, но для некоторого ее (д, г)-фрагмента А(у) (при q ф 1 или г ф 1) выводима секвенция I- 3уф Л(у), то будем говорить, что 3(и>) 1- Зх^ А(х) является частично (д, г)-выводимой.

Формула £)А(х) называется негативным дополнением формулы А(х) до ее фрагмента А (у), если она является элементарной дизъюнкцией, состоящей из отрицаний конъюнктивных членов формулы А(х), не вошедших во фрагмент А(у). То есть А(х) А(у) & -~<1-)А{х).

Секвенция 5(со) Ь Зх^ А(х) называется (д, г)-выводимой, если она частично (д, г)-выводима и ни для каких наборов различных констант т, для которых из истинности 5(ш) следует истинность А(т), не выводима секвенция Б (и:) К Зх^ \ОА(х))~, где у - подсписок списка х, являющийся списком аргументов формулы А{у).

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

По сути дела, понятие (q, г)-выводимости для рассматриваемой секвенции S(oj) Ь 3xjt А(х) означает, что имеется набор различных констант (cjjj, ...,uí~), количество которых составляет долю q от общего количества переменных формулы А(х), для которого истинна подформула ...,u>i~), длина которой составляет долю г от общей длины формулы, а также нет информации о том, что формула А(х) не выполнима на ш.

Разработаны алгоритмы проверки неполной выводимости, основанные как на алгоритме полного перебора, так и на построении вывода в исчислении предикатов. Доказаны оценки числа шагов этих алгоритмов.

Теорема IV.1. Число шагов работы переборного алгоритма проверки неполной выводимости секвенции S(uj) ь Зх^ А{х) составляет

0(Г-2а~

где t - число объектов предметной области, т - число предметных переменных в формуле А(х), а - количество атомарных формул в А(х).

Теорема IV.2. Число шагов работы алгоритма проверки неполной выводимости секвенции S(u¡) Ь А(х) в секвенциальном исчислении предикатов составляет

0(sa'1 ■ а2 ■ (s + г]2 ■ а)),

если s > 2, где s - наибольшее число вхождений каждого из предикатов Pi в множество S(qj) , а - количество атомарных формул в А(х), r¡ -максимальное количество аргументов предикатов р\,...,рп.

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

Пусть задано не полное описание объекта S(u>), содержащее все истинные на ш атомарные формулы или их отрицания, а лишь некоторое его подмножество S(u>) С S(ui). Так как описание класса представляет из себя дизъюнкцию элементарных конъюнкций, то Ак(х) = V¿=i Akíj(yktj), где для каждого j (1 < j < Jk) yk¿ является подстрокой списка переменных х.

При решении задач идентификации, классификации и анализа сложного объекта при наличии неполного описания объекта вместо проверки справедливости секвенций

5(ы) Ь 3x¿ Ak(x), SH f- V S(u) h V Ak(x)

fc=1 k=1

соответственно имеется возможность проверки лишь того, что

5(и>) Ь За* Ак(х), Ё{и>) Ь \/ Ак(й), ¿(и) Ь V За* Ак{х).

к= 1 к=1

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

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

Утверждение IV. 1. Если (§)а~1 много меньше, чем £т, то алгоритм, основанный на построении вывода в секвенциальном исчислении предикатов заканчивает работу по идентификации объекта с неполным описанием за меньшее число шагов, чем алгоритм решения той оке задачи, основанный па полном переборе.

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

Глава V. „Адаптация логико-предметной распознающей системы к преобразованиям, не выводящим из заданного класса". В этой главе адаптация распознающей системы к заданной совокупности преобразований рассматривается в смысле ее способности отождествлять два объекта, отличающихся друг от друга только преобразованиями, не выводящими из заданного класса объектов. Результаты этой главы опубликованы в [7].

Пусть на множестве П задана совокупность преобразований С, отображающих это множество на себя. Обозначим посредством С{ю) множество термов вида д(и>), где д £ С?, ш € Г2.

Определение. Логико-предметная распознающая система называется инвариантной относительно совокупности С?, если она одинаково идентифицирует любые два объекта, отличающиеся только преобразованиями из совокупности С.

Определение. Класс объектов Пь называется замкнутым относительно совокупности преобразований б, если любые два объекта, отли-

чающиеся только преобразованиями из совокупности одновременно принадлежат (или не принадлежат) этому классу

\/ыеП£ и' € Пк).

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

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

Пусть для каждого преобразования д^ = 1,...,Т}) можно указать, как изменяются значения отдельных предикатов или их совокупностей при воздействии преобразования д^ на распознаваемый объект. Для каждого д^ таких изменений может быть несколько (обозначим количество таких изменений посредством 1^). Эти изменения будем записывать в виде эквивалентностсй между описаниями объектов а; и д^{х)

В13{х) * С'(ф)), (УЛ)

где В^{х) и С^(д^(х)) - элементарные конъюнкции атомарных формул, I = 11,..., I]. Равносильности вида (У.1) будем называть описаниями преобразования д^ и обозначать Г'(х). Множество описаний для всех преобразований {Г'-(х^) : з = 1,...,Т,I = 1,...,^} будем обозначать посредством Г(х).

Теорема У.1. Пусть на £1 задана группа с конечным числом образующих С = {д:,---,дт}, для каждого преобразования д^ которой справедливы ^ описаний преобразования вида (У.1).

Если для каждого ] описание к-го класса Ак(х) вместе с каждым дизъюнктивным членом, в который входит В1-^х{) к. ... & В1-{хГ) содержит дизъюнктивный член с элементарной конъюнкцией С] (а^) & ... & С* (хТ), причем все остальные конъюнктивные члены этих дизъюнктов одинаковы и инвариантны относительно д то Ак(х) инвариантна относительно группы преобразований С*.

Описания преобразований позволяют расширить понятие логико-предметной распознающей системы введением в неё равносильностей вида (У.1). При этом задачи инвариантного распознавания могут быть сведены к следующим задачам.

Задача инвариантной идентификации: Проверить, принадлежит ли объект ш или его часть классу £1к, если класс 0,к замкнут относительно группы преобразований С* с конечным числом образующих С? = {дь-..,3г}-

Эта задача сводится к доказательству выводимости формулы ЗуфАк(у) из описания распознаваемого объекта 5(ш) и совокупности описаний преобразований Г(х)

ЗД Г (г) (= 3 УфАк(у). (У.2)

Задача инвариантной классификации. Найти все такие номера классов к, что ш 6 £1к, если класс £1к замкнут относительно группы преобразований С с конечным числом образующих С = {д1, ■■■, дт}-

Эта задача сводится к доказательству выводимости формулы \/к=х Ак(ш) из описания распознаваемого объекта £>(ш) и совокупности описаний преобразований Г(г) с указанием всех таких номеров классов к, для которых соответствующий дизъюнктивный член истинен наш

ад Г(х) Н V ЛИ- (У.З)

к= I

Задача инвариантного анализа сложного объекта. Найти и классифицировать все части т объекта ш, для которых т £ £1, если класс £1к замкнут относительно группы преобразований С* с конечным числом образующих С = {<уь ..., д-р}.

Эта задача сводится к доказательству выводимости формулы

1 из описания распознаваемого объекта Б(и>) и совокупно-

сти описаний преобразований Г(х) с указанием всех частей объекта и, поддающихся классификации, и идентифицировать их

ад Г(а?) Н V Зу*Ак®. (УЛ)

к=1

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

Пусть

\Ак\ ~ количество различных вхождений предметных переменных в описание к-го класса;

гпь - количество различных предметных переменных в описании к-го класса;

|С| максимальное количество различных вхождений предметных переменных в правые части эквивалентностей вида (У.1), задающих описания преобразований;

|5| - количество различных вхождений предметных переменных в описание объекта;

тс - количество различных предметных переменных в правых частях эквивалентностей вида (V. 1), задающих описания преобразований;

Ь - максимальное количество описаний одного элементарного преобразования;

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

Теорема У.2. Если для доказательства следствия формулы Зу^Ак(у) из конечного множества постоянных формул использован алгоритм полного перебора, то число шагов инвариантной идентификации класса, замкнутого относительно группы С с конечным числом образующих С = {<71,Зг} ограничении, что глубина вложенности термов, задающих преобразования из группы С, не превосходит заданного числа В., составляет

0(ТК • Д • |5| ■ (Г* • \Ак\ + Г1' ■ |С| • Ь) + Д • Т*-1 • Я2 ■ (Г* • \Ак\ + Гс • \С\ ■ Ь)).

Пусть

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

я - максимальное количество вхождений одного и того же предиката (только без отрицаний или только с отрицаниями) в описание объекта

ЗД,

<4 - количество дизъюнктов в описании /с-го класса;

<5 - максимальное изменение количества атомарных формул с одним и тем же предикатом (только без отрицаний или только с отрицаниями) в множестве после выполнения п. 5 алгоритма;

с - максимальное количество вхождений атомарных формул в элементарные конъюнкции С](у).

Теорема V.3. Если для доказательства следствия формулы Зу^Ак(у) из конечного множества постоянных формул использован алгоритм поиска вывода в исчислении предикатов, то число шагов инвариантной идентификации класса, замкнутого относительно группы G* с конечным числом образующих G = {gi,---,gr} при ограничении, что глубина вложенности термов, задающих преобразования из группы G*, не превосходит заданного числа R, составляет

0(TR ■{.Jk-{s+R■ df + (s + R■ 6)c).

Приведены примеры построения описаний преобразований.

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

Щ(х) => С'(ф)), (V.5)

где Bj(x) и Cj(gj(x)) - элементарные конъюнкции атомарных формул, I = 1,..., lj.

Если ~Г(х) - множество всех описаний управления, то задача выбора последовательности действий может быть формализована следующим образом.

Задача выбора последовательности действий сводится к нахождению для исходной ситуации и с описанием S'(gj) такой последовательности управлений <7t,,--.,i7tB из заданной совокупности G, что gil(...(giR(u))...) удовлетворяет заданному целевому условию А(х)

S(w) ~Г(х) (= 3уфА{у). (V.6)

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

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

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

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

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

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

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

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

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

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

Доказаны оценки числа шагов решения рассматриваемых задач при использовании двухуровневого описания классов.

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

4. Обоснована возможность построения нейронных сетей и распараллеливания вычислений на основе многоуровневого описания классов.

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

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

5. Введено понятие неполного вывода как средства адаптации распознающей системы к неполной информации и доказаны оценки числа шагов его реализации.

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

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

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

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

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

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

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в журналах, рекомендованных ВАК

[1] Косовская Т.М., Тимофеев A.B. Об одном новом подходе к формированию логических решающих правил - Вестник ЛГУ, 1985, №8. С. 22 27.

[2] Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вести. С.-Петербург, ун-та. Сер. 1. 2007. Вып. 4. С. 82 90.

[31 Косовская Т.М., Тимофеев A.B. Иерархическое описание классов и нейросетевое распознавание сложных образов // Нейрокомпьютеры: разработка, применение. 2007. № G. С. 30-33.

[4] Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых пропозициональными формулами // Вестн. С.-Петербург, унта. Сер. 1. 2008. Вып.1. С. 29-37.

[5] Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестн. С.-Петербург.ун-та. Сер. 10. 2008. Вып.1. С. 64-72.

[6| Косовская Т. М. Частичная выводимость предикатных формул как средство распознавания объектов с неполной информацией // Вестн. С.-Петербург.ун-та. Сер. 10. 2009. Вып. 1. С. 74-84.

[7| Косовская Т.М. Распознавание объектов из классов, замкнутых относительно группы преобразований // Вестн. С.-Петербург.ун-та. Сер. 10. 2009. Вып. 3. С. 45-55.

[8] Косовская Т.М., Косовский Н. К. О числе шагов получения булевого решения у полиномиальных сравнений и у систем из них // Вестн. С.-Петербург, ун-та. Сер. 1. 2007. Вып. 3. С. 84-90.

Другие публикации

[9] Артюшкова (Косовская) Т.М., Тимофеев А.В. Диагностика, прогни-зирование и выбор метода лечения как задача автоматического доказательства теорем // Биологическая и медицинская кибернетика, ч.4, Научный совет по комплексной проблеме «Кибернетика» АН СССР, М., 1974. С. 13-16.

[10] Косовская Т.М. О сложности распознавания контурных изображений с помощью линейных стратегий метода резолюций // Всесоюзная научно-техническая конференция «Образный анализ многомерных данных» (тезисы докладов), 2-3 октября 1984г., Владимир, 1984. С. 77-78.

[11] Косовская Т.М., Мишин С.Н., Тимофеев А.В. Алгоритмы и программы логического анализа изображений и сцен // Всесоюзная научно-техническая конференция «Образный анализ многомерных данных» (тезисы докладов), 2-3 октября 1984г., Владимир, 1984. С.79-80.

[12] Kosovskaya Т.М., Timofeev A.V. Logic-Axiomatical Method of Recognition and its Application // Proceedings of Symposium IFAC on Artificial Intelligence, Leningrad, 4-6 October 1983. IFAC proceedings series No 9, Pergamon Press, 1984. P. 523-528.

[13] Косовская Т.М. Распознавание преобразованных и искаженных изображений // Тезисы докладов Всесоюзного симпозиума «Зрение организмов и роботов» (Вильнюс, 1-3 октября 1985 г.), т. 2, Вильнюс, 1985. С. 59-60.

[14] Kossovskaya Т.М., Timopheev A.V. Logic-Axiomatical Method of Intellectual Recognition of Complex and Distributed Objects // Proceedings of Symposium IFAC « Distributed and Intellectual Systems. Methods and Applications», v. 2, Varna, Bulgaria, 1988.

[15] Kossovskaya T.M., Timopheev A.V. Adaptive Logical Recognition Algorithms for Expert Systems IMS // Third International Summer Seminar on Intelligent Manufacturing Systems (August 28 - September 2), Dubrovnik, Yugoslavia, 1989.

[16] Kossovskaya T.M., Timopheev A.V. Methods of Adaptive Logical Recognition and its Application // International Conference «Artificial

Intelligence - Industrial Application» (Abstracts of papers) (Leningrad, 15-19.04.1990),1990. P. 247-249.

[17] Timofeev A.V., Kosovskaya T.M. Logic-Axiomatical Method of Knowledge Representation and Recognition for Robots // Computers in Industry 15, Elsevier Science Publishers B.V., 1990. P.3-6.

[18] Косовская T.M., Миронов C.H., Тимофеев А.В. Экспертные системы адаптивного логического распознавания и их применение // Адаптивные и экспертные системы в управлении. Тезисы докладов 5-го Ленинградского симпозиума по теории адаптивных систем, ч. II, 1990.

[19] Kossovskaya T.M. Complexity bounds of some pattern recognition problems // Abstrscts of the Second International Conference «Mathematical Algorithms», Nizhny Novgorod, 1995. P.28.

[20] Косовская T.M. Оценки сложности решения задач распознавания при иерархическом описании классов // Тез. докл. на XI Междунар. конф. по проблемам теоретической кибернетики. Ульяновск, 1996.

[21] Косовская Т.М, Многоуровневые описания классов для принятия решений в задачах распознавания образов - Тр. III Междунар. конф. "Дискретные модели в теории управляющих систем". М., Диалог — МГУ, 1998.

[22] Косовская Т.М. Оценки числа шагов решения некоторых задач распознавания образов с логическими описаниями // Материалы IX Международного семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О.Б.Лупанова (Москва, 18-23 июня 2007 г.) , Изд. мех-мат МГУ, М., 2007. С. 94-96.

[23] Т.М.Косовская, А.В.Тимофеев. Иерархическое логическое описание и нейросетевое распознавание сложных образов // Proc. of XIII-th International Conference "Knowledge-Dialogue-Solution"(KDS-2007)(June 18-24, 2007, Varna, Bulgaria), vol. 1, pp. 22-27.

[24] A.Timofeev, T.Kosovskaya. Conditions of Effectiveness of Pattern Recognition Problem Solution Using Logical Level Descriptions of

Classes // Proc. of XIII-th International Conference "Knowledge-Dia-logue-So!ution"(KDS-2007)(June 18-24, 2007,Varna, Bulgaria), vol. 2, pp. 572-575.

[25] Косовская T.M., Тимофеев A.B. Логические и нейросетевые методы распознавания и интеллектуального анализа сложных изображений и сцен // Сборник трудов Международной выставки-конгресса <Ме-хатроника и робототсхника-2007> (М& R'2007). '2-5 октября 2007, Санкт-Петербург, Россия, с. 185-189.

[26] Косовская Т.М. Оценки сложности многоуровневого распознавания объектов с неполной информацией // „Проблемы теоретической кибернетики", Тезисы докладов XV Международной конференции (Казань 2-7 июня 2008 г.), под общей редакцией академика РАН Ю.И.Журавлева. 2008. С. 59-60.

[27] Косовская Т.М. Логико-предикатный подход к распознаванию и анализу составных объектов и оценки сложности // XVII Международная школа-семинар «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова. (Новосибирск, 27 октября - 1 ноября 2008 г.). Новосибирск: Изд-во Института математики, 2008. С. 65-70.

[28] Косовская Т. М. Решение задач распознавания образов при неполной информации об объектах на основе частичной выводимости формул исчисления предикатов // Международная научная конференция „Космос, астрономия, программирование" [Лавровские чтения] (20-22 мая 2008г., математико-механический факультет СПбГУ), Тезисы докладов. С. 58 - 65.

[29] Косовская Т.М., Тимофее

в A.B. Логико-нейросетевые методы распознавания сложных изображений и сцен // Труды международной научно-технической конференции „Многопроцессорные вычислительные и управляющие системы" (МВУС-2009, Россия, Дивно-морское, 28 сентября - 3 октября 2009). С. 121 - 125.

Подписано к печати 23.12.09. Формат 60 х 84 V . Бумага офсетная. Гарнитура Times. Печать цифровая. Печ. л. 2,0. Тираж 100 экз. Заказ 4575.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

Введение.

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

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

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

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

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

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

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

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

Глава II. Оценки числа шагов работы алгоритмов, решающих поставленные задачи.

II. 1. Распознавание объектов при их глобальной характеризации пропозициональными переменными.

11.2. Распознавание объектов при их локальной характеризации предикатными формулами.

11.3. Замечания о связи между оценками числа шагов работы алгоритма, решающего задачу распознавания образов, описанную формулами исчисления предикатов, и соотношением между классами Р и ОТ.

II.4. Пример распознавания объекта с локальными характеристиками и оценки числа шагов.

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

III.1. Многоуровневое описание классов.

111.2. Условия уменьшения числа шагов решения задач распознавания образов, описываемых пропозициональными формулами.

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

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

III.5. Пример применения двухуровневого описания при локальной характеризации объекта.

111.6. Использование многоуровневого описания классов для построения нейронных сетей.

111.7. Многоуровневое описание классов в задачах распознавания образов как средство для параллелизации вычислений.

Глава IV. Адаптация логико-предметной распознающей системы к неполной информации.

IV. 1. Построение неполного вывода как средство адаптации распознающей системы к неполной или недостоверной информации.

IV.2. Оценки числа шагов построения неполного вывода.

IV.3. Распознавание в условиях неполной информации. Построение неполного вывода.

IV.4. Пример распознавания частично заслоненного объекта.

Глава V. Адаптация логико-предметной распознающей системы к преобразованиям, не выводящим из заданного класса.

V.l. Инвариантность к заданному множеству преобразований. Инвариантные признаки и инвариантные описания классов.

V.2. Инвариантные описания классов с неинвариантными признаками

V.3. Задача инвариантного распознавания как задача поиска логического вывода.

V.4. Алгоритм инвариантного распознавания.

V.5. Оценки числа шагов работы алгоритмов инвариантной идентификации

V.6. Примеры инвариантных распознающих систем с неинвариантными признаками.

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

Существенной чертой задач искусственного интеллекта является большая размерность как исходных данных, так и математических описаний поставленных задач. В современной научной литературе имеется достаточно мало работ, посвященных оценке числа шагов решения задач искусственного интеллекта, связанных с конкретным выбором средств их решения. Математические работы, как правило, посвящены доказательству сходимости предложенных алгоритмов [2, 29, 36] или доказательству условий применимости рассматриваемого метода решения задач [12, 13]. Работы, посвященные практической реализации имеющихся алгоритмов, решают конкретные задачи, зачастую используя те или иные эвристики, мало применимые к решению другой конкретной задачи [17].

В то же время усилия многих ученых, работающих в области математических основ информатики, посвящены доказательству не только правильности работы алгоритма, решающего поставленную задачу, но и оценок числа шагов его работы [1, 7, 41]. Это особенно актуально для алгоритмов, решающих задачи искусственного интеллекта, прежде всего в связи с огромным объемом информации, которую необходимо обработать на компьютере.

Особое место занимают задачи, относительно которых доказаны их ЫР-полнота или КР-трудность [7, 41, 42]. Широко распространено мнение, что такие задачи не предназначены для их реализации па компьютере с большим объемом исходных данных в силу огромного времени их решения. Выделение подзадач таких задач, имеющих полиномиальные верхние оценки числа шагов решения, — одно из направлений, имеющих целью выделить границы практической применимости создаваемых моделей [19, 21, 43]. Одним из способов выделения таких подзадач является не только доказательство КР-пол ноты или КР-трудности исходной задачи, но и установление достаточно точных верхних оценок числа шагов алгоритмов, решающих исходную задачу.

Неформальное описание задач распознавания. Под задачей распознавания образов в разной литературе зачастую понимают разные задачи. В частности, в [5] к ним относят, например, следующие.

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

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

Разбиение множества всех объектов на классы (образы), если это не задано в постановке задачи (кластеризация).

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

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

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

Среди задач распознавания можно выделить следующие, рассматриваемые в диссертации.

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

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

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

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

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

Обзор имеющихся результатов по теме диссертации. Первое, с чем сталкивается теория распознавания образов - это выбор набора признаков, на основании которых будет производиться распознавание. В работе [5] определены четыре класса таких признаков: детерминированные (принимающие конкретные числовые значения); вероятностные (случайные значения которых распределены по всем классам объектов); логические (принимающие два значения „истина" или „ложь"); структурные (являющиеся непроизводными элементами структуры объекта).

В соответствии с тем, па языке каких признаков производится описание объектов, системы распознавания могут быть подразделены на детерминированные, вероятностные, логические, структурные и комбинированные [5]. В работах Ю.И. Журавлева [10, 11, 12, 13] и его учеников рассматриваются алгебраические распознающие системы, представляющие собой комбинацию детерминированных и логических систем распознавания.

В каждом из этих подходов описания классов являются аналогом понятия фрейм, введенного Н. Минским [26].

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

Выбор набора признаков может быть обусловлен различными причинами: наилучшее разделение классов [2], наименьшая стоимость измерения признаков (даже до определенной степени в ущерб качеству распознавания) и минимизация количества измерений [14], простота полученных решающих правил [29] и многими другими.

Методы построения рабочего набора признаков по известному исходному набору изложены, например, в [2, 5, 29].

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

В теории построения систем распознавания образов наряду с другими широкое распространение получили и логические методы [30, 13, 15]. Рассматриваемые в литературе логические методы описаний классов сводятся к представлению связей между отдельными признаками объекта в виде булевых функций или булевых уравнений. Решение булевых уравнений равносильно доказательству истинности (или выводимости) формул исчисления высказываний, перед которыми стоят кванторы существования по пропозициональным переменным. Методы получения и представления знаний, в частности, в виде продукций, хорошо приспособленных для доказательства целевых условий методом резолюций, рассмотрены, например, в [3].

Никакие потенциально бесконечные классы объектов, описание которых существенным образом задается формулами исчисления предикатов, с помощью булевых уравнений описать нельзя. В [30] на стр. 550 приведена экспоненциальная оценка числа пропозициональных переменных в пропозициональных формулах, моделирующих формулу исчисления предикатов в конечной области для задач планирования

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

Идея существенного использования исчисления предикатов и построения терма (последовательности функций, воздействующих на объект), задающего последовательность действий в задачах планирования движения, использовалась Нильсоном Н. [27], Хантом Э. [37] и многими другими. Однако применение этих идей к решению задач распознавания образов автору диссертации неизвестны.

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

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

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

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

Решение всех задач, рассматриваемых в диссертации, сведено к решению задач доказательства теорем простого подмножества формул исчисления высказываний и исчисления предикатов [16]. Доказательство таких теорем может быть проведено, например, посредством применения метода резолюций [31, 27, 30] (и даже линейных стратегий метода резолюций [23], или в секвенциальных исчислениях высказываний и предикатов [16, 20]. Поскольку метод резолюций и секвенциальные исчисления хорошо приспособлены для их компьютерной реализации, то оценки числа шагов алгоритмов построения вывода в диссертации приводятся именно для этих методов доказательства.

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

В диссертации рассматривается логико-аксиоматический подход к решению задач распознавания образов, основанный на сведении некоторых задач распознавания образов к задачам поиска вывода в логических исчислениях. Термин „логико-аксиоматический метод решения задач распознавания образов" был предложен совместно автором диссертации и A.B. Тимофеевым ещё в 80-ые годы [45] в связи с тем, что описание класса представляет собой формализацию утверждений об объектах, безусловно истинные для каждого объекта из этого класса и, следовательно, могут рассматриваться как аксиомы этого класса. При этом рассматриваются задачи, в которых объекты могут быть описаны с помощью логических формул. При использовании пропозициональных формул такой подход является достаточно представительным частным случаем логико-алгебраического подхода, подробно обоснованного и развитого в работах Ю.И. Журавлева [13]и его учеников .

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

Логико-предметный подход к решению задач распознавания образов представляется удобным также в случаях, когда параметры распознаваемого объекта имеют интервальный характер или описания объекта содержат взаимоисключающие признаки, например, цвет объекта. В первом случае можно ввести предикат, зависящий дополнительно от трех аргументов х, а, Ь, истинный на тех значениях переменной х, для которых а < х < Ъ. Во втором случае можно рассматривать предикат, дополнительно зависящий от параметра г, являющегося номером соответствующего бинарного признака. Например, если рассматриваемые объекты могут иметь один из девяти цветов (черный, белый и 7 цветов радуги), то для того, чтобы указать, что объект белый, вместо набора значений (0,1,0,0,0,0,0,0,0) достаточно записать р(2).

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

В [45] рассматриваемые в диссертации задачи распознавания образов сведены к задаче проверки выводимости формул описанного ниже вида из заданного множества атомарных формул. В этой работе автору диссертации принадлежит основная идея и детальная проработка подхода, Тимофееву A.B. - общая постановка задачи и научное руководство.

Как уже было сказано, одним из важных направлений в создании алгоритмических моделей решения тех или иных задач является доказательство оценок числа шагов таких алгоритмов. В общей постановке задача проверки истинности (или выполнимости) формул вызывает значительные трудности. Так, например, для исчисления высказываний задача проверки выполнимости формулы в КНФ является МР-полной [7].

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

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

В [64] предложены многоуровневые описания классов, при использовании которых в диссертации доказаны условия уменьшения числа шагов работы алгоритмов, решающих рассматриваемые задачи распознавания образов [47, 49, 69, 65]. Многоуровневые описания классов являются также удобным средством анализа составных сложных объектов.

Введение предикатов различных уровней оказалось полезным при создании искусственных нейронных сетей [48, 67].

Диссертация состоит из введения и пяти глав. Во введении изложена содержательная постановка задач распознавания образов, рассматри

ЗАКЛЮЧЕНИЕ

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

1. Доказаны оценки числа шагов алгоритмов решения задач распознавания:

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

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

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

Доказаны оценки числа шагов решения рассматриваемых задач при использовании двухуровневого описания классов.

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

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

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

Показано, что многоуровневые описания классов обеспечивают естественное распараллеливание вычислений, отличное от классического И/ИЛИ параллелизма.

4. Неполный вывод как средство адаптации распознающей системы к неполной информации и оценки числа шагов его реализации.

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

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

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

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

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

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Васильев В.И. Конструирование пространства в процессе обучения распознаванию образов // Автоматика, 1982, № 5. С. 18-27.

3. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПБ: Питер, 2000. 384 с.

4. Горелик А.Л. Об одном подходе к выбору пространства признаков, используемого при построении системы распознавания объектов и являний // Кибернетика, 1972, № 4. С. 142-146.

5. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1984. 208 с.

6. Гузман А. Декомпозиция зрительных сцен // Интегральные роботы, вып.1, М: Мир, 1973.

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

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

9. Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977. 128 с.

10. Журавлёв Ю.И. Алгебраический подход к проблеме распознавания // Проблемы кибернетики, 1978, вып. 33. С. 35-43.

11. Журавлёв Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов // Кибернетика: I, 1977, №4. С. 14-21; II, 1977, № 6. С. 21-27; III, 1978, № 2. С. 35-43.

12. Журавлёв Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. 1989. М.: Наука. С. 9-16.I

13. Журавлёв Ю.И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах) // Журнал вычислительной математики и математической физики, 2002, т. 42, № 9. С. 1425-1435.

14. Загоруйко Н.Г. Прикладные методы анализа данных и знаний — Новосибирск: Изд-во Ин-та математики, 1999. 270 с.

15. Закревский А.Д. Выявление импликативных закономерностей в булевом пространстве признаков и распознавание образов // Кибернетика, 1982, № 1. С. 1-6.

16. Клини С. Математическая логика. — М.: Мир, 1973. 480 с.

17. Козлов В.Н. Элементы математической теории зрительного восприятия — М.: Издательство Центра прикладных исследований при механико-математическом факультете МГУ, 2001. 128 с.

18. Комашинский В.И., Смирнов Д.А. Нейронные сети и их применение в системах управления и связи. М.: Горячая линия Телеком, 2002. 94 с.

19. Косовская Т.М., Косовский H. К. Об эффективности получения бу-левого решения у полиномиальных сравнений и у систем из них // Матер. IX Междунар.семинара «Дискретная математика и ее приложения», МГУ. 2007. С. 97 99.

20. Косовский Н.К. Элементы математической логики и её приложения к теории субрекурсивных алгоритмов. Л.: изд-во ЛГУ, 1981. 192 с.

21. Косовский Н.К., Косовская Т.М. Полиномиальность и NP-трудность задачи вычисления знака постоянного терма // Математические вопросы кибернетики. Вып.16. 2007. С. 125 128.

22. Круглов В.В. Борисов В.В. Искусственные нейронные сети. Теория и практика. М.: Горячая линия Телеком, 2002. 382 с.

23. Курьеров Ю.Н. Условия полноты тактики линейного вывода // Семантические вопросы искусственного интеллекта. Киев, 1977. С. 4445.

24. Леденева Т.М., Подвальный C.B., Васильев В.И. Системы искусственного интеллекта и принятия решений: Учебное пособие. Уфа: УГАТУ, 2005. 206 с.

25. Маслов С.Ю. Связь между тактиками обратного метода и метода резолюций // Записки научных семинаров ЛОМИ АН СССР, т. 16, 1969. С. 137-146.

26. Минский Н. Фреймы для представления знаний. М.: Энергия, 1979. 152 с.

27. Нильсон Н. Искусственный интеллект. М.: Мир, 1973. 270 с.

28. Пулатов A.M., Никифоров A.C. Справочник по семиотике нервных болезней. Ташкент: Медицина, 1983. 200 с.

29. Пшибихов В.Н., Тимофеев A.B. Полные системы логических разделяющих функций и оптимальные опознающие графы // Методы вычислений. Л., 1973, № 7. С. 36-46.

30. Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ. М.: Издательский дом "Вильяме", 2006. 1408 с.

31. Робинсон Дж. Машинно ориентированная логики, основанная на методе резолюций // Кибернетический сборник, новая серия. М., 1970, вып. 7. С. 194-218.

32. Соловьев H.A. Тесты. Новосибирск, 1979. 189 с.

33. Тимофеев A.B. Математическая модель инвариантного восприятия и опознания по группам преобразования // Кибернетика и вычислительная техника. Киев: Наукова думка, 1973. С. 48-54.

34. Тимофеев A.B. Адаптивная система логического вывода и оптимальные опознающие графы // Вопросы кибернетики. Адаптация в системах со сложной организацией. М.: Научный совет по комплексной проблеме „Кибернетика" АН СССР, 1977. С. 33-35.

35. Тимофеев A.B. Управление роботами. Л.: Изд-во Ленингр. ун-та. 1986. 240 с.

36. Фомин В.Н. Математическая теория обучаемых опознающих систем. Л., 1976. 235 с.

37. Хант Э. Искусственный интеллект. — М.: Мир, 1978. 558 с.

38. Шмидт А.А. Построение полных систем непрерывных инвариантов для некоторого класса групп преобразований изображений // Деп. в ВИНТИ, 6879-83, 1983.

39. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов. 2-е изд., перераб. и доп. - М.: Наука,-1986. 384 с.

40. Яблонский С.В. Тест // Математическая энциклопедия, т.5, М.: „Советская энциклопедия", 1985. С. 342-346.

41. Du D.-Z., Ко K.-I. Theory of Computational Complexity. A Wiley-Interscience Publication. John Wiley & Sons, Inc. 2000. 491p.

42. Johnson D. The NP-completeness column // ACM Trans. Algorithms 1(2005) No 1, 160-176.

43. Wang Lusheng, Zhao Нао, Dong Guozhu, Li Jianping. On the complexity of finding emergin patterns // Theor. comput. Sci. 2005, 335, N 1. P. 15-27.

44. РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

45. Статьи в журналах, рекомендованных ВАК,

46. Косовская Т.М., Тимофеев A.B. Об одном новом подходе к формированию логических решающих правил Вестник ЛГУ, 1985, №8. С. 22-27.

47. Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестн. С.-Петербург.ун-та. Сер. 1. 2007. Вып.(4) С. 82-90.

48. Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых пропозициональными формулами // Вестн. С.-Петербург, унта. Сер. 1. 2008. Вып.1. С. 29-37.

49. Косовская Т.М., Тимофеев A.B. Иерархическое описание классов и нейросетевое распознавание сложных образов // Нейрокомпьютеры: разработка, применение. 2007. № 6. С. 30-33.

50. Косовская Т.М. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестн. С.-Петербург.ун-та. Сер. 10. 2008. Вып.1. С. 64-72.

51. Косовская Т. М. Частичная выводимость предикатных формул как средство распознавания объектов с неполной информацией // Вестн. С.-Петербург.ун-та. Сер. 10. 2009. Вып. 1. С. 74-84.

52. Косовская Т.М. Распознавание объектов из классов, замкнутых относительно группы преобразований // Вестн. С.-Петербург.ун-та. Сер. 10. 2009. Вып. 3. С. 45-55.

53. Косовская Т.М., Косовский Н. К. О числе шагов получения булевого решения у полиномиальных сравнений и у систем из них // Вестн. С.-Петербург, ун-та. Сер. 1. 2007. Вып. 3. С. 84-90.1. Другие публикации

54. Косовская Т.М., Мишин С.Н., Тимофеев A.B. Алгоритмы и программы логического анализа изображений и сцен // Всесоюзная научно-техническая конференция «Образный анализ многомерных данных» (тезисы докладов), 2-3 октября 1984г., Владимир, 1984. С.79-80.

55. Kosovskaya Т.М., Timofeev A.V. Logic-Axiomatical Method of Recognition and its Application // Proceedings of Symposium IFAC on

56. Artificial Intelligence, Leningrad, 4-6 October 1983. IFAC proceedings series No 9, Pergamon Press, 1984. P. 523-528.

57. Косовская T.M. Распознавание преобразованных и искаженных изображений // Тезисы докладов Всесоюзного симпозиума «Зрение организмов и роботов» (Вильнюс, 1-3 октября 1985 г.), т. 2, Вильнюс, 1985. С. 59-60.

58. Kossovskaya Т.М., Timopheev A.V. Logic-Axiomatical Method of Intellectual Recognition of Complex and Distributed Objects // Proceedings of Symposium IFAC « Distributed and Intellectual Systems. Methods and Applications», v. 2, Varna, Bulgaria, 1988.

59. Kossovskaya T.M., Timopheev A.V. Adaptive Logical Recognition Algorithms for Expert Systems IMS // Third International Summer Seminar on Intelligent Manufacturing Systems (August 28 September 2), Dubrovnik, Yugoslavia, 1989.

60. Kossovskaya T.M., Timopheev A.V. Methods of Adaptive Logical Recognition and its Application // International Conference «Artificial Intelligence Industrial Application» (Abstracts of papers) (Leningrad, 15-19.04.1990),1990. P. 247-249.

61. Timofeev A.V., Kosovskaya T.M. Logic-Axiomatical Method of Knowledge Representation and Recognition for Robots // Computers in Industry 15, Elsevier Science Publishers B.V., 1990. P.3-6.

62. Косовская T.M., Миронов C.H., Тимофеев A.B. Экспертные системы адаптивного логического распознавания и их применение // Адаптивные и экспертные системы в управлении. Тезисы докладов 5-го

63. Ленинградского симпозиума по теории адаптивных систем, ч. II, 1990.

64. Kossovskaya Т.М. Complexity bounds of some pattern recognition problems // Abstrscts of the Second International Conference «Mathematical Algorithms», Nizhny Novgorod, 1995. P.28.

65. Косовская Т.М. Оценки сложности решения задач распознавания при иерархическом описании классов // Тез. докл. на XI Междунар. конф. по проблемам теоретической кибернетики. Ульяновск, 1996.

66. Косовская Т.М. Многоуровневые описания классов для принятия решений в задачах распознавания образов Тр. III Междунар. конф. "Дискретные модели в теории управляющих систем". М., Диалог — МГУ, 1998.

67. Т.М.Косовская, А.В.Тимофеев. Иерархическое логическое описание и нейросетевое распознавание сложных образов // Proc. of XIII-th International Conference "Knowledge-Dialogue-Solution"(KDS-2007)(June 18-24, 2007, Varna, Bulgaria), vol. 1, pp. 22-27.

68. A.Timofeev, T.Kosovskaya. Conditions of Effectiveness of Pattern Recognition Problem Solution Using Logical Level Descriptions of

69. Classes // Proc. of XIII-th International Conference "Knowledge-Dia-logue-Solution"(KDS-2007) ( June 18-24, 2007,Varna, Bulgaria), vol. 2, pp. 572-575.